Class groups drawn at random

In the whole numbers every number factors into primes in one way. In a larger number system, such as the numbers $a + b\sqrt{-5}$, it can fail: $6 = 2 \times 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$, and none of those four factors breaks down further. How badly it fails is measured by a finite group, the class group, and its size, the class number. Counting reduced quadratic forms computes it: for the imaginary quadratic fields with discriminants $-3, -4, -7, -8, -11, -15, -20, -23, \ldots$ the class numbers are $1, 1, 1, 1, 1, 2, 2, 3, \ldots$, and they grow irregularly, roughly like the square root of the discriminant.

Individually the class numbers look arbitrary. Statistically they have structure, and the structure was described in 1984 by Henri Cohen and Hendrik Lenstra in a conjecture that is part theorem, part heuristic and part experiment. This essay measures it over every imaginary quadratic field with discriminant down to $-300{,}000$ — 91,183 fields.

Three divides more often than it should #

The simplest question is how often a given prime divides the class number. If class numbers were ordinary whole numbers chosen without bias, 3 would divide one in three of them.

It divides 39.1 per cent of them. Five divides 22.6 per cent against 20, seven 15.3 against 14.3. For eleven the excess is not visible at this range; the prediction for it is only about one percentage point above one in eleven. The measured shares lie between the naive value and Cohen and Lenstra’s, which for 3 is

$$1 - \Big(1 - \tfrac13\Big)\Big(1 - \tfrac19\Big)\Big(1 - \tfrac1{27}\Big)\cdots \approx 0.4399.$$

The class numbers were computed by counting reduced forms for every discriminant at once, a single pass over all triples $(a, b, c)$ with $|b| \le a \le c$ whose discriminant is in range, and checked against the direct count at sample discriminants. The single pass is what makes three hundred thousand discriminants cheap: every reduced form is visited once, and each visit adds one to the class number of its own discriminant, so the whole table costs about as much as listing the forms. The group structure is dearer, since it needs composition, and is computed only to $-20{,}000$.

The nine fields with class number one — discriminants $-3, -4, -7, -8, -11, -19, -43, -67, -163$ — appear exactly as Heegner, Baker and Stark proved, and no other.

Three classes, and a triangle of forms #

The smallest field whose class number is divisible by 3 has discriminant $-23$. Its reduced forms are $x^2 + xy + 6y^2$, $2x^2 + xy + 3y^2$ and $2x^2 - xy + 3y^2$: three classes, forming a cyclic group of order 3 in which the first form is the identity and the other two are inverses of each other. The primes the first form represents — 59, 101, 167, 173, … , besides 23 itself — split into principal ideals; the primes the other two represent, such as 2, 3 and 13, split into ideals that are not principal, and it is exactly those primes whose cubes, and not themselves, are represented by the first form. Which primes a form takes is decided by the group.

After $-23$ come $-31$, $-59$, $-83$ and $-107$, each with class number 3, and then fields with class numbers 6, 9, 12 and so on. Among the first few hundred discriminants the share divisible by 3 is close to a third, which is part of why the excess took so long to notice: it grows in as the discriminants grow, and the smallest cases say the naive thing.

Why the odd part and not the whole #

The prime 2 is left out of the table on purpose, because the even part of the class group is not random at all.

The table confirms Gauss’s genus theory across all 91,183 fields. A discriminant with $t$ distinct prime factors gives a class group whose elements of order two form a group of size exactly $2^{t-1}$, so the class number is divisible by $2^{t-1}$, and it is odd exactly when the discriminant is a prime or four or eight times a prime. The 13,018 fields with one prime in the discriminant all have odd class number; the other 78,165 all have even class number. Nothing about the 2-part is left to chance, which is why the random model is stated for the odd part. (Refined versions for the 2-part exist, and treat it after genus theory has taken its share.)

Groups weighted by their symmetries #

Cohen and Lenstra’s idea is that the odd part of the class group is a random finite abelian group — but not with every group equally likely. Each group $G$ is weighted by $1/|\mathrm{Aut}\, G|$, one over the number of its symmetries.

The weighting is the natural one from counting. A group with many automorphisms can be presented in many equivalent ways, and when isomorphism classes are counted by orbits and stabilisers, each class is weighted by one over its stabiliser, which is its automorphism group. Groups with few symmetries are, in this sense, more numerous. The cyclic group of order 3 has two automorphisms; the group $(\mathbb{Z}/3)^2$ has forty-eight. So among class groups whose 3-part has order 9, the prediction is that the cyclic one, with six automorphisms, should appear eight times as often as $(\mathbb{Z}/3)^2$.

