Gram-Schmidt coefficients in LLL algorithm

Question

To my understanding the LLL lattice reduction algorithm starts with a set of integer vectors $\{b_1, \dots, b_2\}$, which span a lattice, and tries to generate a new basis of shorter vectors of the same lattice. It first defines the Gram-Schmidt orthogonal basis $\{b_1^\ast, \dots, b_2^\ast\}$ (which is in general not integer) and proceeds to find new vectors according to $$ b_i \leftarrow b_i - \lfloor \mu_{i,j} \rceil b_j \, $$ where the Gram-Schmidt coefficients $\mu_{i,j}$ are given by $$ \mu_{i,j} = \frac{(b_i, b^\ast_j)}{(b^\ast_j, b^\ast_j)} \,. $$ This process is repeated iteratively (including some resorting of the $b_i$) until certain criteria are met.

However, naively I could also imagine to use $$ \tilde \mu_{i,j} = \frac{(b_i, b_j)}{(b_j, b_j)} $$ instead of $\mu_{i,j}$ in the above replacement rule. In particular, if one tries to minimize the norm of $b_i + \lambda b_j$ analytically by taking the derivative of $$ \|b_i + \lambda b_j\|^2 = \|b_i\|^2 + 2 \lambda (b_i, b_j) + \lambda^2 \|b_j\|^2 $$ with respect to $\lambda$ and setting the resulting expression to zero, the optimal $\lambda$ is exactly given by $- \tilde \mu_{i,j}$ (and not $- \mu_{i,j}$). So I would imagine that the shortest possible vector on the lattice is obtained by rounding this value to the closest integer.

Therefore, my question is: Why does LLL use the coefficients $\mu_{i,j}$ and not $\tilde \mu_{i,j}$? For just two input vectors they are literally the same, but do they guarantee a shorter runtime or better results (despite my naive argument) in the higher dimensional case?

Answer 1

It is not just the case that LLL tries to find a shorter basis, but recall the two conditions for a basis to be reduced:

1. Size Reduction: $|\mu_{i, j}| \leq 1/2$ for $1 \leq j \leq i \leq d$
2. Lovasz Condition: $||\mathbf{b}^*_i||^2 \geq (\delta - \mu ^2_{i,i-1})||\mathbf{b}^*_{i_1}||^2,\ \ \ \ 2 \leq i \leq n$

The first condition here is consistent with what you are talking about with a shorter basis, but the second is a notion of near orthogonality on top of this (see this answer for a more indepth explanation of why).

By the definition your new $\tilde{\mu}$, you are not using any of this orthogonality from Gram Schmidt when finding your new $\mathbf{b}_i$, and so your outcome is likely going to be a holistically worse basis.

In fact, there may be the case where the Lovasz condition is never met, and so your will never terminate. It is probably possible to work through and find such an example with $\tilde{\mu}$, and show that the same cannot happen for $\mu$, but this is left as an exercise.