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, 7x^{2}-5xy-3y^{2}+2x+4y-11=0,
or x^{3}+y^{3}=z^{3}. 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 a_{1}x+b_{1}y=c_{1}, where the
coefficients a_{1}, b_{1} 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:

ax^{2}+bxy+cy^{2}+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 by^{2}-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]):

ax^{2}+(by+d)x+(cy^{2}+ey+f)=0,

then he multiplies it by 4a:

4a^{2}x^{2} + 2*2ax(by+d) +
4a(cy^{2}+ey+f) = 0,

(2ax+by+d)^{2} - (by+d)^{2} +
4a(cy^{2}+ey+f) = 0.

Now we can introduce a new unknown Y=2ax+by+d:

Y^{2} = (by+d)^{2} - 4a(cy^{2}+ey+f),

Y^{2} = (b^{2}-4ac)y^{2}
+ 2(bd-2ae)y + (d^{2}-4af).

The number D=b^{2}-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:

DY^{2} = D^{2}y^{2} +
2Dy(bd-2ae) + D(d^{2}-4af),

DY^{2} = (Dy+bd-2ae)^{2} -
(bd-2ae)^{2} + D(d^{2}-4af).

Now let us introduce the second new unknown X=Dy+bd-2ae:

X^{2 }- DY^{2} = (bd-2ae)^{2
}- D(d^{2}-4af).

Hence, if the discriminant D=b^{2}-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

X^{2 }- DY^{2} = M,
------------(2)

where D>0, or D<0, and M = (bd-2ae)^{2 }- D(d^{2}-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 Ax^{2}+By^{2}=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 X^{2
}- DY^{2} = 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 X^{2
}- DY^{2} = 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=k^{2} 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 x^{2}-Dy^{2}=M,
where D is a positive non-square integer. The next smart idea
allowing to proceed is the following. Let us rewrite x^{2}-Dy^{2}=M
as follows:

(x+y*sqrt(D))*(x-y*sqrt(D))=M. ----------(4)

And let us denote by R_{D} the set of all real numbers
having the form x+y*sqrt(D) for some integers x, y. It appears
that the numbers from R_{D} behave like a kind of
"semi-integers".

**Exercise 4.1c.** Verify that:

a) For each u in R_{D} there is only one pair of
integers x, y such that u = x+y*sqrt(D).

b) For each pair u, v from R_{D} the numbers u+v, u-v,
u*v also belong to R_{D}.

c) Let us introduce the following notion of "norm"
for numbers of R_{D}: if u = x+y*sqrt(D), then let us
define: Norm(u) = x^{2}-Dy^{2}. Now, verify the
most remarkable fact: Norm(u*v) = Norm(u) * Norm(v). Hint:
multiply the two corresponding equalities (4).

Using Norm, our equation x^{2}-Dy^{2}=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(i^{2})=1, Norm(i^{3})=1,
Norm(i^{4})=1, ...

Norm(u)=M, Norm(u*i)=M, Norm(u*i^{2})=M,
Norm(u*i^{3})=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 R_{D}), then it has an infinite number of such
solutions: i, i^{2}, i^{3}, i^{4}, ...
And in this case, if for some non-zero integer M, the equation
Norm(u)=M has at least one solution u (in R_{D}), then it
has an infinite number of such solutions: u, u*i, u*i^{2},
u*i^{3}, ... !

Moreover:

x+y*sqrt(D) = (x-y*sqrt(D)) / (x^{2}-Dy^{2}),

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 R_{D}, if
Norm(j)=1, then the fraction i/j** **also belongs to R_{D}.
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 i_{1}.

These simple facts yield fantastic consequences! We have
denoted by i_{1} the least i from R_{D} 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>=i_{1},
i.e. j>=i*i_{1}. Thus, i*i_{1} is the least
solution greater than **i**. Hence, the sequence i_{1},
i_{1}^{2}, i_{1}^{3}, i_{1}^{4},
... represents all >1 solutions of the equation Norm(i)=1!
Each non-trivial solution of the equation x^{2}-Dy^{2}=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 x^{2}-Dy^{2}=1 a
non-trivial solution or not? If it has, then we can take the
least one: i_{1}=x_{1}+y_{1}*sqrt(D), and
calculate other solutions simply as i_{1}^{2}, i_{1}^{3},
i_{1}^{4}, ...!

Thus, it seems that the equation x^{2}-Dy^{2}=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 x^{2}-Dy^{2}=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:

x^{3}+y^{3}=z^{3},

x^{4}+y^{4}=z^{4},

x^{5}+y^{5}=z^{5},

...

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 (the10^{th}
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 s_{stop}) 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(x_{1},
...,x_{m})=0 build another Diophantine equation Q(x_{1},
...,x_{n})=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, x_{1}, ..., x_{n})=0
be Diophantine equation containing a parameter b. Verify, that
the set S = { b | Ex_{1}...Ex_{n} P(b, x_{1},
..., x_{n})=0 }, (i.e. the set of all values of b such
that the equation P(b, x_{1}, ..., x_{n})=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,
x_{1}, ..., x_{n})=0 for **every** effectively
enumerable set S of natural numbers.

