Nine cubes for two numbers

Thirty-three as three cubes allowed negative cubes, and the problem became one about cancellation: two enormous cubes nearly equal, and a third to make up the difference. It noted in passing the problem it was not about. With positive cubes only, nothing cancels, the cubes below a number are few, and the question is the one Edward Waring asked in 1770 — how many cubes does it take to make every number?

The answer is nine, and it is the wrong question. Nine is needed for exactly two numbers. The interesting number is the count that suffices for every number past some point, which is not nine, not eight, and probably not seven, six or five. This essay computes the least number of cubes for every number up to a million and a half and reads the problem off the result.

The least number of cubes, for every number at once #

The computation is the plainest kind. Let $c(n)$ be the fewest positive cubes adding to $n$. Then $c(0) = 0$, and for every other $n$, $c(n)$ is one more than the least $c(n - k^3)$ over the cubes $k^3 \le n$, because a cheapest sum for $n$ has some cube in it and what is left must itself be made as cheaply as possible. Filling in $c$ from $1$ upward takes, for each number, one look per cube below it — about a hundred and fourteen looks at a million and a half — and gives the exact answer for every number in the range.

The recursion matters because the obvious shortcut is wrong. Taking the largest cube that fits, then the largest that fits in what is left, is the greedy rule, and for building a spanning tree the greedy rule is provably optimal. For cubes it is not. Greedy writes 239 as $216 + 8 + 8 + 7 \cdot 1$, ten cubes, one more than the best; it writes 454 as $343 + 64 + 27 + 8 + 8 + 4 \cdot 1$, nine cubes against eight; and it needs eleven for 1,290,740, which six will do. The cheapest sum often avoids the largest cube entirely, so a computation that wants the true count has to try them all, which is what the recursion does at a cost of one comparison per cube.

The result, counted:

• nine cubes are needed by exactly two numbers, 23 and 239;
• eight by fifteen numbers: 15, 22, 50, 114, 167, 175, 186, 212, 231, 238, 303, 364, 420, 428 and 454;
• seven by 121 numbers, the last of them 8,042;
• six by 3,922 numbers, the last of them 1,290,740;
• five by many, still common at a million and a half.

The first three lines are old. Arthur Wieferich proved in 1909, with a gap Aubrey Kempner filled in 1912, that nine cubes always suffice, so the count every number needs, written $g(3)$, is exactly nine. Leonard Dickson showed in 1939 that 23 and 239 are the only numbers needing nine. The fourth line, the last number needing six, is the kind of fact only computation finds, and the run here reaches it with a margin.

Why small numbers are the expensive ones #

The expensive numbers are all small, and the reason is visible in the grid. A number needs many cubes when the cubes below it are few and badly placed. Below 600 there are only eight cubes — 1, 8, 27, 64, 125, 216, 343, 512 — and the larger ones are far apart. A number sitting just below a cube cannot use it, and has to be made of the cubes below, which are much smaller.

That is 23 exactly. It is four short of 27, so the only cubes available are 8 and 1, and the best that can be done is two eights and seven ones: nine cubes. The grid shows the same thing happening at the other dark cells. They cluster just below cubes and in the long stretches where the next cube is still far off and the previous ones are too small to fill the space efficiently.

239 is the same accident on a larger scale. It sits 23 above 216 and 104 below 343, and $239 - 216 = 23$ costs nine on its own; without 216 the best is built from 125s, 64s and 27s, and the search finds exactly two ways to do it in nine — $125 + 3 \cdot 27 + 4 \cdot 8 + 1$ and $2 \cdot 64 + 4 \cdot 27 + 3 \cdot 1$ — and none in eight. 454 is the last number that cannot be done in seven: it has two cheapest sums, $343 + 4 \cdot 27 + 3 \cdot 1$ and $125 + 5 \cdot 64 + 8 + 1$, both of eight.

