Ch16-GaloisPolys2.html

A Second Look at Galois Groups: Probabalistic Methods

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

> restart;

In "Abstract Algebra" by Dummit and Foote), it is mentioned that "if one could compute forever one could at least be sure of the precise distribution of cycle types among the elements of the Galois group." The idea is that the cycle types we get by factoring the polynomial mod various primes shows up with a proportion that, in the limit, matches the proportion of the cycle type in the Galois group. We can't compute forever, but we can use Maple to check lots of primes and report the results.

As part of the set-up we want to use the Galois command. This loads a number of other commands in that we will be interested in.

> with(group):
galois(x^2+x+1);

For a given polynomial there is some preliminary information to gather. The information includes the degree of the polynomial and the possible partitions associated with that degree.

> f := x^7 + 3*x + 3;
deg := degree(f,x);
d:=discrim(f,x);
ifactor(d);
NumParts := `galois/encode`(`galois/initpart`(deg), deg)+1;
for i from 1 to NumParts do
print(i,combinat[decodepart](deg,i));
od;

Recall that if a prime p divides the discriminant, then our polynomial has repeated roots over the field . Thus we want the discriminant in factored form. The variable top tells us the number of cycle types for the given degree.

When the degree is less than or equal to 9, we can get a list of the transitive subgroups of along with the cycle types involved in those groups by pulling information from the groups table of the galois command.

>    Possible := {}:
grps:=`galois/groups`:
p0 := nops(grps[deg,0]):
for i from 1 to p0 do
   tempname := `galois/groups`[deg,0][i][1];
   Possible := Possible union {[tempname,
      group[transgroup](tempname, names) ,grps[deg,0][i][4]]}:
  od:
p1 := nops(grps[deg,1]):
for i from 1 to p1 do
   tempname := `galois/groups`[deg,1][i][1];
   Possible := Possible union {[tempname,
      group[transgroup](tempname, names) ,grps[deg,1][i][4]]}:
  od:
for i from 1 to nops(Possible) do
print(Possible[i]);
od;

We are now ready to look at the cycle types for a given polynomial factored over lots of primes. The loop in the code below is set up to print out the cases when the prime divide the discriminant or when our polynomial factors to produce a cylye type we have not seen with a smaller prime. A summary of the distribution of cycle types is given every 100 primes.

>    f := x^7 + 3*x + 3;
deg := degree(f,x);
d:=discrim(f,x);
ifactor(d);
top := `galois/encode`(`galois/initpart`(deg), deg)+1;
i:='i':
dist :=linalg[vector](top,0):
for j from 0 to 9 do
for i from 1 to 100 do
     p := ithprime(i+100*j):
     if modp(d,p) = 0 then
        print(p, ` divides the discrininant `, d);
     else
        shape := `galois/cyclepattern`(f, x, p):
        e := `galois/encode`(`galois/initpart`(deg), shape)+1:
        dist[e] := dist[e] + 1:
        if dist[e] = 1 then
             print(p,[shape], Factor(f) mod p);
         fi:
      fi:
od:
print(`The distribution of cycletypes at n = `,100*(j+1),` is `, dist);
od:
for i from 1 to top do
print(i, dist[i],combinat[decodepart](deg,i));
od;

Notice that the distribution at 500 primes follows very closely with the distribution at 1000 primes. It is pretty clear from this distribution that the group is S(7). (Recall that the information in the group table does not include the trivial partition that is first on our list.

Exercises:

1) List the partitions of 7 and the information on cycle structure on the transitive subgroups of .

2) Use the techniques of this worksheet to identify the Galois groups of three irreducible polynomials of degree 7.

There are a number of drawbacks to this technique. The first obvious drawback is that it gives a definitive answer only when the group is a symmetric group. A second problem is the number of primes we need to test to get all the cycle types. If we have a 9th degree polynomial whose Galois group is , we expect to find a prime over which it factors into linear factors once every 9! (about 360,000) primes. We expect to get a transposition every 10,000 primes. To get an answer in a more reasonable amount of time we notice that the existence of a group element of a given cycle type implies the existence of elements of the cycle types corresponding to powers of the element. Thus we always have a group element corresponding to the trivial cycle type, and we get a transposition whenever we have an element of cycle type (7,2) or (3,3,2,1) or any other cycle type containing only odd numbers except for a single 2. This technique then is useful to verify that a polynomial has as its Galois group. It should be noted that we expect most irreducible polynomials to have as their Galois group since that is the generic case.

A second case when the technique is useful is when we are trying to verify that the Galois group is a known group of small size. (For example, if we suspect that it is cyclic or dyhedral, testing 1000 primes gives very strong confirmation.)

Exercises:

3) Find an irreducible polynomial of degree 9 with Galois group . Justify your answer. How many primes did you have to consider before you became confident that you were confident that you had all the cycle types?)

4) Let f(x) be the 11th cyclotomic polynomial. We that the corresponding Galois group is cyclic of order 10. Find the distribution of cycle types produced by the first 1000 primes and compare to the expected distribution.

5) We also know the Galois group of polynomials of the form x^p - q for primes p and q. (The Galois group has order p*(p-1)/2 = p choose 2.) Compare the expected and acual distribution of cycle types for the first 1000 primes for an 11th degree polynomial of this form.