How to find the Galois group of a polynomial?

I've been learning about Galois theory recently on my own, and I've been trying to solve tests from my university. Even though I understand all the theorems, I seem to be having some trouble with the technical stuff. A specific example would be how to find the Galois group of a given polynomial. I know some tricks, and I manage to solve some of those questions, but some not.

For example, one of the tests asks to find the Galois group of $x^{4}-4x+2$.

I can see that it is irreducible over $\mathbb Q$ (Eisenstein), but I have no clue as to how to find its Galois group over $\mathbb Q$. Can someone tell me how to do this? General techniques concerning this sort of problems are also welcome :).

Thanks!

This is an attempt to write a canonical answer listing techniques to compute Galois groups of explicit polynomials, primarily over $\mathbb{Q}$, as described in this meta thread. This answer is CW to encourage others to add techniques.

Computability: Over any reasonable field $K$, such as $\mathbb{Q}$, $\mathbb{F}_p$, $\mathbb{Q}(t)$, etc, Galois groups are computable. See Computable fields and Galois theory by Russel Miller for a good summary of this subject. Logicians can construct countable fields $K$ where the basic field operations $+$, $-$, $\times$, $\div$ are computable but the question "is $D$ square?" is not computable. In such a field, we cannot compute the Galois group of the splitting field of $x^2-D$. However, this is not the issue that this answer seeks to address and, as described in the linked article, there are very good criteria for showing that fields encountered in ordinary practice do not exhibit this phenomenon.

Although Galois groups are computable, computation of Galois groups, both by computer systems and by students in Galois theory courses, does not proceed along a single algorithm, but rather involves a smorgasboard of methods which are used to prove facts about the group $G$, until enough facts are accumulated to single out a particular group. The main goal of this entry is to list such techniques. I've listed the methods roughly in the order I would pull them out. Some methods are left blank for now; feel free to fill them in before I do!

Several of these methods are either primarily used to prove $G$ is large, or primarily used to prove $G$ is small. In this case, I have put "LARGE" or "SMALL" after the subject heading.

I also plan to put some useful lemmas about permutation subgroups at the end, since the more you know about subgroups of $S_n$, the fewer facts you need about a group $G$ in order to identify it.

As I assume you understand already, if $f$ is a separable polynomial of degree $n$, with roots $\theta_1$, $\theta_2$, ..., $\theta_n$, and $L$ is the splitting field of $f$ over $K$, then $Gal(L/K)$ is a subgroup of $S_n$, which can be thought of as permutations of the roots.

Noticing obvious additive and multiplicative relations between roots (SMALL) Let $f(x) = x^4+2 x^2 + 3$. Since all the exponents in $f$ are even, if $\theta$ is a root then so is $-\theta$. Let the roots be $(\theta_1, -\theta_1, \theta_2, -\theta_2)$. So any Galois symmetry must take the (unordered) pair $\{ \theta_1, - \theta_1 \}$ either to $\{ \theta_1, - \theta_1 \}$ or $\{ \theta_2, - \theta_2 \}$.

Similarly, let $f(x) = x^4 + 2 x^3 + 5 x^2 + 2 x + 1$. Since this polynomial is palindromic, if $\theta$ is a root, then so is $\theta^{-1}$. Writing the roots as $(\theta_1, \theta_1^{-1}, \theta_2, \theta_2^{-1})$, one obtains similar restrictions on $G$. One can also see more complicated multiplicative relations: If $\theta_1$ and $\theta_2$ are two roots of $x^5-2=0$, then so is $\theta_2^2/\theta_1$; relations of the form $\theta_3 = \theta_2^2/\theta_1$ quickly restrict the Galois group to be a subgroup of a $20$ element group.

Irreducibility of polynomials and transitive group actions The polynomial $f$ is irreducible if and only if the Galois group is transitive. Wolfram alpha, Mathematica, Maple, SAGE, etc. will factor polynomials for you.

To prove polynomials are irreducible by hand, one can use Eisenstein's criterion or can try to find a prime $p$ such that $f$ does not factor modulo $p$. However, there are polynomials which are irreducible but for which neither of these tests will prove them so.

