Counting the classes that break factorisation

Factoring uniquely with no way to divide ended with a number that measured failure. In the integers of $\mathbb{Q}(\sqrt{-5})$, six factors two ways, $2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5})$, and the repair is to count the ideals up to multiplication by numbers: two classes of them, the principal ones and the rest. The class number is how many classes there are. It is one exactly when factorisation is unique — one way to factor, and no other, as in the ordinary integers — and nine imaginary quadratic fields have class number one.

Defined that way, through ideals, the class number looks like something that cannot be computed: an ideal is an infinite set, and there are infinitely many of them. Carl Friedrich Gauss computed it for hundreds of fields in 1801, before ideals were invented, and he did it by counting something finite. This essay is that count.

The figure below is the whole count for one field, $\mathbb{Q}(\sqrt{-21})$, whose discriminant is $-84$. Four expressions — $x^2 + 21y^2$, $2x^2 + 2xy + 11y^2$, $3x^2 + 7y^2$ and $5x^2 + 4xy + 5y^2$ — each drawn at a point of the upper half-plane, all four inside a shaded region. Every quadratic form of discriminant $-84$ can be moved into that region in exactly one way, and there are exactly four places it can land. The class number of the field is four.

Forms instead of ideals #

A binary quadratic form is an expression $ax^2 + bxy + cy^2$ with whole coefficients, and its discriminant is $b^2 - 4ac$. The forms that decide which primes are sums of squares are the simplest examples: $x^2 + y^2$ has discriminant $-4$, and $x^2 + 5y^2$ has $-20$. When the discriminant is negative and $a$ is positive the form takes only positive values, like a squared length — it is the squared length of a vector in a lattice with a tilted or stretched grid.

Two forms are equivalent when a change of variables $x \mapsto px + qy$, $y \mapsto rx + sy$ with whole numbers and $ps - qr = 1$ turns one into the other. Such a change is a relabelling of the same lattice by a different basis, so equivalent forms take exactly the same values. They have the same discriminant, and a form’s equivalence class is the lattice itself, stripped of the choice of basis.

Dedekind proved the dictionary Gauss had been using without it: for the discriminant of a field, equivalence classes of forms correspond exactly to classes of ideals. Each ideal is a lattice of numbers in the field; its norm form, the squared length of its elements divided by the ideal’s norm, is a binary quadratic form; and two ideals are in the same class exactly when their forms are equivalent. The class number is the number of classes of forms, and that number Gauss could count.

Squeezing a form into shape #

A form can be simplified by two moves. A shift, $x \mapsto x + ky$, keeps $a$ and changes $b$ by $2ka$, so $b$ can be brought between $-a$ and $a$. A swap, $x \mapsto -y$, $y \mapsto x$, exchanges $a$ and $c$ and negates $b$. Each keeps the discriminant and the set of values.

Alternate them: shift to make $|b| \le a$, and if then $a > c$, swap and shift again. Each swap makes $a$ strictly smaller, so the process stops, and it stops at a form with $|b| \le a \le c$. Such a form is called reduced — with a small convention on signs when $|b| = a$ or $a = c$, to break ties. The form $9x^2 + 14xy + 6y^2$ reduces in three steps to $x^2 + 5y^2$, and the figure checks at each step that the discriminant is still $-20$ and that the forms take the same values.

Joseph-Louis Lagrange proved in 1773 the fact that makes reduction a counting tool: every form is equivalent to exactly one reduced form. So the classes of forms of a given discriminant are in one-to-one correspondence with the reduced forms, and those can be listed. A reduced form has $a \le \sqrt{|D|/3}$, since $4a^2 \le 4ac = b^2 - D \le a^2 + |D|$. So $a$ is bounded, $b$ is bounded by $a$, and $c$ is determined by the discriminant. Finitely many candidates, each checked in a line.

The upper half-plane #

The shaded region in the hero is where the reduced forms live when each is drawn as a point.

A form $ax^2 + bxy + cy^2$ with negative discriminant has, as a quadratic in $x/y$, two complex roots, and the one in the upper half-plane is $\tau = (-b + \sqrt D)/2a$. The shift moves $\tau$ one step left or right; the swap sends it to $-1/\tau$, reflecting it through the unit circle. The reduction conditions $|b| \le a \le c$ say precisely that $\tau$ has real part between $-\tfrac12$ and $\tfrac12$ and distance at least one from the origin: the region bounded by two vertical lines and an arc. So the reduction is a walk of $\tau$ in the upper half-plane, and it ends when $\tau$ enters the region.