From the weighting everything follows. The chance that $p$ does not divide the order of a random group is $\prod_{k \ge 1}(1 - p^{-k})$, which for $p = 3$ is $0.5601$; so $p$ divides it with chance $0.4399$. The chance that the group has exactly $r$ independent elements of order $p$ — its $p$-rank — is

$$\frac{p^{-r^2} \prod_{k \ge 1}(1 - p^{-k})}{\prod_{k=1}^{r}(1 - p^{-k})^2},$$

which for $p = 3$ gives 56.0, 42.0 and 2.0 per cent for ranks 0, 1 and 2. Neither number is a third or two thirds; both come from the weighting.

The same count extends to larger groups, and it shows how strongly symmetry is penalised. Of the groups of order 27, the cyclic one has 18 automorphisms, $\mathbb{Z}/3 \times \mathbb{Z}/9$ has 108, and $(\mathbb{Z}/3)^3$ has 11,232 — the number of invertible three-by-three matrices over the field of three elements. Weighted by the reciprocals, the cyclic group of order 27 should be six times as common as $\mathbb{Z}/3 \times \mathbb{Z}/9$ and more than six hundred times as common as $(\mathbb{Z}/3)^3$. A class group with three independent elements of order 3 is predicted to be very rare indeed, and the first imaginary quadratic field with one has a discriminant in the millions.

The weighting also explains why the prediction is not simply “3 divides with chance one third”. A random whole number is divisible by 3 one time in three. A random group, weighted by symmetries, has order divisible by 3 whenever it contains any element of order 3, and the cyclic groups of order 3, 6, 9, and so on — with few symmetries, so heavily weighted — pile up the chance to 44 per cent.

The approach is slow #

The measured 39.1 per cent is well short of 44.0, and the gap is not noise.

Band by band, the share climbs from about 36 per cent among the smallest discriminants to 40 per cent among the largest. The climb is real and slow. Manjul Bhargava, Arul Shankar and Jacob Tsimerman, and independently Takashi Taniguchi and Frank Thorne, found in 2013 the reason: the count of 3-torsion has a secondary term, negative, that shrinks only like the discriminant to the power $-1/6$. At a discriminant of three hundred thousand that term is still several per cent. The limit is approached so slowly that no feasible computation comes close to it, and early computations that seemed to contradict Cohen and Lenstra were seeing this term.

The one case that is proved #

One part of the prediction is a theorem, and it was proved before the prediction was made.

The number of classes whose cube is the identity is $3^r$ for 3-rank $r$: one, three or nine. Cohen and Lenstra’s weighting predicts that its average over fields is exactly 2. Harold Davenport and Hans Heilbronn proved in 1971 that it is: their theorem counts cubic fields, and each non-identity class of order 3 in an imaginary quadratic field corresponds to a cubic field of related discriminant, so counting cubic fields counts 3-torsion. The figure computes the group structure directly, by Dirichlet composition of forms, and finds the running average at 1.73 at $-20{,}000$ and rising — the same slow approach from below.

The correspondence behind the theorem is concrete. A subgroup of index 3 in the class group of a quadratic field gives, by class field theory, an extension of degree 3 of the quadratic field that is unramified, and inside it sits a cubic field whose discriminant is the quadratic field’s discriminant itself. Each pair of non-identity classes of order 3 gives one such cubic field. So counting the 3-torsion of class groups, on average over discriminants, is the same as counting cubic fields by discriminant, and Davenport and Heilbronn had counted those, by counting binary cubic forms in a region of space much as Gauss had counted binary quadratic forms.

That makes the 3-part of imaginary quadratic class groups the best understood case. The average of the 3-torsion is known; the chance that 3 divides the class number is only conjectured, because it needs the whole distribution rather than its average. For 5 and higher primes even the average is unproved.

Ranks one and two #

The composition that counts 3-torsion also gives the 3-rank of every group.

The shape of the prediction is right: rank zero commonest, rank one next, rank two rare. The computation also tests the weighting directly. Among the 525 fields whose class group has a 3-part of order exactly nine, 512 have the cyclic group and 13 have $(\mathbb{Z}/3)^2$: the group with fewer symmetries dominates, as the weighting says, and at this range it dominates even more than the eight to one the weighting predicts for the limit. The numbers are shifted towards rank zero, which is the same deficit in divisibility by 3 seen band by band, larger here because the range is smaller. Rank two is five times rarer than the limit, and it is the most sensitive to the slow approach, since it needs two independent classes of order 3 in a group that is only a few dozen elements large.

