How a polynomial breaks modulo the primes

A polynomial with whole-number coefficients can be read modulo any prime $p$: reduce each coefficient to its remainder, and the result is a polynomial over the field with $p$ elements. There it factors into irreducible pieces, as every polynomial over a field does, and the degrees of those pieces form a pattern — for a cubic, one of $1 + 1 + 1$, $1 + 2$ or $3$.

The pattern changes from prime to prime, and at first sight erratically. But it is not erratic. Which patterns occur, and how often, is decided by a single object attached to the polynomial: its Galois group, the group of symmetries of its roots that the correspondence between subgroups and fields is built from. The primes take a census of that group, one element at a time, and the census comes out in exact proportion.

Two cubics, prime by prime #

The two columns behave differently from the first row. Take $x^3 - 3x + 1$. Modulo 17 it has three roots; modulo 19 three; modulo 37 and 53 three; modulo every other prime in the table, none. It never has exactly one root. And the primes where it splits are recognisable: 17, 19, 37 and 53 leave remainder 8, 1, 1 and 8 on division by 9. The rule — split exactly when $p \equiv \pm 1 \pmod 9$ — holds for every prime in the table, and the figure checks it. A cubic that behaves this way is rare: most cubics with integer coefficients break in all three ways, and the ones that never produce the pattern $1 + 2$ are exactly those whose three roots can each be written as polynomials in any one of them.

Now $x^3 - 2$. Modulo every prime that is 2 more than a multiple of 3 — 5, 11, 17, 23, 29, 41, 47, 53, 59 — it has exactly one root, $1 + 2$. That has a quick explanation: when $p \equiv 2 \pmod 3$, cubing is a one-to-one map on the nonzero remainders, so 2 has exactly one cube root. Modulo primes that are 1 more than a multiple of 3 it either splits completely (31, 43) or stays whole (7, 13, 19, 37). And there the pattern is not decided by any congruence: 31 and 43 split, 37 does not, and no modulus separates them. As the essay on which primes a form takes showed, the primes that split are exactly those of the form $x^2 + 27y^2$, a condition no remainder can express.

The symmetry group of three cube roots #

The difference between the two cubics is a difference between their Galois groups.

$x^3 - 2$ has three complex roots: the real cube root $\sqrt[3]{2}$ and two complex ones, $\sqrt[3]{2}\,\omega$ and $\sqrt[3]{2}\,\omega^2$, where $\omega$ is a primitive cube root of unity. Any permutation of the three roots that respects every polynomial relation among them with rational coefficients is a symmetry, and for $x^3 - 2$ all six permutations qualify. The group is $S_3$, the symmetry group of a triangle: the identity, two rotations and three flips.

$x^3 - 3x + 1$ is different. Its three roots are real, $2\cos(2\pi/9)$, $2\cos(4\pi/9)$ and $2\cos(8\pi/9)$, and each is a polynomial in any other: if $\theta$ is one root, the others are $\theta^2 - 2$ and $2 - \theta - \theta^2$. So a symmetry that fixes one root fixes them all, and the only symmetries are the three rotations. Its group is $C_3$, the cyclic group of order three.

The difference is visible in the degrees. The splitting field of $x^3 - 2$ — the smallest field containing all three roots — has degree six over the rationals, because adjoining $\sqrt[3]{2}$ gives a real field of degree three that cannot contain the complex roots, and adjoining $\omega$ doubles it. The splitting field of $x^3 - 3x + 1$ has degree three: adjoining one root already brings the other two. Degrees multiply up a tower, and the order of the Galois group is the degree of the splitting field, so a group of order six and a group of order three were visible before a single prime was examined.

Frobenius: one symmetry for each prime #

The bridge between primes and symmetries is the map that raises to the $p$-th power. Over the field with $p$ elements, $a^p = a$ for every element — Fermat’s little theorem — and the map $x \mapsto x^p$ fixes exactly the elements of that field. Applied to the roots of the polynomial, reduced modulo $p$, it permutes them, and the permutation it induces is an element of the Galois group: the Frobenius element of $p$.

The factorisation pattern of the polynomial modulo $p$ is the cycle type of that permutation. A root fixed by Frobenius satisfies $x^p = x$ and so lies in the field with $p$ elements: it is a root modulo $p$, a linear factor. Roots swapped in a 2-cycle are fixed by Frobenius twice over, so they lie in the field with $p^2$ elements and are the roots of an irreducible quadratic factor. Roots in a 3-cycle give an irreducible cubic. So:

• identity → $1 + 1 + 1$;
• a flip, which swaps two roots and fixes one → $1 + 2$;
• a rotation, a 3-cycle → $3$.

