Ideal Class Groups

This section describes functions for computing the group of ideal classes of the maximal order of an absolute number field. The method usually employed is the relation method ([Coh93, Hes96]), basically consisting of the following steps. In the first step a list of prime ideals of norm below a given bound is generated, the factor basis. In the second step a search is conducted to find in each of the prime ideals a few elements for which the principal ideals they generate factor completely over the factor basis. Using these relations, a generating set for the ideal class group is derived (via matrix echelonization), and in the final step it is verified that the correct orders for the generators have been found. To determine the class group or class number rigorously, one must ensure that all ideals having norm smaller than the Minkowski bound – or smaller than the Bach bound, if one assumes the generalized Riemann hypothesis – are taken into consideration. It should be stressed that, by default, a guaranteed result is computed using the Minkowski bound. Even for innocent looking fields, this may take considerable time. In contrast, Pari (from version 2.0), by default, uses a much smaller bound giving results that are not guaranteed. In Magma, to perform computations comparable to Pari, the user must request a non-rigorous computation. The recommended way is to globally control this by using SetClassGroupBounds("GRH"), before calling routines involving class group calculations. Note that it is better to give "GRH" here than to give a numerical value for the bound. Starting from version 2.20, a new implementation of the sieve algorithm for finding relations ([Bia]) is used automatically, as a subroutine, to the extent it is advantageous. This method is very effective for fields of degree up to \(5\), and to a lesser extent degree \(6\). When a class group computation has been completed, the results are stored with the order (to avoid repeated computation).

SetPrintClassGroupWarnings(b): BoolElt: Set whether the class group algorithm prints warnings about expensive computations.

ClassGroup(O: parameters): RngOrd -> GrpAb, Map

ClassGroup(K: parameters): FldNum -> GrpAb, Map

Bound          : RngIntElt                    Default: MinkowskiBound
Proof          : MonStgElt                    Default: "Full"
Al             : MonStgElt                    Default: "Automatic"
UsePowerProduct: BoolElt                      Default: false
ClassGroup     : Verbose                      Default: 3 % internally 5, but > 3 is not useful for users

The group of ideal classes in the ring of integers \(O\) of a number field \(K\) is returned as an abelian group, together with a map from this abstract group to the set of ideal of \(O\). The map is defined in both directions: in the inverse direction, it returns the ideal class of a given ideal of \(O\). Since V2.28, a distributed parallel version of the main algorithm is available. As usual, one first uses SetNthreads and optionally StartWorkers to select the number of cores/workers before the class group algorithm is called. By default, all computations are unconditionally rigorous: this means that a final step must be performed, checking all prime ideals up to the Minkowski bound (which is impractical for many fields). To perform conditional computations (under “GRH”, or with a smaller bound), the recommended approach is to set the rigour for all class groups by using SetClassGroupBounds("GRH") before calling ClassGroup. Note that it is better to give "GRH" than to give a numerical value for the bound. The alternative approach is to use the parameters Proof and Bound, which have the following effect. If Proof := "GRH", a bound for generators of the class group based on the GRH is used to replace the Minkowski bound. Further, a GRH based aopproximation of the residue of the Dedekind zeta function is assumed to be correct. The result will hence be correct under the GRH. If Bound is set to some positive integer \(M\), \(M\) is used instead of the Minkowski bound. The validity of the result still depends on the "Proof" parameter. If Proof := "Bound", the maximum of the given bound and a GRH based bound for a generating set of the class group is used. Further, a GRH based aopproximation of the residue of the Dedekind zeta function is assumed to be correct. The result will hence be correct under the GRH. If Proof := "Subgroup", a maximal subset of the relations is constructed. In terms of the result, this means that the group returned will be a subgroup of the class group (i.e. the list of prime ideals considered may be to small). If Proof := "Full" (the default) the bound given by "SetClassGroupBounds" is used. By default this is the Minkowski bound and a guaranteed result is computed. This is equivalent to Bound := MinkowskiBound(K) and Proof := "Subgroup". But, if SetClassGroupBounds("GRH"); was used, the result is conditional and correct under the GRH.