Twenty-three is not an accident peculiar to cubes. Leonhard Euler’s son Johann Albrecht noticed the general shape: for $k$-th powers take $n = 2^k \lfloor (3/2)^k \rfloor - 1$, which is below $3^k$, so the only powers available are $1$ and $2^k$. The best is then $\lfloor (3/2)^k \rfloor - 1$ copies of $2^k$ and $2^k - 1$ ones, a total of $2^k + \lfloor (3/2)^k \rfloor - 2$. For squares that is $n = 7$, needing four; for cubes it is $n = 23$, needing nine; for fourth powers it is $79$, needing nineteen. The conjecture that this lower bound is always the true $g(k)$ is called the ideal Waring theorem, and it is known to hold for every $k$ for which a condition on the fractional part of $(3/2)^k$ holds — checked for all $k$ up to hundreds of millions, with Kurt Mahler’s theorem that at most finitely many $k$ could fail it.

So $g(3) = 9$ is a fact about 23 and 239 and nothing else. It is a statement about the arithmetic of a handful of small numbers, true because those numbers are awkwardly placed among the first few cubes, and it would not change if every number past 240 needed only four. That is the sense in which nine is the wrong question. The same thing happens for the polygonal numbers in six numbers that need five pentagons and for the pyramidal numbers in five pyramids for every number: the count for all numbers is set by a few small exceptions, and the count for large numbers is a different and harder quantity.

The count for large numbers #

That second quantity is written $G(3)$: the least $s$ such that every sufficiently large number is a sum of $s$ positive cubes. The table above already bounds it from above: past 454 nobody needs eight, past 8,042 nobody in range needs seven, past 1,290,740 nobody in range needs six.

The lower bound is four, and it is the same congruence that rules numbers out in the three-cubes problem. A cube leaves 0, 1 or 8 on division by 9, so three cubes leave a remainder between $-3$ and $3$, and a number leaving 4 or 5 on division by 9 needs at least four. Two numbers in every nine are of that kind, so infinitely many numbers need four and $G(3) \ge 4$.

What is proved above is less than the computation shows. Yuri Linnik proved in 1943 that every sufficiently large number is a sum of seven cubes, so $G(3) \le 7$, and Samir Siksek made it explicit in 2016: every number above 454 is a sum of at most seven positive cubes, a theorem whose proof finished with a large computation. Nothing better is proved. $G(3)$ is 4, 5, 6 or 7, and nobody knows which.

The computation’s verdict is plain. Six is needed for the last time at 1,290,740 within the range, and five is thinning. Jean-Marc Deshouillers, François Hennecart and Bernard Landreau, extending the computation far beyond this range in 2000, conjectured from the trend that the last number needing five is 7,373,170,279,850, which would make $G(3) = 4$. The hero figure carries that number as a dashed bar because it is a conjecture: it is the largest number found needing five, and the claim that it is the last rests on a model of how the counts fall.

Five thinning, four taking over #

The shares in doubling windows show the trend that conjecture is drawn from. In the window from 64 to 127 the counts are spread almost evenly between three or fewer, four, five and six. By the window from 16,384 to 32,767, five is the commonest count at about 40 per cent and six has fallen to a few. By the last window, half a million to a million, six has all but vanished, five is down to about a quarter and falling, and four has risen to about two-thirds.

Three or fewer holds steady around a tenth, and cannot do much better: the sums of three positive cubes below $N$ are at most the number of triples of cubes, about $N/6$, so at most a sixth of numbers are sums of three cubes. Most numbers must need four or more, and the question is whether the share needing five or more falls all the way to nothing.

The curve for five is the one that matters, and it falls slowly. That slowness is what keeps $G(3) = 4$ out of reach of computation alone: a share that halves every few doublings can leave a last straggler at thirteen digits, which is where Deshouillers and his collaborators put it.

Why four should be enough #

The reason to believe four is a count of opportunities. The quadruples of positive whole numbers $(a, b, c, d)$ with $a^3 + b^3 + c^3 + d^3 \le N$ are the lattice points inside a curved region of four-dimensional space, and their number is close to the region’s volume, which is

$$\frac{\Gamma(4/3)^4}{\Gamma(7/3)}\, N^{4/3}.$$

Spread over the $N$ numbers below $N$, that gives an average of about $0.712\, N^{1/3}$ ordered representations for a number near $N$. The figure counts them exactly in windows of a thousand: 6.8 per number near a thousand, 31.7 near a hundred thousand, 70.8 near a million, against predictions of 8.2, 33.1 and 71.2. The prediction is from a continuous volume and the count is of lattice points, and they converge as the region grows.

