efficient method to compare polynomials (fixed degree and non-negative indeterminate $x$)

104 Views Asked by At

Let's say i have two polynomials $P_1(x)=a+bx+cx^2+dx^3$ and $P_2(x)=p+qx+rx^2+sx^3$ where $a,b,c,d \ge 0$ and $p,q,r,s \ge 0$ $a,b,c,d,p,q,r,s$ are all integers then can i say

if $a+2b+4c+8d \gt p+2q+4r+8s$

then can I say $a+bt+ct^2+dt^3 \ge p+qt+rt^2+st^3$ for $t \ge 1$? $t$ is an integer. All I want to do is minimize the calculation part in my algo.

4

There are 4 best solutions below

6
On BEST ANSWER

No. Take $(a,b,c,d,p,q,r,s)=\left(0,\frac 32,0,2,0,1,2,1\right)$.

We have $$a+2b+4c+8d\gt p+2q+4r+8s$$ but $$a+bt+ct^2+dt^3\color{red}{\lt} p+qt+rt^2+st^3$$ for $t=1$.


Take $(a,b,c,d,p,q,r,s)=(1,1,2,1,0,0,0,2)$ where $a,b,c,d,p,q,r,s$ are non-negative integers.

We have $$a+2b+4c+8d\gt p+2q+4r+8s$$ but $$a+bt+ct^2+dt^3\color{red}{\lt} p+qt+rt^2+st^3$$ for $t=3$.

2
On

$$a+2b+4c+8d > p+2q+4r+8s$$

Let $t=1$, $$a+b+c+d < p+q+r+s$$

Let $a=b=c=d=1$.

$$15 > p+2q+4r+8s$$ $$4 < p+q+r+s$$

Let me set $p=4, q=1, r=0, s=0$ and I have proven that your claim is not true.

0
On

Your question is equivalent to:

If $P$ is a cubic polynomial with integer coefficients such that $P(2) \ge0$, does it follow that $P(t)\ge0$ for all $t \in \mathbb N$?

This is clearly not true. Take $P(x)=-(x-2)^3$.

0
On

Taking into account your comment about how you intended to use the relationship that you had conjectured, your purpose was to find an easily-tested relationship among the coefficients of the two polynomials $P_1(x) = a+bx+cx^2+dx^3$ and $P_2(x) = p+qx+rx^2+sx^3$ along with a minimum parameter value $m$ such that if the coefficients satisfy your condition, then you can guarantee that $$ a+bx+cx^2+dx^3 > p+qx+rx^2+sx^3 \tag1$$ for every integer $x$ such that $x \geq m.$ (You were attempting to use the minimum value $m=1,$ but since you are mainly concerned about having to evaluate the polynomials for thousands of values of $x$ I think we can afford to allow the value of $m$ to be greater than $1$ as long as it is not too large.)

The desired inequality $(1)$ is equivalent to $$ P_3(x) = (a-p) + (b-q)x + (c-r)x^2 + (d-s)x^3 > 0.$$

Now a fact about polynomials is that if a polynomial (in this case $P_3(x)$) is not constant, it tends either to $+\infty$ or to $-\infty$ as the parameter $x$ tends to $+\infty.$ In the first case there is some minimum value $m$ such that $P_3(x) > 0$ whenever $x \geq m$; in the second case there is some value $m$ such that $P_3(x) < 0$ whenever $x \geq m.$ And you only need to look at leading term to see which way the polynomial will go. For $P_3(x),$ as long as $d \neq s$ then the leading term is $(d-s)x^3,$ and in order to have $P_3(x) > 0$ whenever $x \geq m$ we just need to see that $d > s.$ Once we see that, it remains only to find a suitable value of $m.$

When $d > s,$ to simplify things, let \begin{align} d' &= d - s, \\ p' &= \begin{cases} p - a & p > a, \\ 0 & p \leq a, \end{cases}\\ q' &= \begin{cases} q - b & q > b, \\ 0 & q \leq b, \end{cases}\\ r' &= \begin{cases} r - c & r > c, \\ 0 & r \leq c, \end{cases} \end{align} and set $P_4(x) = -p' - q'x - r'x^2 + d'x^3.$ Then $a - p \geq -p' \geq 0,$ $b - q \geq -q' \geq 0,$ $c - r \geq r' \geq 0,$ and therefore $P_3(x) \geq P_4(x)$ whenever $x \geq 0.$

Notice that whatever the value of $m$ turns out to be, if $x \geq m$ then we can set $y = x - m,$ which implies that $y \geq 0.$ Then \begin{align} P_4(x) &= -p' - q'(m+y) - r'(m+y)^2 + d'(m+y)^3 \\ &= -p' - q'(m+y) - r'(m^2 + 2my + y^2) + d'(m^3 + 3m^2y + 3my^2 + y^3) \\ &= -p' - mq' - m^2r' + m^3d' + (-q' - 2mr' + 3m^2d')y + (-r' + 3md')y^2 + d'y^3\\ &\geq -p' - mq' - m^2r' + m^3d' + \frac3m(-p' - mq' - m^2r' + m^3d')y \\ &\qquad + \frac3{m^2}(-p' - mq' - m^2r' + m^3d')y^2 + \frac1{m^3}(-p' - mq' - m^2r' + m^3d')y^3\\ &= \left(1 + \frac3my + \frac3{m^2}y^2 + \frac1{m^3}y^3\right) (-p' - mq' - m^2r' + m^3d'), \end{align} and the last quantity is positive as long as $m^3d' - m^2r' - mq' - p' > 0.$

In summary, if we set $d',$ $p',$ $q',$ and $r'$ as shown above, and if $m^3d' - m^2r' - mq' - p' > 0,$ then whenever $x\geq m$ it follows that $P_4(x) >0,$ therefore $P_3(x) > 0,$ and therefore $a+bx+cx^2+dx^3 > p+qx+rx^2+sx^3.$