Real fields that factorise uniquely

Counting the classes that break factorisation counted, for negative discriminants, the reduced binary quadratic forms that measure how badly unique factorisation fails in a quadratic field. For imaginary fields $\mathbb Q(\sqrt{-d})$ the class number grows with $d$, and only nine of them — $d = 1, 2, 3, 7, 11, 19, 43, 67, 163$ — have class number one, which Gauss conjectured and Baker, Heegner and Stark proved in the 1960s. Sixty needs two digits and sixty-one ten followed Pell’s equation, whose fundamental solution is the fundamental unit of the real field $\mathbb Q(\sqrt D)$, and found its size jumping erratically with $D$. This essay puts the two together. Real quadratic fields have class numbers too, and their behaviour is the opposite of the imaginary ones’: Gauss conjectured that infinitely many real fields have class number one, and that conjecture is still open.

The figures compute the class number of $\mathbb Q(\sqrt p)$ for every prime $p \equiv 1 \pmod 4$ below 400,000 — 16,900 fields — by counting cycles of reduced forms, and find class number one in about four fields out of five. They then find why the real fields can afford it: the class number formula ties the class number to the size of the field’s fundamental unit, and when the unit is large, as it typically is, there is no room left for a large class group.

Cycles of forms instead of a single reduced form #

For a negative discriminant, each class of forms contains exactly one reduced form, and counting classes is counting reduced forms. For a positive discriminant $D$ the forms are indefinite — they take both positive and negative values — and reduction does not settle on a single representative. A form $ax^2 + bxy + cy^2$ with $D = b^2 - 4ac > 0$ is called reduced when $0 < b < \sqrt D$ and $\sqrt D - b < 2|a| < \sqrt D + b$, and there are finitely many reduced forms of each discriminant. Gauss’s reduction step sends a reduced form $(a, b, c)$ to $(c, b', c')$, where $b'$ is chosen congruent to $-b$ modulo $2c$ in the window just below $\sqrt D$; the result is reduced again, and the step permutes the reduced forms. Two reduced forms are equivalent exactly when one step sequence leads from one to the other, so the classes are the cycles of the permutation.

The hero figure draws them for $D = 229$, the smallest prime $p \equiv 1 \pmod 4$ for which the answer is not one. There are fourteen reduced forms, and the reduction step arranges them in three cycles, of six, six and two forms. Three classes means that the ring of integers of $\mathbb Q(\sqrt{229})$ does not factorise uniquely: there are ideals not generated by any single element. The method was checked against published values before being trusted: $\mathbb Q(\sqrt5)$ and $\mathbb Q(\sqrt{13})$ have class number one, $\mathbb Q(\sqrt{229})$ and $\mathbb Q(\sqrt{257})$ three, $\mathbb Q(\sqrt{401})$ five, $\mathbb Q(\sqrt{577})$ seven, and $\mathbb Q(\sqrt{1129})$ nine.

Two features of prime discriminants make the count clean. Because $p \equiv 1 \pmod 4$ is prime, the negative Pell equation $x^2 - py^2 = -1$ always has a solution — the fact when minus one can be reached proved with a remainder argument — so the fundamental unit has norm $-1$, which makes the narrow class number that the cycles count equal to the ordinary class number. And Gauss’s genus theory shows that for a prime discriminant there is only one genus, which forces the class number to be odd. Every one of the 16,900 class numbers computed is odd.

The principal cycle is a continued fraction #

One of the cycles is special. The form $x^2 + xy - \tfrac{p-1}{4}y^2$ takes the value 1 and represents the class of principal ideals, those generated by a single element; its cycle is the principal cycle, and the field factorises uniquely exactly when it is the only cycle. Following the principal cycle step by step is the same computation as expanding $(1 + \sqrt p)/2$ as a continued fraction: each reduction step is one step of the expansion, the middle coefficients $b$ of the forms are the numerators of the complete quotients, and the cycle closes exactly when the continued fraction’s period does. That identification goes back to Gauss and Lagrange, and it is why one computation gives both invariants. The length of the principal cycle is the period of the continued fraction, and the product of the complete quotients over that period is the fundamental unit.

So the number of reduced forms is shared out among the cycles, and the principal cycle’s share is the continued fraction’s period. If the period is long, the principal cycle swallows most of the reduced forms and few remain to form other cycles; if it is short, the remaining forms must be arranged in other cycles, and the class number is large. For $p = 229$ the fourteen reduced forms split into the principal cycle and two others of comparable size, so the period is short enough to leave room. For most primes the period is long, of order $\sqrt p$, and the principal cycle takes everything, which is the counting version of the class number formula below: the number of reduced forms grows like $\sqrt p \log p$ and the period, typically, nearly as fast.

