Which primes a form takes

Fermat’s two-square theorem says that an odd prime is $a^2 + b^2$ exactly when it is $1$ modulo four. It is a perfect answer: a question about representing a number by a quadratic expression, settled by a congruence anybody can check in a second.

The obvious next question is what happens to other forms, and the obvious guess is that each has its own congruence. That guess is right for a while and then it is spectacularly wrong, and the point at which it fails is where elementary number theory ends.

The three easy cases #

For $n = 1, 2, 3$ there is a congruence and it is short.

An odd prime is $x^2 + y^2$ exactly when $p \equiv 1 \pmod 4$. It is $x^2 + 2y^2$ exactly when $p \equiv 1$ or $3 \pmod 8$. It is $x^2 + 3y^2$ exactly when $p \equiv 1 \pmod 3$, with the single exception $p = 3$ itself.

Each of those is a theorem of Fermat’s or Euler’s, and each is proved the same way. The condition on $p$ is exactly the condition for $-n$ to be a square modulo $p$ — which is what the supplements and reciprocity compute — and the step from there is a square root of $-n$ to there is a representation goes through a ring.

For $n = 1$ the ring is the Gaussian integers $\mathbb{Z}[i]$: a square root of $-1$ modulo $p$ shows that $p$ is not prime there, and a factorisation of $p$ into conjugate factors is a representation. For $n = 2$ it is $\mathbb{Z}[\sqrt{-2}]$ and for $n = 3$ it is the Eisenstein integers. In all three the ring has unique factorisation, and that is the load-bearing hypothesis.

Why the ring is the whole story #

The chain of reasoning is worth setting out once in full, because everything that follows is about which link breaks.

Suppose $-n$ is a square modulo $p$, say $c^2 \equiv -n$. Then $p$ divides $c^2 + n = (c + \sqrt{-n})(c - \sqrt{-n})$ in the ring $\mathbb{Z}[\sqrt{-n}]$, while dividing neither factor — since $p$ dividing $c \pm \sqrt{-n}$ would mean $p$ divides $1$, looking at the coefficient of $\sqrt{-n}$. So $p$ is not a prime element of that ring.

If the ring has unique factorisation, not prime implies not irreducible: $p = \alpha\beta$ with both factors non-units. Taking norms, $p^2 = N(\alpha)N(\beta)$ with both norms bigger than one, so $N(\alpha) = p$. And $N(x + y\sqrt{-n}) = x^2 + ny^2$, so a representation has appeared.

Every step is easy except the words if the ring has unique factorisation. That is where the subject actually lives, and the reason the elementary treatment covers $n = 1, 2, 3$ and stops is that those are among the very few $n$ for which the ring behaves.

A form is a lattice, and two forms can be one lattice #

The clean way to say what is going on uses lattices rather than expressions, and it makes the count of forms into a count of shapes.

The values of $x^2 + ny^2$ are the squared lengths of the points of a rectangular lattice with sides $1$ and $\sqrt{n}$. Changing coordinates by an invertible integer matrix of determinant one changes the expression and not the lattice, so $x^2 + ny^2$ and $x^2 + 2xy + (1+n)y^2$ are the same object written twice. What is genuinely different is a lattice of the same determinant with a different shape, and the number of such shapes is the class number.

That reformulation is what makes the subject finite. For $n = 5$ there are two shapes of lattice with the right determinant, giving $x^2 + 5y^2$ and $2x^2 + 2xy + 3y^2$; a prime represented by the first is a point at the right distance in the first lattice, and a prime represented by the second is a point in the other. For $n = 1, 2, 3$ there is one shape, and that is exactly the statement that every prime passing the congruence is represented by the one form.

A lattice’s own arithmetic is therefore the object, and the form is a coordinate system on it. The switch of viewpoint costs nothing and explains why the answers come in finite lists.

Where unique factorisation fails #

The standard first failure is $n = 5$. In $\mathbb{Z}[\sqrt{-5}]$,

$$6 = 2 \times 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}),$$

and all four factors are irreducible with no common refinement. So the argument above breaks: a prime can fail to be irreducible without a factor of norm $p$ existing.

The consequence is visible in the answers. A prime $p$ is $x^2 + 5y^2$ when $p \equiv 1$ or $9 \pmod{20}$, and it is represented by the other form $2x^2 + 2xy + 3y^2$ when $p \equiv 3$ or $7 \pmod{20}$. The congruence condition for $-5$ to be a square modulo $p$ covers all four classes; which of the two forms actually represents $p$ needs one more bit of information, and that bit is still a congruence.

So $n = 5$ is not the counterexample. It is the first case where the answer needs two forms rather than one, and the split between them is still decided modulo $20$. The class group has order two, the two classes are told apart by congruences, and everything remains elementary.

The case where congruences run out #

The counterexample is $n = 27$, and Gauss found the answer.

