From: Dave Rusin
Subject: Re: Concerning Galois Groups a silly question!!!
Date: Fri, 9 Apr 1999 16:55:12 -0500 (CDT)
Newsgroups: sci.math
To: mckay@cs.concordia.ca
Keywords: How are Galois groups computed?
In article <7elqgp$lr8$1@newsflash.concordia.ca> you write:
>The essence of the problem is to determine whether (a) certain function(s)
>which are polynomials in n variables (n = deg(f)) take integer values
>for some substitution of the roots for the variables. It is not easy to
>prove the result is an integer. For this one needs either exact computation
>or some use of p-adic techniques. [See Darmon & Ford in Comm. in Algebra
>with M12 as an example.]
>
>I hope one day to product a book on computing Galois groups.
I hope one day to see this book.
Your description is not quite what I have been telling students (with the
caution to them that I was sort of an outsider). Am I so far off? I thought
the idea was to (1) pre-compute all transitive permutation groups of a
given degree (2) study the action of each on the original permutation set
and various derived sets (e.g. the set of ordered/unordered pairs/triples/...
of elements in the original set) (3) compute functions of the n coefficients
of the original polynomial which can distinguish these actions; for
example the square root of the discriminant of a cubic distinguishes
Alt(3) from Sym(3) -- one preserves it, not the other. (4) Decide whether
these functions are integral; by process of elimination, pick the right group.
This sounds like your description, except that I don't see why it is a
problem to detect integrality -- e.g. it's easy to decide whether an integer is
a square, right? I wasn't really sure but I thought the other tests only
really asked whether an integer point lay on an integral variety, which is
not a floating-point kind of problem.
I also must confess that I was disappointed when I learned of this algorithm:
somehow I wanted the coefficients to magically make the Galois group appear
(I don't know how I thought this would happen); a process of elimination
starting from a full list of candidates seemed somehow like cheating!
dave
==============================================================================
From: MCKAY john
Subject: [missing]
Date: Fri, 09 Apr 1999 20:56:55 -0400
Newsgroups: [missing]
To: rusin@math.niu.edu
Dave Rusin
>>The essence of the problem is to determine whether (a) certain function(s)
>>which are polynomials in n variables (n = deg(f)) take integer values
>>for some substitution of the roots for the variables. It is not easy to
>>prove the result is an integer. For this one needs either exact computation
>>or some use of p-adic techniques. [See Darmon & Ford in Comm. in Algebra
>>with M12 as an example.]
>>
>>I hope one day to product a book on computing Galois groups.
>
>I hope one day to see this book.
>
>Your description is not quite what I have been telling students (with the
>caution to them that I was sort of an outsider). Am I so far off? I thought
>the idea was to (1) pre-compute all transitive permutation groups of a
>given degree (2) study the action of each on the original permutation set
>and various derived sets (e.g. the set of ordered/unordered pairs/triples/...
>of elements in the original set) (3) compute functions of the n coefficients
>of the original polynomial which can distinguish these actions; for
>example the square root of the discriminant of a cubic distinguishes
>Alt(3) from Sym(3) -- one preserves it, not the other. (4) Decide whether
^^^^^^^^^^^^
between Gal(f) contained in Alt(n) or not... each function tells you only
what Gal(f) is contained in. By the way there IS a paper in about 1970
Math. Comp. by Stauduhar. It is the first modern paper on the topic.
There are two by me. in 1979 - one in J. Number Theory vol 20 and one in
J. SIAM Computing vol 8.
>these functions are integral; by process of elimination, pick the right group.
>
>This sounds like your description, except that I don't see why it is a
>problem to detect integrality -- e.g. it's easy to decide whether an integer
>is a square, right? I wasn't really sure but I thought the other tests only
>really asked whether an integer point lay on an integral variety, which is
>not a floating-point kind of problem.
>
>I also must confess that I was disappointed when I learned of this algorithm:
>somehow I wanted the coefficients to magically make the Galois group appear
>(I don't know how I thought this would happen); a process of elimination
>starting from a full list of candidates seemed somehow like cheating!
The point is that the polynomial may be too big to hold. For an easy small
example there is a paper of mine in J. Num. Thy in 1979. Here suppose we
have a deg 7 pol with the simple gp PSL(3,2) of order 168 as Gal/Q. To prove
this... [f=x^7-7*x+3] .. we construct a polynomial of degree binomial(7,3)=
35 and see if it has a deg 7 factor. This together with irreducibility
and the existence of a 4,2,1 shape (found by factoring mod some prime p)
suffices. See van der Waerden's book.
Now let's see what is involved for something serious... Let us take M24,
a perm gp of deg 24. Order = 24.23.22.21.20.48. We need to look at sets
8 at a time of roots. binomial(24,8) is BIG. And then we need to factor
it to find a factor of degree 759. This is not on.
If we try to find whether some fn has a value in Z, the problems are
1. finding the fn.
2. finding what identification of the roots is needed.
1. Is not easy.
2. There are a priori n! possible orderings of the roots.
Actually it is less since many will fix the fn.
For M24 there are 24!/ order(M24) = 19!/48 choices of ordering. This is
BIG.
However there are tricks which make is feasible to use shortcuts.
It is perhaps instructive to examine the 4-ic:
Here F = x1.x2+x3.x4 is the function which tells you if Gal(f)/Q is in
the dihedral group of order 8.
You will find a cubic polynomial with roots F, F_s, F_s^2 where s = (1,2,3)
applied to the x subscripts. This is the "resolvent cubic" R3.
Cases:
1. Disc(f) = square
G = Alt(4) or V4 (=2x2)
a. R3 irred => Alt4.
b. R3 3 linear factors => V4
2. Disc(F) = not square
G = Symm(4), D4, C4
a. R3 irred => Symm(4).
b. 1 linear factor g1 = x-(a1a2+a3a4) say. Other factor = g2.
if the roots of g2 and g = t^2-(a1+a2)t-a1a2a3a4 lie in same quadratic
field then Gal(f)/Q = C4 - else = D4. This uses fact that C4 has
a unique quadratic subfield.
Transitive groups of degree 4 =
S4
A4
D4
V4
C4
These form a semi-lattice.
As you say, it would be nice to see the group appear ... This is done by
Yokoyama et al, in some recent paper - but they first compute the splitting
field which is unnecessary... and is roughly the order of Gal(f) to compute.
I hope this makes some sense for you. There is a lot of difference between
computing something "in theory" and in practical terms. Unless you have some
good tricks it will not be feasible for reasonable degree.
John McKay