# Is decidability reducible to unique decidability (perhaps in multilinear polynomial situations)?

Given a Diophantine equation it is not decidable if it has integer solution.

I. Is there a Diophantine set $$\mathcal D_{unique}$$ satisfying the properties

1. every member in $$\mathcal D_{unique}$$ is a polynomial

2. every member in $$\mathcal D_{unique}$$ has one integral point or less

3. every polynomial $$f$$ is reducible in finite time to a polynomial in $$\mathcal D_{unique}$$ satisfying the property $$f$$ has no integral solution iff the mapped polynomial has no integral solution?

II. Is there an universal set $$\mathcal D_{unique}^{univeral}$$ which models $$\mathcal D_{unique}$$?

Essentially given a diophantine equation, can we produce another with at most one integer solution, and which has an integer solution if and only if the first one does?

Assume $$f$$ is taken in $$\mathbb Z[x_1,\dots,x_t]$$ and has terms only of form $$b\prod_{i=1}^tx_i^{a_i}$$ where $$a_i\in\{0,1\}$$ and $$b\in\mathbb Z$$.

III. Perhaps in the above scenario an unique integral solution polynomial reducible situation is feasible.

• I think one can use the following reduction algorithm: For $f$ a polynomial in $(x_1,\dots, x_n)$, pick some computable ordering of tuples in $\mathbb Z^n$ with finitely many before a given tuple (e.g. order first by $\max |x_i|$ and then lexicograpically) and then encode "$f(x_1,\dots,x_n)=0$ and $f(y_1,\dots,y_n) \neq 0$ for all $(y_1,\dots, y_n)<(x_1,\dots, x_n)$ in this ordering" using MRDP. But maybe MRDP doesn't preserve unique solubility. – Will Sawin Apr 19 at 0:45
• "Diophantine set" usually refers to subsets of $\mathbb Z^n$, not sets of polynomials. Could you clarify what yiu mean? – Wojowu Apr 19 at 0:47
• Why do you need the set at all? You seem to be asking: given a diophantine equation, can we produce another with at most one integer solution, and which has an integer solution if and only if the first one does? – Joel David Hamkins Apr 19 at 8:10
• Yes, my proposal was that you could ask the question in a more straightforward manner. – Joel David Hamkins Apr 19 at 9:28
• I think this was answered by Martin Davis in 1972, "On the Number of Solutions of Diophantine Equations", semanticscholar.org/paper/… – Matt F. Apr 19 at 9:45

[Update: This may not work, as per the comments by Joel David Hamkins and Wojowu]

Can we produce another equation with at most one integer solution, and which has an integer solution if and only if the first one does?

Let's take the equation $$xyz=x^2+y^2-z^2+2$$ as an example, as suggested here. Then we want the new equation to say $$xyz=x^2+y^2-z^2+2 \wedge \forall uvw\ (u,v,w)<(x,y,z) \to uvw \neq u^2 + v^2 - w^2 + 2$$ for some appropriate ordering $$<$$. We can use the ordering that $$(u,v,w)<(x,y,z)$$ iff in the lexicographic ordering $$(u^2+v^2+w^2,u,v,w)<(x^2+y^2+z^2,x,y,z).$$
• I think the runtime is short. As a guess, if the first equation has $n$ variables and degree $d$, the new equation has at most $10n$ variables and degree $10d^2$. – Matt F. Apr 19 at 10:17
• I don't think that works. The polynomials which are produced by the method explained by Davis have a lot of auxiliary variables, not just the same variables $(x,y,z)$. See for instance Lemma 5.1 already, which throws in a new variable $u$ which can be arbitrarily high. Heck, there is a lot of new variables throw in even when writing down $z\leq y$, since it asserts that $y-z$ is a sum of four squares. – Wojowu Apr 19 at 10:32