LLL Reduced Basis

Given a basis $b_1,\ldots,b_n$ for $\mathbf{R}^n$, the Gramm-Schmidt orthogonalization process produces an orthogonal basis $b_1^*,\ldots, b_n^*$ for $\mathbf{R}^n$ as follows. Define inductively

$$b_i^* = b_i - \sum_{j < i} \mu_{i,j} b_j^*$$

where

$$\mu_{i,j} = \frac{b_i \cdot b_j^*}{b_j^* \cdot b_j^*}.$$

Example 2.5.1   We compute the Gramm-Schmidt orthogonal basis of the rows of a matrix. Note that no square roots are introduced in the process; there would be square roots if we constructed an orthonormal basis.

sage: A = matrix(ZZ, 2, [1,2, 3,4]); A
[1 2]
[3 4]
sage: Bstar, mu = A.gramm_schmidt()

The rows of the matrix $B^*$ are obtained from the rows of $A$ by the Gramm-Schmidt procedure.

sage: Bstar
[   1    2]
[ 4/5 -2/5]
sage: mu
[   0    0]
[11/5    0]

A lattice $L\subset \mathbf{R}^n$ is a subgroup that is free of rank $n$ such that $\mathbf{R}L = \mathbf{R}^n$.

Definition 2.5.2 (LLL-reduced basis)   The basis $b_1,\ldots,b_n$ for a lattice $L\subset \mathbf{R}^n$ is LLL reduced if for all $i,j$,

$$\vert\mu_{i,j}\vert \leq \frac{1}{2}$$

and for each $i\geq 2$,

$$\vert b_i^*\vert^2 \geq \left( \frac{3}{4} - \mu_{i,i-1}^2\right) \vert b_{i-1}^*\vert^2$$

For example, the basis $b_1 = (1,2)$, $b_2 = (3,4)$ for a lattice $L$ is not LLL reduced because $b_1^*=b_1$ and

$$\mu_{2,1} = \frac{b_2 \cdot b_1^*}{b_1^* \cdot b_1^*} = \frac{11}{5} > \frac{1}{2}.$$

However, the basis $b_1 = (1,0)$, $b_2 = (0,2)$ for $L$ is LLL reduced, since

$$\mu_{2,1} = \frac{b_2 \cdot b_1^*}{b_1^* \cdot b_1^*} = 0,$$

and

$$2^2 \geq (3/4) \cdot 1^2.$$

sage: A = matrix(ZZ, 2, [1,2, 3,4])
sage: A.LLL()
[1 0]
[0 2]