.. status: ok



8.13 Computation of Galois Groups
---------------------------------

As a sample use of FriCAS's algebraic number facilities, group:Galois we
compute Galois:group the Galois group of the polynomial p(x)=x5-5x+12.


.. spadInput
::

	p := x^5 - 5*x + 12


.. spadMathAnswer
.. spadMathOutput
.. math::

+------------+
| x5-5x+12   |
+------------+




.. spadType

:sub:`Type: Polynomial Integer`



We would like to construct a polynomial f(x) such that the splitting
field:splitting field splitting field of p(x) is generated by one root
of f(x). First we construct a polynomial r=r(x) such that one root of
r(x) generates the field generated by two roots of the polynomial p(x).
(As it will turn out, the field generated by two roots of p(x) is, in
fact, the splitting field of p(x).)

From the proof of the primitive element theorem we know that if a and b
are algebraic numbers, then the field Q(a,b) is equal to Q(a+kb) for an
appropriately chosen integer k. In our case, we construct the minimal
polynomial of ai-aj, where ai and aj are two roots of p(x). We construct
this polynomial using resultant. The main result we need is the
following: If f(x) is a polynomial with roots ai…am and g(x) is a
polynomial with roots bi…bn, then the polynomial
h(x)=resultant(f(y),g(x-y),y) is a polynomial of degree m*n with roots
ai+bj,i=1…m,j=1…n.

For f(x) we use the polynomial p(x). For g(x) we use the polynomial
-p(-x). Thus, the polynomial we first construct is
resultant(p(y),-p(y-x),y).


.. spadInput
::

	q := resultant(eval(p,x,y),-eval(p,x,y-x),y)


.. spadMathAnswer
.. spadMathOutput
.. math::

+--------------------------------------------------------------------------------+
| x25-50x21-2375x17+90000x15-5000x13+2700000x11+250000x9+18000000x7+64000000x5   |
+--------------------------------------------------------------------------------+




.. spadType

:sub:`Type: Polynomial Integer`



The roots of q(x) are ai-aj,i≤1,j≤5. Of course, there are five pairs
(i,j) with i=j, so 0 is a 5-fold root of q(x).

Let's get rid of this factor.


.. spadInput
::

	q1 := exquo(q, x^5)


.. spadMathAnswer
.. spadMathOutput
.. math::

+----------------------------------------------------------------------------+
| x20-50x16-2375x12+90000x10-5000x8+2700000x6+250000x4+18000000x2+64000000   |
+----------------------------------------------------------------------------+




.. spadType

:sub:`Type: Union(Polynomial Integer,...)`



Factor the polynomial q1.


.. spadInput
::

	factoredQ := factor q1


.. spadMathAnswer
.. spadMathOutput
.. math::

+---------------------------------------------------------------------------+
| (x10-10x8-75x6+1500x4-5500x2+16000)*(x10+10x8+125x6+500x4+2500x2+4000)   |
+---------------------------------------------------------------------------+




.. spadType

:sub:`Type: Factored Polynomial Integer`



