Twenty-seven million cubics, sorted by their symmetry

A cubic with whole-number coefficients has three roots, and its Galois group records which rearrangements of those roots preserve every rational relation among them. There are only three possibilities. If the cubic factors over the rationals, one root is rational and the question collapses to a quadratic. If it does not, the group is either all six permutations of the roots, $S_3$, or the three rotations, $A_3$, and the quintic essay gave the test that separates them: the group is $A_3$ exactly when the discriminant is a perfect square.

That essay closed on the question of how often each group occurs. Bartel van der Waerden asked it in 1936 and answered it in rough form: almost every polynomial has the full symmetric group, and the exceptions thin out as the coefficients grow. “Almost every” hides two separate questions — how thin, and thin in what way — and for cubics both can be settled by counting. Every monic cubic $x^3 + ax^2 + bx + c$ with $|a|, |b|, |c| \le 150$ is sorted here by its group. There are $301^3 = 27{,}270{,}901$ of them. The sort is exact, because each test in it is a finite computation on whole numbers.

Three tests, each a finite computation #

The first test is for a rational root. A monic polynomial with whole coefficients can only have whole-number rational roots, and any such root divides the constant term. So deciding whether $x^3 + ax^2 + bx + c$ factors means trying the divisors of $c$, positive and negative, and if $c = 0$ the root $0$ is there already. A cubic that has no rational root cannot factor at all, since any factorisation of a cubic includes a factor of degree one.

The second test is the discriminant, which for a monic cubic is

$$D = a^2b^2 - 4b^3 - 4a^3c - 27c^2 + 18abc.$$

It is the product of the squared differences of the roots, so it is a symmetric function of them and therefore a whole number computable from the coefficients. Every even permutation of the roots leaves its square root, the product of the differences themselves, unchanged; every odd one changes its sign. If the group contains an odd permutation, $\sqrt D$ is not fixed by the group and so is not rational. If the group is $A_3$, $\sqrt D$ is fixed and is rational, and since $D$ is a whole number its square root must then be a whole number too.

The third test is not needed for cubics: once a cubic is irreducible its group acts transitively on three roots, and the only transitive groups on three points are $A_3$ and $S_3$. So three outcomes, three tests, and a perfect-square check on a number that never exceeds a few hundred billion — well inside exact arithmetic. The figure above is the slice $a = 0$ of the box, with $H = 30$, and it already shows the shape of the answer. The 309 reducible cubics lie on lines: a whole-number root $r$ forces $r^3 + br + c = 0$, which is the line $c = -r^3 - rb$ in the $(b, c)$ plane, and there is one line for each $r$ whose line crosses the square. The twenty cyclic cubics are scattered with no visible pattern. Everything else, 3,392 of the 3,721, has the full group.

How the counts grow #

Let $H$ run from 2 to 150 and keep a running count for each box. The total is $(2H + 1)^3$, growing like $H^3$, and the question is how each kind of exception grows against it.

On logarithmic axes a quantity growing like $H^k$ is a straight line of slope $k$, and the figure has three. The full-group line hugs the total from the start; by $H = 150$ it holds 26,928,280 of the 27,270,901, all but about one cubic in eighty. The reducible line has slope 2. The cyclic line has slope about 1.5 and sits two orders of magnitude below the total at small $H$ and three and a half orders below it at the end.

So van der Waerden’s statement takes a precise form for cubics. The cubics that do not have the full group number about $H^2$ in a box of $H^3$, a share falling like $1/H$, and almost all of them are reducible. The cyclic cubics, which are the only genuinely different symmetry a cubic can have, are a vanishing share even of the exceptions: about one in thirty-seven at $H = 150$ and falling like $H^{-1/2}$.

This is the pattern the quintic essay described for every degree. Van der Waerden conjectured that among monic polynomials of degree $n$ with coefficients up to $H$, those without the full group number at most a constant times $H^{n-1}$, which is exactly how the reducible ones grow; Manjul Bhargava proved it in 2021 after decades in which the best bounds were weaker powers. For cubics the counts above are that theorem’s first case, read off the box rather than derived.

Constants settling, and what the 1/H means #

A slope says how a count grows; the constant says how large it is. Divide each count by its power of $H$ and the curves should flatten.

The reducible count divided by $H^2$ creeps upwards and settles near 14.8 at $H = 150$; a longer run of the same count to $H = 300$, too slow to repeat inside a figure, reached 14.95. The cyclic count divided by $H^{3/2}$ is flat from $H = 100$ on at about 5.0, wobbling by a few per cent. And $H$ times the share of exceptions levels at about 1.9.

The last number is the plainest summary. In a box of side $2H + 1$, every row of $2H + 1$ cubics contains on average about one exception, and in a large box the share of cubics without the full group is about $1.9/H$. At $H = 150$ that is one cubic in eighty; at $H = 1{,}000$ it would be one in five hundred. The full group is not merely the commonest. In the limit it is everything.

