4
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$ – Will Sawin Apr 19 at 0:45
  • $\begingroup$ "Diophantine set" usually refers to subsets of $\mathbb Z^n$, not sets of polynomials. Could you clarify what yiu mean? $\endgroup$ – Wojowu Apr 19 at 0:47
  • 2
    $\begingroup$ 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? $\endgroup$ – Joel David Hamkins Apr 19 at 8:10
  • 2
    $\begingroup$ Yes, my proposal was that you could ask the question in a more straightforward manner. $\endgroup$ – Joel David Hamkins Apr 19 at 9:28
  • 1
    $\begingroup$ I think this was answered by Martin Davis in 1972, "On the Number of Solutions of Diophantine Equations", semanticscholar.org/paper/… $\endgroup$ – Matt F. Apr 19 at 9:45
0
$\begingroup$

[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?

The answer is yes.

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).$$

Now we can write the new equation in a Diophantine way using the standard techniques for Diophantine equivalents of bounded quantifiers, as in section 5 of Martin Davis's well-known paper "Hilbert's 10th Problem is Unsolvable".

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ – Matt F. Apr 19 at 10:17
  • $\begingroup$ I am confused by this answer, since "the standard techniques" for representing bounded quantification introduces new variables (to code the sequence of prior values etc.), and I worry that we might not have unique solutions after doing this. $\endgroup$ – Joel David Hamkins Apr 19 at 10:30
  • $\begingroup$ 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. $\endgroup$ – Wojowu Apr 19 at 10:32
  • $\begingroup$ That's fair on the uniqueness of the new variables. I'm not sure if this can be saved, but I'll leave this it up in the hopes that it's instructive for others. $\endgroup$ – Matt F. Apr 19 at 10:40

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.