Hilbert's 10th Problem

Introducing undergraduate (or early graduate) students to topics in mathematics that might not be part of a typical curriculum is one of the things that the AMS Student Mathematical Library series does very, very well, and the book now under review is an excellent addition to this excellent series. Some of the earlier books in the series have focused on a particular concept in mathematics (such as the winding number; see Roe’s Winding Around). Others introduce an entire branch of mathematics (such as in Pollack’s A Conversational Introduction to Algebraic Number Theory or Weber’s Computability Theory). The focus in this book is on one particular theorem — its background, proof, applications, and extensions.

 

The theorem in question, as is obvious from the title of the book, is the solution to Hilbert’s Tenth Problem. Most readers of this column probably already know that in 1900 David Hilbert, at the second International Congress of Mathematicians (in Paris), delivered an address in which he discussed important (then-)unsolved problems. Some, like the Riemann Hypothesis, remain unsolved to this day; the tenth problem on his list, however, was subsequently resolved, albeit in a negative sense. This problem (hereafter, HTP) asked for an algorithm that would determine whether a given Diophantine equation (i.e., a polynomial equation in n variables with integer coefficients) has a solution in integers. In 1970, the question was, thanks to the combined work of mathematicians Martin Davis, Hilary Putnam, Julia Robinson and Yuri Matiyaesevich extending over several decades, answered in the negative: no such algorithm exists.

 

The interesting thing about the solution to HTP is that it, unlike the proofs of many longstanding conjectures, is accessible to undergraduates. Indeed, proofs of the result have previously appeared in the undergraduate textbook literature, including, for example, Hodel’s excellent book An Introduction to Mathematical Logic. However, the discussion of the problem in Hodel’s book begins on page 435 of a fairly thick text and, even though the author describes a path for getting to this chapter without having to read all of the 434 preceding pages, the size of the book may be daunting to students, who may also not be happy about paying for a very thick book and using only a part of it. The book now under review, by contrast, consists of a bit more than 200 pages, and, although it works towards the goal of proving the theorem, it also stops, so to speak, to smell the roses along the way; the reader will encounter other interesting areas of mathematics on his or her journey, including discussion of some of the other Hilbert problems. And this book, unlike Hodel’s book, contains post-proof chapters that discuss applications and extensions of the result. So, although this may not be the only undergraduate-level source of a proof of HTP, it certainly adds considerably to the existing literature on the subject. 

 

The authors have gone to some lengths to minimize the background necessary for understanding this book. Essentially, a person who understands the basic ideas of sets and functions and equivalence relations should have the technical prerequisites; even this material is quickly discussed in an Appendix. Some prior exposure to mathematical proofs, either in a proof-based post-calculus course or an “introduction to proofs” course, is also necessary. No specific background in logic, set theory or number theory is assumed; indeed, the first four chapters of the book, roughly half of it in total length, develop this necessary background. 

 

More specifically: the first chapter discusses the basics of countable and uncountable sets, including a brief look at the Continuum Hypothesis and a reference to the first of Hilbert’s problems. The authors also point the existence of paradoxes in informal set theory, which, accordingly, leads in chapter 2 to an exposition of the Zermelo-Frankel axioms of set theory, which touches on such topics as the axiom of choice, cardinal and ordinal numbers, and, in a quick footnote, the Banach-Tarski paradox. 

 

Chapter 3 discusses a selection of topics in elementary number theory: divisibility, primes, congruence, Pythagorean triples, sums of two and four squares, and the Pell equation. (It seems quite interesting that such familiar number-theoretic topics as Pell’s equation and the four squares theorem should wind up having connections to mathematical logic.) Finally, chapter 4 gives an overview of computability theory, including discussion of such topics as Gödel’s theorems, Turing machines, recursive functions and decidability. As an important step in the solution of HTP, the existence of a set U of natural numbers that is computably enumerable (i.e., is either the null set or the range of a computable function) but not decidable (there is no algorithm for determining whether an arbitrary natural number is in U) is proved. 

 

Chapter 5 comprises a proof of Hilbert’s Tenth Problem. The basic idea of the proof is as follows: one first shows, using the four-squares theorem from chapter 3, that the problem can be reduced to showing that there is no algorithm for determining whether an arbitrary Diophantine equation has a solution in natural numbers. Then one defines the notion of a Diophantine set: a set of n-tuples of natural numbers that is related, in a way the authors make precise, to the set of solutions of a Diophantine equation. From here, we can define a Diophantine function to be one whose graph is a Diophantine set. One then proves that a function is Diophantine if and only if it is recursive, which in turn is true if and only if it is computable. It is also true that a set of natural numbers is Diophantine if and only if it is computably enumerable. Once all this has been established, the negative solution to HTP flows easily from the existence of the set U described in the previous paragraph.

 

Of course, the devil is in the details, which in this case are certainly not trivial. However, the authors do an excellent job of working through them over the course of the chapter in a clear, gradual way, to the point where, in the grand finale, the actual proof of HTP reduces to a single short paragraph. In fact, the authors give alternative proofs of the result: one approach uses the Halting problem from chapter 4, the other does not. Finally, the authors give a nice historical sketch of the evolution of the solution to the problem, explaining how the various contributions by the four people identified in the second paragraph of this review gradually, over the course of several years, fit together to form a solution. 

 

Two chapters remain. Both of these, especially the last one, are more demanding than the first five, and for that reason are likely to be of less general interest than they are. The first of these relates HTP to other mathematical topics, including other famous unsolved problems. It turns out, for example, that the truth of Goldbach’s conjecture is equivalent to the non-existence of solutions of a certain Diophantine equation; thus, if an algorithm for determining whether solutions to Diophantine equations did exist, that conjecture could be resolved. The procedure used to prove this, the authors point out, is fairly general and applies to other problems as well. Thus, the authors show (omitting some details about complex analysis) that a similar result is true for the Riemann hypothesis and, in another section, for the consistency of Peano arithmetic and ZFC set theory. Another application discussed in this chapter refers to prime-generating polynomials: using Wilson’s theorem on primes (discussed in chapter 3), the authors produce a polynomial, in 25 variables, all of whose nonnegative values are prime.

 

The final chapter in the text addresses the question of the decidability of Diophantine equations over rings of integers of algebraic number fields. Much of this chapter consists of a rapid excursion through ideas of algebraic number theory and elliptic curves (including zeta and L-functions) and thus will quite likely be above the heads of most undergraduate readers. More mathematically sophisticated readers might find this chapter to be an interesting way to end the book. 

 

Throughout the text, the authors’ writing style is clear, inviting and accessible; they have succeeded in their goal of putting the solution of Hilbert’s Tenth Problem within reach of motivated undergraduates. As is the case with many other titles in this series, this book would make a good text for a very interesting senior seminar or capstone course. I think it’s also a book that non-specialist faculty members will enjoy having on their shelves, just for their own edification. 

---

 

Mark Hunacek (mhunacek@iastate.edu) teaches mathematics at Iowa State University.