Diophantine equations, solvability problem of

decision problem of Diophantine sets

The problem of finding an algorithm by which to tell whether or not any Diophantine equation has a solution (cf. Diophantine equations).

An essential feature of the problem as posed is to find a universal method which would be suitable for any equation (all known methods of telling whether or not a given Diophantine equation has a solution are applicable only to equations of specific (narrower or broader) classes). Such a method would also permit one to solve systems of Diophantine equations, since the system $P_1=0, \ldots, P_k=0$ is equivalent to the equation $$ P_1^2 + \cdots + P_k^2 = 0 \ . $$

The problem of finding such a universal method for detecting solutions in integers was posed by D. Hilbert [1].

In the early 1950s there appeared the first studies aimed at proving the non-existence of a decision algorithm of Diophantine equations. At this time Davis' hypothesis [2] appeared, saying that any enumerable set is also a Diophantine set. Since examples of recursively enumerable but algorithmically unsolvable sets are known, it immediately follows, if Davis' hypothesis is correct, that the problem of solvability of Diophantine equations has a negative solution.

A weaker statement was demonstrated in 1961 [3]: Each enumerable set is an exponential-Diophantine set, i.e. for each enumerable set $\mathcal{M}$ there exist expressions $K$ and $L$ constructed from natural numbers and variables $a,z_1,\ldots,z_n$ by addition, multiplication and exponentiation, such that $a \in \mathcal{M}$ if and only if the exponential-Diophantine equation $K=L$ is solvable for $z_1,\ldots,z_n$. After this, for Davis' hypothesis it remained to be proved that a method for converting an arbitrary exponential-Diophantine equation into some Diophantine equation which also has (or has not) at the same time a solution, exists. It was shown [4] that such a conversion is possible if a Diophantine equation $$ G(u,v,z_1,\ldots,z_n) = 0 $$ exists with the following two properties: 1) in any solution of this equation $v \le u^u$; 2) for any $k$ there exists a solution in which $v > u^k$ (such an equation is said to have exponential growth). An example of a Diophantine equation with exponential growth, which was first established in [5], completed the proof of the hypothesis that enumerable sets are Diophantine (for a complete proof of Davis' hypothesis see [6], [7], [9]). The converse theorem, viz. that all Diophantine sets are enumerable, is readily proved. Thus, the class of enumerable sets is identical with the class of Diophantine sets.

It follows from this result that it is possible to find a specific polynomial $W(a,z_1,\ldots,z_n)$ with integer coefficients such that there is no algorithm by which one can tell, from a known value of $a$, whether or not the equation $W(a,z_1,\ldots,z_n) = 0$ can be solved for $z_1,\ldots,z_n$ and, a fortiori, no algorithm exists for the recognition of the existence of solutions of an arbitrary Diophantine equation.

The problem of the existence of an algorithm for the recognition of the solvability of Diophantine equations in rational numbers is equivalent to the problem of the existence of an algorithm for the recognition of the solvability of homogeneous Diophantine equations in integers. This important question is still (1988) open and has not been studied to a sufficient extent.

References

[1]	D. Hilbert, "Mathematical problems" Bull. Amer. Math. Soc. , 8 : 10 (1902) pp. 437–479
[2]	M. Davis, "Arithmetical problems and recursively enumerable predicates" J. Symbol. Logic , 18 : 1 (1953) pp. 33–41
[3]	M. Davis, H. Putnam, J. Robinson, "The decision problem for exponential Diophantine equations" Ann. of Math. , 74 : 3 (1961) pp. 425–436
[4]	J. Robinson, "Existential definability in arithmetic" Trans. Amer. Math. Soc. , 72 : 3 (1952) pp. 437–449
[5]	Yu.V. Matiyasevich, "Enumerable sets are diophantine" Soviet Math. Dokl. , 11 : 2 (1970) pp. 354–358 Dokl. Akad. Nauk. SSSR , 191 : 2 (1970) pp. 279–282
[6]	Yu.V. Matiyasevich, "Diophantine sets" Russ. Math. Surveys , 27 : 5 (1972) pp. 124–164 Uspekhi Mat. Nauk , 27 : 5 (1972) pp. 185–222
[7]	Yu.I. Manin, "Hilbert's tenth problem" J. Soviet Math. , 3 : 1 (1975) pp. 164–184 Itogi Nauk. i Tekhn. Sovrem. Probl. Mat. , 1 (1973) pp. 5–37
[8]	J. Robinson, "Hilbert's tenth problem. Diophantine equations: positive aspects of a negative solution" F.E. Browder (ed.) , Mathematical developments arising from Hilbert problems , Proc. Symp. Pure Math. , 28 , Amer. Math. Soc. (1976) pp. 323–375
[9]	Yu.I. Manin, "A course in mathematical logic" , Springer (1977) (Translated from Russian)

References

[a1]	M. Davis, "Hilbert's tenth problem is unsolvable" Amer. Math. Monthly , 80 (1973) pp. 233–269