40
$\begingroup$

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.

$\endgroup$
6
  • 9
    $\begingroup$ 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. $\endgroup$ Apr 29, 2010 at 1:48
  • 1
    $\begingroup$ Section 6.3 of Henri Cohen's A Course in Computational Algebraic Number Theory - Google Books: books.google.com/… $\endgroup$ Apr 29, 2010 at 1:55
  • 3
    $\begingroup$ 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. $\endgroup$ Apr 29, 2010 at 3:04
  • $\begingroup$ Maple's implementation also is just for low degree. $\endgroup$ Apr 29, 2010 at 12:08
  • $\begingroup$ 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. $\endgroup$ Apr 29, 2010 at 13:04

5 Answers 5

36
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Leonard Eugene Dickson I think. $\endgroup$ Aug 5, 2015 at 0:24
21
$\begingroup$

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.

$\endgroup$
2
  • 8
    $\begingroup$ 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). $\endgroup$ Apr 29, 2010 at 13:01
  • 2
    $\begingroup$ These papers have essentially no new information, and a lot of category-theoretic jargon to obscure this fact. $\endgroup$
    – Igor Rivin
    Jul 1, 2013 at 4:30
15
$\begingroup$

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.

$\endgroup$
1
  • 8
    $\begingroup$ 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 $\endgroup$
    – Junkie
    Jun 14, 2010 at 0:45
9
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ I believe this algorithm is the one described by Susan Landau in the early '80s (and it has pretty bad complexity). $\endgroup$
    – Igor Rivin
    Aug 5, 2015 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.