Class Groups, Units and Regulators
Class Group and Unit Computation: the Computational Problem
Why class group and unit computation are a single problem, what the combined algorithm produces, and how the results are verified.
Engineering / MathematicsClass Groups, Units and Regulators2 min readKV-MATH-0598
Class group and unit group are computed together, not separately. The same relation collection produces both, and separating them would duplicate the expensive part of the work.
Why they are one problem
Relations among ideal classes are collected by finding elements whose principal ideals factor over the factor base. A relation that turns out to be trivial in the class group corresponds to a principal ideal, and the generator of a principal ideal that is trivial in every coordinate is a unit.
The combined output
What a complete run produces
The pipeline
The combined class group and unit computation
- Build the factor basePrime ideals of norm below a chosen bound — see factor base selection.
- Collect relationsFind smooth principal ideals — see relation matrix construction.
- Reduce the matrixStructured elimination, then Smith normal form.
- Read the class groupFrom the invariant factors — see group structure.
- Recover unitsFrom the kernel — see regulator recovery.
- VerifyAgainst the analytic class number formula.
Two failure modes
| Failure | Effect | Detection |
|---|---|---|
| Too few relations | Computed class number is a multiple of the truth | Analytic formula comparison |
| Factor base does not generate | Computed group is a quotient of the truth | Analytic formula comparison; GRH bound rules it out |
Cost
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.