In mathematics, a set S of j-tuples of integers is Diophantine precisely if there is some polynomial with integer coefficients f(n₁, ..., n_j, x₁, ..., x_k) such that a tuple (n₁, ..., n_j) of integers is in S if and only if there exist some integers x₁, ..., x_k with f(n₁, ..., n_j, x₁, ..., x_k) = 0. (Such a polynomial equation over the integers is also called a Diophantine equation.) In other words, a Diophantine set is a set of the form

$\backslash \{\backslash ,\; (n\_1,\backslash dots,n\_j)\; :\; \backslash exists\; x\_1\backslash ,\backslash dots\backslash ,\backslash exists\; x\_k\backslash ,\; f(n\_1,\backslash dots,n\_j,x\_1,\backslash dots,x\_k\; )=0\; \backslash ,\backslash \}$

where f is a polynomial function with integer coefficients.

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.

Matiyasevich's theorem effectively settled Hilbert's tenth problem.

Diophantine equations