Search

Given a lattice L in the plane, we define the affiliated deep hole lattice H(L) to be spanned by a shortest vector of L and a deep hole of L contained in the triangle with sides corresponding to the shortest basis vectors. We study the geometric and arithmetic properties of deep hole lattices. In particular we investigate conditions on L under which H(L) is well-rounded and prove that H(L) is defined over the same field as L. For the period lattice corresponding to an isomorphism class of elliptic curves, we produce a finite sequence of deep hole lattices ending with a well-rounded lattice which corresponds to a point on the boundary arc of the fundamental strip under the action of SL 2 (Z) on the upper halfplane. In the case of CM elliptic curves, we prove that all elliptic curves generated by this sequence are isogenous to each other and produce bounds on the degree of isogeny. Finally, we produce a counting estimate for the planar lattices with a prescribed deep hole lattice. [ABSTRACT FROM AUTHOR]

We give a new deterministic construction of integer sensing matrices that can be used for the recovery of integer-valued signals in compressed sensing. This is a family of n × d integer matrices, d ≥ n , with bounded sup-norm and the property that no ℓ column vectors are linearly dependent, ℓ ≤ n . Further, if ℓ ≤ o (log n) then d / n → ∞ as n → ∞ . Our construction comes from particular sets of difference vectors of point-sets in R n that cannot be covered by few parallel hyperplanes. We construct examples of such sets on the 0 , ± 1 grid and use them for the matrix construction. We also show a connection of our constructions to a simple version of the Tarski's plank problem. [ABSTRACT FROM AUTHOR]

We consider multivariable polynomials over a fixed number field, linear in some of the variables. For a system of such polynomials satisfying certain technical conditions we prove the existence of search bounds for simultaneous zeros with respect to height. For a single such polynomial, we prove the existence of search bounds with respect to height for zeros lying outside of a prescribed algebraic set. We also obtain search bounds in the case of homogeneous multilinear polynomials, which are related to a so-called "sparse" version of Siegel's lemma. Among the tools we develop are height inequalities that are of some independent interest. [ABSTRACT FROM AUTHOR]

Let L be a full-rank lattice in ℝd and write L+ for the semigroup of all vectors with nonnegative coordinates in L. We call a basis X for L positive if it is contained in L+. There are infinitely many such bases, and each of them spans a conical semigroup S(X) consisting of all nonnegative integer linear combinations of the vectors of X. Such S(X) is a sub-semigroup of L+, and we investigate the distribution of the gaps of S(X) in L+, i.e. the points in L+ ∖ S(X). We describe some basic properties and counting estimates for these gaps. Our main focus is on the restrictive successive minima of L+ and of L+ ∖ S(X), for which we produce bounds in the spirit of Minkowski's successive minima theorem and its recent generalizations. We apply these results to obtain analogous bounds for the successive minima with respect to Weil heights of totally positive sub-semigroups of ideals in totally real number fields. [ABSTRACT FROM AUTHOR]

Given a primitive collection of vectors in the integer lattice, we count the number of ways it can be extended to a basis by vectors with sup-norm bounded by T, producing an asymptotic estimate as T \to \infty. This problem can be interpreted in terms of unimodular matrices, as well as a representation problem for a class of multilinear forms. In the 2-dimensional case, this problem is also connected to the distribution of Farey fractions. As an auxiliary lemma we prove a counting estimate for the number of integer lattice points of bounded sup-norm in a hyperplane in \mathbb R^n. Our main result on counting basis extensions also generalizes to arbitrary lattices in \mathbb R^n. Finally, we establish some basic properties of sparse representations of integers by multilinear forms. [ABSTRACT FROM AUTHOR]

Nearly orthogonal lattices were formally defined in [4] , where their applications to image compression were also discussed. The idea of "near orthogonality" in 2-dimensions goes back to the work of Gauss. In this paper, we focus on well-rounded nearly orthogonal lattices in R n and investigate their geometric and optimization properties. Specifically, we prove that the sphere packing density function on the space of well-rounded lattices in dimension n ≥ 3 does not have any local maxima on the nearly orthogonal set and has only one local minimum there: at the integer lattice Z n. Further, we show that the nearly orthogonal set cannot contain any perfect lattices for n ≥ 3 , although it contains multiple eutactic (and even strongly eutactic) lattices in every dimension. This implies that eutactic lattices, while always critical points of the packing density function, are not necessarily local maxima or minima even among the well-rounded lattices. We also prove that a (weakly) nearly orthogonal lattice in R n contains no more than 4 n − 2 minimal vectors (with any smaller even number possible) and establish some bounds on coherence of these lattices. [ABSTRACT FROM AUTHOR]

