More sums of three cubes

About six months ago I wrote about the recent discovery that 33 can be written as the sum of three cubes. At that time, the only remaining number less than 100 whose status was still unknown was 42. And just recently that, too, has fallen: thanks to Andrew Booker and Andrew Sutherland, we now know that

$\displaystyle 42=(-80538738812075974)^3+80435758145817515^3+12602123297335631^3.$

Again, this was very difficult to find (it required 1.3 million hours of computer time!) but very easy to verify: you can plug the above numbers into a computer yourself and see that you get 42. In fact, I’ve set up some links here so you can try it yourself using either Wolfram Alpha or Python. (Sadly, most graphing calculators don’t have enough precision to represent these numbers exactly. But seriously, click one of the links above and try it out!)

I still don’t understand the math behind the algorithm Booker and Sutherland used (I tried reading the paper but quickly got lost, and my sense is that I would probably have to spend at least several months doing background reading to be able to understand it). But this time around I’ve been learning more about the sums of three cubes problem itself. Today I’ll write a bit about which numbers actually have a hope of being written as a sum of three cubes, and in a future post I plan to write about numbers that have multiple representations as sums of cubes.

For the rest of this post I’m going to use the word tricubic to refer to numbers which can be written as a sum of three cubes. So, for example, we now know that $42$ is tricubic. I’ll also say tricubic sum to refer to three cubes that add up to a given number, for example, “ $1^3 + 2^3 + 3^3$ is a tricubic sum for $36$ ”.

Which numbers are tricubic?

Some numbers definitely aren’t tricubic: for example, 13. How did I know that? The key is to look at the remainders of cubes $\pmod 9$ :

$\begin{array}{rcl}0^3 &=& 0 \\[0.5em] 1^3 &=& 1 \\[0.5em] 2^3 &=& 8 \equiv (-1) \pmod 9 \\[0.5em] 3^3 &=& 27 \equiv 0 \pmod 9 \\[0.5em] 4^3 &=& 64 \equiv 1 \pmod 9 \\[0.5em] 5^3 &=& 8 \equiv (-1) \pmod 9 \\[0.5em] 6^3 &=& 216 \equiv 0 \pmod 9 \\[0.5em] 7^3 &=& 343 \equiv 1 \pmod 9 \\[0.5em] 8^3 &=& 512 \equiv (-1) \pmod 9\end{array}$

Notice that in the above table we only ever get remainders of $-1$ , $0$ , or $1$ . And since every integer is equivalent, $\pmod 9$ , to one of the numbers from $0$ through $8$ , this table actually tells us everything we need to know: every integer cube will be either a multiple of 9, one more than a multiple of 9, or one less. By adding up three remainders which are all $-1$ , $0$ , or $1$ , you can get any remainder between $-3$ and $3$ , inclusive. But that leaves out exactly two remainders you can’t get: $4$ and $5$ . That’s how I knew 13 is not tricubic: $13 = 9 + 4$ is four more than a multiple of $9$ .

OK, so now we know that any number either 4 or 5 more than a multiple of 9 is not tricubic. What about other numbers? Maybe if we look at remainders modulo some other divisor, say, $347$ , we can rule out other numbers in a similar way? Actually, no! So far it seems like this simple restriction is the only restriction on tricubic numbers: the conjecture is that every number not of the form $9k + \{4,5\}$ is tricubic—but right now this is only a conjecture; no one has yet managed to prove it!

So, in general, numbers fall into three groups:

Numbers of the form $9k + 4$ or $9k + 5$ which we know are not tricubic: $\{4, 5, 13, 14, 22, 23, 31, 32, \dots\}$ .
Numbers which we know are tricubic, because we know of at least one tricubic sum for them: $\{0, 1, 2, 3, 6, 7, 8, \dots\}$ .
Numbers which we think are probably tricubic, but we currently don’t actually know: $\{114, 165, 390, 579, 627, \dots\}$

Where do we go from here?

Progress on this problem could theoretically come in a lot of different ways.

First, someone could prove that there are additional numbers which are not tricubic. But as far as I can tell, everyone thinks this is pretty unlikely.

