Galois groups with SymPy: why x⁵ − x − 1 has no formula in radicals

The problem: which quintics have a formula in radicals?

The quadratic formula has relatives for degree 3 and degree 4, and for degree 5 there is none. Yet some quintics can be solved in radicals and others cannot, and what decides it is the Galois group, a group of permutations of the roots that SymPy computes with galois_group. For \(x^5 - x - 1\) the group is \(S_5\), all 120 permutations of the five roots. For \(x^5 + 15x + 12\), which looks just as harmless, it is the Frobenius group \(F_{20}\) of order 20: number the roots 0 to 4, and \(F_{20}\) is the 20 maps \(k \mapsto ak + b \pmod 5\) with \(a \neq 0\).

A formula in radicals builds the roots from the coefficients with \(+\), \(-\), \(\times\), \(\div\) and \(n\)-th roots. The Galois group is the set of permutations of the roots that keep every polynomial relation with rational coefficients among them true. Galois's theorem says that the roots have a formula in radicals exactly when this group is solvable, a property defined in Step 3. We use the theorem without proving it (Dummit and Foote, section 14.7, have the proof). SymPy's galois_group handles polynomials up to degree 6 and raises a ValueError above. The cubics come first, because there the discriminant decides and you can check every step by hand.

The three patterns of roots look alike, and only the group in the label tells them apart. Each label is computed by galois_group, and the rings are the radical formulas SymPy finds, evaluated; Step 6 draws the figure.

Setup

galois_group lives in sympy.polys.numberfields and is importable from the top level. The permutation groups it returns come from sympy.combinatorics.

import sympy as sp
from sympy import (symbols, discriminant, factor_list, galois_group, roots, solve,
                   nroots, N, cos, pi, minimal_polynomial, count_ops)
import matplotlib.pyplot as plt

plt.rcParams.update({
    "figure.figsize": (7, 3.6), "figure.dpi": 110,
    "axes.spines.top": False, "axes.spines.right": False,
    "axes.grid": True, "grid.alpha": 0.25,
    "font.size": 11, "lines.linewidth": 1.8,
})
INK, ACCENT, SECOND, MUTED = "#1f2a44", "#c8553d", "#2a7f9e", "#8a8f98"

x = symbols("x")
cubics = [x**3 - 3*x + 1, x**3 - 2]
quintics = [x**5 - x - 1, x**5 + 15*x + 12, x**5 - 5*x + 12]

print(f"SymPy {sp.__version__}:", ",  ".join(str(p) for p in cubics + quintics))

SymPy 1.14.0: x**3 - 3*x + 1,  x**3 - 2,  x**5 - x - 1,  x**5 + 15*x + 12,  x**5 - 5*x + 12

Step 1: Check irreducibility and the discriminant

A group of permutations of the roots is transitive when, for any two roots, some element of the group takes the first to the second. The Galois group of \(p\) is transitive exactly when \(p\) is irreducible over \(\mathbb{Q}\) (Dummit and Foote, 14.6). One half you can see from the definition: if \(p = fg\) over \(\mathbb{Q}\), then \(f(r) = 0\) is a rational relation that holds for the roots of \(f\) and fails for those of \(g\), so no permutation in the group carries one kind into the other. galois_group accepts only irreducible polynomials, so factor_list comes first.

The discriminant is \(\Delta = \prod_{i<j} (r_i - r_j)^2\). Its square root \(d = \prod_{i<j} (r_i - r_j)\) changes sign under an odd permutation and keeps it under an even one. When \(\Delta = q^2\) with \(q\) rational, \(d = q\) or \(d = -q\) is a relation with rational coefficients, no permutation in the group may flip its sign, and the group lies in the alternating group \(A_n\). When \(\Delta\) is not a square, the group does not lie in \(A_n\) (same section).

for p in cubics:
    print(f"{str(p):14s}  factor_list: {factor_list(p)}   discriminant: {discriminant(p, x)}")

