Hilbert, tenth problem, 10th, problem, Diophantine, equation
Back to title page.
Statement of the problem:
10. Determining the solvability of a Diophantine equation. Given a Diophantine equation with any number of unknowns and with rational integer coefficients: devise a process, which could determine by a finite number of operations whether the equation is solvable in rational integers.
(See the original statement in German at http://logic.pdmi.ras.ru/Hilbert10/stat/stat.html).
See also a collection of Hilbert web-sites at www.geometry.net.
Linear Diophantine equations
Problems that can be solved by finding solutions of algebraic equations in the domain of integer numbers are known since the very beginning of mathematics. Some of these equations do not have solutions at all. For example, the equation 2x-2y=1 cannot have solutions in the domain of integer numbers since its left-hand side is always an even number. Some other equations have a finite set of solutions. For example, the equation 3x=6 has only one solution x=2. And finally, some equations have an infinite set of integer solutions.
For example, let us solve the equation 7x-17y=1:
x = (17y+1)/7 = 2y + (3y+1)/7.
The number (3y+1)/7 must be integer, let us denote it by z. Then 3y+1=7z and x=2y+z. Thus we have arrived at the equation 3y-7z=-1 having smaller coefficients than the initial one. Let us apply our "coefficient reduction method" once more:
y = (7z-1)/3 = 2z + (z-1)/3.
The number (z-1)/3 must be integer, let us denote it by t. Then z=3t+1, and
y=2z+t=7t+2,
x=2y+z=2(7t+2)+3t+1=17t+5.
By taking t = 0, 1, -1, 2, -2, ... we obtain an infinite set of solutions of the equation 7x-17y=1 (moreover, we obtain in this way all solutions of this equations):
x = 5, y = 2;
x = 22, y = 9;
x = -12, y = -5;
x = 39, y = 16;
...
In general, the above "algebraic equations in the domain of integer numbers" can be defined as P=0, where P is a polynomial with integer coefficients and one, two or more variables (the "unknowns"). For example, 7x2-5xy-3y2+2x+4y-11=0, or x3+y3=z3. The problem to be solved is: given an equation P(x, y, ...) = 0, how could we determine, has it solutions in the domain of integer numbers, and, if it has, how to find all of them efficiently? Such equations are called Diophantine equations. They have been named after Diophantus of Alexandria (III century AD).
The above method of solving the equation 7x-17y=1 can be used to solve an arbitrary linear equation ax+by=c. If one of the coefficients is 0, for example, if b=0, then the equation ax=b has one or no integer solutions. So, let us assume that a, b are not 0. If the coefficients a, b have a common divisor d, then we have two possibilities:
a) If d does not divide the coefficient c, then the equation has no integer solutions.
b) If d divides c, then let us divide both sides of the equation by d. In this way we can arrive at an equivalent equation a1x+b1y=c1, where the coefficients a1, b1 do not have common divisors. Equations of this kind all have an infinite set of integer solutions that can be found by iterating the above "coefficient reduction method". At the end of the process we arrive at two formulas: x = et+f, y = gt+h, where e, g are not 0, and by taking t = 0, +1, -1, +2, -2, ..., we obtain all solutions of the equation.
Thus we have a simple general method allowing to determine, given an arbitrary linear Diophantine equation with two unknowns, has it solutions in integer numbers or not. A similar algorithm solves this problem for linear Diophantine equations with any other number of unknowns.
Second order Diophantine equations
The next step would be to consider second order Diophantine equations:
ax2+bxy+cy2+dx+ey+f=0, ------------(1)
where a, b, c, d, e, f are integer numbers, and at least one of the numbers a, b, c is not 0. This is a much more complicated task than solving linear equations. The general method of solving second orders equations involves some smart ideas by different people such as Bhaskara and Pierre Fermat, yet a complete solution is due to Joseph-Louis Lagrange (published in 1769).
Read about computer programs for solving the equation (1) at http://alpertron.tripod.com/METHODS.HTM.
The equation (1) always represents in the (x, y)-plane a curve (an ellipse, a hyperbola, or a parabola), one or two straight lines, one isolated point, or nothing. In the case of ellipse our equation can have only a finite set or no integer solutions. In the case of isolated point our equation can have only one or no integer solutions. In the case of straight lines our equation can be reduced to one or two separate linear equations. Hence, the most interesting cases are the "hyperbolic", and the "parabolic" ones.
If a=b=c=0, then we have a first order equation. So, let us assume that at least one of the numbers a, b, c is not 0. Moreover, we can assume that a is not 0. Indeed, if a=0 and c is not 0, then we can substitute x for y and y for x. If a=c=0, then a smart idea is necessary: substitute: x = y-X, thus obtaining an equivalent equation by2-bXy-dX+(d+e)y+f=0. So, let us assume that a is not 0.
As the first step, Lagrange rewrites (1) as a quadratic equation for x (let us follow the excellent book by H.M.Edwards [1977]):
ax2+(by+d)x+(cy2+ey+f)=0,
then he multiplies it by 4a:
4a2x2 + 2*2ax(by+d) + 4a(cy2+ey+f) = 0,
(2ax+by+d)2 - (by+d)2 + 4a(cy2+ey+f) = 0.
Now we can introduce a new unknown Y=2ax+by+d:
Y2 = (by+d)2 - 4a(cy2+ey+f),
Y2 = (b2-4ac)y2 + 2(bd-2ae)y + (d2-4af).
The number D=b2-4ac is called the discriminant of the equation (1).
Exercise 4.1a. If D=0, then we have the "parabolic" case. As a rule, this case is ignored in textbooks of number theory. Maybe, you would like to fill the gap? You could develop a simple "theory" of solving the "parabolic" equation (1) in integer numbers (or, see http://alpertron.tripod.com/METHODS.HTM).
So, let us ignore the "parabolic" case (i.e. let us assume that D is not 0), and multiply the latter equation by D:
DY2 = D2y2 + 2Dy(bd-2ae) + D(d2-4af),
DY2 = (Dy+bd-2ae)2 - (bd-2ae)2 + D(d2-4af).
Now let us introduce the second new unknown X=Dy+bd-2ae:
X2 - DY2 = (bd-2ae)2 - D(d2-4af).
Hence, if the discriminant D=b2-4ac is not 0, then each integer solution (x, y) of the equation (1) yields an integer solution
X=Dy+bd-2ae,
Y=2ax+by+d
of the equation
X2 - DY2 = M, ------------(2)
where D>0, or D<0, and M = (bd-2ae)2 - D(d2-4af).
Of course, we can revert our definition of (X, Y), i.e. we can express (x, y) by (X, Y):
y=(X-bd+2ae)/D, -----------(3)
x=(Y-by-d)/2a=(Y-b(X-bd+2ae)/D-d)/2a.
Since D and a are not 0, this means that a solution (X, Y) of the reduced equation (2) yields a solution (x, y) of the equation (1), iff X-bd+2ae is divisible by D and Y-by-d is divisible by 2a (else x and y would not be integer numbers).
Of course, this reduction process resembles the well-known reduction process of the equation (1) to its canonical form Ax2+By2=1 by a linear transformation in the field of rational numbers. The above process is "smarter" than the canonical one in that at least the coefficients of the "forward" transformation are integer numbers.
D<0 - the "elliptic" case
If D<0, then we have the "elliptic" case. Since ellipses are "finite" curves, the equation (2) has in this case a finite number or no integer solutions. Hence, so does the equation (1). All integer solutions of (1) (if any) can be found by the following process. First, let us note, that if X2 - DY2 = M, then |X|<=sqrt(|M|), and |Y|<=sqrt(|M/D|). Let us scan all pairs (X, Y) satisfying these conditions, checking for each pair the equality (2). If X2 - DY2 = M, then let us calculate from (3) the corresponding pair (x, y). If x and y both are integer numbers, then we have found a solution of the equation (1). In this way we will found all integer solutions of (1).
D>0 - the "hyperbolic" case
If D>0, then we have the "hyperbolic" case. Since hyperbolas are "infinite" curves, then, perhaps, the equation (2) may have (for some D and M) an infinite number of solutions.
If D=k2 for some integer k, then the equation (2) can be transformed in the following way:
(X-kY)(X+kY) = M.
Exercise 4.1b. Show that if M is not 0, then this equation has a finite number or no integer solutions, and define a process allowing to find all these solutions. Consider also the case M=0.
Thus, the most complicated (i.e. the most interesting) is the case when the discriminant D is a non-square positive integer.
Thus, let us consider the equation x2-Dy2=M, where D is a positive non-square integer. The next smart idea allowing to proceed is the following. Let us rewrite x2-Dy2=M as follows:
(x+y*sqrt(D))*(x-y*sqrt(D))=M. ----------(4)
And let us denote by RD the set of all real numbers having the form x+y*sqrt(D) for some integers x, y. It appears that the numbers from RD behave like a kind of "semi-integers".
Exercise 4.1c. Verify that:
a) For each u in RD there is only one pair of integers x, y such that u = x+y*sqrt(D).
b) For each pair u, v from RD the numbers u+v, u-v, u*v also belong to RD.
c) Let us introduce the following notion of "norm" for numbers of RD: if u = x+y*sqrt(D), then let us define: Norm(u) = x2-Dy2. Now, verify the most remarkable fact: Norm(u*v) = Norm(u) * Norm(v). Hint: multiply the two corresponding equalities (4).
Using Norm, our equation x2-Dy2=M containing two unknowns can be reformulated as Norm(u)=M, i.e. as an equation containing only one unknown! (Indeed, there is a one-to-one correspondence between u's and x, y's.) The second remarkable fact!
Combining these two remarkable facts we can conclude the following: if Norm(u)=M and Norm(i)=1 then
Norm(i2)=1, Norm(i3)=1, Norm(i4)=1, ...
Norm(u)=M, Norm(u*i)=M, Norm(u*i2)=M, Norm(u*i3)=M, ...
Of course, always Norm(1)=Norm(-1)=1, i.e. the equation Norm(i)=1 always has two trivial solutions i=1 and i=-1. Still, if the equation Norm(i)=1 has at least one non-trivial solution i (in RD), then it has an infinite number of such solutions: i, i2, i3, i4, ... And in this case, if for some non-zero integer M, the equation Norm(u)=M has at least one solution u (in RD), then it has an infinite number of such solutions: u, u*i, u*i2, u*i3, ... !
Moreover:
x+y*sqrt(D) = (x-y*sqrt(D)) / (x2-Dy2),
Hence, if i = x+y*sqrt(D) and Norm(i)=1, then 1/i = x-y*sqrt(D), i.e. for each pair i, j from RD, if Norm(j)=1, then the fraction i/j also belongs to RD. And: if Norm(i)=M, and Norm(j)=1, then i/j is another solution of the equation Norm(i)=M.
Exercise 4.1d. Let i = x+y*sqrt(D) be a solution of the equation Norm(i)=1. Verify that: a) if x<0, then i<0, b) if x>0 and y<0, then i<1. Hence, if i>1, then x>0 and y>0, i.e. i>=1+sqrt(D). Now, let j be another solution such that j>i. Then j/i>1 also is a solution, hence, j/i>=1+sqrt(D), j>=i+i*sqrt(D)>i+sqrt(D). I.e. the distance between two different solutions >1 is greater than sqrt(D). Thus, among the solutions >1 there exists the least one, let us denote it by i1.
These simple facts yield fantastic consequences! We have denoted by i1 the least i from RD such that i>1 and Norm(i)=1. Let i<j be two solutions of the equation Norm(i)=1. Then j/i>1 is also a solution, hence j/i>=i1, i.e. j>=i*i1. Thus, i*i1 is the least solution greater than i. Hence, the sequence i1, i12, i13, i14, ... represents all >1 solutions of the equation Norm(i)=1! Each non-trivial solution of the equation x2-Dy2=1 can be obtained - simply by changing signs - from a solution (x, y) where x, y are positive integers, i.e. from a solution >1 of the equation Norm(i)=1. Thus we have almost a complete picture!
Only one problem remains: how to detect for a given non-square integer D, has the equation x2-Dy2=1 a non-trivial solution or not? If it has, then we can take the least one: i1=x1+y1*sqrt(D), and calculate other solutions simply as i12, i13, i14, ...!
Thus, it seems that the equation x2-Dy2=1 plays a key role in the analysis of second order Diophantine equations. This is because this equation was given a separate name - Pell equation. Unfortunately, L.Euler assigned this name accidentally, ignoring the real history. To restore Justice, Fermat's equation or Indian (Bhaskara's) equation would be better terms.
Bhaskara in XII century and Pierre Fermat in XVII century knew that for a non-square D the equation x2-Dy2=1 always has an infinite set of integer solutions, they knew also how to calculate efficiently the least non-trivial solution (the so-called cyclic method, see H.M.Edwards [1977]). Still, the first complete proof of its existence obtained J.L.Lagrange - some 100 years later...
To be continued?
The problem
The next step would be considering Diophantine equations of 3rd order, 4th order etc. Consider, for example, the following famous sequence of equations:
x3+y3=z3,
x4+y4=z4,
x5+y5=z5,
...
Fermat's 350 years old hypothesis that none of these equations has non-zero integer solutions, was 100% proved as late as in September 19, 1994 (the last step is due to Andrew Wiles, see online text Fermat's Last Theorem in The CRC Concise Encyclopedia of Mathematics or Fermat's Last Theorem in Frequently Asked Questions in Mathematics, or Fermat's Last theorem in BBC Online, or Solving Fermat: Andrew Wiles in NOVA Online).
Until now, we still have no general method of solving an arbitrary 3rd order Diophantine equation. All the sophisticated methods invented by smartest number theorists apply only to very specific types of 3rd order equations. Why?
In August 6-12, 1900 in Paris the Second International Congress of Mathematicians took place. In his Wednesday morning lecture of August 8 David Hilbert stated his famous 23 mathematical problems for the coming XX century (see full text at http://aleph0.clarku.edu/~djoyce/hilbert/problems.html). The 10th of these 23 Hilbert's problems was the following:
10. Determining the solvability of a Diophantine equation.
Given a Diophantine equation with any number of unknowns and with rational integer coefficients: devise a process, which could determine by a finite number of operations whether the equation is solvable in rational integers. (See the original statement in German at http://logic.pdmi.ras.ru/Hilbert10/stat/stat.html).
Note. During his lecture Hilbert mentioned only 10 of 23 problems. The remaining 13 problems (the10th problem included) were formulated in a paper distributed among the participants of the congress (C.Reid [1996]).
In 1900 Hilbert could speak only of a positive solution of the problem ("devise a process..."). This was due not only to his young man's (in 1900 he was 38) optimism of the moment (entering a new century!). In 1900 none of even the smartest people could imagine that, maybe, a "process" detecting the solvability of such an enormous variety of equations is impossible? The idea that problems like Hilbert's, maybe, have negative solutions could appear only in 1930s, when the notion of algorithm ("process, which could determine by a finite number of operations...") was formalized. Until the class of all possible "processes" is not defined explicitly, you cannot come to the idea of proving that some "process" is impossible!
A problem is called a mass problem, iff it contains an infinite number of cases. For example, the problem of determining, is n a prime number or not, is a mass problem, since it must be solved for an infinite set of values of n. This problem is solvable: you know many algorithms for solving it (some are simple and slow, some other - faster and more complicated).
In 1936, when Turing, Post and Church introduced the first formalized concepts of algorithm, of course, they discovered also the first unsolvable mass problems. For example, the following problem appeared unsolvable: given a Turing machine M, and a natural number n, determine, will M halt (i.e. reach the final state sstop) after starting its work on a tape containing the number n? (For details, see Section 3.3). This "halting problem" was proved unsolvable in the following sense: there is no Turing machine that: a) starting on the tape containing the program of a Turing machine M and a natural number n, will: b) print 1, if M halts on n, and c) print 0, if M does nor halt on n. Referring to Church's thesis, we can say, that the halting problem of Turing machines is unsolvable for any concept of algorithm.
Another kind of unsolvable mass problems (discovered in the same 1936) are the so-called decision problems for formal theories. If T is a formal theory, then the following problem is associated with it: given a formula F, determine whether T proves F or not. In Section 6.3 we will prove that for PA, ZF, ZFC, etc. for any consistent fundamental theory T this problem is unsolvable.
The first mass problem of the traditional mathematics that was proved unsolvable, is the famous word identity problem for semigroups. Axel Thue stated this problem in 1914, and it was proved unsolvable in 1947 by E.L.Post and A.A.Markov. For details see Mendelson [1997] or Kleene [1952].
Soon after this, in his Ph.D. theses of 1950 Martin Davis (see also http://cs.nyu.edu/cs/faculty/davism/) made the first step to prove that also Hilbert's Tenth problem is unsolvable. (Martin Davis was a student of E.L.Post at New York City College and his doctorate supervisor was A.Church.)
M.Davis. On the theory of recursive unsolvability. Ph.D. Theses. Princeton University, 1950
M.Davis. Arithmetical problems and recursively enumerable predicates (abstract). "J. Symbolic. Logic", 1950, vol.15, pp.77-78
M.Davis. Arithmetical problems and recursively enumerable predicates. "J. Symbolic. Logic", 1953, vol.18, N1, pp.33-41
Still, the entire process took exactly 20 years - the last step was made in 1970 (see below).
First of all, instead of solving Diophantine equations in integer numbers we can restrict ourselves to solving of them in natural numbers - a more customary domain for mathematical logic.
Exercise 4.2. For each Diophantine equation P(x1, ...,xm)=0 build another Diophantine equation Q(x1, ...,xn)=0 such that P=0 has a natural solution, iff Q=0 has an integer solution. (Hint: every natural number can be expressed as a sum of 4 squares - a theorem proved by Lagrange in 1770).
Hence, if we had an algorithm determining the solvability of Diophantine equations in integer numbers, we had also an algorithm determining their solvability in natural numbers. So, let us try disproving the existence of the latter algorithm.
Exercise 4.3. Let P(b, x1, ..., xn)=0 be Diophantine equation containing a parameter b. Verify, that the set S = { b | Ex1...Exn P(b, x1, ..., xn)=0 }, (i.e. the set of all values of b such that the equation P(b, x1, ..., xn)=0 has a natural solution) is effectively enumerable. (Hint: write a program modeling a "parallel" checking of P=0 for all possible values of b and the unknowns, printing out the required values of b, one by one.)
Some of effectively enumerable sets are unsolvable (for such sets there is no algorithm determining for a given number n, is n in S, or not. For details see Mendelson [1997] or Kleene [1952].). If we could construct an equation with a parameter such that that set S would be unsolvable, then we had proved that Hilbert's tenth problem is unsolvable. The simplest way to build such an equation is (surprisingly): build the corresponding equation P(b, x1, ..., xn)=0 for every effectively enumerable set S of natural numbers.
Therefore (following M.Davis's theses), if R(b1, ..., bm) is a predicate for natural numbers, then let us call Diophantine representation of R any formula
Ex1...Exn P(b1, ..., bm, x1, ..., xn)=0,
where P is a polynomial with integer coefficients, such that this formula is true for some values (b1, ..., bm), iff R(b1, ..., bm) is true. For example, the predicate "b is even number" has the following Diophantine representation: Ex(b-2x=0). Hence, Diophantine representation of a predicate R(b1, ..., bm) is, in fact, a Diophantine equation P(b1, ..., bm, x1, ..., xn)=0 with parameters b1, ..., bm that has solutions in natural numbers, iff R(b1, ..., bm) is true.
M.Davis conjectured that each effectively enumerable predicate has a Diophantine representation. If this would be true, then we could take an effectively enumerable, unsolvable predicate S(b), and build its Diophantine representation:
Ex1...Exn P(b, x1, ..., xn)=0.
Then there would be no algorithm determining for a given value of b, has the equation P(b, x1, ..., xn)=0 natural solutions or not. I.e. Hilbert's 10th problem would be proved unsolvable! Q.E.D.
As the first step, M.Davis proved in 1950 the following theorem: each effectively enumerable predicate R(b1, ..., bm) can be represented by a formula
EyAz<yEx1...Exn P(b1, ..., bm, y, z, x1, ..., xn)=0.
The elimination of the remaining (one and restricted!) universal quantifier Az<y took 20 years!
Julia Robinson made another important step in 1952:
J.Robinson. Existential definability in arithmetic. "Trans. Amer. Math. Soc.", 1952, vol. 72, N3, pp.437-449
The problem was proposed to her by A.Tarski who had just produced his (non-trivial!) decision method for elementary algebra and geometry. Perhaps, this was the reason why Julia Robinson tried the opposite (to Davis's) way of solving the problem. Instead of trying to prove that every effectively enumerable predicate has a Diophantine representation she tried to construct Diophantine representations for particular important predicates: the exponentiation (i.e. the predicate x=yz), binomial coefficients (x=Cyz), the factorial function (x=y!) and the predicate "x is prime number". She was not 100% successful, yet she proved that all these predicates had Diophantine representations, if at least one "exponentially growing" function had such representation (see below).
Martin Davis and Hilary Putnam made the next step in 1960. They proved that each effectively enumerable predicate R(b1, ..., bm) can be represented by a formula
Ex1...Exn T(b1, ..., bm, x1, ..., xn)=0,
where the expression T is composed of the letters b1, ..., bm, x1, ..., xn, natural numbers, addition letter "+", subtraction letter "-", multiplication letter "*", and a letter representing exponentiation (i.e. xy). For example, xby+z-yz+3=0. In their proof an unproved number-theoretic hypothesis was used ("there exist arbitrary long arithmetic progressions of prime numbers"). Julia Robinson removed the need for this extra hypothesis and simplified the proof. The final result was published in 1961:
M.Davis, H.Putnam, J.Robinson. The decision problem for exponential Diophantine equations. "Annals of Mathematics", 1961, vol.74, N3, pp.425-436
The equations T(b1, ..., bm, x1, ..., xn)=0 are called exponential Diophantine equations. Thus, in 1961 the unsolvability of (modified) Hilbert's 10th problem for exponential Diophantine equations was proved.
This was a great success (and a wonderful piece of mathematics - see Section 4.7 below), still, even it could not remove serious doubts in the perspective of the entire process (i.e. that for each effectively enumerable predicate a "true" Diophantine representation will be obtained). For example, let take the predicates "x is prime number" and "x is power of 2", and imagine that we have Diophantine representations of them:
"b is prime number" <-> Ex1...Exk P1 (b, x1, ..., xk)=0,
"b is power of 2" <-> Ex1...Exm P2(b, x1, ..., xm)=0.
Then the equation P1 (b, x1, ..., xk)=0 has solutions, iff b is prime, and P2(b, x1, ..., xm)=0 has solutions, iff b is power of 2.
Exercise 4.4. (H.Putnam, 1960). Let the set of natural numbers A have a Diophantine representation:
b in A <-> Ex1Exn P(b, x1, ..., xn)=0.
Take the polynomial Q = x(1-P2). Verify that the set of all positive values of Q is exactly the set A.
Hence, if the set of all primes or the set of all powers of 2 had Diophantine representations, then these sets could be represented as sets of positive values of appropriate polynomials. The current number-theoretic intuition even of 1969 did not believe that this is 100% possible.
Nevertheless, in 1970 Yuri Matiyasevich succeeded in building a Diophantine representation of an "exponentially growing" function, and hence - of the exponentiation itself:
a=bc <-> Ex1...Exn P(a, b, c, x1, ..., xn)=0.
Y.Matiyasevich. Diophantovost perechislimikh mnozhestv. "Doklady Akad. Nauk SSSR", 1970, vol.191, pp.279-282 (Enumerable sets are Diophantine, in Russian, translated in: Soviet Math. Doklady, 11(2):354-358, 1970)
This paper was presented by I.M.Vinogradov on February 5, 1970 (at that time your paper could be published in "Doklady" only if you had a recommendatory visa of a Member of Academy on it). A post factum exposition of the entire story (with some improvements in proofs etc. - another wonderful piece of mathematics, see Sections 4.3, 4.4 and 4.5) was published in the paper:
Y.Matiyasevich. Diophantovi mnozhestva. "Uspekhi Math. Nauk", 1972, vol.27, pp.185-222 (Diophantine sets, in Russian, translated in: Russian Mathematical Surveys, 27(5):124-164, 1972)
Using its Diophantine representation, the exponentiation could be excluded from the representations by Davis, Putnam, and Robinson, and thus for each effectively enumerable predicate a Diophantine representation could be obtained. And thus, since February 5, 1970 we know 100% that Hilbert's Tenth problem is unsolvable.
This result explains why solving of Diophantine equations of higher orders is so difficult: because a general method of doing this is impossible. Any method determining solvability of high order equations in integer numbers can be successful only for some specific types of equations. At the same time, this sad conclusion makes the field of Diophantine equations an inexhaustible source of challenge for mathematicians!
Exercise 4.5. Show that the solvability problem of an arbitrary Diophantine equation can be reduced: a) to the problem of solvability of a system of second order Diophantine equations, and then: b) to the problem of solvability of a 4th order Diophantine equation. (Hint: replace powers xn by chains of predicates x2=y and xy=z.)
Hence, small wonder at the fact, that until now no general methods of solving are known neither for systems of second order equations, nor for 4th order equations. What about 3rd order equations? And 2nd order - with more than two unknowns?
Since 1970 many improvements were invented allowing, on the one hand, to shorten the chain of manipulations leading from Turing machines to Diophantine equations, and, on the other hand, allowing to reduce the "size" (number of unknowns, power, sum of coefficient modules etc.) of equations representing important predicates ("x is prime number", "x is power of 2" etc.). See, for example:
Y.Matiyasevich, J.Robinson. Reduction of an arbitrary Diophantine equation to one in 13 unknowns. "Acta Arithmetica", 1975, vol. 27, pp.521-553
Still, I find the initial versions of constructions and proofs proposed by Davis, Putnam, Julia Robinson, and Matiyasevich extremely beautiful (see their portraits at http://logic.pdmi.ras.ru/Hilbert10/portrait/portrait.html and http://www.bkstore.com/harvard/fac/putnam.html). This is why I present in the subsequent sections not the latest record achievements, yet the original (with only minor changes) beautiful chain of reasoning that has lead to the solution of Hilbert's Tenth problem.
For authentic comments by Martin Davis see http://www.informatik.uni-stuttgart.de/ifi/ti/personen/Matiyasevich/H10Pbook/foreword.htm.
The starting point is an arbitrary effectively enumerable predicate R(b1, ..., bm) for natural numbers b1, ..., bm. At the end we must obtain a Diophantine representation of R, i.e. a formula
Ex1...Exn P(b1, ..., bm, x1, ..., xn)=0
(where P is a polynomial with integer coefficients), which is true for some (b1, ..., bm), iff R(b1, ..., bm) is true.
So let us start from a computer program BR that is printing out one by one all tuples (b1, ..., bm) such that R(b1, ..., bm) is true. Then the following function is computable:
fR(b1, ..., bm, s) = 1, if the program BR prints the tuple (b1, ..., bm) within the first s seconds of its work, and
fR(b1, ..., bm, s) = 0, otherwise.
By Church's thesis, if fR is computable, then an appropriate Turing machine can compute it. Let MR be this Turing machine. By the representation theorem (see Section 3.3), in the language of the first order (Peano) arithmetic there is a formula FR(b1, ..., bm, s, u) representing the function fR. Hence,
R(b1, ..., bm) <-> Es FR(b1, ..., b1m, s, 1). ----------(1)
This is the first representation of our predicate R by some formula. We will transform it into a Diophantine representation.
As we know from the proof of the representation theorem (see Section 3.3) the formula FR is built by using only the following means:
a) Atomic formulas t1=t2 anf t1<t2, where t1, t2 are polynomials with natural coefficients.
b) Logical operations "&" and "v" (not the negation!).
c) Existential quantifiers Ex.
d) Only restricted universal quantifiers Ax(x<U -> ...), where U are linear functions with natural coefficients.
Note. Negations and unrestricted universal quantifiers are unwelcome as means of representing effectively enumerable predicates: if R(b, c) is effectively enumerable, then the predicates ~R(b, c) and AcR(b, c) may be not effectively enumerable.
Let us start the process of transforming (1) into a Diophantine representation.
Atomic formulas t1<t2 can be converted as Ex(t1+x+1=t2). This formula is a Diophantine representation.
Exercise 4.6. Let E(P=0) and E(Q=0) be two Diophantine representations (E's represent blocks of existential quantifiers). Show how the conjunction E(P=0) & E(Q=0) and the disjunction E(P=0) v E(Q=0) can be converted into a Diophantine representation.
And, of course, if E(P=0) is a Diophantine representation, then ExE(P=0) is also a Diophantine representation.
Thus the only hard problem that occurs during our process of transformation is the case d) - how to eliminate restricted universal quantifiers? I.e. how to convert some formula
(Az<U)Ex1...Exn P(b1, ..., bk, z, x1, ..., xn)=0, -----------(2)
where U is a linear function of b1, ..., bk with natural coefficients, into an equivalent formula
Ey1...Eyq Q(b1, ..., bk, y1, ..., yq)=0?
If we will solve this problem, then the above process of transforming (1) will yield a Diophantine representation of the predicate R. Q.E.D.
So, let us show how to eliminate Az<U. This will take the rest of Section 4. Our plan is as follows:
1) A detailed investigation of solutions of Fermat's equation x2-(a2-1)y2=1 in natural numbers. For any a>1 this equation has an infinite sequence of solutions (xn(a), yn(a)), n=0, 1, 2, .... As a function of n, xn (a) is growing exponentially.
2) Using the results of the investigation, we will build a Diophantine representation of the predicate
F(a, x, y, n) <-> a>=3 & x=xn(a) & y = yn(a).
3) Using the Diophantine representation of the predicate F(a, x, y, n) we will build a Diophantine representation of the exponential function x=yz.
4) Using the Diophantine representation of the exponential function we will build Diophantine representations of binomial coefficients (x=Cyz) and the factorial function (x=y!).
5) Using the above Diophantine representations we will show how to eliminate the restricted universal quantifier from (2).
Matiyasevich solved the problems 1), 2) in 1970, Julia Robinson - the problems 3) and 4) in 1952, the problem 5) was solved by Davis, Putnam and Julia Robinson in 1961.
In subsequent sections we will follow the practice of number theorists by using the so-called congruencies. Congruencies are a kind of equalities, yet not exact equalities. The record
x = y mod z
means that x-y is divisible by z (the module). (In Pascal we would write x mod z = y mod z). In other words, x = y mod z means that x=y+kz, but we wish to ignore items divisible by z. For example, 18 = 78 mod 10, since 78=18+6*10. A number x is congruent to 0 mod m (x = 0 mod m), iff x is divisible by m.
Exercise 4.7. Prove the following properties of congruencies (allowing treating them in most cases as "normal" equalities):
x = x mod m,
x = y mod m -> y = x mod m,
x = y mod m & y = z mod m -> x = z mod m,
x1 = y1 mod m & x2 = y2 mod m -> x1+x2 = x1+y2 mod m,
x1 = y1 mod m & x2 = y2 mod m -> x1x2 = x1y2 mod m,
xz = yz mod mz -> x = y mod m.
If z has no common divisors with m, then
xz = yz mod m -> x = y mod m.
Hilbert, tenth problem, 10th, problem, Diophantine, equation
Back to title page.