Computing only the order of Galois group (not the group itself).

Question

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.

Answer 1

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.

Answer 2

Do you want a rigorous algorithm or a very compelling heuristic?

If $f(x)$ is an irreducible polynomial in ${\mathbf Q}[x]$ whose Galois group size you want to compute, then search for the primes $p$ such that $f(x) \bmod p$ splits completely into distinct linear factors. The natural density of this set is $1/N$, where $N$ is the size of the Galois group. This result is a theorem (a special case of the Chebotarev density theorem), and although effective error estimates have been given, by Lagarias and Odlyzko, I am not sure how practical they are.

For example, take $f(x) = x^3 - 2$. If you look at all primes $p$ below 10000, there are 1229 such primes and $x^3 - 2 \bmod p$ splits into three distinct linear factors 200 times. Since 200/1229 = .1627..., whose reciprocal is 6.145, the obvious guess is that the splitting field (and thus the Galois group) over $\mathbf Q$ has degree 6.

(Note: I say one should focus on splittings into distinct linear factors mod $p$. There are only finitely many primes modulo which there could be repeated factors, so you really don't have to worry about distinctness of the factors; just count primes $p$ up to some large $x$ for which the factorization of $f(x) \bmod p$ has all linear factors and you get the same limit.)

Answer 3

Code looks awful in a comment. Here is Kash 2.5 code to calculate the Galois group:

kash> AlffInit( FF(2), "x" );
"Defining global variables: k, w, kx, kxf, kxy, x, y, AlffGlobals"
kash> f := y^5 + y + x^2 + x;
y^5 + y + x^2 + x
kash> Galois( f );
"A5"

Kash 2.5 is the old version, but I never really learned the new version, KASH3. Both are available from http://www.math.tu-berlin.de/~kant/download.html

Kash 2.5 syntax is similar to GAP, and it is should be easy to loop over the polynomials. SAGE has interfaces to both magma and kash if for some reason you need to produce the polynomials in one program and filter them in the other.

I don't know much about function fields, but Kash says your MinP has galois group A5 over Z/2Z, but S5 over Z/3Z. Your magma code had some typos:

k := FiniteField(2);
kx<x> := RationalFunctionField(k);
kxy<y> := PolynomialRing(kx);
MinP := y^5 + y + x^2 + x;
GaloisGroup(MinP);

That is what I assume you meant. This gives "Runtime error: too much looping" in V2.16-10. Magma agrees that MinP over Z/3Z has Galois group S5, and A5 over the field with four elements (a silly trick you might use if you want to stick with magma).