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

Given a lattice $L = \bigoplus_{i=1}^{m} \mathbb{Z}v_i$ (the $v_i$ are linearly independent vectors in $\mathbb{R}^n$) and a number $c > 0$, can one quickly compute or find a good estimate on the number of lattice vectors $v$ with $|v| \leq c$ without actually enumerating these vectors? The basis $v_1,\ldots, v_m$ of the lattice can be assumed to be LLL reduced.

Also asked at: http://cstheory.stackexchange.com/questions/7488/the-number-of-short-vectors-in-a-lattice

share|improve this question
3  
Of course, for large $c$ this approximates the volume of a ball of radius $c$, divided by the covolume of the lattice, and error estimates are an important part of number theory about which I know almost nothing (Gauss circle problem, etc.) On the other hand, if you want to know how many vectors have a particular length (for example, the shortest length) there are so-called mass formulae dealing with such problems, due to Siegel, Minkowski, and others, although there are subtleties if the lattice in question is not alone in its genus. –  Daniel Litt Jul 23 '11 at 7:47
    
For a range of relatively small values of $c$ and $m$ the sphere decoding algorithm could probably be tweaked to produce an answer, but it would also enumerate them, so you want something faster. But in that low range of $c$ IIRC the question of whether the number of short vectors is positive belongs to some discouraging complexity class. –  Jyrki Lahtonen Jul 23 '11 at 9:51

1 Answer 1

up vote 6 down vote accepted

For this problem one typically employs the so-called Gaussian heuristic:

if $K$ is a measurable subset of the span of the $n$-dimensional lattice $L$, then $| K \cap L | \approx > \mbox{vol}(K)/\det(L)$.

In particular, the case for $K$ a ball is used in some (enumerative) SVP/CVP solvers. See $\S 5$ of "Algorithms for the shortest and closest lattice vector problems" by Hanrot, Pujol and Stehlé.

share|improve this answer

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.