How does the lengths of the Gram-Schmidt orthogonal basis of a lattice basis change after lll reduction?

Question

Assuming there is a lattice basis $B=\{b_1,...,b_n\}$, we use $B^*=\{b_1^*,...,b_n^*\}$ to denote the Gram-Schmidt orthogonal basis, where $b_i^*=\pi_i(b_i)$ and $\pi_i(b_i)$ denotes the projection of $b_i$ on the orthogonal complement of the space $span(b_1,...,b_{i-1})$. We use $\|b_i^*\|$ to denote the Euclidean norm of $b_i^*$. I want to know how $\min_{1\leq i \leq n}{\|b_i^*\|}$ changes after LLL reduction in detail. Is there any reference for this question? Thank you in advance for your help.

Answer 1

Although there is not a formal result with respect to this question, there is a widely accepted empirical observation for "typical" lattices known as the Geometric Series Assumption (see the 8th slide of this talk by Martin Albrecht for example). This states that we believe that the $||b_i^*||$ form a decaying geometric progression so that the least value is $||b_n^*||$. As the product of the $||b_i^*||$ is the determinant of the lattice, we expect that for $1\le i\le n$ we have $$||b_i^*||\cdot||b_{n-i}^*||\approx\Delta^{2/d}$$ where $d$ is the degree of the lattice and $\Delta$ its determinant. It follows then that we expect $$\min_{1\le i\le n}||b_i^*||=||b_n^*||\approx\frac{\Delta^{2/d}}{||b_1||}.$$ Entering your favourite expression for the length of the shortest vector in the LLL basis (e.g. $||b_1||=\delta_0^d\Delta^{1/d}$) will give an expression such as $$\min_{1\le i\le n}||b_i^*||\approx\delta_0^{-d}\Delta^{1/d}.$$