7
$\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$
8
  • 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, 2021 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, 2021 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$ Apr 19, 2021 at 8:10
  • 2
    $\begingroup$ Yes, my proposal was that you could ask the question in a more straightforward manner. $\endgroup$ Apr 19, 2021 at 9:28
  • $\begingroup$ I'm curious about your personal opinion, how is this problem at all related to P vs NP vs PSPACE "puzzle"? Also what's up with the f-1 tag? $\endgroup$
    – Wojowu
    Apr 19, 2021 at 11:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.