View source for Matiyasevich theorem

<strong>Matiyasevich's theorem</strong> (also known as the
'''DPRM-theorem''' or the '''MRDP-theorem''')  implies that the notion of
[http://www.example.com effectively enumerable set] from computability theory
coincides with the notion of [http://en.wikipedia.org/wiki/Diophantine_set Diophantine set] from
number theory.

==Definitions and results==

A set <math>\mathfrak{M}</math> of non-negative integers is called
'''Diophantine''' provided that
there exists a [http://www.example.com polynomial] <math>P(a,x_1,\dots,x_m)</math>
with integer coefficients such that the one-parameter [http://en.wikipedia.org/wiki/Diophantine_equation Diophantine equation]
:<math>P(a,x_1,\dots,x_m)=0</math> 
has a solution in the unknowns  <math>x_1,\dots,x_m</math>
if and only if the value of the parameter <math>a</math> 
belongs to the set <math>\mathfrak{M}.</math> [[Matiyasevich theorem/Range of unknowns|Range of unknowns]]
The equivalence 
:<math>a \in \mathfrak{M} \iff \exists  x_1\dots x_m
\{P(a,x_1,\dots,x_m)=0\}
</math>
is called a '''Diophantine representation''' of the set 
<math>\mathfrak{M}.</math>  [[Matiyasevich theorem/Examples of Diophantine sets|Examples of Diophantine sets]]


A set <math>\mathfrak{M}</math> of natural numbers is called
'''effectively enumerable''', or '''listable''' provided 
that there exists an [[algorithm]] which, working potentially
infinitely long, would output all elements of the 
set&nbsp;<math>\mathfrak{M}</math> in some order and only those. [[Matiyasevich theorem/Examples of listable sets|Examples of listable sets]]

The fact that every Diophantine set is listable is evident, and
the theorem  states that the converse is also true:
 ''Every listable set is Diophantine.''

The proof of the theorem 
is constructive: ''if a listable set is presented in any standard way, one can actually write down corresponding polynomial for a Diophantine representation of this set.''

__AUTOLINKER{1|normal form}

==History==

The equations, and afterwards sets and representations are named after the
Greek mathematician   [http://en.wikipedia.org/wiki/Diophantus Diophantus].

The existence of Diophantine representations for all listable sets was
first conjectured by [http://en.wikipedia.org/wiki/Martin_Davis Martin Davis] at the end of 1940's. At that time 
he made the first step towards the final proof of this conjecture by showing
that every listable set has an arithmetical representation with a single
bounded universal quantifier; such representations became known as 
'''Davis normal form'''. This was an improvement of a previous
fundamental result of [http://en.wikipedia.org/wiki/Kurt_Gödel Kurt Gödel] concerning the existence of arithmetical representations
of a general form for all listable set.

A weaker form of Davis' conjecture was established in 1961 by [http://en.wikipedia.org/wiki/Martin_Davis Martin Davis],
[http://en.wikipedia.org/wiki/Hilary_Putnam Hilary Putnam], and [http://en.wikipedia.org/wiki/Julia_Robinson Julia Robinson]; namely they  considered the
broader class of so called ''exponential Diophantine equations'' and
obtained a purely existential ''exponential Diophantine representations''
for all listable sets.

Already at the beginning of 1950's Julia Robinson had found a sufficient condition for the possibility of
transforming an arbitrary exponential Diophantine equation into an 
equivalent Diophantine equation.

The final step, performed by [http://en.wikipedia.org/wiki/Yuri_Matiyasevich Yuri Matiyasevich] in 1970, consisted in fulfilling this condition of Julia Robinson by providing a Diophantine representation of the set of ordered pairs <math> (u,v) </math> such that <math> v=F_{2u}</math> where <math>F_n</math> is the <math>n</math>th 
[http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number]. 

Matiyasevich's theorem is often referred to as the '''DPRM-theorem''' (or the '''MRDP-theorem''') after 
Davis-Putnam-Robinson-Matiyasevich.

==Generalizations and extensions==


The Diophantine equation of the general form 
:<math>P(a,x_1,\dots,x_m)=0</math> 
in the definition of a Diophantine representation can be replaced 
by a Diophantine equation of a special kind, namely,  with the parameter 
isolated in the right-hand side, thus giving a representation of form
:<math>
a \in \mathfrak{M} \iff \exists  x_1\dots x_n
\{Q(x_1,\dots,x_n)=a\}
</math>
In other word, 
''every Diophantine (and hence every listable) set  of non-negative integers is the set of all values assumed by some polynomial with integer coefficients with many variables''.

The definitions of Diophantine and listable set can be generalized in a 
natural way to sets of pairs, triples, ..., <math>n</math>-tuples of
non-negative integers, and the theorem easily extends to these cases:
''every listable set of <math>n</math>-tuples of non-negative integers has a representation of the form''
:<math>
\langle a_1,\dots,a_n \rangle \in \mathfrak{M} \iff \exists  x_1\dots x_m
\{P(a_1,\dots,a_n,x_1,\dots,x_m)=0\}
</math>
''with some polynomial <math>P(a_1,\dots,a_n,x_1,\dots,x_m)</math> with integer coefficients.''

Moreover, it is possible to bound both the degree of such a polynomial in the unknowns, and the
number of unknowns. It is easy to show that the degree can be as low as 4. The least known
(as of 2008) 
bound on number of unknowns is 9 in the case when they range over non-negative
integers, and 11 in the case of arbitrary integer values (with very large degree).

The theorem was extended by several authors to numerous cases when the unknowns range over certain [http://en.wikipedia.org/wiki/Ring_(mathematics) rings] of [http://en.wikipedia.org/wiki/Algebraic_integers algebraic integers], for example, when the unknowns are [http://en.wikipedia.org/wiki/Gaussian_integers Gaussian integers], that is 
complex numbers of the form <math>a+b\sqrt{-1}</math> where are <math>a</math> and 
<math>b</math> are "ordinary" integers.

==Applications==

Martin Davis stated his conjecture as a (possible) tool to prove  undecidability of the tenth among [http://en.wikipedia.org/wiki/Hilbert's_problems Hilbert's problems]. In this problem [http://en.wikipedia.org/wiki/David_Hilbert David Hilbert] asked about an algorithm for deciding,
for a given  arbitrary Diophantine equation, whether it has solutions or not. Davis' conjecture implied the undecidability of [http://en.wikipedia.org/wiki/Hilbert's_tenth_problem Hilbert's tenth problem] thanks to the fundamental  fact of the existence of undecidable listable sets. Moreover, if <math>\mathfrak{M}</math> is such a set and 
:<math>a \in \mathfrak{M} \iff \exists  x_1\dots x_m
\{P(a,x_1,\dots,x_m)=0\}
</math>
is its Diophantine representation, then one gets the following strong form of the undecidability of Hilbert's tenth problem: ''there is no algorithm for deciding, for given value of the parameter <math>a\ ,</math> whether the Diophantine equation <math>P(a,x_1,\dots,x_m)=0</math> has a solution in <math>x_1,\dots,x_m.
</math>''

The theorem gives an improvement of [[Goedel incompleteness theorems|Gödel's incompleteness theorems]] by specifying that 
the unprovable statement can be the assertion that a particular Diophantine equation has no solution.

The theorem turned out to be a powerful tool for establishing the undecidability of numerous decision problems.

==Open problems==

* Is it true that every listable set has a Diophantine representation with a polynomial of degree 3?

* What is the least number of unknowns sufficient for defining all listable sets via Diophantine representations?

* Is it possible to improve the theorem to the case when the unknowns range over [http://en.wikipedia.org/wiki/Rational_numbers rational numbers]? 

* Is it possible to improve the theorem to the case when the unknowns range over integers from arbitrary fixed finite extension of the rational numbers?

* Is it true that every listable set has '''single-fold''' or, at least, '''finite-fold''' Diophantine representation, that is, such a representation that for every value of the parameter(s) there is a unique or, respectively, only finitely many choices for the values of the unknowns?

==References==

=== Papers of historical interest ===

The following four papers comprised the original proof of the theorem:

* Robinson J. (1952) Existential definability in arithmetic. Transactions of the American Mathematical Society, 72(3):437--449.

* Davis M. (1953) Arithmetical problems and recursively enumerable predicates. Journal of Symbolic Logic, 18(1):33-41.

*Davis M., Putnam H., and Robinson J. (1961) The decision problem for exponential Diophantine equations. Annals of Mathematics, Second Series, 74(3):425-436.

* Matiyasevich Yu. V. (1970) Enumerable sets are Diophantine (in Russian). Doklady Akademii Nauk SSSR, 191(2):279--282 English translation:  Soviet Mathematics.   Doklady, 11(2):354--358.

=== Popular Readings  ===

* Davis M., Hersh R. (1973) Hilbert's tenth problem.  Scientific American, 229:84-91.

* Matiyasevich Yu. (1999) Hilbert's tenth problem: a two-way bridge between number theory and computer science. People & ideas in theoretical computer science, 177--204,  Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, Singapore. 

* Matiyasevich, Yu. V. (2006) Hilbert's tenth problem: Diophantine equations in the twentieth century. Mathematical events of the twentieth century, 185--213, Springer, Berlin.

=== Books and surveys ===

* Davis M, Matijasevich Yu, and  Robinson J. (1976) Hilbert's tenth problem: Diophantine equations: positive aspects of a negative solution. Mathematical developments arising from Hilbert problems. Proc. Sympos. Pure Math., XXVIII:323-378 Amer. Math. Soc., Providence, R. I.

* Manin YuI (1977) A course in mathematical logic (translated from the Russian). Graduate Texts in Mathematics, Vol. 53. Springer-Verlag, New York-Berlin.

* Matiyasevich Yu. [http://logic.pdmi.ras.ru/~yumat/H10Pbook/index.html Hilbert's Tenth Problem].  Original Russian edition (1993) Nauka publisher; English translation (1993) MIT Press; French translation (1995) Masson editeur

* Matiyasevich Yu. (2008) Computation Paradigms in Light of Hilbert’s Tenth Problem. in New Computational Paradigms - Changing Conceptions of What is Computable, Cooper SB,  Loewe  B,  Sorbi  A., edts,  Springer Mathematics of Computing series, XIII:59-86.

* Shlapentokh A. (2007) Hilbert's Tenth Problem. Diophantine classes and extensions to global fields. New Mathematical Monographs, 7. Cambridge University Press, Cambridge.

===See also===

[http://logic.pdmi.ras.ru/Hilbert10/index.html Hilbert's tenth problem site]

[[Category:Mathematics]]
[[Category:Hilbert's problems]]
[[Category:Eponymous]]