Given an isotropic quadratic form over a number field which assumes a value t , we investigate the distribution of points at which this value is assumed. Building on the previous work about the distribution of small-height zeros of quadratic forms, we produce bounds on height of points outside of some algebraic sets in a quadratic space at which the form assumes the value t. Our bounds on height are explicit in terms of the heights of the form, the space, the algebraic set and the value t. [ABSTRACT FROM AUTHOR]

Abstract Compressed sensing is a relatively new mathematical paradigm that shows a small number of linear measurements are enough to efficiently reconstruct a large dimensional signal under the assumption the signal is sparse. Applications for this technology are ubiquitous, ranging from wireless communications to medical imaging, and there is now a solid foundation of mathematical theory and algorithms to robustly and efficiently reconstruct such signals. However, in many of these applications, the signals of interest do not only have a sparse representation, but have other structure such as lattice-valued coefficients. While there has been a small amount of work in this setting, it is still not very well understood how such extra information can be utilized during sampling and reconstruction. Here, we explore the problem of integer sparse reconstruction, lending insight into when this knowledge can be useful, and what types of sampling designs lead to robust reconstruction guarantees. We use a combination of combinatorial, probabilistic and number-theoretic methods to discuss existence and some constructions of such sensing matrices with concrete examples. We also prove sparse versions of Minkowski’s Convex Body and Linear Forms theorems that exhibit some limitations of this framework. [ABSTRACT FROM AUTHOR]

Let Λ ⊂ ℝn be an algebraic lattice coming from a projective module over the ring of integers of a number field K. Let Z ⊂ ℝn be the zero locus of a finite collection of polynomials such that Λ ... Z or a finite union of proper full-rank sublattices of Λ. Let K1 be the number field generated over K by coordinates of vectors in Λ, and let L1, ..., Lt be linear forms in n variables with algebraic coefficients satisfying an appropriate linear independence condition over K1. For each ε > 0 and a ∈ ℝn, we prove the existence of a vector x ∈ Λ \Z of explicitly bounded sup-norm such that ∥Li(x) - ai∥ < ε for each 1 ≤ i ≤ t, where ∥ ∥ stands for the distance to the nearest integer. The bound on sup-norm of x depends on ε, as well as on Λ, K, Z, and heights of linear forms. This presents a generalization of Kronecker's approximation theorem, establishing an effective result on density of the image of Λ\Z under the linear forms L1, ..., Lt in the t-torus ℝt/ℤt. [ABSTRACT FROM AUTHOR]

This note supplies additions to our paper quoted in the title on integral spans of tight frames in Euclidean spaces. In that previous paper, we considered the case of an equiangular tight frame (ETF), proving that if its integral span is a lattice then the frame must be rational, but overlooking a simple argument in the reverse direction. Thus our first result here is that the integral span of an ETF is a lattice if and only if the frame is rational. Further, we discuss conditions under which such lattices are eutactic and perfect and, consequently, are local maxima of the packing density function in the dimension of their span. In particular, the unit ( 276 , 23 ) equiangular tight frame is shown to be eutactic and perfect. More general tight frames and their norm-forms are considered as well, and definitive results are obtained in dimensions two and three. [ABSTRACT FROM AUTHOR]

We investigate similarity classes of arithmetic lattices in the plane. We introduce a natural height function on the set of such similarity classes, and give asymptotic estimates on the number of all arithmetic similarity classes, semi-stable arithmetic similarity classes, and well-rounded arithmetic similarity classes of bounded height as the bound tends to infinity. We also briefly discuss some properties of the j-invariant corresponding to similarity classes of planar lattices. [ABSTRACT FROM AUTHOR]

We consider the set of all linear combinations with integer coefficients of the vectors of a unit equiangular tight ( k , n ) frame and are interested in the question whether this set is a lattice, that is, a discrete additive subgroup of the k -dimensional Euclidean space. We show that this is not the case if the cosine of the angle of the frame is irrational. We also prove that the set is a lattice for n = k + 1 and that there are infinitely many k such that a lattice emerges for n = 2 k . We dispose of all cases in dimensions k at most 9. In particular, we show that a (7,28) frame generates a strongly eutactic lattice and give an alternative proof of Roland Bacher's recent observation that this lattice is perfect. [ABSTRACT FROM AUTHOR]

Let K be a global field or , let F be a nonzero quadratic form on KN with N ≥ 2, and let V be a subspace of KN.We prove the existence of an infinite collection of finite families of small-height maximal totally isotropic subspaces of (V, F) such that each such family spans V as a K-vector space. This result generalizes and extends a well known theorem of Vaaler [16] and further contributes to the effective study of quadratic forms via height in the general spirit of Cassels' theorem on small zeros of quadratic forms. All bounds on the height are explicit. [ABSTRACT FROM AUTHOR]