We see that q1 has two irreducible factors, each of degree 10. (The fact
that the polynomial q1 has two factors of degree 10 is enough to show
that the Galois group of p(x) is the dihedral group of order 10.See
McKay, Soicher, Computing Galois Groups over the Rationals, Journal of
Number Theory 20, 273-281 (1983). We do not assume the results of this
paper, however, and we continue with the computation. Note that the type
of factoredQ is FR POLY INT, that is, Factored Polynomial Integer.
Factored This is a special data type for recording factorizations of
polynomials with integer coefficients.

We can access the individual factors using the operation
nthFactornthFactorFactored.


.. spadInput
::

	r := nthFactor(factoredQ,1)


.. spadMathAnswer
.. spadMathOutput
.. math::

+-------------------------------------+
| x10-10x8-75x6+1500x4-5500x2+16000   |
+-------------------------------------+




.. spadType

:sub:`Type: Polynomial Integer`



Consider the polynomial r=r(x). This is the minimal polynomial of the
difference of two roots of p(x). Thus, the splitting field of p(x)
contains a subfield of degree 10. We show that this subfield is, in
fact, the splitting field of p(x) by showing that p(x) factors
completely over this field.

First we create a symbolic root of the polynomial r(x). (We replaced x
by b in the polynomial r so that our symbolic root would be printed as
b.)


.. spadInput
::

	beta:AN := rootOf(eval(r,x,b))


.. spadMathAnswer
.. spadMathOutput
.. math::

+-----+
| b   |
+-----+




.. spadType

:sub:`Type: AlgebraicNumber`



We next tell FriCAS to view p(x) as a univariate polynomial in x with
algebraic number coefficients. This is accomplished with this type
declaration.


.. spadInput
::

	p := p::UP(x,INT)::UP(x,AN)


.. spadMathAnswer
.. spadMathOutput
.. math::

+------------+
| x5-5x+12   |
+------------+




.. spadType

:sub:`Type: UnivariatePolynomial(x,AlgebraicNumber)`



Factor p(x) over the field . (This computation will take some time!)


.. spadInput
::

	algFactors := factor(p,[beta])


.. spadMathAnswer
.. spadMathOutput
.. math::

+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| (x+(-85b9-116b8+780b7+2640b6+14895b5-8820b4-127050b3-327000b2-405200b+2062400)1339200)(x+-17b8+156b6+2979b4-25410b2-1408066960)(x+143b8-2100b6-10485b4+290550b2-334800b-960800669600)(x+143b8-2100b6-10485b4+290550b2+334800b-960800669600)(x+(85b9-116b8-780b7+2640b6-14895b5-8820b4+127050b3-327000b2+405200b+2062400)1339200)   |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+




.. spadType

:sub:`Type: Factored UnivariatePolynomial(x,AlgebraicNumber)`



When factoring over number fields, it is important to specify the field
over which the polynomial is to be factored, as polynomials have
different factorizations over different fields. When you use the
operation factor, the field over which the polynomial is factored is the
field generated by

#. the algebraic numbers that appear in the coefficients of the
   polynomial, and
#. the algebraic numbers that appear in a list passed as an optional
   second argument of the operation.

In our case, the coefficients of p are all rational integers and only
beta appears in the list, so the field is simply .

It was necessary to give the list [beta] as a second argument of the
operation because otherwise the polynomial would have been factored over
the field generated by its coefficients, namely the rational numbers.


.. spadInput
::

	factor(p)


.. spadMathAnswer
.. spadMathOutput
.. math::

+------------+
| x5-5x+12   |
+------------+




.. spadType

:sub:`Type: Factored UnivariatePolynomial(x,AlgebraicNumber)`



We have shown that the splitting field of p(x) has degree 10. Since the
symmetric group of degree 5 has only one transitive subgroup of order
10, we know that the Galois group of p(x) must be this group, the
dihedral group group:dihedral of order 10. Rather than stop here, we
explicitly compute the action of the Galois group on the roots of p(x).

First we assign the roots of p(x) as the values of five root variables.

We can obtain an individual root by negating the constant coefficient of
one of the factors of p(x).


.. spadInput
::

	factor1 := nthFactor(algFactors,1)


.. spadMathAnswer
.. spadMathOutput
.. math::

+----------------------------------------------------------------------------------------+
| x+(-85b9-116b8+780b7+2640b6+14895b5-8820b4-127050b3-327000b2-405200b+2062400)1339200   |
+----------------------------------------------------------------------------------------+




.. spadType

:sub:`Type: UnivariatePolynomial(x,AlgebraicNumber)`




.. spadInput
::

	root1 := -coefficient(factor1,0)


.. spadMathAnswer
.. spadMathOutput
.. math::

+-------------------------------------------------------------------------------------+
| (85b9+116b8-780b7-2640b6-14895b5+8820b4+127050b3+327000b2+405200b-2062400)1339200   |
+-------------------------------------------------------------------------------------+




.. spadType

:sub:`Type: AlgebraicNumber`



We can obtain a list of all the roots in this way.


.. spadInput
::

	roots := [-coefficient(nthFactor(algFactors,i),0) for i in 1..5]


.. spadMathAnswer
.. spadMathOutput
.. math::

+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| [(85b9+116b8-780b7-2640b6-14895b5+8820b4+127050b3+327000b2+405200b-2062400)1339200,17b8-156b6-2979b4+25410b2+1408066960,-143b8+2100b6+10485b4-290550b2+334800b+960800669600,-143b8+2100b6+10485b4-290550b2-334800b+960800669600,(-85b9+116b8+780b7-2640b6+14895b5+8820b4-127050b3+327000b2-405200b-2062400)1339200]   |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+




.. spadType

:sub:`Type: List AlgebraicNumber`



The expression


.. spadVerbatim

::

 - coefficient(nthFactor(algFactors, i), 0)}



