Ch15-GaloisGroupOfPoly.html

Galois Groups of Polynomials

ŠMike May, S.J., maymk@slu.edu, Saint Louis University

A worksheet to look at how Maple finds the Galois group of a polynomial.

> restart;

Outline:

Maple has a command "galois(f(x));" that computes the Galois group of f(x), an
irreducible polynomial of degree at most 8 over the rationals.

In this worksheet we would like to:

1) Learn the syntax of the Maple command and how to get more information on it from Maple's help facility;
2) Work through the computations to see how to compute galois groups;
3) Explore determining the degree of the splitting field to find the order of the Galois group.

>

Understanding how to use the galois command

The basic sytax of the command is galois(f); where f is a polynomial of degree 8 or less in a single variable.

> galois(x^6 + 2*x + 2);

The result gives us the name of the group from two different lists, whether the group is odd or even, its order, and a set of generators for the group expressed as a subgroup of the Symmetric group , where n is the degree of the polynomial.
The help command will give us more information on the galois command and the naming convensions used in the second set of names.

> ?galois

> ?`group/transnames`

For this class, we are interested not only on the result, but also in following the argument to see how Maple produces its answer.

We can get more information on how Maple is doing the computations by changing
the value of "infolevel[galois]" from its default value of 0 to 1 or 2.

> infolevel[galois] := 1;
galois(x^6 +3*x +3);

galois:   Computing the Galois group of    x^6+3*x+3

galois/absres:   -9059283 = -9059283, (nonsquare)

When the inforlevel is 1, we get the discriminant Maple computes in finding the Galois group.

> infolevel[galois] := 2;
galois(x^6 + 5*x + 5);

galois:   Computing the Galois group of    x^6+5*x+5

galois/absres:   -96971875 = -96971875, (nonsquare)

galois/absres:   Possible groups:   {"6T11", "6T13", "6T14", "6T16", "6T5", "6T9", "6T1", "6T2", "6T3", "6T6", "6T8"}

galois/absres:   p = 2   gives shape   6

galois/absres:   Removing   {"6T2", "6T8"}

galois/absres:   Possible groups left:   {"6T11", "6T13", "6T14", "6T16", "6T5", "6T9", "6T1", "6T3", "6T6"}

galois/absres:   p = 3   gives shape   6

galois/absres:   p = 17   gives shape   5, 1

galois/absres:   Removing   {"6T11", "6T13", "6T5", "6T9", "6T1", "6T3", "6T6"}

galois/absres:   Possible groups left:   {"6T14", "6T16"}

galois/absres:   p = 19   gives shape   6

galois/absres:   p = 23   gives shape   5, 1

galois/absres:   p = 29   gives shape   5, 1

galois/absres:   p = 37   gives shape   4, 1, 1

galois/absres:   p = 41   gives shape   3, 2, 1

galois/absres:   Removing   {"6T14"}

galois/absres:   Possible groups left:   {"6T16"}

When the infolevel is 2 we get a flurry of information that gives the results of intermediate computations.

[Note that Maple version 6 has an error in the table here. The group with 720 elements and the given generators is S(6), not A(6). Other groups seem to be correctly identified. The error is corrected in Maple version 7.]

Exercise:

1) Use the help pages to describe the two Galois groups found above as named groups.

>

Maple's method of computing Galois groups

Step 1 - Set up the polynomial and look at possible groups.

The information we got from running galois with infolevel at 2 is a bit overwhelming and needs a lot of explaining. We will step through the process that Maple uses to find the galois group of a polynomial. We start by defining the polynomial we will look at.

> f := x^6 + 3*x + 3;

The next thing to do is to check that the polynomial is in fact irreducible .

> factor(f);

If the polynomial factors, Maple will give an error message that it does not know how to compute the Galois group. Since our polynomial is irreducible Maple will continue.

> degf := degree(f);

The galois function in Maple is table driven. Maple stores information
about all the transative subgroups of Sn for n <8 in a table called `galois/groups`.
It will check information about the groups, then look up in the table to see what groups still qualify. When it gets down to a single group it quits. It is instructive to look at part of the table even if the meaning of the entries are not yet self-evident.

> grps:= `galois/groups`:
print(grps[6,1]);

The table above names the groups as dTn where d is the degree and n is the number of the group in a list of transative groups on d elements. We would like access to more descriptive names. The following procedure gets names of transative groups on sets of size up to 9.

