Diophantine set

Diophantine set

In mathematics, a Diophantine equation is an equation of the form P(x1, ..., xj, y1, ..., yk)=0 (usually abbreviated P(x,y)=0 ) where P(x,y) is a polynomial with integer coefficients. A Diophantine set is a subset S of Nj [1] so that for some Diophantine equation P(x,y)=0.

\bar{n} \in S \iff (\exists \bar{m} \in \mathbb{N}^{k})(P(\bar{n},\bar{m})=0)

That is, a parameter value is in the Diophantine set S if and only if the associated Diophantine equation is satisfiable under that parameter value. Note that the use of natural numbers both in S and the existential quantification merely reflects the usual applications in computability and model theory. We can equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers.[2] Also it is sufficient to assume P is a polynomial over \mathbb{Q} and multiply P by the appropriate denominators to yield integer coefficients. However, whether quantification over rationals can also be substituted for quantification over the integers it is a notoriously hard open problem.

The MRDP theorem states that a set of integers is Diophantine if and only if it is computably enumerable. [3] A set S is recursively enumerable precisely if there is an algorithm that, when given an integer, eventually halts if that input is a member of S and otherwise runs forever. This means that the concept of general Diophantine set, apparently belonging to number theory, can be taken rather in logical or recursion-theoretic terms. This is far from obvious, however, and represented the culmination of some decades of work.

Matiyasevich's completion of the MRDP theorem settled Hilbert's tenth problem. Hilbert's tenth problem[4] was to find a general algorithm which can decide whether a given Diophantine equation has a solution among the integers. While Hilbert's tenth problem is not a formal mathematical statement as such the nearly universal acceptance of the (philosophical) identification of a decision algorithm with a total computable predicate allows us to use the MRDP theorem to conclude the tenth problem is unsolvable.



The well known Pell equation

x2d(y + 1)2 = 1

is an example of a Diophantine equation with a parameter. As has long been known, the equation has a solution in the unknowns x,y precisely when the parameter d is 0 or not a perfect square. In the present context, one says that this equation provides a Diophantine definition of the set


consisting of 0 and the natural numbers that are not perfect squares. Other examples of Diophantine definitions are as follows:

  • The equation a = (2x + 3)y only has solutions in \mathbb{N} when a is not a power of 2.
  • The equation a = (x + 2)(y + 2) only has solutions in \mathbb{N} when a is greater than 1 and is not a prime number.
  • The equation a + x = b defines the set of pairs (a\,,\,b) such that a\le b.\,

Matiyasevich's theorem

Matiyasevich's theorem says:

Every computably enumerable set is Diophantine.

A set S of integers is computably enumerable if there is an algorithm that behaves as follows: When given as input an integer n, if n is a member of S, then the algorithm eventually halts; otherwise it runs forever. That is equivalent to saying there is an algorithm that runs forever and lists the members of S. A set S is Diophantine precisely if there is some polynomial with integer coefficients f(n, x1, ..., xk) such that an integer n is in S if and only if there exist some integers x1, ..., xk such that f(n, x1, ..., xk) = 0.

It is not hard to see that every Diophantine set is recursively enumerable: consider a Diophantine equation f(n, x1, ..., xk) = 0. Now we make an algorithm which simply tries all possible values for n, x1, ..., xk, in the increasing order of the sum of their absolute values, and prints n every time f(n, x1, ..., xk) = 0. This algorithm will obviously run forever and will list exactly the n for which f(n, x1, ..., xk) = 0 has a solution in x1, ..., xk.

Proof technique

Yuri Matiyasevich utilized a method involving Fibonacci numbers in order to show that solutions to Diophantine equations may grow exponentially. Earlier work by Julia Robinson, Martin Davis and Hilary Putnam had shown that this suffices to show that every computably enumerable set is Diophantine.

Application to Hilbert's Tenth problem

