The Number of Short Vectors in a Lattice - MathOverflow

The Number of Short Vectors in a Lattice

2011-07-23T06:11:09Z

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

Answer by Steve Huntsman for The Number of Short Vectors in a Lattice

2011-07-23T13:55:43Z

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