In her paper Defining Integers, Alexandra Shlapentokh presents the following as an immediate corollary of the undecidability of Hilbert's Tenth Problem --- that is, the language $\{p : p$ is a polynomial with integer coefficients with at least an integer root $\}$:

Corollary 1.5. There are undecidable Diophantine subsets of $\mathbb{Z}$

I'm not sure this is a consequence of the undecidability of HTP, so maybe I misread, and what the author is saying is that this is a consequence of the correspondence between recognizable sets and Diophantine sets.

Question: Is Corollary 1.5 a direct consequence of the undecidability of HTP?

Question (rephrased): Suppose every Diophantine set is decidable; does this imply that HTP is decidable?

  • $\begingroup$ What is HTB? (this comment isn't long enough so I am adding this to make it long enough) $\endgroup$ – Tyson Williams Sep 29 '11 at 21:51
  • 2
    $\begingroup$ @TysonWilliams: Maybe Hilbert’s Tenth proBlem. $\endgroup$ – Tsuyoshi Ito Sep 30 '11 at 0:18
  • $\begingroup$ Ahaha :-) So I made this mistake a gazillion times without noticing. Now I get the Kaveh's remark :-) I'm fixing that. $\endgroup$ – Michaël Cadilhac Sep 30 '11 at 12:53

Looking at the paper, I believe that what Shlapentokh is saying is that "there is an undecidable Diophantine subset of $\mathbb Z$" is an immediate consequence of "there is an r.e. set that is not recursive" and the MRDP theorem, where by the "MRDP theorem" is meant "A set is Diophantine if and only if it is r.e." Nothing deeper than that.


Take an arbitrary Diophantine equation over natural numbers. By Lagrange's sum of four squares theorem, any natural number is sum of squares of 4 integers. Replace each variable by sum of squares of four new variables. It is easy to see that there is a solutions to the original Diophantine equation over natural numbers iff there is solution for the modified equation over integers.

Edit: Assume that every Diophantine set is decidable (1).

We know that every r.e. set is Diophantine by MRDP. In particular the Hilbert's tenth problem is r.e., so it is expressible by a fixed Diophantine equation. Now by (1), we have that it is decidable. So Hilbert's tenth problem is decidable.

  • 1
    $\begingroup$ Sorry Kaveh, I probably wasn't clear enough: my problem is not about natural numbers vs. integers. Simply, I would like to see how the fact that all Diophantine sets are computable leads to HTP being decidable. I'll clarify that. $\endgroup$ – Michaël Cadilhac Sep 29 '11 at 16:35
  • $\begingroup$ @Michaël Cadilhac: Diophantine sets are all r.e., but that is not what is needed. What is needed is the reverse direction, i.e. all r.e. sets are Diophantine. Can you also state explicitly what you mean by HTB? I don't think it is a standard notation. $\endgroup$ – Kaveh Sep 29 '11 at 16:40
  • 1
    $\begingroup$ Thanks for the edit, Kaveh. Again, I'm not sure I got my question through: I'm wondering if one needs the fact that r.e. = Diophantine to conclude that [undecidability of HTB] implies Corollary 1.5. I'm guessing yes, but again, I'm unsure so I prefer to ask. $\endgroup$ – Michaël Cadilhac Sep 29 '11 at 18:18
  • $\begingroup$ @Michaël Cadilhac: that is not the question stated in the post. :) What do you mean by "one needs the fact that r.e. = Diophantine to conclude that [undecidability of HTB] implies Corollary 1.5."? Do you mean: "is there an argument that does not use MRDP?". The essential point here is that there is universal Diophantine equation, can you prove that there is one without using MRDP? Maybe, you can take a proof that say an NP-complete set is Diophantine and you can express paring. $\endgroup$ – Kaveh Sep 29 '11 at 19:38
  • $\begingroup$ There are such Diophantine equations, but the problem is that I don't if the proof of NP-completeness of that Diophantine equation uses MRDP (explicitly/implicitly). (ps: a problem complete for much weaker classes would also do, essentially what is needed is a universal computation verifier). $\endgroup$ – Kaveh Sep 29 '11 at 19:46

I always thought it would be cool to write a compiler who's target is Diophantine equations. Especially to see what kind of programs translate into equations of the form $x^n+y^n = z^n$ :)

For all the flack that Wolfram's NKS gets, he has a very interesting blurb in there about doing just this sort of thing. NKS Hilbert 10th He has a nice table showing how some simple statements have corresponding Diophantine compilation targets. Universal Diophantine Equation For instance:

$A<B \iff B == A+C+1$

  • $\begingroup$ I've thought the same thing. Are there results that say which equations can be the encoding of which statements? $\endgroup$ – Jim Hefferon Sep 30 '11 at 13:47
  • $\begingroup$ Lol. Downvotes for mentioning NKS. $\endgroup$ – Chad Brewbaker Sep 30 '11 at 14:38
  • 1
    $\begingroup$ I do not think that you can blame downvoters after posting an answer which starts with “Regardless of the question….” $\endgroup$ – Tsuyoshi Ito Sep 30 '11 at 22:33

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.