Diophantine set

From Wikipedia, the free encyclopedia

In mathematics, a Diophantine set of j-tuples of integers is a set S for which there is some polynomial with integer coefficients

f(n1, ..., nj, x1, ..., xk)

such that a tuple

(n1, ..., nj)

of integers is in S if and only if there exist some (non-negative) [1] integers

x1, ..., xk with
f(n1, ..., nj, x1, ..., xk) = 0.

Such a polynomial equation over the integers is called a Diophantine equation. In other words, a Diophantine set is a set of the form

\{\, (n_1,\dots,n_j) : \exists x_1\,\dots\,\exists x_k\, f(n_1,\dots,n_j,x_1,\dots,x_k )=0 \,\}

where f is a polynomial function with integer coefficients. [2]

Matiyasevich's theorem, published in 1970, states that a set of integers is Diophantine if and only if it is recursively enumerable. 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 theorem effectively settled Hilbert's tenth problem. It implies that Hilbert's tenth problem is unsolvable. This problem is the challenge to find a general algorithm which can decide whether a given system of Diophantine equations has a solution among the integers. David Hilbert posed the problem in his celebrated list, from his 1900 address to the International Congress of Mathematicians.

Contents

[edit] Examples

The well known Pell equation

x^2-d(y+1)^2=\pm 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

{0,2,3,5,6,7,8,10,...}

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 defines the set of numbers that are not powers of 2.
  • The equation a = (x + 2)(y + 2) defines the set of numbers that are not prime numbers.
  • The equation a + x = b defines the set of pairs (a\,,\,b) such that a\le b.\,

[edit] Matiyasevich's theorem

Matiyasevich's theorem says:

Every recursively enumerable set is Diophantine.

A set S of integers is recursively 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.

[edit] Proof technique

Yuri Matiyasevich utilized an ingenious trick 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 recursively enumerable set is Diophantine.

[edit] Application to Hilbert's Tenth problem

Main article: 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 a result discovered in the 1930s implies that a solution to Hilbert's tenth problem is impossible. The result discovered in the 1930s by several logicians can be stated by saying that some recursively enumerable sets are non-recursive. In this context, a set S of integers is called "recursive" if there is an algorithm that, when given as input an integer n, returns as output a correct 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.

[edit] Logical structure

Here an argument taking exactly the form of an Aristotelian syllogism is of interest:

(Major premise): Some recursively enumerable sets are non-recursive.
(Minor premise): All recursively enumerable sets are Diophantine.
(Conclusion): Therefore some Diophantine sets are non-recursive.

The conclusion entails that Hilbert's 10th problem cannot be solved. The most difficult part of the argument is the proof of the minor premise, i.e. Matiyasevich's theorem, which itself is much stronger than the unsolvability of the Tenth Problem.

[edit] Refinements

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).

[edit] 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 axiomatization of number theory, one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization.

[edit] Footnotes

  1. ^ The two definitions are equivalent. This can be proved using Lagrange's four-square theorem.
  2. ^ Note that one can also use a simultaneous system of Diophantine equations to define a Diophantine set, because the system
    f_1=0,\ldots,f_k=0
    is equivalent to the single equation
    f_1^2+\cdots+f_k^2=0.\,

[edit] References

  • Yuri Matiyasevich. "Enumerable sets are Diophantine." Doklady Akademii Nauk SSSR, 191, pp. 279-282, 1970. English translation in Soviet Mathematics. Doklady, vol. 11, no. 2, 1970.
  • 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-10: 0-262-13295-8