Thirty-three as three cubes

Which numbers are a sum of two squares has a complete answer: factor the number, and it is a sum of two squares exactly when every prime leaving 3 on division by 4 appears to an even power. Which are a sum of three squares has a complete answer too, Legendre’s: all but the numbers $4^a(8b + 7)$. Four squares reach everything.

Ask the same question about cubes — allowing negative cubes, so that the question is which whole numbers $n$ have $x^3 + y^3 + z^3 = n$ — and almost nothing is known. Numbers leaving 4 or 5 on division by 9 are impossible. Every other number is believed to be a sum of three cubes, in infinitely many ways. Not one number has been proved to be such a sum unless a sum has been found for it, and finding one can take a very long time.

Searching every triple with all three numbers at most 5,000 in size, which takes about four hundred milliseconds, finds a representation for every number below 100 that is not ruled out — except eight. Those eight, 30, 33, 39, 42, 52, 74, 75 and 84, have representations too, but with cubes of between six and seventeen digits. The last two below a hundred to be found were 33, in April 2019, and 42, in September of the same year.

What negative cubes change #

With positive cubes only, the question is Waring’s — the cubic case of the problem Fermat posed for polygonal numbers — and its answer is that every number is a sum of at most nine positive cubes, and only 23 and 239 actually need nine. That is a question about how densely positive cubes pack, and it has the flavour of the two-squares problem, where the share of numbers reached falls slowly to nothing — the cubes up to $N$ number about $N^{1/3}$, and sums of three of them can reach at most about $N$ numbers, so they have a chance of covering a positive share.

Allowing negative cubes changes the problem completely. The difference of two large cubes, $x^3 - y^3$ with $x$ and $y$ close together, can be small: $10^3 - 9^3 = 271$, and $(k + 1)^3 - k^3 = 3k^2 + 3k + 1$. So a small number can be the sum of three cubes that are all enormous, two of them nearly cancelling and the third making up the difference. There is no longer a bound on the search: a representation of 33 could use cubes of any size, and it did. That is why no amount of failed searching can show a number is not a sum of three cubes, and why every negative answer has to come from a proof.

The first figure records, for each number, the size of the largest of $|x|, |y|, |z|$ in the smallest representation found. Most numbers need nothing larger than 10. A few need hundreds: 51 first appears with 796, as $602^3 + 659^3 - 796^3$, and 87 with 4,271. Below a hundred, eight need more than 5,000.

The obstruction from division by nine #

There is exactly one known reason a number can fail to be a sum of three cubes.

Cubes leave only 0, 1 or 8 on division by 9. A multiple of 3 cubed is a multiple of 27; and $(3k \pm 1)^3 = 27k^3 \pm 27k^2 + 9k \pm 1$, which leaves $\pm 1$. So a sum of three cubes leaves a sum of three numbers from $\{0, 1, -1\}$, which ranges from $-3$ to $3$ and so leaves one of 0, 1, 2, 3, 6, 7 or 8 — never 4 or 5. Two of every nine numbers are ruled out.

The same trick fails for every other modulus. Cubes modulo 7 leave 0, 1 or 6, and three of them reach every remainder; modulo any prime other than 3, three cubes reach everything; and running through every modulus up to 300 finds that three cubes miss a remainder only when the modulus is a multiple of 9, where the miss is the one already found. So if there is a second obstruction, it is not a congruence. The conjecture is that there is none: every number not leaving 4 or 5 on division by 9 is a sum of three cubes.

This is the place where the problem departs most sharply from the two-squares problem. There, the congruence obstruction — primes leaving 3 on division by 4 — is not the whole story, because the obstruction attaches to each prime factor and has to be applied to the factorisation. For three squares, Legendre’s exceptions $4^a(8b + 7)$ are again purely congruence conditions, and for three triangular numbers there are none at all. For three cubes there may be nothing beyond the congruence, but the reason the theorems for squares exist — the geometry of quadratic forms, the arithmetic of the Gaussian integers — has no counterpart for a cubic.

How far a box reaches #

The search records, for every number below 1,000, the smallest box in which it has a representation.

Cubes up to 10 in size reach 54.8 per cent of the possible numbers below 1,000. Cubes up to 100 reach 79.0 per cent, up to 1,000 reach 85.2 per cent, and up to 5,000 reach 88.4 per cent, leaving 90 numbers. Each tenfold enlargement of the box costs a hundred times as much work — the search runs over pairs — and finds a few per cent more.

The curve’s shape is not an accident of these particular numbers. If a typical number’s representations arrived at random, at a steady rate per unit of $\log B$ — which is what the heuristic below predicts — then the chance that none has arrived by the time the box reaches $B$ would fall like a power of $B$, with an exponent that differs from number to number. A number with a small exponent can go an extremely long way with nothing. The heuristic says the curve should creep towards 100 per cent without ever reaching it in any finite search, and it says the long tail is made of numbers that are merely unlucky, not of numbers that are impossible.