If only Bound is given, the Proof defaults to "Subgroup".

Finally, giving Proof := "Current" is the same as repeating the last call to ClassGroup(), but without the need to explicitly restate the value of Proof or Bound. If there was no prior call to ClassGroup, a fully proven computation will be carried out.

For quadratic fields, alternative algorithms may be selected using the Al parameter.

In some previous versions of Magma, use of the sieve algorithm was controlled by setting Al to "Sieve" or to "NoSieve". This usage is deprecated, as the choice is now made internally: the sieve algorithm is called automatically by the main class group routine to the extent it is advantageous.

If UsePowerProduct is set to true then images of group elements under the map from the class group will be returned as a power product of ideals.

RingClassGroup(O): RngOrd -> GrpAb, Map

PicardGroup(O): RngOrd -> GrpAb, Map

UsePowerProduct: BoolElt                    Default: false

For a (possibly non-maximal) order \(O\), compute the ring class group (Picard group) of \(O\), ie. the group of invertible ideals in \(O\) modulo principal ideals. The algorithm and its implementation are due to Klüners and Pauli, [PK05].

If UsePowerProduct is set to true, any computations using the images of elements of the class group will not evaluate a power product representation of ideals but instead work with this representation. This can be substantially more efficient for some orders.

ConditionalClassGroup(O): RngOrd -> GrpAb, Map
ConditionalClassGroup(K): FldNum -> GrpAb, Map: This is equivalent to calling ClassGroup(O:Proof := "GRH").

ClassGroupPrimeRepresentatives(O, I): RngOrd, RngOrdIdl -> Map: For the maximal order \(O\) of some absolute number field \(k\) and an ideal \(I\) of \(O\), compute a set of prime ideals in \(O\) that are coprime to \(I\) and represent all ideal classes. The map, mapping elements of the class group to the primes representing the ideal class is returned.

PrimeRepresentative(c, f: parameters): GrpAbElt, Map -> RngOrdIdl

DegreeOne: BoolElt                    Default: false

Given an element c of the abelian group A and the map f returned by ClassGroup for a maximal order \(O\), this function returns a prime ideal of \(O\) lying in the ideal class \(c\). If DegreeOne is set to true, the prime ideal returned will have residue degree one over the rationals. If Minimal is set to true, the search proceeds by splitting successive rational primes and testing whether a prime above lies in the class \(c\), which tends to produce an ideal of small norm. Otherwise, the search enumerates lattice points of \(O\) until an ideal in the required class is found.

PrimeRepresentative(I: parameters): RngOrdIdl -> RngOrdIdl

DegreeOne: BoolElt                    Default: false
Minimal  : BoolElt                    Default: false

Given an ideal \(I\) of a maximal order \(O\) of a number field, this function returns a prime ideal of \(O\) lying in the same ideal class as \(I\). The search is carried out by enumerating lattice points of \(O\). If DegreeOne is set to true, the prime ideal returned will have residue degree one.

ClassNumber(O: parameters): RngOrd -> RngIntElt

ClassNumber(K: parameters): FldNum -> RngIntElt

Bound     : RngIntElt                    Default: MinkowskiBound
Proof     : MonStgElt                    Default: "Full"
Al        : MonStgElt                    Default: "Automatic"
ClassGroup: Verbose                      Default: 5

Return the class number of the ring of integers \(O\) of a number field \(K\). The options for the parameters are the same as for ClassGroup.

MinkowskiBound(K): FldNum -> RngIntElt
MinkowskiBound(O): RngOrd -> RngIntElt: This returns the Minkowski bound for the maximal order of the given field \(K\). This is an unconditional integer upper bound for norms of the generators of the ideal class group of the maximal order.

BachBound(K): FldNum -> RngIntElt
BachBound(O): RngOrd -> RngIntElt: This returns the Bach bound for the maximal order of the given field \(K\). This is an integer upper bound for norms of the generators of the ideal class group of the maximal order which holds if the generalized Riemann hypothesis is true.

