5
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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
    Commented May 30, 2017 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
    Commented Jun 1, 2017 at 0:49

1 Answer 1

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • $\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
    Commented May 30, 2017 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
    Commented May 30, 2017 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
    Commented May 31, 2017 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
    Commented May 31, 2017 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
    Commented May 31, 2017 at 14:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .