How many LLL reduced bases are there?

For a given $n$-dimensional lattice embedded inside $\mathbb R^n$ along with a given inner product, how many distinct LLL-reduced bases are there?

In this question, a lattice is the set of all $\mathbb Z$-linear combinations of a set of $n$ vectors from $\mathbb R^n$ that are linearly independent over $\mathbb R$.

-
And what, precisely, is the definition of LLL-reduced? I know the colloquial "a basis of nearly orthogonal vectors", but I'd appreciate a precise definition, or a good link. –  Kevin O'Bryant Mar 1 '11 at 19:08
See here. I'm pretty sure the answer to the OP is exponential. –  Emil Jeřábek Mar 1 '11 at 19:19
Klim, I don't think that's correct. It's true that there are n! inputs to the LLL algorithm, each of which leads to an LLL reduced basis (some of which may coincide). But the condition of being an LLL reduced basis has nothing to do with using the LLL algorithm, and there may be LLL reduced bases which are not obtained from any permutation of a given starting basis. So you may be right that n! is an upper bound, but I don't think that you've given a proof. OTOH, I certainly agree with you that computing the exact number is likely to be a hard question. –  Joe Silverman Mar 1 '11 at 21:46
I think you are better off asking about Minkowski reduced quadratic forms, where some things are known. In any case, until told otherwise, I would assume that your bound depends on both the dimension and a determinant term. –  Will Jagy Mar 2 '11 at 0:41
If the lattice is $\mathbb Z^n$ with the standard dot product as the inner product, then the standard basis is LLL reduce and multiplying any of the basis vectors by $-1$ will result in an LLL reduced basis. So, in this case, there are at least $2^n$ distinct LLL-reduced bases. –  David Cardon Mar 2 '11 at 6:55

1 Answer

Here is the answer.

Claim: Any given n-dimensional lattice has at most $2^{0(n^3)}$ LLL reduced bases.

Notice: the bound is a function of the dimension $n$ only, and does not depend on the determinant of the lattice. Here is a simple proof:

Proof: Fix a lattice $L(B)$ and let $\lambda$ be the minimum distance of the lattice. The first vector of an LLL reduced basis $B=[\vec b_1,\ldots,\vec b_n]$ has length at most $2^{O(n)}\lambda$. Since spheres of radius $\lambda/2$ centered around lattice points are disjoit, by a simple volume argument, the number of lattice points in a sphere of radius $r=2^{O(n)}\lambda$ is at most $(1+2r/\lambda)^n = 2^{O(n^2)}$. For any such first vector $\vec b_1$, let $\pi_1$ be the projection orthogonal to $\vec b_1$. By definition of LLL reduced basis, $\pi_1(B)$ is also LLL reduced. Using LLL size reduction conditions, each projected LLL reduced basis $\pi_1(B)$ thas a unique lift such that all its Gram-Schmidt coefficients are in the range $[-1/2,1/2)$. So, we can proceed by induction, and see that there are at most $2^{O((n-1)^2)}$ possible choices for $\vec b_2$, and so on. Overall, the number LLL reduced bases for $L$ is at most $\prod_{k=1}^n 2^{O(k^2)} = 2^{O(n^3)}$. This concludes the proof of the upper bound. [Q.E.D.]

Of course, the number of LLL bases for a given lattice can be much smaller, e.g., you can easily build lattices whose LLL basis is unique up to the sign of the basis vectors. (E.g., take an orthogonal lattice with longer and longer basis vectors.) So, the number of LLL reduced basis can be as low as $2^n$. Every lattice has at least these many LLL reduced basis because you can set the signs of the basis vectors arbitrarily. However, my guess is that the upper bound is asymptotically optimal in the worst case, i.e., there are lattices with $2^{\Omega(n^3)}$ LLL reduced bases. It should be possible to construct such lattices starting from examples lattices that achieve LLL worst case approximation factor $2^{O(n)}$ on the length of the shortest vector, but I didn't check the details.

-