GRHBound(K): FldNum -> RngIntElt
GRHBound(O): RngOrd -> RngIntElt: This returns an integer upper bound, proven assuming the generalized Riemann hypothesis, for norms of the generators of the ideal class group of the maximal order of the given field \(K\). The function returns the best bound obtainable in Magma. In the current version, in addition to the Bach bound, the algorithm uses results of Belabas and Grenie, Molteni, which often produce bounds that are significantly smaller than the Bach bound.

FactorBasisVerify(O, a, b): RngOrd, RngIntElt, RngIntElt: This verifies that every prime ideal of the order \(O\) with norm between \(a\) and \(b\) is equivalent to an ideal of \(O\) with norm smaller than \(a\). This function requires that a class group computation has already been done for \(O\).

Class Group Internals

The results of a class group computation, which are stored internally on the order \(O\), are a factor base, a set of relations, and the relation matrix. (Units are also stored, and used in later computations.) Access to this data is provided by functions below. Also listed are functions for independently producing data of the same form; these do not use the same code as the internal class group computation.

EulerProduct(O, B): RngOrd, RngIntElt -> FldReElt: Computes an approximation of the residue of the Dedekind zeta function of \(O\) at \(s=1\) via the Euler product for the order \(O\) using only prime ideals over prime numbers of norm \(\leq B\).

ResidueGRH(O, B): RngOrd, RngIntElt -> FldReElt: Computes an approximation of the residue of the Dedekind zeta function of \(O\) at \(s=1\) as a sum involving only prime ideals of norm \(\leq B\). Assuming GRH, the best known error bounds for ResidueGRH are smaller than the error bounds for EulerProduct.

ResidueGRHbound(O, e): RngOrd, FldReElt -> FldReElt: Assuming GRH, this function computes a bound \(B\) such that ResidueGRH will have a logarithmic error less than \(e\) [BF15].

FactorBasis(K, B): FldNum, RngIntElt -> [ RngOrdIdl ]
FactorBasis(O, B): RngOrd, RngIntElt -> [ RngOrdIdl ]: Given the maximal order \(O\), or a number field \(K\) with maximal order \(O\), this function returns a sequence of prime ideals of norm less than a given bound \(B\).

FactorBasis(O): RngOrd -> [ RngOrdIdl ], Integer: Given the maximal order \(O\) where the class group has previously been computed, this function returns a sequence of prime ideals that have been used as factor basis for the class group computation. In addition the used upper bound for the factor basis is returned. This bound can be different from the bound passed in using the Bound := bound parameter.

RelationMatrix(O): RngOrd -> ModHomElt: Given a maximal order \(O\) where the class group has been computed previously, the resulting relation matrix is returned.

Relations(O): RngOrd -> ModHomElt: Given a maximal order \(O\) where the class group has been computed previously, the vector containing the order elements used to compute the class group is returned.

ClassGroupCyclicFactorGenerators(O): RngOrd -> ModHomElt: Let \(a_i\) be the generators for the cyclic factors of the class group of \(O\). This function returns generators for \(a_i^{c_i}\) where \(c_i\) is the order of \(a_i\) in the class group.

Example: Class Group of a Real Quadratic Field (ex-92eeba)

Run in calculator (opens in a new tab)

We give an example of a class group calculation, illustrating some of the functions.

> R<x> := PolynomialRing(Integers());
> O := MaximalOrder(x^2-10);
> C, m := ClassGroup(O);
> C;
Abelian Group isomorphic to Z/2
Defined on 1 generator
Relations:
    2*C.1 = 0
> m(C.1);
Prime Ideal of O
Two element generators:
    [2, 0]
    [0, 1]
> p := Decomposition(O, 31)[1][1];
> p;
Prime Ideal of O
Two element generators:
    [31, 0]
    [45, 1]
