# The Number of Short Vectors in a Lattice

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.

• 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. 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. Jul 23 '11 at 9:51

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