Writing 33 as a Sum of Cubes

Gödel’s Lost Letter and P=NP 2019-10-01

Cracking a Diophantine problem for 42 too

Andrew Booker is a mathematician at the University of Bristol, who works in analytic number theory. For example he has a paper extending a result of Alan Turing on the Riemann zeta function. Yes our Turing.

Today Ken and I will talk about his successful search for a solution to a 64 year old problem.

He was inspired by a video on the search problem authored by Tim Browning and Brady Haran. The question was to find a solution to

$\displaystyle 33 = x^{3} + y^{3} + z^{3}.$

Booker found

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

The search was for all possible solutions with ${x,y,z}$ bounded by ${10^{16}}$ . Note that this is expensive, and is not even close to polynomial time in the number of bits. But it is feasible today thanks to modern technology:

The total computation used was approximately ${23}$ core-years over one month of real time.

Before we turn to our discussion, note that Booker’s paper on extending Turing is really a result on proof checking. Turing had great intuition, terrible that we lost him so early. He, Turing, essentially proved the first result ever on how to efficiently check a computation. Booker says:

Turing introduced a method for certifying the completeness of a purported list of zeros of ${Z(t)}$ that is guaranteed to work (when the list is in fact complete). Turing’s method has remained a small but essential ingredient in all subsequent verifications of RH and its many generalizations.

That is checking the zeroes of the Riemann zeta function ${Z(t)}$ .

Speaking of checking, when I was drafting this I initially had the wrong solution:

$\displaystyle 33 = (8 866 128 975 287 528)^{3} + (8 778 405 442 862 239)^{3} - (2 736 111 468 807 040)^{3}.$

which is wrong. Can you quickly see why this cannot be right? Answer at the end.

The Press

The press love Booker’s result. Not the one on the zeta function, the one on the number ${33}$ .

Part of the excitement is caused by the number ${33}$ . In complexity theory we rarely see explicit numbers—more likely to see expressions like

$\displaystyle O(n^{\log_2 3}(\log \log n)^{3})$

and worse.

The press seem to like the numerology of ${33}$ . The number ${33}$ is quite neat:

The atomic number of arsenic.
It is the code for international direct-dial phone calls to France.
It is Kareem Abdul-Jabbar’s old jersey number.
And more ${\dots}$

Most important is the connection with Rolling-Rock beer:

The press from Newsweek and other sites talked about Booker’s solution. See here and here. And here at the Quanta magazine with a great diagram:

One said:

To crunch the numbers, he then used a cluster of powerful computers – 512 central processing unit (CPU) cores at the same time – known as Blue Crystal Phase 3. When he returned to his office one morning after dropping his children off at school, he spotted the solution on his screen. “I jumped for joy,” he recalled.

Another reported,

Booker said: “This one’s right at the boundary between what we know how to prove and what we suspect might be undecidable.”

I hope we will get the same coverage for our big results.

More Press

The press love Booker’s result. Not the one on the zeta function, the one on the number ${42}$ . This search was jointly led by Andrew Sutherland of MIT.

Part of the excitement is caused by the number ${42}$ . In complexity theory we rarely see explicit numbers—more likely to see expressions like

$\displaystyle O(n^{\log_{3} 4}(\log \log n)^{2})$

and worse.

The press seem to like the numerology of ${42}$ . The number ${42}$ is quite neat:

The atomic number of molybdenum.
It was the code for international direct-dial phone calls to Czechoslovakia, until the “velvet divorce” split the codes into ${420}$ and ${421}$ .
It was Jackie Robinson’s old jersey number. Major League Baseball retired the number for all teams. The last player allowed to wear it was Mariano Rivera of the Yankees, himself a Hall-of-Famer, except that all players on all teams wear it on April 15. Rivera is nicknamed “Mo” which is the symbol for molybdenum—are we the first to notice this coincidence?
And more ${\dots}$

Most important is the connection with The Hitchhiker’s Guide to the Galaxy:

The press from New Scientist and other sites talked about Booker’s solution. See here and here. But here the Quanta magazine seems not to have mentioned the number ${42}$ at all in over three months:

One said:

Of course, it wasn’t simple. The pair had to go large, so they enlisted the aid of the Charity Engine, an initiative that spans the globe, harnessing unused computing power from over 500,000 home PCs to act as a sort of “planetary supercomputer.”
It took over a million hours of computing time, but the two mathematicians found their solution:

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

Another reported:

Booker said: “I feel relieved … we might find what we’re looking for with a few months of searching, or it might be that the solution isn’t found for another century.”

I hope we will get the same coverage for our big results.

Less Press

Booker and Sutherland also discovered that

$\displaystyle 569936821221962380720^3 - 569936821113563493509^3 - 472715493453327032^3 = 3.$

This is the next-largest solution after ${3 = 1^3 + 1^3 + 1^3}$ and ${3 = 4^3 + 4^3 + (-5)^3}$ . Weird. And the first solution not to duplicate a number. And it uses two numbers that agree to markedly more decimal places than those in the above solutions for ${33}$ and ${42}$ . Weirder.

Smart Search

Booker wanted to search for a solution to

$\displaystyle k = x^{3} + y^{3} + z^{3}.$

Actually his main interest was in ${k=33}$ , but his method is general. How does one do this for ${x,y,z}$ bounded by ${B = 10^{16}}$ . The obvious method is: Try all numbers below ${B}$ .

This is too expensive and requires ${\widetilde{O}(B^{3})}$ time. Too much, even with a cluster of fast processors.

An improvement is to try all ${x,y}$ in the range and then check that ${k-x^{3}-y^{3}}$ is cube. This runs in ${\widetilde{O}(B^{2})}$ time. Still too much.

A key insight is to re-write the equation as

$\displaystyle k -z^{3} = x^{3} + y^{3} = (x + y)(x^{2} - xy + y^{2}).$

Then we note that ${x+y}$ must be a divisor of ${k-z^{3}}$ . Since there are few such divisors, we can improve the time greatly. For the divisors ${d}$ of ${k-z^{3}}$ some simple algebra and the quadratic formula shows that

$\displaystyle x = \frac{d}{2} + \sqrt{\frac{4|k-z^{3}| - d^{3}}{6d}},$

and

$\displaystyle y = \frac{d}{2} - \sqrt{\frac{4|k-z^{3}| - d^{3}}{3d}}.$

This shows that the search is now reduced to ${\widetilde{O}(B)}$ . Still too much, but close to doable. The next trick is to avoid the factoring step. See Booker’s paper for the rest of the search description.

I like the progression of time bounds from

$\displaystyle \widetilde{O}(B^{3}) \rightarrow \widetilde{O}(B^{2}) \rightarrow \widetilde{O}(B).$

Open Problems

Can one beat ${\widetilde{O}(B)}$ ? Could there be an algorithm that runs in ${\widetilde{O}(B^{a})}$ for some ${a<1}$ ? Can any of our tricks apply here? A possible observation: Booker is clever but he writes that the methods use not

$\displaystyle \widetilde{O}(B^{3}) \rightarrow \widetilde{O}(B^{2}) \rightarrow \widetilde{O}(B)$

time, but that they use

$\displaystyle {O}(B^{3+\epsilon}) \rightarrow {O}(B^{2+\epsilon}) \rightarrow {O}(B^{1+ \epsilon})$

time. Maybe we can help in some manner. What do you think? The next unsolved number, ${114}$ , awaits.

Answer to the question on checking: Take the numbers modulo ${10}$ .

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

becomes

$\displaystyle 3 \equiv (8)^{3} + (9)^{3} - (0)^{3} \equiv 2 + 9 \equiv 1.$

[Typo fixed]