Three triangular numbers, and no fewer

The triangular numbers are 0, 1, 3, 6, 10, 15, 21, 28 — the dots that stack into a triangle one row at a time, and the half of a rectangle that two copies of the staircase make. Every whole number can be written as a sum of three of them, allowing 0: $4 = 3 + 1 + 0$, $5 = 3 + 1 + 1$, $20 = 10 + 10 + 0$, $100 = 36 + 36 + 28$.

Pierre de Fermat claimed in 1638 that every number is a sum of three triangular numbers, four squares, five pentagonal numbers, and in general $k$ numbers of any $k$-sided polygonal kind, and said he had a proof he would write out in a book. He never did. Carl Friedrich Gauss proved the triangular case on 10 July 1796, at eighteen, and recorded it in his mathematical diary as ΕΥΡΗΚΑ num = Δ + Δ + Δ. Lagrange had proved the four-square case in 1770, and Cauchy proved the rest of Fermat’s claim in 1813.

The statement is about triangles. The proof is entirely about squares, and the translation between them is a picture.

Eight triangles and a dot #

Take the square with side $2k + 1$. Remove its centre cell. What is left can be cut into four rectangles of $k$ by $k + 1$ arranged round the centre like the blades of a pinwheel, and each rectangle splits along its diagonal staircase into two copies of the triangular number $T_k = k(k+1)/2$. So

$$8\,T_k + 1 = (2k+1)^2.$$

Every odd square is one more than eight times a triangular number, and every triangular number comes from an odd square this way. The identity is Diophantus’s, and it converts any statement about triangular numbers into a statement about odd squares: multiply by eight and add the right number of ones.

Two triangular numbers are two squares #

Apply the translation to a sum of two. If $n = T_a + T_b$, then

$$8n + 2 = (2a+1)^2 + (2b+1)^2.$$

The two odd numbers $2a + 1$ and $2b + 1$ can be traded for their half-sum and half-difference, $a + b + 1$ and $a - b$, and a line of algebra turns the equation into

$$4n + 1 = (a + b + 1)^2 + (a - b)^2.$$

Conversely, any way of writing the odd number $4n + 1$ as a sum of two squares uses one odd and one even square, and running the same algebra backwards recovers $a$ and $b$. So $n$ is a sum of two triangular numbers exactly when $4n + 1$ is a sum of two squares, and which numbers are sums of two squares has a complete answer: those in which every prime of the form $4k + 3$ appears to an even power.

The grid shows the gaps multiplying. Five is missing, then 8 is not — $33 = 3 \cdot 11$, two primes of the bad form, but each once, so 8 is missing too — and by the end of the grid about three numbers in eight are missing. The gaps are not random: they sit wherever $4n + 1$ picks up a prime like 3, 7, 11 or 19 an odd number of times, and those primes divide $4n + 1$ in regular arithmetic progressions, so the gaps line up along diagonals of the grid.

Two thin out to nothing #

A quarter of numbers below two hundred being unreachable looks like a stable proportion. It is not.

The fall is the Landau–Ramanujan theorem in disguise. Almost no number is a sum of two squares: the count below $x$ is about $K x/\sqrt{\log x}$, because a number has to avoid every prime of the form $4k + 3$ to an odd power, and the chance of avoiding all of them shrinks like $1/\sqrt{\log x}$. The numbers $4n + 1$ are a slice of the same population, and they thin out at the same rate.

So the share of numbers that are sums of two triangular numbers tends to nought — so slowly that at a million it is still 0.4, and at $10^{50}$ it would still be above a tenth. That is the whole reason the question of three is not settled by the question of two. Two triangular numbers reach almost every small number and almost no large ones, in the sense of proportions, and a third is not a luxury but a necessity.

Three triangular numbers are three odd squares #

Apply the translation to three:

$$n = T_a + T_b + T_c \quad\Longleftrightarrow\quad 8n + 3 = (2a+1)^2 + (2b+1)^2 + (2c+1)^2.$$

And the three squares on the right are forced to be odd by arithmetic alone. Every square leaves remainder 0, 1 or 4 when divided by 8, and the only way three of those can add to 3 is $1 + 1 + 1$ — which happens exactly when all three squared numbers are odd. So $n$ is a sum of three triangular numbers exactly when $8n + 3$ is a sum of three squares of any kind.

That reduces Gauss’s Eureka to a question about sums of three squares, and that question has a complete answer: the three-square theorem, stated by Legendre in 1798 and proved completely by Gauss in 1801. A number is a sum of three squares unless it has the form $4^a(8b + 7)$.

