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>



The Number of Short Vectors in a Lattice
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"](http://docs.google.com/viewer?a=v&q=cache%3AAhvHFVKJM6gJ%3Aperso.ens-lyon.fr/guillaume.hanrot/Papers/iwcc.pdf+%2522Algorithms+for+the+Shortest+and+Closest+Lattice%2522&hl=en&gl=us&pid=bl&srcid=ADGEESgobFF10e7VdXrwpPBbjVxoAKFKPeLIKDgr_t23PLdWk0RYK1NTG2L_0jkyYMoCIGfwombzc8QWsOc77syabUW4z41kyggPGw7Ku9g1bw_OviJHeDpoiw03Szwp0CIWm0VU_ass&sig=AHIEtbQS1o9KO1WzlxdFen5jkXJ4Ff8UAA&pli=1)
by Hanrot, Pujol and Stehlé.


