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 ([Cohen, 1993, Heß, 1996]), 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 ([Biasse, n.d.]) 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
verbose        : ClassGroup                    Default: Verbose : 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, [Pauli and Klüners, 2005].

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.

ClassNumber(O: parameters): RngOrd -> RngIntElt

ClassNumber(K: parameters): FldNum -> RngIntElt

Bound  : RngIntElt                     Default: MinkowskiBound
Proof  : MonStgElt                     Default: "Full"
Al     : MonStgElt                     Default: "Automatic"
verbose: ClassGroup                    Default: Verbose : 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, 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 that \(e\) [Belabas and Friedman, 2015].

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 (ex-92eeba)

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

Run in calculatorCopy input

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)

Run in calculatorCopy input

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]
]

Run in calculatorCopy input

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

Run in calculatorCopy input

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 calculatorCopy input

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: 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 calculatorCopy input

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.