Matiyasevich theorem
| Yuri Vladimirovich Matiyasevich (2008), Scholarpedia, 3(7):7095. | doi:10.4249/scholarpedia.7095 | revision #127038 [link to/cite this article] |
Matiyasevich's theorem (also known as the DPRM-theorem or the MRDP-theorem) implies that the notion of effectively enumerable set from computability theory coincides with the notion of Diophantine set from number theory.
Contents |
Definitions and results
A set \(\mathfrak{M}\) of non-negative integers is called Diophantine provided that there exists a polynomial \(P(a,x_1,\dots,x_m)\) with integer coefficients such that the one-parameter Diophantine equation \[P(a,x_1,\dots,x_m)=0\] has a solution in the unknowns \(x_1,\dots,x_m\) if and only if the value of the parameter \(a\) belongs to the set \(\mathfrak{M}.\) Range of unknowns The equivalence \[a \in \mathfrak{M} \iff \exists x_1\dots x_m \{P(a,x_1,\dots,x_m)=0\} \] is called a Diophantine representation of the set \(\mathfrak{M}.\) Examples of Diophantine sets
A set \(\mathfrak{M}\) 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 \(\mathfrak{M}\) in some order and only those. 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.
History
The equations, and afterwards sets and representations are named after the Greek mathematician Diophantus.
The existence of Diophantine representations for all listable sets was first conjectured by 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 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 Martin Davis, Hilary Putnam, and 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 Yuri Matiyasevich in 1970, consisted in fulfilling this condition of Julia Robinson by providing a Diophantine representation of the set of ordered pairs \( (u,v) \) such that \( v=F_{2u}\) where \(F_n\) is the \(n\)th 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 \[P(a,x_1,\dots,x_m)=0\] 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 \[ a \in \mathfrak{M} \iff \exists x_1\dots x_n \{Q(x_1,\dots,x_n)=a\} \] 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, ..., \(n\)-tuples of non-negative integers, and the theorem easily extends to these cases: every listable set of \(n\)-tuples of non-negative integers has a representation of the form \[ \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\} \] with some polynomial \(P(a_1,\dots,a_n,x_1,\dots,x_m)\) 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 rings of algebraic integers, for example, when the unknowns are Gaussian integers, that is complex numbers of the form \(a+b\sqrt{-1}\) where are \(a\) and \(b\) are "ordinary" integers.
Applications
Martin Davis stated his conjecture as a (possible) tool to prove undecidability of the tenth among Hilbert's problems. In this problem 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 Hilbert's tenth problem thanks to the fundamental fact of the existence of undecidable listable sets. Moreover, if \(\mathfrak{M}\) is such a set and \[a \in \mathfrak{M} \iff \exists x_1\dots x_m \{P(a,x_1,\dots,x_m)=0\} \] 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 \(a\ ,\) whether the Diophantine equation \(P(a,x_1,\dots,x_m)=0\) has a solution in \(x_1,\dots,x_m. \)
The theorem gives an improvement of 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 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. 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.
