The ideal class group turns failure of unique element factorisation into a finite computable object. Its definition is compact: take nonzero fractional ideals and quotient by principal fractional ideals. Its computation is not compact. One must bound the search, choose generators, collect exact relations, prove enough relations have been found and reduce a large integer matrix to invariant factors.
This is Guide 20 in the Bukit Timah Tutor Computational Number Theory series. It closes Batch 05 by combining ideals from Guide 16, normal forms from Guide 18 and unit relations from Guide 19. The main worked field is Q(√−5), where the complete class group can be derived by hand.
Return to the BTT Mathematics Hub for the wider Mathematics estate.
1. What the class group measures
Let K be a number field with ring of integers O_K. Nonzero fractional ideals form an abelian group under multiplication. Principal fractional ideals (α)=αO_K form a subgroup.
The ideal class group is
Cl(K)=I_K/P_K.
Two ideals represent the same class when their quotient is principal. The identity class contains every principal ideal.
The class group is finite. Its order h_K is the class number.
2. Why class number one matters
If Cl(K) is trivial, every nonzero ideal is principal. Since ideals factor uniquely into prime ideals, principal ideal domains recover unique factorisation of elements up to units.
If the class group is nontrivial, prime-ideal factorisation remains unique while element factorisation may fail.
The class group therefore measures an obstruction: how far ideal arithmetic is from being generated by single elements everywhere.
3. Finiteness becomes an algorithm through Minkowski
Minkowski’s geometry-of-numbers theorem gives an explicit norm bound. If K has degree n, discriminant D_K and r2 complex-conjugate pairs, every ideal class contains an integral ideal I with
N(I) ≤ M_K, M_K = (4/π)^r2 · n!/n^n · √|D_K|.
This converts the abstract finiteness theorem into a finite search: only ideals with norm up to the bound need be considered to generate all classes.
The bound is often not tight, but it is rigorous and sufficient for certification.
4. The field Q(√−5)
Let K=Q(√−5). Its ring of integers is Z[√−5] and its field discriminant is −20.
The degree is n=2 and r2=1. Therefore
M_K = (4/π)(2!/2²)√20
= (2/π)√20
≈ 2.847.
Every ideal class therefore has an integral representative of norm at most 2.847. Ideal norms are positive integers, so only norms 1 and 2 matter.
The norm-one ideal is O_K itself, the principal class. The entire class-group computation is now reduced to understanding ideals of norm two.
5. The prime ideal above 2
Modulo two, the polynomial X²+5 becomes
X²+1 = (X+1)² over F2.
The repeated factor signals ramification. Define
p = (2,1+√−5).
The quotient O_K/p has two elements, so N(p)=2.
Moreover
(2)=p².
Thus the class [p] has order dividing two.
6. Proving p is not principal
If p were principal, p=(α), then
|N_K/Q(α)| = N(p)=2.
Every algebraic integer in Z[√−5] has the form a+b√−5, with norm
a²+5b².
The equation a²+5b²=2 has no integer solution. If b=0, a²=2 is impossible; if |b|≥1, the left side is at least five.
Therefore no element has norm two, so p is not principal.
7. The complete class group of Q(√−5)
Minkowski says every class has a representative of norm 1 or 2. There is the principal norm-one class and the nonprincipal norm-two class [p]. No third class can exist.
Since p²=(2) is principal,
[p]² = 1.
Hence
Cl(Q(√−5)) ≅ Z/2Z.
This is a complete certified computation: a global bound proves completeness, a norm equation proves nonprincipality, and an ideal identity proves the relation.
8. The relation-matrix view of the same example
Choose the factor base containing the single nonprincipal prime ideal p. The principal ideal relation
p²=(2)
gives the exponent relation 2[p]=0.
The relation matrix is the 1×1 matrix
R=[2].
Its Smith normal form is [2]. The quotient Z/RZ is Z/2Z, exactly the class group.
This tiny example is the prototype of much larger class-group algorithms.
9. Factor bases in larger fields
For a larger field, choose prime ideals p1,…,pm of relatively small norm. This is a factor base.
To use it for a certified class-group computation, one must know that these prime ideals generate Cl(K). A Minkowski bound supplies one rigorous choice: include prime ideals of norm up to a sufficient bound.
Practical algorithms often use smaller heuristic or theorem-assisted bounds and then certify the result through additional arguments.
10. Relation collection
Search for algebraic integers α such that the principal ideal (α) factors completely over the factor base:
(α)=p1^e1 ··· pm^em.
Each such smooth principal ideal gives an integer relation vector
(e1,…,em).
Stack these vectors as rows of a relation matrix R. The true class group is a quotient of Z^m by the lattice of all principal relations among the factor-base ideals.
Collected relations generate only a sublattice until completeness is proved.
11. Why smoothness matters
A random principal ideal may contain prime ideals outside the factor base. Such a factorisation does not give a relation solely among the chosen generators.
Relation algorithms therefore search for elements whose norms or ideals are factor-base smooth. This resembles integer factorisation relation collection: multiplicative structure is converted into linear exponent data.
Sieving, lattice enumeration and randomised searches can all be used to find smooth relations. The exact strategy depends on the field degree and discriminant size.
12. From relation matrix to candidate class group
Compute the Smith normal form of R. If the relation lattice has full rank m, the quotient is finite and the nontrivial Smith invariant factors d_i give
G_candidate ≅ Z/d1Z ⊕ ··· ⊕ Z/dsZ.
The determinant or product of nonzero invariant factors gives the candidate class number when the matrix represents the complete relation lattice.
If relations are missing, the candidate quotient is too large: adding more relations can only shrink it.
13. Relation completeness is a separate problem
A square full-rank relation matrix does not automatically prove completeness. The collected relation lattice may have finite index inside the true relation lattice.
Certification methods compare analytic class-number estimates, use additional random relation tests, prove generation by a factor base, saturate the relation lattice at suspect primes, or combine class-group and regulator information.
A computation should distinguish candidate group from collected relations from certified class group.
14. Principal ideal testing
Given an ideal I, the principal ideal problem asks whether I=(α) for some α and, if so, to find such an α.
A necessary condition is that the class of I be trivial in Cl(K). If class-group coordinates are known, this is an immediate group test.
Finding the generator is an additional problem. Since |N(α)|=N(I) for an integral principal ideal up to unit effects and sign conventions, norm equations and embedding bounds can restrict candidates.
In higher-degree fields, lattice methods and unit-group reduction are central to recovering a generator of manageable size.
15. Why units complicate generators
If I=(α), then every uα with u a unit generates the same ideal. Real fields can have infinitely many units, so there are infinitely many generators with very different archimedean sizes.
The logarithmic unit lattice from Guide 19 lets an algorithm multiply by a suitable unit to balance the embeddings of α and find a smaller representative.
Thus the principal ideal problem naturally couples class-group information with unit and regulator computation.
16. Prime ideal decomposition as preprocessing
A factor base begins with rational primes. To obtain prime ideals above each p, factor a defining polynomial modulo p when the integral-order hypotheses permit the standard Dedekind factorisation rule, or use a general prime-decomposition algorithm.
Residue degrees determine prime-ideal norms:
N(p_i)=p^f_i.
Ramified primes require multiplicities. Prime decomposition therefore depends on the exact ring of integers, not merely on a convenient nonmaximal order.
17. Ideal arithmetic and HNF
Ideals are stored as Z-lattices in an integral basis. Products initially produce many generators. Hermite normal form reduces them back to a canonical module basis.
Ideal equality, containment and norm calculations can then be reduced to exact integer matrix operations.
This is why Guide 18 is infrastructure rather than a separate topic: class-group arithmetic repeatedly calls HNF and Smith form.
18. LLL and relation searching
LLL can shorten ideal-lattice bases and help find algebraic integers with small embeddings or controlled norms. Such elements are better candidates for smooth principal ideals.
LLL does not prove a class relation by itself. Once a candidate α is found, factor the exact principal ideal (α) and record the exact exponent vector.
Geometry proposes; exact ideal arithmetic certifies.
19. Binary quadratic forms as a specialised class-group algorithm
For imaginary quadratic fields, reduced binary quadratic forms provide an elegant specialised representation of ideal classes.
At discriminant −23, Guide 17 enumerated exactly three reduced forms and composition produced a cyclic group of order three. That is a class-group computation without a large general-purpose relation matrix.
Specialised algorithms can exploit quadratic structure far more directly than a generic number-field implementation.
20. Class group discrete logarithms
Once the class group is decomposed into invariant factors, an ideal class can be represented by coordinates in the finite abelian group.
The class-group discrete logarithm problem asks for exponents expressing one class in terms of chosen generators. With Smith transformation data, relation-matrix computations can provide these coordinates directly.
This is different from a multiplicative finite-field discrete logarithm, although both are finite abelian group problems.
21. Class number, regulator and analytic checks
The analytic class number formula relates the class number h_K, regulator R_K, roots of unity, discriminant and residues of the Dedekind zeta function.
Computational systems can use analytic estimates to check whether a collected relation lattice and unit lattice have the correct combined index.
This is powerful but introduces numerical approximation and explicit error bounds. A numerical agreement without a rigorous error interval is evidence rather than certification.
22. A general computational workflow
Step 1: compute O_K, an integral basis and the discriminant. Step 2: choose a factor base with a justified generation bound. Step 3: decompose the small rational primes into prime ideals.
Step 4: collect factor-base-smooth principal ideals. Step 5: build the exponent relation matrix. Step 6: compute HNF/SNF and candidate invariant factors.
Step 7: certify relation completeness and factor-base generation. Step 8: compute or certify units and regulator as needed. Step 9: expose class coordinates and principal-ideal tests.
23. Verification receipts
Each relation row should retain the algebraic integer α and the exact ideal factorisation of (α). Each factor-base ideal should retain its norm and prime decomposition data.
The Smith computation should retain transformation matrices or at least exact invariant-factor certificates. A final class-number claim should retain the argument showing that no missing generators or relations remain.
For Q(√−5), the receipt is compact: D=−20, Minkowski bound <3, p=(2,1+√−5) of norm 2, no element norm 2, p²=(2), hence Cl≅Z/2Z.
24. Common mistakes
1. Treating a set of collected relations as complete without proof. 2. Choosing a factor base without proving it generates the class group. 3. Computing ideals in the wrong order instead of O_K. 4. Confusing an ideal norm with an element norm.
5. Assuming trivial class coordinates automatically give a small generator. 6. Ignoring units when normalising principal generators. 7. Using floating lattice output as an exact relation. 8. Reporting only the class number when the invariant-factor structure is available.
25. Practice set
1. Define the ideal class group. 2. What is the class number? 3. State Minkowski’s ideal-class bound. 4. Compute the bound for Q(√−5).
5. Why do only ideal norms 1 and 2 need be checked? 6. Define p=(2,1+√−5) and state its norm. 7. Why is p not principal? 8. What relation does p satisfy?
9. Deduce the complete class group. 10. What is the relation matrix in this one-generator example? 11. What does its Smith form say? 12. Define a factor base.
13. What makes a principal ideal relation useful? 14. Why can an incomplete relation matrix overestimate the class group? 15. How do units enter principal ideal testing? 16. What is one role of HNF and one role of LLL in this computation?
26. Answers
1. Nonzero fractional ideals modulo principal fractional ideals. 2. Its finite order. 3. Every class contains an integral ideal of norm at most (4/π)^r2 n!/n^n √|D_K|. 4. (2/π)√20≈2.847.
5. Ideal norms are positive integers below three. 6. Its norm is two. 7. Principal would require an algebraic integer a+b√−5 with a²+5b²=2, which is impossible. 8. p²=(2), so [p] has order two.
9. Cl(Q(√−5))≅Z/2Z. 10. [2]. 11. The quotient has invariant factor two. 12. A finite chosen set of prime ideals intended to generate the class group.
13. It converts a principal ideal factorisation into an integer exponent relation among factor-base classes. 14. Missing relations mean quotienting by too small a relation lattice. 15. Multiplying a generator by a unit preserves the ideal and can balance its embedding size. 16. HNF normalises exact ideal/module bases; LLL shortens lattices to help search for useful elements and relations.
Sources and further study
Harvard Math 123 notes give the explicit result Cl(Q(√−5))≅Z/2Z and the ideal calculation p²=(2). Kimball Martin’s number theory notes give the Minkowski-bound computation and the same class-group representatives. Henri Cohen’s A Course in Computational Algebraic Number Theory develops general class-group, unit and relation algorithms.
Computational Number Theory — Batch 05
Guide 17: Binary Quadratic Forms, Reduction, Composition and Class Groups
Guide 18: Smith & Hermite Normal Forms, Integer Modules and Exact Lattice Arithmetic
Guide 19: Dirichlet Unit Theorem, Regulators and Logarithmic Unit Lattices
Guide 20: Class Group Algorithms, Minkowski Bounds, Relation Matrices and Principal Ideal Tests