> groupnamer := proc(x)
local deg, numb:
deg := substring(x,1):
numb := parse(substring(x,3..-1)):
`group/transgroup/names`||deg[numb]:
end proc:
groupnamer("6T9");
groupnamer(grps[6,1][1][1]);

Exercise:

2) Give examples to show that the Galois group of a reducible polynomial cannot be determined by knowing the Galois groups of the factors. (Hint, it suffices to look at 4th degree polynomials that factor as the product of 2 quadratic polynomials.)

>

Step 2 - See if the discriminant is square.

The group array has 24 entries indexed by ordered pairs (n,d) with n between 1 and 12 for the degree of the polynomial and d either 0 or 1 determined by whether or not the group is contained in the alternating group. (The entries for degrees 9 through 12 are rather incomplete.) Recall that the Galois group is contained in the alternating group if and only if the discriminant is a squar e.

We check this with our test polynomial.

> disc:= discrim(f, x);
issqr(disc);

Since the discriminant is not a square we want the (6, 1) entry of the table.
To make this easier to read, we just want to look at the names of the groups .

We will do that under both naming conventions.

> possible := grps[6,1];
possgrps := `galois/short`(possible);
print(`The possible groups are:`);
for i from 1 to nops(possgrps) do
print(possgrps[i] =groupnamer(possgrps[i]));
od;

>

Thus we have 11 possible groups at this point. The first set of names used, the names listed in possgrps, follows Butler and McKay, Comm. Alg. 11(1983) pp. 863-911. The second set of name was explained in the help page called earlier, but should be more familiar anyway. You should recognize the symmetric groups and . is a projective general linear group. It is obtained by taking invertible 2 by 2 matrices over , then modding out by the normal subgroup of scalar matrices. The cyclic groups are denoted by C(n). The group [S(3)^2]2 is the semidirect product of C(2) over the direct product of 2 copies of S(3).

>

Step 3 - Use primes to check for cycle types of elements of the group.

The next technique used is to factor f(x) mod p for a variety of primes. We have seen in class that if f(x) mod p has distinct roots and factors into irreducible factors of length , ... , over , then the Galois group G of f(x) contains an element that can be written as a product of disjiont cycles of length , ... , . This can be used to eliminate groups that do not have elements with the right cycle length.

The fouth element of information on each group above is a vector that encodes information about the cycle structure of elements of the group. obviously has elements of all possible cycle types. on the other hand only has elements of type 2,2,2, type 3,3, and type 6. If we order cycle types lexicographically with 1,1,1,1,1,1 omitted from the front as trivial, followed by 2,1,1,1,1 and ending with 6, we have 11 possible cycle structures. Of the 10 nontrivial types, has elements of the third, sixth, and tenth type.

For f(x) to have distinct roots mod p we need the leading coefficient of f(x) and the discriminant of f(x) to both be nonzero mod p. Since we started with a monic polynomial, we only need to check the discriminant. We see that it is zero mod 3 and 17 but not mod p for any other prime less thn 40.

> print(disc mod 2, disc mod 3, disc mod 7, disc mod 11, disc mod 13, disc mod 17);

We are ready to start considering specific primes.

> g = Factor(f) mod 2;

Since this polynomial is irreducible, G must contain an element that is a single 6-cycle. The commands cylcepattern and encode can be used to tell us that this is the 10th nontrivial partition of 6. That lets us remove and / from the list of possible groups .

>    shape := `galois/cyclepattern`(f, x, 2);
  e := `galois/encode`(`galois/initpart`(6), shape);
  rm := {}:
  rmgrp := {}:
  for i to nops(possible) do
      grp := possible[i];
      if grp[4][e] = 0 then
        rm := rm union {grp};
        rmgrp := rmgrp union {[grp[1],groupnamer(grp[1])]}; fi
      od:
  print(`groups removed `=rmgrp);
  possible := possible minus rm:
  grpleft := `galois/short`(possible);

> Factor(f) mod 5; Factor(f) mod 7;

Using p = 5, the polynomial factored the same way, so it did not give us any new information, but using p = 7 give a shape of 3, 2, 1, the fifth nontrivial partition of 6. This lets us eliminate 7 more groups .

