Overview

  • What does it mean to compute a Galois group?
  • How do local factorizations and resolvents determine it?
  • Which software outputs require a separate proof step?

Input and permutation action

The input is a polynomial and a ground field. For f∈Q[x]f\in\mathbb Q[x], clear denominators, remove content, and compute a squarefree factorization. A transitive-group label describes the action for an irreducible factor. If ff is reducible, its whole splitting field is a compositum; the group need not be the direct product of the groups of the factors because their splitting fields can intersect.

For an irreducible degree-nn input, the output should specify the subgroup of SnS_n up to conjugacy, together with its action on the roots. An abstract isomorphism type alone may lose information needed for cycle types, resolvents, subfields, or iteration.

References 2

Subgroup descent

  1. Irreducibility and separability. A factorization or irreducibility certificate establishes the input assumptions.
  2. Structural restrictions. The discriminant, reciprocity, composition, and known intermediate fields restrict the ambient permutation group.
  3. Local factorizations. Exact irreducible factorizations at good primes determine cycle types.
  4. Subgroup tests. Primitive-group theorems, relative resolvents, and subgroup descent eliminate incompatible candidates.
  5. Certification. The decisive tests require exact verification and retained proof data.

Stauduhar's method makes the fourth step systematic. Starting from a known overgroup, it tests relative invariants for maximal subgroups and descends whenever a certified resolvent condition permits it.

References 2

Solvability by radicals

Landau–Miller (1985) give a polynomial-time decision procedure for solvability by radicals over Q\mathbb Q, in the dense binary input model. Their paper also constructs radical expressions in a compact straight-line-program representation. The size bound applies to this compact encoding and need not survive expansion of repeated subexpressions.

The method exploits blocks of imprimitivity and the restricted size of primitive solvable permutation groups. Thus one can answer a structural question about a Galois group without first listing all its elements. This is different from constructing the splitting field in an explicit basis: its degree may be n!n! for a degree-nn polynomial with group SnS_n.

References 1

Software

ToolScopeVerification data
MagmaNative GaloisGroup accepts integer, rational, and number-field polynomials without a fixed degree cap, but does not automatically prove its conditional steps. The documented GaloisProof(f,S) function covers integer polynomials; an absolute number-field overload is also available.Input, options, GaloisData, successful proof result, and version.
PARI/GP 2.19polgalois requires irreducible input over Q\mathbb Q, of degree at most seven, or eleven with galdata. Its resolvent method can rarely return a wrong answer when initial numerical precision is insufficient.Polynomial, precision, complete output, numbering convention, and version.
SageMath 10.10The rational-polynomial galois_group interface requires irreducible input. It uses PARI through degree eleven and attempts GAP above that; GAP's documented algorithm range is through degree fifteen, with some higher cases possible. The Magma wrapper identifies groups only through degree thirty.Routine, algorithm, backend version, permutation action, and separate certification outcome.

Native Magma's degree-independent algorithm and Sage's wrapper have different limits. A database containing transitive groups of a given degree does not guarantee that the group-computation algorithm handles every polynomial of that degree. Runtime and memory can be decisive even without a formal degree cap.

For Sage number fields, gc_numbering controls whether permutations act on roots of the original defining polynomial or of the Galois closure's defining polynomial. For a relative number field, this interface currently computes the absolute Galois closure over Q\mathbb Q and emits a deprecation warning. It does not compute the group over the intermediate base field.

Sage also documents galois_group_davenport_smith_test: return values 11 and 22 certify SnS_n and AnA_n, while 00 means inconclusive. Its default checks irreducibility; setting assume_irreducible=True requires an independently established hypothesis. This specialized test is different from unrestricted group determination.

References 3
  • MagmaGaloisDocumentation · GaloisGroup and GaloisProofInput fields, degree independence, conditional output, and documented certification scope.Source
  • PARIDocumentation · polgalois, PARI/GP 2.19.0Degree limits, output conventions, and explicit precision warning.Source
  • SageGaloisDocumentation · Polynomial_rational_flint.galois_group; galois_group_davenport_smith_test; NumberField.galois_group, SageMath 10.10Backend limits, certified specialized test, root-action conventions, and relative-field warning.Source

Example

Example

For f=x4+2x+2f=x^4+2x+2, the following data determine the group:

  1. Eisenstein at 22, proving irreducibility.
  2. The resolvent R=T3−8T−4R=T^3-8T-4, with no rational root among ±1,±2,±4\pm1,\pm2,\pm4.
  3. The discriminant Δ(f)=1616=16⋅101\Delta(f)=1616=16\cdot101, a nonsquare.

The quartic classification proves the group is S4S_4. These three exact tests form a certificate for the group.

A corresponding Magma command sequence is:

