This section describes the functions related to finding class groups and class numbers for (the maximal order O 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 correctly one has to make sure 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, and that the final stage, which may be time consuming, is properly executed. Optional arguments allow the user to override these, but correctness of such results can not be guaranteed.
It should be stressed that by default a guaranteed result is computed using the Minkowski bound. Thus even for innocent looking fields it may take considerable time. In comparison, pari (as of version 2.0) will by default use a much smaller bound giving results that are not guaranteed even under GRH. On the other hand, it will be much faster. It is possible to use the same bounds in Magma. In this case the running times will be similar.
When the discriminant of an order is very large (above 1030) a sieving method developed by [Bia] is used. Using this method the relations are derived using an analogue of the number field sieve. Lattice sieving and the special-Q are also used. The verbose flag "ClassGroupSieve" can be set to view information about the computation.
Once a class group computation has been completed, the results are stored with the order.
All functions mentioned in this section support the verbose flag ClassGroup up to a maximum value of 5.
Ideals in Magma are discussed in Section Ideals and Quotients.
It is also possible to drive the class group computation "by hand", that is one can call the individual parts one by one to for example re-create a class group computation:
Given an order O as well as a positive integer bound B, return a sequence consisting of all prime ideals in O whose norm is a rational prime not exceeding the bound B.
Bound: RngIntElt Default: MinkowskiBound
Proof: MonStgElt Default: "Full"
Enum: BoolElt Default: true
Al: MonStgElt Default: "Automatic"
SetVerbose("ClassGroup", n): Maximum: 5
SetVerbose("ClassGroupSieve", n): Maximum: 5
The group of ideal classes for the ring of integers O of the number field K is returned as an abelian group, together with a map from this abstract group to O. The map admits inverses and can therefore be used to compute "discrete logarithms" for the class group.With the default values for the optional parameters the Minkowski bound is used and the last step of the algorithm verifies correctness (see the explanation above), hence a fully proven result is returned.
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.
If Enum := false, then instead of enumerating short elements to get relations, Magma will use random linear combinations of a reduced basis instead. For "small" fields this will typically slow down the computations, but for large fields it is sometimes not possible to find any point using enumeration so that this is necessary for "large" fields. Unfortunately, there is no known criterion to decide beforehand if a field is "large" or "small".
If Al is set to "Sieve" (regardless of the size of the discriminant) or the discriminant of O is greater than 1030 then the sieving method developed by [Bia] is used. If Al is set to "NoSieve" then this sieving method will not be used regardless of the size of the discriminant.
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 pricipal ideals. The algorithm and its implementation are due to Klüners and Pauli, [PK05].
The class group of the order O or the number field K assuming the generalized Riemann hypothesis.
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
SetVerbose("ClassGroupSieve", 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.
An integral upper bound for norms of generators of the ideal class group for the number field K or the maximal order O assuming the generalized Riemann hypothesis.
An unconditional integral upper bound for norms of the generators of the ideal class group for the number field K or the maximal order O.
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, or a number field K with maximal order O, generate relations for each prime ideal in the factor basis for O with bound B on the norms of the ideals. The relations are given by rows in a matrix. If at some stage the relations generate the trivial group, no more relations are generated.
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;
33
Even though the MinkowskiBound is only 3, we take 33 as the bound.
The reason for this behaviour is that the factor base has to have at least
some elements (about 20) if it is non-empty. Otherwise the search for
relations is hopeless.
> 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)As one can see, the RelationMatrix basically stores the valuation of the elements of Relations at the prime ideal contained in 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
> time ClassGroup(K);
Abelian Group isomorphic to Z/10
Defined on 1 generator
Relations:
10*$.1 = 0
Mapping from: Abelian Group isomorphic to Z/10
Defined on 1 generator
Relations:
10*$.1 = 0 to Set of ideals of Maximal Equation Order with defining
polynomial x^5 - 14*x^4 + 14*x^3 - 14*x^2 + 14*x - 14 over Z
Time: 14.600
Note, that is an unconditional result. As one can see, the BachBound
(proven under GRH) is much smaller than MinkowskiBound. The difference
shows up in the running time:
> K := NumberField(x^5-14*x^4+14*x^3-14*x^2+14*x-14); > time _, _ := ClassGroup(K: Bound := BachBound(K)); Time: 7.080In comparison, pari (2.0.20) uses an even smaller bound as default, namely BachBound(K)/40 for fields of degree >2 and BachBound(K)/20 for quadratics.
> K := NumberField(x^5-14*x^4+14*x^3-14*x^2+14*x-14); > time _, _ := ClassGroup(K: Bound := Floor(BachBound(K)/40)); Time: 1.300In comparison, bnfinit in pari (version 2.0.20) takes about 1.4 seconds for this example.
Note, that in general one cannot use arbitrarily small bounds. If they are too small, the computation time will increase again as the system will not be able to find any relations.
> R<x> := PolynomialRing(IntegerRing());
> f := x^3 + 3592347*x^2 - 6*x + 3989864;
> K<y> := NumberField(f);
> time G, m := ClassGroup(K : Al := "Sieve", Proof := "GRH");
Time: 3.200
> G, m;
Abelian Group isomorphic to Z/6
Defined on 1 generator
Relations:
6*G.1 = 0
Mapping from: GrpAb: G to Set of ideals of Maximal Order of Equation Order with
defining polynomial x^3 + 3592347*x^2 - 6*x + 3989864 over Z
> m(G.1);
Ideal
Two element generators:
[4373, 0, 0]
[2118, 1, 0]
> $1 @@ m;
G.1
> IsPrincipal($2^6);
true
> f:= x^5 + 3330*x^3 - 50*x + 107392;
> K<y> := NumberField(f);
> time G, m := ClassGroup(K : Al := "Sieve", Proof := "GRH");
Time: 9.930
> G, m;
Abelian Group of order 1
Mapping from: GrpAb: G to Set of ideals of Maximal Order of Equation Order with
defining polynomial x^5 + 3330*x^3 - 50*x + 107392 over Z
Creates a class group process by computing a factor basis containing all ideals of norm ≤B in the order O and returning this factor basis.
Computes an approximation to the Euler product for the order O using only prime ideals over prime numbers of norm ≤B.
Adds a relation (order element) E to the class group process of the parent of E. This function returns true exactly when the element factors over the factor basis and if the new relation matrix is of full rank.
Finalizes a class group process for the order O, that is, it computes (if possible) the class group structure based on the current relation matrix and a basis of the unit group generated by the nullspace of the relation matrix.This function returns true when the class group is determined by the current data. In order to use this function, one has to create a factor basis and then add enough relations.
This function completes an already started class group process for the order O by using the internal functions to look for relations until the class group can be determined.
This function verifies the "completeness" of the current factor basis for the order O with respect to the prime ideals of norm between L and U. That is, for all prime ideals which norm is between L and U, the function tries to find a relation between the new prime ideal and the prime ideals already in the factor basis. If successful, this means that the new prime ideal does not contribute anything to the class group that is not already known and can therefore safely be ignored.This function does not return if unsuccessful.
For an order O where the class group is already computed, decide if results of the discrete logarithm computation for the class group are stored. For example if the order O is going to be used extensively as a coefficient ring for class field computations, then every time discrete logatrithms 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. Setting the flag f to true will help to keep computation times down - at the expense of additional use of memory. This functionality is disabled by default.
For an order O where the class group has been computed check if discrete logarithm values should be stored or not.
It is possible to preset the bounds to be used in all class group computations. Two bounds can be specified: the first controls the size of the factor base used in the first stage of the class group computation, and the second is the bound used in the checking stage (this controls the level of rigour of the computation).
The bounds may be specified using either of the intrinsics below; SetClassGroupBounds is a simple special case of SetClassGroupBoundMaps, provided for the user's convenience.
This determines the bounds that will be used in all subsequent calls to ClassGroup. The argument can be an integer n (then the bounds are both set to this constant). Alternatively the argument can be a string: either "GRH" (then the bounds will guarantee correctness assuming GRH) or "PARI" (this is intended to give roughly the same level of rigour as PARI).
This determines the bounds that will be used in all subsequent calls to ClassGroup. The arguments should be maps from PowerStructure(RngOrd) (which is the parent object of all orders in number fields) to integers.The bounds used when ClassGroup is called for a number field will be the bounds for the maximal order of that field.
> map1 := map< PowerStructure(RngOrd) -> Integers() | > order :-> BachBound(order) div 10 >; > map2 := map< PowerStructure(RngOrd) -> Integers() | > order :-> MinkowskiBound(order) >; > SetClassGroupBoundMaps( map1, map2);