New Proofs Probe the Limits of Mathematical Truth

The world of mathematics is full of unreachable corners, where unsolvable problems live. Now, yet another has been exposed.

In 1900, the eminent mathematician David Hilbert announced a list of 23 key problems to guide the next century of mathematical research. His problems not only provided a road map for the field but reflected a more ambitious vision — to build a firm foundation from which all mathematical truths could be derived.

A key part of this vision was that mathematics should be “complete.” That is, all its statements should be provably true or false.

In the 1930s, Kurt Gödel demonstrated that this is impossible: In any mathematical system, there are statements that can be neither proved nor disproved. A few years later, Alan Turing and others built on his work, showing that mathematics is riddled with “undecidable” statements — problems that cannot be solved by any computer algorithm.

These results demonstrated that there are fundamental limits to what proof and computation are capable of. Some mathematics can simply never be known.

Hilbert’s dream was dead. But it lived on in fragments. Many of the questions from his turn-of-the-century list still evoked his vision, allowing the idea of a complete mathematics to survive in narrower contexts.

Chief among them was his 10th problem. It concerns Diophantine equations: polynomials with integer coefficients, such as x² + y² = 5.  These familiar equations are one of the most central objects of study in mathematics. For millennia, mathematicians have sought integer solutions to them. In this example, for instance, one solution is x = 1, y = 2 (since 1² + 2² = 5). Another is x = 2, y = −1.

Other Diophantine equations, such as x² + y² = 3, don’t have any integer solutions. Hilbert’s 10th problem asked whether it’s always possible to tell if a given Diophantine equation has integer solutions. Does an algorithm exist to determine this for every equation, or is the problem undecidable? There might be no hope for a complete and systematic approach to all of mathematics — or even all 23 of Hilbert’s problems — but one might still exist when it comes to Diophantine equations, forming a microcosm of his original program. “This problem is a very natural version of that dream,” said Peter Koymans of Utrecht University.

In 1970, a Russian mathematician named Yuri Matiyasevich shattered this dream. He showed that there is no general algorithm that can determine whether any given Diophantine equation has integer solutions — that Hilbert’s 10th is an undecidable problem. You might be able to come up with an algorithm that can assess most equations, but it won’t work for every single one.

In even this most straightforward kind of math, unknowability lurks.

Mathematicians wanted to test the reach of Matiyasevich’s conclusion. Say you allow your Diophantine equations to have complex solutions (numbers that can be written with real and imaginary parts, and that aren’t limited to integers). In this case, every Diophantine equation has a solution, and the answer to Hilbert’s 10th problem is a resounding yes. But there’s a whole range of Diophantine equations between ones with solutions that must be integers and ones with solutions that can be complex.

“It’s unsolvable for integers, then when you pass to much larger systems of numbers, you get solvability all of a sudden,” said Barry Mazur of Harvard University. “Where is the cutoff?”

In the 50 years since Hilbert’s 10th problem was resolved, mathematicians have been searching for this cutoff. Now, Koymans and his longtime collaborator, Carlo Pagano of Concordia University in Montreal — as well as another team of researchers working independently — have taken a major step toward that goal. Both groups have proved that, for a vast and important collection of settings beyond integers, there is likewise no general algorithm to determine if any given Diophantine equation has a solution. The work not only allows mathematicians to get a more precise view of what they can and cannot know but gives them an entirely new level of control over one of the most central objects in mathematics.

Extending From Integers

The new proofs focused on a natural extension of Hilbert’s 10th problem. The extension deals with Diophantine equations whose solutions belong to number systems that are close relatives of the integers.

If you start with the numbers 1 and −1, you can add them in different combinations to get every other integer. But say you start with a different finite set of numbers — like 1, −1 and $latex \sqrt{2}$. You can add those numbers in different combinations to get a new number system, called a ring of integers (so named even though the ring need not contain only integers). Other rings of integers can be built out of sets of numbers that include, say, the square root of −1 (the imaginary number that mathematicians call i), or the cube root of 2. Is there an algorithm that can always determine whether a given a Diophantine equation has solutions that fall in one of these rings of integers?

Mathematicians suspected that, for every single ring of integers — that is, infinitely many systems of numbers — the problem is still undecidable. This would extend the conclusion well beyond the initial, integer-focused scope of Hilbert’s 10th problem.

To prove this, they hoped to follow in the footsteps of the proof of that original problem — the one involving only integer solutions.

