3
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 29, 2010 at 1:24
  • 1
    $\begingroup$ @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). $\endgroup$
    – user6976
    Nov 29, 2010 at 1:52
  • $\begingroup$ 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 $\endgroup$
    – user11202
    Nov 30, 2010 at 17:32

2 Answers 2

6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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?> $\endgroup$
    – alex
    Nov 29, 2010 at 4:29
  • $\begingroup$ @alex: every two rational numbers have the same denominator: $3/5=6/10$. $\endgroup$
    – user6976
    Nov 29, 2010 at 10:51
  • 1
    $\begingroup$ Just to be clear, this procedure only gives decidability in the case that $p$ and $q$ are homogeneous of the same degree. $\endgroup$
    – Noah Stein
    Nov 29, 2010 at 17:44
  • $\begingroup$ @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. $\endgroup$
    – user6976
    Nov 29, 2010 at 18:51
4
$\begingroup$

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.

$\endgroup$

Your Answer

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

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