diameter of Voronoi cell of the lattice ? What about R^n ? What about small n =2,3,4 ?What about random lattice ? - MathOverflow

diameter of Voronoi cell of the lattice ? What about R^n ? What about small n =2,3,4 ?What about random lattice ?

2011-05-02T11:41:14Z

Consider a lattice in R^n. Consider Voronoi cell of it. What is known about diameter ? About the shape ? What are good references ?

As far as I understand they are not easy to compute.

May be in small dimensions like 2,3,4 there are some manageable results ?

Is there something known about diameter of the random lattice ? (e.g. components of generating vectors are distributed as N(0,1) )

Answer by Will Jagy for diameter of Voronoi cell of the lattice ? What about R^n ? What about small n =2,3,4 ?What about random lattice ?

2011-05-03T21:57:36Z

Alex, the covering radius of a lattice is the circumradius of the Voronoi cell around the origin. For a lattice, all Voronoi cells are translates of each other. The points on the boundary of the Voronoi cell that achieve that maximum distance from the origin are called the deep holes. Let's see, the Voronoi cell around the origin is the set of points that are closer to the origin, or no farther away from the origin, than to any other lattice point. So, in $R^2,$ for the standard hexagonal circle packing the cell is a regular hexagon, which you can easily draw by hand. The covering radius is then the distance from the origin to a vertex of the hexagon. For a slightly skewed lattice and slightly irregular (but centrally symmetric) hexagon, the covering radius would be the distance to the farthest vertex from the origin. This is mostly from chapter 2 of SLG, which is Sphere Packings, Lattices and Groups by J. H. Conway and N. J. A. Sloane. Let's see, for the standard integer lattice in $R^2$ the cell would be a square.

It is known that calculating the Voronoi cell, deep holes, and in particular covering radius is NP-hard, the number of steps required grows exponentially with the dimension $n.$ The great advance in the LLL algorithm is that it finds fairly short vectors, where the steps grow only as a polynomial in $n.$ And of course, for very small $n,$ it finds the shortest vector. Meanwhile, the algorithm finds an entire basis, so the comments about possible minimality refer to the first reported vector in the (integral) basis. A full basis is a different problem from a single short vector, in dimension 100 you would usually rather have a basis of all medium length vectors than a single very short one and 99 long ones.

Perhaps this will help, there is a useful language called Magma that has this, see here

Meanwhile, for examples of lattices, with an emphasis of root lattices for Lie algebras, see here. Note that Gabriele Nebe has written an article finding all lattices with covering radius below a certain bound, in her normalization that is $\sqrt 2.$ This anticipates me and Pete Clark of MO,

http://mathoverflow.net/questions/39510/must-a-ring-which-admits-a-euclidean-quadratic-form-be-euclidean

so it is not clear what will be published on that...

Answer by Daniele Micciancio for diameter of Voronoi cell of the lattice ? What about R^n ? What about small n =2,3,4 ?What about random lattice ?

2011-06-08T05:09:42Z

Computing the covering radius of a lattice (wrt $\ell_2$ norm) is not known to be NP-hard. (Will, if you got that piece of information from SLG, I guess SLG is wrong.)

Computing the covering radius of linear codes (wrt Hamming metric) and of lattices (wrt $\ell_p$ norm but only for large $p>2$) is NP-hard. In fact these problems are even $\Pi_2$ hard to approximate for small constant approximation factors. See papers

http://dx.doi.org/10.1007/s00037-005-0193-y (The complexity of the covering radius problem, Guruswami, Micciancio and Regev, Computational Complexity 14(2):90-121)
http://dx.doi.org/10.1109/CCC.2006.23 (Hardness of the covering radius problem on lattices, Haviv and Regev, in CCC 2006)

Approximating the covering radius of lattices in $\ell_2$ norm is also conjectured (in reference 1) to be $\Pi_2$ hard to approximate within some small constant factor (and NP-hard for any constant factor), but as far as I know this is an open problem.

For any fixed dimension n, the covering radius problem can be solved in polynomial time. So, for small $n$ (certainly for $n=2,3,4$, and probably for up to $n\leq 20$ or so), the problem can be solved efficiently. There are several ways to do that, but they are all based on enumerating all the vertices of the Voronoi cell, which takes at least $n^{O(n)}$ time. See http://dx.doi.org/10.1145/1806689.1806739 and references therein. Computing the covering radius in single exponential time $2^{O(n)}$ is an open problem.

For larger dimension it may be more effective to approximate the covering radius within a factor 2 as suggested in reference 1 above, by picking a random point in space and computing its distance to the lattice. This can be done in $2^{O(n)}$ time.