|
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
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 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.
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:
Subsections
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.
ClassGroup(O: parameters) : RngOrd -> GrpAb, Map
ClassGroup(K: parameters) : FldNum -> GrpAb, Map
Bound: RngIntElt Default: MinkowskiBound
Proof: MonStgElt Default: "Full"
Enum: BoolElt Default: true
SetVerbose("ClassGroup", 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".
PicardGroup(O) : RngOrd -> GrpAb, Map
For a (possibly non-maximal) order O, compute the ring class group (Picard
group) of O, ie. the group of invertable ideals in O modulo pricipal
ideals. The algorithm and its implementation are due to
Klüners and Pauli, [PK05].
ConditionalClassGroup(K) : FldNum -> GrpAb, Map
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.
ClassNumber(K: parameters) : FldNum -> RngIntElt
Bound: RngIntElt Default: MinkowskiBound
Proof: MonStgElt Default: "Full"
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.
BachBound(O) : RngOrd -> RngIntElt
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.
MinkowskiBound(O) : RngOrd -> RngIntElt
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.
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.
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, B) : RngOrd, RngIntElt -> ModHomElt
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.
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;
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 larger 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.080
In 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.300
In 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.
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 factorbasis. 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.
SetClassGroupBounds(n) : RngIntElt ->
SetClassGroupBounds(string) : MonStgElt ->
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.
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);
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