The first discriminant with 3-rank two is $-3299$, whose class group, of order 27, is $\mathbb{Z}/3 \times \mathbb{Z}/9$ — found here by the composition, and long known from tables; groups like it are exactly the ones whose many symmetries make them rare. The weighting by $1/|\mathrm{Aut}|$ is not a statement that such groups are forbidden — only that they must be counted by how many ways they can be written down, and they can be written down in many ways.

What a heuristic is for #

Cohen–Lenstra is not a theorem, and most of it is not even close to one. It is a model: a precise description of what the class groups would look like if nothing but symmetry constrained them. Its value is that it makes predictions that can fail. It predicted the 44 per cent, the rank distribution, and the averages of $p$-torsion for every odd prime, and every one of those has survived computation, once the slow secondary terms are accounted for.

The model has also been extended with care. For real quadratic fields the weighting changes because of the units: a real field has infinitely many, and the prediction divides by an extra factor of $p$ for each, making 3 divide the class number of a real quadratic field only about 16 per cent of the time. For the even part, genus theory’s contribution is removed first and a separate model describes the rest. For fields containing extra roots of unity, Gunter Malle found in 2008 that the prediction must be modified, and the modification was found only after computations disagreed with the original — the model is corrected by exactly the process that tests it.

A group in place of a number #

It is worth noticing how much the move from class number to class group buys. The class number of a field is one integer, and a statistic of integers — how often 3 divides them — has no natural prediction beyond one in three. The class group is an object with structure, and asking which group it is, rather than how big, is what produces the 44 per cent: the prediction is a statement about groups, and divisibility by 3 is its shadow on numbers.

That shift is typical of how the arithmetic of a field is studied. The ring of integers of a field is described by its units and its class group; the units form a lattice whose shape is measured by the regulator, and the class group measures the failure of unique factorisation. For imaginary quadratic fields the units are trivial and the class group is everything, which is why these fields are the cleanest place to test a model of class groups, and why the model was checked here first.

What the computation cannot show #

Every class number here is exact, computed by counting reduced forms, and the class groups down to $-20{,}000$ are computed by composition, with the classes of order dividing 3 counted directly. What the figures cannot reach is the limit, and the heuristic is about the limit. A share of 39 per cent, rising slowly, is consistent with 44 per cent in the limit and would be consistent with other values; the case for 44 rests on the model, on the proved Davenport–Heilbronn average, and on the secondary term that explains the shortfall.

The rank shares at $-20{,}000$ are shares of about six thousand fields, and the rank-two share is a few dozen of them. They show the shape of the distribution, not its limit, and a range a hundred times larger would still sit visibly below the prediction.

Still open: the distribution itself #

The Cohen–Lenstra prediction for imaginary quadratic fields is proved in two places only: the average of 3-torsion, by Davenport and Heilbronn, and — in a form over function fields rather than number fields — a version proved by Jordan Ellenberg, Akshay Venkatesh and Craig Westerland in 2016 using the topology of spaces of branched covers. For number fields themselves, the average of 5-torsion is unknown, and so is the chance that 3 divides the class number.

The questions it answers statistically remain open individually. Whether Euler’s list of convenient numbers is complete is a question about class groups with every element of order two, and the random model says such groups become vanishingly rare; proving there are no more requires a lower bound on class numbers that nobody has. The random model predicts a great deal about the ensemble and nothing about any single field.

What the symmetries decide #

A class number measures how badly factorisation fails, and it looks like the least structured number in arithmetic. Counted across ninety thousand fields, it is divisible by 3 far more often than by chance, it is even exactly when genus theory says so, and its 3-torsion averages what a random group’s does. The randomness is of a particular kind — each group weighted by one over its symmetries — and that single rule predicts the 44 per cent, the rank distribution and the average, and it explains why groups with many symmetries, which one might expect to be the natural ones, are the rare ones.

The same principle runs through the whole of counting up to symmetry: an object with more symmetries is one object where a less symmetric one would have been several. Here it tells the arithmetic which groups to expect, and the arithmetic, over ninety thousand fields and as slowly as the secondary terms allow, agrees.