Someone could find a way to write some additional numbers as sums of three cubes. For example, the smallest number whose tricubic status we don’t currently know is $114$ ; someone might find a way to write $114$ as a sum of three cubes. However, the amount of computer time necessary to search for these may get prohibitively large: as I mentioned earlier, finding a tricubic sum for $42$ required 1.3 million hours of computer time. Note, however, that finding $33$ and $42$ was possible specifically because Andrew Booker came up with a better algorithm than what had been used before. So perhaps someone will come up with an even better algorithm that makes it feasible to search for larger tricubic sums. At some point, however, people will lose interest: finding bigger and bigger tricubic sums just gets boring after a while.

Someone could prove that every number not of the form $9k + \{4,5\}$ is tricubic by finding an algorithm which takes a number $n$ as input, and spits out a tricubic sum for $n$ . But wait, you ask, don’t we already have that? Weren’t $33$ and $42$ found using an algorithm? Well, yes, but the search algorithm used to find tricubic sums for $33$ and $42$ was not guaranteed to find anything. You give it an upper limit for the size of the cubes involved, and it will search everything below that, but there is no guarantee that it will find what it is looking for. You could easily modify the program to run as follows: given a number $n$ for which we wish to find a tricubic sum, start by searching for tricubic sums under a certain upper bound; if nothing is found, increase the upper bound and try again. If nothing is found the second time, increase the upper bound yet again, and so on. This is called a semi-decision procedure: if a tricubic sum exists for $n$ , this program will eventually find it, but if no tricubic sum exists then it will simply run forever (in theory, that is; of course any real computer would run out of memory long before that). So this doesn’t count as a proof because it doesn’t guarantee to find a tricubic sum for every number. An algorithmic proof would consist of an algorithm to find a tricubic sum for any suitable input number, along with a proof that the program will always return a tricubic sum in a finite amount of time for any input.

I don’t actually find the above scenario very likely (though a dramatic example of this kind is the recent proof that every positive integer is a sum of three palindromes). I find it more likely that someone will prove that every number not of the form $9k + \{4,5\}$ is tricubic, but in a way that is non-effective. That is, we would know that every suitable number must be tricubic, but the proof would not actually give us a way to find a tricubic sum for any given $n$ . (There is a very interesting distinction here between classical and constructive mathematics; maybe I’ll write more on this in a future post!)

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

6 Responses to More sums of three cubes

normativeforce says:

September 16, 2019 at 10:09 am

The complexity of the conjecture appears to be at most $\Pi_2$ in the arithmetical hierarchy, so using standard proof-theoretic techniques you should, in principle, be able to extract an ”algorithmic proof” from a non-constructive one. (All known naturally occurring classical theories, where we would expect the proof to be formalizable, are conservative over their intuitionistic versions for $\Pi_2$ statements.)
- Brent says:
  
  September 16, 2019 at 5:38 pm
  
  Fascinating, thanks! I agree it seems like it is $\Pi_2$ . However, I’m not familiar with the proof-theoretic techniques you mention. Do you have any good references for reading about this?
  - normativeforce says:
    
    September 17, 2019 at 10:10 am
    
    I’ll try to dip up some accessible references (not always an easy task when it comes to proof theory, alas!). In the meanwhile, perhaps the following remarks are of some help.
    
    First, let’s note that in a sense any proof of the conjecture would count as an ”algorithmic proof” simply by virtue of the logical form of the statement ( $\Pi_2), since every$ latex \Pi_2$ asserts the totality of the witnessing function (which we can read off an algorithm for from the formalization in the language of arithmetic, say)! Of course, it’s possible that the proof is by classical reduction, so that what we have established, from a constructive point of view, is not $\forall x \exists y P(x,y)$ — where P(x,y) is the formalization of ”if x is a natural of suitable form then y codes three integers, the sum of cubes of which add up to x” — but rather $\forall x \neg \neg \exists y P(x,y)$ , which is, on the face of it, constructively a weaker claim. But, as it happens, using devices such as the so-called Friedman translation (a variant of the double negation translation), we can show that whenever $\forall x \neg \neg \exists y P(x,y)$ is constructively provable, so is $\forall x \exists y P(x,y)$ , even though the corresponding equivalence is not in general valid — and indeed, classical Peano arithmetic, for instance, is conservative over Heyting arithmetic for $\Pi_2$ statements, or, in technical jargon, they have the same provably total functions.
    - Brent says:
      
      September 18, 2019 at 5:51 am
      
      Fascinating, thanks! I think that’s actually sufficient info for me to go off and find things to read. I had not heard of the Friedman translation before.
Pingback: Sums of cubes: multiple representations | The Math Less Traveled
Pingback: More powers of 3 | Newton Excel Bach, not (just) an Excel Blog