Zx<x> := PolynomialRing(Integers());
f := x^4 + 2*x + 2;
G, roots, S := GaloisGroup(f);
assert GaloisProof(f, S);
Order(G);

The commands illustrate the documented interface; they were not executed for this example. The preceding proof gives ∣G∣=24|G|=24.

References 2

Local Galois groups

For a rational polynomial, computing its group over Qp\mathbb Q_p is distinct from computing its group over Q\mathbb Q. If L/QL/\mathbb Q is the global splitting field and P∣p\mathfrak P\mid p, the local splitting-field group identifies with the decomposition subgroup DP⊆Gal⁡(L/Q)D_{\mathfrak P}\subseteq\operatorname{Gal}(L/\mathbb Q). The embedding depends on the choice of P\mathfrak P, up to conjugacy.

Doris (2020) develops local algorithms using ramification towers, global models, and resolvents. A global model supplies a tractable overgroup; local factorization of resolvents distinguishes the desired subgroup. The base field therefore remains part of the result even when global auxiliary calculations are used.

Certification also depends on the implementation. Remark 3.5 of the paper identifies a heuristic complex-root bound in the then-current implementation. The author's package documentation later describes an exact pp-adic input mode that produces proved results. The mode and verification outcome are part of the computation record; an algorithm does not by itself certify a finite-precision implementation.

References 2

Computations in families

For a parameterized family, state the parameter range and exceptional cases. A computation proves only the tested cases unless a theorem reduces the whole family to that finite calculation.

Factor degrees identify the Frobenius cycle type, which may correspond to several conjugacy classes in the Galois group. Dokchitser and Dokchitser construct invariants that distinguish these classes when the arithmetic application requires them.

A reproducible group computation records the exact polynomial, ground field, permutation action, algorithm and verification data. Witness primes, resolvents and the discriminant often give a short proof that can be checked independently of the original software.

References 2

Fixed fields and splitting fields

Once G=Gal⁡(L/K)G=\operatorname{Gal}(L/K) is known as a permutation group, relative invariants construct a defining polynomial for LUL^U, where U≤GU\le G. Fieker–Sutherland construct splitting fields along a subgroup chain

G=G0>G1>⋯>Gr=1.G=G_0>G_1>\cdots>G_r=1.

The corresponding field tower has successive degrees [Gi−1:Gi][G_{i-1}:G_i]. This avoids repeated factorization over the growing tower. Their algorithms cover number fields and several rational-function-field settings, with certified reconstruction of exact coefficients from root approximations.

References 1

Questions

Research directionAlgorithms and certificates

How can a computed group be certified?

Scope. Reproducible computations for explicit polynomial families

Short certificates and verifiers for subgroup containment and noncontainment can simplify computations in a specified family. The quartic example illustrates such a certificate. The problem is to find suitable certificates for the chosen family, rather than to establish that Galois-group certification is possible.

References 2
Discuss this question →

Related topics

References

  1. Galois Theory

    Cox, David A. Edition 2. John Wiley & Sons, 2012.

    Read the source
  2. Computation of Galois groups of rational polynomials

    Fieker, Claus and Klüners, Jürgen. LMS Journal of Computation and Mathematics, 17(1), 141–158, 2014.

    Read the source
  3. The determination of Galois groups

    Stauduhar, R. P. Mathematics of Computation, 27(124), 981–996, 1973.

    Read the source
  4. Solvability by radicals is in polynomial time

    Landau, Susan and Miller, Gary Lee. Journal of Computer and System Sciences, 30(2), 179–208, 1985.

    Read the source
  5. Magma Handbook: Galois groups

    Magma Computational Algebra System.

    Read the source
  6. PARI/GP reference manual: general number fields and polgalois

    The PARI Group.

    Read the source
  7. SageMath reference manual: polynomial and number-field Galois groups

    The Sage Developers.

    Read the source
  8. Galois groups of cubics and quartics (not in characteristic 2)

    Conrad, Keith. Author-hosted expository note.

    Read the source
  9. Algebraic Number Theory

    Neukirch, Jürgen. Springer, Grundlehren der mathematischen Wissenschaften, vol. 322, 1999.

    Read the source
  10. Computing the Galois group of a polynomial over a p-adic field

    Doris, Christopher. International Journal of Number Theory, 16(8), 1767–1801, 2020.

    Read the source
  11. Identifying Frobenius elements in Galois groups

    Dokchitser, Tim and Dokchitser, Vladimir. Algebra & Number Theory, 7(6), 1325–1352, 2013.

    Read the source
  12. The L-functions and Modular Forms Database: number fields and Galois groups

    The LMFDB Collaboration.

    Read the source
  13. Computing splitting fields using Galois theory and other Galois constructions

    Fieker, Claus and Sutherland, Nicole. Journal of Symbolic Computation, 116, 243–262, 2023.

    Read the source