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

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.

-
I would also be interested in the related question of determining the exponent of the group. As far as performance, Galois group identification in the "low" range is ridiculously fast in all systems. Magma may be the only system that contains algorithms for arbitrary degree. They are based on work form the TU-Berlin KANT school, but I have not seen published versions of the current algorithm (published versions stop at degree 23). –  Jack Schmidt Jun 13 '10 at 5:09
You could of course just compute the splitting field (e.g. by iterating pari's "polcompositum" command on your input f and the poly of largest degree in the last output)---that would be one way of computing the order of the group whilst meticulously avoiding computing the group at least externally. This might work well when the degree becomes large? Not sure though and not competent enough to be able to work it out, given that I know neither the algorithms used for computing splitting fields nor the algorithms known for computing Galois groups... –  Kevin Buzzard Jun 13 '10 at 7:26
I'm putting this comment here so that (hopefully) the OP will see it. I remember a talk by Fernando Rodriguez Villegas from four or so years ago where he explained how to augment the method described below by Keith Conrad (which in practice is slow, I think, because totally split primes tend to be large) by combining it with some character theory of finite groups. I can't find any record of this on his web-page, but perhaps I missed it; in any case, if you are interested you could ask him. –  Emerton Jun 14 '10 at 4:14
To Kevin Buzzard: Does polcompositum in Pari works for function fields as well? AFAIK Magma's support for function fields used to be incomparable to Pari and Sage –  Syed Jun 16 '10 at 1:14
Fernando Rodriguez Villegas has a neat little book "Experimental number theory", which has several sections on Galois groups. I am away from home so I can't check right now whether there is anything in there that's relevant, but there may well be. –  Balazs Jun 16 '10 at 12:57

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.

-

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.)

-
I worry that this is less efficient than the standard algorithms. For instance, we exam the primes 2,3,5,7 (or just 5,7) to see by cycle types that the galois group is the permutation group S3. For x^5+x^3+38*x^2-13*x+169 if one examines the primes up to 1000, then the splitting ratio (incorrectly) indicates A5 (ratio is 1/56), but if one looks at the degrees of the factors for just 2,3,5,7 then one gets S5 by cycle lengths. A set of four primes suffices to identify the permutation group structure, while a set of 168 primes fails to indicate the order. –  Jack Schmidt Jun 13 '10 at 4:53
Sure, in practice most Galois groups are S_n or A_n and it's very easy to prove that is the Galois group (if it really is) by finding a few "good" irreducible factorizations mod some primes and also determining if the discriminant is a perfect square (to distinguish S_n from A_n as potential Galois group). But what would you do if the polynomial has degree n and the Galois group is smaller than S_n or A_n? Try x^4 + 8*x + 14 but please avoid special quartic methods. I had initially picked something with degree 3 just to explain the meaning of the result I was describing (using the 1/N). –  KConrad Jun 13 '10 at 5:13
My point was that it's possible to guess the size of the Galois group without having to determine the group structure at the same time. –  KConrad Jun 13 '10 at 5:14
I think that in practice applying this method naively may not be so good, because totally split primes tend to be large, and so counting them is painful. However, I remember seeing a talk by Fernando Rodriguez Villegas on this topic four or so years ago, where he explained how to use Cebotarev plus some character theory to get a more efficient algorithm. I couldn't find any record of this on his web-page, unfortunately. –  Emerton Jun 14 '10 at 4:10

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).

-
@Jack Schmidt: 1. Thank you very much for the trick (changing the constant field). I'll see if the trick works for all polynomials. 2. I don't know how to enter the code here, so the editor doesn't eat my angular bracket signs (I copied the code from a working program). I would appreciate if you tell me how to write code in MathOverflow. 3. "Code looks awful in a comment". I really don't know what kind of comment I should put. I thought the code is simple and self sufficient (supposing that it was copied correctly). 4. You, of course, mean over Z/2Z(x) and Z/3Z(x). –  Syed Jun 16 '10 at 3:23
I don't mind using Kash as it's free, although I don't know the syntax that much. It's interesting that Kash has no problem but Magma has. AFAIK the function field modules of Magma have been copied from Kash. –  Syed Jun 16 '10 at 3:24
Sorry, two of my comments were phrased poorly and were not meant to be critical. Re #2, I put four spaces in front of each line to make it look pretty. I got a different answer (A5 vs. S5), so I wanted to make sure to say that I changed your code. If I get a wrong answer, then it may be because I asked the wrong question! Re #3, I was talking about my code. I tried putting it in a comment (like this), but it smooshed all the lines together. In an answer you can put each line on its own line (like you did). –  Jack Schmidt Jun 16 '10 at 17:14
Re: kash. I think most of Kash is incorporated into Magma, but it is harder than just "copying", and so small bugs might be in one and not in the other. I couldn't find the Galois group calculators for function fields in Kash3. I thought that Kash3 had extra support for galois groups, but all I could find was for the coefficient field Q(x). Kash2 has pretty good documentation and examples, but I might just like it because of the GAP-like feel. I found magma hard to learn, and lots of people think it is much easier to learn. –  Jack Schmidt Jun 16 '10 at 17:19
I talked to Magma people, their first response was that my "constant field" is too small (in accordance to your solution). They said they'll get back to me. Which haven't happened yet. They claimed that Magma is the only system that has implemented this computation for function field. But I think, for this moment the solving the problem over rational function field (as you did) is enough for me. –  Syed Jun 18 '10 at 1:53