# How Hermite Lattice reduced basis implies LLL reduced basis?

Hermite reduced basis is defined as

A basis $\{b_1,\dots,b_n\}$ is reduced if it satisfies

1. $|\mu_{i,j}| \le \frac{1}{2}$ and

2. $||\pi_i(b_i)|| \le ||\pi_i(b_j)||$ for $1\le i \le j \le n$

where $\pi_i(x)=\sum_{j=i}^{n}\frac{(x \cdot b_j^*)}{b_j^* \cdot b_j^*)}b_j^*$ i.e., component of $x$ orthogonal to $b_1,\dots,b_{i-1}$

Since the algorithm to find Hermite's reduced basis not known to be in polynomial time for varying dimension.

Lenstra $et\;al$ defined the reduced basis and an algorithm to find the reduced basis in polynomial time.

LLL reduced basis is defined as

1. $|\mu_{i,j}| \le \frac{1}{2}$ and

2. $||\pi_i(b_i)|| \le ||\pi_i(b_{i+1})||$

How the second condition of hermite reduced basis implies second condition of Lenstra $et\;al$ reduced basis. Second condition of Lenstra $et\;al$ reduced basis satisfies only some inequalities in second condition of hermite reduced basis. What about the other inequalities? Does other inequalities are satisfied? If not, how does it output nearly orthogonal basis?

• if you set $j=i+1$ to the second condition (of Hermite) then you get the 2nd condition of LLL. – 111 Jan 23 '17 at 22:09
• Hermite rediced basis is nearly orthogonal basis. if $j=i+1$, only some inequalities of hermite second condition is satisfied then what about the remaining inequalities? – preethi Jan 24 '17 at 4:02
• No. All the inequalities will be true. You just borrow the inequalities j=i+1, for i = 1,2,..,n-1, (where n=rank(L)). These inequalities tells you that the Hermite basis is (also) an LLL basis. – 111 Jan 24 '17 at 4:11
• consider, $\{b_1,b_2,b_3,b_4\}$ is the basis. According to hermite second condition $||b_1||^* \le ||\pi_1(b_1)||=||b_1^*||, ||b_1^*|| \le ||\pi_1(b_2)||=||b_2||, ||b_3^*|| \le ||b_3||, ||b_4^*|| \le ||b_4||$. For $i=2$, $||b_2^*||$ must be $\le ||b_3^*+\mu_{3,2}b_2^*|| \; and \; ||b_4^*+\mu_{4,2}b_2^*+\mu_{4,3}b_3^*||$. For $i=3$, $||b_3^*|| \le ||b_4^*+\mu_{4,3}b_3^*||$ where as in lll second condition for $i=1$, $||b_1^*|| \le ||b_2||$, for $i=2$: $||b_2^*|| \le ||b_3^*+\mu_{3,2}b_2^*$ are satisfied and it does not imply the other conditions for $i=1,2$. Please clarify, if I am wrong. – preethi Jan 24 '17 at 6:55

Ignoring the trivial case $j = i$, for which the second condition is automatically satisfied, the conditions for Hermite-reduced bases can be formally written as:

1. For all $1 < i \leq n$ and for all $1 \leq j < i$: $\qquad \quad \quad \ \ |\mu_{i,j}| \le \frac{1}{2}$.

2. For all $1 \leq i < n$ and for all $i + 1 \ {\color{red}\leq} \ j \leq n$: $\ \quad \|\pi_i(b_i)\| \le \|\pi_i(b_j)\|$.

The conditions for LLL-reduced bases can be slightly rewritten as:

1. For all $1 < i \leq n$ and for all $1 \leq j < i$: $\qquad \quad \quad \ \ |\mu_{i,j}| \le \frac{1}{2}$.

2. For all $1 \leq i < n$ and for all $i + 1 \ {\color{red}=} \ j\leq n$: $\ \quad \|\pi_i(b_i)\| \le \|\pi_i(b_j)\|$ .

The only difference in the definitions, highlighted in red, is on the values $j$ for which the second condition must hold; for Hermite-reduced bases it must hold for all $j \in \{i+1, \dots, n\}$ while for LLL-reduced bases it must hold for $j \in \{i + 1\}$ (provided $i + 1 \leq n$). Since $\{i + 1\} \subset \{i+1, \dots, n\}$ this means Hermite-reduction is a stronger notion than LLL-reduction. So Hermite-reduction implies LLL-reduction.

What about the other inequalities? Does other inequalities are satisfied? If not, how does it output nearly orthogonal basis?

For the case $n = 2$, the sets $\{i + 1, \dots, n\}$ and $\{i + 1\}$ are equal for $i = 1$, while for $i = 2 = n$ the second condition does not apply. So for $n = 2$, both notions of reducedness are equivalent. (Many other notions of reducedness also collapse to the same definition in case $n = 2$.)

For $n > 2$, setting $i = 1$ shows that the conditions are not necessarily equivalent. I am not sure whether already for $n = 3$ there are examples of LLL-reduced bases which are not Hermite-reduced, but certainly for larger $n$ there are many such examples - by the second condition, the vector $b_1$ of a Hermite-reduced basis must be a shortest non-zero vector of the lattice, while for LLL-reduced bases the vector $b_1$ is only known to be at most a factor $2^{O(n)}$ longer than a shortest non-zero vector in the lattice. In high dimensions, an LLL-reduced basis will look quite skewed compared to a Hermite-reduced basis, so in that sense it does not really output a "nearly orthogonal basis" - only a "somewhat orthogonal basis".