Two squares, and a lattice

Draw a circle of radius $\sqrt{n}$ centred on the origin of the integer grid. Whether it passes through any lattice points is the question of whether $n$ is a sum of two squares, and the answer is far more structured than the drawing suggests.

Twenty-five is $25 + 0$ and $16 + 9$, giving twelve points once signs and orders are counted. Twenty-four is nothing at all — no circle of radius $\sqrt{24}$ touches a lattice point anywhere.

The primes decide it #

Start with the primes, because the general case reduces to them.

$5 = 1 + 4$, $13 = 4 + 9$, $17 = 1 + 16$, $29 = 4 + 25$, $37 = 1 + 36$ — every prime leaving remainder one on division by four. And $3$, $7$, $11$, $19$, $23$, $31$ — every prime leaving remainder three — is not a sum of two squares at all.

Half of that is easy. A square is congruent to $0$ or $1$ modulo $4$, since even numbers square to $0$ and odd numbers to $1$. So a sum of two squares is $0$, $1$ or $2$ modulo $4$, and can never be $3$. That disposes of the primes $\equiv 3$ in one line, and it is the kind of argument modular arithmetic exists to supply: an obstruction found by looking at a small dial rather than at the numbers themselves.

The other half is not easy at all, and it is Fermat’s theorem: every prime $\equiv 1 \pmod 4$ is a sum of two squares. Fermat stated it in 1640 and, as usual, gave no proof; Euler proved it in 1749 after seven years of work.

Why the hard half is hard #

The difficulty is the shape of the claim. Ruling something out needs an obstruction, and modulo four supplies one. Producing something needs a construction, and there is no obvious place to get one — nothing about $10007$ announces which two squares add to it.

Euler’s proof goes in two stages. First, $-1$ is a square modulo $p$ when $p \equiv 1 \pmod 4$: the multiplicative group modulo $p$ is cyclic of order $p - 1$, which is divisible by four, so it contains an element of order four, and that element squares to $-1$. Second, from a solution of $x^2 + 1 \equiv 0 \pmod p$, a descent argument produces the two squares — take any multiple of $p$ expressible as a sum of two squares, and manufacture a smaller one, until the multiplier is one.

The descent is the same machinery as the shrinking square run in the opposite direction: there it derives a contradiction by making something smaller forever, here it makes something smaller until it reaches the answer. Fermat’s method was descent and this is one of the few places his own version survives.

There is a shorter route, and it is worth knowing because it explains what the lattice is doing. In the Gaussian integers — numbers $a + bi$ with $a$ and $b$ whole — the quantity $a^2 + b^2$ is the norm, and it is multiplicative. Asking whether $p$ is a sum of two squares is asking whether $p$ factors as $(a+bi)(a-bi)$. Since $\mathbb{Z}[i]$ factors uniquely, a rational prime either stays prime there or splits into two conjugates, and which it does is decided by whether $-1$ is a square modulo $p$ — the same condition as before, arrived at through algebra instead of descent.

Counting the points exactly #

Knowing which numbers are sums of two squares is one question; knowing in how many ways is another, and it has a clean answer that nothing about the geometry suggests.

Jacobi’s formula says the number of lattice points on the circle of radius $\sqrt{n}$ is

$$r_2(n) = 4\big(d_1(n) - d_3(n)\big),$$

where $d_1$ counts the divisors of $n$ congruent to $1$ modulo $4$ and $d_3$ those congruent to $3$. For $n = 65$ the divisors are $1, 5, 13, 65$, all $\equiv 1$, so $d_1 = 4$, $d_3 = 0$, and $r_2 = 16$. For $n = 24$ the divisors are $1, 2, 3, 4, 6, 8, 12, 24$, of which $1$ is $\equiv 1$ and $3$ is $\equiv 3$, giving zero.

The formula is one of the most surprising in elementary number theory. Counting points on a circle is a geometric question; counting divisors in residue classes involves neither circles nor squares; and the two are equal for every $n$. Every figure in this essay checks it, which is the only honest way to present an identity of that shape — the generator counts the drawn points and computes the divisor difference, and refuses to draw if they disagree.

The factor of four is the symmetry: the lattice is invariant under quarter turns, so points come in fours unless they sit on an axis, and the formula absorbs the exceptions.

Reading Jacobi’s formula as a product rather than a difference makes the mechanism clearer. The quantity $d_1 - d_3$ is multiplicative — it is $\sum_{d \mid n} \chi(d)$ for the character $\chi$ that is $+1$ on $1 \bmod 4$, $-1$ on $3 \bmod 4$ and $0$ on evens — so it factors over the prime powers of $n$. A prime $\equiv 1$ raised to the $a$th power contributes $a + 1$; a prime $\equiv 3$ contributes $1$ if its exponent is even and $0$ if odd; a power of two contributes $1$. So the whole count is a product of small factors, one per prime, and the zero that kills $7$ and $24$ comes from a single prime $\equiv 3$ appearing an odd number of times.

Where the circle count becomes $\pi$ #

Adding up $r_2(n)$ for $n$ up to $R^2$ counts every lattice point inside a circle of radius $R$, and that count is estimated by an area.

So $\sum_{n \le R^2} r_2(n) \approx \pi R^2$, and combining that with Jacobi’s formula gives

$$\frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots,$$

the Leibniz series, derived from counting divisors in residue classes. That is a genuinely startling route to it. No circle appears in the right-hand side, no trigonometry appears anywhere, and $\pi$ arrives because the number of divisors in one class exceeds the number in the other by an amount that averages to a quarter of it.

This collection has met $\pi$ arriving uninvited before, and this is the arithmetic version of the same phenomenon. The constant is not about circles; it is about the two-dimensional shape of anything, and here the anything is a lattice being counted.

