Minkowski reduced

Definition

The basis$\left\{b_i\right\}_{i=1}^d$ is Minkowski-reduced if $b_i$has minimum length among all vectors in $L$ linearly independent from$\left\{b_j\right\}_{j=1}^{i-1}$. Equivalently, $b_i$has minimum length among all vectors $v$such that $\left\{b_1,\dots,b_{i-1},v\right\}$can be extended to form a basis of$L$. Such a notion is strongest among all lattice reduction notions and is generally extremely hard to compute. Another equivalent definition is

Bounds

The proof presented here is based off [Waerden 1956]. We proceed by induction. Letbe a Minkowski-reduced basis for some lattice. The lower bound is immediate and for , the upper bound is immediate as well.

Let be linearly independent vectors such that. Let be the sublattice generated by . Evidently somemust exist such thatis not in . Consider the new lattice . Letbe the shortest vector insuch thatis a basis for and we have

If, then we are done sincecan be extended to a basis of , so . Otherwise, we have . Let whereis the projection ofin. Since by definition we have, we must have

Furthermore, since

we have , hence we have

but since by definition, the case of cannot occur here (hence in these cases).

Exercises

1) Show that both definitions of Minkowski-reduced lattice are equivalent

2) Consider the lattice . We have showed in a previous exercise that the successive minima are allbut no basiscan satisfy , show that for any Minkowski reduced basis , the basis must satisfy