# 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 (`AnticNumberField`

)`K`

a simple extension of an`AnticNumberField`

`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`AnticNumberField`

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 specialised 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

`automorphism_list(::Hecke.NumFieldMor)`

`automorphism_group(::NumField)`

`automorphism_group(::NumField, ::NumField)`

## Subfields

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

`subfields(K::SimpleNumField; degree::Int = -1)`

`Hecke.principal_subfields(K::SimpleNumField)`

`subfields(FF::Generic.FunctionField{QQFieldElem})`

By setting `set_verbose_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_verbose_level(:GaloisGroup, n::Int)`

`set_verbose_level(:GaloisInvariants, n::Int)`

`galois_group`

— Function`galois_group(K::AnticNumberField, extra::Int = 5; useSubfields::Bool = true, pStart::Int = 2*degree(K)) -> PermGroup, GaloisCtx`

Computes 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)
(Group([ (1,4,2,3), (1,2)(3,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{qadic}:
(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)
```

`galois_group`

— Method`galois_group(f::PolyRingElem{<:FieldElem})`

Computes 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.

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

```
julia> Qt, t = RationalFunctionField(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 Rational field with defining polynomial a^3 + 54*t + 27, (1//12*_a^4 + (3//2*t + 3//4)*_a)//(t + 1//2))
(Function Field over Rational field with defining polynomial a^2 + 108*t^2 + 108*t + 27, _a^3)
(Function Field over Rational field with defining polynomial a^3 - 108*t^2 - 108*t - 27, -_a^2)
(Function Field over Rational field 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)
(Group([ (), (1,5)(2,3)(4,6), (1,3,4)(2,5,6) ]), Galois Context for s^6 + 108*t^2 + 540*t + 675)
julia> G, C, k = galois_group(F, overC = true)
(Group([ (1,4,3)(2,6,5) ]), 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 $p^{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.

`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.

`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`

.

`resolvent`

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

Find a `G`

-relative `H`

-invariant `I`

and form the corresponding resolvent polynomial $\prod (x-I^t)$ where the product runs over all coset-representatives of `G/U`

.

To illustrate:

```
julia> Qx, x = QQ["x"];
julia> f = (x^2-2)*(x^2-3);
julia> G, C = galois_group(f)
(Group([ (1,2), (3,4) ]), Galois Context for x^4 - 5*x^2 + 6 and prime 11)
julia> r = roots(C, 5)
4-element Vector{qadic}:
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)
(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)
(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)
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 $\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 = RationalFunctionField(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)`

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

`galois_quotient`

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

Finds 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])
(Group([ (), (1,5)(2,4)(3,6), (1,2,3)(4,5,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
```

`galois_quotient`

— Method`galois_quotient(C::GaloisCtx, d::Int, n::Int)`

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

`galois_quotient`

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

Equivalent to

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

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

`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.

`minpoly`

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

Computes the minimal polynomial of `I`

evaluated at the roots stored in `C`

.

`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(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)
```

`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 `C`

as 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(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
```

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_verbose_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.NfRelElem{Hecke.NfRelElem{nf_elem}}}:
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])
```

`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( [ 1 .. 3 ] ), Galois Context for x^3 - 3*x + 17 and prime 7)
julia> d = derived_series(G)
3-element Vector{PermGroup}:
Sym( [ 1 .. 3 ] )
Alt( [ 1 .. 3 ] )
Group(())
julia> fixed_field(C, d)
(Relative number field of degree 3 over number field, a2)
```