That is the uncomfortable position the problem is in. Among the numbers below a thousand, the large searches of the last thirty years — with cubes up to $10^{16}$ and $10^{17}$ — have reached all but a handful. As of the searches reported in 2021, seven remained: 114, 390, 627, 633, 732, 921 and 975. Each is believed to be a sum of three cubes, and for each the belief rests on nothing more than the heuristic and the fact that every other number has turned out to be one.

How large the first solution can be #

The eight numbers below a hundred that the box misses stand out in the figure as a separate population.

Below the line at 5,000, the blue points sit almost all below 100. Above it, the red points spread over thirteen orders of magnitude: 39 needs cubes of six digits, $134{,}476^3 + 117{,}367^3 - 159{,}380^3$; 84 eight; 75 nine; 30 ten, as $2{,}220{,}422{,}932^3 - 2{,}218{,}888{,}517^3 - 283{,}059{,}965^3$, found in 1999; 52 eleven; 74 fifteen, found by Sander Huisman in 2016; 33 sixteen and 42 seventeen. Every one of those representations is checked in the figure in exact integer arithmetic, because a rounding error in a seventeen-digit cube is about a hundred, and the whole point is that the three cubes cancel to within a hundred.

Andrew Booker’s representation of 33,

$$33 = 8{,}866{,}128{,}975{,}287{,}528^3 - 8{,}778{,}405{,}442{,}862{,}239^3 - 2{,}736{,}111{,}468{,}807{,}040^3,$$

came from a search over every $z$ up to about $10^{16}$ in size. The method uses the factorisation $x^3 + y^3 = (x + y)(x^2 - xy + y^2)$: the number $d = x + y$ must divide $n - z^3$, and for each $d$ and each $z$ satisfying that divisibility the remaining factor determines $x$ and $y$ by solving a quadratic. Because $d$ divides $n - z^3$, only certain $z$ are possible for each $d$ — the cube roots of $n$ modulo $d$ — and running through them costs far less than running through all pairs. The representation of 42, by Booker and Andrew Sutherland, took about a million hours of donated computer time; 42 had been the last number below a hundred.

Nothing in the arithmetic of 30, 33, 42 or 74 explains why they are hard. They are not distinguished by their residues, their factorisations, or any other visible property. The heuristic attributes it to a constant attached to each number, an expected density of representations, which is computed from how many solutions the equation has modulo every prime — and some numbers simply have a small one.

Three, a third time #

The number 3 is the oldest form of the question. It has the representations $1 + 1 + 1$ and $4^3 + 4^3 - 5^3 = 64 + 64 - 125$, and Louis Mordell asked in 1953 whether it has any others.

J. W. S. Cassels proved in 1985, using cubic reciprocity, that any representation of 3 has $x$, $y$ and $z$ all leaving the same remainder on division by 9 — which both known ones do. That restricted the search, and for thirty years the searches found nothing. In September 2019 Booker and Sutherland found the third:

$$3 = 569{,}936{,}821{,}221{,}962{,}380{,}720^3 - 569{,}936{,}821{,}113{,}563{,}493{,}509^3 - 472{,}715{,}493{,}453{,}327{,}032^3.$$

It has twenty-one digits, and it satisfies Cassels’ congruence: all three numbers leave 1 on division by 9, as $1, 1, 1$ do, and as $4, 4, -5$ all leave 4. It is plotted on the figure above at the top left, alone, ten thousand times further from the axis than anything else.

Families of solutions, and solutions outside them #

For two numbers, and for every multiple of their cubes, the question has an algebraic answer.

The identity $(1 + 6t^3)^3 + (1 - 6t^3)^3 + (-6t^2)^3 = 2$ holds for every $t$, as expanding it shows: the cubes of $1 \pm 6t^3$ add to $2 + 216t^6$, and $(-6t^2)^3$ cancels the second term. So 2 is a sum of three cubes in infinitely many ways, and the ten representations the box finds are exactly $t = 0, 1, \ldots, 9$ of this one family. Whether 2 has any representation not of this form is unknown. For 1, Kurt Mahler found the family $(9t^4)^3 + (3t - 9t^4)^3 + (1 - 9t^3)^3 = 1$ in 1936, and the box finds twenty-four representations of 1, of which eight are Mahler’s and sixteen are not — the smallest of them $94^3 + 64^3 - 103^3$.

Multiplying a family by a cube gives a family for $k^3$ and $2k^3$. Beyond those, no number is known to have a polynomial family of representations. So for 3, and for every number that is neither a cube nor twice one, the representations that exist are sporadic — isolated points on a surface, with nothing generating them.

Two cubes, by contrast, are well understood, and the contrast is instructive. For a fixed $n$, the equation $x^3 + y^3 = n$ defines a curve rather than a surface, and once rational solutions are allowed it is an elliptic curve — the same kind of object that decides which numbers are the areas of right triangles with rational sides. Its whole-number points are finite in number, for an elementary reason — $x + y$ divides $x^3 + y^3$, so it must be one of the divisors of $n$, and each divisor leaves a quadratic to solve — and can be listed; Ramanujan’s $1729 = 12^3 + 1^3 = 10^3 + 9^3$ is the smallest number with two representations as a sum of two positive cubes. Adding a third cube adds a dimension, and the finiteness disappears: the surface carries infinitely many whole-number points whenever it carries a polynomial family, and is conjectured to carry infinitely many in every other case too, but there is no theorem like Thue’s to organise them.

