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]

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]

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]

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]