Hilbert’s 10th Problem and the Limits of Computation
Benjamin Skuse
Mathematics could be renamed the glacial science. 125 years since revered German mathematician David Hilbert listed 23 problems he felt were worthy challenges upon which the community should focus their minds for the next century, just 10 are generally accepted as resolved.
One of the most interesting of these solved problems, particularly in the context of the main talking points at the 12th Heidelberg Laureate Forum, is Hilbert’s 10th problem, which Hilbert stated roughly as follows:
Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients, devise a process involving a finite number of operations to determine whether the equation is solvable in rational integers.
In simpler terms Hilbert himself did not use:
Design an algorithm that decides whether any given polynomial equation \( p(x_{1}, . . . , x_{n}) = 0 \) over the integers has an integral solution \( x_{1}, . . . , x_{n} \in \mathbb{Z} \).
In even simpler terms, Hilbert wanted to know if there was a universal way to know whether it is always possible to tell if a polynomial equation with integer coefficients has integer solutions; does something fundamental set, for example, \(3x + 6y = 18\) (which has several solutions including \(x = 4, y = 1\)) apart from \(2x + 10y = 17\), which has no solution?
Computer Science to the Rescue
No progress was made on this problem until computer science had matured to the point where it could come to the aid of number theory in the 1950s and 60s. American mathematician and computer scientist Martin Davis was the first to make any inroads. In the early 1950s, he posited that a set is Diophantine if and only if it is recursively enumerable.
Here, a ‘Diophantine set’ is a set of integers that can be defined by a Diophantine equation or a system of Diophantine equations, and to be ‘recursively enumerable’ means listable. Importantly, a recursively enumerable set is another way of describing an algorithm; or, more precisely, it is the set of outputs or elements that an algorithm can list, given infinite time.
Around the same time Davis was formulating this general result, American mathematician Julia Robinson, who began studying Hilbert’s 10th problem in 1948, was looking at special cases of Diophantine relations and building a conjecture that would become known as the Julia Robinson hypothesis, or simply JR.
Robinson’s work focused on constructing a Diophantine relation that satisfies the fast-growing properties:
- \( J(a,b) \) implies \(a \lt b^{b}\)
- For every positive integer \( k \), there exist \( a \) and \(b \) such that \( J(a,b) \) and \(a \gt b^{k}\),
and showing that if such a relation exists, as she suspected it did, then the exponential relation is also Diophantine.
Fast forward almost a decade and Martin Davis and his collaborator American analytical philosopher Hilary Putnam teamed up with Robinson – who would later become the first female mathematician to be elected to the National Academy of Sciences and first female president of the American Mathematical Society – to make another critical breakthrough. In 1961, they published a paper revealing that listable sets and exponential Diophantine sets are one and the same.
If JR was ever proven true, meaning that exponentiation was Diophantine, then the new paper would mean listable sets were Diophantine, and therefore Hilbert’s 10th problem would be unsolvable. Sadly, proving JR was tricky.
A Birthday Wish Come True
“It was the custom in our family to have a get-together for each family member’s birthday,” recalled Robinson in an interview for the 1990 book More Mathematical People. “When it came time for me to blow out the candles on my cake, I always wished, year after year, that the Tenth Problem would be solved – not that I would solve it, but just that it would be solved. I felt that I couldn’t bear to die without knowing the answer.”
Robinson’s wish came true in 1970. Russian mathematician Yuri Matiyasevich was equally obsessed with Hilbert’s 10th problem. In 1969, he was asked to referee a paper by Robinson in which she introduced a new idea concerning the periodicity of sequences of solutions of a well-known Diophantine equation called Pell’s equation (\( x^{2} – ny^{2} = 1\), where \( n \) is a positive nonsquare integer).
This work inspired him to adapt the idea to a different sequence: the Fibonacci numbers (\( x_{n+2} = x_{n+1} + x_{n} = 0, 1, 1, 2, 3, 5, 8,…\)). When he did this, everything fell into place. By showing that the sequence of Fibonacci numbers is Diophantine, he thereby proved that JR was true, listable sets were Diophantine, and Hilbert’s 10th problem was unsolvable.
You may ask, what on Earth has the undecidability of Hilbert’s 10th problem, solved 55 years ago, got to do with topical conversations at the 12th Heidelberg Laureate Forum? Well, a significant amount of time in the lecture halls and during the coffee breaks was spent asking questions such as, how exactly will the roles of computers and human mathematicians change as AI advances? And just how much of mathematics is solvable by machines?
Proving that an easily understood mathematical challenge – determining whether every Diophantine equation restricted to integers has a solution – cannot be solved by mechanical means is a vivid example showing the limitations of computing and AI in mathematics.
But it is also puzzling. If Diophantine equations are allowed to have complex number solutions instead of just integer ones, Hilbert’s 10th problem is actually trivial and always solvable by a general algorithm, even though integers can be written as complex numbers; the integers are a subset of the complex numbers! Might there be other sets of numbers over which Hilbert’s 10th problem is unsolvable too?
Beyond the Integers
Manjul Bhargava (Fields Medal – 2014) was scheduled to offer fresh insight into this question at this year’s Forum. It was a shame that he ultimately could not attend, because recently he and his collaborators posted an arXiv preprint detailing their discovery of one of these special sets; discovered independently around the same time by Peter Koymans and Carlo Pagano.
Using completely different methods, both teams proved that Hilbert’s 10th problem is unsolvable for every ring of integers. The ring of integers \( \mathcal{O}_{K} \) of a number field \( K \), which is a finite extension of the rational numbers, is the set of all integers contained within \( K \). Crucially, \( \mathcal{O}_{K} \) is always a set that is the same size as or bigger than the set of ordinary integers, often including infinitely many numbers that are not in the set of integers. This result makes the potential solution space for a machine mathematician, a future superhuman AI mathematician, just that little bit smaller.
The next challenge is widely regarded as one of the biggest open problems in the area of undecidability in number theory: proving whether Hilbert’s 10th problem over the field \( \mathbb{Q} \) of rational numbers is unsolvable too.
Solving this one way or another would be profound. It would either mean that there is an inherent, algorithmic limit to what can be determined about rational-valued polynomial equations, shrinking machine-based mathematical problem solving even further, or that an algorithm exists to solve all rational Diophantine equations. And at the same time, it would bring number theorists closer to understanding the ultimate source of mathematical undecidability.
Either way, pursuing an answer will no doubt introduce entirely new frameworks and techniques to study rational solutions, ushering in a new era of exploration in the theory of computation and number theory.
The post Hilbert’s 10th Problem and the Limits of Computation originally appeared on the HLFF SciLogs blog.