From: ksbrown@seanet.com (Kevin Brown)
Newsgroups: sci.math
Subject: Re: Galois groups of polynomials
Date: Tue, 21 Jul 1998 19:38:11 GMT
On Wed, 15 Jul 1998 mbg@cyclone.be (marc bogaerts) wrote:
> Until a little while I was convinced that the galois group of a
> polynomial of degree p was the group S_p of permutations of p
> elements (generally speaking, unless the polynomial was rather
> "special").
The symmetric group S_n is indeed the most general possible Galois
group for a polynomial of degree n, but it's not at all uncommon for
a polynomial (even an irreducible one) of degree n to have as it's
group a proper SUB-group of S_n. This is the reason it's possible to
solve many particular 5th (and higher) degree polynomials in radicals.
On Wed, 15 Jul 1998 mbg@cyclone.be (marc bogaerts) wrote:
>Somewhere (I lost the reference) I saw that the Galois group of
>the polynomial x^6+2*x^5+3*x^4+4*x^3+5*x^2+6*x+7 is _not_ S6.
>How can one derive such conclusions ?
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,
which gives a very robust indication of the order of the group.
In your example, 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 you're 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 your example 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 you compute the odds for a Poisson
process of getting 36 splitting primes in a range where only 6 or
7 would be expected, you 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.
___________________________________________________________
| MathPages /*\ http://www.seanet.com/~ksbrown/ |
| / \ |
|____________/"Anyone who considers arithmetical methods ___|
of producing random digits is, of course,
in a state of sin." J. von Neumann