Lattices and LLL Reduction
Lattice Definitions and Quadratic Forms
Lattices as discrete subgroups, the Gram matrix, and the correspondence between lattices with a basis and positive definite quadratic forms.
Engineering / MathematicsLattices and LLL Reduction2 min readKV-MATH-0543
A lattice is a discrete subgroup of a real vector space. Almost every hard problem in this collection that is not factoring can be posed as a question about a lattice, which is why lattice reduction is so pervasive.
Definition
Given linearly independent vectors in real space, the lattice they generate consists of all integer combinations. The vectors form a basis, and the rank is their number.
The Gram matrix
Inner products of the basis vectors assemble into the Gram matrix, which captures all metric information about the lattice.
- Determinant of the lattice
- The square root of the determinant of the Gram matrix. Independent of the basis chosen — a genuine invariant.
- Covolume
- The same quantity, interpreted as the volume of the fundamental parallelepiped.
- Successive minima
- The lengths of the shortest independent vectors, in increasing order. Basis-independent but hard to compute.
Quadratic forms
Writing a general lattice vector as an integer combination and taking its squared length gives a quadratic form in the coefficients. The Gram matrix is exactly the matrix of that form.
Why it matters here
| Lattice | Where it arises |
|---|---|
| Ideal as a Z-module | Every ideal of a number field is a lattice of rank the field degree |
| Unit lattice | The image of the units under the logarithmic embedding |
| Relation lattice | Relations among ideal classes |
| Binary quadratic forms | Rank two lattices; the classical route to quadratic field class groups — see the correspondence |
Hard lattice problems
Finding a shortest non-zero vector is NP-hard under randomised reductions. Finding a reasonably short one is tractable, which is precisely the gap that LLL occupies.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.5.1. 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.