Five pyramids for every number

The essays on figurate numbers so far have been about flat figures: squares as stacks of odd numbers, triangles, pentagons, and the quadratic forms that generalise them. Each had a theorem of the same shape: every number is a sum of a fixed small count of such figures — three triangles, four squares, five pentagons — with a few exceptions that need one more. Gauss proved the triangles in 1796 and Cauchy proved Fermat’s general claim in 1813. This essay goes up a dimension, to numbers that count balls in a solid pile, and the same kind of statement turns from a theorem into a conjecture that has stood for a hundred and seventy years.

The tetrahedral numbers count balls stacked in a triangular pyramid: one ball, then a triangle of three under it, then a triangle of six, and so on, so that the $k$-th pyramid holds

$$\mathrm{Te}(k) = 1 + 3 + 6 + \cdots + \tfrac{k(k+1)}{2} = \frac{k(k+1)(k+2)}{6} = \binom{k+2}{3}$$

balls: 1, 4, 10, 20, 35, 56, 84, 120 and on. They are the third diagonal of Pascal’s triangle, as the run that lands one place along showed, and the sums of the triangular numbers, as the staircase of sums of powers would compute them. In 1850 Frederick Pollock, a judge with a taste for arithmetic, conjectured that every whole number is a sum of at most five tetrahedral numbers.

Counting every number to ten million #

The question for each number $n$ is the fewest tetrahedral numbers that add up to it, and it can be answered for every $n$ at once. Below ten million there are 390 tetrahedral numbers. Write down, as a long row of ten million bits, which numbers are sums of one of them: 390 bits are set. Shift that row by every tetrahedral number and combine the shifted copies with an OR, and the result marks every sum of two; repeat for three, four and five. Each step is 390 shifts of a row of ten million bits, which a computer does in a fraction of a second because the bits are processed thirty-two at a time. A number’s answer is the first step at which its bit appears.

Below ten million, 390 numbers are tetrahedral themselves, 66,593 need two, 4,455,804 need three, 5,476,972 need four, and 241 need five. None needs six. The first that needs five is 17: the tetrahedral numbers below it are 1, 4 and 10, and the best that can be done is $10 + 4 + 1 + 1 + 1$. The last is 343,867, which is $341{,}376 + 1{,}771 + 680 + 20 + 20$ and cannot be written with four. From 343,868 to 9,999,999 every number needs four or fewer.

Why seventeen needs five #

The small exceptions can be checked by hand, and doing so shows where they come from. The pyramids not larger than 17 are 1, 4 and 10, and a sum of them is decided by how many 10s and 4s it uses. With one 10, the remaining 7 must be made of 4s and 1s, and the best is $4 + 1 + 1 + 1$, four more: five in all. With no 10, the 17 must be made of 4s and 1s, and the best is four 4s and a 1: five again. There is no third option, so 17 needs five.

Twenty-seven goes the same way with one more pyramid available. The pieces are 1, 4, 10 and 20; with a 20 the remaining 7 needs four more; with two 10s the remaining 7 again needs four, making six; with a single 10 the remaining 17, made only of 4s and 1s, needs five more, six in all; and without 10 or 20 the best is six 4s and three 1s. Five is the minimum. In both cases the trouble is the same: the remainder after the large pyramids lands on 7, a number that the small pyramids 1 and 4 cover badly, and there is no medium-sized pyramid to absorb it. As numbers grow there are more pyramids of every size to choose from, the awkward remainders can be dodged, and the exceptions thin out — until, after 343,867, they apparently stop.

Greed needs nine #

The obvious way to write a number as a sum of pyramids is greedily: take the largest pyramid that fits, subtract it, and repeat. It is how change is made in coins, and for coins of sensible sizes it is optimal. For pyramids it is not. Greed writes 17 as $10 + 4 + 1 + 1 + 1$, which happens to be best, but it writes 343,867 as a sum of seven pyramids, where five suffice, and below a million there are numbers for which greed takes nine — the first is 35,977 — although none needs more than five. Over all numbers up to a million the greedy count is most often six, against a true minimum that is almost always three or four.

Greed fails because the largest pyramid below $n$ leaves a remainder that can be as large as the gap to the next pyramid, which grows like $n^{2/3}$, and that remainder is then attacked with the same short-sighted rule. The right answer usually takes a pyramid well below the largest, so that the remainders of later steps land on pyramids exactly. Finding it needs the sets of all sums, not a sequence of choices — which is why the computation builds every sum of two, three and four pyramids rather than following any number down a greedy path. Coin systems for which greed is always optimal have been characterised exactly; pyramids are far from being one.

