Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to show that the following sets are Diophantine:

  1. $\{(x,y)\mid x \leq y\}$
  2. $\{(x,y)\mid x < y\}$
  3. $\{(x,y)\mid x\text{ divides }y\}$
  4. $\{(x,y,z)\mid x\equiv y \pmod z\}$
  5. $\{(x,y,z)\mid x = \gcd(y,z)\}$

So, the definition I am using is that a Set $S$ is diophantine if i) it is a subset of $n$ , the set of all $n$-tuples of positive integers, and ii) there is a polynomial $p$ over in $n+k$ variables, $k0$ , such that $x$ is an element of the set $S$ iff there is some y an element of Naturals^k , such that $p(x,y)=0$

So, my answer is that set 1 isn't diophantine since it is not a subset of n, since if we let $y = -2$ for example.

For set 2), it also isn't diophantine by the same reason as in #1

For set 3), it is since we let $k*x = y$, where $k$ is a positive number, but how to take care of the polynomial $p$ over $n+k$ variables?

For set 4, condition 1 is met, but I need some justification

and for set 5, it is also diophantine by the same reason as set 4.


share|cite|improve this question
If you are going to post here regularly, may I suggest you learn a bit about how to format mathematics on this site (see the faq). For example, if I put dollar signs on either side of \{{(x,y)|x\le y\}}, I get $\{{(x,y)|x\le y\}}$. – Gerry Myerson Feb 14 '13 at 23:21
Also, is that supposed to be $k_0$? – Sniper Clown Feb 14 '13 at 23:22
I am surprised at the choice of positive integers. Almost universally in the field, variables range over the non-negative integers. Are you sure? Still doable, but things become more complicated. – André Nicolas Feb 14 '13 at 23:23
@Asaf, why have you discorrected my edits of the spelling of diophantine? – Gerry Myerson Feb 14 '13 at 23:29
@Asaf, you don't know what you're missing. My "Applications of higher cohomology to Latvian folkmusic of the 13th century" is a classic. – Gerry Myerson Feb 15 '13 at 2:26
up vote 3 down vote accepted

As is traditional in the field, we let variables range over the non-negative integers. The definitions should not be hard to modify if we are restricted to quantification over the positive integers. Note that the answers use polynomial equations $P=0$, where some of the coefficients of $P$ may be negative. If we want to avoid negative coefficients, we can, by bringing all the negative stuff to one side, use $P^+=P^-$.

$1.$ For $x\le y$, use the formula $\exists u(x+u-y=0$. If you really insist on quantifying over positive integers only, say that $x=y$ or there exists a $u$ such that $x+u-y=0$. This can be expressed as $\exists u((x-y)(x+u-y)=0)$.

From here on we don't type the existential quantifiers.

$2.$ For $x\lt y$ use $x+1+u-y=0$. Here if we want $u$ to range over the positive integers, we can use the simpler $x+u-y=0$.

$3.$ For $x$ divides $y$, use $ux=y$.

$4.$ For congruence, there is the annoyance that $x-y$ may be positive, negative, or $0$. We can say that there exists $u$ such that $uz=x-y$ or $uz=y-x$. This can be written as there exists a $u$ such that $(uz-x+y)(uz+x-y)=0$.

$5.$ For gcd, say that $x$ divides $y$ and $x$ divides $z$ (we already know how to do these) and $x$ can be written as a linear combination of $y$ and $z$ (Bezout's Theorem).

To say linear combination, we can't quite say that there are $s$ and $t$ such that $sy+tz=x$, because almost always one of $s$ or $t$ will be negative. But we can sneak around that by saying there exist $s$ and $t$ such that $(sy-tz-x)(sy-tz-x)=0$.

Note that we have three conditions whose conjunction we want to assert. Use the fact that the polynomials $P$, $Q$, and $R$ are all $0$ at a certain place iff $P^2+Q^2+R^2=0$ at that place.

Remark: Your $x$, $y$ and so on implicitly range over the non-negative integers or the positive integers, according to local definition. So your choice of $y=-2$ is not allowed. It turns out that all recursively enumerable sunsets of $\mathbb{N}^n$ are Diophantine, so in particular all of the sets in your list will be. But what is asked for is an explicit construction for each.

Added: For the $\gcd$ predicate, putting the pieces together, a formula that one can use is $$\exists u\exists v\exists s\exists t\left((ux-y)^2 +(vx-z)^2 +((sy-tz-x)(sy-tz-x))^2=0\right).$$ Note again the use of product to say "or" and of sum of squares to say "and."

share|cite|improve this answer
@AndréNicolasI dont know what Bezout's theorem is. That was not in my book. Can you please help explain the problem and provide an explicit construction? – mary Feb 17 '13 at 7:57
The theorem is not always given a name. It says that if $\gcd(a,b)=d$ then there exist integers $x$ and $y$ such that $ax+b y=d$. The most frequently used case says that if the $\gcd$ is $1$, there exist integers $x$ and $y$ such that $ax+by=1$. I thought I wrote out instructions for explicit construction. Will add a line at end. For more detail about Bezout's Theorem, see any beginning number theory book, or Wikipedia. – André Nicolas Feb 17 '13 at 15:32
Still confused at how the work you did related to Diophatine characteristic. This is more of a computability question, can you please explain it along those lines? Thanks – mary Feb 18 '13 at 12:15
I do not understand your question. Assume it is about the gcd problem. I gave an explicit existential (Diophantine) definition of your gcd predicate. It is not a computability question, it is a question of representability in a certain form. Of course all computable predicates are so representable, by the result of M., but they want an explicit formula. The reason the expression works is because the gcd can be represented as a linear combination, and nothing smaller can be. – André Nicolas Feb 18 '13 at 12:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.