3
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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}.$$

$\endgroup$
1
  • $\begingroup$ Although this estimate is a little rough, it answers my doubts to some extent. Thanks for your help! $\endgroup$
    – kangli
    Feb 21, 2023 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.