# How can I tell if one polynomial is greater than another over an interval?

$y_1=ax^2 + bx + c$

$y_2=dx^2 + ex + f$

Question: what is the proper way for me to test that $y_1 > y_2$ over an interval (say 0 to 10, inclusive) for all numbers in that interval?

I assume it has something to do with testing the integral of y1 - y2, but not sure.

I'm working on a continuous game theory program written in Python, and am working on the concept of strict domination. $y1$ and $y2$ are meant to be the utility functions for a given agent. $y1$ strictly dominates $y2$ if, over the range of other player actions in question (i.e. the interval of $x$), $y1>y2$.

-
What methods are at your disposal and what level of rigor are you after? For example, if you have $y_1$ and $y_2$, why not just plot them both? Or plot the difference $y_1-y_2$ and see where that's positive? Basically, you are wanting to solve the quadratic inequality $(a-d)x^2+(b-e)x+(c-f)>0$, so it's really just an algebra problem. – JohnD Jan 8 '13 at 20:27
Also, are you wanting to test the truthfulness of the inequality at certain $x$ values or are you wanting to find all $x$ values for which the inequality is true? – JohnD Jan 8 '13 at 20:30

Solve $y_{1} = y_{2}$ and then use the solutions (if there are any) to construct the sign diagram of $y_{1} - y_{2}$ over the interval.

Having $\displaystyle \int_{a}^{b} (y_{1} - y_{2}) \,d{x} > 0$ is a necessary condition for $y_{1} > y_{2}$ over the interval $[a,b]$, but definitely not sufficient.

-

While Haskell Curry's answer gives a mathematical solution to the problem, I thought I would offer a more programmer-oriented solution; in particular, it's worth noting that the problem can be solved without ever calculating a square root.

First of all, as already noted, your question is equivalent to considering the function $f(x) = y_1(x)-y_2(x) =Ax^2+Bx+C$ (with $A=a-d$, etc.) and testing whether $f(x) \gt 0$ over an interval $x\in [x_1, x_2]$; I'll use this formulation of the problem.

Next, consider the vertex of the parabola $(x,f(x))$; that is, the point $x_0=-B/2A$ that represents the axis of symmetry of the function $f$. ($f$ can be written as $f(x) = A(x-x_0)^2+M$ for some constant $M$ and this is in fact the genesis of the quadratic formula, but that's irrelevant to the problem at hand). If $x_0$ isn't in the interval $[x_1, x_2]$ (and note that this also covers the degenerate case where $A=0$, i.e. where there is no vertex) then the function $f$ must be either strictly increasing or strictly decreasing over that range; this means that we can just look at the signs of $f(x_1)$ and $f(x_2)$ and be sure that if both are positive, then $f$ is positive over the whole range.

On the other hand, if $x_0$ is within the interval, then $f$ takes on either a maximum or a minimum there (depending on the sign of $A$), and this means that $f(x)$ will be strictly increasing on one of the two intervals $[x_1, x_0]$ or $[x_0, x_2]$ and strictly decreasing on the other. Here, we can just look at the sign of $f(x)$ at all three points $x=x_0$, $x=x_1$ and $x=x_2$; if any of them are negative then obviously $f$ is negative at some point in the interval, but if all three are positive then by the 'bitonicity' of $f$ we know that it must be positive within the entirety of the interval. This gives us the following (pseudocode) function:

bool PositiveOnRange(Quadratic f, float x1, float x2)
{
if (f.evalAt(x1) <= 0) return false; // negative at one end of the range
if (f.evalAt(x2) <= 0) return false; // negative at the other end
if ( f.A == 0 ) return true; // not actually quadratic
float x0 = -f.B/(2.0*f.A);
if ( (x0 < x1) || (x0 > x2) ) return true; // vertex not in range
return ( f.evalAt(x0) > 0 ); // sign at vertex
}


For functions that aren't as simple as quadratics, the most straightforward approach might be a combination of subdivision and interval arithmetic; essentially, when evaluating a function (it works particularly well for polynomials, but note that exponentials and arbitrary monotonic functions are well-behaved for interval arithmetic too), rather than evaluating it at a point evaluate it 'at' an interval. Intervals can be added and multiplied with simple rules, and any monotonic function $f(x)$ evaluated at an interval $I=[a, b]$ yields the (possibly mis-ordered) interval $f(\!(I)\!) = [f(a), f(b)]$. Interval arithmetic isn't necessarily strict - for an arbitrary function $f$, if we compute $f(\!(I)\!) = J = [J_l, J_r]$ then it doesn't necessarily mean that every value $J_l\lt y\lt J_r$ will be $f(x)$ for some $x\in I$ - but it is conservative, in the sense that if $f(\!(I)\!) = J$, then for every $x\in I$ we have $f(x)\in J$.

Using interval arithmetic, the problem can then be solved with a divide-and-conquer algorithm: start with the interval $I=[x_L, x_R]$ you want to confirm $f()\gt 0$ on. Start by evaluating $f(x_L)$ and $f(x_R)$ to make sure that your endpoints are both positive. Assuming that passes, compute $f(\!(I)\!)$ and test to see whether it contains 0. If not, then you're done; you know that your function must be positive on the interval. If it does contain $0$, on the other hand, then evaluate $f$ at the midpoint $x_M = \frac{(x_L+x_R)}{2}$. Again, if this fails then you're done; if it succeeds, then consider the two intervals $I_L = [x_L, x_M]$ and $I_R = [x_M, x_R]$. You can evaluate $f(\!(I_L)\!)$ to see if it contains 0 (and recurse down until you either fail or finally start getting intervals that are 'good'), and do the same with $f(\!(I_R)\!)$. This gives the following pseudocode (which should probably be converted to use an explicit stack of intervals rather than recursion and of course needs some sanity-checks to keep from recursing infinitely, but those are programming details):

bool PositiveOnRange(Function f, float xL, float xR)
{
// we presume that xL and xR have already been tested and confirmed positive.
Interval testInterval = f.evalOnInterval(Interval(xL, xR));
if ( !(testInterval.Contains(0)) ) return true;
float xM = 0.5*(xL+xR);
if ( f.evalAt(xM) < 0 ) return false;
return (PositiveOnRange(f, xL, xM) && PositiveOnRange(f, xM, xR));
}

-

It depends on what you mean by "$y_1>y_2$ over an interval" ...

The wording of your question seems to suggest you may want something like $$\int_a^b w(x)(y_1(x)-y_2(x))\, \mathrm{d}x > 0$$ meaning that some weighted sum of the polynomials favours $y_1$ over $y_2$ over the interval.

Other notions of $>$ could be something like

$$\mathrm{max}_{x\in[a,b]}\ y_1 > \mathrm{max}_{x\in[a,b]}\ y_2$$

Or perhaps

$$y_1>y_2\ \forall x\in[a,b]$$

Or even as JohnD commented, you may just be interested in one or all values of $x$ for which $y_1>y_2$.

There are different situations where you could use each of those (other possibilities exist too), you just need to be clear on what it is that you need for $>$.

-

One method is to check the first point, so in this case, check $y_1(0)\geq y_2(0)$. Then consider the derivatives and verify that $y_1'(x)\geq y_2'(x)$ for all $x\in[0,10]$.

-
Surely this condition is sufficient but not necessary? For example, $y_1=20-x$ and $y_2=x$ fail your condition, but $y_1\ge y_2$ for $1\le x\le 10$. – user108903 Jan 8 '13 at 20:32
This is an extremely strong condition. It is also not a necessary condition. – Calvin Lin Jan 8 '13 at 20:32