Hilbert's tenth problem asks for a general algorithm deciding the solvability of Diophantine equations. The conjunction of Matiyasevich's theorem with earlier results known collectively as the MRDP theorem implies that a solution to Hilbert's tenth problem is impossible. The work of the Robinson, Davis and Putnam had proved in the 1960s that there are computably enumerable sets that are non-computable [citation?]. In this context, a set S of integers is called "computable" if there is an algorithm that, when given as input an integer n, returns for every n either a yes-or-no answer to the question of whether n is a member of S. It follows that there are Diophantine equations which cannot be solved by any algorithm.


Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the equation only has 9 natural number variables (Matiyasevich, 1977) or 11 integer variables (Zhi Wei Sun, 1992).

Further applications

Matiyasevich's theorem has since been used to prove that many problems from calculus and differential equations are unsolvable.

One can also derive the following stronger form of Gödel's first incompleteness theorem from Matiyasevich's result:

Corresponding to any given consistent axiomatization of number theory,[5] one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization.


  1. ^ Planet Math Definition
  2. ^ The two definitions are equivalent. This can be proved using Lagrange's four-square theorem.
  3. ^ The final piece of this result was published in 1970 by Matiyasevich and is thus also known as Matiyasevich's theorem but pedantically speaking Matiyasevich's theorem refers to the representability of exponentiation in Diophantine sets and the mathematical community has moved to calling the equivalence result the MRDP theorem or the Davis-Putnam-Robinson-Matiyasevich theorem after the mathematicians providing key pieces of the theorem.
  4. ^ David Hilbert posed the problem in his celebrated list, from his 1900 address to the International Congress of Mathematicians.
  5. ^ More precisely, given a \Sigma^0_1-formula representing the set of Gödel numbers of sentences which recursively axiomatize a consistent theory extending Robinson arithmetic.


  • Matiyasevich, Yuri (1970). "Диофантовость перечислимых множеств [Enumerable sets are Diophantine]" (in Russian). Doklady Akademii Nauk SSSR 191: 279–282.  English translation in Soviet Mathematics 11 (2), pp. 354–357.
  • M. Davis. "Hilbert's Tenth Problem is Unsolvable." American Mathematical Monthly 80, pp. 233-269, 1973.
  • Yuri Matiyasevich. Hilbert's 10th Problem Foreword by Martin Davis and Hilary Putnam, The MIT Press. ISBN 0-262-13295-8
  • Zhi-Wei Sun, Reduction of unknowns in Diophantine representations, Sci. China Ser. A, 35:3 (1992), pp. 257–269.

External links

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Diophantine — means pertaining to the ancient Greek mathematician Diophantus. A number of concepts bear this name: Diophantine approximation Diophantine equation Diophantine set This disambiguation page lists articles associated with the same title. If an …   Wikipedia

  • Diophantine geometry — In mathematics, diophantine geometry is one approach to the theory of Diophantine equations, formulating questions about such equations in terms of algebraic geometry over a ground field K that is not algebraically closed, such as the field of… …   Wikipedia

  • Recursively enumerable set — In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing recognizable if: There is an algorithm such that the set of… …   Wikipedia

  • Glossary of arithmetic and Diophantine geometry — This is a glossary of arithmetic and Diophantine geometry in mathematics, areas growing out of the traditional study of Diophantine equations to encompass large parts of number theory and algebraic geometry. Much of the theory is in the form of… …   Wikipedia

  • Erdős-Diophantine graph — In Diophantine geometry, an Erdős Diophantine graph, named after Paul Erdős and Diophantus of Alexandria, is a complete graph with vertices located on the integer square grid scriptstylemathbb{Z}^2 such that all mutual distances between the… …   Wikipedia

  • Harmonious set — In mathematics, a harmonious set is a subset of a locally compact abelian group on which every weak character may be uniformly approximated by strong characters. Equivalently, a suitably defined dual set is relatively dense in the Pontryagin dual …   Wikipedia

  • IP set — In mathematics, an IP set is a set of natural numbers which contains all finite sums of some infinite set.The finite sums of a set D of natural numbers are all those numbers that can be obtained by adding up the elements of some finite nonempty… …   Wikipedia

  • Dense set — In topology and related areas of mathematics, a subset A of a topological space X is called dense (in X) if any point x in X belongs to A or is a limit point of A.[1] Informally, for every point in X, the point is either in A or arbitrarily close …   Wikipedia

  • Hilbert's tenth problem — is the tenth on the list of Hilbert s problems of 1900. Its statement is as follows:Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it… …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.