Polynomial positive on an interval

See "Polynomials that are positive on an interval" by myself and Bruce Reznick, Trans. Amer. Math. Soc. 352 (2000), 4677-4692. We give a brief history of this problem along along with a bound for the minimum $m$ so that $p$ can be written $p = \sum_{i=1}^m c_i x^i (1-x)^{m-i}$ with $c_i \geq 0$. The bound depends on the minimum of $p$ on $[0,1]$ and the size of the coefficients. The best reference for this (without the bound) is probably P\'olya-Szego.

The following extension of Keivan Karai's comment proves the result.

Consider $q(x):=p(x)-c$ where $c=\frac12 \min p([0,1])$.

Approximate $q(x)$ as Keivan suggested: let $$ q_n(x) = \sum_{i=0}^n q(i/n) \binom ni x^i(1-x)^{n-i} . $$ Then $q_n$ is a polynomial of at most the same degree as $q$ (and hence $p$) and $q_n$ converges to $q$ uniformly on $[0,1]$. Since the degree is bounded, it follows that the coefficients of $Q_n$ converge to the coefficients of $q$. In particular, $\deg q_n=\deg q$ for all large enough $n$. Let $a$ be the leading coefficient of $q$ and $a_n$ the leading coefficient of $q_n$. Then $a_n\to a$ and hence the polynomial $$ r_n(x):=\frac a{a_n} q_n(x) $$ converges to $q(x)$ uniformly on $[0,1]$. Choose $n$ so large that $|r_n-q|<c$ on $[0,1]$, then $r_n<p$ on $[0,1]$. Since $r_n$ is already represented in the desired form, it remains to represent $p-r_n$. Observe that $\deg(p-r_n)<\deg p$ and proceed by induction.

Appendix: Why $\deg q_n\le\deg q$.

Since $q_n$ is linear in $q$, it suffices to consider the case $q(x)=x^k$. Let $$ F_0(u,v) = (u+v)^n = \sum_{i=0}^n \binom ni u^i v^{n-i} $$ and $$ F_m = u\cdot \frac{\partial}{\partial u} F_{m-1}, \qquad m=1,2,\dots $$ Then $$ F_k(u,v) = \sum_{i=0}^n i^k \binom in u^iv^{n-i}, $$ hence $q_n(x) = n^{-n} F_k(x,1-x)$. By induction in $k$ one sees that $F_k(u,v)$ is a linear combination of terms of the form $u^j(u+v)^{n-j}$ with $j\le k$. Hence $F_k(x,1-x)$ has degree at most $k$, and so does $q_n(x)$.

Remark. Analyzing the coefficients of the above linear combination, one can see that, as $n\to\infty$ and $k$ fixed, the coefficient at $u^j(u+v)^{n-j}$ goes to 1 and all other ones go to 0. This gives an elementary proof of convergence $q_n\to q$ (coefficient-wise) avoiding the general theory.

My first response (which I'm leaving below) was fallacious, but it was based on the idea that this method had to work, given the truth of the assertion. Since it doesn't work ..., I'll show why my interpretation of the question (I thought $n$ was implicitly bounded) is impossible. Note that Sergei Ivanov's answer, based on a comment suggestion of Keivan Karai, solves the problem when $n$ is unbounded.

There is no solution when $n$ remains bounded.

When the degree $n$ is bounded, the assertion for positive polynomials implies the limiting case, for polynomials that are non-negative in the interval.

But polynomials of the form given in the question do not have zeros on the unit interval (as suggested by commenters). In particular, (x-1/2)^2 cannot be represented by in this form, since all coefficients would be forced to be 0.

Moreover: there cannot be any positive finite generating set for the convex cone of positive polynomials of degree $> 1$. This cone is not polyhedral, having uncountably many different extremal rays for instance in degree 2, where for each $a$ in the unit interval and $t > 0$, the ray of polynomials $t (x-a)^2$ is extremal, not expressible as a convex combination of other positive polynomials.

Here is a plot of the convex cone showing coefficients of positive quadratic polynomials. The three triangles bound the convex combinations of basis functions mentioned in the question. The curved side consists of coefficients of nonnegative quadratic functions with a 0 in the interval. These are not positive linear combinations of any finite collection of positive polynomials.

The $n$th Bernstein polynomial expressions for quadratic polynomials, as described in Ivanov's answer, map to this space as convex cones. Here is a slice, in the quadratic coefficient space, of the images of cones of positive quadratic polynomials so obtained for $n = 2..6$. The vertices in the pictures are coefficients of approximations of quadratic polynomials that have the form $(x-i/n)(x-(i+1)/n$. Even though these polynomials are not positive, the coefficients in the Bernstein approximation are postiive, since they only make use of values at the $(i/n)$ points. The cone of positive quadratic $n$th Bernstein polynomials is somewhat bigger than this, but these are enough to illustrate how they converge.

The answer below was mistaken, as noted in comments. It was based on inverse deduction -- that if the statement were true, this had to be true.

That's a nice, simple representation; I wasn't aware of it, but presumably something this simple must be known. Here's a proof:

The case $i+j = n$ is sufficient to get degree $n$ polynomials (perhaps that's what you meant).

Here is a plot of this positive basis, for $n = 3$; the picture suggests a working strategy.

Since only one of the functions is positive at each endpoint, you know what the coefficients of these functions must be. If you subtract, is it still positive? That follows from

Lemma: any degree $n$ polynomial positive in the unit interval that takes value 1 at 1 must be greater than $x^n$.

(My proof was fallacious ).

From the lemma, it follows that $q(x) = p(x) - p(0) (1-x)^n + p(1) x^n$ is still positive. Since $q(x)$ is 0 at the endpoints of the interval, it is divisible by $x(1-x)$. Use induction to represent the quotient; this gives the desired representation for $p$.