Author: silverxz

  People have a peculiar fascination with mathematical conjectures and the stories of how they were solved. Goldbach’s conjecture and Chen Jingrun, Fermat’s Last Theorem and Wiles, solutions by radicals and Abel and Galois: such examples have found their way into elementary education. Children may not even understand the statements of these problems, yet they enjoy stories in which a legendary figure resolves a long-standing conjecture, much as they enjoy tales of heroes and dragons. This is probably how Hilbert’s name first reached the wider public:

  David Hilbert (1862-1943) was the most celebrated mathematician of his era. In 1900, Hilbert assembled 23 mathematical problems that were then unresolved. Some were sharply defined (Problem 8, for example, is the Riemann hypothesis), while others were not individual questions at all, but research programs or even small fields containing many questions. They later acquired a standard collective name: Hilbert’s 23 problems.

David Hilbert

  This much is a familiar topic in popular mathematics, but many accounts stop here. These problems stood at the frontier in 1900, and several remain unsolved today. Most people’s mathematical education, meanwhile, focuses on work from the nineteenth century or earlier, developed by giants such as Newton, Euler, Gauss, Cauchy, and Riemann. For most readers, simply understanding what Hilbert’s 23 problems ask is difficult, let alone understanding their solutions.

  Fortunately, a few of them are within reach. Hilbert’s Tenth Problem is just barely one of those. Let us first see what it asks. Hilbert’s original statement can be rendered roughly as follows:

Hilbert’s Tenth Problem

Given a Diophantine equation in any number of unknowns: devise a procedure that determines, in finitely many operations, whether the equation has an integer solution.

  What is a Diophantine equation? Simply put, it is an equation formed from a multivariable polynomial with integer coefficients. For example, , or, for something more complicated, . Any polynomial equation with integer coefficients qualifies. Diophantine equations encompass many familiar problems. For example, is the Diophantine equation for Pythagorean triples, while is the equation associated with Fermat’s Last Theorem. The scope is enormous: the statement is simple, but the problem is intricate and important.

  The crucial point lies in the second half: devise a procedure (process) that, in a finite number of operations, determines…

  Some readers may wonder why Hilbert did not simply ask for an “algorithm.” In 1900, Hilbert did not yet have a formal notion of an algorithm. He already had some of the idea in mind: the “procedure” should stop after finitely many operations, and those operations should be mechanical. But he did not yet know how to characterize computation and algorithms mathematically. That work belonged to Turing and others, and Turing would not be born for another 12 years.

  Hilbert was inclined to assume that such a procedure existed: he did not ask whether one existed, but asked us to devise it. Only in Turing’s era did we learn that not every problem admits an algorithm. Hilbert’s Tenth Problem turned out to be one of them: the algorithm Hilbert requested does not exist.

  This is why I call the problem only “just barely” within reach. If you have used a computer, written programs, and have a rough idea of how a Turing machine works, then you already stand on the shoulders of giants and can understand ideas Hilbert never had. You are not impossibly far from understanding the solution, though not especially close either, hence “just barely.” Once you have solved many problems with programs, you may naturally wonder what a problem that no program can solve looks like. Hilbert’s Tenth Problem is one such example.

  That also describes the intended readership: computer-science undergraduates, or anyone with a basic intuitive grasp of algorithms and computation. The first draft was my final project for an undergraduate Theory of Computation course. I have expanded it and tried to lower the barrier to entry. I will avoid skipping crucial steps and go into real depth, while keeping this a popular account rather than a set of lecture notes.

  If you lack some of the prerequisites, you can still read the next installment on the history of Hilbert’s Tenth Problem as a story; it is the less technical part of the series. The proof sections that follow assume that you know what a Turing machine is, and preferably what recursive and recursively enumerable sets are. If not, a brief detour through another explainer or textbook should be enough; none of this is difficult with a computing background. If necessary, I may also add an appendix reviewing the essentials for readers whose foundations are less secure, though I suspect few people would read it, so I will probably keep putting it off.

  Before this series, the Chinese-language web had little beyond an article by Lu Changhai that covered the history of Hilbert’s Tenth Problem in some detail, without attempting the proof. I am writing partly to organize and record what I have learned, and partly, rather boldly, to fill that gap by telling the history from my perspective and presenting the proof. While writing, I deliberately relied on primary sources rather than repeatedly consulting Lu’s article, so as not to become trapped in a single framing. I nevertheless owe that article a debt and include its link below for reference.

References

  Lu Changhai. “A Survey of Hilbert’s Tenth Problem (Part I).”

  https://www.changhai.org/articles/science/mathematics/hilbert10/1.php