|
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
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 [GK00], [Gei03] and recent work by Klüners and Fieker.
For square-free polynomials over Z and irreducible polynomials
over number fields and 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.
For function fields over finite fields, and 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 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.
Subsections
GaloisGroup(L) : FldAlg[FldAlg] -> GrpPerm, [ FldPrElt ], Any
GaloisGroup(O) : RngOrd -> GrpPerm, [ FldPrElt ], Any
GaloisGroup(f) : RngUPolElt[FldAlg] -> GrpPerm, [ FldPrElt ], Any
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<24 over 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 Qp 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 and polynomials of
degree up to 23.
The optional integer Precision := prec sets the precision to be used
and is only possible in combination with the option Al := "Real".
Old: BoolElt Default: false
SetVerbose("GaloisGroup", n): Maximum: 5
SetVerbose("Invariant", n): Maximum: 3
Given a square-free polynomial f over the integers, 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.
If the optional parameter Old is set, then the old method, which
is the only available method for relative computations, is called instead.
Old: BoolElt Default: false
SetVerbose("GaloisGroup", n): Maximum: 5
SetVerbose("Invariant", n): Maximum: 3
Given a number field k over Q, 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.
GaloisProof(f, S) : RngUPolElt, GaloisData -> BoolElt
GaloisProof(K, S) : FldAlg, GaloisData -> BoolElt
Given the result of a (conditional) computation by GaloisGroup
for either an irreducible polynomial over the integers or
an absolute number field, try to find proves for the conditional
steps of the algorithm. The method employed here is to show that
a suitable absolute resolvent polynomials 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
Given a polynomial f and the result S of a computation
of it's Galois group, return the ith root in the ordering
obtained form the Galois process 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.
GaloisRoot(i, S) : RngIntElt, GaloisData -> RngElt
Given the result S of a computation of a Galois group and an
integer i, compute the ith conjugate of the primitive element
used during the computation.
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.
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 this 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:
- 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 prove that the Galois group is contained in
a proper subgroup of G and maybe in Hg
- -2
- if the Galois group maybe 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.
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 forth value is the invariant used to separate the
groups.
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 is set.
Given an element x in the splitting field determined by S
and a bound B on the complex absolute value, determine if there
exists an integer y 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.
A Galois group computation is shown below.
> 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, Introduction, 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 this 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:
- 1
- subtract b from a
- 2
- raise to the 1000th power
- 3
- add a and b
- 4
- raise to the 1000th power
- 5
- multiply the results of steps 2 and 4
- 6
- subtract b2 from a2 and raise to the 1000th power
- 7
- subtract the result of step 7 from 5
Now, while it is trivial to evaluate this polynomial at for example
any pair of elements in any finite ring, it is very difficult to see that
in fact, the polynomial is identical to zero - when expanded as a polynomial.
x * y : RngSLPolElt, RngSLPolElt -> RngSLPolElt
x + y : RngSLPolElt, RngSLPolElt -> RngSLPolElt
x - y : RngSLPolElt, RngSLPolElt -> RngSLPolElt
- x : RngSLPolElt -> RngSLPolElt
Creates the ring of multivariate straight-line polynomials over
the ring R with n indeterminates.
R . i : RngSLPol, RngIntElt -> RngSLPolElt
Return the ith indeterminate of the SL-polynomial ring R.
CoefficientRing(R) : RngSLPol -> Rng
Return the coefficient ring of R.
Return the rank of the SL-polynomial ring, 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 to compare SL-polynomials through their values at random
evaluation points.
Return the finite field and the number of random samples used to compare
polynomials. If SetEvaluationComparison has not been called, the
1st return value will be false while the second is undefined.
The ith partial derivative of the SL-polynomial x.
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 is a subgroup of U - provided it was contained in G.
This is achived by evaluating a G-relative U-invariant polynomial
f∈Z[x1, ..., xn]. 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.
RelativeInvariant(G, H) : GrpPerm, GrpPerm -> RngSLPolElt
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:
- - 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.
If IsMaximal is set to true, Magma will not compute a subgroup
chain but instead assume that H is a maximal subgroup of G.
If Risk is true, then Magma will use
GaloisGroupInvariant to compute invariants on each level.
By default, Magma will use generic invariants (ie. orbit sums of
monomials) on each level. The problem with using special invariants
as produced by GaloisGroupInvariant is that in the
third step we can no longer guarantee that the invariant returned
will be a true G-relative H-invariant as the G-stabilizer might be
too large. On the other hand, the special invariants are much faster
to evaluate and will give the desired result almost always.
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. The input for H1 and H2
consists of a tuple with two (or three) entries, the first specifying
the actual subgroupm the second the G-relative Hi-invariant and
the optional third a Tschirnhaus transformation that should be done
before the invariant is evaluated.
They 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 functions test if Fp eq 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 definetely 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, it it 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.
The result of the computation of Galois groups above contains,
apart form 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 invariant for group pairs, can be used to compute arbitrary
subfields of the splitting field.
GaloisSubgroup(S, U) : GaloisData, GrpPerm -> FldNum, UserProgram
GaloisSubgroup(f, U) : RngUPolElt, GrpPerm -> FldNum, UserProgram
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.
GaloisQuotient(f, Q) : RngUPolElt, GrpPerm -> SeqEnum[FldNum]
GaloisQuotient(S, Q) : GaloisData, GrpPerm -> SeqEnum[FldNum]
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. 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 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 ... .
The second return value is a sequence of tuples each containing
the data used to generate one step:
- - 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"
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.
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
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.
We start with a small example, to illustrate some of the parameters and
their influence:
> 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);
> TransitiveGroupDescription(G);
Thus 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-tranformation 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
- - define the element as a multivariate polynomial in
the roots, i
- - with the aid of Bound and the knowlegde of the complex
roots of f, find a bound B of the complex embeddings of i
and use Bnd as above to find a bound M on the
p-adic precision
- - use the information in D to compute i in Γ, ie
all p-adic conjugates in the "correct" ordering
- - use Reco to find the algebraic representation.
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 an 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 squarefree polynomial f∈Z[t] 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.
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 beused as an upper bound
for the p-adic precision used internally. Expecially 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].
The following example originates in a paper [BDE+] where,
among other things, polynomials are constructed whose roots have
a maximal number of linear dependencies. Note, that the polynomial
constructed here is not extremal.
> G := ShephardTodd(8);
> R := InvariantRing(G);
> p := PrimaryInvariants(R);
> p;
[
x1^8 + 14*x1^4*x2^4 + x2^8,
x1^12 - 33*x1^8*x2^4 - 33*x1^4*x2^8 + x2^12
]
> f := Resultant(p[1]-2, p[2]-3, 2);
> f := Polynomial(Integers(), UnivariatePolynomial(f));
> IsPower(f, 4);
true 27648*x^24 - 34560*x^16 - 25920*x^12 - 6480*x^8 - 648*x^4 - 1
> _, f := $1;
> GG, R, S := GaloisGroup(f);
> #GG;
192
> rel := LinearRelations(f:Galois := <GG, R, S>);
> #rel;
20
> rel[3];
[ 0, 0, 1, 0, 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 := &+ [rel[3][i]*IR.i : i in [1..24]];
> r;
(x7 + (x3 + (x6 * -1)))
> VerifyRelation(f, r:Galois := <GG, R, S>);
true
Now we use this to construct a field of degree 192 over Q where
the conjugates of a primitive element span only a 4-dimensional
vectorspace. We first define an invariant (a multivariate polynomial)
that corresponds to a primitive element. This can be verified by computing
all p-adic conjugates and checking that they are pairwise different.
> i := &+ [ i*IR.i : i in [1..23]];
> I := [Apply(g, i) : g in GG];
> #{Evaluate(i, R) : i in I};
192
So, since i = ∑iαi is a linear combination of the roots
αi of f, the dimension of the vectorspace spanned by the conjugates
of i is 4 again.
Note that this is a property of the polynomial not of the field.
> i := RelativeInvariant(GG, sub<GG|>);
> I := [Apply(g, i) : g in GG];
> #{Evaluate(i, R) : i in I};
192
> #LinearRelations(f, I:Galois := <GG, R, S>, Proof := false);
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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
