Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Its twice the covering radius of the lattice. –  Roland Bacher May 2 '11 at 12:37
    
What is covering radius ? Is is the half diameter of the cell of the lattice ? But cell is not uniquely defined ? Should I take the minimal one ? Is it exact value or an upper bound ? Is it easy to prove ? Thanks You for the comment ! –  Alexander Chervov May 2 '11 at 16:17
1  
The covering radius of a lattice $\lambda$ is the smallest real number $\rho$ such that the union of balls of radius $\rho$ centered at all lattice points is all of $\mathbb R^n$. It is thus by definition the maximal distance of a point of the Voronoi cell to its barycenter. Since the Voronoi cell is centrally symmetric, its diameter is twice the covering radius. –  Roland Bacher May 2 '11 at 16:29
    
Dear Roland, thanks for Yours answer. Is there some way to compute or estimate the covering radius ? At least at R^2 ? –  Alexander Chervov May 3 '11 at 18:37
add comment

2 Answers 2

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

  1. 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)
  2. 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.

share|improve this answer
add comment

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,

Must a ring which admits a Euclidean quadratic form be Euclidean?

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.