Diophantine set

related topics
{math, number, function}
{theory, work, human}

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

such that a tuple

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

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

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

Examples

The well known Pell equation

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 defines the set of numbers that are not powers of 2.

Full article ▸

related documents
Well-order
Kolmogorov space
Goodstein's theorem
Carmichael number
Laurent series
Cartesian product
Group representation
Local ring
Lebesgue measure
Convex set
Axiom of regularity
Conjunctive normal form
Controllability
Euler's totient function
Generalized Riemann hypothesis
Kruskal's algorithm
Monotonic function
Algebraic topology
Diffeomorphism
Isomorphism theorem
Tree (data structure)
Symmetric group
Differential topology
Knight's tour
Mersenne twister
Golomb coding
Analytic geometry
Discriminant
Automated theorem proving
Search algorithm