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