Which diophantine polynomials generate these diophantine sets?

Question

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.

Thanks!

Answer 1

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.