>    shape := `galois/cyclepattern`(f, x, 7);
  e := `galois/encode`(`galois/initpart`(6), shape);
  rm := {}:
  rmgrp := {}:
  for i to nops(possible) do
      grp := possible[i];
      if grp[4][e] = 0 then
        rm := rm union {grp};
        rmgrp := rmgrp union {[grp[1],groupnamer(grp[1])]}; fi
      od:
  print(`groups removed `=rmgrp);
  possible := possible minus rm:
  print("The groups left are:");
    for i from 1 to nops(possible) do
      print([possible[i][1],groupnamer(possible[i][1])]);
    od;

Maple next tries the next 7 primes without being able to eliminate either of the remaining two groups. Furthermore, we have a group that has to be eliminated to eliminate any other groups.

(The group 6T13 is [S(3)^2]2, the semidirect product of the cyclic group C(2) acting on S(3)xS(3). This group is minimal in the set of groups still allowed under the ordering imposed by the shapes.) These two facts makes us suspicious that the minimal group is the Galois group. We need another way to eliminate groups.

>

Step 4 - Look at the factoring of resolvant polynomials.

The other approach we use is to look at how some related polynomials factor. (We have already used this method with the discriminant. We implicitly checked to see if the polynomial x^2 - disc(f(x)) factored in step 2.)

Now we will look at resolvant polynomials. Corresponding to any nth degree polynomial p(x) with roots { , , ... , } is a polynomial of degree (n, s) with roots that are products of s roots of p(x). Thus our 6th degree polynomial has a 15th degree resolvant with roots like and a 20th degree resolvant with roots like . The fifth and sixth entries of the group entries looks at how these polynomials factor. We see that if G is , both of these polynomials are irreducible while they factor in the other case. Let's look at the resolvant using products of two roots .

>    resolv := `galois/rsetpol`(f, x, 2);
  factrsetpoly := factor(resolv);
  shapersetpoly := [`galois/degrees`(factrsetpoly,x)];
  rm := {}:
  for i to nops(possible) do
        grp := possible[i];
        if grp[5] <> shapersetpoly then
          rm := rm union {grp};
         print(`We remove the group `,[grp[1],groupnamer(grp[1])]);
         print(`whose resolvant poly has factor shape `, grp[5]);fi
      od:
possible := possible minus rm:
print(`The groups left are:`);
for i from 1 to nops(possible) do
  print([possible[i][1],groupnamer(possible[i][1])],
   ` with res poly factor shape `, possible[i][5]);
  od:

>

Since the resolvant polynomial factors, we can remove and are left with our single answer.

Exercises:

3) Write out a clear argument for why the Galois group of is [S(3)^2]2. To use a Maple computation, you have to be able to justify the how it helps you find a Galois group.

>

4) Find the Galois group of . Write a clear argument justifying your answer.

>

Another approach - Computing the size of the group.

If K is the splitting field over F of f(x), then K = F[ , ..., ] where the are the roots of f(x). Let = F[ , ..., ]. Define to be the irreducible polynomial of over , a polynomial of degree . Then the degree of K over F is the product of the .

We use this approach to find the order of the Galois groups of when p is 2, 3, and 5.

We start with p = 5.

> f := x^4+5*x+5: alias(alpha = RootOf(f)): factor(f, alpha);

Since f factors completely over , the extension is of degree 4. Since the group must be a transitive subgroup of , the group must be .

> f[1] := x^4+3*x+3; alias(alpha[1] = RootOf(f[1])):
g := factor(f[1], alpha[1]);

This has a quadratic factor and 2 linear factors. Adjoining a root to the quadratic factor splits the polynomial completely. (Counting the constant term in front, the quadratic factor is the second factor of g. We can recover it with the op command.)

> f[2] := op(2,g); alias(alpha[2] = RootOf(f[2])):
h := factor(f[1], {alpha[1], alpha[2]});

Thus we see that the degree of the extension must be 8 when p is 3.

When p is 2 we have to work harder. We first note that adjoining a root of the polynomial leaves a cubic factor.

> f[1] := x^4+2*x+2; alias(alpha[3] = RootOf(f[1])):
g := factor(f[1], alpha[3]);
f[2] := op(2,g); alias(alpha[4] = RootOf(f[2])):

Thus the degree of the splitting field is at least 12. We now adjoin a root of that polynomial and factor again.

> h := factor(f[1], {alpha[3], alpha[4]});

We still have an irreducible quadratic factor. Thus the splitting field must be a degree 24 extension. This means it must be .

Exercises:

5) Show that the order of the Galois group of is 16.

6) Show that the order of the Galois group of is 32.