# Showing that complicated mixed polynomial is always positive

I want to show that

$\left(132 q^3-175 q^4+73 q^5-\frac{39 q^6}{4}\right)+\left(-144 q^2+12 q^3+70 q^4-19 q^5\right) r+\left(80 q+200 q^2-243 q^3+100 q^4-\frac{31 q^5}{2}\right) r^2+\left(-208 q+116 q^2+24 q^3-13 q^4\right) r^3+\left(80-44 q-44 q^2+34 q^3-\frac{23 q^4}{4}\right) r^4$

is strictly positive whenever $q \in (0,1)$ (numerically, this holds for all $r \in \mathbb{R}$, although I'm only interested in $r \in (0,1)$).

Is that even possible analytically? Any idea towards a proof would be greatly appreciated. Many thanks!

Let $f(r) = A + Br + Cr^2 + Dr^3 + Er^4$ be the function as defined above.

Then it holds that

$f(r)$ is a strictly convex function in $r$ for $q \in (0,1)$, $f(0) > 0$, $f'(0) < 0$, and $f'(q) > 0$. Hence, for the relevant $q \in (0,1)$, $f(r)$ attains its minimum for some $r^{min} \in (0,q)$.

$A$ is positive and strictly increasing in $q$ for the relevant $q \in (0,1)$,

$B$ is negative and strictly decreasing in $q$ for the relevant $q \in (0,1)$,

$C$ is positive and strictly increasing in $q$ for the relevant $q \in (0,1)$,

$D$ is negative and non-monotonic in $q$, and

$E$ is positive and strictly decreasing in $q$ for the relevant $q \in (0,1)$.

-
I haven't tried it out. But first thing I would do, is check if each of the terms inside the brackets has a minimum greater or equal zero. If that is the case the complete polynomial is positive as $r\in(0,1)$. –  sonystarmap Dec 17 '12 at 12:49
okay $-144q^2+12q^3+70q^4-19q^5$ has a negative extrema, so forget about my idea. –  sonystarmap Dec 17 '12 at 12:51
Thanks for the input - unfortunately this is not the case. I'll update my post with some more findings. –  Martin Dec 17 '12 at 12:51
Did you lose the tail end of the statement for $D$? –  Amzoti Dec 17 '12 at 12:59
No, well D is negative and non-monotonic for the relevant $q \in (0,1)$. –  Martin Dec 17 '12 at 13:01

I have found an argument which reduces the proof to the positivity on $]0,1[$ of five univariate polynomials with integer coefficients, namely

$$\begin{array}{lcl} A &=& 80-44 q-44 q^2+34 q^3-\frac{23 q^4}{4} \\ & & \\ B_1(w)&=& -92w^{18} - 828w^{17} + 207w^{16} - 1952w^{15} + 987w^{14} + 7372w^{13} - 5693w^{12} \\ & & + 21976w^{11} - 15817w^{10} - 5476w^9 + 10813w^8 - 57744w^7 + 55457w^6 \\ & & - 52140w^5 + 44145w^4 - 13608w^3 + 12393w^2 \\ & & \\ B_2(w) &=& -23w^8 - 44w^6 + 94w^4 + 212w^2 + 81 \\ & & \\ C_1(w) &=& -368w^{27} - 6992w^{26} - 29063w^{25} + 23289w^{24} - 145610w^{23} + 122422w^{22} \\ & &+ 383221w^{21} - 739371w^{20} + 2438232w^{19} - 2093000w^{18} - 785870w^{17} \\ & & + 4785874w^{16} - 14449804w^{15} + 16096660w^{14} - 10344110w^{13} \\ & & - 1681358w^{12} + 26043752w^{11} - 38527768w^{10} + 41520789w^9 \\ & & - 36111627w^8 + 18921222w^7 - 8407962w^6 + 1983609w^5 + 1003833w^4 \\ & & \\ C_2(w) &=& 92w^{15} + 920w^{14} + 713w^{13} + 2665w^{12} + 1678w^{11} - 5694w^{10} \\ & & - w^9 - 21977w^8 - 6160w^7 - 684w^6 - 11497w^5 + 46247w^4 \\ & &- 9210w^3 + 42930w^2 - 1215w + 12393 \\ \end{array} \tag{1}$$

So if you don’t care much about the question and just need to be 90% sure, just plug those polynomials in your favorite math software to compute numerically the minima of those univariate polynomials, and check that the minima are indeed nonnegative.

If, however, you insist on being 100% certain, you can use some more sophisticated software to decompose those polynomials and prove their positivity completely rigorously (I did this with PARI-GP and can discuss the ugly computational details if you're interested).

I denote your polynomial by $M=M(q,r)$. A classical method to show that something is positive is to write it as a sum of squares. To ensure the termination of the computation, we also make degrees (in $r$) decrease : as the initial polynomial has degree $4$ in $r$, we write it as (square of some polynomial)+(positive polynomial of degree $2$ in $r$), etc.

Let $A,B,C,\alpha,\beta,\gamma$ be terms to be defined later. Then

$$M=M(q,r)=A\bigg((r-\alpha)(r-\beta)\bigg)^2+B(r-\gamma)^2+C \tag{2}$$ with $A,B$ and $C$ positive, which concludes the proof. This was really easy, don't you think ? Actually, perhaps I should bother to explain what those terms $A,B,C,\alpha,\beta$ and $\gamma$ are.

$A$ is of course the leading coefficient attached to $r^4$ in $M(q,r)$. Some numerical experiments suggest that the function $N(q)={\sf inf}_{r\in {\mathbb R}}M(q,r)$ has a pole at $q=1$, with $N(q) \sim_{q \to 1} C\sqrt{1-q}$ for some constant $C$. This motivates the change of variables $q=1-w^2$. When $q\in [0,1]$, we can take $w\in [0,1]$ also. Further, the numerical values show that the minimum $N$ is generally attained “near” $1-w$. So let us take $\alpha=1-w$. Next, $\beta$ is for this value of $\alpha$ the unique value making the $r^3$ terms cancel in (1), namely

$$\beta=\frac{-23w^9 + 49w^8 - 44w^7 - 12w^6 + 94w^5 - 314w^4 + 212w^3 - 124w^2 + 81w + 81}{-23w^8 - 44w^6 + 94w^4 + 212w^2 + 81} \tag{3}$$

Then, $B,C$ and $\gamma$ are uniquely defined as they correspond to the canonical form of the trinomial $M-A\bigg((r-\alpha)(r-\beta)\bigg)^2$. We have

$$B=B(w)=\frac{B_1(w)}{B_2(w)}, C=C(w)=\frac{C_1(w)}{C_2(w)} \tag{4}$$

where $B_1,B_2,C_1$ and $C_2$ are as in $(1)$. Finally, I append some PARI-GP that allows one to compute those polynomials :

martin0=132*(q^3)-175*(q^4)+73*(q^5)-(39/4)*(q^6)

martin1=-144*(q^2)+12*(q^3)+70*(q^4)-19*(q^5)

martin2=80*q+200*(q^2)-243*(q^3)+100*(q^4)-(31/2)*(q^5)

martin3=-208*q+116*(q^2)+24*(q^3)-13*(q^4)

martin4=80-44*q-44*(q^2)+34*(q^3)-(23/4)*(q^4)

martin=martin0+martin1*r+martin2*(r^2)+martin3*(r^3)+martin4*(r^4)

rewritten_martin4=(81/4)+53*(1-q)+(27/4)*((1-q)^2)+(67/4)q((1-q)^2)+(23/4)q((1-q)^3)

check1=martin4-rewritten_martin4

term_called_m=subst(martin,q,1-(w^2))

constant_called_a=subst(martin4,q,1-(w^2))

alpha=1-w

term1=term_called_m-constant_called_a*(((r-alpha)*(r-beta))^2)

should_be_zero1=polcoeff(term1,3,r)

beta0=-polcoeff(should_be_zero1,0,beta)/polcoeff(should_be_zero1,1,beta)

term2=term_called_m-constant_called_a*(((r-alpha)*(r-beta0))^2)

b1=numerator(constant_called_b)

b2=denominator(constant_called_b)

rewritten_b1=w^2*(1-w)(11178+1215(1-w)+(w^2)(40022+(1-w)\

((169528389737/244140625)+(690889833236/48828125)w+((w-(1/5))^2)\

((540432547763/9765625)+(16452083708/390625)w+(14109073812/390625)(w^2)+\

(w^2)(1-w)(13421226/78125 +333572514/15625*w +62317552/3125*w^2+\

2068768/125*w^3 +1060753/125*w^4+82041/25*w^5 +5704/5*w^6+92*w^7)))))

check2=rewritten_b1-b1

rewritten_b2=81+(w^2)(212+(w^2)(27+(1-w^2)*(23*w^2 + 67)))

check3=rewritten_b2-b2

term3=term2-constant_called_b*(r-gammaa)^2

should_be_zero2=polcoeff(term3,1,r)

gamma0=-polcoeff(should_be_zero2,0,gammaa)/polcoeff(should_be_zero2,1,gammaa)

constant_called_c=simplify(term2-constant_called_b*(r-gamma0)^2)

c1=(-numerator(constant_called_c))

c2=(-denominator(constant_called_c))

all_checks=[check1,check2,check3]

-
Thanks a ton for your effort. The proof strategy looks very interesting, although I fear that it is of little practical use for my application (applied economics paper). The decomposition into a sum of squares seems like a very good idea though. As my expression arises from summing up different variables (3 equilibrium profit levels + equilibrium consumer surplus - 7/32) [where 7/32 is some meaningful benchmark value], maybe one can come up with a slightly simpler proof. On the other hand, due to the complexity of the function, I might opt for a numerical proof only. –  Martin Dec 20 '12 at 17:13

Because you want to show that this is always positive, consider what happens when $q$ and $r$ get really big. The polynomials with the largest powers will dominate the result.

You can solve this quite easily by approximating the final value using a large number of inequalities.

-

I would do a mixture of numerical and analytic approaches. I'll consider $r<1$ only. First, note that an increasing geometric progression has positive finite differences of all orders and those differences form a geometric progression themselves. Thus, it makes sense to decompose the geometric progressions into the elementary polynomials of the form $1$, $x$, $x(x-1)/2$, $x(x-1)(x-2)/6$, etc. (only starting from the right end because our progressions are decreasing): $$(1,r,r^2,r^3,r^4)=r^4(1,1,1,1,1)+r^3(1-r)(4,3,2,1,0)+r^2(1-r)^2(6,3,1,0,0)+\dots$$ and similarly for $q$. The program below (in Asymptote) does the decomposition. I'm too lazy to rewrite the output, but if you run it and look at the resulting $5\times 7$ matrix, you'll see with a naked eye that the diagonals going left bottom to right top define non-negative polynomials, which is the end of the story.

real[][] C=
{
{0,0,0,132,-175,73,-39/4},
{0,0,-144,12,70,-19,0},
{0,80,200,-243,100,-31/2,0},
{0,-208,116,24,-13,0,0},
{80,-44,-44,34,-23/4,0,0}
};

real[][] X=
{
{1,1,1,1,1},
{4,3,2,1,0},
{6,3,1,0,0},
{4,1,0,0,0},
{1,0,0,0,0},
};

real[][] Y=
{
{1,1,1,1,1,1,1},
{6,5,4,3,2,1,0},
{15,10,6,3,1,0,0},
{20,10,4,1,0,0,0},
{15,5,1,0,0,0,0},
{6,1,0,0,0,0,0},
{1,0,0,0,0,0,0},
};

real[][] Z=X*C*transpose(Y);
write(Z);

pause();

-
I guess the $r<1$ in the first line of your answer should be $0<r<1$, right? –  Ewan Delanoy Dec 24 '12 at 14:50
Yes, of course :) –  fedja Dec 24 '12 at 16:02