Finding Galois groups (of normal closures) of algebraic fields is a hard problem, in general. All practical currently-used 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 [GK00], [Gei03] and recent work by Klüners and Fieker [FK14], Elsenhans [Els12], [Els14], [Els16] and Sutherland [Sut15].
For polynomials over Z, Q, number fields and global function fields and irreducible polynomials over function fields over Q, Magma is able to compute the Galois group without any a-priori restrictions on the degree. Note, however, that the running time and memory constraints can make computations in degree >50 impossible, although computations in degree >200 have been successful as well. 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. On demand, the older version which is restricted to a maximum degree of 23, is still available.
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 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.
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 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.
Prime: RngElt Default:
ShortOK: BoolElt Default: false
Ring: GaloisData Default:
NextPrime: UserProgram Default:
SetVerbose("GaloisGroup", n): Maximum: 5
SetVerbose("Invariant", n): Maximum: 3
Given a polynomial f over the integers, rationals, a number field or an order thereof, compute the Galois group of a splitting field for f, ie. determine the subgroup of the permutations of the roots of f in a splitting field that correspond to field automorphisms. The method applied here is a variant of Stauduhar's algorithm, but with no dependency on the explicit classification of transitive groups and thus no a-priori degree limitation. It must be stated though that this function does not return proven results, if such results are necessary, one needs to call GaloisProof afterwards.Along with the Galois group of a splitting field for f, the roots of f, scaled to be algebraic integers, in a local splitting field and a GaloisData structure are returned.
The prime to use for splitting field computations can be given via the parameter Prime. The method of choosing of primes for splitting field computations can be given by the parameter NextPrime.
If a GaloisData structure has been computed for this polynomial it can be provided in Ring. If ShortOK is set to true then the results of a descent using short cosets [Els14] will be assumed to be as reliable as a descent which did not use short cosets.
Trials: RngIntElt Default: 50
AssumeIrreducibility: BoolElt Default: false
Given a rational polynomial f, attempt some cheap tests to determine if the Galois group is easily determinable as Sn or An. Returns 1 if Sn is proven, 2 is An is proven, and 0 otherwise.
Prime: RngElt Default:
ShortOK: BoolElt Default: false
Ring: GaloisData Default:
NextPrime: UserProgram Default:
Current: BoolElt Default: false
Subfields: BoolElt Default: true
Old: BoolElt Default: false
Type: MonStgElt Default: "p-Adic"
Prec: RngIntElt Default: 20
Time: BoolElt Default: true
SetVerbose("GaloisGroup", n): Maximum: 5
SetVerbose("Invariant", n): Maximum: 3
Given a number field K, compute the Galois group of a normal closure of K. The group is returned as an abstract permutation group acting on the roots of the defining polynomial of K in a suitable splitting field. The method applied here is a variant of Stauduhar's algorithm, but with no dependency on the explicit classification of transitive groups and thus no a-priori degree limitation. It must be stated though that this function does not return proven results, if such results are necessary, one needs to call GaloisProof afterwards.Along with the Galois group of a splitting field for K, the roots of the defining polynomial of K, scaled to be algebraic integers, in a local splitting field and a GaloisData structure are returned.
The prime to use for splitting field computations can be given via the parameter Prime. The method of choosing of primes for splitting field computations can be given by the parameter NextPrime.
If a GaloisData structure has been computed for the defining polynomial it can be provided in Ring. If Old is set to true the older version of [GK00], [Gei03] will be used for the computation.
If Subfields is set to false then the Subfields of K will not be used during the computation of the Galois group. If Current is set to true then the previously computed subfields of K only will be used in the Galois group computation and no more will be computed.
If Type is set to "Complex" then roots of f in the complex field will be used rather than roots of f in a p-adic completion. If Type is set to "Complex", the parameter Prec can be set to the minimum precision required in the roots of f.
If ShortOK is set to true then the results of a descent using short cosets [Els14] will be assumed to be as reliable as a descent which did not use short cosets. If Time is set to true then the time taken for lifting of roots will be stored in the attribute Time of the third return value.
Given the resulting GaloisData structure S of a (conditional) computation by GaloisGroup for either a polynomial f over the integers or an absolute number field K, try to find proofs for the conditional steps of the algorithm. The method employed here is to show that a suitable resolvent polynomial has a factor of a specific degree that can be used to differentiate between the possible groups.
Prec: RngIntElt Default: 20
Bound: RngIntElt Default: 0
Scaled: BoolElt Default: true
Given a polynomial f (optional) and the resulting GaloisData S of a computation of a Galois group, return the ith root of f in the ordering obtained from the Galois process or compute the ith conjugate of the primitive element used during the computation, to the given precision.The precision can be specified either directly by setting Prec to the desired p-adic precision or by giving a bound B in Bound. In the latter case the p-adic precision k will be calculated such that pk > B. If Scaled is set to false a root of f is returned. Otherwise the result is a scalar multiple of the root which is an algebraic integer.
SetVerbose("GaloisGroup", n): Maximum: 5
SetVerbose("Invariant", n): Maximum: 3
AlwaysTransform: BoolElt Default: false
Coset: SeqEnum Default:
PreCompInvar: UserProgram Default:
This function gives access to a single step of the Stauduhar method: Let G be a permutation group known to contain the Galois group of the object under investigation with the numbering of the "roots" determined by S. Furthermore, let B be a bound on the absolute value of the complex roots of the object and H be a (maximal) subgroup of G. Under these circumstances, the intrinsic will decide if there is some g∈G such that the Galois group is contained in Hg. The primary return value can be:In case of a non-zero result, the second return value will be the element g conjugating H, the third value will be true or false, depending on whether the p-adic bound used were proven or heuristic and the fourth value is the invariant used to separate the groups.
- 1
- if the Galois group is proven to be a subgroup of Hg up to precision problems, indicated by the 3rd value
- -1
- if there is a proof that the Galois group is contained in a proper subgroup of G and maybe in Hg
- -2
- if the Galois group may be in Hg, but we could not prove that it is in a proper subgroup of G
- 0
- the Galois group is not contained in a conjugate of H.
The optional parameter Coset can be used to pass a transversal of G/H in, while PreCompInvar should contain a suitable invariant separating G and H if set. If AlwaysTransform is set to true then a transformation will always be applied to the roots.
Given an element x in the splitting field determined by the GaloisData structure S and a bound B on the complex absolute value, determine if there exists an element y ∈Z or an extension of Z defined by the polynomial the Galois group is being computed for, such that y=x up the precision of x and such that |y|<B. In case such a y exists, it is returned as a second return value.
> Z:= Integers();
> P<x>:= PolynomialRing(Z);
> G, R, S := GaloisGroup(x^6-108);
> G;
Permutation group G acting on a set of cardinality 6
Order = 6 = 2 * 3
(1, 5, 3)(2, 6, 4)
(1, 2)(3, 6)(4, 5)
> R;
[ -58648*$.1 + 53139 + O(11^5), 58648*$.1 - 19478 +
O(11^5), -43755*$.1 - 72617 + O(11^5), 58648*$.1 -
53139 + O(11^5), -58648*$.1 + 19478 + O(11^5),
43755*$.1 + 72617 + O(11^5) ]
> S;
GaloisData over Z_11
> time G, _, S := GaloisGroup(x^32-x^16+2);
Time: 65.760
> #G;
2048
Some examples for the relative case
> load galpols;
> f := PolynomialWithGaloisGroup(9, 14);
> G := GaloisGroup(f);
> TransitiveGroupIdentification(G);
14 9
> M := MaximalOrder(f);
> kM := FieldOfFractions(M);
> f:= Factorisation(Polynomial(kM, f))[2][1];
> f;
$.1^8 + (-2/1*kM.1 + kM.2)*$.1^7 + (-60/1*kM.1 -
2/1*kM.2 + kM.3)*$.1^6 + (120/1*kM.1 - 60/1*kM.2 -
2/1*kM.3 + kM.4)*$.1^5 + (980/1*kM.1 + 120/1*kM.2 -
60/1*kM.3 - 2/1*kM.4 + kM.5)*$.1^4 + (-1808/1*kM.1
+ 980/1*kM.2 + 120/1*kM.3 - 60/1*kM.4 - 2/1*kM.5 +
kM.6)*$.1^3 + (-4012/1*kM.1 - 1808/1*kM.2 +
980/1*kM.3 + 120/1*kM.4 - 60/1*kM.5 - 2/1*kM.6 +
kM.7)*$.1^2 + (4936/1*kM.1 - 4013/1*kM.2 -
1809/1*kM.3 + 979/1*kM.4 + 118/1*kM.5 - 60/1*kM.6 -
4/1*kM.7 + 3/1*kM.8)*$.1 - 208769062021/1*kM.1 +
51146604497/1*kM.2 - 30878218588/1*kM.3 +
50063809507/1*kM.4 - 52067647419/1*kM.5 -
94281823910/1*kM.6 + 69906801827/1*kM.7 -
182364865509/1*kM.8 + 214706745867/1*kM.9
> g, r, p:= GaloisGroup(f);
> TransitiveGroupIdentification(g);
5 8
Since g is derived from a factor of the original f, the
Galois group should be isomorphic to a subgroup of G:
> Subgroups(G:OrderEqual := #g);
Conjugacy classes of subgroups
------------------------------
[1] Order 8 Length 9
Permutation group acting on a set of
cardinality 9
Order = 8 = 2^3
(2, 4, 5, 3)(6, 8, 7, 9)
(2, 7, 5, 6)(3, 9, 4, 8)
(2, 5)(3, 4)(6, 7)(8, 9)
> IsIsomorphic(g, $1[1]`subgroup);
true Homomorphism of GrpPerm: g, Degree 8, Order 2^3
into GrpPerm: $, Degree 9, Order 2^3 induced by
(1, 2, 3, 8)(4, 5, 6, 7) |--> (2, 4, 5, 3)(6, 8, 7, 9)
(1, 7, 3, 5)(2, 6, 8, 4) |--> (2, 7, 5, 6)(3, 9, 4, 8)
One of the most important tools in the computational Galois theory are invariants, that is multivariate polynomials that are invariant under some permutation group. While invariant theory in general is a rich and classical branch of mathematics, and is supported by a powerful magma module, Chapter INVARIANT THEORY, the more specific needs in the Galois theory are best met with a different set of functions. Invariants, in this chapter are multivariate polynomials in straight-line representation, the polynomials are represented as programs without branches. The category of these polynomials is of type RngSLPol and its elements are of type RngSLPolElt. A consequence of this representation is that certain operations are very fast, while others are impossible - or at least very difficult. For example, representing (a - b)1000(a + b)1000 - (a2 - b2)1000 is trivial, this is a short program with just a few steps:
Global: BoolElt Default: false
Creates the ring of multivariate straight-line polynomials over the ring R with n indeterminates. If Global is set to true then an existing straight-line polynomial ring will be returned if one has previously constructed.
Return the ith indeterminate of the SL-polynomial ring R.
The i-th elementary symmetric polynomial of the SL-polynomial ring R.
Return the coefficient ring of the SL-polynomial ring R.
Return the rank of the SL-polynomial ring R, ie the number of independent indeterminates over the coefficient ring.
For a SL-polynomial ring R, prepare "probabilistic" comparison of straight-line polynomials, using evaluation at n tuples drawn at random from the finite field F.In order to allow a probabilistic test for "equality" of SL-polynomials in places where a strict, deterministic test is not necessary, this allows comparison of SL-polynomials through their values at random evaluation points.
Return the finite field and the number of random samples used to compare polynomials of the SL-polynomial ring R. If SetEvaluationComparison has not been called, the 1st return value will be false while the second is undefined.
Store the point to evaluate straight line polynomials with parent R to contain the elements of the sequence S whose length is the rank of R and whose elements are coercible into R.
The ith partial derivative of the SL-polynomial x.
Return the evaluation of the straight-line polynomial f at the elements of the sequence S where S contains the rank of the parent of f many elements coercible into the coefficient ring of f and if not given as an argument to this intrinsic is the sequence which was last input to InitializeEvaluation. The map m from the coefficient ring of f into the universe of S can be specified if required.
At the core of the computation of Galois groups is the single Stauduhar step where, for a group G and a (maximal) subgroup U the programme decides if the Galois group is a subgroup of U - provided it was contained in G. This is achieved by evaluating a G-relative U-invariant polynomial f∈Z[x1, ..., xn] (or f ∈Fq[t][x1, ..., xn] when the characteristic of the coefficient ring of the input polynomial is prime). In this subsection several functions are collected that allow a user to access magma's internally used invariants. In what follows, an invariant is always a multivariate polynomial f in n indeterminates where n is the degree of G i.e. G<Sn. Invariants are represented as straight-line polynomials that allow the very compact representation and fast evaluation of polynomials.
DoCost: BoolElt Default: false
Worklevel: RngIntElt Default: -1
SetVerbose("GaloisGroup", n): Maximum: 3
For subgroups H<G of the symmetric group on n elements, where H is maximal in G and G is transitive, compute a G-relative H-invariant. This is done by carefully comparing certain group theoretical properties of the group pair in question to find invariant polynomials of special types that are easy to evaluate. If this fails, generic invariants will be used.If DoCost is true, two values are returned: the first return value in this case is an estimate for the number of multiplications necessary to evaluate the invariant, while the second value is a function that can be evaluated without arguments to compute the invariant. This is done to allow to compare invariants by their computational complexity before actually committing and computing them explicitly as this can be very time consuming.
If Worklevel is set to an integer different from -1 only certain types of invariants are tested for suitability for this particular pair of groups. In this case a special return value of false indicates that Magma was unable to find an invariant at this level. Roughly speaking, the higher the Worklevel, the more time-consuming the invariant will be, both in terms of the time spend in finding as well as the time necessary to evaluate the invariant.
IsMaximal: BoolElt Default: false
Risk: BoolElt Default: false
SetVerbose("Invariant", n): Maximum: 3
For a pair of subgroups H<G of the symmetric group where H is not necessarily maximal in G, find a G-relative H-invariant polynomial. The computation splits into three phases:If IsMaximal is set to true, Magma will not compute a subgroup chain but instead assume that H is a maximal subgroup of G. Otherwise Magma will compute all minimal overgroups of H in G and call GaloisGroupInvariant for each of them. Finally, Magma will combine these invariants to a relative one.
- - First, a subgroup chain between H and G is computed such that each step in the chain is a maximal subgroup.
- - Second, for each pair Ui<Ui + 1 of maximal subgroups one fixed invariant is computed
- - Third, in the last step, the invariants are combined to produce a G-relative H-invariant.
The parameter Risk refers to an old version of the function and does not have an effect.
Given a subgroup G<Sn and three maximal subgroups H1, H2 and H3 of G two of which have already known invariants, try to derive an invariant for H3 from the known ones over the ring R (usually Z). The input for H1 and H2 consists of a tuple with two (or three) entries, the first specifying the actual subgroup, the second the G-relative Hi-invariant and the optional third a Tschirnhaus transformation that should be done before the invariant is evaluated.The typical situation in which this function is used is the case of H1 and H2 being index 2 subgroups of G. In this case elementary theory immediately guarantees a third subgroup H3 of index 2. For this function to work, the core of H1 ∩H2 must be contained in H3. This is only useful if the index of the core is not too large.
Sign: BoolElt Default: false
For a multivariate polynomial F in straight-line representation and a permutation p this function tests if Fp = F with a high probability. In particular, this function will evaluate F at random elements in some large finite field, then permute the evaluation points by p and evaluate again. If the values agree, the polynomial is most likely invariant under p, if they disagree than the polynomial is definitely not invariant. The probability of failure is related to the probability of guessing a zero of a multivariate polynomial at random.In order to get a proof for the invariants, one can convert F into a standard multivariate polynomial and check directly that this is invariant. However, for the invariants typically constructed in the Galois package, the conversion into a multivariate polynomial will not be possible due to the large degree of the polynomial and the resulting large number of terms.
If Sign is set to true, the function checks instead for Fp = - F.
Given a multivariate polynomial I in straight-line representation and an integer B, compute an integer M such that |I(x1, ..., xn)|≤M for all complex numbers |xi|≤B. This returns a bound for the size of an evaluation of I.
Given a multivariate polynomial I in straight-line representation and B, a power series over the integers, compute a power series M such that for all choices of power series xi such that the coefficients of xi are bounded in absolute value by those of B we have that the power series I(x1, ..., xn) has coefficients bounded by those of M.
Prints the straight-line polynomial I into a string. The printing shows the way the polynomial is stored internally. E.g. the reuse of subexpressions gets visible.
The result of a Galois group computation contains, in addition to the Galois group as an abstract group, the explicit action of the group on the roots of the underlying polynomial in some splitting field. This explicit action, together with the availability of invariants for group pairs, can be used to compute arbitrary subfields of the splitting field.
SetVerbose("Invariant", n): Maximum: 2
Given either a polynomial f or number field K or a successful computation of a Galois group in S and a subgroup U<G where G is the Galois group, find a defining polynomial for the subfield of the splitting field that is fixed by U and return also a G-relative U-invariant.
SetVerbose("Invariant", n): Maximum: 2
Given either a polynomial f or number field K or a successful computation of a Galois group in S and a permutation group Q, find all subfields of the splitting field that have a Galois group isomorphic to Q. The defining polynomials of these subfields are returned. This is done by finding all subgroups U of the Galois group G such that the permutation action of G on the cosets G/U is isomorphic to Q.
Risk: BoolElt Default: false
MinBound: RngIntElt Default: 1
MaxBound: RngIntElt Default: ∞
Inv: [RngSLPolElt] Default: false
SetVerbose("GaloisTower", n): Maximum: 2
For data computed as the third return value of GaloisGroup and a subgroup chain U1 > U2 > ... > Us, compute the corresponding tower of fixed fields Ki that is fixed by the operation of Ui on the roots of f as ordered in S.Currently, this function only works for polynomials defined over Q, Fq[t] or absolute extensions of Q.
The first return value is the largest number field in the tower, that is the field fixed by the smallest group in the chain as an extension of the fixed field of the second group which is an extension of the fixed field of the third group etc. The second return value is a sequence of tuples each containing the data used to generate one step:
The third and fourth return values can be used to algebraically identify arbitrary elements of the splitting field that are defined by multivariate polynomials. The third is a function that takes a vector of p-adic conjugates and returns an algebraic representation of the element, the fourth takes an invariant and computes precision bounds for the precision necessary so that the algebraic recognition will work.
- - The first item is the invariant used in this step. This corresponds directly to the choice of the primitive element.
- - The second item is the Tschirnhaus transformation on this level
- - The third item is a transversal of Ui over Ui + 1, the fixed ordering of which gives the ordering of the "relative conjugates"
If Risk is set to true, then for non-maximal subgroup pairs Ui> Ui + 1 the "risky" version of RelativeInvariant is used.
The parameter MinBound can be used to specify a minimal p-adic precision that should be used internally. This can be used to avoid the calculation of an increase in precision which can be costly. On the other hand, to work in larger precision than necessary also incurs a time penalty.
The parameter MaxBound can be used to limit the p-adic precision used internally. Especially when the chain get longer, the internally used precision estimates become more and more pessimistic thus forcing higher and higher precision. In certain cases when it is possible to verify the correctness of the result independently, a smaller precision can speed the computation up considerably.
If the parameter Inv is given it should contain a sequence of invariants, the i-th entry need be an Ui relative Ui + 1 invariant. The invariants used correspond almost directly to the relative primitive elements computed at each step in the tower. This is useful in situation where either certain primitive elements are necessary or where certain invariants are known.
Galois: Tup<GrpPerm, [RngElt], GaloisData> Default:
Roots: BoolElt Default: true
AllAuto: BoolElt Default: false
Stab: BoolElt Default: true
Chain: [GrpPerm] Default: false
Inv: [RngSLPolElt] Default: false
Name: MonStgElt Default: false
For a polynomial f in Z[t], Q[t] or over an absolute number field or Fq[t], this function computes the splitting field of f as a tower of fields. The various parameter can be used to force certain subfield towers and/ or compute additional data. By default Stab is set to true, which means that the splitting field will be the tower corresponding to the chain of stabilizers of {1}, {1, 2}, ..., {1, ..., n}. Also by default Roots is set to true, which means that the roots of f are expressed as elements of the splitting field. If Roots is set to false, only the field is computed and returned.The third return value will be the Galois group, the optional fourth value the automorphisms.
If the parameter Galois is used, it should contain a list or triplet containing the output of GaloisGroup(f);.
If Chain is set to a sequence of subgroups, this chain is used to compute a subfield tower. In this case the first elements must be G, the full Galois group. If Chain is used, Inv can be used to provide the invariants as well.
If AllAuto is set to true, the full automorphism group of the splitting field is computed as a sequence of sequences giving the all the roots of the relative polynomials.
If Name is given, it should be set to a string. In this case the primitive element of the i-subfield in the tower will be called Name.i.
> P<x> := PolynomialRing(IntegerRing());
> f := x^3-2;
> GaloisSplittingField(f);
Number Field with defining polynomial $.1^2 +
$.1*$.1 + $.1^2 over its ground field
[
$.1,
$.1,
-$.1 - $.1
]
Symmetric group acting on a set of cardinality 3
Order = 6 = 2 * 3
(1, 2, 3)
(1, 2)
> K, R, G := $1;
> K:Maximal;
K
|
|
$1
|
|
Q
K : $.1^2 + $.1*$.1 + $.1^2
$1 : x^3 - 2
> [x^3 : x in R];
[
2,
2,
2
]
The fact that by default all generators are called $.1
makes this hard to read, so let us assign other names:
> GaloisSplittingField(f:Name := "K");
Number Field with defining polynomial K1^2 + K2*K1
+ K2^2 over its ground field
[
K2,
K1,
-K1 - K2
]
Symmetric group G acting on a set of cardinality 3
Order = 6 = 2 * 3
(1, 2, 3)
(1, 2)
> (K where K := $1):Maximal;
$1<K1>
|
|
$2<K2>
|
|
Q
$1 : K1^2 + K2*K1 + K2^2
$2 : x^3 - 2
So now we can easily see that the splitting field is a relative
quadratic extension of the degree 3 stem field. Now we try a different
subgroup chain:
> G, r, S := GaloisGroup(f);
> GaloisSplittingField(f:Galois := <G, r, S>,
> Chain := CompositionSeries(G), Name := "K", AllAuto);
Number Field with defining polynomial K1^3 - 2
over its ground field
[
K1,
1/6*K2*K1,
1/6*(-K2 - 6)*K1
]
Symmetric group G acting on a set of cardinality 3
Order = 6 = 2 * 3
(1, 2, 3)
(1, 2)
[
[
K2,
-K2 - 6
],
[
K1,
1/6*K2*K1,
1/6*(-K2 - 6)*K1
]
]
> (K where K := $1):Maximal;
$1<K1>
|
|
$2<K2>
|
|
Q
$1 : K1^3 - 2
$2 : x^2 + 6*x + 36
> f := x^10 - 20*x^8 + 149*x^6 - 519*x^4 + 851*x^2 - 529; > G, r, S := GaloisGroup(f);G,r,S; > TransitiveGroupIdentification(G); 8 10 > TransitiveGroupDescription(G); [2^4]5Thus the Galois group of f is isomorphic to ()10T8 of type [2^4]5 and order 80.
We first compute the splitting field directly:
> time _ := SplittingField(f);This takes a long time, mainly because of the type of the Galois group which will require a field tower involving 5 steps and factorisation of a polynomial in such a tower. Now, we try the same by using the Galois information:
> time K, R := GaloisSplittingField(f:Name := "K");
Time: 4.740
> K:Maximal;
K<K1>
|
|
$1<K2>
|
|
$2<K3>
|
|
$3<K4>
|
|
Q
K : K1^2 + 1/23*(-12*K4^8 + 217*K4^6 - 1374*K4^4
+ 3606*K4^2 - 3381)
$1 : K2^2 + 1/23*(18*K4^8 - 314*K4^6 + 1877*K4^4 -
4512*K4^2 + 3588)
$2 : K3^2 + 1/23*(-5*K4^8 + 77*K4^6 - 377*K4^4 +
663*K4^2 - 437)
$3 : x^10 - 20*x^8 + 149*x^6 - 519*x^4 + 851*x^2 -
529
> [ Evaluate(f, x) eq 0 : x in R];
[ true, true, true, true, true, true, true, true,
true, true ]
From the type of the Galois group, [2^4]5 we expect G to have
a normal subgroup A of type C24 such that the quotient G/A is
a cyclic group of order 5. To find that subfield we can for example
use the Galois computations again:
> A := NormalSubgroups(G:OrderEqual := 16)[1]`subgroup;
> GaloisSubgroup(S, A);
x^5 + 1682*x^4 + 715964*x^3 + 99797360*x^2 +
5206504944*x + 88019915488
(x5 + x10)
The second return value x5 + x10 also tells us that the primitive element
of the subfield is the sum of two roots of f, namly the 5-th and 10-th
in our fixed ordering.
Suppose we want to work in the degree 16 extension over this field, that is we want to work in the fixed field of the trivial subgroup over the field fixed by A:
> K, D, Reco, Bnd := GaloisSubfieldTower(S, [A, sub<G|>]); > GK := GaloisGroup(K); > #GK; 16 > AbelianInvariant(GK); [ 2, 2, 2, 2 ]As an abstract field, K as the splitting field can be described as a quotient of Q[x1, ..., x10]/I for some suitable ideal I also known as the Galois ideal. On the other hand, by tensoring with some p-adic complection Qp we get an embedding of K into Kp#G=:Γ. The sequence D that is returned as the 2nd value contains the information necessary to map elements in Z[x1, ..., x10] via Γ to K. Suppose we want to find x1, ie. a root of f in K. We first have to get the p-adic image in Γ, with appropriate precision. Step one is to define a suitable multivariate polynomial i that will represent x1.
The second step is to compute an integer B such that all complex conjugates if i are bounded by B in absolute value. For this we can use information about the size of the roots of f stored in S.
The next step now is to get a bound for the p-adic precision.
> R := SLPolynomialRing(Integers(), 10); > i := R.1; > B := S`max_comp; > bound := Bnd(B);Now, we need to get the p-adic conjugates of x1, ie. the image in Γ. The third entry in each of the elements of D contains coset representatives that give the relative conjugates:
> rt := [GaloisRoot(i, S:Bound := bound) : i in [1..10]]; > con := CartesianProduct(Reverse([x[3]: x in D])); > gamma := [Evaluate(i, PermuteSequence(rt, &*p)) : p in con]; > im := Reco(gamma: Bound := B); > time Evaluate(f, im) eq 0;Before we try to find an automorphism of the base field using this method we want to find the primitive element of the base field of K. The primitive element is essentially given by the 1st part of D. Note that here a Tschirnhaus-transformation was necessary.
> i := D[1][1]; t := D[1][2]; > B := Bound(i, Evaluate(t, S`max_comp)); > bound := Bnd(B); > rt := [GaloisRoot(i, S:Bound := bound) : i in [1..10]]; > rt := [Evaluate(t, x) : x in rt]; > gamma := [Evaluate(i, PermuteSequence(rt, &*p)) : p in con]; > im := Reco(gamma : Bound := B); > im; $.1 > im eq K.2; true;Now for the automorphism - all we have to change is to permute the roots as we already have the permutation group.
> rt := PermuteSequence(rt, Random(G)); > gamma := [Evaluate(i, PermuteSequence(rt, &*p)) : p in con]; > au := Reco(gamma : Bound := B); > au; 1/92*(-9*$.1^4 + 386*$.1^3 - 5854*$.1^2 + 37120*$.1 - 82288)In order to "find" arbitrary (integral) elements this way one has to
For a polynomial f∈Z[t] with solvable Galois group it is well known that the roots of f can be expressed as nested radicals. On the other hand no good algorithm is known to achieve this. Here we use the explicit action of the Galois group of f as a permutation group on the p-adic roots to compute such a representation.
Prime: RngIntElt Default: false
Name: MonStgElt Default: false
Galois: Tup<GrpPerm, [RngElt], GaloisData> Default:
UseZeta_p: BoolElt Default: false
MaxBound: RngIntElt Default: ∞
SetVerbose("GaloisTower", n): Maximum: 3
For a polynomial f∈Z[x], Fq[t][x] with solvable Galois group, a splitting field as a tower of radical extensions is computed together with algebraic representations of the roots of f as elements in the splitting field. The third return value contains the non-trivial roots of unity which are used.If the parameter Galois is used, it should contain a list or triplet containing the output of GaloisGroup(f);.
If Prime is used, and Galois is unspecified, the value of Prime is passed onto the Galois group computation and can therefore be used to choose the p-adic field.
If UseZeta_p is set to true, then the expression for the roots of p will contain pure radicals and roots of unity. By default, if UseZeta_p is false, radical expressions for the roots of unit necessary will also be computed.
If MaxBound is given, it will be used as an upper bound for the p-adic precision used internally. Especially when the radical tower contains many steps, the internally used precision estimates become more and more pessimistic, thus resulting in larger and larger precision.
If Name is set to some string, the i-th level primitive element in the tower will be called Name.i.
Let K/k be a number field with cyclic automorphism group of order n generated by K.1 to a and z be a n-th root of unity in k. This function will return a field L isomorphic to K such that L is a Kummer extension, ie. the defining polynomial for L will be of the form tn - b for some b in the coefficient field k of K. The second returned value contains the roots of f in L while the third return value contains the roots of unity used.
> P<x> := PolynomialRing(IntegerRing());
> f := x^6 - x^5 - 6*x^4 + 7*x^3 + 4*x^2 - 5*x + 1;
> K, R := SolveByRadicals(f:Name := "K.");
> K:Maximal;
K<K.1>
|
|
$1<K.2>
|
|
$2<K.3>
|
|
$3<K.4>
|
|
Q
K : K.1^3 + 1/2*(3*K.4 - 11)*K.2 + 1/2*(-27*K.4 + 23)
$1 : K.2^2 - 5
$2 : K.3^3 - 228*K.4 + 532
$3 : K.4^2 + 3
> [ Evaluate(f, x) eq 0 : x in R];
[ true, true, true, true, true, true ]
Note that every step in the tower defining K is radical, ie. given
by an equation of type xn - a.
An important question for various problems is that of finding all linear (additive) relations between the roots of some integral polynomial. While there is a obvious algorithm if the splitting field can be constructed explicitly, there is no obvious way of doing it in general. In this section we provide two algorithms to find those and more general relations and a third that can verify arbitrary relations.
Proof: BoolElt Default: true
Galois: Tup<GrpPerm, [RngElt], GaloisData> Default:
UseAction: BoolElt Default: false
UseLLL: BoolElt Default: true
Power: RngIntElt Default: 1
kMax: RngIntElt Default: ∞
LogLambdaMax: RngIntElt Default: ∞
Given an integral monic polynomial f, this function finds a basis for the module of additive relations between the roots of f in some algebraic closure. The ordering of the roots is the same as chosen by the computation of the Galois group of f, in fact, the roots used are precisely the ones returned by GaloisRoot. The output consists of a basis for the relation module encoded in a matrix and the Galois data encoding the ordering of the roots. The algorithm is described in [dGF07].If Power is set to an integer larger than one, the module of relations between the powers of the roots is computed.
Proof: BoolElt Default: true
Galois: Tup<GrpPerm, [RngElt], GaloisData> Default:
UseAction: BoolElt Default: false
UseLLL: BoolElt Default: true
Power: RngIntElt Default: 1
kMax: RngIntElt Default: ∞
LogLambdaMax: RngIntElt Default: ∞
Let f be an integral monic polynomial and α1, ..., αn be the roots of f in some splitting field in a fixed ordering. The field and the ordering used here are the ones chosen by the computation of the Galois group of f. The splitting field K of f be represented as a quotient Q[x1, ..., xn]/J for some suitable ideal J, thus elements in K can be represented as multivariate polynomials in the roots αi. The sequence I that is passed into this function is interpreted to contain elements in K given via the polynomials in I. This function computes a basis for the module of relations between the elements represented by I. The algorithm is described in [dGF07].
Galois: Tup<GrpPerm, [RngElt], GaloisData> Default:
kMax: RngIntElt Default: ∞
Let f be an integral monic polynomial and α1, ..., αn be the roots of f in some splitting field in a fixed ordering. The field and the ordering used here are the ones chosen by the computation of the Galois group of f. The splitting field K of f be represented as a quotient Q[x1, ..., xn]/J for some suitable ideal J, thus elements in K can be represented as multivariate polynomials in the roots αi. For a polynomial F in the roots of f, this function verifies if F evaluated at the roots of f equals zero, ie. if F describes a relation between the roots. The algorithm is described in [dGF07].
> ST := ShephardTodd(8);
> R := InvariantRing(ST);
> p := PrimaryInvariants(R);
> p;
[
x1^8 + (-4*i - 4)*x1^7*x2 + 14*i*x1^6*x2^2 + (-14*i +
14)*x1^5*x2^3 - 21*x1^4*x2^4 + (14*i + 14)*x1^3*x2^5
- 14*i*x1^2*x2^6 + (4*i - 4)*x1*x2^7 + x2^8,
x1^12 + (-6*i - 6)*x1^11*x2 + 33*i*x1^10*x2^2 + (-55*i +
55)*x1^9*x2^3 - 231/2*x1^8*x2^4 + (66*i +
66)*x1^7*x2^5 + (-66*i + 66)*x1^5*x2^7 -
231/2*x1^4*x2^8 + (55*i + 55)*x1^3*x2^9 -
33*i*x1^2*x2^10 + (6*i - 6)*x1*x2^11 + x2^12
]
> res := Resultant(p[1]-2, p[2]-3, 2);
> f4 := Polynomial(Rationals(), UnivariatePolynomial(res));
> bool, f := IsPower(f4, 4);
> bool, f;
true
27/4*x^24 - 135*x^16 + 405*x^12 - 405*x^8 + 162*x^4 - 1
> G, R, S := GaloisGroup(f);
> #G;
192
> rel := LinearRelations(f : Galois := <G, R, S>);
> #rel;
20
There are 20 linear relations between the 24 roots, that is, they span
a vector space of dimension 4 over Q.
We demonstrate how to check one of the relations.
> v := rel[3]; > v; [ 0, 0, 0, -1, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] > IR := SLPolynomialRing(Integers(), 24); > r := &+ [v[i]*IR.i : i in [1..24]]; > r; (x7 + ((-1 * x4) + (-1 * x6))) > VerifyRelation(f, r : Galois := <G, R, S>); trueNext we give a primitive element in the splitting field (of degree 192 over Q) such that the Q-vector space spanned by all 192 conjugates has dimension 4. The element is defined as a linear combination of the 24 roots (most random choices work). We show that the element is primitive by checking that the 192 p-adic conjugates are distinct.
> I := &+ [ (e[n]-1)*IR.n : n in [1..24]] where e is Eltseq(Random(Sym(24)));
> Iorbit := [Apply(g, I) : g in G];
> #{Evaluate(i, R) : i in Iorbit};
192
Thus the 192 conjugates are distinct, and by construction they lie in the
linear span of the alphai, which has dimension 4 over Q as shown.
It is possible to check this directly (i.e. p-adically, using the Galois data).
> time #LinearRelations(f, Iorbit : Galois := <G, R, S>, Proof := false); 188 Time: 645.450One expects most primitive elements of the field not to share this property. We define one by choosing a polynomial I = x1 + xn2 that has trivial stabilizer in G.
> exists(n){n : n in [1..24] | #Orbit(G, [1,n]) eq 192}; n;
true
2
> I := IR.1 + IR.n^2;
> Iorbit := [Apply(g, I) : g in G];
> #{Evaluate(i, R) : i in Iorbit};
192
> time #LinearRelations(f, Iorbit : Galois := <G, R, S>, Proof := false);
182
Time: 816.120
For elements in a sequence I, compute the sequence containing the power sums ∑Iij for j=1, ..., # I. If I is interpreted to contain the Galois conjugates of some algebraic number (or the roots of some polynomial) then this computed the power sums.
Given a sequence I of elements, interpreted as power sums of some algebraic number x, use Newton's relations to compute the elementary symmetric functions in the conjugates of x. In general for this to succeed, the characteristic of the underlying ring needs to be larger than the length of the sequence.