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