The determination of the Galois group of a polynomial

Question

The GAP package has a function $\mathtt {GaloisType}$ that takes a polynomial as an argument and returns a number, the index of the transitive group of order the degree of the polynomial. I read somewhere that the algorithm is based on a theorem by Dedekind based on how the polynomial factors if taken modulo some primes. But this theorem only gives a postive answer about the existence of a cycle, if it finds it, but this gives no certainty about what the group actually is. I also know that there are some probability theorems concerning this problem, but I don't now what they state. What is the probability that the answer is wrong?

Answer 1

It seems the comment field is limited, thus a second answer as example:

What you describe is quite possible (and a plausible and intelligent question):

Take $p(x)=x^3+x^2-2x-1$ (the minimal polynomial of E(7)+E(7)^6, so one can actually work with roots). This is irreducible over the rationals and has Galois group A3, so factoring modulo primes will only ever give irreducible or 3 linear factors. Now both A3 and S3 are transitive on 2-sets, so we need to (white lie! see at the end) take 2-sequences. We therefore form the polynomial whose roots are of the form $\alpha_i+2\alpha_j$. We can do so by calculating the resultant $r(x)=res_y(2^3\cdot p(y/2),p(x-y))$, and dividing off (the case $i=j$) the factor $3^3p(x/3)$.

gap> r:=Resultant(2^3*Value(p,y/2),Value(p,x-y),y);           
x^9+9*x^8+x^7-168*x^6-308*x^5+609*x^4+1463*x^3-363*x^2-1062*x+351
gap> r/3^3/Value(p,x/3);
x^6+6*x^5+x^4-36*x^3-20*x^2+48*x-13

In practice, a method based on symmetric functions is easier

gap> TwoSeqPol(p,2);
x^6+6*x^5+x^4-36*x^3-20*x^2+48*x-13

produces the same result. If we factor this polynomial of degree 6, we get two factors of degree 3 -- two orbits on 2-sequences. If the initial polynomial had had Galois group S3, it would have stayed irreducible.

You can observe what GAP is doing by setting

SetInfoLevel(InfoGalois,3);

Then GaloisType will print information about the process, e.g.

gap> GaloisType(x^5+x^4-4*x^3-3*x^2+3*x+1);
#I  Partitions Test
#I  cands:[ 1, 2, 4 ]
#I  2-Set Resolvent
#I  trying res nr. 0
#I  SumRootsPol 2
#I  Candidates :[ 1, 2 ]
#I  2-Seq Resolvent
#I  TwoSeqPol 2
#I  Candidates :[ 1 ]
1

here cycle shapes leave groups 1,2 and 4 left. Action on 2-sets (SumRootsPol 2) leaves 1 and 2, and 2-sequences finally nails the group.

If you do this on $x^3+x^2-2x-1$ above you notice that the 2-sequence polynomial is never used. That is because we can distinguish $A_n$/$S_n$ by whether the discriminant (for $p$ it is $49$) is a square.

Answer 2

What is happening is a 2-stage process. First Dedekind's theorem is used to obtain some cycle shapes. This gives a lower bound for the Galois group.

Afterwards, polynomials that correspond to the action of the Galois group on k-sets or k-sequences are factored. (E.g. $$\prod_{i,j} (x-(\alpha_i+\alpha_j))$$ corresponds to the action on 2-sets.) This way one shows that the Galois group can't be larger. The result is (modular programming errors) proven correct.

IF you only want a probabilistic result, based on Chebotarev's theorem, the function $\mathtt {ProbabilityShapes}$ does so (and is much faster).

At the risk of shameless self-promotion, http://www.math.colostate.edu/~hulpke/talks/galoistalk.pdf are slides of a relevant talk, http://www.math.colostate.edu/~hulpke/paper/gov.pdf a survey paper.