That is the deepest difference from the two-squares problem. A prime of the form $4k + 1$ is a sum of two squares, and the squares can be computed; there is a formula behind every representation, in the arithmetic of the Gaussian integers. For three cubes there is no ring in which the whole sum factors — $x^3 + y^3 + z^3$ is an irreducible cubic in three variables — and the whole-number points on cubic surfaces are among the least understood objects in number theory.

Solutions arriving at the rate of log B #

The heuristic is Roger Heath-Brown’s of 1992, and it makes a precise prediction that the search can test.

Count the triples with all three numbers at most $B$ in size: there are about $B^3$ of them, and their sums spread over a range of about $B^3$, so each value is hit about once. That alone predicts a bounded number of representations. But the sums are not spread evenly: a triple with $x^3 + y^3 + z^3$ small needs two large cubes nearly cancelling, and the volume of such triples on the scale of each power of 2 in $B$ is the same — so the expected number of representations of a fixed $n$ in the box grows by a constant for each doubling of $B$, which is to say like $\log B$. Heath-Brown attached to each $n$ a constant computed from the number of solutions modulo every prime and conjectured that the count is asymptotic to that constant times $\log B$, with infinitely many representations for every $n$ not ruled out.

The average over the 768 numbers in the figure climbs from 0.77 at $B = 10$ to 1.90 at 100, 3.27 at 1,000 and 4.36 at 5,000 — by about 1.3 for every tenfold enlargement, close to a straight line in $\log B$. The individual counts are small and lumpy: 24 has two solutions in the box, 7 has three, 6 and 10 and 11 have four, 20 has seven. A straight line in $\log B$ is growth so slow that a box with a million on a side would show only a few more representations of a typical number than this one does, and a number with a small constant could have its first beyond any box ever searched.

Where the question becomes undecidable in general #

There is a reason to expect that some questions of this kind have no answer at all. By Matiyasevich’s theorem of 1970, no algorithm can decide, for every polynomial equation with whole-number coefficients, whether it has a whole-number solution. That is Hilbert’s tenth problem, and its negative answer means that somewhere among the polynomial equations there are ones whose solvability is beyond any procedure.

It does not follow that this equation is one of them. If the conjecture is true, deciding whether $x^3 + y^3 + z^3 = n$ has a solution is trivial — divide $n$ by 9 and look at the remainder. But nobody can currently prove that a given $n$ not ruled out has a representation without finding one, and nobody can bound in advance how large the search must be. The procedure search until a representation turns up halts on every $n$ that has one, and the conjecture says that is every $n$ not leaving 4 or 5; but whether it halts on 114 is, for now, a matter of waiting.

The same uneasy position belongs to several other questions in this collection. Erdős and Straus’s conjecture that $4/n$ is always a sum of three unit fractions has been checked to very large $n$ and is unproved, with every case found by search. Moats among the Gaussian primes are found by search for each step length, and whether every step length has one is open. In each case the computation produces facts one at a time and nothing that generalises.

What the box cannot see #

The search here is exhaustive for its box: every triple with all three numbers at most 5,000 in size is examined, and every solution for a number below 1,000 is recorded and checked. It can say that 30 has no representation with cubes that small. It cannot say whether 30 has a representation of eight digits rather than ten, because the box stops at four; the sizes plotted for the eight hard numbers are the sizes of the representations that were found, by searches organised differently, not proven minima.

The averaged count is the part that tests a conjecture, and it does so only weakly. A straight line in $\log B$ across three decades is consistent with Heath-Brown’s prediction and with many other slow growths; the conjecture’s specific constants, which differ from number to number, would need a far larger box to test one number at a time, and the counts here are too small for that — two to seven solutions each, where a single extra solution moves a count by a third.

Still open: one hundred and fourteen #

Is every number not leaving 4 or 5 on division by 9 a sum of three cubes? That is the conjecture, and it is open — for 114, the smallest number with no representation yet found, and for every number at once. Even the weaker statement that infinitely many numbers not ruled out are sums of three cubes in only finitely many ways, or that some such number is not a sum at all, is beyond current methods, and so is the statement that 3 has infinitely many representations, which Heath-Brown’s heuristic predicts. Proving that a single given number, not a cube or twice one, has infinitely many would already be new.

A congruence and nothing else #

Cubes leave 0, 1 or 8 on division by 9, so three of them can never leave 4 or 5 — and that is the only obstruction anyone has found. A box of side 5,000 represents every possible number below a hundred except eight, and those eight needed cubes of six to seventeen digits; 3 has a third representation with twenty-one. Solutions arrive at a rate proportional to $\log B$, as Heath-Brown’s heuristic predicts, so a search can always miss the next one, and the question for two squares that the primes settle completely stays open for three cubes, settled number by number by whoever searches furthest.