In general, undecidability proofs — proofs that determine whether there is a general algorithm that can answer a given question — follow the same recipe: They show that the problem of interest is equivalent to a famous undecidable problem in computer science called the halting problem. The halting problem asks whether an idealized computational device called a Turing machine, when fed a given input, will run forever or eventually halt. It’s known that there’s no algorithm that can answer this for every Turing machine.

It’s possible to think of Diophantine equations as computational devices, too. Consider the equation y = x². It has infinitely many integer solutions. If you plug in different integers for x and solve for y, the values you get all belong to a famous set of integers: the perfect squares. It is easy to imagine a computer program (that is, a Turing machine) that performs an equivalent task: “Compute the sequence of perfect squares.”

Other Diophantine equations can encode other kinds of computations.

To settle Hilbert’s original 10th problem, mathematicians built on this idea. In work that began with Julia Robinson and others around 1950 and culminated in Matiyasevich’s 1970 result, it was shown that for every Turing machine, there is a corresponding Diophantine equation. “It was completely unexpected,” said Hector Pasten of the Pontifical Catholic University of Chile in Santiago. “Diophantine equations over the integers are enough to define, basically, anything you can imagine.”

Moreover, the mathematicians set up this elegant correspondence so that if a Turing machine halted for a given input, its corresponding Diophantine equation would have an integer solution. If the Turing machine ran forever, its corresponding Diophantine equation would have no solution. But this meant that Hilbert’s 10th problem encoded the halting problem: An algorithm that could sort Diophantine equations based on whether or not they had integer solutions would also be able to sort Turing machines based on whether or not they halted.

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 = x². If you’re working in a ring of integers that includes $latex \sqrt{2}$, then you’ll end up with some new solutions, such as x = $latex \sqrt{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 = x² 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.

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.

They started with a simple equation for an elliptic curve that didn’t satisfy either of the required properties. They knew they could use a well-established technique called a quadratic twist — something they’d been studying for the better part of a decade — to tweak the equation so that it would meet the first condition. They simply had to multiply one of the equation’s variables by a specific number, and they’d get a new elliptic curve with infinitely many solutions.

But this left them with a problem. They had no way to guarantee that this new curve satisfied the second property — that its solutions would look similar for rings that differed by an imaginary number. The mathematicians needed to get better control over the quadratic twist.

They got stuck. “I had this dark feeling,” Koymans said. “I started to get suspicious that we were missing something.”

Then, in summer 2024, while working on a different problem, the pair had to use quadratic twists again. One night, in the middle of this research, Koymans found himself lying awake, unable to stop thinking about Hilbert’s 10th problem.

That other work, Koymans realized, gave them an important hint, one of those strange and surprising mathematical concordances that sometimes appear: If the number they used in the quadratic twist was the product of exactly three prime numbers, then they’d get the control they needed to guarantee the second property. But because their elliptic curve had to be constructed so carefully and meet so many specifications, there were lots of additional constraints on what those three primes could be. Could Koymans and Pagano find ones that worked — no matter which ring they were using?

Pagano happened to have planned a visit to the Swiss Federal Institute of Technology Zurich, where Koymans was working at the time, a few days later. They spent the next week struggling at the blackboard together, trying to find primes that would meet all the constraints. Finally, they figured out that they had to use four primes, rather than three, to construct their quadratic twist. This allowed them to apply a method from an entirely separate area of math, called additive combinatorics, to ensure that the right combination of primes existed for every ring.

That was the final piece: They’d built their elliptic curve. It gave them the recipe they needed to add terms to their Diophantine equations, which then enabled them to encode Turing machines — and the halting problem — in those equations, regardless of what number system they used. It was settled. Hilbert’s 10th problem is undecidable for every ring of integers.

The result was solidified further last Thursday, when, less than two months after Koymans and Pagano posted their paper online, an independent team of four mathematicians announced a new proof of the same result. Instead of looking for a special elliptic curve, they had relied on a different kind of equation to do the same job.

Both groups hope to use their techniques — which give them unprecedented control over elliptic curves and related equations — to make progress on other problems as well. “There’s a possibility that the two methods could be used together to do even more,” said Manjul Bhargava, a mathematician at Princeton University and one of the authors of the second proof.

Meanwhile, the search for where undecidability ends and decidability begins is not over: Mathematicians are continuing to explore Hilbert’s 10th problem in new settings.

This is just one of many questions, according to Andrew Granville of the University of Montreal, that “reflect the philosophical side of what in the world is true.”

All knowledge has limits. “It reminds us there are things that are just not doable,” Granville said. “It doesn’t matter who you are or what you are.”