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?
 A: 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). 
A: 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. 
