GitHub

Galois Theory

Let K be a finite (separable) field extension of k. Then, in contrast to most of the literature we distinguish two concepts

  • the automorphism group
  • the Galois group

The automorphism group deals with the actual automorphism of K fixing k and thus is, in general trivial. Access is via two constructions:

  • a list of all automorphisms (usually only the identity)
  • the group of automorphisms, returned as an abstract group and a map linking group elements to actual automorphisms

On the other hand, the Galois group is isomorphic to the automorphism group of the normal closure and is explicitly given as a group of permutations of the roots of the defining polynomial. Thus even in the case of K over k being normal, elements of the Galois group do not immediately give automorphisms at all.

Currently, the computation of Galois groups is possible for

  • K a simple extension of the rationals (AbsSimpleNumField)
  • K a simple extension of an AbsSimpleNumField
  • K a finite extension of the rational function field over the rationals. In this case the monodromy group can be computed as well, ie. the automorphism group over the complex numbers.
  • f a polynomial over the rationals, or an AbsSimpleNumField

Independently of the Galois group, subfields, that is intermediate fields between K and k can be computed as well.

Automorphism Group

The automorphisms are computed using various specialized factoring algorithms: lifting the roots of the defining polynomial in the given field modulo suitable prime ideal powers and recovering the true roots from this information.

The main information is included in the number field chapter, see for example

Subfields

The main information is included in the number field chapter, see

By setting set_verbosity_level(:Subfields, n::Int) to 1 or 2 information about the progress can be obtained.

Galois Group

The computation of Galois groups follows Stauduhars algorithm with many improvements, see ... for an overview.

The entrire computation can also be thought of finding a description of the splitting field of the polynomial. In fact, the information returned can be used to verify any algebraic identity between the roots, and find explicit subfields of the splitting field as well.

Information about the progress is available via

  • set_verbosity_level(:GaloisGroup, n::Int)
  • set_verbosity_level(:GaloisInvariants, n::Int)
galois_group — Function
galois_group(K::AbsSimpleNumField, extra::Int = 5; useSubfields::Bool = true, pStart::Int = 2*degree(K)) -> PermGroup, GaloisCtx

Compute the Galois group of the splitting field of the defining polynomial of K. Currently the polynomial needs to be monic.

The group is returned as an explicit permutation group permuting the roots as contained in the context object (the 2nd return value). The roots live in a suitable unramifed extension of the p-adics.

Examples

julia> K, a = cyclotomic_field(5);

julia> G, C = galois_group(K)
(Permutation group of degree 4 and order 4, Galois context for x^4 + x^3 + x^2 + x + 1 and prime 19)

julia> describe(G)
"C4"

julia> roots(C, 2)
4-element Vector{QadicFieldElem}:
 (4*19^0 + 2*19^1 + O(19^2))*a + 5*19^0 + 9*19^1 + O(19^2)
 (15*19^0 + 16*19^1 + O(19^2))*a + 9*19^0 + 7*19^1 + O(19^2)
 (18*19^0 + 18*19^1 + O(19^2))*a + 12*19^0 + O(19^2)
 (19^0 + O(19^2))*a + 11*19^0 + 19^1 + O(19^2)
source
galois_group — Method
galois_group(f::PolyRingElem{<:FieldElem})

Compute the automorphism group of a splitting field of f as an explicit group of permutations of the roots. Furthermore, the GaloisCtx is returned allowing algorithmic access to the splitting field.

source

Over the rational function field, we can also compute the monodromy group:

julia> Qt, t = rational_function_field(QQ, "t");

julia> Qtx, x = Qt[:x];

julia> F, a = function_field(x^6 + 108*t^2 + 108*t + 27);

