# Undecidability of Diophantine equations with disjoint variables?

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.]

• The Pell equation is not difficult to solve. It is necessary to decompose the coefficient in the continued fraction. Many equations can be solved. – individ May 30 '17 at 16:56
• 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. – 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)$.

• Thanks. I am not clear about the part "get F from F'". For instance, from -2x^3y, what do you obtain? – Liam_math May 30 '17 at 20:51
• 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? – Liam_math May 30 '17 at 20:58
• @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. – joro May 31 '17 at 13:28
• 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. – Liam_math May 31 '17 at 14:03
• @Liam_math for $-2x+4$ the reduction is $(v+2)^2+(vx+4)^2=0$ which forces $v= -2$. – joro May 31 '17 at 14:40