How well the area approximates the count is Gauss’s circle problem. The error is at most about $R$ — the boundary strip — and is conjectured to be about $R^{1/2}$; Gauss proved $R$, Sierpiński improved it, and the current record is roughly $R^{0.63}$ against a conjectured $R^{0.5}$. The exact answer has been open since 1837, which puts it beside the divisor problem as one of the two classical lattice-counting questions nobody can finish.

What the picture cannot show #

A drawing shows one circle at one radius, and the theorem is about all of them.

More particularly, the pictures cannot show the reduction that makes the general theorem work. A number is a sum of two squares exactly when every prime $\equiv 3 \pmod 4$ in its factorisation appears to an even power — so $18 = 2 \times 3^2$ works, and $6 = 2 \times 3$ does not, and the difference is an exponent rather than anything visible on a circle. The proof is that norms multiply, so representations compose; and a prime $\equiv 3$ appearing an odd number of times cannot be absorbed.

That statement is about factorisations, and a factorisation is not a feature of a picture. The lattice shows the answer for one number at a time and hides the mechanism, which is the standing trade in this field: the drawings show instances and the arguments quantify over everything.

The figures also flatten a distinction worth keeping. The circle of radius $\sqrt{25}$ has twelve points, but only two essentially different representations — $25 + 0$ and $16 + 9$ — with the rest produced by signs and swaps. Jacobi’s formula counts all twelve, which is the right thing for the lattice and the wrong thing if the question is about representations, and the two counts differ by a factor that depends on whether zero or a repeat is involved.

A proof in one sentence #

There is a proof of the hard half so short that it is worth setting out, both because it is remarkable and because it shows how little the geometry is really needed.

Zagier’s proof, published in 1990 on a single line, considers the finite set of triples of positive whole numbers $(x, y, z)$ with $x^2 + 4yz = p$. It exhibits an involution on that set — a map that is its own inverse — given by a three-case formula, and observes that it has exactly one fixed point. An involution on a finite set pairs everything up except its fixed points, so the set has odd size. Then the obvious involution $(x, y, z) \mapsto (x, z, y)$ must also have a fixed point, since a map pairing things up on a set of odd size cannot pair everything. A fixed point of that map has $y = z$, so $p = x^2 + 4y^2 = x^2 + (2y)^2$, and there are the two squares.

The whole argument is a parity count on a set nobody would think to write down, and it produces the representation without descent, without Gaussian integers, and without any statement about $-1$ being a square. It is also completely opaque: the complicated involution can be verified in a few lines and gives no sense whatever of why it exists.

That opacity is instructive. A short proof is not the same as an explanatory one, and the descent argument — longer, older, and messier — is the one that says what is going on. The lattice picture at the top of this essay explains nothing and shows everything; Zagier’s proof proves everything and shows nothing; and a subject needs both kinds.

What it is used for #

The result is not an ornament. Deciding which numbers are sums of two squares is the first case of a question that runs through the whole of algebraic number theory: given a form like $x^2 + y^2$, or $x^2 + 2y^2$, or $x^2 + xy + y^2$, which numbers does it represent?

Each such form has an answer of the same shape — a condition on the prime modulo something — and the something is the discriminant of the form. $x^2 + y^2$ answers to $4$; $x^2 + 3y^2$ answers to $3$; and the general statement, that the primes represented by a form are determined by congruence conditions, holds for exactly one class of forms per discriminant and fails as soon as there is more than one. That failure is measured by the class number, which is the same quantity that measures failure of unique factorisation, and the connection is not a coincidence: both are counting how many essentially different lattices share a discriminant.

The practical descendant is factoring. If $n$ has two essentially different representations as $a^2 + b^2$, then $n$ is composite, and the two representations produce a factorisation directly — a fact used by Euler and still the basis of a factoring method for numbers of the right shape. A question about circles turns into a test for primality, which is not a use anybody would have predicted from the figures.

Three squares, four squares, and where the pattern stops #

Two squares turn out to be a peculiar case, and comparing it with three and four is the fastest way to see why.

Four squares. Every whole number is a sum of four squares. Lagrange proved it in 1770 and the statement has no exceptions and no conditions at all — $7 = 4+1+1+1$, $23 = 9+9+4+1$, and so on forever. The reason four is enough is that the four-square identity, an ancestor of quaternion multiplication, shows the sums of four squares are closed under multiplication, so the theorem reduces to primes and the primes are handled by descent.

Three squares. Every number except those of the form $4^a(8b + 7)$ is a sum of three squares. Legendre proved it and the excluded set is exactly what a modular argument predicts: modulo eight, three squares cannot make seven. So three squares has a clean condition, and unlike the two-square case it is a condition on the number rather than on its factorisation.

Two squares. The condition is on the factorisation — every prime $\equiv 3 \pmod 4$ to an even power — and cannot be stated as a congruence on $n$ alone. That is the anomaly, and it is why this case is the interesting one: with only two squares available there is not enough room for the obstructions to cancel, and the answer becomes sensitive to how the number is built rather than to what it looks like.

The pattern across the three says something about how these questions behave. More squares means more freedom, more freedom means fewer obstructions, and past four there is so much freedom that the question stops being interesting. It is the same shape of result as Waring’s problem at higher powers, where every exponent has its own threshold and the thresholds are what the subject is about.

Where the ladder goes next #

The same circle carries a different question. This essay asked which lattice points sit on a circle of a given radius; every triple on one circle asks which rational points sit on the unit circle, and the answer parametrises every Pythagorean triple there is.

The other direction runs through the Gaussian integers into the general theory of which primes split in which rings, and the first real theorem there is quadratic reciprocity — which decides, for any two odd primes, whether each is a square modulo the other, and does it by counting the lattice points in a rectangle.