The 241 #

The list is old. Herbert Salzer and Norman Levine computed it in 1958 on one of the first electronic computers and found the same 241 numbers, the last 343,867, with none further out as far as they could search; later searches have pushed the frontier into the billions and found nothing new. The figure plots them on a logarithmic scale: they are spread over five orders of magnitude, half of them below about 5,600, and they thin out steadily until the last.

The shape is familiar from the flat figures. Three triangular numbers suffice for every number, but two do not, and the numbers needing three never stop; pentagonal numbers need five for six exceptional numbers and four for every number past them, as far as anyone has looked. Every such problem divides into two questions. What is the smallest count that works for every number — the problem’s $g$, in the notation of Waring’s problem — and what is the smallest that works for every number from some point on, its $G$? For tetrahedral numbers the evidence says $g = 5$, with 343,867 the last exception, and Pollock’s conjecture is that statement.

What is proved #

The best theorem is eight. George Watson proved in 1952 that every number is a sum of at most eight tetrahedral numbers, by an argument that writes tetrahedral numbers in terms of cubes — $\mathrm{Te}(k) = \frac{(k+1)^3 - (k+1)}{6}$ — and uses what is known about sums of cubes. Between Watson’s eight and Pollock’s five the gap is three, and it has not narrowed since.

The reason it is hard is the dimension. For a triangular or square number there is an identity — Gauss’s three triangles, Lagrange’s four squares — rooted in the arithmetic of quadratic forms, which have a rich theory of exactly which numbers they represent, the subject of the fifteen theorem. Tetrahedral numbers are cubic in $k$, and sums of cubic polynomials have no comparable theory. The tool that works for them is the Hardy–Littlewood circle method, which counts representations analytically and proves that every sufficiently large number is a sum of a bounded number of them; but its bounds on “sufficiently large” are astronomically larger than any search can reach, and it cannot by itself say anything about every number. That combination — a theorem for all large numbers that cannot be checked below its threshold, and a computation for small numbers that cannot reach the threshold — is the same impasse as Waring’s problem for cubes.

Most numbers need four #

Past 343,867 the question is how many numbers need four rather than three, and the figure follows the shares window by window. Among the hundreds about two thirds need three or fewer; by ten million it is under half, and the share needing exactly four has climbed past one half, slowly, without showing any sign of turning round.

That is what counting predicts. There are about $(6n)^{1/3}$ tetrahedral numbers below $n$, so about $n/6$ combinations of three of them — ignoring order — fall below $n$, and they cannot cover all $n$ numbers; even without repetitions in the sums, at least a share of the numbers must be missed by three. With four tetrahedral numbers the count of combinations below $n$ grows like $n^{4/3}$, far more than $n$, so there is room for every large number to be hit. The conjecture that four suffice for every sufficiently large number — that $G = 4$ — is natural, and it is as unproved as Pollock’s five.

Three summands against four #

The counting can be checked directly. The figure counts, for every number up to 200,000, the ways of writing it as a sum of three tetrahedral numbers and of four, order ignored, and averages them over windows. With three summands the average is flat at about 0.65 to 0.7 — fewer than one way per number on average, which is why about half the numbers have none. With four the average grows steadily, from about 2.7 near a thousand to 16 near 200,000, rising like $n^{1/3}$ as the counting says.

A growing average is not a proof that every number is hit, and that is the heart of the difficulty. The ways are not spread evenly: arithmetic biases — residues modulo small numbers that tetrahedral numbers avoid or favour — can starve particular numbers of representations while the average grows. The circle method controls those biases on average and proves the asymptotic count, but the error terms it leaves are too large to rule out a sparse set of unlucky numbers. Every additive problem of this kind lives in the gap between “almost every number” and “every number”, and the computations here, which find no number needing six or any large number needing five, are evidence about the gap rather than a way across it.

One dimension up each time #

The triangular, tetrahedral and pentatope numbers are three successive diagonals of Pascal’s triangle — $\binom{k+1}{2}$, $\binom{k+2}{3}$, $\binom{k+3}{4}$ — counting balls in a triangle, a pyramid and its four-dimensional analogue. The same computation, run on all three to two million, shows the price of each dimension. Triangles never need more than three, which is Gauss’s theorem. Tetrahedral numbers need five, for the 241. The four-dimensional numbers need as many as eight — for six numbers, the last 774 — and numbers needing seven are still turning up at one and a half million, so the count that suffices for every large number is not even visible yet in that range.

