A diophantine polynomial is a (multivariable) polynomial with integer coefficients. If we write this polynomial as $p(x, y_1, \dots, y_n)$, then it defines the diophantine set $D_p = \{ x \in \mathbb{N} \, | \, \exists y_1, \dots, y_n \in \mathbb{Z} \text{ such that } p(x, y_1, \dots, y_n) = 0 \}$. Is it possible to mathematically characterize the polynomials $p$ for which $\mathbb{N} \setminus D_p$ is also generated by some diophantine polynomial $q$? If so, to what extent is it possible to express $q$ in terms of $p$?

My motivation for this question is Matiyasevich's Theorem, which says that the Turing-recognizable sets are precisely the diophantine sets. I wonder if anything similar can be said about the Turing-decidable sets.


It is well-known that the Diophantine sets are precisely the r.e. sets. We show that in general we cannot construct a $q$ given $p$.

Suppose that we could. Let $A$ be an r.e. set which is not recursive. From $A$, we can construct a polynomial $p(x,y_1,\dots,y_n)$ that represents $A$.

Suppose that we could construct a $q$ as described in the post. Then we could, given $x$, set one computer to search systematically for a solution $(y_1,\dots,y_n)$ of $p(x,y_1,\dots,y_n)=0$. Simultaneously, another computer can search for a solution of $q(x,z_1,\dots, z_m)=0$.

This combination algorithm always terminates, contradicting the fact that $A$ is not recursive.


A $q$ exists if and only if $p$ (and therefore $q$) defines a recursive set.

There is no terminating algorithm to generate $q$ from $p$ whenever possible, and stop otherwise. That would be a way to algorithmically test recursiveness of the solution set of a Diophantine equation, which is the same as automated recursiveness testing of the language accepted by a Turing machine.

It is conceivable that if recursiveness is proved in a constructive formal system (one where existence proofs have extractible algorithms for producing witnesses), you get a construction of $q$ from a construction of $p$, but I am not certain of this and it might depend on how recursiveness is defined.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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