That region is the fundamental domain of the modular group, the group of changes of variable with whole entries and determinant one. Every point of the upper half-plane can be moved into it, and only its boundary points can be moved to each other. The same region appears whenever lattices in the plane are classified up to rotation and scale — it is the space of all lattice shapes — and the forms of a given discriminant are the lattice shapes with one particular covolume. For discriminant $-84$ there are four such shapes, drawn at four points, one of them, $5x^2 + 4xy + 5y^2$, sitting exactly on the arc where two boundaries meet.

Two forms, two kinds of prime #

Different classes take different values, and for the primes the division is clean.

Discriminant $-20$ has two reduced forms, $x^2 + 5y^2$ and $2x^2 + 2xy + 3y^2$, so $\mathbb{Q}(\sqrt{-5})$ has class number two. The figure sorts the primes by their remainder modulo twenty and asks which form takes each. The answer depends only on the remainder: $1$ and $9$ go to the first form, $3$ and $7$ to the second, and the other four remainders to neither. The primes that neither form takes are the ones that stay prime in the field; the others split into two ideal factors, principal for the first form and not for the second.

This is what the class number two looks like in the primes. The prime $3 = 2 \cdot 0^2 + 2\cdot0\cdot1 + 3\cdot1^2$ is taken by the second form, so its ideal factors are not principal, and that is exactly why $6 = 2 \cdot 3$ could also be $(1 + \sqrt{-5})(1 - \sqrt{-5})$: the four factors are products of non-principal ideals grouped two different ways. Euler conjectured which primes are $x^2 + 5y^2$, from tables he computed, and Lagrange and Gauss proved it with forms; the explanation by ideals came half a century later.

The ideal behind the second form #

The dictionary can be run by hand on the field where the failure was first seen. In $\mathbb{Q}(\sqrt{-5})$ the ideal that repairs $2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5})$ is $\mathfrak{p} = (2,\, 1+\sqrt{-5})$: every number $2x + (1+\sqrt{-5})y$ with whole $x$ and $y$. Its norm is $(2x+y)^2 + 5y^2 = 4x^2 + 4xy + 6y^2$, and the ideal’s own norm is $2$, so dividing gives $2x^2 + 2xy + 3y^2$ — the second reduced form of discriminant $-20$, exactly the one the figure above credits with the primes $3$, $7$, $23$ and $43$.

That is what “the ideal is not principal” looks like as a form. If $\mathfrak{p}$ were generated by one number $\alpha$, the norm form of $\mathfrak{p}$ would be equivalent to $x^2 + 5y^2$, and $1$ would be one of its values, since $\alpha$ itself would have norm $2$ and $\alpha/\alpha$ would count. But $2x^2 + 2xy + 3y^2$ never takes the value $1$: it is $2$ at its smallest. So the ideal has no single generator, and the proof is the reduced form’s first coefficient.

The same computation classifies the primes. A prime $p$ that splits in the field splits into two ideals, and they land in one class or the other. If they land in the principal class, $p = x^2 + 5y^2$; if in the other, $p = 2x^2 + 2xy + 3y^2$; and which one happens is decided by $p$ modulo $20$ — $1$ and $9$ for the first, $3$ and $7$ for the second — because here each class is alone in its genus, the set of classes that no congruence can tell apart. When a genus holds more than one class, as it does for $x^2 + 14y^2$ and discriminant $-56$, congruences cannot finish the job, and deciding which form takes a prime needs a polynomial rather than a congruence: for an odd prime $p$ other than $7$, $p = x^2 + 14y^2$ exactly when $-14$ is a square modulo $p$ and the quartic $(x^2+1)^2 - 8x$ has a root modulo $p$ — the quartic being the defining equation of the field that class field theory attaches to the whole class group.

Reduction is Euclid’s algorithm for lattices #

The two moves of the reduction are not new. A shift subtracts a multiple of one basis vector of the lattice from the other, and a swap exchanges them — exactly the two steps of Euclid’s algorithm, subtract the smaller as often as it fits and then exchange, played out on vectors instead of numbers. Gauss’s reduction of forms is Lagrange’s reduction of a two-dimensional lattice to its shortest basis: the reduced form’s first coefficient $a$ is the squared length of the shortest non-zero vector in the lattice, and $c$ the squared length of the shortest vector independent of it.

This is the same computation that produced the two squares whose existence Fermat’s theorem only promised: a lattice of determinant $p$ is reduced, and its shortest vector has squared length $p$ — which is $p$ written as $x^2 + y^2$. There, one form of discriminant $-4$ was all there was, since $-4$ has class number one. Here the point is that for most discriminants there are several classes, and the reduction sorts every lattice into exactly one of them.

Counting with π #

The class number has a second formula, which Dirichlet proved in 1839 and which has nothing finite about it. For a discriminant $D$ below $-4$,

$$h(D) = \frac{\sqrt{|D|}}{\pi} \sum_{n=1}^{\infty} \frac{\chi(n)}{n},$$

