What LLL really means

The following theorem is not too difficult to prove.

Let $b_1,\ldots,b_n$ be an LLL reduced basis for a lattice $L\subset \mathbf{R}^n$. Let $d(L)$ denote the absolute value of the determinant of any matrix whose rows are basis for $L$. Then the vectors $b_i$ are ``nearly orthogonal'' and ``short'' in the sense of the following theorem:

Theorem 2.5.3   We have

1. $d(L) \leq \prod_{i=1}^n \vert b_i\vert \leq 2^{n(n-1)/4} d(L)$,
2. For $1\leq j \leq i \leq n$, we have
   $$\vert b_j\vert \leq 2^{(i-1)/2} \vert b_i^*\vert.$$

3. The vector $b_1$ is very short in the sense that
   $$\vert b_1\vert \leq 2^{(n-1)/4} d(L)^{1/n}$$
   and for every nonzero $x \in L$ we have
   $$\vert b_1\vert \leq 2^{(n-1)/2} \vert x\vert.$$

4. More generally, for any linearly independent $x_1,\ldots, x_t \in L$, we have
   $$\vert b_j\vert \leq 2^{(n-1)/2} \max(\vert x_1\vert, \ldots, \vert x_t\vert)$$
   for $1\leq j \leq t$.

Perhaps the most amazing thing about the idea of an LLL reduced basis is that there is an algorithm (in fact many) that given a basis for a lattice $L$ produce an LLL reduced basis for $L$, and do so quickly, i.e., in polynomial time in the number of digits of the input. The current optimal implementation (and practically optimal algorithms) for computing LLL reduced basis are due to Damien Stehle, and are included standard in Magma in Sage. Stehle's code is amazing - it can LLL reduce a random lattice in $\mathbf{R}^{n}$ for $n<1000$ in a matter of minutes!!

sage: A = random_matrix(ZZ, 200)
sage: t = cputime()
sage: B = A.LLL()     
sage: cputime(t)     # random output
3.0494159999999999

There is even a very fast variant of Stehle's implementation that computes a basis for $L$ that is very likely LLL reduced but may in rare cases fail to be LLL reduced.

sage: t = cputime()
sage: B = A.LLL(algorithm="fpLLL:fast")   # not tested
sage: cputime(t)      # random output
0.96842699999999837