An odd prime $p$ is $x^2 + 27y^2$ exactly when $p \equiv 1 \pmod 3$ and $2$ is a cube modulo $p$. The first condition is a congruence. The second is not, and cannot be made into one.

The hero figure demonstrates the failure without proving it. For every modulus up to a hundred and sixty, the search finds two primes in the same residue class that disagree about whether they are $x^2 + 27y^2$, over the fourteen hundred primes below twelve thousand. The smallest pair is easy to check by hand: $31 = 4 + 27 = 2^2 + 27\cdot 1^2$, and $139$ is not $x^2 + 27y^2$, since $139 - 27 = 112$ and $139 - 108 = 31$ are neither of them squares. Both are $31$ modulo $108$.

That is evidence and not a proof, and the essay says so where the figure does. What makes it a theorem is a statement about symmetry groups: a condition on $p$ expressible by congruences is exactly a condition that comes from a field whose symmetry group is abelian, and the field where is $2$ a cube is decided has symmetry group $S_3$, which is not — and that group’s refusal to come apart is the same obstruction, in the same group, that stops the quintic being solved by radicals.

Why “abelian” is the dividing line #

The reason is worth stating even in outline, because it is the whole of the modern answer.

A congruence condition on $p$ modulo $m$ is a statement about which class $p$ falls into in the group of units modulo $m$. By the theory that grew out of the Gauss sum, that group is the symmetry group of the field generated by the $m$-th roots of unity. So congruence conditions correspond exactly to fields sitting inside a cyclotomic one — and those are exactly the fields whose symmetry group is abelian, because a subgroup of an abelian group’s quotients is abelian.

The condition 2 is a cube modulo $p$ is about how $p$ splits in the field generated by a cube root of two, and that field’s symmetry group is $S_3$. Since $S_3$ is not abelian, the field is not inside any cyclotomic field, and the condition is not any congruence.

So the reason $x^2 + y^2$ is easy and $x^2 + 27y^2$ is not is that one is governed by an abelian group and the other is not, and the whole of class field theory is the systematic version of that sentence.

Which n are easy, and how few there are #

The forms $x^2 + ny^2$ for which a single congruence answers everything are those where the class group is trivial, and the list is short: $n = 1, 2, 3, 4, 7$ among the small ones, and famously nothing beyond a finite list.

The precise statement is a landmark. The imaginary quadratic fields with unique factorisation have discriminants $-3, -4, -7, -8, -11, -19, -43, -67, -163$ and no others — a fact conjectured by Gauss, and proved twice in the twentieth century after a first proof by Heegner in 1952 was wrongly dismissed for a decade.

Nine numbers, and then nothing forever. That is an unusual shape for a theorem in this subject, where answers are normally infinite families, and it says that the elementary case is not the typical case but a finite accident.

The next tier — class number two — is also a finite list, and covers cases like $n = 5$ where two forms and a finer congruence suffice. Beyond that the classes multiply and no arrangement of congruences separates them.

The count, not just the existence #

Once the existence question is settled the counting question follows almost for free, and it is worth having because it is prettier than the existence statement.

The number of ways to write $m$ as an ordered sum of two squares, counting signs and orders as different, is four times the difference between the number of divisors of $m$ congruent to $1$ modulo four and those congruent to $3$. So $25$ has divisors $1, 5, 25$, all $1$ modulo four, giving $4 \times 3 = 12$ representations — which are the four sign choices on $(0, \pm 5)$ and $(\pm 5, 0)$, and the eight on $(\pm 3, \pm 4)$ and $(\pm 4, \pm 3)$.

That formula is Jacobi’s, and it is a statement about the divisor structure of a number rather than about squares. The bridge is again the ring: counting representations counts factorisations in the Gaussian integers, and factorisations there are read off the factorisation in the integers by splitting each prime according to its residue class.

Existence is a yes-or-no about one prime; the count is a multiplicative function on all integers. The second is the stronger statement and it is the one that generalises to the other easy forms, each of which has its own count with its own divisor condition.

The Legendre symbol as the first case of everything #

Standing back, reciprocity looks different from this rung than it did from the first.

The law says: whether $q$ is a square modulo $p$ is determined by $p$ modulo $4q$. Read in the language above, it says the condition $q$ is a square mod $p$ — which is a statement about how $p$ splits in $\mathbb{Q}(\sqrt{q})$ — is a congruence condition, because $\mathbb{Q}(\sqrt{q})$ sits inside a cyclotomic field. And the Gauss sum is the element that exhibits it there.

So the whole ladder has been climbing one statement. The rectangle counted two ways, the sign of a shuffle, the sum of signed roots of unity — each proves that a quadratic field is cyclotomic, in a language that hides what is being proved. The last rung’s job is to say what it was.

Every proof on this ladder proves the same theorem and only one of them names the object. That is the argument for the Gauss sum being the important proof, made from a rung it could not have been made from earlier.

