Commentary to Chapter 1 of the book

"HILBERT's TENTH PROBLEM"

written by Yuri MATIYASEVICH

 

All of Diophantus's extant writings are available in English (Heath [1910]) and Russian (Diophantus [1974]) translations with commentaries.

Hilbert's Tenth Problem is the only decision problem among the twenty-three problems that Hilbert listed.

Number theorists did not show much interest in the inverse problem of finding for a set, property, or relation a Diophantine representation or proving the impossibility of such a representation. Problems of that kind are more typical for investigations in mathematical logic. From ''The Autobiography of Julia Robinson'' (see Reid [1986]), we know that in 1948 Alfred Tarski posed the problem of proving that the set of all powers of 2 is not Diophantine. For Julia Robinson [1952], this problem was the starting point for a systematic investigation to determine whether various particular sets are Diophantine. In this same period, Martin Davis [1953] analyzed the class of Diophantine sets as a whole. In particular, he showed that this class is closed under union and intersection but not under complementation. Also, he established the equivalence of Hilbert's Tenth Problem to its counterpart for solutions in natural numbers. Another paper from that period of pioneering investigations on Hilbert's Tenth Problem is Myhill [1953].

The special forms of Diophantine representations of one-dimensional sets from Section 1.4 and Exercises 1.4, 1.6, and 1.7 were proposed by Hilary Putnam [1960].

The general Diophantine equation was reduced to one of degree 4 by Skolem [1934]. Reduction of a general Diophantine equation to a system of Diophantine equations of degree 2 having a special form was considered by Britton [1979].

The problem of the algorithmic unsolvability of equations of degree 3 was stated in Davis, Matiyasevich, and Robinson [1976]. The three unsolved problems stated above are, of course, closely related to one another. Namely, a positive answer to the first implies a positive answer to the second, which in turn implies a positive answer to the third. However, the three problems are not equivalent; a priori, the answer to the first problem could turn out to be negative while the answer to the third was positive. For the counterparts of these three problems for the case of equations of degree 2, negative answers follow from Siegel [1972].

The English translation of Chapter 1 from the book is placed on WWW with kind permition of ©The MIT Press.


URL of the original Home page of the book is http://logic.pdmi.ras.ru/~yumat/H10Pbook.
It has a mirror at http://www.informatik.uni-stuttgart.de/ifi/ti/personen/Matiyasevich/H10Pbook.
All comments can be e-mailed to the author of the book.