Sum of three cubes

I’ve spent more of the last two months reading about this one line than I’d like to admit:

42 = (−80538738812075974)³ + 80435758145817515³ + 12602123297335631³

Andrew Booker at Bristol and Andrew Sutherland at MIT announced it in early September, and yes, the press coverage contained a lot of Hitchhiker’s Guide jokes. It’s the end of a search that, for numbers under 100, has been going on since the 1950s. I checked it in Python, since Python has arbitrary-precision integers built in, and it really does come out to 42. You should too, it takes one line.

My math degree was a long time ago and I was never a number theorist, so take the deeper parts of this with some salt. But the core of it is accessible, and the algorithm that cracked it is a really nice example of turning an impossible search into a merely enormous one.

The question

Which integers k can be written as x³ + y³ + z³, where x, y and z are integers, positive or negative?

Negative is what makes it hard. If you only allowed positive cubes, the numbers would grow fast and you’d just check a finite list. With negatives allowed, two huge cubes can nearly cancel each other out and leave a small remainder, so a solution for a tiny k can involve 17-digit numbers, as 42 does, and there’s no obvious place to stop looking.

Some are easy. 3 = 1³ + 1³ + 1³. Also 3 = 4³ + 4³ + (−5)³, which is 64 + 64 − 125. Some have neat families of solutions: any cube k = n³ has n³ + 1³ + (−1)³, and there’s a known polynomial identity that gives infinitely many representations of 2. Most numbers have no such shortcut and you just have to find one.

Where not to look

Some numbers can’t be done at all, and the reason is a neat little piece of modular arithmetic. This is what cubes look like mod 9:

Every cube is 0, 1 or −1 mod 9. (Quick check: write n as 3m, 3m + 1 or 3m − 1 and expand. The cross terms all pick up a factor of 9.) So three of them add up to something between −3 and 3, mod 9, and you can never get 4 or 5. That rules out 4, 5, 13, 14, 22, 23 and so on, two of every nine integers, forever, with no computer needed.

The interesting question is whether that’s the only obstruction. Roger Heath-Brown conjectured in 1992 that it is: every k that isn’t 4 or 5 mod 9 should have not just one representation but infinitely many. Nobody can prove it. But it’s backed by a heuristic that predicts roughly how many solutions there should be below a given size, which tells you that the solutions for some k are going to be very large and very rare. It also tells you that searching is not hopeless, just expensive.

The search, before this year

Brute force over x, y and z up to some bound B is B³ work, which is useless. The obvious improvement is to loop over x and y and check whether k − x³ − y³ is a perfect cube, which is B². Still hopeless for B anywhere near 10¹⁶.

The better methods use the fact that for a solution with large numbers, two of the cubes have to nearly cancel. Noam Elkies’s lattice-reduction algorithm (circulated in 1999, published in 2000) finds the points lying very close to the curve x³ + y³ = z³, and searches based on it found solutions for a lot of numbers over the following two decades. One of its first big finds was 30, in 1999, with numbers in the billions:

30 = 2220422932³ + (−2218888517)³ + (−283059965)³

74 was found by Sander Huisman in 2016. After that, the only numbers under 100 left without a known representation, not counting the 4-or-5-mod-9 ones, were 33 and 42.

There’s a Numberphile video from 2015 with Tim Browning called “The Uncracked Problem with 33”, and Booker has credited it with getting him interested. I like that a lot. A YouTube video sends a mathematician off after a problem that’s been open for decades, and he cracks it.

Booker’s trick

The algebra is short. I worked through it on paper because I didn’t believe it at first.

Rearrange to x³ + y³ = k − z³. The left side factors:

x³ + y³ = (x + y)(x² − xy + y²)

Call d = x + y. Then d has to divide k − z³. That’s the key: instead of searching over pairs, you search over z and the divisors d of k − z³.

And given z and d, you don’t need to search for x and y at all. Since x³ + y³ = d³ − 3dxy, you can solve for the product:

xy = (d³ − (k − z³)) / (3d)

Now you know the sum x + y and the product xy, so x and y are the roots of a quadratic, and they’re integers exactly when the discriminant is a perfect square:

(x − y)² = (4(k − z³) − d³) / (3d)

Try it on 3 = 4³ + 4³ + (−5)³. Here d = 8, z = −5, and k − z³ = 3 + 125 = 128. The discriminant is (4 × 128 − 512) / 24 = 0, so x = y, and xy = (512 − 128) / 24 = 16. Both are 4. It works.

The other important fact is that in the solutions that matter, d is small compared to z. Two huge cubes nearly cancel, so their sum x + y is much smaller than either of them. In the 33 solution d is about 3% of |z|, and in the 42 solution it’s under 1%. So the search can loop over d, which is the smaller quantity, instead of z.

For a fixed d you need z³ ≡ k (mod d), because d divides k − z³. Working out which z satisfy that means finding cube roots of k modulo d, which is easy when you know how d factors, and d is small enough that you do. The answer is a handful of residue classes, and z only needs to be checked in those arithmetic progressions, a tiny fraction of all integers. For each candidate, you compute the discriminant and ask whether it’s a perfect square. That’s my reading of the paper, anyway. There’s a lot more cleverness in it, sieving out candidates cheaply before doing the expensive check, but that’s the shape.

The net effect is that the work grows roughly linearly with the bound instead of quadratically. Linear in 10¹⁶ is still a lot, but it’s a lot you can buy.

33, and then 42

Booker posted the 33 result to arXiv in March:

33 = 8866128975287528³ + (−8778405442862239)³ + (−2736111468807040)³

He searched everything with |x|, |y|, |z| up to 10¹⁶. It took about a month of real time on Bristol’s university cluster, roughly 23 core-years of computing. The same search found nothing for 42, and that was that for the 16-digit range.

For 42 he teamed up with Sutherland, who has a lot of experience running huge number-theory computations, and they went an order of magnitude bigger, on Charity Engine, a volunteer grid that runs on idle home PCs, more than 500,000 of them according to Bristol’s press release. It took over a million hours of computing. The answer is the 17-digit one at the top of this post. Every number under 100 that can possibly be a sum of three cubes is now known to be one.

Then a couple of weeks later, the same pair announced a third way of writing 3:

3 = 569936821221962380720³ + (−569936821113563493509)³ + (−472715493453327032)³

That one closes a question Louis Mordell asked in the 1950s, whether 3 had any representations beyond 1, 1, 1 and 4, 4, −5. People had been looking for over 60 years. The numbers are 21 digits long. Heath-Brown’s conjecture says there should be infinitely many more, and nobody has the faintest idea how big the next one is.

Why I care, as a programmer

Partly I just like it. But it’s also a really clean example of something I see at work all the time, without any of the office politics. The brute-force search was never going to finish. Faster hardware didn’t fix it, and neither did more hardware. What fixed it was a bit of algebra that changed the shape of the search: factor the expression, notice which quantity is small, loop over that one, and turn “search for x and y” into “check whether one number is a perfect square”. The million hours of Charity Engine only mattered because the algorithm got the problem into a range where a million hours was enough.

I tried writing a toy version in Python, looping over d and z from −300 to 300 for every k up to 100. It finds representations for 68 of the 78 possible numbers in under two seconds. The ten it misses include 30, 33, 42 and 74, which is the whole story of this problem in one line of output. Still, watching it rediscover 4³ + 4³ + (−5)³ was more satisfying than it had any right to be.

Under 1,000 there are still a few numbers with no known representation, and the smallest is 114. I’d quite like to see that one before the decade’s out, but honestly I have no idea whether it’ll take one more year or fifty.