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: https://cstheory.stackexchange.com/questions/7488/the-number-of-short-vectors-in-a-lattice

  • 3
    $\begingroup$ 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. $\endgroup$ Jul 23 '11 at 7:47
  • $\begingroup$ 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. $\endgroup$ Jul 23 '11 at 9:51

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é.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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