Determining the Galois Group of a Polynomial

Is there a simple way of determining the Galois group of a given
polynomial such as

       x^6 + 2*x^5 + 3*x^4 + 4*x^3 + 5*x^2 + 6*x + 7          (1)

A fairly quick and simplistic way is to check for roots of this 
polynomial modulo various primes, to see in which fields the 
polynomial splits completely into linear factors.  With the 
exception of primes that divide the discriminant (which for this 
equation is (-2^16)(7^4)), the polynomial will have no repeated 
roots, so if there are 6 distinct values of x between 0 and p-1 
such that f(x)=0 (mod p), then f splits in F_p[x].  

Now, by a theorem of Cebotarev we know the proportion of all primes 
relative to which f(x) splits is asymptotic to 1/order(G) where G 
is the galois group of f.  So, it's fairly simple to just write a 
little program to count "splitting primes" for any given polynomial
to give a very robust indication of the order of the group.

For the polynomial (1) we find that f(x) splits relative to p = 1013, 
3797, 6449, 6793, 7309, 9473, ... etc.  In fact, of the first 4792 
primes (not counting 2 and 7, of course), f(x) splits completely relative
to 36 of them, which is about 1 out of 133.  Clearly the order of the 
group is not 720 (which it would have to be if the Galois group was 
S_6), so it must be a proper subgroup.  The proper subgroups of S_6 
are
             group      order
            --------   ------
             A_6        360
             PGL(2,5)   120
             G_72        72
             PSL(2,5)    60
             G_48        48
                  etc.

and we can rule out the alternating group because the discriminant 
of an alternating group must be a positive square, whereas our 
discriminant is -157351936, so the only possibility that's really 
feasible is the group PGL(2,5) of order 120.

If we are worried that the group might really be G_72 (even 
though the "odds" of G_72 having only 36 of the first 4792 primes 
as splitting primes are incredibly tiny), it's not hard to rule 
out the smaller groups just by noting how f(x) factors in various 
F_p[x], and recalling that these factorizations correspond to cyclic
decompositions of the permutations in the respective Galois group.  
For the polynomial (1) we can verify that f splits into irredicible 
factors of the degrees shown below

                   degrees of
         p         factors in F_p[x]
       -----      ------------------
         3          6
         5          3,3
        13          5,1
        19          4,1,1
        61          2,2,1,1
        79          2,2,2

and of course we've seen that f splits into 1,1,1,1,1,1 relative
to p=1013, etc., so the Galois group must certainly contain the 
permutations with these cyclic decompositions, and this rigorously 
rules out any groups smaller than PGL(5,2).  Of course, this still 
relies on the count of splitting fields, which indicates an order 
in the neighborhood of 133, to assure us that the order of the 
group isn't 720.  However, if we compute the odds for a Poisson 
process of getting 36 splitting primes in a range where only 6 or 
7 would be expected, we probably won't lose much sleep over it.

Moreover, the numbers of factorizations of the different types for
the 168 primes (not counting 2 and 7) up to 1013 are

                                  predicted
          type         number     for G(2,5)
        ----------    -------     ---------
         6              36          33.2       +2.8
         5,1            31          27.6       +3.4
         4,1,1          39          41.5       -2.5
         2,2,1,1        20          20.7       -0.7
         2,2,2          11          13.8       -2.8
         3,3            29          27.6       +1.4
         1,1,1,1,1,1     1           1.4       -0.4

and these densities also conform pretty well with Cebotarev's
density theorem for the Galois group PGL(2,5), and of course 
the compositions {4,2}, {3,2,1}, {3,1,1,1}, and {2,1,1,1,1} are 
entirely absent, whereas if the group were S_6 they should have
asymptotic densities 90/720, 120/720, 40/720, and 15/720, 
respectively.  Thus they should account for almost 37% of 
the primes, but they are completely absent.  Furthermore, they 
are precisely the compositions that MUST be absent if the group 
is actually PGL(2,5).  

The point is that by just playing around with f(x) in various 
F_p[x] the Galois group of the polynomial quickly becomes very 
apparent, even without slogging through a rigorous demonstration.

                     "Anyone who considers arithmetical methods
                      of producing random digits is, of course,
                      in a state of sin."     J. von Neumann

Return to MathPages Main Menu