11
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Daniel Litt
    Commented Jul 23, 2011 at 7:47
  • $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 23, 2011 at 9:51

1 Answer 1

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .