The Number of Short Vectors in a Lattice - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T12:51:12Z http://mathoverflow.net/feeds/question/71052 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71052/the-number-of-short-vectors-in-a-lattice The Number of Short Vectors in a Lattice OSHE 2011-07-23T06:11:09Z 2011-07-23T14:01:15Z <p>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.</p> <p>Also asked at: <a href="http://cstheory.stackexchange.com/questions/7488/the-number-of-short-vectors-in-a-lattice" rel="nofollow">http://cstheory.stackexchange.com/questions/7488/the-number-of-short-vectors-in-a-lattice</a></p> http://mathoverflow.net/questions/71052/the-number-of-short-vectors-in-a-lattice/71066#71066 Answer by Steve Huntsman for The Number of Short Vectors in a Lattice Steve Huntsman 2011-07-23T13:55:43Z 2011-07-23T14:01:15Z <p>For this problem one typically employs the so-called Gaussian heuristic: </p> <blockquote> <p>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)$.</p> </blockquote> <p>In particular, the case for $K$ a ball is used in some (enumerative) SVP/CVP solvers. See $\S 5$ of <a href="http://docs.google.com/viewer?a=v&amp;q=cache%3AAhvHFVKJM6gJ%3Aperso.ens-lyon.fr/guillaume.hanrot/Papers/iwcc.pdf+%2522Algorithms+for+the+Shortest+and+Closest+Lattice%2522&amp;hl=en&amp;gl=us&amp;pid=bl&amp;srcid=ADGEESgobFF10e7VdXrwpPBbjVxoAKFKPeLIKDgr_t23PLdWk0RYK1NTG2L_0jkyYMoCIGfwombzc8QWsOc77syabUW4z41kyggPGw7Ku9g1bw_OviJHeDpoiw03Szwp0CIWm0VU_ass&amp;sig=AHIEtbQS1o9KO1WzlxdFen5jkXJ4Ff8UAA&amp;pli=1" rel="nofollow">"Algorithms for the shortest and closest lattice vector problems"</a> by Hanrot, Pujol and Stehlé.</p>