Lattices and LLL Reduction
Detecting Algebraic and Linear Dependence with LLL
Recovering exact integer relations from numerical approximations using LLL, and the precision requirements that make the method reliable.
Engineering / MathematicsLattices and LLL Reduction2 min readKV-MATH-0552
Given a real number known only to high precision, LLL can often recover an exact polynomial it satisfies. The technique is one of the most striking applications of lattice reduction and one of the easiest to misuse.
The construction
To find an integer relation among given real numbers, build a lattice whose vectors pair the candidate coefficients with a scaled approximation of the corresponding combination. A short vector corresponds to a small combination — that is, to a relation.
Integer relation detection
- Compute to high precisionObtain the values to substantially more digits than the expected coefficient size.
- Build the latticeIdentity block alongside scaled values.
- ReduceApply LLL.
- Read the candidateThe first vector gives candidate coefficients.
- Verify exactlyConfirm the relation by an independent exact computation. This step is mandatory.
Finding a minimal polynomial
Applying this to the powers of an algebraic number recovers its minimal polynomial: a relation among the powers is precisely a polynomial the number satisfies.
Precision
| Symptom | Diagnosis |
|---|---|
| Relation fails exact verification | Insufficient precision |
| Coefficients as large as the scale factor | No genuine relation exists at this degree |
| Different relations at different precisions | Spurious; increase precision |
| Relation is a multiple of a smaller one | Degree guess was too high |
Applications
The technique recovers minimal polynomials of algebraic numbers given numerically, identifies class invariants in complex multiplication, and supports polynomial reduction by recognising small defining polynomials.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.7.2. 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.