Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
7  
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 '10 at 1:48
1  
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 '10 at 1:55
3  
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 '10 at 3:04
    
Maple's implementation also is just for low degree. –  Gerald Edgar Apr 29 '10 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 '10 at 13:04
show 1 more comment

4 Answers 4

up vote 21 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
6  
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 '10 at 13:01
    
These papers have essentially no new information, and a lot of category-theoretic jargon to obscure this fact. –  Igor Rivin Jul 1 '13 at 4:30
add comment

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.

share|improve this answer
7  
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 '10 at 0:45
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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