Therefore (following M.Davis's theses), if R(b_{1},
..., b_{m}) is a predicate for natural numbers, then let
us call **Diophantine representation** of R any formula

Ex_{1}...Ex_{n} P(b_{1},
..., b_{m}, x_{1}, ..., x_{n})=0,

where P is a polynomial with integer coefficients, such that
this formula is true for some values (b_{1}, ..., b_{m}),
iff R(b_{1}, ..., b_{m}) 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(b_{1}, ..., b_{m})
is, in fact, a Diophantine equation P(b_{1}, ..., b_{m},
x_{1}, ..., x_{n})=0 with parameters b_{1},
..., b_{m} that has solutions in natural numbers, iff R(b_{1},
..., b_{m}) 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:

Ex_{1}...Ex_{n} P(b, x_{1},
..., x_{n})=0.

Then there would be no algorithm determining for a given value
of b, has the equation P(b, x_{1}, ..., x_{n})=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(b_{1},
..., b_{m}) can be represented by a formula

EyAz<yEx_{1}...Ex_{n} P(b_{1},
..., b_{m}, y, z, x_{1}, ..., x_{n})=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=y^{z}),
binomial coefficients (x=C_{y}^{z}), 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(b_{1}, ..., b_{m})
can be represented by a formula

Ex_{1}...Ex_{n} T(b_{1},
..., b_{m}, x_{1}, ..., x_{n})=0,

where the expression T is composed of the letters b_{1},
..., b_{m}, x_{1}, ..., x_{n}, natural
numbers, addition letter "+", subtraction letter
"-", multiplication letter "*", and a letter
representing **exponentiation** (i.e. x^{y}). For
example, x^{by+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(b_{1}, ..., b_{m}, x_{1},
..., x_{n})=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" <-> Ex_{1}...Ex_{k}
P_{1} (b, x_{1}, ..., x_{k})=0,

"b is power of 2" <-> Ex_{1}...Ex_{m}
P_{2}(b, x_{1}, ..., x_{m})=0.

Then the equation P_{1} (b, x_{1}, ..., x_{k})=0
has solutions, iff b is prime, and P_{2}(b, x_{1},
..., x_{m})=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 <-> Ex_{1}Ex_{n}
P(b, x_{1}, ..., x_{n})=0.

Take the polynomial Q = x(1-P^{2}). 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=b^{c} <-> Ex_{1}...Ex_{n}
P(a, b, c, x_{1}, ..., x_{n})=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 x^{n}
by chains of predicates x^{2}=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(b_{1}, ..., b_{m}) for natural
numbers b_{1}, ..., b_{m}. At the end we must
obtain a Diophantine representation of R, i.e. a formula

Ex_{1}...Ex_{n} P(b_{1},
..., b_{m}, x_{1}, ..., x_{n})=0

(where P is a polynomial with integer coefficients), which is
true for some (b_{1}, ..., b_{m}), iff R(b_{1},
..., b_{m}) is true.

So let us start from a computer program B_{R} that is
printing out one by one all tuples (b_{1}, ..., b_{m})
such that R(b_{1}, ..., b_{m}) is true. Then the
following function is computable:

f_{R}(b_{1}, ..., b_{m}, s) = 1, if
the program B_{R} prints the tuple (b_{1}, ..., b_{m})
within the first s seconds of its work, and

f_{R}(b_{1}, ..., b_{m}, s) = 0,
otherwise.

By Church's thesis, if f_{R} is computable, then an
appropriate Turing machine can compute it. Let M_{R} 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 F_{R}(b_{1},
..., b_{m}, s, u) representing the function f_{R}.
Hence,

R(b_{1}, ..., b_{m}) <->
Es F_{R}(b_{1}, ..., b_{1m}, 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 F_{R }is
built by using only the following means:

a) Atomic formulas t_{1}=t_{2} anf t_{1}<t_{2},
where t_{1}, t_{2} 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 t_{1}<t_{2} can be
converted as Ex(t_{1}+x+1=t_{2}). 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)Ex_{1}...Ex_{n} P(b_{1},
..., b_{k}, z, x_{1}, ..., x_{n})=0,
-----------(2)

where U is a linear function of b_{1}, ..., b_{k }with
natural coefficients, into an equivalent formula

Ey_{1}...Ey_{q} Q(b_{1},
..., b_{k}, y_{1}, ..., y_{q})=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
x^{2}-(a^{2}-1)y^{2}=1 in natural
numbers. For any a>1 this equation has an infinite sequence of
solutions (x_{n}(a), y_{n}(a)), n=0, 1, 2, ....
As a function of n, x_{n} (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=x_{n}(a)
& y = y_{n}(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=y^{z}.

4) Using the Diophantine representation of the exponential
function we will build Diophantine representations of binomial
coefficients (x=C_{y}^{z}) 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,

x_{1} = y_{1} mod m & x_{2} = y_{2}
mod m -> x_{1}+x_{2} = x_{1}+y_{2}
mod m,

x_{1} = y_{1} mod m & x_{2} = y_{2}
mod m -> x_{1}x_{2} = x_{1}y_{2}
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.