Question

Given two polynomials $p_1$ and $p2$ each of which is a multi-variate polynomial with positive integer coefficients, we want to decide if $p_1 \leq p_2$ over all integral values of the variables.

The undecidability of Hilbert's tenth problem implies the undecidability of the above problem.

Now we throw in the additional restriction that each of $p_1$ and $p_2$ is homogeneous. Is there any decision procedure known for this restricted version?

Answer 1

It seems to me that for homogeneous polynomials it is decidable. First of all note that $p\le q$ is the same as $p-q\le 0$ and the condition of positivity of coefficients is extra. Let $f(x_1,...,x_n)$ be a polynomial. Then $f(x_1/y^2,...,x_n/y^2)=g(x_1,...,x_n,y)/y^m$ where $g$ is homogeneous and $m$ is even. Then $f\le 0$ is equivalent to $g\le 0$. So your problem (for homogeneous polynomial $g$) is equivalent to inequality $f\le 0$ for all rational values of variables $x_1,...,x_n$. But that is equivalent to $f\le 0$ for all (real) values of $x_1,...,x_n$. That is decidable by Tarski (the elementary theory of the reals is decidable).

Answer 2

I can prove that the following problem is undecidable: To determine, given two homogenous polynomials $p_1$ and $p_2$, whether or not the inequality $p_1\le p_2$ holds for all integer arguments.

Indeed, suppose there was an algorithm $A$ to determine whether $p_1\le p_2$ always holds. Then we can use this algorithm to determine whether any polynomial $f$ has an integer zero.

To see this, suppose $f=f(x_1,\ldots,,x_n)$ has total degree $d$. Let $$g(x_1,\ldots,,x_n,z)=z^d f(x_1/z,\ldots,x_n/z),$$ so $g$ is homogeneous of degree $d$.

I claim that $f$ has no integer zero if and only if the inequality $$2z^d\le g(x_1,\ldots,,x_n,z)^2+z^{2d} $$ holds for all integer arguments. Note that the left and right hand sides are homogeneous polynomials, so if the claim is true then we can we can use algorithm $A$ to decide whether or not $f$ has an integer zero.

To verify the claim, suppose first that $f$ has no integer zero. If $z=1$ then the inequality reduces to $2\le g(x_1,\ldots,,x_n,1)^2+1$, i.e., $1\le f(x_1,\ldots,,x_n)^2$. If $z$ is different than 1, then already $2z^d\le z^{2d}$, therefore $2z^d\le g(x_1,\ldots,,x_n,z)^2+z^{2d}$. So if $f$ has no integer zero then the inequality holds for all integer arguments.

Conversely, if the inequality holds for all integer arguments, then put $z=1$ to obtain $1\le f(x_1,\ldots,,x_n)^2$.

What about the case that the coefficients of the $p_i$ are assumed to be positive? It would be interesting if in this case the problem was decidable.

Answer 3

Hi Mark & SJR,

Thanks for your insightful responses.

I forgot to add an additional restriction: the variables can only take non-negative integral values. I don't know if this restriction helps.

Also in general, the degrees of the two polynomials can be different.

Thanks, Raghav