We consider the well-known Rosenbloom–Tsfasman function field lattices in the special case of Hermitian function fields. We show that in this case the resulting lattices are generated by their minimal vectors, provide an estimate on the total number of minimal vectors, and derive properties of the automorphism groups of these lattices. Our study continues previous investigations of lattices coming from elliptic curves and finite Abelian groups. The lattices we are faced with here are more subtle than those considered previously, and the proofs of the main results require the replacement of the existing linear algebra approaches by deep results of Gerhard Hiss on the factorization of functions with particular divisor support into lines and their inverses. [ABSTRACT FROM AUTHOR]

We say that a Euclidean lattice in R n is permutation invariant if its automorphism group has non-trivial intersection with the symmetric group S n , i.e., if the lattice is closed under the action of some non-identity elements of S n . Given a fixed element τ ∈ S n , we study properties of the set of all lattices closed under the action of τ : we call such lattices τ -invariant . These lattices naturally generalize cyclic lattices introduced by Micciancio (2002, 2007), which we previously studied in Fukshansky and Sun (2014). Continuing our investigation, we discuss some basic properties of permutation invariant lattices, in particular proving that the subset of well-rounded lattices in the set of all τ -invariant lattices in R n has positive co-dimension (and hence comprises zero proportion) for all τ different from an n -cycle. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of lattices generated by finite Abelian groups. Special species of such lattices arise in the exploration of elliptic curves over finite fields. In the case where the generating group is cyclic, they are also known as the Barnes lattices. It is shown that for every finite Abelian group with the exception of the cyclic group of order four these lattices have a basis of minimal vectors. Another result provides an improvement of a recent upper bound by M. Sha for the covering radius in the case of the Barnes lattices. Also discussed are properties of the automorphism groups of these lattices. [ABSTRACT FROM AUTHOR]

Let F be a quadratic form in N ≥ 2 variables defined on a vector space V ⊆ KN over a global field K, and Ƶ ⊆ KN be a finite union of varieties defined by families of homogeneous polynomials over K. We show that if V \ Ƶ contains a nontrivial zero of F, then there exists a linearly independent collection of small-height zeros of F in V \ Ƶ, where the height bound does not depend on the height of Ƶ, only on the degrees of its defining polynomials. As a corollary of this result, we show that there exists a small-height maximal totally isotropic subspace W of the quadratic space (V, F) such that W is not contained in Ƶ. Our investigation extends previous results on small zeros of quadratic forms, including Cassels' theorem and its various generalizations. The paper also contains an appendix with two variations of Siegel's lemma. All bounds on height are explicit. [ABSTRACT FROM AUTHOR]

Cyclic lattices are sublattices of $$\mathbb Z^N$$ that are preserved under the rotational shift operator. Cyclic lattices were introduced by Micciancio (FOCS, IEEE Computer Society, pp 356-365, ) and their properties were studied in the recent years by several authors due to their importance in cryptography. In particular, Peikert and Rosen (Theory of Cryptography, Lecture Notes in Computer Science, vol 3876. Springer, Berlin, pp 145-166, ) showed that on cyclic lattices in prime dimensions, the shortest independent vectors problem SIVP reduces to the shortest vector problem SVP with a particularly small loss in approximation factor, as compared to general lattices. In this paper, we further investigate geometric properties of cyclic lattices, proving that a positive proportion of them in every dimension is well-rounded. One implication of our main result is that SVP is equivalent to SIVP on a positive proportion of cyclic lattices in every dimension. As an example, we demonstrate an explicit construction of a family of cyclic lattices on which this equivalence holds. To conclude, we introduce a class of sublattices of $$\mathbb Z^N$$ closed under the action of subgroups of the permutation group $$S_N$$ , which are a natural generalization of cyclic lattices, and show that our results extend to all such lattices closed under the action of any $$N$$ -cycle. [ABSTRACT FROM AUTHOR]

Abstract: In their well known book [6] Tsfasman and Vladut introduced a construction of a family of function field lattices from algebraic curves over finite fields, which have asymptotically good packing density in high dimensions. In this paper we study geometric properties of lattices from this construction applied to elliptic curves. In particular, we determine the generating sets, conditions for well-roundedness and a formula for the number of minimal vectors. We also prove a bound on the covering radii of these lattices, which improves on the standard inequalities. [Copyright &y& Elsevier]

