In other terms, the 10th problem posed by Hilbert is undecidable.
Mathematicians held hopes of applying a similar approach to demonstrate the extended rings-of-integers version of the problem, but they encountered difficulties.
Causing Complications
The beneficial connection between Turing machines and Diophantine equations diminishes when the equations are permitted to possess non-integer solutions. For instance, examining the equation y = x2 again, if you’re considering a ring of integers that encompasses √2, you’ll discover some new solutions, like x = √2, y = 2. The equation ceases to represent a Turing machine that computes perfect squares—and, more broadly, the Diophantine equations can no longer encapsulate the halting problem.
However, in 1988, a graduate student at New York University named Sasha Shlapentokh began exploring ideas to circumvent this issue. By 2000, she and others had crafted a strategy. Suppose you added several additional terms to an equation like y = x2 that would magically enforce x to remain an integer, even within a different numerical system. This could potentially restore the correspondence to a Turing machine. Could a similar tactic be applied to all Diophantine equations? If that were the case, it would suggest that Hilbert’s problem could encode the halting problem within this new numerical system.
Illustration: Myriam Wares for Quanta Magazine
Throughout the years, Shlapentokh and her colleagues identified the necessary terms to integrate into the Diophantine equations for various types of rings, enabling them to establish that Hilbert’s problem was still undecidable in those contexts. They subsequently consolidated all remaining rings of integers to a singular case: rings that include the imaginary number i. Mathematicians determined that, in this scenario, the required additional terms could be derived from a specific equation known as an elliptic curve.
However, the elliptic curve would need to meet two essential criteria. First, it should possess infinitely many solutions. Second, if you transitioned to a different ring of integers—removing the imaginary number from your numerical system—then all solutions to the elliptic curve must retain the same foundational structure.
Ultimately, creating such an elliptic curve that functioned for every remaining ring proved to be an exceedingly complex and intricate endeavor. Yet Koymans and Pagano—specialists in elliptic curves who had collaborated closely since their graduate studies—possessed the exact expertise necessary to tackle the challenge.
Nights Without Sleep
Since his undergraduate years, Koymans had been mulling over Hilbert’s 10th problem. Throughout graduate school and his partnership with Pagano, the problem remained a persistent challenge. “I dedicated a few days each year pondering it and getting utterly blocked,” Koymans recounted. “I would explore three approaches, and they would all collapse in failure.”
In 2022, while attending a conference in Banff, Canada, he and Pagano found themselves discussing the problem. They aspired to collaborate and develop the specific elliptic curve needed to resolve the issue. After completing various other projects, they dove into the task.
