My question is related to this one: Computing the Galois group of a polynomial.
I was wondering if there is a faster algorithm just to compute the order of the group rather than the group itself.
Also, has anybody compared the performance of GAP and Magma in computing Galois groups? I just heard Magma is very good at it.
I asked this question because I encounter every so often new bug with Magma's implementation and I wanted to see if I can implement something similar. But at this time I'm just interested in the exponent at the first place. This is the last annoying error that I get for basically any deg 5 poly that has Gal group $S_5$.
k := FiniteField(2);
kx<x> := RationalFunctionField(k);
kxbyb<y> := PolynomialRing(kx);
MinP := y^5 + y + x^2 + x;
print GaloisGroup(MinP);
The result is:
Runtime error: too much looping
Which I don't understand what it means (Magma Ver 2.16-8).
To be more clear, my ultimate goal is to check a lot of polynomials and throw out those with $S_n$ Gal group and focus on those which are not such. As you see even an upper bound over the exponent is enough for me.
Best Answer
I am actually one of the authors of the Galois package in Magma. Firstly, the "too much looping" error does not happen anymore (for this example at least) in the current Magma version (2.16-13). Secondly, the way Sn/An is recognized in general is through the use of factorisation as suggested. More precisely, the polynomial is factored modulo several primes and the resulting factors (well their degrees) are noted. Those give possible cycle types of the Galois group. If cycle types of certain patterns happen, we know the group is An/Sn. Those types are very frequent, hence this is trivial. However, then we hit a problem. In order to distinguish An and Sn usually one looks at the discriminant of the polynomial with the idea that the group is An (or in general contained in An) iff the discriminant is a square. This unfortunately breaks down in characteristic 2 and the currently employed test is slow. (And caused the "too much looping" message). Unfortunately, we don't have an interface like IsAnOrSn(f) which would be sufficient here.
In general, looking at cycle types or even at types and their frequency, will not determine the group nor the group size. All one gets from here are a lower bounds. However for small degrees (and 5 is small) this would work.
The connection between Kash and Magma here is difficult: Magma used to rely on Kash for the Galois groups, but the algorithm was limited to degree <= 23. This is the PhD of Katharina Geissler, her thesis can be found on the Kash page in Berln. The current Magma implementation of Galois groups is independent and does not share any code with Kash.