x**3 - 3*x + 1  factor_list: (1, [(x**3 - 3*x + 1, 1)])   discriminant: 81
x**3 - 2        factor_list: (1, [(x**3 - 2, 1)])   discriminant: -108

Both cubics are irreducible: one factor, of degree 3. The group is then transitive on three roots, so by orbit-stabilizer 3 divides its order, and inside \(S_3\) that leaves \(A_3\) (order 3) and \(S_3\) (order 6). The discriminant decides: \(81 = 9^2\) puts \(x^3 - 3x + 1\) in \(A_3\), and \(-108\), not a square, gives \(x^3 - 2\) the full \(S_3\).

Step 2: Compute the Galois group with galois_group

galois_group returns a pair. With by_name=True the first entry is the group's name, otherwise a PermutationGroup:

for p in cubics:
    name, alt = galois_group(p, by_name=True)
    print(f"{str(p):14s}  {name}   alt = {alt}")

G_A3, _ = galois_group(cubics[0])
print(G_A3)

x**3 - 3*x + 1  S3TransitiveSubgroups.A3   alt = True
x**3 - 2        S3TransitiveSubgroups.S3   alt = False
PermutationGroup([
    (0 1 2)])

The second entry, alt, is the discriminant test of Step 1 done for you: True when the group lies in \(A_n\). SymPy confirms \(A_3\) and \(S_3\). The permutation group of the first cubic is generated by the 3-cycle (0 1 2), which permutes three abstract labels; Pitfall 3 comes back to what they mean.

The relation behind \(A_3\) can be seen, too, once you know that the roots of \(x^3 - 3x + 1\) are \(2\cos(2\pi k/9)\) for \(k = 1, 2, 4\). The minimal polynomial of a number \(a\), which minimal_polynomial computes, is the monic rational polynomial of lowest degree with root \(a\). roots returns a dict from each root to its multiplicity, here with Cardano's formula:

r = roots(cubics[0])
print(list(r.values()), " first root:", list(r)[0])
print("minimal polynomial of 2cos(2π/9):", minimal_polynomial(2*cos(2*pi/9), x))
print(sorted(sp.re(N(z)) for z in r))
print(sorted(N(2*cos(2*pi*k/9)) for k in (1, 2, 4)))

[1, 1, 1]  first root: -(27/2 + 27*sqrt(3)*I/2)**(1/3)/3 - 3/(27/2 + 27*sqrt(3)*I/2)**(1/3)
minimal polynomial of 2cos(2π/9): x**3 - 3*x + 1
[-1.87938524157182, 0.347296355333861, 1.53208888623796]
[-1.87938524157182, 0.347296355333861, 1.53208888623796]

Three simple roots, written with cube roots of complex numbers although all three are real. Cardano cannot avoid the detour for any irreducible cubic with three real roots, the casus irreducibilis. The minimal polynomial of \(2\cos(2\pi/9)\) is our cubic, and the numbers agree.

Since \(2\cos 2\theta = (2\cos\theta)^2 - 2\), the map \(s(r) = r^2 - 2\) doubles the angle and sends \(k\) to \(2k\): \(1 \mapsto 2 \mapsto 4 \mapsto 8\). The cosine is even with period \(2\pi\), so \(k\) counts modulo 9 and up to sign, and \(8 \equiv -1\) is the root with \(k = 1\) again. So \(s\) is a 3-cycle of the roots. The three equations \(r_{\text{next}} = r^2 - 2\) are relations with rational coefficients, and a permutation \(\sigma\) in the group keeps them true, so \(\sigma(s(r)) = s(\sigma(r))\): \(\sigma\) commutes with the 3-cycle \(s\), and only the three rotations do. By transitivity the group is all three, \(A_3\), seen from a relation instead of from \(\Delta\).

Step 3: Read the group with sympy.combinatorics

The commutator subgroup \([G, G]\) is the subgroup generated by all \(ghg^{-1}h^{-1}\), and it is trivial exactly when \(G\) is abelian. The derived series repeats the step, \(G \supseteq [G, G] \supseteq [[G, G], [G, G]] \supseteq \dots\), and \(G\) is solvable when the series reaches the trivial group. derived_series returns the series until it stops shrinking, so a list that ends above 1 is complete, not cut off.