We investigate the properties of the zeta-function of well-rounded sublattices of a fixed arithmetic lattice in the plane. In particular, we show that this function has abscissa of convergence at s = 1 with a real pole of order 2, improving upon a result of Stefan Kühnlein. We use this result to show that the number of well-rounded sublattices of a planar arithmetic lattice of index less than or equal to N is O(N logN) as N → ∞. To obtain these results, we produce a description of integral well-rounded sublattices of a fixed planar integral well-rounded lattice and investigate convergence properties of a zeta-function of similarity classes of such lattices, building on the results of a paper by Glenn Henshaw, Philip Liao, Matthew Prince, Xun Sun, Samuel Whitehead, and the author. [ABSTRACT FROM AUTHOR]

We study well-rounded lattices which come from ideals in quadratic number fields, gen-eralizing some recent results of the first author with Petersen [On ideal well-rounded lattices, Int. J. Number Theory 8(1) (2002) 189-206]. In particular, we give a character-ization of ideal well-rounded lattices in the plane and show that a positive proportion of real and imaginary quadratic number fields contains ideals giving rise to well-rounded lattices. [ABSTRACT FROM AUTHOR]

We study well-rounded lattices which come from ideals in quadratic number fields, generalizing some recent results of the first author with Petersen [On ideal well-rounded lattices, Int. J. Number Theory 8(1) (2002) 189-206]. In particular, we give a characterization of ideal well-rounded lattices in the plane and show that a positive proportion of real and imaginary quadratic number fields contains ideals giving rise to well-rounded lattices. [ABSTRACT FROM AUTHOR]

We investigate distribution of integral well-rounded lattices in the plane, parameterizing the set of their similarity classes by solutions of the family of Pell-type Diophantine equations of the form x+ Dy= z where D>0 is squarefree. We apply this parameterization to the study of the greatest minimal norm and the highest signal-to-noise ratio on the set of such lattices with fixed determinant, also estimating cardinality of these sets (up to rotation and reflection) for each determinant value. This investigation extends previous work of the first author in the specific cases of integer and hexagonal lattices and is motivated by the importance of integral well-rounded lattices for discrete optimization problems. We briefly discuss an application of our results to planar lattice transmitter networks. [ABSTRACT FROM AUTHOR]

Abstract: Let and let be relatively prime integers. The Frobenius number of this -tuple is defined to be the largest positive integer that has no representation as where are nonnegative integers. More generally, the-Frobenius number is defined to be the largest positive integer that has precisely distinct representations like this. We use techniques from the geometry of numbers to give upper and lower bounds on the -Frobenius number for any nonnegative integer . [Copyright &y& Elsevier]

Abstract: We find sharp absolute constants and with the following property: every well-rounded lattice of rank 3 in a Euclidean space has a minimal basis so that the solid angle spanned by these basis vectors lies in the interval . In fact, we show that these absolute bounds hold for a larger class of lattices than just well-rounded, and the upper bound holds for all. We state a technical condition on the lattice that may prevent it from satisfying the absolute lower bound on the solid angle, in which case we derive a lower bound in terms of the ratios of successive minima of the lattice. We use this result to show that among all spherical triangles on the unit sphere in with vertices on the minimal vectors of a lattice, the smallest possible area is achieved by a configuration of minimal vectors of the (normalized) face centered cubic lattice in . Such spherical configurations come up in connection with the kissing number problem. [ABSTRACT FROM AUTHOR]

Abstract: We produce an explicit parameterization of well-rounded sublattices of the hexagonal lattice in the plane, splitting them into similarity classes. We use this parameterization to study the number, the greatest minimal norm, and the highest signal-to-noise ratio of well-rounded sublattices of the hexagonal lattice of a fixed index. This investigation parallels earlier work by Bernstein, Sloane, and Wright where similar questions were addressed on the space of all sublattices of the hexagonal lattice. Our restriction is motivated by the importance of well-rounded lattices for discrete optimization problems. Finally, we also discuss the existence of a natural combinatorial structure on the set of similarity classes of well-rounded sublattices of the hexagonal lattice, induced by the action of a certain matrix monoid. [ABSTRACT FROM AUTHOR]

Abstract: Text: Let K be a number field, , or the field of rational functions on a smooth projective curve over a perfect field, and let V be a subspace of , . Let be a union of varieties defined over K such that . We prove the existence of a point of small height in , providing an explicit upper bound on the height of such a point in terms of the height of V and the degree of a hypersurface containing , where dependence on both is optimal. This generalizes and improves upon the results of Fukshansky (2006) . As a part of our argument, we provide a basic extension of the function field version of Siegel''s lemma (Thunder, 1995) to an inequality with inhomogeneous heights. As a corollary of the method, we derive an explicit lower bound for the number of algebraic integers of bounded height in a fixed number field. Video: For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=R-o6lr8s0Go. [Copyright &y& Elsevier]

