Orientation
The Four Core Computational Tasks of Number Fields
The four fundamental computational problems for a number field, their dependencies, and what counts as a complete answer to each.
Engineering / MathematicsOrientation4 min readKV-MATH-0504
Given a number field presented as the quotient of the rationals by an irreducible polynomial, four computational tasks account for nearly everything one wants to know. They are strictly ordered by dependency: each needs the ones before it.
The four tasks
The four core tasks, in dependency order
- Compute the maximal orderFind an integral basis for the ring of integers. Everything else is expressed relative to this basis, so an error here invalidates all downstream work. See the Round 2 algorithm.
- Decompose primesFor a rational prime p, find the prime ideals above it with their ramification indices and residue degrees. See the simple case and Buchmann-Lenstra.
- Compute the class groupDetermine the group structure as a product of cyclic groups, with explicit ideal generators. See relation matrices.
- Compute units and the regulatorFind a system of fundamental units and the regulator. In practice this falls out of the same relation collection as the class group. See regulator recovery.
Why the ordering is strict
The dependency is not stylistic. Each task consumes the output of its predecessor in an essential way.
| Task | Consumes | Why it cannot be reordered |
|---|---|---|
| Prime decomposition | Maximal order | Prime ideals are ideals of the maximal order. Decomposing in a non-maximal order gives a different and generally wrong answer. |
| Class group | Prime decomposition | The factor base consists of prime ideals of small norm. You cannot assemble it without decomposition. |
| Units and regulator | Class group relations | Relations that are trivial in the class group are exactly the ones that yield units. Both come from the same matrix. |
What counts as a complete answer
- Maximal order
- An integral basis expressed in terms of a power basis, plus the field discriminant. A basis alone is not enough — the discriminant is what lets you verify maximality.
- Prime decomposition
- For each prime above p: a two-element or HNF representation of the ideal, its ramification index e, and its residue degree f, satisfying the degree relation.
- Class group
- The invariant factor decomposition, plus an explicit ideal generating each cyclic factor. The order alone (the class number) is a weaker result.
- Units
- A system of fundamental units in the standard representation, plus the regulator to sufficient precision, plus the roots of unity.
Conditionality
The first two tasks are unconditional and deterministic. The last two are usually computed under the Generalised Riemann Hypothesis, because unconditional bounds on the factor base are impractically large. This is a real distinction that must be recorded with the result.
| Task | Status | Note |
|---|---|---|
| Maximal order | Unconditional | Requires factoring the polynomial discriminant, which may be hard but is not conditional |
| Prime decomposition | Unconditional | Deterministic |
| Class group | Conditional on GRH in practice | Unconditional verification is possible but expensive |
| Regulator | Conditional on GRH in practice | Can be checked against the analytic class number formula |
Verification
Each task admits an independent check, and using them is strongly advised because the failure modes are quiet.
Maximal order
Verify that the index-squared divides the polynomial discriminant and that the quotient is the field discriminant.
Prime decomposition
Check that the sum of e times f over all primes above p equals the field degree. This catches most errors immediately.
Class group and regulator
Compare the product of class number and regulator against the analytic class number formula. See verification.
Frequently Asked Questions
Can the class group be computed without the maximal order?
Is the class number enough, or do I need the group structure?
How expensive is each task in practice?
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 4.9.3. 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.