The counting heuristic explains the climb. Numbers of the form $\binom{k+d-1}{d}$ below $n$ are about $n^{1/d}$ in number, so $s$ of them make about $n^{s/d}$ sums, and covering every number needs $s$ at least $d$ — more in practice, because the sums cluster. The flat case has $d = 2$ and its answer, three, sits just above. Each extra dimension thins the supply of summands, and the exceptional small numbers, which have only the few smallest figures to work with, are the ones that pay.

The cannonball problem #

Pyramids of balls had a practical life before Pollock: cannonballs were stacked in them, in triangular and square piles, and counting a pile from its base was a gunner’s arithmetic. The square-based pile, with $1 + 4 + 9 + \cdots + k^2$ balls, raises a question that sounds like a puzzle and turned out to be deep. Édouard Lucas asked in 1875 when a square pile can be rearranged into a single flat square layer — when $1 + 4 + \cdots + k^2$ is itself a perfect square. It is for $k = 1$, trivially, and for $k = 24$, where the pile of 4,900 balls makes a square of side 70. George Watson proved in 1918 that there are no others; the proof needed elliptic functions, and the problem is equivalent to finding the whole-number points on an elliptic curve, the same kind of curve that decides which numbers are the areas of right triangles.

The tetrahedral numbers have their own questions of this kind — which of them are also triangular, which are also squares — and each comes down to whole-number points on a curve. The additive question of this essay is of a different nature: not which single pyramid has a property, but how many pyramids it takes to make every number. The cannonball problem was solved with the theory of curves; Pollock’s conjecture would need a theory of sums that does not yet exist for cubic shapes.

Pollock’s other conjecture #

Pollock made a second conjecture in the same paper, about the octahedral numbers $\frac{k(2k^2+1)}{3}$: 1, 6, 19, 44, 85, 146, …, which count balls stacked in two square pyramids placed base to base. He guessed that every number is a sum of at most seven of them. The same bit-set computation, run to ten million, confirms it: twelve numbers need seven — 17, 35, 55, 61, 73, 79, 80, 200, 206, 213, 225 and 309 — and every other number needs six or fewer. Most need four; only 168 need six, and 45,966 need five.

The octahedral conjecture has the same status as the tetrahedral one: true for every number anyone has checked, implied for large numbers by the expected behaviour of the circle method, and unproved. The two problems are not independent curiosities; they are the first cases of a general question — for a polynomial that takes whole-number values, how many of its values are needed to write every number — that Waring’s problem asks for the powers and that has no general answer.

What the computations show and assume #

Every count is exact. The bit-set method marks a number as reachable with $s$ summands exactly when it is, and the fewest needed is the first $s$ at which it is marked; the tally for each $s$ up to ten million follows. The representation shown for 343,867 is found by search, and the absence of a four-term representation is the bit set’s verdict. The averages of representation counts are exact for each number, averaged over windows. What none of this shows is anything past ten million: the conjectures are about every number, and the computation stops.

Still open: Pollock’s conjectures #

Is every positive integer a sum of at most five tetrahedral numbers? Is every positive integer a sum of at most seven octahedral numbers? Both have been open since 1850. For the tetrahedral numbers the known bound is Watson’s eight; whether the 241 exceptions needing five are all, and whether every sufficiently large number needs only four, are open too, with the evidence from searches into the billions on the side of Pollock and of four. A proof would need either a new identity of the kind that settled the flat cases — something that writes every number as a sum of five pyramids by a formula — or an effective form of the circle method sharp enough to bring its threshold down to where computation can meet it.

Pyramids instead of triangles #

Every number below ten million is a sum of at most five tetrahedral numbers, and only 241 need five — from 17 to 343,867, the same list Salzer and Levine found in 1958 — while most large numbers need four and the share needing four keeps creeping up. Counting explains the pattern: three pyramids leave about half of the numbers unreached, four provide more ways than there are numbers and more every decade. The flat figures had identities that made such statements theorems; the solid ones have only the circle method, which proves bounds for large numbers it cannot check, and so Pollock’s five pyramids and seven octahedra remain conjectures that every computation supports.