# Proving univariate polynomials (defined by sums, binomial coeffs, etc.) are nonnegative: is it 'routine'?

My colleagues and I are working on a project related to an old paper of C. Borell and we have boiled it down to the following problem:

Show, for all integers $1 \leq i \leq k$, that the univariate real polynomial $P(x) = \frac12 \binom{2k}{2i} (1+x)^{2k-2i} + \frac12 Q(x)$ is everywhere nonnegative, where $Q(x) = \sum_{j=i}^k \binom{2k}{2j}(1-x)^{2k-2j}\binom{j}{i}(-4x)^{j-i}$.

(For what it's worth, Maple recognizes $Q(x)$ as $\binom{2k}{2i} (1-x)^{2k-2i} \text{hypergeom}([-(k-i), -(k-i)+\frac12], [i+\frac12], -4x/(1-x)^2)$.

I'm not asking MO to prove this (although I suppose if someone saw how to do so immediately I wouldn't turn down the answer). Instead, I'm asking "Is this 'routine'?" in the sense of the word used in the Petkovsek-Wilf-Zeilberger A=B book? In other words, would Doron Zeilberger say, "Oh yes, just type the following into Maple and it will produce a proof of the claim"? In other other words, does this question fall into a class of problems known to be decidable?

Of course, for any fixed $i$ and $k$ the problem is 'routine'. E.g., for $k = 4$, $i = 2$, we have $P(x) = 70x^4-168x^3+804x^2-168x+70$ and furthermore I can coax my computer into proving that's nonnegative. (Say, by obtaining a sum-of-squares representation like $P(x) = 42(x-1)^4 + 28x^4 + 552x^2+28$.)

I don't know the "A=B technology" very well: my question is whether it, or any other techniques, can be used to automatically prove these inequalities. I would also be happy to accept an answer explaining why proving these inequalities is not obviously 'routine' and will require some ingenuity.

UPDATE: Doron Zeilberger wrote me an email describing why at least 'half' of this problem is routine: namely, that for $i$ symbolic and $k-i$ numeric the nonnegativity can be proven by computer. He preferred not to post himself but said I could post his ideas here; I will do so once I get a chance to think about them.

-
I wonder if you can manipulate this into a sum of squares plus a positive polynomial with a little bit of work. Notice first that $P(x)$ adds with the $j=i$ summand of $Q(x)$ to give a positive polynomial. Now I wonder if you can show that the sum of the $j=2r+1$ and $j=2r+2$ summands are a sum of squares for each $r\ge 1$, using some variation on the fact that $(1−x)^2+4x=(1+x)^2$. I don't have time right now to see if I can make this work, but it might conceivably be something to try. –  Patricia Hersh Aug 8 '12 at 17:28
There are occasional tricks. I saw this on a website, either MO or MSE. Let $f_n(x) = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \cdots + \frac{x^n}{n!}. \;$ We have the derivative relationship $f_n(x) = f_n'(x) + \frac{x^n}{n!}. \;$ As a result, if $n$ is even, at any critical point $f_n(x) = \frac{x^n}{n!} \geq 0, \;$ and a little detail showing $x=0$ is not a critical point shows $f_n(x) > 0$ for $n$ even and all $x.$ –  Will Jagy Aug 8 '12 at 17:37
@Patricia: I am hoping for a nice SOS representation... –  Suvrit Aug 8 '12 at 17:56
If what I suggested actually worked, it would give a nice SOS representation -- since $P(x)$ added with the $j=i$ summand of $Q(x)$ is a polynomial whose odd degree coefficients are all 0. I was getting something like $(1-x)^2 + 4x$ by factoring out common factors, but there were complicated binomial coefficients one would have to figure out how to rearrange... –  Patricia Hersh Aug 8 '12 at 19:29
Thanks for the comments Patricia and Will -- let me try to think about them... –  Ryan O'Donnell Aug 8 '12 at 21:02

There are some techniques for proving positivity of sums using computer algebra, but they are all heuristic approaches rather than solid algorithms. This is in contrast to identities, which we understand very well algorithmically.

One possibility to prove positivity of some quantity f[n] involving a discrete parameter n is to search for a "witness recurrence", for instance of the form

f[n+2] == a[n] f[n+1] + b[n] f[n]

where a[n] and b[n] are positive rational functions. Once such a recurrence is found, positivity of f[n] follows easily by induction.

Such a witness recurrence need not exist, but if it does, it is typically routine to find (and prove!) it with computer algebra.

For your particular family of polynomials, I found the following recurrence, which implies positivity for a decent portion of indices (k,i), albeit not for all:

(1 + i)*(7 + 6*i + 13*k)*f[k, i] = - (1 + i - 2*k)*(7 + 6*i - k)f[k-2, i-2] + 2(7+13*i+6*i^2-20*k-13*i*k+13*k^2)*(1+x)^2*f[k-2, i-1] - (1 + i)*(7 + 6*i - 13*k)*(1 + x)^4*f[k-2, i] - 2*(-7 + 8*i + 6*i^2 - 20*k - 13*k^2)f[k-1, i-1] + 4(1 + i)*(10 + 3*i)*(1 + x)^2*f[k-1, i]

Observe that the polynomial coefficients of this recurrence are nonnegative whenever 1<=i<=k, EXCEPT the coefficient in front of f[k-2,i-2], which becomes negative for 6i+7 < k. So this recurrences suffices to prove positivity for all i,k with 1<=i<=k<=7+6i.

