Consider a special case of the Hilbert's 10th problem:

$f(\vec{x})=g(\vec{y})$, where $\vec{x}$ and $\vec{y}$ are disjoint ( i.e, the LHS and RHS do not have any common variables), moreover, $f$ and $g$ are polynomials with positive coefficients.

The question is, with the restrictions, whether the undecidability still holds?

For example, the Pell equation $x^2=3y^2+1$ falls into this class and is difficult to solve. I am wondering whether we can obtain undecidability outright.

[Important note: the Hilbert 10th question has two versions, ie., whether there is a solution in natural numbers, or in integers. In general, they are equivalent, but in this particular case, they are not. The answer below shows that checking whether there is a solution in integers is undecidable, but it is still open for the case that the solution must be natural numbers.]

  • $\begingroup$ The Pell equation is not difficult to solve. It is necessary to decompose the coefficient in the continued fraction. Many equations can be solved. $\endgroup$ – individ May 30 '17 at 16:56
  • $\begingroup$ This problem is at least NP-hard, because the set $\{(a,b,c)\in \mathbb{N}^3|\exists x,y\in \mathbb{N}: ax^2+by=c\}$ is NP-complete. $\endgroup$ – Erfan Khaniki Jun 1 '17 at 0:49

It is undecidable.

The only integral point on $x^3+x=y^2$ is $(0,0)$.

Let $F(\vec{y})=0$ be undecidable diophantine equation with positive coefficients and not depending on $x$.

Take $f(x)=x^3+x$ and $g(\vec{y})=F^2$ leading to $x^3+x=F^2(\vec{y})$.

To get $F$ from $F'$ with negative coefficients use sum of squares replacing each negative coefficient $c_i$ with variable $v_i$ and add the square $(v_i + c_i)^2$.

Even simpler, the integral solutions of $x^2=1+d^2 y^2$ are $(\pm 1,0)$.

| cite | improve this answer | |
  • $\begingroup$ Thanks. I am not clear about the part "get F from F'". For instance, from -2x^3y, what do you obtain? $\endgroup$ – Liam_math May 30 '17 at 20:51
  • $\begingroup$ Moreover, this answer is nice, but what I meant to ask is whether $f(\vec{x})=g(\vec{y})$ has a solution in natural numbers (my apology!) In this case, is the problem still undecidable? $\endgroup$ – Liam_math May 30 '17 at 20:58
  • $\begingroup$ @Liam_math from $-2x^3y$ I get $(v_1+2)^2+(v_1x^3 y)^2$. For naturals probably every variable should be replaced by sum of 4 squares. $\endgroup$ – joro May 31 '17 at 13:28
  • $\begingroup$ For the requirement that each variable is in natural numbers, the reduction probably does not work, because $f(\vec{x})=0$ cannot have a solution in natural numbers if all coefficients of $f$ are positive. Again, please correct me. $\endgroup$ – Liam_math May 31 '17 at 14:03
  • $\begingroup$ @Liam_math for $-2x+4$ the reduction is $(v+2)^2+(vx+4)^2=0$ which forces $v= -2$. $\endgroup$ – joro May 31 '17 at 14: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.