The basis is Minkowski-reduced if has minimum length among all vectors in linearly independent from. Equivalently, has minimum length among all vectors such that can be extended to form a basis of. Such a notion is strongest among all lattice reduction notions and is generally extremely hard to compute. Another equivalent definition is
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
we have , hence we have
but since by definition, the case of cannot occur here (hence in these cases).
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