> p @@ m;
0
> IsPrincipal(p);
true
> p := Decomposition(O, 37)[1][1];
> p @@ m;
C.1
> IsPrincipal(p);
false
> MinkowskiBound(O);
3
> F, B := FactorBasis(O);
> B;
50

Note that although the MinkowskiBound is only \(3\), the algorithm chose a larger bound for the computation internally.

> r := Relations(O);
> M := RelationMatrix(O);
> [ Valuation(r[1][1], x) : x in F];
[ 0, 0, 0, 0, 0, 1, 1, 0 ]
> M[1];
(0 0 0 0 0 1 1 0)

The RelationMatrix stores the valuation of the Relations at each prime ideal contained in the FactorBasis.

> f,g := IsPrincipal(m(C.1)^2);
> f;
true
> g;
[2, 0]
> ClassGroupCyclicFactorGenerators(O);
[
    [2, 0]
]

Now we will consider some larger fields to demonstrate the effect of the "Bound" parameter:

> K := NumberField(x^5-14*x^4+14*x^3-14*x^2+14*x-14);
> MinkowskiBound(K);
21106
> BachBound(K);
7783
> GRHBound(K);
259
> time C := ClassGroup(K);
Time: 0.510
> C;
Abelian Group isomorphic to Z/10
Defined on 1 generator
Relations:
    10*$.1 = 0

This is an unconditional result. The conditional computation, assuming GRH, is faster. Note that the BachBound should NOT be used – the better GRHBound is much smaller. (They both are bounds which guarantee the class group computation is correct assuming GRH.)

> K := NumberField(x^5-14*x^4+14*x^3-14*x^2+14*x-14);
> time #ClassGroup(K : Proof := "GRH");
10
Time: 0.100
> K := NumberField(x^5-14*x^4+14*x^3-14*x^2+14*x-14);
> time #ClassGroup(K : Bound := BachBound(K));
10
Time: 0.280

Run in calculator (opens in a new tab)

Setting the Class Group Bounds

These functions control the rigour of all subsequent of class group computations. The recommended way is SetClassGroupBounds("GRH"). This is the minimum possible level of rigour with the current implementation – all class groups will be correct if GRH holds, regardless of all settings.

SetClassGroupBounds(string): MonStgElt: If this is called with the string “GRH”, all subsequent class group computations will be performed in such a way that either they are correct, or GRH does not hold.

SetClassGroupBounds(n): RngIntElt: The integer \(n\) is the proof bound to be used in all subsequent calls to ClassGroup. That is, each class group computed will be correct if it is generated by ideals of norm at most \(n\).

Example: Setting Class Group Bounds (ex-3fbfbd)

We select some bounds which will then be used in all calls to ClassGroup. (The class group computations will be rigorous, but will use a relatively small factor base for the first part of the computation).

> map1 := map< PowerStructure(RngOrd) -> Integers() |
>                             order :-> BachBound(order) div 10 >;
> map2 := map< PowerStructure(RngOrd) -> Integers() |
>                             order :-> MinkowskiBound(order) >;
> SetClassGroupBoundMaps( map1, map2);

Run in calculator (opens in a new tab)

Class Group Map Caching

The map returned by ClassGroup can be used to compute the ideal class of a given ideal. In applications which involve many repeated calls to this, it may be advantageous to store the results of each call (although this may also use a lot of memory). By default, results are not stored.

For example, if the order \(O\) is to be used extensively as a coefficient ring for class field computations, then every time discrete logarithms of ray class groups are computed, a discrete logarithm computation in the class group is triggered. In particular when investigating the cohomology of various extensions over \(O\), this involves testing the same ideals over and over again.

ClassGroupGetUseMemory(O): RngOrd -> BoolElt
ClassGroupSetUseMemory(O, f): RngOrd, BoolElt: These functions access and set whether or not the map returned by ClassGroup(O) stores the results of calls to the inverse map.

Ideal Class Groups#

Class Group Internals#

Setting the Class Group Bounds#

Class Group Map Caching#

Ideal Class Groups

Class Group Internals

Setting the Class Group Bounds

Class Group Map Caching