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 x44x+2.

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

Thanks!

Answer

This is an attempt to write a canonical answer listing techniques to compute Galois groups of explicit polynomials, primarily over 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 Q, Fp, 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 +, , ×, ÷ 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 x2D. 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 Sn, 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 θ1, θ2, …, θn, and L is the splitting field of f over K, then Gal(L/K) is a subgroup of Sn, which can be thought of as permutations of the roots.

Noticing obvious additive and multiplicative relations between roots (SMALL) Let f(x)=x4+2x2+3. Since all the exponents in f are even, if θ is a root then so is θ. Let the roots be (θ1,θ1,θ2,θ2). So any Galois symmetry must take the (unordered) pair {θ1,θ1} either to {θ1,θ1} or {θ2,θ2}.

Similarly, let f(x)=x4+2x3+5x2+2x+1. Since this polynomial is palindromic,
if θ is a root, then so is θ1. Writing the roots as (θ1,θ11,θ2,θ12), one obtains similar restrictions on G. One can also see more complicated multiplicative relations: If θ1 and θ2 are two roots of x52=0, then so is θ22/θ1; relations of the form θ3=θ22/θ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 R (such as the rationals). Let θ1, θ2, …, θn be the roots of f, thought of as complex numbers. Again, Wolfram alpha or any computer algebra system will find the θ‘s for you.

If there are r real roots and 2s complex roots among the θ‘s, then G contains a permutation of conjugacy class (1 2)(3 4)(2s1 2s)

Discriminants Define β=i<j(θiθj) and Δ=β2. Since Δ is symmetric in the θ's, it is in the ground field K and is quite reasonable to compute. The number Δ is called the discriminant of f.
The Galois group G is contained in An if and only if β is in K; in other words, if and only if Δ is square in K.

Here is a sample Wolfram alpha session, verifying that the Galois group of the splitting field of 12x+x2+x3 is contained in A3.

Recognizing Sn and An (LARGE) A random polynomial over Q has very high probability of having Galois group Sn. (See this paper of Cohen for a precise bound.) So it is worth being able to recognize the Galois group Sn 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 Sn. 🙂

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 (h1,h2,,hd). Then G contains an element with cycles of length h1, h2, ..., hd. Conversely, by the Cebatarov density theorem, if G contains an element of cycle type (h1,h2,,hd), 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=A4. Indeed,

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

outputs 331776=5762 so we know GA4, and the above data shows that G contains a 3-cycle and contains an element of type (2,2), so G=A4.

Distinguishing D4 and C4 Let f(x)=x45x2+5. Since f(x) is even, if θ is a root, so is θ. This shows that G is a subgroup of D4, the dihedral symmetries of a square. Since the polynomial is irreducible, the action on a 4 element set is transitive, which makes G either D4, the cyclic group C4, or C2×C2 with the generators (12)(34) and (13)(24). Since the discriminant is 2000, which is not square, it is not contained in A4, which rules out C2×C2.

Factoring modulo p finds no factors with cycle type (1,1,2), which strongly suggests G is C4. 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 β=θ1+2θ2++kθk and let g(x) be the minimal polynomial of β. If g(x) has degree n(n1)(nk+1), then G is k-transitive on (θ1,,θn). If there is some number of the form θs1+2θs2++kθsk which is not a root of g, then the group G is not k-transitive. Since the k-transitive groups have been classified for k3 (see previous link), this can be very useful in identifying G.

Here is a small example. Take f(x)=x44x3+2x2+4x6. 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 θi's. For a careful proof, we need to make sure that we don't have accidental equalities of the form θi+2θj=θk+2θ. In particular, we check that g(θ1+2θ3)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 Sn

Attribution
Source : Link , Question Author : IBS , Answer Author :
9 revs, 3 users 98%

Leave a Comment