Finding Galois groups (of normal closures) of algebraic fields is a hard problem, in general. All practical algorithms use 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 [GK00] and yields proven results for polynomials up to degree 23. In contrast to the absolute resolvent method, it also provides the explicit action on the roots of the polynomial f which generates the algebraic 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 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 Q which we get by adjoining a root of f to Q. Using this knowledge of the subfields, the Galois group is found as a subgroup of the intersection of suitable wreath products which may be easily computed. This intersection is a good starting point for the algorithm.
For primitive groups we use a combination of the method of Stauduhar and the absolute resolvent method. The Frobenius automorphism of the underlying p-adic field or the complex conjugation, when using complex approximations of the roots of the polynomial f, already determines a subgroup of the Galois group, which is used to speed up computations in the primitive case.
Al: MonStgElt Default: "pAdic"
Prime: Any Default:
Precision: RngIntElt Default: 100
Conditional: BoolElt Default: false
SetVerbose("GaloisGroup", n): Maximum: 5
Given an algebraic field F defined by an irreducible polynomial f of degree n over the rationals or a simple extension L of Q, this function returns a permutation group that forms the Galois group of the normal closure of F in some algebraic closure of Q or L. The permutation group acts on the points 1, 2, ..., n. The roots of f are calculated in the process and returned as elements of the residue field as the second argument. The prime number resp. prime ideal in the relative case, which is used for the p-adic computations is returned as a third argument. Currently this function is restricted to fields, orders and polynomials of degree n le23. In the relative case it is advisable to work with maximal orders as coefficient orders, since this will speed up computations.
The default version employs p-adic computation and returns proven results. The prime number resp. prime ideal p is determined during a Galois group computation in such a way that f is squarefree modulo p and the degree of the splitting field of f over Q_p is minimal. In the relative case the prime ideal is chosen that the prime number lying under the prime ideal does not divide the discriminant of the absolute extension.
The optional prime number, respectively prime ideal, Prime := p gives the prime to be used for the p-adic computations. In the relative case only unramified degree one prime ideals of the coefficient ring are allowed. If the prime does not satisfy certain criteria (also s.o.) computations cannot be fulfilled for these primes.
The use of the option Conditional := true speeds up p-adic computation considerably and may only be used with the p-adic version. Heuristic bounds are used during the inclusion test of a Galois group computation and therefore the result is conditional.
If Al := "Real" the algorithm will use complex approximations of the roots of the polynomial f and a standard precision of 100 digits. In this case the result is not guaranteed to be correct. This parameter works only for absolute extensions.
The optional integer Precision := prec sets the precision to be used and is only possible in combination with the option Al := "Real".
> Z:= Integers();
> P<x>:= PolynomialRing(Z);
> f:= x^20 - x^19 - 40*x^18 + 39*x^17 + 620*x^16 - 566*x^15 - 4766*x^14 +
> 3885*x^13 + 19304*x^12 - 13064*x^11 - 40385*x^10 + 19927*x^9 + 39899*x^8 -
> 11658*x^7- 14656*x^6 + 3092*x^5 + 2111*x^4 - 346*x^3 - 108*x^2 + 12*x + 1;
> G, R:= GaloisGroup(f);
> G;
Permutation group acting on a set of cardinality 20
(1, 4, 6, 8, 9, 12, 13, 16, 18, 20, 2, 3, 5, 7, 10, 11, 14, 15, 17, 19)
(1, 12, 2, 11)(3, 14, 4, 13)(5, 15, 6, 16)(7, 17, 8, 18)(9, 20, 10, 19)
> R;
[ (16*w + 21)*w + w + 22, (7*w + 2)*w + w + 22, (21*w + 4)*w + 10*w + 10,
(2*w + 19)*w + 10*w + 10, (10*w + 16)*w + 15*w + 8, (13*w + 7)*w + 15*w + 8,
(19*w + 8)*w + 3*w + 3, (4*w + 15)*w + 3*w + 3, (17*w + 18)*w + 14*w + 9,
(6*w + 5)*w + 14*w + 9, (14*w + 18)*w + 22*w + 22, (9*w + 5)*w + 22*w + 22,
(22*w + 3)*w + 13*w + 10, (w + 20)*w + 13*w + 10, (20*w + 6)*w + 8*w + 8,
(3*w + 17)*w + 8*w + 8, (2*w + 17)*w + 20*w + 3, (21*w + 6)*w + 20*w + 3,
(12*w + 22)*w + 9*w + 9, (11*w + 1)*w + 9*w + 9 ]
> t1, t2:= TransitiveGroupIdentification(G);
> t1;
1
> t2;
20
Some examples for the relative case
> P<x>:= PolynomialRing(Rationals());
> f:= x^16 - 4*x^12 + 8*x^8 - 4*x^4 + 1;
> M := MaximalOrder(x^4-7);
> Q<y>:=PolynomialRing(FieldOfFractions(M));
> f:=PolynomialRing(M)!Evaluate(f, y+M![0,0,0,1]);
> o:= EquationOrder(f);
> o:Maximal;
F[1]
/
/
E1[1]
/
/
Q
F [ 1] x^16 + [0,0,0,16]*x^15 + [0,0,840,0]*x^14 + [0,27440,0,0]*x^13 +
[624256,0,0,0]*x^12 + [0,0,0,1498176]*x^11 + [0,0,19225360,0]*x^10 +
[0,192228960,0,0]*x^9 + [1513463498,0,0,0]*x^8 + [0,0,0,1344818000]*x^7 +
[0,0,6586059816,0]*x^6 + [0,25127428144,0,0]*x^5 + [73210811796,0,0,0]*x^4 +
[0,0,0,22494642448]*x^3 + [0,0,33680152184,0]*x^2 + [0,31361592304,0,0]*x +
[13680812594,0,0,0]
E 1[ 1] x^4 - 7
Index : <[1, 0, 0, 0]>
> lp := Decomposition(M, 19);
> i := Position([Degree(x[1]) : x in lp], 1);
> prime:=lp[i][1];
> prime;
Prime Ideal of M
Two element generators:
[19, 0, 0, 0]
[7, 1, 0, 0]
> G, r, p:= GaloisGroup(o: Prime:= prime);
> t1, t2:= TransitiveGroupIdentification(G);
> t1;
42
> t2;
16
And a second one.
> f:= x^10 + 26*x^9 + 196*x^8 + 112*x^7 - 2416*x^6 + 10336/11*x^5 +
> 45824/11*x^4 +85760/11*x^3 - 339200/11*x^2 + 317440/11*x - 97280/11;
> g:= x^2-3/2;
> K:= NumberField([f, g]);
> G, r, p:= GaloisGroup(K: Conditional:= true);
> G;
Permutation group G acting on a set of cardinality 10
(1, 3, 5, 7, 9)(2, 4, 6, 8, 10)
(1, 2, 9, 8)(3, 6, 7, 4)(5, 10)