is the i-th root of p(x) and the elements of roots are the i-th roots of
p(x) as i ranges from 1 to 5.

Assign the roots as the values of the variables a1,...,a5.


.. spadInput
::

	(a1,a2,a3,a4,a5) := (roots.1,roots.2,roots.3,roots.4,roots.5)


.. spadMathAnswer
.. spadMathOutput
.. math::

+--------------------------------------------------------------------------------------+
| (-85b9+116b8+780b7-2640b6+14895b5+8820b4-127050b3+327000b2-405200b-2062400)1339200   |
+--------------------------------------------------------------------------------------+




.. spadType

:sub:`Type: AlgebraicNumber`



Next we express the roots of r(x) as polynomials in beta. We could
obtain these roots by calling the operation factor: factor(r,[beta])
factors r(x) over . However, this is a lengthy computation and we can
obtain the roots of r(x) as differences of the roots a1,...,a5 of p(x).
Only ten of these differences are roots of r(x) and the other ten are
roots of the other irreducible factor of q1. We can determine if a given
value is a root of r(x) by evaluating r(x) at that particular value. (Of
course, the order in which factors are returned by the operation factor
is unimportant and may change with different implementations of the
operation. Therefore, we cannot predict in advance which differences are
roots of r(x) and which are not.)

Let's look at four examples (two are roots of r(x) and two are not).


.. spadInput
::

	eval(r,x,a1 - a2)


.. spadMathAnswer
.. spadMathOutput
.. math::

+-----+
| 0   |
+-----+




.. spadType

:sub:`Type: Polynomial AlgebraicNumber`




.. spadInput
::

	eval(r,x,a1 - a3)


.. spadMathAnswer
.. spadMathOutput
.. math::

+-----------------------------------------------------------------------------------------------------------+
| (47905b9+66920b8-536100b7-980400b6-3345075b5-5787000b4+75572250b3+161688000b2-184600000b-710912000)4464   |
+-----------------------------------------------------------------------------------------------------------+




.. spadType

:sub:`Type: Polynomial AlgebraicNumber`




.. spadInput
::

	eval(r,x,a1 - a4)


.. spadMathAnswer
.. spadMathOutput
.. math::

+-----+
| 0   |
+-----+




.. spadType

:sub:`Type: Polynomial AlgebraicNumber`




.. spadInput
::

	eval(r,x,a1 - a5)


.. spadMathAnswer
.. spadMathOutput
.. math::

+------------------------------------------+
| 405b8+3450b6-19875b4-198000b2-58800031   |
+------------------------------------------+




.. spadType

:sub:`Type: Polynomial AlgebraicNumber`



Take one of the differences that was a root of r(x) and assign it to the
variable bb.

For example, if eval(r,x,a1-a4) returned 0, you would enter this.


.. spadInput
::

	bb := a1 - a4


.. spadMathAnswer
.. spadMathOutput
.. math::

+---------------------------------------------------------------------------------------+
| (85b9+402b8-780b7-6840b6-14895b5-12150b4+127050b3+908100b2+1074800b-3984000)1339200   |
+---------------------------------------------------------------------------------------+




.. spadType

:sub:`Type: AlgebraicNumber`



Of course, if the difference is, in fact, equal to the root beta, you
should choose another root of r(x).

Automorphisms of the splitting field are given by mapping a generator of
the field, namely beta, to other roots of its minimal polynomial. Let's
see what happens when beta is mapped to bb.

