How Search Algorithms Are Changing the Course of Mathematics


Image credit: NAUTILUS
The sum-of-three-cubes problem solved for “stubborn” number 33.

By John Pavlus | NAUTILUS

Mathematicians long wondered whether it’s possible to express the number 33 as the sum of three cubes—that is, whether the equation 33 = x³+ y³+ z³ has a solution. They knew that 29 could be written as 3³ + 1³ + 1³, for instance, whereas 32 is not expressible as the sum of three integers each raised to the third power. But the case of 33 went unsolved for 64 years.

Now, Andrew Booker, a mathematician at the University of Bristol, has finally cracked it: He discovered that (8,866,128,975,287,528)³ + (–8,778,405,442,862,239)³ + (–2,736,111,468,807,040)³ = 33.

Booker found this odd trio of 16-digit integers by devising a new search algorithm to sift them out of quadrillions of possibilities. The algorithm ran on a university supercomputer for three weeks straight. (He says he thought it would take six months, but a solution “popped out before I expected it.”) When the news of his solution hit the Internet earlier this month, fellow number theorists and math enthusiasts were feverish with excitement. According to a Numberphile video about the discovery, Booker himself literally jumped for joy in his office when he found out.

“He has found a genuinely more efficient way of locating the solutions.”

Why such elation? Part of it is the sheer difficulty of finding such a solution. Since 1955, mathematicians have used the most powerful computers they can get their hands on to search the number line for trios of integers that satisfy the “sum of three cubes” equation k = x³ + y³ + z³, where k is a whole number. Sometimes solutions are easy, as with k = 29; other times, a solution is known not to exist, as with all whole numbers that leave behind a remainder of 4 or 5 when divided by 9, such as the number 32.

read more