(You may not see with with the naked eye that the nonlinear polynomials in front of f[k-2,i-1] and f[k-1,i-1] are indeed positive for all i,k with 1<=i<=k, but confirming this is routine for the computer, e.g., using Collins's algorithm for Cylindrical Algebraic Decomposition.)

There are some other recurrences of similar shape, only slightly more complicated, for which the portion of indices (i,k) not covered is smaller. But I was not able to find a recurrence that proves positivity for all i,k in question. Maybe it's possible with some effort.

Following Doron's observation that g[L] := f[i,L+i] is a polynomial in x and i for every fixed L, there is a linear recurrence of order 3 for g[L] with polynomial coefficients in L,i,x, which implies positivity under certain (ugly) restrictions on i and x but not in full generality.

For a fixed positive integer L, you can show positivity of g[L] in Mathematica most easily as follows. Define the function

check[L_Integer] := CylindricalDecomposition[Implies[i>=1, Factor[FunctionExpand[1/2 Binomial2(i+L),2i^(2(i+L)-2i) + 1/2 Sum[Binomial2(i+L),2j^(2(i+L)-2j)Binomialj,i^(j-i),{j,i,(i+L)}]]/Pochhammer[i+1,L]] >= 0], {x,i}]

then check[10] evaluates to True in about 20sec (on my computer), proving the positivity for L=10.

-
Thank you Manuel! This is exactly the sort of answer I was looking for. –  Ryan O'Donnell Aug 10 '12 at 12:27
UPDATE: Fairly soon after posting the above, Manuel emailed me a complete, automatically-found solution; it's a quite simple recurrence relation in the parameters L and i which shows nonnegativity. If he doesn't post it, I may ask him if I can add it here. –  Ryan O'Donnell Aug 13 '12 at 0:08

In good old times the word "routine" meant "easily done by a trained person". In this sense, the problem is, indeed, routine. Change the notation to $s=j-i$, $p=k-i$. Observe that negative $x$ are not a problem. For positive $x$, denote $y^2=\frac{4x}{(1-x)^2}$ and rewrite the inequality as $${2(p+i)\choose 2i}(1+y^2)^p+\sum_{s=0}^p (-1)^s{2(p+i) \choose 2(s+i)}{s+i\choose i}y^{2s}\ge 0.$$ Now start with $i=0$. Then the ugly junk goes away and we get $(1+y^2)^p+\Re[(1+iy)^{2p}]\ge 0$, which is a no-brainer ($|z|^{2p}+\Re[z^{2p}]\ge 0$ for all complex $z$). Now just define $F_0(y)=\Re[(1+iy)^{2p}$, $F_m(y)=y\int_0^yF_{m-1}(t)dt$ and $G_m(y)=\frac{1}{(2m-1)!!}y^{2m}(1+y^2)^p$. The general inequality is equivalent to $G_m+F_m\ge 0$ (my $m$ is your $i$ but, since I used $i$ for the imaginary unit, to use it for the index now would be quite unfortunate). However $y\int_0^y G_{m-1}(t)dt\le y\int_0^y\frac{1}{(2m-3)!!}t^{2m-2}(1+y^2)^p dt=G_m(y)$ ($(-1)!!=1$, of course).

But, as you said, today "routine" means something completely different and I just retreat in shame from the brave new world with my outdated language and ideas...

-
@fedja: I was waiting for an answer from you fedja! I knew you'll find a really cool one :-) –  Suvrit Aug 11 '12 at 7:37
Thank you Fedja! To be honest, like Suvrit I was secretly hoping that you would take a look at this problem ;) –  Ryan O'Donnell Aug 11 '12 at 11:31

EDIT The material below is not really an answer to the original question, but only highlights a technique for checking positivity of a specific polynomial, not an entire class. It might well be impossible to have a generic scheme for entire families of polynomials in general.

Let me recall some results, discussed in these lecture notes, which are helpful for numerically checking if a univariate polynomial is nonnegative.

Theorem A univariate polynomial is nonnegative if and only if it is a sum of squares.

Theorem Let $\mathbf{x}=[1,x,x^2,\ldots,x^m]^T$, and let $P(x)$ have degree $2m$. Then, $P(x)$ is nonnegative if and only if there exists a $m+1 \times m+1$ positive semidefinite matrix $Q$ such that $P(x) = \mathbf{x}^TQ\mathbf{x}$.

Let $P(x)=\sum_{i=0}^{2m} p_ix^i$. It can be further shown that the matrix $Q$ must satisfy \begin{equation*} p_i = \sum_{j+k=i} Q_{jk},\qquad i=0,1,\ldots,2m. \end{equation*}

Theorem If we can find a positive semidefinite matrix $Q$ that satisfies the above linear constraints (this can be done using regular semidefinite programming software), then the polynomial $P(x)=\sum_{i=0}^{2m} p_ix^i$ is nonnegative or SOS, otherwise not.

-
Right, that's really what I meant about each specific case being 'routine'; you can certify that a given matrix with rational entries is PSD in polynomial time. The question is about doing it for families of polynomials. –  Ryan O'Donnell Aug 8 '12 at 16:50
Indeed, each specific case is "routine", though it is worth noting here that if the degree of the polynomial gets high enough, then you'll probably have to give up maple, and use an SDP solver. When you say certifying for families, do you have a parameterized class in mind; in that case, one could see if the resulting parametric SDP can be solved in polynomial time, though I am not that too certain about that. –  Suvrit Aug 8 '12 at 17:16
Hi Suvrit, thanks for the comments. I mean specifically for the family of polynomials (parameterized by i and k) in the question. I thought perhaps that if one could give a recurrence relation for the polynomials, it might become clear that they are nonnegative... –  Ryan O'Donnell Aug 8 '12 at 17:37
Sorry, somehow in my excitement, I suppressed $i$ and $k$ being free parameters (I just read them as summation indices); maybe you might want to call them $m$ and $n$ to ameliorate dumb oversights like mine! –  Suvrit Aug 8 '12 at 17:48

Proving that one polynomial with numerical coefficients is positive is indeed routine, and you can write a computer program doing this. There are many ways to do this by performing finitely many rational operations on coefficients. For example, Sturm's algorithm.

But your problem is proving positivity of infinitely many polynomials of all degrees. And I don't think that in general this problem can be solved by some finite procedure.

-