Breaking Boundaries in Epistemological Unknowns

The world of mathematics is full of unreachable corners, where unsolvable problems live. Recently, two groups of mathematicians have expanded the realm of mathematical unknowability by proving a broader version of Hilbert’s famous 10th problem.

In 1900, 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,’ meaning all its statements should be provably true or false.

However, 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. 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.

Many of the questions from Hilbert’s 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, which concerns Diophantine equations: polynomials with integer coefficients. For millennia, mathematicians have sought integer solutions to these equations.

In 1970, Yuri Matiyasevich shattered the dream of a complete mathematics by showing that there is no general algorithm that can determine whether any given Diophantine equation has integer solutions—that Hilbert’s 10th problem is an undecidable problem. However, mathematicians wanted to test the reach of Matiyasevich’s conclusion.

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.

However, the useful correspondence between Turing machines and Diophantine equations falls apart when the equations are allowed to have non-integer solutions. Mathematicians needed a new approach. In 1988, Sasha Shlapentokh started playing with ideas for how to get around this problem.

After years of work, Peter Koymans and Carlo Pagano finally built the special elliptic curve needed to resolve the problem. They used a well-established technique called a quadratic twist to tweak their equation so that it would meet the required properties. However, they still had to guarantee that the solutions would look similar for rings that differed by an imaginary number.

Koymans realized that if the number they used in the quadratic twist was the product of exactly four prime numbers, then they’d get the control they needed. This allowed them to apply a method from additive combinatorics to ensure that the right combination of primes existed for every ring.

Their elliptic curve 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 by an independent team of four mathematicians who announced a new proof of the same result. Both groups hope to use their techniques 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.

However, the search for where undecidability ends and decidability begins is not over: Mathematicians are continuing to explore Hilbert’s 10th problem in new settings. ‘It reminds us there are things that are just not doable, ‘ said Andrew Granville. ‘It doesn’t matter who you are or what you are.’