Global function fields admit a class field theory in the same way as number fields do (CLASS FIELD THEORY). From a computational point of view the main difference is the use of divisors rather than ideals.
This Magma module should be considered as experimental. Especially the interface will change for the next release.
Class field theory deals with the abelian extensions of a given field. In the number field case, all abelian extensions can be parametrized using more general class groups, in the case of global function fields, the same will be achieved using the divisor class group and extensions of it.
The ray divisor class group Cl_m modulo a divisor m of a global function field K is defined via the following exact sequence: 1 to k^ x to O^times_m to Cl_m to Cl to 1 where O^ * _m is the group of units in the "residue ring" mod m, k is the exact constant field of K and Cl is the divisor class group of K. This follows the methods outlined in [HPP03].
Let D = sum n_iP_i be an effective divisor for some places P_i (so n_i>0). The RayResidueRing R is the product of the unit groups of the local rings: R = O^times_m := prod (O_(P_i)/P_i^(n^i))^ x where O_(P_i) is the valuation ring of P_i.The map returned as the second return value is from the RayResidueRing into the function field and admits a pointwise inverse for the computation of discrete logarithms.
Let D be an effective (positive) divisor. The RayClassGroup modulo D is a quotient of the group of divisors that are coprime to D modulo certain principal divisors. It may be computed using the exact sequence: 1 to k^ x to O^times_m to Cl_m to Cl to 1Note that in contrast to the number field case, the ray class group of a function field is infinite.
The map returned as the second return value is the map from the RayClassGroup into the group of divisors and admits a pointwise inverse for the computation of discrete logarithms.
Since this function uses the class group of the function field in an essential way, it may be necessary for large examples to precompute the class group. Using ClassGroup directly gives access to options that may be necessary for complicated fields.
This is a version of the pointwise inverse of the map returned by RayClassGroup. The main difference is that using the intrinsics the values are cached, ie. if the same place (or divisor) is decomposed twice, the second time will be instantaneous.A disadvantage is that in situations where a great number of discrete logarithms is computed for pairwise different divisors, a great amount of memory is wasted.
First we have to create a function field:
> k<w> := GF(4); > kt<t> := PolynomialRing(k); > ktx<x> := PolynomialRing(kt); > K := FunctionField(x^3-w*t*x^2+x+t);Now, to create some divisors:
> lp := Places(K, 2); > D1 := 4*lp[2]+2*lp[6]; > D2 := &+Support(D1);And now the groups:
> G1, mG1 := RayResidueRing(D1); G1;
Abelian Group isomorphic to Z/2 + Z/2 + Z/2 + Z/2 + Z/2 + Z/2 +
Z/2 + Z/4 + Z/60 + Z/60
Defined on 10 generators
Relations:
2*G1.1 = 0
2*G1.2 = 0
2*G1.3 = 0
2*G1.4 = 0
2*G1.5 = 0
2*G1.6 = 0
2*G1.7 = 0
4*G1.8 = 0
60*G1.9 = 0
60*G1.10 = 0
> G2, mG2 := RayResidueRing(D2); G2;
Abelian Group isomorphic to Z/15 + Z/15
Defined on 2 generators
Relations:
15*G2.1 = 0
15*G2.2 = 0
G_1 = O_(D_1)^ x should surject onto D_2 = O_(D_2)^ x since
D_2 | D_1:
> h := hom<G1 -> G2 | [G1.i@mG1@@mG2 : i in [1..Ngens(G1)]]>;
> Image(h) eq G2;
true
> [ h(G1.i) : i in [1..Ngens(G1)]];
[
0,
0,
0,
0,
0,
0,
0,
0,
G2.2,
G2.1
]
Ray class groups are similar and can be mapped in the same way:
> R1, mR1 := RayClassGroup(D1);
> R2, mR2 := RayClassGroup(D2); R2;
Abelian Group isomorphic to Z/5 + Z/15 + Z
Defined on 3 generators
Relations:
5*R2.1 = 0
15*R2.2 = 0
> hR := hom<R1 -> R2 | [R1.i@mR1@@mR2 : i in [1..Ngens(R1)]]>;
> Image(hR);
Abelian Group isomorphic to Z/5 + Z/15 + Z
Defined on 3 generators in supergroup R2:
.1 = R2.1
.2 = R2.2
.3 = R2.3
Relations:
5 *.1 = 0
15*.2 = 0
> 1 eq R2;
true
Note that the missing C_3 part in comparing G_2 and R_2 corresponds
to factoring by k^ x . The free factor comes from the class group.
Now, let us investigate the defining exact sequence for R_2:
> C, mC := ClassGroup(K); > h1 := map<K -> G2 | x :-> (K!x)@@mG2>; > h2 := hom<G2 -> R2 | [ G2.i@mG2@@mR2 : i in [1..Ngens(G2)]]>; > h3 := hom<R2 -> C | [ R2.i@mR2@@mC : i in [1..Ngens(R2)]]>; > sub<G2 | [h1(x) : x in k | x ne 0]> eq Kernel(h2); > Image(h2) eq Kernel(h3); > Image(h3) eq C;So indeed, the exact sequence property holds.
Since the beginning of class field theory one of the core problems has been to find defining equations for the fields. Although most of the original proofs are essentially constructive, they rely on complicated and involved computations and thus were not suited for hand computations.
The method used here to compute defining equations is essentially the same as the one used for number fields. The main differences are due to the problem of p-extensions in characteristic p where Artin-Schreier-Witt theory is used, and the fact that the divisor class group is infinite.
WithAut: BoolElt Default: false
SetVerbose("ClassField", n): Maximum: 3
Given an effective divisor D and a subgroup U of the RayClassGroup Cl_D of D such that the quotient Cl_D/U is finite, compute defining equations for the corresponding (ray) class field.More precisely: Let Cl/U = prod Cl/U_i be a decomposition such that the Cl/U_i are cyclic of prime power order. Then for each U_i the function will return the corresponding function field.
If WithAut is true, the second sequence returned contains a generating automorphism for each of the fields returned as the first return value.
> k<w> := GF(4); > kt<t> := PolynomialRing(k); > ktx<x> := PolynomialRing(kt); > K := FunctionField(x^3-w*t*x^2+x+t); > lp := Places(K, 2); > D := 4*lp[2]+2*lp[6]; > R, mR := RayClassGroup(D);Let us compute the maximal extension of exponent 5 such that the infinite place is totally split. This means that we
> inf := InfinitePlaces(K); > U1 := sub<R | [x@@ mR : x in inf]>; > U2 := sub<R | [5*R.i : i in [1..Ngens(R)]]>; > U3 := sub<R | U1, U2>; > RayClassField(D, U3); > E := 1[1]; > InfinitePlaces(E); 10Which shows that all the places in ( inf) split completely.
Now, suppose we still want the infinite places to split, but now we are looking for degree 4 extensions such that the quotient of genus by number of rational places is maximal:
> q, mq := quo<R | U1>; > l4 := [ x`subgroup : x in Subgroups(q : Quot := [4])]; > #l4; 768 > s4 := [<Genus(D, u), NumberOfPlacesOfDegreeOne(D, u), u> > where u := x@@mq : x in l4]; > Maximum([x[2]/x[1] : x in s4]); 16/5 15 > E := RayClassField(D, s4[15][3])[1];Since this a are quite a lot, we won't investigate them here further. extensions such that the quotient of genus by number of rational places is maximal:
> l22 := [ x`subgroup : x in Subgroups(q : Quot := [2, 2])];
> #l22; 43435
> q, mq := quo<R | U1>; > l4 := [ x`subgroup : x in Subgroups(q : Quot := [4])]; > #l4; 768 > s4 := [<Genus(D, u), NumberOfPlacesOfDegreeOne(D, u), u> > where u := x@@mq : x in l4]; > Maximum([x[2]/x[1] : x in s4]); 16/5 15 > E := RayClassField(D, s4[15][3])[1];Since this a are quite a lot, we won't investigate them here further.
> l22 := [ x`subgroup : x in Subgroups(q : Quot := [2,2])];
> #l22; 43435
Let D be an effective divisor and U be a subgroup of the ray class group Cl_D. The main existence theorem of class field theory asserts that there is exactly one function field corresponding to the quotient Cl_D/U such that its Galois group is isomorphic to Cl_D/U in a canonical way.
Since the field is uniquely defined this way so are its invariants. Some of the invariants can easily be read of the groups involved. Therfore none of the function listed here will compute a set of defining equations. They can therefore be used on very large fields.
Let m be an effective divisor. This function computes the conductor of Cl_m which is the smallest divisor f such that the projection Cl_m to Cl_f is surjective.
Let m be an effective divisor and U be a subgroup of the RayClassGroup of m. This function computes the conductor of Cl_m/U which is the smallest divisor f such that the projection pi:Cl_m/U to Cl_f/pi(U) is an isomorphism.
Let m be an effective divisor and U a subgroup of RayClassGroup such that Cl_m/U is finite. The discriminant divisor is definied as the norm of the different divisor.
Let m be an effective divisor. Since the ray class field modulo m is always an infinite field extension containing the algebraic closure of the constant field, this returns Infinity.
Let m be an effective divisor and U be a subgroup of the RayClassGroup modulo m. This functions computes the degree of the algebraic closure of the constant field in the class field corresponding to Cl_m/U. This can be infinite.
Let m be an effective divisor and U be a subgroup of the RayClassGroup modulo m. This function computes the genus of the class field corresponding to Cl_m/U.
Let m be an effective divisor and U be a subgroup of the RayClassGroup modulo m such that the quotient Cl_m/U is finite. For a place p this function will determine the decomposition type of the place in the extension definined by Cl_m/U. I.e. it will return a sequence of pairs < f, e > containing the inertia degree and ramification index for all places above p.
Let m be an effective divisor and U be a subgroup of the RayClassGroup modulo m such that the quotient Cl_m/U is finite. This function will compute the number of places of degree 1 that the class field corresponding to Cl_m/U has.
The ring of Witt vectors of length n (type RngWitt) over a global function field K parametrizes the cyclic extensions of K of degree p^n where p is the characteristic of K. Witt vectors (type RngWittElt) can be definined over any ring with positive characteristic p, the ring of Witt vectors of length n will always be of characteristic p^n. In the case of Witt vectors over finite fields, they can be seen as isomorphic to finite quotients of unramified p-adic rings.
The functionnality offered here is mainly motivated by the class field theory which deals with vectors of short length only.
The Witt rings are based on code developed by David Kohel.
Creates the ring of Witt vectors of length n. F must be a field of positive characteristic.
Witt vectors of W can be constructed from
- -
- elements of the same ring
- -
- integers
- -
- elements of the base ring
- -
- sequences of length Length(W) that can be change universed into the base ring of W
The field of coefficients of the Witt ring W.
The length (dimension) of the elements of the Witt ring W.
The list of coefficients of the Witt vector a.
The one resp. zero in W.
The Forbenius map on the Witt ring W which is defined to be the map sending vectors to vectors where every coefficient is raised to the pth power.
Computes the image of e under the Frobenius map.
The verschiebungs map, i.e. shift all coefficients on position to the right and pad with a zero in front.
Computes the image under the verschiebung map.
For finite Witt rings, ie. Witt rings definined over finite fields, return a random element.
For Witt rings where the base field admits a random function with size restriction.
A Techmüller system for R, ie. a system of representatives for the residue class field of R that is closed under multiplication.
Any ring of Witt vectors of finite length over a finite field is isomorphic to some unramified local ring. This intrinsic will create the corresponding local ring and the embedding into it.
Returns the map x |-> F(x) - x where F is the Frobenius map.,
This function computes the image of e under the Artin-Schreier map.
WithAut: BoolElt Default: true
Check: BoolElt Default: false
Abs: BoolElt Default: false
A Witt vector e = (e_1, ..., e_n) of length n over k where e_1 is not in the image of the Artin-Schreier map e_1 not in {x^p - x : x in k} defines a cyclic extension K/k of degree p^n. This function will compute K.If WithAut is true in addition to K it will compute a generating automorphism and return it as second return value.
If Abs is true, the function fill compute a K as a single step extension of k, otherwise, K will be constructed as a series of n Artin-Schreier extensions.
If Check is true, it will be verified that the extension is of degree p^n. In particular the restrictions on e_1 are tested.
This section list some related functions that are either useful in the context of class fields for function fields or are necessary for their computation. They will most certainly change their appearance.
Strict: BoolElt Default: false
Exception: DivFunElt Default: false
Raw: BoolElt Default: false
Given an effective divisor m and a sequence of pairs (Q_i, e_i) of places and elements, find an element a and a place Q_0 such that v_(Q_i)(a - e_i) >= v_(Q_i)(m), a is integral everywhere outside Q_i (0 <= i <= n).If Exception is not false, it has to be a place that will be used for Q_0.
If Strict is true, the element a will be chosen such v_(Q_i)(a - e_i) = v_(Q_i)(m)
If Raw is true, different rather technical return values are computed that are used internally.
> k<w> := GF(4); > kt<t> := PolynomialRing(k); > ktx<x> := PolynomialRing(kt); > K := FunctionField(x^3-w*t*x^2+x+t); > lp := Places(K, 2);We will now try to find an element x in K such that v_(p_i)(x - e_i) >= m_i for p_i = lp[i], m_i = i and random elements e_i:
> e := [Random(K, 3) : i in lp]; > m := [i : i in [1..#lp]]; > D := &+ [ m[i]*lp[i] : i in [1..#lp]]; > x := StrongApproximation(D, [<lp[i], e[i]> : i in [1..#lp]]); > [Valuation(x-e[i], lp[i]) : i in [1..#lp]]; [ 1, 2, 3, 4, 5, 6 ]Note, that we only required >= for the valuations, to enforce = we would need to pass the Strict option. This will double the running time.
Exception: DivFunElt Default:
Given an effective divisor m, find a place P coprime to m and an integer r >= 0 such that rP - m is a non special divisor and return r and P.If Exception is specified, it must be an effective divisor n coprime to m. In this case the function finds r>0 such that rn - m is non special and returns r and n.
Cond: DivFunElt Default:
AS: RngWittElt Default:
Extra: RngIntElt Default: 5
Given a global function field, try to compute its norm group. The norm group is defined to be the group generated by norms of unramified divisors. This group can be related to a subgroup of some ray class group.Provided F is abelian, this function will compute a divisor m and a sub group U of the ray class group modulo m sutch that F is isomorphic to the ray class field thus defined.
This function uses a heuristic algorithm. It will terminate after the size of the quotient by the norm group is less or equal than the degree for Extra many places.
If Cond is given, it must be an effective divisor that will be used as the potential conductor of F. Note: if Cond is too small, ie. a proper divisor of the true conductor, the result of this function will be wrong. However, if the conductor is not passed in, the discriminant divisor is used as a starting point. As this is ingeneral far too large, the function will be much quicker if a better (smaller) starting point is passed in.
If AS is given, it must be a Witt vector e of appropriate length and F should be the corresponding function field. This allows a much better initial guess for the conductor than using the discriminant.
In several situations one needs to loop over the places of a function field until either the one finds a place with special properties or until they generate a certain group. The functions listed here support this.
Coprime: Any Default:
All: BoolElt Default: false
Initialises an enumeration process for places of K. The enumeration process will loop over all irreducible polynomials of the underlying finite field and for each polynomial over all primes lying above it.If Coprime is given, it should be either a set of places that should be ignored in the process or a divisor. In case a divisor is passed in only places coprime to the divisor will be returned.
If All is false, the infinite places won't be considered.
Coprime: Any Default:
Constructs an enumeration process for places starting at the place P.If Coprime is given, it should be either a set of places that should be ignored in the process or a divisor. In case a divisor is passed in only places coprime to the divisor will be returned.
Coprime: Any Default:
Constructs an enumeration environment that starts at the place indexed by Pos as returned from PlaceEnumPosition.
Copies the environment and the current state.
Returnes a list of integers that acts as an index to the places as enumerated by the environment.
Returns the "next" place of the process.
Returns the current place pointed to by the environment, i.e. the last place returned by PlaceEnumNext.[Next][Prev] [Right] [Left] [Up] [Index] [Root]