Computing the Galois group of a polynomial

Question

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.

Answer 1

There is an algorithm described in an ancient and interesting book on Galois Theory by Leonard 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$.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

There is another way that doesn't seem to be mentioned here. This is just something that occurred to me a few days ago; if anyone knows whether this has been done before I would greatly appreciate your comments.

It is well known that, given a field $K_0$ and a polynomial $p \in K_0[x]$, the following process will eventually give us a field $K_n$ which is a splitting field for $p$:

• choose a monic irreducible factor of $p$ of degree $> 1$ in $K_0[x]$. Call this factor $q_1$.

• Let $K_1 = K[r_1] / (q_1(r_1))$.

• choose a monic irreducible factor of $p$ of degree $> 1$ in $K_1[x]$. Call this factor $q_2$.

• Let $K_2 = K_1[r_2] / (q_2(r_2))$.

• choose a monic irreducible factor of $p$ of degree $> 1$ in $K_2[x]$, etc.

So we have a splitting field $K_n$, explicitly constructed as a quotient of $K_0[r_1, \ldots r_n]$. Let $I$ be the kernel of the obvious map from $K_0[r_1, ... r_n]$ to $K_n$. The algorithm above also gives us a Gröbner basis for $I$: for each of the polynomials $q_i$, with $2 \leq i \leq n$ let $q'_i$ be a lift of $q_i$ to a monic polynomial with coefficients in the polynomial ring $K_0[r_1, ... r_{i - 1}]$. Then it is easy to see that $B:=\{q_1(r_1), q'_2(r_2), ... q'_n(r_n)\}$ is a Gröbner basis for $I$ with the lexicographic monomial ordering with $r_n > r_{n-1} > ... > r_1$.

In general, if we have a ring $R$ with an ideal $J$, an automorphism $f: R \rightarrow R$ will induce an automorphism of $R/J$ iff $J$ is $f$-invariant, i.e. $f(x) \in J$ whenever $x \in J$. In particular, if $\sigma$ is a permutation of $\{ r_1 \ldots r_n \}$, and $f_\sigma$ is the corresponding automorphism of $K_0[r_1, ... r_n]$, we have that $f_\sigma$ induces an automorphism of $K_n$ iff $I$ is $f_\sigma$-invariant, or equivalently, $f_\sigma(b) \in I$ for each $b \in B$. Furthermore, we can test if $f_\sigma(b) \in I$ with multivariate division, which is convenient as $B$ is already a Gröbner basis for $I$.

In summary, we can check if a permutation $\sigma$ of the roots of $p$ is in the Galois group by checking if $f_\sigma(b) \in I$ for each $b \in B$, and this can be done with multivariate division.