MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Computing the Galois group of a polynomial

Does there exist an algorithm which computes the Galois group of a polynomial $p(x) \in \mathbb{Z}[x]$? Feel free to interpret this question in any reasonable manner. For example, if the degree of $p(x)$ is $n$, then the algorithm could give a set of permutations $\pi \in Sym(n)$ which generate the Galois group.

-
Yes. There is a description of (a slow) one in van der Waerden even. If you are interested in implementations, Pari/GP, Sage and Magma will do it if the degree is not too large. – Felipe Voloch Apr 29 2010 at 1:48
Section 6.3 of Henri Cohen's A Course in Computational Algebraic Number Theory - Google Books: books.google.com/… – François G. Dorais Apr 29 2010 at 1:55
GAP also computes Galois groups, and it even finds explicit formulas for the roots (this makes for very, very impressive formulas!) when they can be gotten by radicals---you need to install the Radiroot package. – Mariano Suárez-Alvarez Apr 29 2010 at 3:04
Maple's implementation also is just for low degree. – Gerald Edgar Apr 29 2010 at 12:08
To be even more precise: Maple's implementation goes to degree 12 (from algorithms of J. McKay). It was implemented well over 15 years ago; the code has been maintained but otherwise not improved since. In large part because there has (AFAIK) not been any demand for it. Probably because anyone serious about group computations would use GAP. – Jacques Carette Apr 29 2010 at 13:04
show 1 more comment

There is an algorithm described in an ancient and interesting book on Galois Theory by Eugene Dickson. Here is a brief sketch in the case of an irreducible polynomial $f\in \mathbb{Q}[x]$.

Suppose that $z_1\ldots z_n$ are the roots of $f$ in some splitting field of $f$ over $\mathbb{Q}$. (We don't need to construct the splitting field. The $z_i$ are mentioned here for the sake of explanation.) Let $x_1\ldots x_n$ be indeterminates. For a permutation $\sigma\in S_n$, let $$E_\sigma=x_1z_{\sigma(1)}+\ldots+ x_n z_{\sigma(n)}.$$ Let $g(x):=\prod _{\sigma} (x-E_\sigma)$, where $\sigma$ runs through all permutations in $S_n$. Each coefficient $c_i$ of $x^i$ in $g$ is symmetric in $z_1 \ldots z_n$, so (using the theorem on symmetric functions) we can write $c_i$ as a polynomial in $x_1\dots x_n$ with rational coefficients.

Assuming that this has been done, factor $g$ into irreducibles over the ring $\mathbb{Q}[x_1 \ldots x_n]$. Let $g_0$ be the irreducible factor of $g$ that is satisfied by $E_{Id}$, where $Id$ is the identity permuation. Then the galois group of $f$ consists of all permutations of $x_1\ldots x_n$ that fix $g_0$.

The point is that the computation of $g_0$ is effective (albeit horrendous) and so is the determination of the permutations that fix $g_0$.

-

I have been told by Frank Sottile that the reason many computer algebra systems only do low degrees is the following: Let $H$ be a subgroup of $S_n$ and suppose that we want to test whether $\mathrm{Gal}(f)$ is contained in a conjugate of $H$. One can use the following test: As in SJR's answer, let $z_1$, $z_2$, ..., $z_n$ be the roots of $f$. Choose some low degree monomial $m:=\prod z_i^{a_i}$ and let $q = \sum_{h \in H} h(m)$. If the Galois group is contained in $H$, then $q$ will be rational. Let $F(t) = \prod_{g \in G/H} (t-g(q))$. The polynomial $F$ has rational coefficients and is computable using symmetric polynomials. Using the rational root theorem, it is "easy" to test whether $F$ has a rational root. ("Easy" is in quotes because it involves prime factorization, but my understanding was that this is not the bottleneck.) If it does for several choices of $m$, then it is highly plausible that $\mathrm{Gal}(f)$ is contained in a conjugate of $H$.

For small $n$, the lattice of subgroups of $S_n$ is such that, by running tests of this sort, you can rapidly zoom in on a candidate for $\mathrm{Gal}(f)$. Once you hit $n=11$, you run into the Matheiu groups. At least as of a year ago, when Frank and I discussed this, he was very interested in finding good algorithms to test whether a Galois group was a subgroup of a Matheiu group.

-
In fact, Klueners and Fieker now have a method where they avoid pre-computation of the transitive subgroups, and compute both the lattices of relevant subgroups and necessary resolvents "on the fly" to make it practical for larger degrees (above 23). I think it is now in Magma, and can handle degree 50 or so rather routinely, and perhaps higher degrees with more work. Unfortunately, I can't find a preprint, only a conference abstract. atlas-conferences.com/cgi-bin/abstract/cayr-04 – Junkie Jun 14 2010 at 0:45

There is an essentially different algorithm from the ones mentioned above, due to N. Durov:

• N. V. Durov, Computation of the Galois group of a polynomial with rational coefficients. I. (Russian) Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 319 (2004), Vopr.Teor. Predst. Algebr. i Grupp. 11, 117–198, 301; English translation in J. Math. Sci. (N. Y.) 134 (2006), no. 6, 2511–2548 (MR2006b:12006)

• N. V. Durov, Computation of the Galois group of a polynomial with rational coefficients. II. (Russian) Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 321 (2005), Vopr. Teor. Predst. Algebr. i Grupp. 12, 90–135, 298; English translation in J. Math. Sci. (N. Y.) 136 (2006), no. 3, 3880–3907 (MR2006e:12004)

the algorithm is probabilistic, based on Chebotarev density theorem, and requires some random data as input; as far as I know, the algorithm ends with probability 1 for all equations provided that the Riemann hypothesis is true.

-
Most interesting. I'll point some of my colleagues to these papers (they like to de-randomize algorithms, then find a faster random one, de-randomize it, repeat). – Jacques Carette Apr 29 2010 at 13:01

The comments and SJR's answer show that there are indeed algorithms to compute this. But all of these suggestions are so far from effective, they can only be considered 'existence proofs' of an algorithm.

This is in fact a very active area of research, although it seems that most of this work has fallen completely under the radar of mainstream mathematicians, but this has been kept alive by a rogue band of mathematicians often calling a computer science department their home. Enough polemic, on to actual results. I find Alexander Hulpke's Techniques for the Computation of Galois Groups especially enlightening. Certain subcases, like that of the symmetric and alternating groups, can be found even more quickly (see Fast recognition of alternating and symmetric Galois groups ).

Even better, there are excellent implementations of recent such algorithms in GAP. Thus these computations are doubly effective.

-