S3, _ = galois_group(cubics[1])
for label, G in [("S3", S3), ("A3", G_A3)]:
    series = [H.order() for H in G.derived_series()]
    print(f"{label}: degree {G.degree}, order {G.order()}, transitive {G.is_transitive()}, "
          f"abelian {G.is_abelian}, solvable {G.is_solvable}, derived series {series}")
print("roots of x**3 - 2:", list(roots(cubics[1])))

S3: degree 3, order 6, transitive True, abelian False, solvable True, derived series [6, 3, 1]
A3: degree 3, order 3, transitive True, abelian True, solvable True, derived series [3, 1]
roots of x**3 - 2: [2**(1/3), -2**(1/3)/2 - 2**(1/3)*sqrt(3)*I/2, -2**(1/3)/2 + 2**(1/3)*sqrt(3)*I/2]

The degree of a permutation group is the number of points it permutes, here the three roots. Both groups are transitive, as Step 1 predicted from irreducibility. \(S_3\) has the series of orders 6, 3, 1, so its steps shrink by factors 2 and 3. The radicals of \(x^3 - 2\) show the same pattern: a square root, \(\sqrt{3}\,i = \sqrt{\Delta}/6\), and a cube root, \(2^{1/3}\). The theorem makes this pattern general; here it is an observation, not a proof. Every permutation group of degree at most 4 is solvable, which is why formulas exist up to degree 4.

Step 4: Compute the groups of three quintics

The same loop, for the quintics. name.get_perm_group() turns the name into the group, so one call to galois_group per polynomial is enough:

groups = {}
print(f"{'polynomial':16s}{'Δ':>11s}  in A5  name  order  solvable  derived series")
for p in quintics:
    name, alt = galois_group(p, by_name=True)
    G = name.get_perm_group()
    groups[p] = (name.value, G)
    series = [H.order() for H in G.derived_series()]
    print(f"{str(p):16s}{int(discriminant(p, x)):11d}  {str(alt):5s}  {name.value:4s}  {int(G.order()):5d}  "
          f"{str(G.is_solvable):8s}  {series}")
    print(f"{'':16s}generators: {'  '.join(str(g) for g in G.generators)}")

polynomial                Δ  in A5  name  order  solvable  derived series
x**5 - x - 1           2869  False  S5      120  False     [120, 60]
                generators: (0 1 2 3 4)  (4)(0 1)
x**5 + 15*x + 12  259200000  False  M20      20  True      [20, 5, 1]
                generators: (0 1 2 3 4)  (1 2 4 3)
x**5 - 5*x + 12    64000000  True   D5       10  True      [10, 5, 1]
                generators: (0 1 2 3 4)  (0 4)(1 3)

SymPy's M20 ("metacyclic") is the \(F_{20}\) of the textbooks. Read its generators against the maps \(k \mapsto ak + b\): (0 1 2 3 4) is \(k \mapsto k + 1\) and (1 2 4 3) is \(k \mapsto 2k\). The maps with \(a = \pm 1\) form the dihedral group \(D_5\) of order 10, whose second generator (0 4)(1 3) is \(k \mapsto 4 - k\), and those with \(a = 1\) form the cyclic \(C_5\). So \(C_5 \subset D_5 \subset F_{20}\), the three solvable transitive groups of degree 5. None of the three quintics has \(C_5\), and the series of \(F_{20}\) and of \(D_5\) both end at 1.

The series of \(S_5\) stops at order 60, the alternating group \(A_5\), which is its own commutator subgroup. It never reaches 1, and that is the whole reason \(x^5 - x - 1\) has no formula. The discriminant cannot sort the quintics alone: \(64\,000\,000 = 8000^2\) puts \(x^5 - 5x + 12\) inside \(A_5\), but \(C_5\), \(D_5\), and \(A_5\) all lie there. galois_group separates them with resolvents and Tschirnhausen transformations, following H. Cohen, as its module docstring says.