# Decision Procedure for Inequalities between Homogeneous Polynomials

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?

-
Isn't this equivalent to asking several instances of the original problem (for the dehomogenized versions of the inequality) over Q? I think this is open. –  Qiaochu Yuan Nov 29 '10 at 1:24
@Qiaochu: the solvability of polynomial equations in rationals is a big open problem. But here we have an inequality. The statement $f\le 0$ for all rationals is equivalent to the same statement for all reals and is decidable by Tarski (I wrote it in my answer below). –  Mark Sapir Nov 29 '10 at 1:52
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 –  user11202 Nov 30 '10 at 17:32

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

-
Shouldn't the conclusion be: the problem (for homogeneous polynomial $g$) is equivalent to the inequality $f \leq 0$ for all rational values of variables $x_1,\ldots,x_n$ with the same denominator?> –  alex Nov 29 '10 at 4:29
@alex: every two rational numbers have the same denominator: $3/5=6/10$. –  Mark Sapir Nov 29 '10 at 10:51
Just to be clear, this procedure only gives decidability in the case that $p$ and $q$ are homogeneous of the same degree. –  Noah Stein Nov 29 '10 at 17:44
@Noah: Yes, you are right. If $p$ and $q$ are homogeneous of different degrees, then the problem is undecidable in general as shown by SJR's answer below. I do not know which interpretation of the question is correct. –  Mark Sapir Nov 29 '10 at 18:51

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.

-