julia> subfields(F)
4-element Vector{Any}:
 (Function Field over QQ with defining polynomial a^3 + 54*t + 27, (1//12*_a^4 + (3//2*t + 3//4)*_a)//(t + 1//2))
 (Function Field over QQ with defining polynomial a^2 + 108*t^2 + 108*t + 27, _a^3)
 (Function Field over QQ with defining polynomial a^3 - 108*t^2 - 108*t - 27, -_a^2)
 (Function Field over QQ with defining polynomial a^3 - 54*t - 27, (-1//12*_a^4 + (3//2*t + 3//4)*_a)//(t + 1//2))

julia> galois_group(F)
(Permutation group of degree 6 and order 6, Galois context for s^6 + 108*t^2 + 540*t + 675)

julia> G, C, k = galois_group(F, overC = true)
(Permutation group of degree 6 and order 3, Galois context for s^6 + 108*t^2 + 540*t + 675, Number field of degree 2 over QQ)

So, while the splitting field over Q(t) has degree 6, the galois group there is isomorphic to the S(3) or D(3) (on 6 points), the splitting field over C(t) is only of degree 3. Here the group collapses to a cyclic group of degree 3, the algebraic closure of Q in the splitting field is the quadratic field returned last. It can be seen to be isomorphic to a cyclotomic field:

julia> is_isomorphic(k, cyclotomic_field(3)[1])
true

The information returned consists always at least of a group G and a GaloisCtx: C. Jointly, they can be used to further work with the information:

roots — Method
roots(G::GaloisCtx, pr::Int)

The roots of the polynomial used to define the Galois context in the fixed order used in the algorithm. The roots are returned up to a precision of pr p-adic digits, thus they are correct modulo pprp^{pr}

For non-monic polynomials the roots are scaled by the leading coefficient. If raw is set to true, the scaling is omitted. The bound in the GaloisCtx is also adjusted.

source
upper_bound — Function
upper_bound(G::GaloisCtx, f...)

Given a GaloisCtx and some multivariate function, upper_bound the image of f upon evaluation at the roots implicit in G.

f can be

  • a multivariate polynomial or straight-line polynomial (strictly: any object allowing evaluate
  • elementary_symmetric or power_sum, in which case more arguments are needed: the array with the values and the index. upper_bound(G, power_sum, A, i) is equivalent to upper_bound(G, power_sum(A, i)) but more efficient.

In every case a univariate polynomial (over the integers) can be added, it will act as a Tschirnhaus-transformation, ie. the roots (bounds) implicit in G will first be transformed.

source
isinteger — Function
isinteger(C::GaloisCtx, B::BoundRingElem, v)

For an element v representing an integral polynomial evaluated at the roots stored in C, known to be bounded from above by B, either return true and an explicit (algebraic) integer in the base ring of the context or return false.

source
resolvent — Function
resolvent(C::GaloisCtx, G::PermGroup, U::PermGroup)

Find a G-relative H-invariant I and form the corresponding resolvent polynomial ∏(x−It)\prod (x-I^t) where the product runs over all coset-representatives of G/U.

source

To illustrate:

julia> Qx, x = QQ[:x];

julia> f = (x^2-2)*(x^2-3);

julia> G, C = galois_group(f)
(Permutation group of degree 4 and order 4, Galois context for x^4 - 5*x^2 + 6 and prime 11)

julia> r = roots(C, 5)
4-element Vector{QadicFieldElem}:
 5*11^0 + 2*11^1 + 6*11^2 + 8*11^3 + 11^4 + O(11^5)
 6*11^0 + 8*11^1 + 4*11^2 + 2*11^3 + 9*11^4 + O(11^5)
 (10*11^0 + 4*11^1 + 4*11^2 + 10*11^3 + 8*11^4 + O(11^5))*a + 2*11^0 + 6*11^1 + 4*11^2 + 3*11^3 + 9*11^4 + O(11^5)
 (11^0 + 6*11^1 + 6*11^2 + 2*11^4 + O(11^5))*a + 9*11^0 + 4*11^1 + 6*11^2 + 7*11^3 + 11^4 + O(11^5)

julia> r[1]^2
3*11^0 + O(11^5)

julia> r[3]^2
2*11^0 + O(11^5)

To illustrate the use as a splitting field, we will prove that r[1]^2 is actually an integer - and that r[1]+r[3] is not.

Any multivariate polynomial in four variables and with integer coefficients defines via evaluation at the roots an element in the splitting field. In case the evaluation is actually an integer, this can be proven with the tools provided.

julia> I, s = polynomial_ring(ZZ, 4);

julia> s[1]^2
x1^2

Next, we need a bound for the evaluation as a complex number, and compute the precision necessary:

julia> B = Oscar.GaloisGrp.upper_bound(C, s[1]^2)
(x <= 36)

julia> pr = Oscar.GaloisGrp.bound_to_precision(C, B)
7

Finally, we evaluate the polynomial at the roots and verify that the exact value is 3:

julia> evaluate(s[1]^2, roots(C, 7))
3*11^0 + O(11^7)

julia> Oscar.GaloisGrp.isinteger(C, B, ans)
(true, 3)

Now, to show that r[1] + r[3] is not an integer:

julia> B = Oscar.GaloisGrp.upper_bound(C, s[1] + s[3])
(x <= 12)

julia> Oscar.GaloisGrp.isinteger(C, B, evaluate(s[1] + s[3], roots(C, 7)))
(false, nothing)

More interestingly, we can use this to find the minimal polynomial of r[1] + r[3]. Generically, the Galois-conjugates of r[1]+r[3] should be the G-orbit of s[1]+s[3] evaluated at the roots.

Once the orbit is known, the coefficients of the minimal polynomial are just the elementary symmetric functions evaluated at the roots: 

julia> o = collect(orbit(G, s[1]+s[3]))
4-element Vector{ZZMPolyRingElem}:
 x1 + x3
 x1 + x4
 x2 + x4
 x2 + x3

julia> for i=1:4
         B = Oscar.GaloisGrp.upper_bound(C, elementary_symmetric, o, i)
         pr = Oscar.GaloisGrp.bound_to_precision(C, B)
         co = [evaluate(x, roots(C, pr)) for x = o]
         println(i, ": ", Oscar.GaloisGrp.isinteger(C, B, elementary_symmetric(co, i)))
       end
1: (true, 0)
2: (true, -10)
3: (true, 0)
4: (true, 1)

So, x^4-10x^2+1 should be the minimal polynomial to 3+2\sqrt 3 + \sqrt 2 - which it is.

In the case of computations over the rational function field, both the precision and the bound are more complicated - but can be used in the same way: Here, the roots are power series with q-adic coefficients, thus the precision has to cover both the precision of the coefficient as well as the number of terms in the series. Similarly, in this context, an isinteger is now a polynomial with integer coefficients. Thus the bound needs to bound the degree as well as the coefficient size.

julia> Qt,t = rational_function_field(QQ, "t");

julia> Qtx, x = Qt[:x];

julia> F, a = function_field(x^3+t+2);

julia> G, C = galois_group(F);

julia> describe(G)
"S3"

julia> _, s = slpoly_ring(ZZ, 3);

julia> B = Oscar.GaloisGrp.upper_bound(C, prod(s))
(x <= (9261, 2, 1))

julia> pr = Oscar.GaloisGrp.bound_to_precision(C, B)
(2, 2)

julia> Oscar.GaloisGrp.isinteger(C, B, evaluate(prod(s), roots(C, pr)))
(true, -t - 2)
galois_quotient — Method
galois_quotient(C::GaloisCtx, Q::PermGroup)

Find all(?) subfields of the splitting field s.th. the galois group will be permutation isomorphic to Q.

source
galois_quotient — Method
galois_quotient(C::GaloisCtx, d::Int)

Find all(?) subfields (up to isomorphism) of the splitting field of degree d with galois group isomorphic to the original one.

Examples

julia> Qx, x = QQ[:x];

julia> G, C = galois_group(x^3-2);

julia> galois_quotient(C, 6)
1-element Vector{Any}:
 Number field of degree 6 over QQ

julia> galois_group(ans[1])
(Permutation group of degree 6 and order 6, Galois context for x^6 + 324*x^4 - 4*x^3 + 34992*x^2 + 1296*x + 1259716 and prime 13)

julia> is_isomorphic(ans[1], G)
true
source
galois_quotient — Method
galois_quotient(C::GaloisCtx, d::Int, n::Int)

Find all subfields of the splitting field with galois group the n-th transitive group in degree d

source
galois_quotient — Method
galois_quotient(f::PolyRingElem, p::Vector{Int})

Equivalent to

galois_quotient(galois_group(f)[2], p[1], p[2])

Find all subfields of the splitting field of f with galois group the p[2]-th transitive group of degree p[1]

source
fixed_field — Function
fixed_field(GC::GaloisCtx, U::PermGroup, extra::Int = 5)

Given the GaloisCtx as returned by a call to galois_group and a subgroup U of the Galois group, compute the field fixed by U as a simple extension.

source
minpoly — Function
minpoly(C::GaloisCtx, I, extra::Int = 5)

Compute the minimal polynomial of I evaluated at the roots stored in C.

source
cauchy_ideal — Method
cauchy_ideal(f::PolyRingElem{<:FieldElem})

The coefficients of f are the elementary symmetric functions evaluated at the roots of f. The cauchy_ideal is the ideal generated by the differences between the elementary symmetric functions and the coefficients.

Examples

julia> Qx, x = QQ[:x];

julia> cauchy_ideal(x^4-2)
Ideal generated by
  x4^4 - 2
  x3^3 + x3^2*x4 + x3*x4^2 + x4^3
  x2^2 + x2*x3 + x2*x4 + x3^2 + x3*x4 + x4^2
  x1 + x2 + x3 + x4
source
galois_ideal — Function
galois_ideal(C::GaloisCtx, extra::Int = 5)

The so-called Galois ideal is a description of the splitting field of the polynomial underlying Cas a quotient by some maximal ideal. Algebraically, this ideal is an irreducible component of the Cauchy ideal, the ideal generated by the elementary symmetric functions and the coefficients of the polynomial.

Examples

julia> Qx, x = QQ[:x];

julia> i = galois_ideal(galois_group(x^4-2)[2])
Ideal generated by
  x4^4 - 2
  x3^3 + x3^2*x4 + x3*x4^2 + x4^3
  x2^2 + x2*x3 + x2*x4 + x3^2 + x3*x4 + x4^2
  x1 + x2 + x3 + x4
  x1*x3 + x2*x4
  x1^2*x3^2 + x2^2*x4^2 - 4
  x1^4 - 2
  x2^4 - 2
  x3^4 - 2
  x4^4 - 2

julia> k, _ = number_field(i);

julia> length(roots(k, x^4-2))
4
source

Over the integers, if the Galois group is solvable, the roots can be expressed as radicals:

solve — Method
Oscar.solve(f::ZZPolyRingElem; max_prec::Int=typemax(Int))
Oscar.solve(f::QQPolyRingElem; max_prec::Int=typemax(Int))

Compute a presentation of the roots of f in a radical tower. The necessary roots of unity are not themselves computed as radicals.

See also galois_group.

VERBOSE

Supports set_verbosity_level(:SolveRadical, i) to obtain information.

Examples

julia> Qx,x = QQ[:x];

julia> K, r = solve(x^3+3*x+5)
(Relative number field over with defining polynomial x^3 + (3*z_3 + 3//2)*a2 + 135//2
 over Relative number field over with defining polynomial x^2 + 783
 over Number field over Rational Field with defining polynomial x^2 + x + 1, Any[((1//81*z_3 + 1//162)*a2 - 5//18)*a3^2 + 1//3*a3, ((-1//162*z_3 + 1//162)*a2 + 5//18*z_3 + 5//18)*a3^2 + 1//3*z_3*a3, ((-1//162*z_3 - 1//81)*a2 - 5//18*z_3)*a3^2 + (-1//3*z_3 - 1//3)*a3])

julia> #z_3 indicates the 3-rd root-of-1 used

julia> map(x^3+3*x+5, r)
3-element Vector{Hecke.RelSimpleNumFieldElem{Hecke.RelSimpleNumFieldElem{AbsSimpleNumFieldElem}}}:
 0
 0
 0

julia> solve(cyclotomic(12, x)) #zeta_12 as radical
(Relative number field over with defining polynomial x^2 - 3//4
 over Number field over Rational Field with defining polynomial x^2 + 1, Any[a2 + 1//2*a1, a2 - 1//2*a1, -a2 - 1//2*a1, -a2 + 1//2*a1])
Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source
fixed_field — Method
fixed_field(C::GaloisCtx, s::Vector{PermGroup})

Given a descending chain of subgroups, each being maximal in the previous one, compute the corresponding subfields as a tower.

Examples

julia> Qx, x = QQ[:x];

julia> G, C = galois_group(x^3-3*x+17)
(Sym(3), Galois context for x^3 - 3*x + 17 and prime 7)

julia> d = derived_series(G)
3-element Vector{PermGroup}:
 Sym(3)
 Alt(3)
 Permutation group of degree 3 and order 1

julia> fixed_field(C, d)
(Relative number field of degree 3 over number field, a2)
Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source