Now the table’s behaviour is forced. $x^3 - 3x + 1$ has no flips in its group, so the pattern $1 + 2$ cannot occur for it — and it never does. $x^3 - 2$ has all three kinds of element, and all three patterns occur.

A single prime shows the mechanism. Modulo 7, the cubes of the nonzero remainders are only 1 and 6, so 2 is not a cube and $x^3 - 2$ has no root: it is irreducible, and its roots live in the field with $7^3 = 343$ elements. Every finite field is a single cycle under multiplication, and in that field the map $x \mapsto x^7$ sends a root $r$ to $r^7 = r \cdot (r^3)^2 = 4r$, then to $16r = 2r$, then back to $8r = r$. It cycles the three roots — a rotation, as the pattern $3$ says. Modulo 31, by contrast, 2 is a cube, $4^3 = 64 \equiv 2$, and so are $4 \cdot 5 = 20$ and $4 \cdot 25 = 100 \equiv 7$, because 5 is a cube root of unity modulo 31. All three roots lie in the field with 31 elements, $x \mapsto x^{31}$ fixes each of them, and Frobenius is the identity.

The census comes out in proportion #

Frobenius explains which patterns occur. How often each occurs is a theorem of Nikolai Chebotarev from 1922: as $p$ runs over the primes, the Frobenius element is spread evenly over the group — each conjugacy class is hit with frequency proportional to its size.

For $x^3 - 3x + 1$ the group has one identity and two rotations, so the prediction is splitting a third of the time and staying whole two-thirds — and the bars are $0.333$ and $0.667$ to within sampling. For $x^3 - 2$ the six elements are one identity, three flips and two rotations, predicting $1/6$, $1/2$ and $1/3$ for the three patterns, and those are the bars. For $x^4 - 2$, whose roots are $\pm\sqrt[4]{2}$ and $\pm i\sqrt[4]{2}$, the group is the eight symmetries of a square, and the four patterns occur in the proportions $1/8$, $1/4$, $3/8$ and $1/4$ of its cycle types — the identity, the two diagonal flips that fix two corners, the three elements that pair the corners off, and the two quarter-turns.

Why should each symmetry be picked in proportion? A heuristic makes it plausible. The primes carry no preference among the symmetries of the roots, because the rational numbers cannot tell conjugate roots apart — any statement about them that the primes could “see” would be a polynomial relation with rational coefficients, and the symmetries preserve all of those. So the Frobenius elements should be spread over the group as evenly as the group’s own structure allows, which is evenly over each conjugacy class. Chebotarev’s proof makes this precise with $L$-functions, as Dirichlet’s did for residue classes, and the heuristic is the reason the answer is the one it is.

The convergence is the density theorem at work, and its rate is itself a deep question: how quickly the shares settle is controlled by the zeros of an $L$-function attached to the polynomial, just as the error in counting primes is controlled by the zeros of the zeta function.

Irreducible, and reducible modulo every prime #

The fourth polynomial in the census is the most surprising, and it is an old friend: $x^4 - 10x^2 + 1$ is the minimal polynomial of $\sqrt 2 + \sqrt 3$, found by counting powers in a space of dimension four.

Its four roots are $\pm\sqrt2 \pm \sqrt3$, and its Galois group consists of the four sign changes. Every one of them has order at most two, so there is no four-cycle in the group, and by Frobenius the polynomial can never stay irreducible modulo a prime. Yet it is irreducible over the rationals. A polynomial that is irreducible over the integers and reducible modulo every single prime sounds impossible, and the elementary reason is a small miracle of its own.

The squares modulo an odd prime form a subgroup of index two in the nonzero remainders: the product of two non-squares is a square. So if 2 and 3 are both non-squares modulo $p$, their product 6 is a square. One of the three is therefore always a square, and each gives a factorisation: $x^4 - 10x^2 + 1 = (x^2 - 2\sqrt2\,x - 1)(x^2 + 2\sqrt2\,x - 1)$, $(x^2 - 2\sqrt3\,x + 1)(x^2 + 2\sqrt3\,x + 1)$ or $(x^2 - 5 - 2\sqrt6)(x^2 - 5 + 2\sqrt6)$, each of which has coefficients modulo $p$ as soon as the square root in it exists there. The table checks every prime to 79 and the census every prime to 20,000; the argument covers them all.

The lesson reaches beyond the example. A standard way to prove a polynomial irreducible over the integers is to find one prime modulo which it is irreducible. For $x^4 - 10x^2 + 1$ that test fails at every prime, not because the polynomial is reducible but because its Galois group has no element of the right cycle type. The test is sound and incomplete, and the Galois group says exactly when it is incomplete.

From Dirichlet to Chebotarev #