This is a different mechanism from the one factoring uniquely with no way to divide used for the Gaussian integers, where a division algorithm with small remainders proves unique factorisation directly. Most real quadratic fields with class number one have no such algorithm — they are not Euclidean for the ordinary norm — and their unique factorisation is a consequence of counting rather than of any procedure.

Four fields in five #

The next figure follows the share of fields with class number one as the primes increase.

Below ten thousand, 83.0 per cent of the fields have class number one; below four hundred thousand, 79.1 per cent. The share falls, but slowly, and it sits well above the line at $75.45$ per cent that Henri Cohen and Hendrik Lenstra’s heuristic of 1984 predicts as the limit. Class groups drawn at random tested the same heuristic for imaginary fields, where it predicts how often the class group has a factor of 3 or 5 or 7; for real fields the heuristic needs one change, accounting for the unit, and its prediction for prime discriminants is that a share $0.754458\ldots$ have class number one. The data are consistent with a slow approach to that value from above and cannot confirm it; the convergence is known to be slow, through terms that decrease like a power of $\log p$.

What the data cannot do is prove Gauss’s conjecture, which needs only that infinitely many of these fields have class number one. Every counted share is far above nought, and the heuristic says three quarters, but there is no proof that the count of class-number-one fields among the $\mathbb Q(\sqrt p)$ is even unbounded. That is the strangeness of the subject: the imaginary fields with class number one were proved to be exactly nine, a finite list that took a century and a half to establish, while the real fields that seem to have class number one most of the time have not been proved to have it infinitely often.

Where three quarters comes from #

The heuristic behind the dashed line is a rule for guessing how often a random-looking abelian group appears. Cohen and Lenstra proposed that the odd part of the class group of an imaginary quadratic field behaves like a random finite abelian group in which each group occurs with probability proportional to one over the number of its symmetries: groups with many automorphisms are rare, because there are many ways of building them that are counted as the same. That single principle predicts, for example, that the class number is divisible by 3 for about 44 per cent of imaginary fields, which class groups drawn at random measured.

For real fields the unit changes the model. A real quadratic field’s class group is predicted to look like a random group of the same kind with one random element divided out, standing for the unit’s contribution to the arithmetic, and dividing out a random element makes small groups — the trivial group above all — considerably more likely. Carried through, the computation gives $0.754458\ldots$ as the probability that the odd part of a real field’s class group is trivial; for prime discriminants, where the class group has no even part, that is the probability of class number one. The heuristic is not a theorem in any case, but it agrees with everything that has been proved, including the average number of elements of order 3 in the class groups of real and of imaginary fields, which Harold Davenport and Hans Heilbronn computed exactly in 1971 by counting cubic fields — and the real-field average they found is exactly what the version with one element divided out predicts.

The class numbers that occur #

When the class number is not one, it is usually small.

Class number one occurs 13,366 times, three 1,795 times, five 630, seven 323, nine 205, and the counts thin out from there, with occasional larger values. The pattern follows the heuristic’s logic: a class group whose order is divisible by a prime $\ell$ is less likely the larger $\ell$ is, roughly in proportion to $1/\ell$, and class groups with a repeated factor, such as order 9 or 25, are rarer still. The same heuristic governs the imaginary fields, where the class numbers themselves grow without bound and only the shape of the group is predicted; for real fields of prime discriminant, the prediction is that the class group is trivial three times in four, and the counts find order three about one time in nine or ten, and the larger orders progressively rarer.

The unit takes up the slack #

The reason real fields can have class number one so often is in the class number formula. For a real quadratic field with discriminant $D$,

$$h \cdot R = \frac{\sqrt D}{2}\, L(1, \chi_D),$$

where $h$ is the class number, $R$ is the regulator — the natural logarithm of the fundamental unit — and $L(1, \chi_D)$ is a sum of the Legendre symbol $\chi_D(n)/n$ over all $n$, which stays of moderate size. For imaginary fields there is no regulator, and the formula gives $h$ itself of order $\sqrt D$: the class number must grow. For real fields the product $hR$ is of order $\sqrt p$, and it can be made up either way.

