In other words, Hilbert’s 10th problem is undecidable.
Mathematicians hoped to follow the same approach to prove the extended, rings-of-integers version of the problem—but they hit a snag.
Gumming Up the Works
The useful correspondence between Turing machines and Diophantine equations falls apart when the equations are allowed to have non-integer solutions. For instance, consider again the equation y = x2. If you’re working in a ring of integers that includes √2, then you’ll end up with some new solutions, such as x = √2, y = 2. The equation no longer corresponds to a Turing machine that computes perfect squares—and, more generally, the Diophantine equations can no longer encode the halting problem.
But in 1988, a graduate student at New York University named Sasha Shlapentokh started to play with ideas for how to get around this problem. By 2000, she and others had formulated a plan. Say you were to add a bunch of extra terms to an equation like y = x2 that magically forced x to be an integer again, even in a different number system. Then you could salvage the correspondence to a Turing machine. Could the same be done for all Diophantine equations? If so, it would mean that Hilbert’s problem could encode the halting problem in the new number system.
Illustration: Myriam Wares for Quanta Magazine
Over the years, Shlapentokh and other mathematicians figured out what terms they had to add to the Diophantine equations for various kinds of rings, which allowed them to demonstrate that Hilbert’s problem was still undecidable in those settings. They then boiled down all remaining rings of integers to one case: rings that involve the imaginary number i. Mathematicians realized that in this case, the terms they’d have to add could be determined using a special equation called an elliptic curve.
But the elliptic curve would have to satisfy two properties. First, it would need to have infinitely many solutions. Second, if you switched to a different ring of integers—if you removed the imaginary number from your number system—then all the solutions to the elliptic curve would have to maintain the same underlying structure.
As it turned out, building such an elliptic curve that worked for every remaining ring was an extremely subtle and difficult task. But Koymans and Pagano—experts on elliptic curves who had worked closely together since they were in graduate school—had just the right tool set to try.
Sleepless Nights
Since his time as an undergraduate, Koymans had been thinking about Hilbert’s 10th problem. Throughout graduate school, and throughout his collaboration with Pagano, it beckoned. “I spent a few days every year thinking about it and getting horribly stuck,” Koymans said. “I’d try three things and they’d all blow up in my face.”
In 2022, while at a conference in Banff, Canada, he and Pagano ended up chatting about the problem. They hoped that together, they could build the special elliptic curve needed to resolve the problem. After finishing some other projects, they got to work.