The density theorem is the natural completion of Dirichlet’s theorem on primes in progressions, which that essay left as a debt. Dirichlet’s theorem says that primes are spread evenly among the residue classes modulo $m$ coprime to $m$. Seen through Galois theory, that is Chebotarev’s theorem for the polynomial $x^m - 1$: its Galois group is the group of units modulo $m$, the Frobenius element of $p$ is simply $p$ modulo $m$, and “evenly over the group” is “evenly over the residue classes”. Chebotarev’s theorem does the same thing for every polynomial, including those like $x^3 - 2$ whose splitting primes no congruence can describe.

It also explains the boundary that the essay on quadratic forms found. The primes of the form $x^2 + y^2$ are described by a congruence because the corresponding polynomial, $x^2 + 1$, has an abelian Galois group; the primes of the form $x^2 + 27y^2$ are not, because the corresponding polynomial is $x^3 - 2$, whose group $S_3$ is not abelian. Class field theory is the statement that the abelian case is always governed by congruences, and the non-abelian case is where the Langlands programme begins.

What the counts show and what they do not #

Every factorisation is exact, every share is a count. The patterns are computed by distinct-degree factorisation over the field with $p$ elements — a procedure with no rounding — and checked against a brute-force count of roots in the table. The shares in the census are ratios of counts. The predictions are exact fractions from the group. The agreement between them is measured, and a percentage point is the tolerance.

The census omits the primes that divide the discriminant. At 2 and 3 for $x^3 - 2$, at 3 for $x^3 - 3x + 1$, and at 2 and 3 for $x^4 - 10x^2 + 1$, the polynomial has repeated roots modulo $p$, Frobenius is not a well-defined permutation, and the pattern is not a cycle type. Finitely many primes are excluded, which does not change any density.

The table’s congruence for $x^3 - 3x + 1$ is checked, not derived. The figure checks that the cubic splits exactly when $p \equiv \pm 1 \pmod 9$ for every prime it lists. The reason is that its roots are $2\cos(2\pi k/9)$, which live in the field generated by the ninth roots of unity, and there the Frobenius element of $p$ is just $p$ modulo 9 acting on the exponents; a root is fixed when $p \equiv \pm 1$. The argument is Dirichlet’s in miniature, and the table only confirms it on its first fourteen primes.

The theorem is about limits. Twenty thousand primes give shares within a percentage point, but Chebotarev’s theorem is a statement about the limit, and nothing finite proves it. The rate of convergence depends on the generalised Riemann hypothesis for the relevant $L$-functions, and the best unconditional error bounds are much weaker than what the figures show.

Still open: how soon the census is fair #

Chebotarev’s theorem says the proportions come out right eventually. How soon is open in a precise sense: the least prime whose Frobenius element lies in a given conjugacy class is conjectured to be small — polynomial in the logarithm of the discriminant — and this is known only assuming the generalised Riemann hypothesis. Unconditionally, the known bounds are polynomial in the discriminant itself, exponentially worse.

There is also the inverse Galois problem: every finite group is conjectured to be the Galois group of some polynomial with rational coefficients, so that every group has its own census among the primes. It is known for all soluble groups and for many simple ones, and open in general. The census exists for every polynomial; whether every group can be made to hold one is not known.

And there is a question hiding in the second figure’s ticks. Two different polynomials can have the same census — the same shares of every factorisation pattern — without having the same splitting field, because different groups can have the same proportions of cycle types. Which fields are determined by their factorisation statistics, and which pairs are “arithmetically equivalent” without being the same, has a complete answer in small degrees and examples of equivalent pairs from degree seven on, found by Gassmann in 1926; a general description of when the census determines the field is not known.

A group read off the primes #

A polynomial’s roots are permuted by its symmetries, and each prime picks out one symmetry — the one that raising to the $p$-th power induces. The factorisation of the polynomial modulo $p$ is that symmetry’s cycle type, and over all primes each symmetry is picked in exact proportion. So the Galois group, an abstract object built from the roots, can be recovered from arithmetic modulo primes alone: factor the polynomial modulo enough primes, count the patterns, and the shares are the shape of the group.

That inversion is what makes the subject remarkable. The Galois group was defined by looking at the roots, which live in the complex numbers or in some abstract extension, and the primes know nothing of either. Yet Fermat’s little theorem, applied field by field, turns every prime into a symmetry of the roots, and the primes collectively know the group exactly — which elements it has, how many of each kind, everything but the labels. A question about symmetry, asked of the integers, is answered by counting. It is the same move this subject has made before, turning a structure into a census, and it has rarely been made to such effect: Chebotarev’s theorem is one of the tools by which modern number theory reads non-abelian symmetry off the primes, and the four bars of the census figure are its simplest possible demonstration.