We compute the images of the roots a1,...,a5 under this automorphism:


.. spadInput
::

	aa1 := subst(a1,beta = bb)


.. spadMathAnswer
.. spadMathOutput
.. math::

+-------------------------------------------------------+
| -143b8+2100b6+10485b4-290550b2+334800b+960800669600   |
+-------------------------------------------------------+




.. spadType

:sub:`Type: AlgebraicNumber`




.. spadInput
::

	aa2 := subst(a2,beta = bb)


.. spadMathAnswer
.. spadMathOutput
.. math::

+--------------------------------------------------------------------------------------+
| (-85b9+116b8+780b7-2640b6+14895b5+8820b4-127050b3+327000b2-405200b-2062400)1339200   |
+--------------------------------------------------------------------------------------+




.. spadType

:sub:`Type: AlgebraicNumber`




.. spadInput
::

	aa3 := subst(a3,beta = bb)


.. spadMathAnswer
.. spadMathOutput
.. math::

+-------------------------------------------------------------------------------------+
| (85b9+116b8-780b7-2640b6-14895b5+8820b4+127050b3+327000b2+405200b-2062400)1339200   |
+-------------------------------------------------------------------------------------+




.. spadType

:sub:`Type: AlgebraicNumber`




.. spadInput
::

	aa4 := subst(a4,beta = bb)


.. spadMathAnswer
.. spadMathOutput
.. math::

+-------------------------------------------------------+
| -143b8+2100b6+10485b4-290550b2-334800b+960800669600   |
+-------------------------------------------------------+




.. spadType

:sub:`Type: AlgebraicNumber`




.. spadInput
::

	aa5 := subst(a5,beta = bb)


.. spadMathAnswer
.. spadMathOutput
.. math::

+----------------------------------------+
| 17b8-156b6-2979b4+25410b2+1408066960   |
+----------------------------------------+




.. spadType

:sub:`Type: AlgebraicNumber`



Of course, the values aa1,...,aa5 are simply a permutation of the values
a1,...,a5.

Let's find the value of aa1 (execute as many of the following five
commands as necessary).


.. spadInput
::

	(aa1 = a1) :: Boolean


.. spadMathAnswer
.. spadMathOutput
.. math::

+---------+
| false   |
+---------+




.. spadType

:sub:`Type: Boolean`




.. spadInput
::

	(aa1 = a2) :: Boolean


.. spadMathAnswer
.. spadMathOutput
.. math::

+---------+
| false   |
+---------+




.. spadType

:sub:`Type: Boolean`




.. spadInput
::

	(aa1 = a3) :: Boolean


.. spadMathAnswer
.. spadMathOutput
.. math::

+--------+
| true   |
+--------+




.. spadType

:sub:`Type: Boolean`




.. spadInput
::

	(aa1 = a4) :: Boolean


.. spadMathAnswer
.. spadMathOutput
.. math::

+---------+
| false   |
+---------+




.. spadType

:sub:`Type: Boolean`




.. spadInput
::

	(aa1 = a5) :: Boolean


.. spadMathAnswer
.. spadMathOutput
.. math::

+---------+
| false   |
+---------+




.. spadType

:sub:`Type: Boolean`



Proceeding in this fashion, you can find the values of aa2,...aa5. You
have represented the automorphism beta->bb as a permutation of the roots
a1,...,a5. If you wish, you can repeat this computation for all the
roots of r(x) and represent the Galois group of p(x) as a subgroup of
the symmetric group on five letters.

Here are two other problems that you may attack in a similar fashion:

#. Show that the Galois group of p(x)=x4+2x3-2x2-3x+1 is the dihedral
   group of order eight. group:dihedral (The splitting field of this
   polynomial is the Hilbert class field Hilbert class field of
   field:Hilbert class the quadratic field Q(145).)
#. Show that the Galois group of p(x)=x6+108 has order 6 and is
   isomorphic to S3, the symmetric group on three letters.
   group:symmetric (The splitting field of this polynomial is the
   splitting field of x3-2.)