# 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. – 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

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