Abstract: Text: A lattice is called well-rounded if its minimal vectors span the corresponding Euclidean space. In this paper we study the similarity classes of well-rounded sublattices of . We relate the set of all such similarity classes to a subset of primitive Pythagorean triples, and prove that it has the structure of a non-commutative infinitely generated monoid. We discuss the structure of a given similarity class, and define a zeta function corresponding to each similarity class. We relate it to Dedekind zeta of , and investigate the growth of some related Dirichlet series, which reflect on the distribution of well-rounded lattices. We also construct a sequence of similarity classes of well-rounded sublattices of , which gives good circle packing density and converges to the hexagonal lattice as fast as possible with respect to a natural metric we define. Finally, we discuss distribution of similarity classes of well-rounded sublattices of in the set of similarity classes of all well-rounded lattices in . Video: For a video summary of this paper, please visit http://www.youtube.com/watch?v=q3LJV4lv0PA. [Copyright &y& Elsevier]

Abstract: A lattice is called well-rounded if its minimal vectors span the corresponding Euclidean space. In this paper we completely describe well-rounded full-rank sublattices of , as well as their determinant and minima sets. We show that the determinant set has positive density, deriving an explicit lower bound for it, while the minima set has density 0. We also produce formulas for the number of such lattices with a fixed determinant and with a fixed minimum. These formulas are related to the number of divisors of an integer in short intervals and to the number of its representations as a sum of two squares. We investigate the growth of the number of such lattices with a fixed determinant as the determinant grows, exhibiting some determinant sequences on which it is particularly large. To this end, we also study the behavior of the associated zeta function, comparing it to the Dedekind zeta function of Gaussian integers and to the Solomon zeta function of . Our results extend automatically to well-rounded sublattices of any lattice , where A is an element of the real orthogonal group . [Copyright &y& Elsevier]

Let N ≥ 2 be an integer, F a quadratic form in N variables over $\overline{\mathbb{Q}}$, and $Z \subseteq \overline{\mathbb{Q}}^N$ an L-dimensional subspace, 1 ≤ L ≤ N. We prove the existence of a small-height maximal totally isotropic subspace of the bilinear space (Z,F). This provides an analogue over $\overline{\mathbb{Q}}$ of a well-known theorem of Vaaler proved over number fields. We use our result to prove an effective version of Witt decomposition for a bilinear space over $\overline{\mathbb{Q}}$. We also include some related effective results on orthogonal decomposition and structure of isometries for a bilinear space over $\overline{\mathbb{Q}}$. This extends previous results of the author over number fields. All bounds on height are explicit. [ABSTRACT FROM AUTHOR]

Abstract: Let K be a number field, and let W be a subspace of , . Let be subspaces of of dimension less than dimension of W. We prove the existence of a point of small height in , providing an explicit upper bound on the height of such a point in terms of heights of W and . Our main tool is a counting estimate we prove for the number of points of a subspace of inside of an adelic cube. As corollaries to our main result we derive an explicit bound on the height of a nonvanishing point for a decomposable form and an effective subspace extension lemma. [Copyright &y& Elsevier]

Given a quadratic form and M linear forms in N+1 variables with coefficients in a number field K, suppose that there exists a point in KN+1 at which the quadratic form vanishes and all the linear forms do not. Then we show that there exists a point like this of relatively small height. This generalizes a result of D.W. Masser. [Copyright &y& Elsevier]

Let F (x) be a homogeneous polynomial in n ≥ 1 variables of degree 1 ≤ d ≤ n with integer coefficients so that its degree in every variable is equal to 1. We give some sufficient conditions on F to ensure that for every integer b there exists an integer vector a such that F (a) = b . The conditions provided also guarantee that the vector a can be found in a finite number of steps. [ABSTRACT FROM AUTHOR]

A correction to the article "On the Geometry of Cyclic Lattices," that appeared in the April 22, 2015 issue is presented

We consider lattices generated by finite Abelian groups. We prove that such a lattice is strongly eutactic, which means the normalized minimal vectors of the lattice form a spherical 2-design, if and only if the group is of odd order or if it is a power of the group of order 2. This result also yields a criterion for the appropriately normalized minimal vectors to constitute a uniform normalized tight frame. Further, our result combined with a recent theorem of R. Bacher produces (via the classical Voronoi criterion) a new infinite family of extreme lattices. Additionally, we investigate the structure of the automorphism groups of these lattices, strengthening our previous results in this direction. [ABSTRACT FROM AUTHOR]