Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

2 Answers

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

share|improve this answer
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
add comment

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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