Lattices and LLL Reduction
Lattice Determinant and the Hadamard Bound
The lattice determinant as a basis-independent invariant, the Hadamard inequality, and using the orthogonality defect to measure basis quality.
Engineering / MathematicsLattices and LLL Reduction2 min readKV-MATH-0545
The determinant is the one number attached to a lattice that no change of basis can alter. Comparing it against the product of the basis vector lengths gives a direct measure of how bad a basis is.
Definition
The Hadamard inequality
The product of the vector lengths is at least the determinant, with equality exactly when the basis is orthogonal.
Orthogonality defect
The ratio of the two sides measures basis quality on a scale where one is perfect.
| Defect | Interpretation |
|---|---|
| Close to 1 | Nearly orthogonal; reduction has little to offer |
| Moderate | Typical of an LLL-reduced basis |
| Very large | Severely skewed; reduction will help substantially |
Minkowski's bound
A short vector must exist: any symmetric convex body of sufficient volume contains a non-zero lattice point. This gives an existence bound on the shortest vector in terms of the determinant and the rank.
Use as a computational bound
The Hadamard inequality bounds determinants of integer matrices, which is what makes modular determinant computation a complete algorithm — see determinant computation. The same bound sizes the modulus in modular Hermite normal form.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.5. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.