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
    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
    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
    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
    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
    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
    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
    May 31, 2017 at 14:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.