<p>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.</p>

CC BY-SA 3.0
2011-09-30T01:59:20.210Z
2011-09-30T01:59:20.210Z
Timothy Chow
<p>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.</p>

<p>Edit:
Assume that every Diophantine set is decidable (1). </p>

<p>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.</p>

CC BY-SA 3.0
2011-09-29T16:35:09.420Z
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.
Michaël Cadilhac
CC BY-SA 3.0
2011-09-29T16:40:29.950Z
@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.
Kaveh
CC BY-SA 3.0
2011-09-29T18:18:50.393Z
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.
Michaël Cadilhac
CC BY-SA 3.0
2011-09-29T19:38:18.370Z
@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.
Kaveh
CC BY-SA 3.0
2011-09-29T19:46:54.663Z
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).
Kaveh
CC BY-SA 3.0
2011-09-29T16:30:09.757Z
2011-09-29T17:18:29.167Z
2011-09-29T17:18:29.167Z
Kaveh
<p>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$ :)</p>

<p>For all the flack that Wolfram's NKS gets, he has a very interesting blurb in there about doing just this sort of thing. <a href="http://www.wolframscience.com/nksonline/page-1161a-text" rel="nofollow">NKS Hilbert 10th</a> He has a nice table showing how some simple statements have corresponding Diophantine compilation targets. <a href="http://www.wolframscience.com/nksonline/page-1160" rel="nofollow">Universal Diophantine Equation</a> For instance:</p>

<p>$A&lt;B \iff B == A+C+1$</p>

CC BY-SA 3.0
2011-09-30T13:47:47.337Z
I've thought the same thing.  Are there results that say which equations can be the encoding of which statements?
Jim Hefferon
CC BY-SA 3.0
2011-09-30T14:38:20.603Z
Lol. Downvotes for mentioning NKS.
Chad Brewbaker
CC BY-SA 3.0
2011-09-30T22:33:59.857Z
I do not think that you can blame downvoters after posting an answer which starts with “Regardless of the question….”
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-29T18:49:17.100Z
2011-09-30T14:52:53.180Z
2011-09-30T14:52:53.180Z
Chad Brewbaker
<p>In her paper <a href="http://arxiv.org/abs/1008.0809" rel="nofollow">Defining Integers</a>, 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 $\}$:</p>

<blockquote>
<b>Corollary 1.5.</b> There are undecidable Diophantine subsets of $\mathbb{Z}$
</blockquote>

<p>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.</p>

<p><b>Question:</b> Is Corollary 1.5 a direct consequence of the undecidability of HTP?</p>

<p><b>Question (rephrased):</b> Suppose every Diophantine set is decidable; does this imply that HTP is decidable?</p>

CC BY-SA 3.0
2011-09-29T21:51:43.480Z
What is HTB? (this comment isn't long enough so I am adding this to make it long enough)
Tyson Williams
CC BY-SA 3.0
2011-09-30T00:18:32.213Z
@TysonWilliams: Maybe Hilbert’s Tenth proBlem.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-30T12:53:22.570Z
Ahaha :-)  So I made this mistake a gazillion times without noticing.  Now I get the Kaveh's remark :-)  I'm fixing that.
Michaël Cadilhac
<computability>
Hilbert's Tenth Problem and nonrecursive Diophantine sets
Michaël Cadilhac
# Hilbert's Tenth Problem and nonrecursive Diophantine sets

(Asked by: username_0 on 2011-09-29)

In her paper [Defining Integers](http://arxiv.org/abs/1008.0809), 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?

**Tags:** computability

> **Comments:**
> **username_1**: What is HTB? (this comment isn't long enough so I am adding this to make it long enough)  
> **username_2**: @TysonWilliams: Maybe Hilbert’s Tenth proBlem.  
> **username_0**: Ahaha :-)  So I made this mistake a gazillion times without noticing.  Now I get the username_4's remark :-)  I'm fixing that.  

---

## 3 answers

### Answer by username_3 on 2011-09-30. Score: 9

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.


---

### Answer by username_4 on 2011-09-29. Score: 2

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.

> **Comments:**
> **username_0**: Sorry username_4, 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.  
> **username_4**: @username_0: 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.  
> **username_0**: Thanks for the edit, username_4.  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.  
> **username_4**: @username_0: 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.  
> **username_4**: 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).  

---

### Answer by username_5 on 2011-09-29. Score: 0

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](http://www.wolframscience.com/nksonline/page-1161a-text) He has a nice table showing how some simple statements have corresponding Diophantine compilation targets. [Universal Diophantine Equation](http://www.wolframscience.com/nksonline/page-1160) For instance:

$A

> **Comments:**
> **username_6**: I've thought the same thing.  Are there results that say which equations can be the encoding of which statements?  
> **username_5**: Lol. Downvotes for mentioning NKS.  
> **username_2**: I do not think that you can blame downvoters after posting an answer which starts with “Regardless of the question….”  

---