That the reducible count should be a constant times $H^2$, and not $H^2$ times a slowly growing factor, is not obvious. Each whole number $r$ is the root of some cubics in the box, and there are infinitely many possible $r$. If the contributions of different roots did not shrink fast enough, their sum would add a logarithm, as sums over divisors often do. The next figure shows why it does not.

Where the reducible cubics come from #

Sort the reducible cubics by the smallest whole number, in absolute value, that is a root.

A root of $0$ means $c = 0$, which happens for $121^2 = 14{,}641$ of the cubics in the box with $H = 60$ — every choice of $a$ and $b$ with the constant term zero. A root of $1$ means $1 + a + b + c = 0$ and a root of $-1$ means $-1 + a - b + c = 0$: each is a single linear condition on three coefficients, so each holds on a plane through the box, and there are 21,600 such cubics. Together they are 69% of everything reducible.

A root $r$ of larger size forces $c = -r(r^2 + ar + b)$. For the constant term to stay inside the box the bracket must be smaller than $H/|r|$, which confines $r^2 + ar + b$ to a narrow band; and for the bracket itself to be small with $|a|$ and $|b|$ at most $H$, $a$ must lie within about $H/|r|$ of $-r$. The two restrictions together cut the admissible pairs $(a, b)$ by a factor near $r^2$. That is the $1/r^2$ curve in the figure, and the sum $\sum 1/r^2$ converges. The reducible count is a constant times $H^2$ because the roots that can occur get rarer like an inverse square, and the constant near 14.8 is, in effect, that convergent sum with the planes for $0$ and $\pm 1$ added in.

The same picture is visible in the hero figure. The lines $c = -r^3 - rb$ for larger $r$ are steeper, so each crosses the square along a shorter stretch, and lines for $|r| \ge 4$ in the slice with $H = 30$ are nearly vertical and touch only a handful of cells.

Squares where chance does not put them #

The cyclic cubics grow like $H^{3/2}$, and it is natural to ask whether that exponent can be guessed. A cubic is cyclic when its discriminant is a perfect square, and a whole number of size $X$, chosen blindly, is a square with probability about $1/(2\sqrt X)$ — there are $\sqrt X$ squares below $X$, spread over $X$ numbers, and they thin out as $1/\sqrt X$. Treat each discriminant as such a blind number, add up the chances, and compare with the true count.

The guess gets the growth nearly right, and for a reason worth saying. A typical discriminant in the box is of size $H^4$, so the typical chance is about $1/H^2$ and a crude estimate would give only $H^3/H^2 = H$ squares. But discriminants are not typically sized. A discriminant is small when two roots are close together, and cubics with nearly repeated roots are a substantial part of the box; for them the chance of a square is large. Summing over the true distribution of discriminants rather than a typical one gives slope 1.44, close to the measured 1.54.

What the guess gets wrong is the constant, and the error is a steady factor of about four. Square discriminants are four times commoner than squares among random numbers of the same sizes, at every $H$ from 20 to 150.

Part of the factor has a clean explanation. Ludwig Stickelberger proved in 1897 that the discriminant of any polynomial with whole coefficients leaves remainder 0 or 1 on division by 4 — never 2 or 3. Every square also leaves remainder 0 or 1. So a discriminant is confined in advance to the half of the residues where all the squares live, and that alone doubles its chance of being one. The census checks Stickelberger’s congruence on every irreducible cubic among the 531,441 with coefficients up to 40 and finds no exception. Congruences of the same kind modulo other primes — conditions a discriminant must satisfy that a random number need not — plausibly account for the rest of the factor. That is a guess, though, and nothing in these figures confirms it: the factor of two is the only part of the four that this essay can name.

The prime that every square carries #

A square discriminant is not just any square. Its square root has a structure inherited from the field the cubic’s roots generate.

The four cyclic cubics with every coefficient at most 2 are $x^3 + x^2 - 2x - 1$, $x^3 - x^2 - 2x + 1$ and the two obtained by reversing their coefficients, and all four have discriminant $49 = 7^2$. Their roots are $2\cos(2\pi k/7)$ for $k = 1, 2, 3$ and their negatives — the sums of seventh roots of unity that obey a smaller equation. Allow coefficients up to 3 and six more appear, all with discriminant $81 = 9^2$, including $x^3 - 3x + 1$, whose roots are $2\cos(2\pi k/9)$ and whose real roots no real radicals reach.

The pattern continues through the whole census. The square root of every cyclic cubic’s discriminant is divisible either by a prime that leaves remainder 1 on division by 3 — 7, 13, 19, 31, 37, 43 — or by 9. Primes leaving remainder 2, such as 2 and 5, do occur, but never alone. This is the conductor: a cyclic cubic field is contained in a field of roots of unity, and the smallest such field is generated by the $f$-th roots for a number $f$ built only from primes $\equiv 1 \pmod 3$ and possibly 9. The field’s own discriminant is $f^2$. A particular polynomial generating the field can have a larger discriminant than the field does, by a square factor that the integers a field contains measures as the index, and the cool primes enter only there.

