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 ([Heß96], [Coh93]), 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).
Set whether the class group algorithm prints warnings about expensive computations.
Bound: RngIntElt Default: MinkowskiBound
Proof: MonStgElt Default: "Full"
Al: MonStgElt Default: "Automatic"
UsePowerProduct: BoolElt Default: false
SetVerbose("ClassGroup", n): Maximum: 3
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 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 := "GRH", everything remains as in the default case except that a bound based on the GRH is used to replace the Minkowski bound. This bound may be enlarged setting the Bound parameter accordingly. The result will hence be correct under the GRH.
If Proof := "Bound", the computation stops if an independent set of relations between the prime ideals below the chosen bound is found. The relations may not be maximal.
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) a guaranteed result is computed. This is equivalent to Bound := MinkowskiBound(K) and Proof := "Subgroup".
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.
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.
This is equivalent to calling ClassGroup(O) after SetClassGroupBounds("GRH") is invoked.
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.
Bound: RngIntElt Default: MinkowskiBound
Proof: MonStgElt Default: "Full"
Al: MonStgElt Default: "Automatic"
SetVerbose("ClassGroup", n): Maximum: 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.
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.
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.
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.
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.
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.
Computes an approximation to the Euler product for the order O using only prime ideals over prime numbers of norm ≤B.
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.
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.
Given a maximal order O where the class group has been computed previously, the resulting relation matrix is returned.
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.
Let ai be the generators for the cyclic factors of the class group of O. This function returns generators for aici where ci is the order of ai in the class group.
> 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
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.
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.
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.
> map1 := map< PowerStructure(RngOrd) -> Integers() | > order :-> BachBound(order) div 10 >; > map2 := map< PowerStructure(RngOrd) -> Integers() | > order :-> MinkowskiBound(order) >; > SetClassGroupBoundMaps( map1, map2);
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.
These functions access and set whether or not the map returned by ClassGroup(O) stores the results of calls to the inverse map.