|
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.
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
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 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.
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(K) : FldNum -> GrpAb, Map
This is equivalent to calling ClassGroup(O:Proof := "GRH").
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"
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.
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(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(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.
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 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 ≤B.
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 ≤B.
Assuming GRH, the best known error bounds for ResidueGRH are smaller than the
error bounds for EulerProduct.
Assuming GRH, this function computes a bound B such that ResidueGRH will have a
logarithmic error less that e [BF15].
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.
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;
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.
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);
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.
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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|