Diophantine set

A set S is said to be DiophantineMathworldPlanetmath if

  • it is a subset of n, the set of all n-tuples of positive integers, and

  • there is a polynomialPlanetmathPlanetmath p over in n+k variables, k0, such that xS iff there is some yk, such that p(x,y)=0.

So S can be thought of as a set such that, there is a Diophantine equation p=0 and a non-negative integer k, so that when each element in S is “combined” with some k-tuple, makes up a solution to a Diophantine equation p=0. In other words, if fnn+k:n+kn is a projection function given by fnn+k(x,y)=x where xn and yk, then S is a Diophantine setMathworldPlanetmath iff S=fnn+k(Z), where Z is the zero set of some Diophantine equation p=0. Equivalently, a set Sn is Diophantine if there is a p[X1,,Xn+k], such that


For example, itself is Diophantine, for the polynomial p(x,y)=x-y works. Another trivial example: the set of all positive integers divisible by 3 is Diophantine, for the polynomial p(x,y)=x-3y works.

For a less trivial example, let us show that the set of all triples (a,b,c) such that abc is Diophantine. For the inequality ab, let p(x1,x2,y)=x2-x1-(y-1). Then the sentenceMathworldPlanetmath yp(x1,x2,y)=0 is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to x1x2. Similarly, for the inequality bc, we have the same polynomial p. Putting the two inequality together amounts to setting q(x1,x2,x3,y1,y2)=p(x1,x2,y1)2+p(x2,x3,y2)2. Thus, the sentence (y1,y2)q(x,y)=0, where x=(x1,x2,x3) and y=(y1,y2) is the same as the inequality x1x2x3.

Some other Diophantine sets are:

  • the set A=BC, where B and C are Diophantine

  • the set A=BC, where B and C are Diophantine

  • the set {aab(modn)}

  • the set of composite numbersMathworldPlanetmath

  • the set of prime numbersMathworldPlanetmath

  • the set of powers of a positive integer {mnn=0,1,}

Remark. Associated with the concept of a Diophantine set is that of a Diophantine function: a functionMathworldPlanetmath f is said to be Diophantine if its graph {(x,f(x))xdom(f)} is a Diophantine set. Some well-know Diophantine functions are the exponential functionsDlmfDlmfMathworld f(x)=nx and the factorial function f(x)=x!, where n,x are positive integers.

It turns out that a function is Diophantine iff it is recursive. From this, it is possible to prove that Hilbert’s 10th problem is unsolvable.

The idea behind using Diophantine sets to prove the unsolvability of Hilbert’s 10th problem comes from Yuri Matiyaseviĉ, and hence the theorem is known as Matiyaseviĉ’s theorem.


  • 1 M Davis, Computability and Unsolvability. Dover Publications, Inc. New York, 1982
Title Diophantine set
Canonical name DiophantineSet
Date of creation 2013-03-22 18:02:50
Last modified on 2013-03-22 18:02:50
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 13
Author CWoo (3771)
Entry type Definition
Classification msc 03D99
Classification msc 03D80
Defines Diophantine function