1.1 Diophantine equations as a decision problem
Let us recall that a Diophantine equation is an equation of the form
| D(x1,...,xm)=0, | (1.1.1) |
where D is a polynomial with integer coefficients. In addition to (1.1.1), Diophantine equations can be written in the more general form
| DL(x1,..., xm) = DR(x1,..., xm) | (1.1.2) |
where DL and DR are again polynomials with integer coefficients. When we speak of ''an arbitrary Diophantine equation,'' we shall have in mind an equation of the form (1.1.1) since an equation of the form (1.1.2) can easily be transformed into an equation of the form (1.1.1) by transposing all the terms to the left-hand side. However, we will often use the notation (1.1.2) for particular equations if this form turns out to be easier to grasp. We shall also take another advantage of the more general form (1.1.2); namely, in this case we can demand that DL and DR are polynomials with non-negative coefficients.
Diophantine equations typically have several unknowns, and we must distinguish the degree of (1.1.1) with respect to a given unknown xi and the (total) degree of (1.1.1), i.e., the maximum, over all the monomials constituting the polynomial D, of the sum of the degrees of the individual variables in such a monomial.
In specifying a Diophantine equation it is necessary to provide not only a representation of the form (1.1.1) (or equivalently (1.1.2)), but also to indicate the range of the unknowns. Hilbert, in his Tenth Problem, spoke of solutions in rational integers. In the present book we shall just use the term '' integers'' because the case of algebraic integers will be almost completely ignored. (The cases of other ranges for the unknowns will be considered in Sections 1.3, 7.3, and 7.4.)
Hilbert's Tenth Problem is an example of a decision problem. A decision problem consists of countably many individual problems, for each of which an answer ''YES'' or ''NO'' is to be given. We shall refer to these individual problems as subproblems of the corresponding decision problem. Each individual subproblem is specified by a finite amount of information. (In the case of Hilbert's Tenth Problem, this information is the polynomial D from (1.1.1)).
The essence of a decision problem lies in the requirement to find a single method that can be used for obtaining the answer to any of the individual subproblems. Since Diophantus's time, number theorists have found solutions for many Diophantine equations and have established the unsolvability of many other equations. However, for many particular classes of equations, and even for certain individual equations, it was necessary to invent a specific method. In the Tenth Problem, Hilbert asked for a universal method for deciding the solvability of Diophantine equations.
A decision problem can be solved either directly or indirectly. In the the former case, one provides a procedure for finding the answer to any individual subproblem, while in the latter case one reduces the given decision problem to another, the solvability of which has already been shown. We will not give a formal definition of what constitutes such a reduction, because the general theory of reducibility will not be needed, and in each particular case of such a reduction it will be clear from the context what is actually meant.
An unsolvability proof for a decision problem can also be either direct or indirect. In the latter case one also reduces one problem to another, but what is required is a reduction in the reverse direction. Namely, to establish the unsolvability of a decision problem, one has to reduce to it another problem the unsolvability of which has already been shown. In the first few chapters of this book, we reduce to Hilbert's Tenth Problem successively more and more complicated problems. This chain of reductions should lead ultimately to a problem for which we can give a direct proof of unsolvability. However, to be able to give such a proof, we need some way of surveying all conceivable methods of solving the problem. The possibility of doing this became available only after the development of the mathematically rigorous general notion of computability. All the necessary definitions are given in Chapter 5, where we establish the algorithmic unsolvability of Hilbert's Tenth Problem.
The English translation of Chapter 1 from the book is placed on WWW with kind permition of ©The MIT Press.