Search

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]

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]

We present a new family of one-coincidence sequence sets suitable for frequency hopping code division multiple access (FH-CDMA) systems with dispersed (low density) sequence elements. These sets are derived from one-coincidence prime sequence sets, such that for each one-coincidence prime sequence set there is a new one-coincidence set comprised of sequences with dispersed sequence elements, required in some circumstances, for FH-CDMA systems. Getting rid of crowdedness of sequence elements is achieved by doubling the size of the sequence element alphabet. In addition, this doubling process eases control over the distance between adjacent sequence elements. Properties of the new sets are discussed. [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 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]

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 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]

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]