The regulators in the figure are computed from the period of the continued fraction of $(1 + \sqrt p)/2$, as the logarithm of the product of its complete quotients over one period, which is the fundamental unit. For fields with class number one they cluster near $\sqrt p$, an average regulator of $10^{1.70}$ against $10^{1.11}$ for the fields with larger class numbers. The formula was checked directly for six of the primes, by summing the Legendre symbol to four hundred thousand terms: $h \cdot R$ agrees with $\sqrt p\,L(1, \chi)/2$ to within five per cent each time, the residue being the truncation of the slowly converging sum.

So the dichotomy is clean. A field whose fundamental unit is small, with a short continued fraction period, must have a large class number to make up the product; a field whose unit is large, with a long period, has room for class number one. Since the fundamental unit of $\mathbb Q(\sqrt p)$ is typically large — its logarithm of order $\sqrt p$, as the Pell equation’s erratic solutions showed — class number one is typical. The unpredictability of the size of Pell’s solutions and the unpredictability of class numbers are one phenomenon seen from two sides of one equation.

Where factorisation fails #

The last figure lists the exceptions among the smallest primes.

Of the 211 primes $p \equiv 1 \pmod 4$ below 3,000, only 27 give fields without unique factorisation, and most of those have class number three. The first is 229, the first with class number five is 401, the first with seven is 577, and 1,297 has class number eleven. How badly factorisation fails depends on the class number as well. Leonard Carlitz proved in 1960 that when the class number is two, an element can factorise into irreducibles in several ways but always into the same number of factors; with class number three or more, as at 229, even the number of factors can change from one factorisation to another, so the class number measures not only whether uniqueness is lost but how much of it. The exceptions become slowly more common as $p$ grows: about one prime in eight below 3,000, one in five below 400,000, and towards one in four in the limit if the heuristic is right. The smallest primes are misleading in a specific direction, as a cube root that looks like chance found for continued fractions: the regularities that small cases suggest are not the ones that hold at large sizes.

What the counts cannot show #

The class numbers are exact: each is a count of cycles of forms, computed in integer arithmetic, and checked against published values for the small cases. The regulators are computed in floating point, as sums of logarithms, and are accurate to many digits; the class number formula checks agree to five per cent because the $L$-function sums were truncated, not because the regulators are uncertain. What the counts cannot do is reach the limit. Cohen and Lenstra’s 75.45 per cent is a heuristic, not a theorem, and the data’s approach to it, from 83 to 79 per cent across the primes counted, is consistent with it and with other limits nearby.

Nor do the counts say anything about real fields that are not of prime discriminant. Many of those have class number one too — $\mathbb Q(\sqrt 2)$, $\mathbb Q(\sqrt 3)$ and $\mathbb Q(\sqrt 6)$ among them — but for them the narrow class number that the cycles count can be twice the ordinary one, and genus theory no longer forces it to be odd, so the prime case drawn here is the cleanest instance of Gauss’s question rather than the whole of it.

Still open: Gauss’s conjecture #

Are there infinitely many real quadratic fields with class number one? Gauss conjectured so in the Disquisitiones Arithmeticae of 1801, and it has not been proved, or even reduced to a standard hypothesis such as the generalised Riemann hypothesis. The difficulty is the regulator. To show $h = 1$ from the class number formula one would need to show that the regulator is as large as $\sqrt p\,L(1, \chi)/2$ for infinitely many $p$, and lower bounds for regulators that strong are far out of reach; the regulator is a statement about the size of the smallest solution of Pell’s equation, and nothing better than computing it is known for an individual $p$.

The conjecture is also tied to a question about continued fractions. The regulator is roughly the period of the continued fraction of $\sqrt p$ times a slowly varying average, and Gauss’s conjecture would follow from a proof that infinitely many $\sqrt p$ have periods about as long as $\sqrt p$. Units that form a lattice described the unit group of a number field as a lattice whose volume is the regulator; for real quadratic fields that lattice is one-dimensional, its generator is the fundamental unit, and the open question is how long that single vector usually is.

A trade between two invariants #

The real quadratic fields of prime discriminant split their arithmetic between two invariants whose product is fixed: the class number, which measures how badly factorisation fails, and the regulator, which measures how large the smallest nontrivial unit is. In four fields out of five, below four hundred thousand, the unit takes everything and the class number is one. That is why the imaginary fields, which have no units to speak of, run out of class-number-one examples after nine, while the real fields seem to have them in abundance — and why proving that abundance is a question about the size of solutions to Pell’s equation, the oldest and most erratic object in the subject.