Higher reciprocity, and why it needs a bigger ring #

The natural extension asks about cubes and fourth powers, and it immediately leaves the integers.

Gauss found that a law for fourth powers is clean only over $\mathbb{Z}[i]$, and one for cubes only over the Eisenstein integers. Stated over $\mathbb{Z}$ they are a mess of cases; stated over the right ring they look like reciprocity again. His remark, in the 1828 paper on biquadratic residues, is that the natural home for such a theorem is not the ordinary integers, and that observation is the reason algebraic number theory exists.

The pattern the ladder has been describing therefore continues: each reciprocity law is a statement that a condition on primes is a congruence in a suitable ring, and the general theorem — Artin’s reciprocity law of 1927 — covers all of them and is the summit of the abelian theory. What lies beyond it, where the symmetry group is not abelian, is where $x^2 + 27y^2$ lives, and that is not finished.

Doing one case by hand #

Take $p = 61$ and ask whether it is $x^2 + 27y^2$.

First condition: $61 = 3 \times 20 + 1$, so $61 \equiv 1 \pmod 3$. Passed.

Second: is $2$ a cube modulo $61$? The cubes modulo $61$ form a subgroup of index three in the group of order sixty, so there are twenty of them, and $2$ is a cube exactly when $2^{20} \equiv 1$. Computing, $2^6 = 64 \equiv 3$, so $2^{20} = 2^{18}\cdot 4 = (2^6)^3 \cdot 4 \equiv 27 \times 4 = 108 \equiv 47$, which is not $1$. So $2$ is not a cube modulo $61$, and $61$ is not $x^2 + 27y^2$.

Checking directly: $61 - 27 = 34$ and $61 - 108 < 0$, and $34$ is not a square. Correct.

The test that decided it was an exponentiation, not a congruence, and that is exactly the difference this rung is about. Nothing about $61$’s residue class modulo any fixed modulus was consulted at the second step.

What a table of primes shows and what it hides #

It is worth being clear about what a reader can and cannot get from staring at the data, because this is a subject where the pattern is visible long before it is provable and one of the patterns is not there.

For $n = 1$ the pattern is obvious after twenty primes: the represented ones are $5, 13, 17, 29, 37, 41$ and the unrepresented $3, 7, 11, 19, 23, 31$, and the split by residue modulo four jumps out. Euler had exactly this kind of table and the conjecture cost him nothing; the proof cost seven years.

For $n = 27$ the represented primes below three hundred are $31, 43, 109, 127, 157, 223, 229, 277$ and $283$, and there is no pattern to find, because there is none. A reader who sorts them by residue modulo any modulus small enough to try will see classes that are partly represented and partly not, and will conclude either that the modulus is too small or that something else is going on. Both conclusions are reasonable and only the second is right.

A negative result about patterns is much harder to reach from data than a positive one. Seeing a pattern takes twenty numbers; establishing that none exists takes the theory of field extensions, and no amount of further computation substitutes.

What the picture cannot show #

The refusal is demonstrated over a range and not proved. The hero sweeps every modulus up to a hundred and sixty against fourteen hundred primes and finds a disagreeing pair each time. A modulus of ten thousand is not tested and a proof would have to cover all of them; the argument that does is the one about abelian symmetry groups, and it is algebra rather than search.

The failure of unique factorisation is invisible in a lattice. The points of $\mathbb{Z}[\sqrt{-5}]$ look exactly like the points of $\mathbb{Z}[\sqrt{-2}]$, differently spaced. What distinguishes them is which elements divide which, and divisibility is not a property of a point’s position.

And the marked rows are of primes below two hundred. Every claim of the form exactly these residue classes is a statement about all primes; the search that supports it runs to twelve thousand and stops there.

Where the ladder goes next #

This closes the ladder. It began with a rectangle of dots counted along its rows and then along its columns, and it ends with the observation that the theorem that rectangle proves is the first case of a correspondence between congruences and symmetry groups — which is a subject rather than a result.

What remains unwritten from here is not a further rung on reciprocity but a different anchor: the arithmetic of quadratic forms in their own right, where the class group is the object and reciprocity is a tool. Sideways, the primes that are sums of two squares is where this rung’s easiest case was proved for its own sake, and unique factorisation and where it fails is the hypothesis every argument here leaned on.

What is worth carrying away #

The reach of an elementary method is usually decided by a structural fact nobody mentions while using it.

The two-square theorem is proved in a paragraph, and the paragraph works because $\mathbb{Z}[i]$ has unique factorisation. Nine imaginary quadratic rings do; the rest do not; and the whole difference between a subject that can be done by hand and a subject that needs a theory is that finite list.

So the useful question about any elementary argument is which of its steps is quietly a theorem. Here it is the one that reads and therefore it factors, which is four words long and is the entire content.