where $\chi(n)$ is $+1$, $-1$ or $0$ according to whether $n$ is a square modulo $D$ in the sense of the Kronecker symbol — the same symbol that decides which primes the forms take. The series is a sum with a sign in front of every term, converging slowly and conditionally, and multiplied by $\sqrt{|D|}/\pi$ it comes out to exactly the whole number of reduced forms: two for $-20$, four for $-84$.

That a transcendental number and an infinite series should conspire to produce a small whole number is the analytic class number formula’s surprise, and it is also the reason class numbers grow like $\sqrt{|D|}$: the series is bounded above and below by quantities that vary slowly, so $h(D)$ tracks $\sqrt{|D|}$ up to those slowly varying factors. Siegel’s theorem below is a statement that the series cannot be too small, and the difficulty of making it effective is the difficulty of ruling out a zero of the corresponding function very close to one — a possibility connected, like so much in this subject, to the Riemann hypothesis in a generalised form.

A group of classes #

The classes can be multiplied. Gauss defined a composition of forms — a third form whose values include the products of the two forms’ values — and proved that it makes the classes of a given discriminant into a finite abelian group, the class group. Dirichlet later gave a much simpler recipe, which is what the figure runs.

For discriminant $-84$ the table shows a group in which every element is its own inverse — the group of order four that is not cyclic, the one made of two independent switches. The identity is the principal form, $x^2 + 21y^2$, whose class is the principal ideals. The figure checks associativity on all sixty-four triples, which is the part of Gauss’s proof that took him the longest.

A group whose elements all have order two has a special meaning here. Gauss’s theory of genera sorts forms by which remainders their values leave modulo the primes dividing the discriminant, and for $-84 = -4 \cdot 3 \cdot 7$ there are four genera. When every genus holds exactly one class, as here, the remainder of a prime modulo $84$ already decides which form takes it — nothing finer is needed. Euler, without knowing why, had found the numbers $n$ for which $x^2 + ny^2$ has this property and called them idoneal; $21$ is one of them, and so, in its way, is $5$.

Nine fields, and no tenth #

With reduction, the class number of any imaginary quadratic field is a finite computation, and Gauss computed a great many.

Class number one — unique factorisation — occurs at nine discriminants: $-3, -4, -7, -8, -11, -19, -43, -67, -163$. Gauss conjectured that there are no others. The conjecture resisted for a century and a half. Kurt Heegner published a proof in 1952 that was dismissed as incomplete; Alan Baker and Harold Stark independently proved it in 1966 and 1967, by quite different methods, and Heegner’s proof was then re-examined and found to be essentially correct. He had died in 1965.

The reason there are no more is visible in the growth. The class numbers fill a band that widens like $\sqrt{|D|}$, and Carl Ludwig Siegel proved in 1935 that $h(D)$ is larger than $|D|^{1/2-\varepsilon}$ once $|D|$ is large enough, for any $\varepsilon$. That implies only finitely many discriminants have any given class number. What it does not give is a bound on how large “large enough” is: Siegel’s proof is ineffective, able to show that exceptions stop without saying where. The list of class number one had to be proved complete by other means, and making Siegel’s bound effective took until Dorian Goldfeld, Benedict Gross and Don Zagier in the 1980s, with a bound that grows only like a logarithm.

What counting forms cannot do #

The reduction counts classes exactly, for any one discriminant. What it cannot do is prove a statement about all discriminants: that class number one stops at $-163$, or that the class number grows. Each discriminant is a separate finite computation, and there are infinitely many. The figures count up to $-400$ and $-3{,}000$, and the theorems of Heegner, Baker, Stark and Siegel are what reach beyond.

The figures also draw only imaginary quadratic fields, where forms are positive and reduction is clean. For real quadratic fields, with positive discriminant, forms take both signs, a reduced form is no longer unique in its class — the reduced forms of a class come in cycles, the same cycles as the continued fraction of the square root — and counting classes means counting cycles. The class number there is small much more often, and whether it is one infinitely often is not known.

Still open: the idoneal numbers #

Euler found sixty-five idoneal numbers — the $n$ for which the form $x^2 + ny^2$ is alone in its genus, so that which primes it takes is decided by remainders alone — the largest being $1848$. He searched well beyond and found no more. It is now known, from the theory of the class group, that the idoneal numbers are exactly the $n$ for which the class group of discriminant $-4n$ has every element of order at most two.

Whether Euler’s list of sixty-five is complete is not known. Peter Weinberger proved in 1973 that at most one more exists, and none at all if a generalised form of the Riemann hypothesis is true. So the list is complete unless there is a single further idoneal number, far beyond every range that has been searched, whose existence would contradict a hypothesis almost everyone believes. It is the same kind of gap as the class-number problem had before Heegner: a finite list, an ineffective proof that it is nearly complete, and no way to rule out the last exception by computation.