Complex conjugation (LARGE) Suppose that $K$ is a subfield of $\mathbb{R}$ (such as the rationals). Let $\theta_1$, $\theta_2$, ..., $\theta_n$ be the roots of $f$, thought of as complex numbers. Again, Wolfram alpha or any computer algebra system will find the $\theta$'s for you.

If there are $r$ real roots and $2s$ complex roots among the $\theta$'s, then $G$ contains a permutation of conjugacy class $(1\ 2) (3\ 4) \cdots (2s-1 \ 2s)$

Discriminants Define $\beta = \prod_{i<j} (\theta_i - \theta_j)$ and $\Delta = \beta^2$. Since $\Delta$ is symmetric in the $\theta$'s, it is in the ground field $K$ and is quite reasonable to compute. The number $\Delta$ is called the discriminant of $f$. The Galois group $G$ is contained in $A_n$ if and only if $\beta$ is in $K$; in other words, if and only if $\Delta$ is square in $K$.

Here is a sample Wolfram alpha session, verifying that the Galois group of the splitting field of $-1 - 2 x + x^2 + x^3$ is contained in $A_3$.

Recognizing $S_n$ and $A_n$ (LARGE) A random polynomial over $\mathbb{Q}$ has very high probability of having Galois group $S_n$. (See this paper of Cohen for a precise bound.) So it is worth being able to recognize the Galois group $S_n$ early in the process. Keith Conrad has good notes on how to do so. Galois groups appearing on problem sets in Galois theory courses have a lower probability of being $S_n$. :-)

Reduction modulo $p$/Chebotarev's density theorem (LARGE, but useful both ways) Suppose that $p$ does not divide the discriminant of $f$. Let $f$ factor modulo $p$ into factors of degrees $(h_1, h_2, \ldots, h_d)$. Then $G$ contains an element with cycles of length $h_1$, $h_2$, ..., $h_d$. Conversely, by the Cebatarov density theorem, if $G$ contains an element of cycle type $(h_1, h_2, \ldots, h_d)$, then there is a prime $p$ such that $f$ factors modulo $p$ with factors of that size. See David Speyer's blogpost, Hendrik Lenstra's exposition or Keith Conrad's notes.

Here is an example:

Table[Factor[X^4 + 4 X^3 + 12 X^2 + 24 X + 24, Modulus -> Prime[n]], {n, 3, 10}]

produces

{(4 + X) (1 + 2 X + X^3), (5 + X) (2 + 3 X + 6 X^2 + X^3), 
 (3 + X) (8 + 9 X + X^2 + X^3), (12 + X) (2 + 4 X + 5 X^2 + X^3), 
 (16 + X + X^2) (10 + 3 X + X^2), (14 + 11 X + X^2) (18 + 12 X + X^2), 
 (17 + X) (19 + 3 X + 10 X^2 + X^3), (22 + X) (9 + 2 X + 11 X^2 + X^3)}

All the polynomials have cycle type $(3,1)$ or $(2,2)$, proving that $G$ contains those cycle types, and producing strong evidence that $G$ is contained in a group which only has cycles of that type. That can't quite be right, because $G$ contains the identity with cycle type $(1,1,1,1)$; searching up to $p=71$ finds such a factorization. But even running the search that far, we only see cycle types $(1,1,1,1)$, $(3,1)$, $(2,2)$, suggesting that $G = A_4$. Indeed,

Discriminant[X^4 + 4 X^3 + 12 X^2 + 24 X + 24, X]

outputs $331776=576^2$ so we know $G \subseteq A_4$, and the above data shows that $G$ contains a $3$-cycle and contains an element of type $(2,2)$, so $G = A_4$.

Distinguishing $D_4$ and $C_4$ Let $f(x) = x^4 - 5 x^2 + 5$. Since $f(x)$ is even, if $\theta$ is a root, so is $- \theta$. This shows that $G$ is a subgroup of $D_4$, the dihedral symmetries of a square. Since the polynomial is irreducible, the action on a $4$ element set is transitive, which makes $G$ either $D_4$, the cyclic group $C_4$, or $C_2 \times C_2$ with the generators $(12)(34)$ and $(13)(24)$. Since the discriminant is $2000$, which is not square, it is not contained in $A_4$, which rules out $C_2 \times C_2$.

