How Hermite Lattice reduced basis implies LLL reduced basis?

Question

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?

Answer 1

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.

As for your last questions:

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".