The numbers $8n + 3$ leave remainder 3 when divided by 8. They are odd, so the $4^a$ is $1$, and they are not $7$ modulo $8$. No number of the form $8n + 3$ is an exception, so every one is a sum of three squares, and therefore every $n$ is a sum of three triangular numbers.

Why three squares are so much harder than two or four #

The chain of translations is short. The theorem at the end of it is not, and the contrast with its neighbours is instructive.

Sums of two squares are governed by factorisation: a number is one exactly when its bad primes pair off, a fact that follows from factoring in the Gaussian integers, and the squares themselves can be produced by a Euclidean algorithm. Sums of four squares are governed by an identity: the product of two sums of four squares is again a sum of four squares, by Euler’s four-square identity, so it is enough to check primes, and every prime works by a descent argument. Both are multiplicative.

Sums of three squares have no such structure. The product of two sums of three squares need not be one: $3 = 1 + 1 + 1$ and $5 = 4 + 1 + 0$, but $15$ is $8 \cdot 1 + 7$ and is not a sum of three squares. There is no identity to multiply with and no factorisation to reduce to primes. Gauss’s proof went through his theory of ternary quadratic forms, and every later proof has needed comparably heavy tools — Dirichlet’s theorem on primes in arithmetic progressions, or the geometry of lattices in three dimensions. The obstruction $4^a(8b+7)$ is easy to see. Squares leave remainders 0, 1 or 4 modulo 8, and no three of those add to 7, so no number $8b + 7$ is a sum of three squares. And if a multiple of 4 is a sum of three squares, all three squares must be even — any odd one would leave a remainder that no choice of the other two can cancel modulo 4 — so the number divided by 4 is also a sum of three squares, and an obstruction for $8b+7$ passes up to $4(8b+7)$, $16(8b+7)$ and so on. That it is the only obstruction is the deep part.

The same shape — a congruence obstruction that is easy, and a proof that nothing else obstructs that is hard — runs through the question of which primes a quadratic form takes, where reciprocity supplies the congruences and the theory of forms has to show they are sufficient.

So the one-line statement Gauss wrote in his diary rests on the hardest of the three classical square theorems, entered through a residue class chosen so that its single obstruction can never apply.

Why the number of pieces is the number of sides #

Fermat’s full claim was that $k$ numbers of any $k$-sided polygonal kind are always enough, and the smallest numbers already show why nothing less can work.

For triangles, the number 5 needs three: the triangular numbers below it are 0, 1 and 3, and no two of those add to 5. For squares, 7 needs four: the squares below it are 0, 1 and 4, and $4 + 1 + 1 + 1$ is the only way. For pentagonal numbers — 0, 1, 5, 12, 22 — the number 9 needs five, $5 + 1 + 1 + 1 + 1$, and for hexagonal numbers 11 needs six. Each polygonal sequence starts with 0, 1 and then a jump to $k$, so the number just below $2k$ has to be built from one copy of $k$ and a pile of ones, and the pile forces the count up to the number of sides.

That lower bound is trivial; Fermat’s claim is that it is also the upper bound, for every number however large. Cauchy’s proof of 1813 reduced the general case to sums of three and four squares, and showed that every number is a sum of $k$ polygonal numbers of $k$ sides of which all but four may be taken to be 0 or 1. The four-square and three-square theorems do all of the work; the extra pieces only ever fill in with ones. The triangular case is the one where the count is smallest and the translation into squares cleanest, which is why it is the one Gauss celebrated.

An exact count for four, and none for three #

Adding a fourth triangular number changes the character of the question completely, and the change shows why three is the difficult case rather than merely the boundary one.

The number of ordered ways to write $n$ as a sum of four triangular numbers is exactly $\sigma(2n+1)$, the sum of the divisors of $2n + 1$ — a theorem of Legendre. For $n = 0$ that is $\sigma(1) = 1$, the single representation $0+0+0+0$. For $n = 1$ it is $\sigma(3) = 4$, the four places the single 1 can go. For $n = 2$ it is $\sigma(5) = 6$, the six ways to place two ones. The formula is a statement about the divisor rectangle of $2n+1$, and it comes from an identity between infinite products, of the kind that also hides every partition in a product.

For three triangular numbers no formula of that kind exists. The count is governed by class numbers, which are not multiplicative functions of anything simple, and the ragged bars below are the visible sign. Four pieces give a count that is a divisor sum; three give a count that is a class number, and the difference between those two kinds of arithmetic is the difference between a formula anyone can evaluate and one of the central open subjects of number theory.

