One object, two languages
A lattice is a discrete subgroup of ℝn of full rank: the set of integer combinations of a basis. Its determinant — the covolume of a fundamental domain — is independent of the basis chosen, while the basis itself is defined only up to unimodular transformation. Attaching the quadratic form given by the Gram matrix translates every lattice question into a question about forms, and back again. The central computational problem is finding short vectors.
Learning objectives
- Define a lattice, its basis and its determinant.
- Relate lattices to positive definite quadratic forms via the Gram matrix.
- State Minkowski's theorem and the meaning of the successive minima.
- Explain why an arbitrary basis is usually a poor one.
- Identify where lattices arise in number theory.
Section 01Lattices and bases
Given linearly independent b1, …, bn in ℝn, the lattice they generate is
Two bases generate the same lattice exactly when they differ by a unimodular matrix. The determinant, defined as |det B| for a basis matrix B, is therefore an invariant of the lattice — a unimodular change of basis has determinant ±1 and cannot alter it.
A basis obtained from a natural description of a problem is typically skewed: its vectors are long and nearly parallel. The lattice is unchanged, but computations become hopeless. Reduction theory exists to replace such a basis with a short, near-orthogonal one.
Section 02The Gram matrix and quadratic forms
The Gram matrix G = BBt has entries ⟨bi, bj⟩ and defines a positive definite quadratic form
The correspondence is exact: lattices up to isometry correspond to positive definite quadratic forms up to unimodular equivalence, and det G = (det L)2. Every question about short lattice vectors becomes a question about small values of a form.
| Lattice language | Form language |
|---|---|
| Basis change by unimodular U | Equivalence of forms G → UtGU |
| Determinant of the lattice | Square root of the discriminant of the form |
| Shortest non-zero vector | Minimum of the form |
| Reduced basis | Reduced form |
| Sublattice of finite index | Form of larger discriminant representing a subset of values |
In dimension 2 the theory of binary quadratic forms predates lattice reduction by a century and remains the natural language for quadratic fields, where forms correspond to ideal classes. Higher-dimensional work generally prefers the lattice language.
Section 03Minima, Minkowski and Hermite
The successive minima λ1 ≤ … ≤ λn record the smallest radii within which the lattice contains 1, 2, …, n linearly independent vectors. Minkowski's convex body theorem bounds the first of them.
Here γn is Hermite's constant, known exactly only in low dimensions. The bound is existential: it guarantees a short vector exists but gives no procedure for finding one.
Finding a genuinely shortest vector is hard in high dimension. LLL settles for a vector within an exponential factor of the minimum — which sounds weak, and is entirely sufficient for most number-theoretic applications, because the lattices arising there have an unusually large gap between the shortest vector and the rest.
Section 04Where lattices arise in number theory
Rings of integers
ℤK embeds as a lattice of rank n in ℝn via the archimedean embeddings; its determinant is essentially the field discriminant.
Ideals
Every non-zero ideal is a full-rank sublattice of ℤK, with index equal to its norm.
Unit groups
The logarithmic embedding maps the units onto a lattice of rank r1+r2−1 whose covolume is the regulator.
Polynomial factorisation
Recombining modular factors is a short-vector problem in a lattice built from the coefficients.
Integer relations
Detecting a linear relation among real numbers is a short-vector problem in a lattice with a scaled last coordinate.
Sieving
The number field sieve enumerates lattice points in a sieving region — its dominant cost.
ReferenceFrequently asked questions
Must a lattice have full rank?
Not necessarily — a lattice of rank k in dimension n is perfectly well defined. But most algorithms assume full rank, and a lower-rank lattice should be re-expressed in the span it actually occupies before reduction.
Is the Gram matrix enough to recover the lattice?
It determines the lattice up to isometry, which is all that matters for questions about lengths and inner products. It does not determine the embedding in ℝn, so the actual coordinates are lost.
Why is the shortest vector problem hard when Minkowski guarantees one exists?
Because the guarantee is non-constructive. It bounds the length of the shortest vector from the volume, but locating it requires searching a region containing exponentially many candidates in high dimension.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.