Why is the Lovász condition used in the LLL algorithm?

Question

The LLL algorithm is used to approximate the Shortest Vector Problem, i.e., it outputs a reduced basis. Such a basis will satisfy two conditions: $$ \forall i \gt j. \quad \lvert\mu_{ij}\rvert \le \frac{1}{2} \qquad\text{[size-reduced]} $$ $$ \forall i.\quad \lVert b_i^*\rVert^2 \le \lVert b_{i+1}^*\rVert^2 + \mu_{i+1,i}^2\lVert b_i^*\rVert^2 \qquad\text{[Lovász condition]}$$

It seems the first condition assures the resulting basis is nearly orthogonal. But what does the Lovász condition mean and why is it used?

Answer 1

The issue with the length-reduction criterion alone (and the reason the Lovász condition is included in the LLL algorithm) is that the following basis satisfies it:

_{(The grey arrow is the projection of $b_2$ to the orthogonal complement of $b_1$.)}

Clearly, this basis is not very short, nor is it close to being orthogonal (i.e., note that length reduction alone does not imply almost-orthogonality!). The Lovász condition is suited to detect such a situation: If the order of the vectors is swapped, another length reduction can easily be performed, yielding the following LLL-reduced basis:

It seems that Lenstra, Lenstra, and Lovász have noticed that a situation in which length reduction alone is stuck with a very bad basis — as depicted in the first image — always has vectors which are in the "wrong" order comparing their lengths and which are far from being orthogonal, and that it helps in this case to exchange them and continue length-reducing.¹ That is really the core idea of the LLL algorithm.

I think of the Lovász condition mainly as a technical construction that just "turned out" to work well, but by rearranging the terms, one may get a feeling for why it enforces close-to-orthogonality:

$$ (\delta-\mu_{i+1,i}^2)\lVert b_i^\ast\rVert^2 \;\leq\; \lVert b_{i+1}^\ast\rVert^2 $$ _{(In your formula, $\delta=1$ is "hardcoded".)}

The Gram-Schmidt coefficient $\mu_{i+1,i}$ measures the angle between $b_i^\ast$ and $b_{i+1}$; the angle is small iff $\mu$ is close to $1$, and it is large (i.e. almost orthogonal) iff $\mu$ is close to $0$. Note this talks about the angle between the orthogonalized vector $b_i^\ast$ and the lattice vector $b_{i+1}$, but $b_i^\ast$ is in turn forced to be "quite close" to $b_i$, hence this also bounds the angle between the lattice basis vectors depending on the orthogonalized vectors' lengths relative to each other.

In short: The Lovász condition is fulfilled if the vectors are close enough to being orthogonal, or if they are roughly ordered by length. Both of these properties lead to length reduction being quite effective.

¹ ^{The procedure of changing the order of some vectors and length-reducing approximates another basis reduction concept, weight reduction, but there is no efficient algorithm to compute that one.}

Answer 2

Personally, I find that the QR decomposition makes the condition a lot more intuitive, in addition to being the computationally efficient way to implement LLL. Since the problem of finding a short basis isn't changed if you rotate or reflect the vectors in space (the linear combination of the good basis in terms of the old basis) will be the same, you can always assume that the vectors in your basis form an upper triangular matrix, and otherwise rotate it into one with Givens rotations.

If your basis is upper triangular with basis vectors $v^k$ with coordinates given by subscripting, then the Lovasz condition reduces to $\delta |v^{k}_{k}| ^2 \leq |v_{k}^{k+1}|^2 + |v_{k+1}^{k+1}|^2 $

But since we had an upper triangular basis, the LHS (up to the slack factor $\delta$) and RHS are just the squared length of the components of our basis vectors that are orthogonal to the span of the previous basis vectors $v^1 ... v^{k-1}$.

So it really is just about moving the shorter vector first whenever possible and using it to reduce later vectors. The algorithm can then be seen as basically similar to the Euclidean algorithm, just keep subtracting multiples of the smaller vectors from the larger ones.