Finding Galois groups (of normal closures) of polynomials over rational function fields over k∈{Q, Fq}, where Fq denotes the finite field of characteristic p with q=pr, r∈Z> 0 is a hard problem, in general. All practical algorithms used the classification of transitive groups, which is known up to degree 31 [CHM98]. These algorithms fall into two groups: The absolute resolvent method [SM85] and the method of Stauduhar [Sta73].
The Magma implementation is based on an extension of the method of Stauduhar by Klüners, Geißler [Gei03], [GK00] and, more recently, Fieker [FK12] and Sutherland [Sut]. There is no longer any limit on the degree of the polynomials or fields as this algorithm does not use the classification of transitive groups. In contrast to the absolute resolvent method, it also provides the explicit action on the roots of the polynomial f which generates the function field. The algorithm strongly depends on the fact that the corresponding problem is implemented for the residue class field.
Roughly speaking, the method of Stauduhar traverses the subgroup lattice of transitive permutation groups of degree n from the symmetric group to the actual Galois group. This is done by using so-called relative resolvents. Resolvents are polynomials whose splitting fields are subfields of the splitting field of the given polynomial which are computed using approximations of the roots of the polynomial f.
If the field (or the field defined by a polynomial) has subfields (i.e. the Galois group is imprimitive) the current implementation changes the starting point of the algorithm in the subgroup lattice, to get as close as possible to the actual Galois group. This is done via computation of subfields of a stem field of f, that is the field extension of k(t) which we get by adjoining a root of f to k(t). The Galois group is found as a subgroup of the intersection of suitable wreath products (using the knowledge of the subfields) which may be easily computed.
If the field (or the field defined by a polynomial) does not have subfields (i.e. the Galois group is primitive) we use a combination of the method of Stauduhar and the absolute resolvent method. The Frobenius automorphism of the underlying field already determines a subgroup of the Galois group, which is used to speed up computations in the primitive case.
The algorithms used here are similar to those use for number fields. See also Chapter GALOIS THEORY OF NUMBER FIELDS. In addition to the intrinsics described here, some of the intrinsics described in Section Galois Groups apply to polynomials over function fields also.
Prime: RngElt Default:
NextPrime: UserProgram Default:
ProofEffort: RngIntElt Default: 10
Ring: GaloisData Default:
ShortOK: BoolElt Default: false
Old: BoolElt Default: false
SetVerbose("GaloisGroup", n): Maximum: 5
Given a separable, (irreducible if k is Q) polynomial f(t, x) of degree n over the rational function field k(t), k∈{Q, Fq}, or an extension K thereof (if k = Fq) this function returns a permutation group that forms the Galois group of a splitting field for f in some algebraic closure of K. The permutation group acts on the points 1, 2, ..., n. The roots of f are calculated in the process, expressed as power series and returned as the second argument: For a prime polynomial p(t)∈k(t) denote by bar(N) the splitting field of the polynomial f(t, x) mod p(t). It is well known that the roots of the polynomial f(t, x) can be expressed as power series in bar(N)[[t]]. We embed bar(N) in an unramified p-adic extension. The third return value is a structure containing information about the computation that can be used to compute the roots of f to arbitrary precision. This can be used for example in GaloisSubgroup to compute arbitrary subfields of the splitting field.The required precision increases linearly with the index of the subgroups, which are passed traversing the subgroup lattice. Therefore computations may slow down considerably for higher degrees and large indices.
The default version employs series computations over either unramified p-adic fields (k=Q) or finite fields (k=Fq). The prime polynomial is determined during a Galois group computation in such a way that f is squarefree modulo p.
The prime to use for splitting field computations can be given via the parameter Prime. The method of choosing primes for splitting field computations can be given by the parameter NextPrime. An indication of how much effort the computation should make to prove the results can be provided by altering the parameter ProofEffort, it should be increased if more effort should be made.
If Old is set to true, then the old version is called if available. Since the return values of the new version differ substantially from the old one, this may be used in old applications.
Prime: RngElt Default:
NextPrime: UserProgram Default:
ProofEffort: RngIntElt Default: 10
Ring: GaloisData Default:
ShortOK: BoolElt Default: false
Given a function field F defined as an extension of either a rational function field or a global algebraic function field by one polynomial compute the Galois group of a normal closure of F.The prime to use for splitting field computations can be given via the parameter Prime. The method of choosing primes for splitting field computations can be given by the parameter NextPrime. An indication of how much effort the computation should make to prove the results can be provided by altering the parameter ProofEffort, it should be increased if more effort should be made.
> k<t>:= FunctionField(Rationals()); > R<x>:= PolynomialRing(k); > f:= x^15 + (-1875*t^2 - 125)*x^3 + (4500*t^2 + 300)*x^2 + > (-3600*t^2 - 240)*x + 960*t^2+ 64; > G, r, S:= GaloisGroup(f); > TransitiveGroupDescription(G); 1/2[S(5)^3]S(3) > A := Universe(r); > AssignNames(~A, ["t"]); > A; Power series ring in t over Unramified extension defined by the polynomial (1 + O(191^20))*x^4 + O(191^20)*x^3 + (7 + O(191^20))*x^2 + (100 + O(191^20))*x + 19 + O(191^20) over Unramified extension defined by the polynomial (1 + O(191^20))*x + 190 + O(191^20) over pAdicField(191) > r[1]; > r[1]; -54*$.1^3 + 68*$.1^2 + 31*$.1 - 12 + O(191) + (-15*$.1^3 - 66*$.1^2 - 2*$.1 - 39 + O(191))*t + O(t^2) > S; GaloisData of type p-Adic (FldFun over Q) > TransitiveGroupIdentification(G); 99 15
> k<x>:= FunctionField(GF(1009)); > R<y>:= PolynomialRing(k); > f:= y^10 + (989*x^4 + 20*x^3 + 989*x^2 + 20*x + 989)*y^8 + (70*x^8 + > 869*x^7 + 310*x^6 + 529*x^5 + 600*x^4 + 479*x^3 + 460*x^2 + 719*x + > 120)*y^6 + (909*x^12 + 300*x^11 + 409*x^10 + 1000*x^9 + 393*x^8 + > 657*x^7 + 895*x^6 + 764*x^5 + 420*x^4 + 973*x^3 + 177*x^2 + 166*x + > 784)*y^4 + (65*x^16 + 749*x^15 + 350*x^14 + 909*x^13 + 484*x^12 + > 452*x^11 + 115*x^10 + 923*x^9 + 541*x^8 + 272*x^7 + 637*x^6 + 314*x^5 + > 724*x^4 + 490*x^3 + 948*x^2 + 99*x + 90)*y^2 + 993*x^20 + 80*x^19 + > 969*x^18 + 569*x^17 + 895*x^16 + 101*x^15 + 742*x^14 + 587*x^13 + > 55*x^12+ 437*x^11 + 97*x^10 + 976*x^9 + 62*x^8 + 171*x^7 + 930*x^6 + > 604*x^5 + 698*x^4 + 60*x^3 + 60*x^2 + 1004*x + 1008; > G, r, p:= GaloisGroup(f); > t1, t2:= TransitiveGroupIdentification(G); > t1; 1 > t2; 10And a second one.
> k<t>:= FunctionField(GF(7)); > R<x>:= PolynomialRing(k); > f:= x^12 + x^10 + x^8 + (6*t^2 + 3)*x^6 + (4*t^4 + 6*t^2 + 1)*x^4 + > (5*t^4 + t^2)*x^2 + 2*t^4; > G, r, p:= GaloisGroup(f); > G; Permutation group G acting on a set of cardinality 12 (2, 8)(3, 9)(4, 10)(5, 11) (1, 5, 9)(2, 6, 10)(3, 7, 11)(4, 8, 12) (1, 12)(2, 3)(4, 5)(6, 7)(8, 9)(10, 11) > A := Universe(r); > AssignNames(~A, ["t"]); > r; [ w^950*t^13 + w^1350*t^12 + w^1900*t^11 + w^500*t^10 + w^2050*t^9 + 2*t^8 + w^1350*t^7 + w^300*t^6 + w^350*t^5 + w^1450*t^4 + w^950*t^3 + w^1000*t^2 + w^1100*t + w^550, w^1175*t^13 + w^1825*t^12 + w^1675*t^11 + w^725*t^10 + w^1025*t^9 + w^1825*t^8 + w^1325*t^7 + w^775*t^6 + w^1775*t^5 + w^1325*t^4 + w^1575*t^3 + w^1175*t^2 + w^2225*t + w^2275, w^25*t^13 + w^1075*t^12 + w^425*t^11 + w^925*t^10 + w^225*t^9 + w^2375*t^8 + w^2125*t^7 + w^625*t^6 + w^1175*t^5 + w^425*t^4 + w^575*t^3 + w^825*t^2 + w^1175*t + w^2375, w^175*t^13 + w^1525*t^12 + w^575*t^11 + w^475*t^10 + w^1575*t^9 + w^1025*t^8 + w^475*t^7 + w^775*t^6 + w^1025*t^5 + w^1775*t^4 + w^1625*t^3 + w^2175*t^2 + w^1025*t + w^1025, w^1025*t^13 + w^1975*t^12 + w^2125*t^11 + w^1475*t^10 + w^2375*t^9 + w^1975*t^8 + w^2075*t^7 + w^1825*t^6 + w^425*t^5 + w^875*t^4 + w^1425*t^3 + w^2225*t^2 + w^1175*t + w^325, w^650*t^13 + w^2250*t^12 + w^100*t^11 + w^1100*t^10 + w^1150*t^9 + 2*t^8 + w^1050*t^7 + w^2100*t^6 + w^1250*t^5 + w^550*t^4 + w^650*t^3 + w^2200*t^2 + w^1700*t + w^1450, w^2150*t^13 + w^150*t^12 + w^700*t^11 + w^1700*t^10 + w^850*t^9 + 5*t^8 + w^150*t^7 + w^1500*t^6 + w^1550*t^5 + w^250*t^4 + w^2150*t^3 + w^2200*t^2 + w^2300*t + w^1750, w^2375*t^13 + w^625*t^12 + w^475*t^11 + w^1925*t^10 + w^2225*t^9 + w^625*t^8 + w^125*t^7 + w^1975*t^6 + w^575*t^5 + w^125*t^4 + w^375*t^3 + w^2375*t^2 + w^1025*t + w^1075, w^1225*t^13 + w^2275*t^12 + w^1625*t^11 + w^2125*t^10 + w^1425*t^9 + w^1175*t^8 + w^925*t^7 + w^1825*t^6 + w^2375*t^5 + w^1625*t^4 + w^1775*t^3 + w^2025*t^2 + w^2375*t + w^1175, w^1375*t^13 + w^325*t^12 + w^1775*t^11 + w^1675*t^10 + w^375*t^9 + w^2225*t^8 + w^1675*t^7 + w^1975*t^6 + w^2225*t^5 + w^575*t^4 + w^425*t^3 + w^975*t^2 + w^2225*t + w^2225, w^2225*t^13 + w^775*t^12 + w^925*t^11 + w^275*t^10 + w^1175*t^9 + w^775*t^8 + w^875*t^7 + w^625*t^6 + w^1625*t^5 + w^2075*t^4 + w^225*t^3 + w^1025*t^2 + w^2375*t + w^1525, w^1850*t^13 + w^1050*t^12 + w^1300*t^11 + w^2300*t^10 + w^2350*t^9 + 5*t^8 + w^2250*t^7 + w^900*t^6 + w^50*t^5 + w^1750*t^4 + w^1850*t^3 + w^1000*t^2 + w^500*t + w^250 ] > p; t^2 + 4