Namespaces
Variants
Actions

Difference between revisions of "Diophantine equations, solvability problem of"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(LaTeX)
Line 1: Line 1:
 +
{{TEX|done}}
 
''decision problem of Diophantine sets''
 
''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|Diophantine equations]]).
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d0326201.png" /> is equivalent to the equation
+
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
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d0326202.png" /></td> </tr></table>
+
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 [[#References|[1]]].
 
The problem of finding such a universal method for detecting solutions in integers was posed by D. Hilbert [[#References|[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 [[#References|[2]]] appeared, saying that any [[Enumerable set|enumerable set]] is also a [[Diophantine set|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.
+
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 [[#References|[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 [[#References|[3]]]: Each enumerable set is an exponential-Diophantine set, i.e. for each enumerable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d0326203.png" /> there exist expressions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d0326204.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d0326205.png" /> constructed from natural numbers and variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d0326206.png" /> by addition, multiplication and exponentiation, such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d0326207.png" /> if and only if the exponential-Diophantine equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d0326208.png" /> is solvable for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d0326209.png" />. 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 [[#References|[4]]] that such a conversion is possible if a Diophantine equation
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d03262010.png" /></td> </tr></table>
 
  
exists with the following two properties: 1) in any solution of this equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d03262011.png" />; 2) for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d03262012.png" /> there exists a solution in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d03262013.png" /> (such an equation is said to have exponential growth). An example of a Diophantine equation with exponential growth, which was first established in [[#References|[5]]], completed the proof of the hypothesis that enumerable sets are Diophantine (for a complete proof of Davis' hypothesis see [[#References|[6]]], [[#References|[7]]], [[#References|[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.
+
A weaker statement was demonstrated in 1961 [[#References|[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 [[#References|[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 [[#References|[5]]], completed the proof of the hypothesis that enumerable sets are Diophantine (for a complete proof of Davis' hypothesis see [[#References|[6]]], [[#References|[7]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d03262014.png" /> with integer coefficients such that there is no algorithm by which one can tell, from a known value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d03262015.png" />, whether or not the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d03262016.png" /> can be solved for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032620/d03262017.png" /> and, a fortiori, no algorithm exists for the recognition of the existence of solutions of an arbitrary Diophantine equation.
+
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.
 
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====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  D. Hilbert,  "Mathematical problems"  ''Bull. Amer. Math. Soc.'' , '''8''' :  10  (1902)  pp. 437–479</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  M. Davis,  "Arithmetical problems and recursively enumerable predicates"  ''J. Symbol. Logic'' , '''18''' :  1  (1953)  pp. 33–41</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  M. Davis,  H. Putnam,  J. Robinson,  "The decision problem for exponential Diophantine equations"  ''Ann. of Math.'' , '''74''' :  3  (1961)  pp. 425–436</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  J. Robinson,  "Existential definability in arithmetic"  ''Trans. Amer. Math. Soc.'' , '''72''' :  3  (1952)  pp. 437–449</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  Yu.V. Matiyasevich,  "Diophantine sets"  ''Russ. Math. Surveys'' , '''27''' :  5  (1972)  pp. 124–164  ''Uspekhi Mat. Nauk'' , '''27''' :  5  (1972)  pp. 185–222</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  Yu.I. Manin,  "A course in mathematical logic" , Springer  (1977)  (Translated from Russian)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  D. Hilbert,  "Mathematical problems"  ''Bull. Amer. Math. Soc.'' , '''8''' :  10  (1902)  pp. 437–479</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  M. Davis,  "Arithmetical problems and recursively enumerable predicates"  ''J. Symbol. Logic'' , '''18''' :  1  (1953)  pp. 33–41</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  M. Davis,  H. Putnam,  J. Robinson,  "The decision problem for exponential Diophantine equations"  ''Ann. of Math.'' , '''74''' :  3  (1961)  pp. 425–436</TD></TR>
 +
<TR><TD valign="top">[4]</TD> <TD valign="top">  J. Robinson,  "Existential definability in arithmetic"  ''Trans. Amer. Math. Soc.'' , '''72''' :  3  (1952)  pp. 437–449</TD></TR>
 +
<TR><TD valign="top">[5]</TD> <TD valign="top">  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</TD></TR>
 +
<TR><TD valign="top">[6]</TD> <TD valign="top">  Yu.V. Matiyasevich,  "Diophantine sets"  ''Russ. Math. Surveys'' , '''27''' :  5  (1972)  pp. 124–164  ''Uspekhi Mat. Nauk'' , '''27''' :  5  (1972)  pp. 185–222</TD></TR>
 +
<TR><TD valign="top">[7]</TD> <TD valign="top">  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</TD></TR>
 +
<TR><TD valign="top">[8]</TD> <TD valign="top">  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</TD></TR>
 +
<TR><TD valign="top">[9]</TD> <TD valign="top">  Yu.I. Manin,  "A course in mathematical logic" , Springer  (1977)  (Translated from Russian)</TD></TR>
 +
</table>
  
  
Line 30: Line 42:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Davis,  "Hilbert's tenth problem is unsolvable"  ''Amer. Math. Monthly'' , '''80'''  (1973)  pp. 233–269</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Davis,  "Hilbert's tenth problem is unsolvable"  ''Amer. Math. Monthly'' , '''80'''  (1973)  pp. 233–269</TD></TR>
 +
</table>

Revision as of 19:36, 31 December 2014

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)


Comments

References

[a1] M. Davis, "Hilbert's tenth problem is unsolvable" Amer. Math. Monthly , 80 (1973) pp. 233–269
How to Cite This Entry:
Diophantine equations, solvability problem of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Diophantine_equations,_solvability_problem_of&oldid=36012
This article was adapted from an original article by Yu.V. Matiyasevich (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article