So every cyclic cubic is secretly a sum of roots of unity — Kronecker and Weber’s theorem for the case at hand — and the scattered dots in the hero figure each point at a field of roots of unity of some conductor. The commonest are those of the smallest conductors, 7, 9 and 13, because those fields have generating polynomials with the smallest coefficients.

Small boxes disagree with large ones #

A census of a box is a list of facts about that box, and three of the box’s features mislead if read as statements about all cubics.

The first is the ratio of reducible to cyclic. At $H = 2$ there are 53 reducible cubics and 4 cyclic ones; at $H = 150$ the ratio is about 36 to 1. It keeps growing, like $H^{1/2}$, and a census at any fixed size gives a fixed number that is not the limit.

The second is the constant for the cyclic count. It looks flat at about 5.0 from $H = 100$ to $H = 200$ and was 4.88 at $H = 300$, so the figure cannot exclude a slow drift — a factor of a power of $\log H$ would look very like this over a range of three. Whether the true count is exactly of order $H^{3/2}$ is a question about the distribution of conductors and indices that a census cannot answer by extension.

The third is the shape of the slice. The hero figure shows $a = 0$, the cubics with no square term, and those are not typical: any cubic can be moved to $a = 0$ by the substitution $x \to x - a/3$, but only when $3$ divides $a$ does the result keep whole coefficients. The slice is a convenient plane, not a random sample of the box, and its counts — twenty cyclic cubics among 3,721 — are not the box’s share.

What the counting cannot show #

Counting establishes what is in a box. It does not establish asymptotic laws, and every slope and constant quoted here is a measurement over $H \le 150$, with a check to 300, not a theorem. What is proved independently of the figures is the statement they illustrate: Bhargava’s theorem that the exceptions number at most a constant times $H^2$ for cubics, and the elementary argument for the reducible ones that the $1/r^2$ figure makes visible.

The figures also cannot show why a particular cubic has the group it has beyond the two tests. The discriminant test certifies $A_3$; it does not exhibit the rotation of the roots. That rotation is visible only when the roots are written down, as they are for the seventh roots of unity, and for most of the 9,138 cyclic cubics in the box nobody has written them down.

Nor do the figures say anything about real and complex roots. A cyclic cubic must have three real roots, since a square discriminant is positive, but an $S_3$ cubic can have one real root or three, and the census does not separate them. Almost none of the roots of a random polynomial are real when the degree is large; for cubics the box gives a definite share for each kind, and it is another count of the same type.

Still open: the exponents for every smaller group #

For cubics the exponents are $3$, $2$ and $3/2$, with the last one clear in the census and the proof of its exact order a matter of counting cyclic cubic fields and their generators. For higher degree the situation is less tidy. Bhargava’s theorem bounds all the exceptions together by $H^{n-1}$ and shows that reducible polynomials are most of them, but it does not give the count for each smaller group separately. For most groups in most degrees the true exponent is not known, and where it is known the proof is specific to the group.

The quartics are the first case where the question has real content, because a quartic can have five different groups and they come in different numbers. Three ways to pair four roots gave the tool that decides them — a resolvent cubic built from the pairings of the roots — and that tool makes a census of the quartics as exact as this one. Whether the smaller groups line up in order of size, or in some other order, is a question the box can at least begin to answer. So is whether the discriminant’s square is as commonly found there as among the cubics.

There is also a question this census raises and cannot settle. The factor of four in the square discriminants is half explained by Stickelberger’s congruence. The other half presumably comes from congruences modulo other primes, conditions satisfied by discriminants and not by random numbers, and a sharp form of the heuristic that included them would predict the constant 5.0 rather than merely the exponent. Whether such a heuristic gives the right constant here, and in which degrees it fails, is not settled.

A rule of thumb with a precise form #

“Almost every polynomial has the largest possible group” is the kind of statement that sounds true and vague at once. Counted, it is neither vague nor only true. For cubics the exceptions number about $15H^2$, nearly all of them because a small whole number happens to be a root, and the share without the full group falls like $1.9/H$. The one genuinely different symmetry, the rotation of three roots, occurs about $5H^{3/2}$ times. It does so four times as often as a square would turn up among random numbers, because discriminants are confined to the residues where squares live. And every one of those cyclic cubics carries in its discriminant a prime that ties it to a field of roots of unity — the exact reason each one exists.

What the generic case looks like is the lattice the Galois correspondence builds at its fullest. All six permutations act, every intermediate field is present, and the cubic is solvable only through the radicals Cardano used. The census says that this full lattice is not a special case to be hoped for. It is what a polynomial chosen from a box nearly always has, and the smaller lattices are the coincidences — rare, countable, and each with a reason.