So four cubes land on a typical number many times, and more often the larger it is. The same count for three cubes gives an average that settles at a constant below one, which is why three cannot be enough for almost every number. With four, a number would need to be avoided by dozens of representations that are, on this count, landing at random — and then by hundreds, and then by thousands.

That is the heuristic and it is not a proof, for the reason the heuristic that cannot be a proof gives in another setting. An average over a window says nothing about whether some particular numbers are skipped, and there are numbers that are: every number needing five is a number the four-cube sums miss entirely, despite an average of dozens. What a proof needs is control over how evenly the sums spread among the residues and sizes, and for four cubes the available methods — the Hardy–Littlewood circle method in its strongest forms — fall short. The circle method proves that almost every number is a sum of four cubes, in the sense that the exceptions up to $N$ are a vanishing share; it cannot rule out an infinite thin set of exceptions, and that is exactly what $G(3) = 4$ has to do.

What “almost every number” does and does not give #

The strongest theorem in the direction of four is Harold Davenport’s, from 1939: almost every number is a sum of four positive cubes. Precisely, the numbers up to $N$ that are not are a share of $N$ that tends to nothing. The proof is the circle method run on the average, and it is the rigorous form of the volume count in the last figure — it shows that the representations do spread evenly over almost all numbers, and so miss only a vanishing fraction of them.

That is a strong statement and it is exactly as strong as the figure of shares. The window counts show five falling to a quarter by a million and still falling; Davenport proves the fall goes all the way to a share of zero. What neither can do is say that the numbers needing five eventually stop. A set can have density zero and still be infinite — the squares, the primes and the sums of two squares are all such sets — and an infinite set of numbers needing five would leave $G(3) = 5$ while every statement about averages and shares was true.

So the problem lives in the gap between “almost all” and “all but finitely many”. The circle method is very good at the first and has no grip on the second, because a finite list of exceptions and an infinite thin list look the same to any argument about averages. The same gap holds open the corresponding question for higher powers. For fourth powers Davenport also proved $G(4) = 16$, matching an obstruction modulo 16 exactly; for fifth and higher powers only bounds are known, and the true values are believed to sit near the congruence obstructions, exactly as four is believed for cubes.

How this sits beside two squares #

The essays on sums of squares began with two squares and a lattice, where the question of which numbers are sums of two squares has a complete answer in terms of prime factors, and the share of such numbers falls to nothing. The contrast with cubes is instructive at each step.

For squares the counts are all settled. Two squares are not enough for almost every number; three are enough except for one congruence family, Legendre’s $4^a(8b + 7)$, which is the same theorem that lets three triangular numbers reach everything; four are enough for every number, by Lagrange. The reason is algebra: sums of squares are norms, they multiply, and the theory of quadratic forms says exactly which numbers each form represents.

Cubes have no such theory. A sum of two cubes does not multiply into another sum of two cubes in any useful way, there is no norm, and the representation counts behave like the averages in the last figure rather than like the exact formulas for squares. That is why the three-cubes problem is open for 114 and why $G(3)$ is open between 4 and 7: the only general tools are counting and the circle method, which see averages, and the questions are about every number.

What the computation does and does not settle #

Everything in the figures up to 1,500,000 is exact: the least number of cubes for each number is computed by a recursion that cannot miss a cheaper sum, and the counts and last occurrences are read from it. The representations of 23, 239 and 454 are found by listing every multiset of the required size, so “exactly two ways” means two.

The statement that 1,290,740 is the last number needing six is exact only up to the range of the computation. Beyond it, the evidence is the published searches, which go many orders of magnitude further and found no later one. The four-cube averages are exact counts in windows of a thousand, and the volume formula they are compared to is a heuristic for the average, not a statement about any particular number.

Still open: four cubes #

Is every sufficiently large number a sum of four positive cubes? If so, $G(3) = 4$, and the last number needing five is, on the evidence, 7,373,170,279,850. Even $G(3) \le 6$ is open — that every large number is a sum of six cubes — although it is supported by the same computations, which find the last number needing six at 1,290,740 and none in the many orders of magnitude after it.

The gap between what is proved, seven, and what is believed, four, has stood since Linnik, apart from making seven explicit. Closing it by one would need a new way to show that sums of cubes cannot all avoid a given number, and the averages in the last figure, growing without end, are the evidence that such a way should exist.