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

Via Matiyasevich's Theorem, it is easy to prove that the following sets are diophantine:

  1. $\{k\}$
  2. $\{0, 1, \dots, k-1, k+1, k+2, \dots \}$
  3. $\{0, 1, \dots, k\}$
  4. $\{k+1, k+2, \dots\}$

Number 1 is generated by the diophantine polynomial $f(x) = x - k$. Number 3 is generated by the diophantine polynomial $f(x) = (x)(x - 1)\dots(x - k)$.

What is the simplest diophantine polynomial that generates sets 2 and 4? Also, is there a simpler diophantine polynomial that generates set 3?

The word "simplest" is completely subjective, but obviously a short, low-degree polynomial with relatively few variables is ideal.


share|cite|improve this question
up vote 2 down vote accepted

To express a quantity $Q$ being greater than $0$, use $Q = a$ for Diophantine equations in positive integers, $Q=1+a$ for equations in non-negative integers, and $Q= 1 + a^2 + b^2 + c^2 + d^2$ for equations in integers, where $a,(b,c,d)$ are additional variables.

To say that $Q$ is nonzero, express that $Q^2$ is positive. Now,

(2) says that $(x-k)$ is nonzero and $x+1$ is positive.

(4) says that $(x-k)$ is positive.

(3) can be restated as saying that $x-1$ and $k + 1 - x$ are both positive. For large $k$ this is shorter than $f(x)$, but uses more variables.

share|cite|improve this answer
Thank you for spending your free time running around and answering all my questions about Diophantine programming. You're great. – GMB Sep 20 '13 at 1:01
Thanks for the questions. The Diophantine encodings are a nice pleasant bag of tricks that one does not get a chance to work out very often, so the unanswered questions are an occasion to meet old friends. – zyx Sep 20 '13 at 1:14

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.