Factoring modulo $p$ finds no factors with cycle type $(1,1,2)$, which strongly suggests $G$ is $C_4$. But that isn't a proof. This particular case comes up enough (especially on exams!) that there are special methods for it, see Keith Conrad's notes or my answer here.

Testing for $k$-transitivity (LARGE) More generally, let $\beta = \theta_1 + 2 \theta_2 + \cdots + k \theta_k$ and let $g(x)$ be the minimal polynomial of $\beta$. If $g(x)$ has degree $n(n-1) \cdots (n-k+1)$, then $G$ is $k$-transitive on $(\theta_1, \ldots, \theta_n)$. If there is some number of the form $\theta_{s_1} + 2 \theta_{s_2} + \cdots + k \theta_{s_k}$ which is not a root of $g$, then the group $G$ is not $k$-transitive. Since the $k$-transitive groups have been classified for $k \geq 3$ (see previous link), this can be very useful in identifying $G$.

Here is a small example. Take $f(x) = x^4-4 x^3+2 x^2+4 x-6$. We check that $f$ is irreducible:

f = x^4 - 4 x^3 + 2 x^2 + 4 x - 6;
Factor[f]

We store the roots of $f$ in variables t1, t2, t3, t4. (Mathematica can actually solve this polynomial exactly, but this is just meant as an example.)

{t1, t2, t3, t4} = x /. Solve[f == 0, x];

b = t1 + 2 t2;

g = MinimalPolynomial[b, x] 
(* Output is 42 - 84 x + 50 x^2 - 12 x^3 + x^4 *)

Since $g$ has degree $4$, we conclude that the group $G$ probably has an orbit of size $4$ acting on ordered pairs of distinct $\theta_i$'s. For a careful proof, we need to make sure that we don't have accidental equalities of the form $\theta_i+2 \theta_j = \theta_k + 2 \theta_{\ell}$. In particular, we check that $g(\theta_1+2 \theta_3) \neq 0$, so $(1,2)$ and $(1,3)$ are in different orbits for the $G$-action. This example is small enough for Mathematica to do exactly, but I'll do the computation numerically because that is good practice for larger examples:

N[g /. x -> t1 + 2 t3]
(* Output is 198.996 + 220.833 I *)

Relative resultants

Installing PARI, GAP or MAGMA This section is about which computer algebra systems have implemented general algorithms to do this, and where to get them.

Useful lemmas about subgroups of $S_n$

There are standard tests for polynomials of degree $3$ and $4$, and beyond that there are strategies that sometimes work and sometimes don't. There is a fairly thorough discussion in Keith Conrad's expository papers here (degrees $3$ and $4$) and here (Galois groups $S_n$ and $A_n$).

For irreducible quartic polynomials, there are five possible Galois groups: $S_4, A_4, D_4, V_4, C_4$. The polynomial $x^4 - 4x + 2$ has one extreme point, so has either $2$ or $0$ real roots, and by inspection it has $2$. That means that complex conjugation is an element of the Galois group, and it acts as a transposition.

Edit, 6/27/15: The original answer here contained an error; at this point we know that the Galois group is either $S_4$ or $D_4$, since those are the two possibilities that contain a transposition. To resolve this ambiguity you can use the techniques described in Keith Conrad's papers above or here.

The Galois group of a polynomial is a transitive permutation group of its roots. How many real roots does it have? What can you say about non-real roots? What are the transitive subgroups of $S_4$? For those, see http://hobbes.la.asu.edu/Groups/group-data/degree4.html from Transitive Group Data.

Consider the splitting field. Since adding a real root of the polynomial gives you an extension degree of 4 and that there are non-real roots, the degree of the splitting extension is at least 8, ie, is a multiple of 8. So, the Galois group is either $D_8$ (the dihedral group of order 8) or $S_4$.