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 , clear denominators, remove content, and compute a squarefree factorization. A transitive-group label describes the action for an irreducible factor. If 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- input, the output should specify the subgroup of 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
- Cox2012Source
- FiekerKlueners2014 · Introduction and Section 2Source
Subgroup descent
- Irreducibility and separability. A factorization or irreducibility certificate establishes the input assumptions.
- Structural restrictions. The discriminant, reciprocity, composition, and known intermediate fields restrict the ambient permutation group.
- Local factorizations. Exact irreducible factorizations at good primes determine cycle types.
- Subgroup tests. Primitive-group theorems, relative resolvents, and subgroup descent eliminate incompatible candidates.
- 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
- Stauduhar1973Source
- FiekerKlueners2014 · Sections 3 and 7Source
Solvability by radicals
Landau–Miller (1985) give a polynomial-time decision procedure for solvability by radicals over , 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 for a degree- polynomial with group .
References 1
- LandauMiller1985 · Introduction and Sections 2–4Source
Software
| Tool | Scope | Verification data |
|---|---|---|
| Magma | Native 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.19 | polgalois requires irreducible input over , 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.10 | The 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 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 and certify and , while 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 , the following data determine the group:
- Eisenstein at , proving irreducibility.
- The resolvent , with no rational root among .
- The discriminant , a nonsquare.
The quartic classification proves the group is . 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 .
References 2
- ConradCubicQuartic · Table 5 and Theorem 3.6Source
- MagmaGaloisDocumentation · GaloisGroup and GaloisProofSource
Local Galois groups
For a rational polynomial, computing its group over is distinct from computing its group over . If is the global splitting field and , the local splitting-field group identifies with the decomposition subgroup . The embedding depends on the choice of , 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 -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
- Neukirch1999 · Decomposition groups and completionsSource
- Doris2020 · Sections 1.1–4 and Remark 3.5; linked author package documentation for the exact-input modeSource
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
- DokchitserDokchitser2013Distinguishing Frobenius classes beyond their cycle types.Source
- LMFDBFieldsGroupsComparison data for number fields and transitive groups.Source
Fixed fields and splitting fields
Once is known as a permutation group, relative invariants construct a defining polynomial for , where . Fieker–Sutherland construct splitting fields along a subgroup chain
The corresponding field tower has successive degrees . 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
- FiekerSutherland2023 · arXiv v3: §3, Theorem 4; §4, Algorithms 2–4 and Theorems 5–6Source
Questions
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
- FiekerKlueners2014 · Section 7Source
- MagmaGaloisDocumentation · GaloisProofSource
Related topics
Resolvents and subgroup tests
Relative invariants certify containment in smaller subgroups.
UsesFrobenius and factorization modulo primes
Factorization at small primes restricts the candidate groups.
UsesPolynomial factorization algorithms
Exact factors and irreducibility checks establish the input assumptions.
Applies toEulerian polynomials
Computed tables certify finite ranges; an all-degree result requires a separate argument.
References
- Galois Theory
Cox, David A. Edition 2. John Wiley & Sons, 2012.
Read the source - 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 - The determination of Galois groups
Stauduhar, R. P. Mathematics of Computation, 27(124), 981–996, 1973.
Read the source - 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 - Magma Handbook: Galois groups
Magma Computational Algebra System.
Read the source - PARI/GP reference manual: general number fields and polgalois
The PARI Group.
Read the source - SageMath reference manual: polynomial and number-field Galois groups
The Sage Developers.
Read the source - Galois groups of cubics and quartics (not in characteristic 2)
Conrad, Keith. Author-hosted expository note.
Read the source - Algebraic Number Theory
Neukirch, Jürgen. Springer, Grundlehren der mathematischen Wissenschaften, vol. 322, 1999.
Read the source - 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 - Identifying Frobenius elements in Galois groups
Dokchitser, Tim and Dokchitser, Vladimir. Algebra & Number Theory, 7(6), 1325–1352, 2013.
Read the source - The L-functions and Modular Forms Database: number fields and Galois groups
The LMFDB Collaboration.
Read the source - 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
Comments
Any comments are welcome. Comments appear after the site owner approves them. Privacy policy.