How many ways #

Every number is a sum of three triangular numbers; most are sums in several ways.

The bars grow on average with $n$, but raggedly, and the ragged part has an explanation that reaches into the deepest part of Gauss’s work. The number of ways to write a number as a sum of three squares is tied to the class number of a quadratic form — the count of genuinely different quadratic forms of a given discriminant — and class numbers fluctuate wildly from one discriminant to the next while growing roughly like the square root of the discriminant. The bar chart is, up to a simple factor, a chart of class numbers for the discriminants $-(8n+3)$.

The numbers with exactly one representation stop at 53: no larger number has a single decomposition, and a search to thirty thousand finds none. That they stop is the statement that only finitely many of those class numbers are very small, and pinning down exactly which are small was Gauss’s class number problem, whose small cases took until the second half of the twentieth century to settle. A question about stacks of dots with a unique arrangement is a question about the rarest discriminants there are.

What the grids and bars cannot establish #

Every figure here covers numbers up to a few hundred, or up to a million for the density. Gauss’s theorem is about every number, and no picture reaches every number. The bars show that 0 to 120 each have a representation; the three-square theorem shows that every number does.

The density figure shows the share of sums of two triangular numbers falling to 0.4 by a million, and the claim that it falls to nought is Landau’s theorem, not an observation. The fitted curve matches over four decades; a fit over four decades is compatible with many other rates of decay, and it is the theorem that picks out $1/\sqrt{\log x}$.

And the eight-triangles picture is exact only for the identity it draws. It shows why $8T_k + 1$ is a square. It does not show why a number of the form $8n + 3$ is a sum of three squares, which is the hard step, and there is no picture of that step anyone has found.

A finite check that settles every number #

There is a modern way to see how much the three-square theorem is doing, and it turns a statement about infinitely many numbers into a finite list.

Take any quadratic form in several variables with whole-number coefficients whose matrix has whole-number entries — $x^2 + y^2 + z^2 + w^2$, or $x^2 + 2y^2 + 5z^2 + 5w^2$ — and which is positive for every non-zero input. In 1993 John Conway and William Schneeberger found, and in 2000 Manjul Bhargava proved, that such a form represents every positive whole number as soon as it represents 1, 2, 3, 5, 6, 7, 10, 14 and 15. Nine numbers decide infinitely many. For forms whose cross terms may have odd coefficients, Bhargava and Jonathan Hanke proved in 2005 that the corresponding list has twenty-nine entries, the largest of them 290.

The four-square theorem is the simplest instance: $x^2 + y^2 + z^2 + w^2$ reaches all nine critical numbers, so it reaches everything. A form in three variables can never pass the test — every positive ternary form misses infinitely many numbers, as $x^2 + y^2 + z^2$ misses the numbers $4^a(8b+7)$ — which is another way of saying that three is too few squares to reach everything, and that the triangular numbers reach everything only because the translation lands in a residue class the obstruction avoids.

Still open: which numbers a lopsided form misses #

The three-square theorem answers completely which numbers $x^2 + y^2 + z^2$ reaches. Change the coefficients and the question becomes much harder, and one small case of it has been open for a century.

Ramanujan listed the odd numbers that $x^2 + y^2 + 10z^2$ fails to represent: 3, 7, 21, 31, 33, 43, 67, 79, 87, 133, 217, 219, 223, 253, 307, 391, and more. In 1997 Ken Ono and Kannan Soundararajan proved that the complete list of such odd numbers is those sixteen together with 679 and 2719 — provided the generalised Riemann hypothesis is true. Without that hypothesis nobody can rule out a nineteenth exception somewhere beyond the range checked. The obstruction for the three-square form is a pair of congruence conditions visible at a glance; for this form the obstructions are sporadic, and proving that no more exist needs control over the zeros of $L$-functions that is currently out of reach.

Dots, squares and the last obstruction #

The triangular numbers are the simplest figures there are, and a statement about adding three of them sounds like something a patient child could check. It is checkable number by number, and it is true for every number, and the reason it is true passes through odd squares, residues modulo eight, and a theorem about ternary forms that Gauss needed a book to prove.

The two-triangle version shows why the third is necessary: two reach a share of the numbers that falls, very slowly, to nothing. The three-triangle version shows why three suffice: multiply by eight, add three, and the result lands in the one residue class where sums of three squares have no obstruction at all.