Score:3

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

in flag

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.

Score:4
ru flag

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

in flag
Although this estimate is a little rough, it answers my doubts to some extent. Thanks for your help!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.