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]

September 30, 2019 11:26 am

In regard to fair credit, fairly given, remember that 42 was one of Deacon Dodgson’s favorite numbers. Abstracted by Disney, it plays daily as, “Rule 42, the Queen always wins!” The specific reference is,

“It’s the oldest rule in the book,” said the King.
“Then it ought to be Number One,” said Alice.

• September 30, 2019 3:46 pm

I considered also mentioning that there are 42 Laws of Cricket—a number that has been conserved even with the advent of digital review. On this matter I would speak with some authority. 🙂 But the “33” post was drafted before we saw 42 had been solved too, and we decided to conserve the parallel between the two “Press” sections as much as possible to be funny.

September 30, 2019 12:30 pm

Did you mean $B^{1+\epsilon}$ (not $B^\epsilon$) in the last equation?

September 30, 2019 12:32 pm

Dear Clement Canonne:

Yes of course…thanks very much all fix

Best

Dick

September 30, 2019 1:03 pm

Could we use this as the basis of an encryption system, I choose three large random cubes and find their sum, publish the sum as a public key and the large cubes as a private key?

September 30, 2019 5:58 pm

One more missing fact since the ancient times :

http://vixra.org/abs/1909.0638