15
$\begingroup$

If $p$ is a polynomial with real coefficients and p(x)>0 on [0,1], then $p(x)=\sum c_{i,j} x^i(1-x)^j$ with $c_{i,j}$ positive. I know this is true but but I need a proof/reference. Thanks!

$\endgroup$
7
  • $\begingroup$ For further needs: note the usual $ \$ $ for the TeX. As to the question, note that $p(x):=x(1-x)=x^1(1-x)^0-x^2(1-x)^0$, so the claim as you stated has to be corrected/made precise. $\endgroup$ Sep 19, 2010 at 11:17
  • $\begingroup$ Pietro: Yes, but you can also write it as $x(1-x)$. The dimension of the space of the functions $x^i(1-x)^{n-i}$ for $0 \le i \le n$ is less than $n+1$, so to write an arbitrary polynomial of degree $n$ you need to use polynomials of degree $n+1$, so the representation will be non-unique. $\endgroup$ Sep 19, 2010 at 11:29
  • 5
    $\begingroup$ You can certainly use Bernstein polynomials to approximate your polynomials by positive linear combinations of $x^i (1-x)^{n-i}$. More precisely, if you set $$ P_n(x)=\sum_{i=0}^{n} p(\frac{i}{n}) {n \choose i} x^i (1-x)^{n-1}$$ then it turns out that $p_n$ converges uniformly to $p(x)$ on $[0,1]$. (This is, by the way, true for any continuous function, hence it gives a proof of Weierstrass approximation theorem). I did some calculations which show that the sequence does not stabilize if you start with a polynomial, but it always produces a polynomial of the same degree. $\endgroup$ Sep 19, 2010 at 11:48
  • 1
    $\begingroup$ So, what I wrote above is not a solution, but maybe someone can find a clever way to modify these polynomials to get the answer. $\endgroup$ Sep 19, 2010 at 11:49
  • 1
    $\begingroup$ Google on "polynomials positive on an interval", why not? This finds me a paper by Powers and Reznick which apparently covers much more, though. $\endgroup$ Sep 19, 2010 at 13:28

6 Answers 6

19
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Dear Vicki: Welcome to MO! $\endgroup$ Sep 20, 2010 at 1:55
  • $\begingroup$ Thank you, this helps! I had seen Akhizier's book where he writes p(x) as its Bernstein polynomial (with a higher N) plus 'smaller terms' but was looking for this exact representation. $\endgroup$ Sep 20, 2010 at 8:35
13
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Very nice. As a comment, there is an alternative way to show why the $\deg q_n \le \deg q$. In fact, $q_n={\mathbb E}[q(\frac{X_1+ \cdots X_n}{n})]$ where each $X_i$ are i.i.d. with Bin. distribution with parameter $x$. Now assume $q(x)=x^k$. Now expand $(X_1+\cdots +X_n)^k$ and use the fact that all of the moments ${\mathbb E}[X^k]=x$ for all $k$ when $X$ has Binomial distribution. So using independence of $X_i$, each summand has degree at most $k$. $\endgroup$ Sep 19, 2010 at 15:48
  • 2
    $\begingroup$ I had trouble following, and had doubts because of my negative answer, so I tried the approximation in your formula for the polynomial q(x) = .1 + (x-.1)^2, correcting assumed typo $x^i(1-x)^i \to x^i(1-x)^{n-i}$. For the degree 15 approximation, I get degree 15: $ 1.51667 x - 10.6167 x^2 + 50.05 x^3 - 150.15 x^4 + 330.33 x^5 - 550.55 x^6 + 707.85 x^7 - 707.85 x^8 + 550.55 x^9 - 330.33 x^10 + 150.15 x^11 - 50.05 x^12 + 11.55 x^13 - 1.65 x^14 + 0.11 x^15 $. It approximates well except near the 0 endpoint --- should the summation have started from 0? The extra term still gives degree 15. $\endgroup$ Sep 19, 2010 at 16:23
  • $\begingroup$ Sorry for the typos. Yes all sums should start with $i=0$. Fixed now. $\endgroup$ Sep 19, 2010 at 16:30
  • 1
    $\begingroup$ I rechecked your example (using computer algebra program 'maxima') with corrected summation range and got degree 15 too. What a surprise! Then I replaced 0.1 by 1/10 and got a nice short answer: $\frac{14}{15}x^2-\frac{29}{15}+\frac{11}{10}$. Damn stupid machine! $\endgroup$ Sep 19, 2010 at 16:53
  • 1
    $\begingroup$ Yes, I too rechecked, including the i=0 term and being more careful about rounding, and got a degree 2 polynomial. I understand now: the expression necessarily involves polynomials of arbitrarily high degree, even though the answer is quadratic, and no such expression is possible for $p$ that is nonnegative with an interior 0. It would be interesting to plot the polyhedral subdivision of coefficients of quadratic polynomials given by the degree 2 or 3 polynomials expressible in the above form, as $n$ varies. $\endgroup$ Sep 19, 2010 at 17:02
4
$\begingroup$

Later Still: See Vicki Power's answer for a reference more suitable for your specific question.

Alternatively, if you simply want a reference, this is an application of the highly nontrivial Schmüdgen theorem (a.k.a. Schmüdgen's Positivstellensatz) 1. The theorem says that if you have a compact semialgebraic set $K \subset \mathbb{R}^n$ defined by inequalities $\{g_1 \geq 0, \dots, g_s \geq 0\}$, then any positive polynomial $f$ on $K$ belongs to the cone generated by $\{g_1, \dots, g_s\}$, i.e. sums with positive coefficients of products of the $g_i$'s (including powers) together with squares of arbitrary polynomials.

In your case, you have $g_1(x)=x$ and $g_2(x)=1-x$, and because you're in the one variable case, you should be able to get rid of the arbitrary squares (I might come back to this answer when I have more time).

1 K. Schmüdgen, The K-moment problem for compact semi-algebraic sets. Math. Ann. 289 (1991), no. 2, 203-206. (link)

Added Later: Note that Schmüdgen's result is only when $f|K>0$. If you relax to $f|K\geq 0$, it is not true any more. More surprisingly, Stengle points out in the MR that this result does not hold if you replace $\mathbb{R}$ by an arbitrary real closed field.

$\endgroup$
4
$\begingroup$

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.

enter image description here

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.

alt text

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.

alt text

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$.

$\endgroup$
4
  • 1
    $\begingroup$ How about $p(x)=(x-\frac12)^2+\epsilon$ where $\epsilon$ is very small? It is not representable with $i+j\le 2$ because the basis satisfies $p(1/2)\ge (f(0)+f(1))/4$ but $p$ does not. Moreover $i,j$ cannot be uniformly bounded as $\epsilon\to 0$, otherwise it would be possible to represent $(x-\frac12)^2$ as a limit. $\endgroup$ Sep 19, 2010 at 14:30
  • 3
    $\begingroup$ I don't follow this argument. When you replace x^k by x^n, how do you know the polynomial doesn't become negative somewhere. $\endgroup$ Sep 19, 2010 at 14:32
  • 1
    $\begingroup$ In particular the polynomial a(x-1/2)^2 + b is a counterexample to the lemma above if a/4+b=1, 0<b<1/4, as it is less than x^2 at x=1/2. $\endgroup$ Sep 19, 2010 at 14:52
  • 1
    $\begingroup$ The Mathematica command to produce the 3D figure, in case anyone wants to experiment e.g. with cubics: Show[ParametricPlot3D[ CoefficientList[ t (x - a)^2, x], {t, 0, 1}, {a, 0, 1}], Graphics3D[{Polygon[ {{0, 0, 0}, CoefficientList[x^2, x], CoefficientList[x (1 - x), x]}], Polygon[ {{0, 0, 0}, CoefficientList[(1 - x)^2, x], CoefficientList[x (1 - x), x]}], Polygon[ {{0, 0, 0}, CoefficientList[(1 - x)^2, x], CoefficientList[x (1 - x), x]}], Polygon[{{0, 0, 0}, CoefficientList[(1 - x)^2, x], CoefficientList[x^2, x]}]}], PlotRange -> All] $\endgroup$ Sep 19, 2010 at 15:48
2
$\begingroup$

As Vicki already pointed out above, Polya-Szegö (Problems and Theorems in Analysis II. Theory of Functions. Zeros. Polynomials. Determinants. Number Theory. Geometry.) is a good reference for this particular result.

See §6, Problem 49 in that book: By the Fundamental Theorem of Algebra you can restrict to quadratic polynomials. For lines it is trivial. For parabolas opening down it is easy. The only nontrivial case happens for parabolas opening up. Parabolas opening up whose minimum lies above the interval are also just a little exercise. The only case remaining is parabolas opening up without zero on the real line.

Now determine a polynomial $h \in \mathbb Z[K,L,A,B,C]_ 4$ such that for all $a,b,c\in\mathbb R$ and all $\ell\in\mathbb N_{\ge2}$ one has $$aX^2+bX+c=\sum_{k=0}^\ell\frac{(\ell-2)!}{k!(\ell-k)!}h(k,\ell,a,b,c)X^k(1-X)^{\ell-k}.$$

Show that each $f\in\mathbb R[X]_ 2$ with $f>0$ on $\mathbb R$ has the desired representation by comparing the discriminants of $f=aX^2+bX+c\in\mathbb R[X]_ 2$ and $h(K,\ell,a,b,c)\in\mathbb Z[K]_ 2$ for $a,b,c\in\mathbb R$ and large $\ell\in\mathbb N_{\ge2}$.

This approach unfortunately does not carry over for the numerous generalizations of the theorem.

$\endgroup$
2
$\begingroup$

On the segment $[0,\infty)$ the analogous statement reads as follows:

Theorem 1. If $f(x)>0$ for all $x\geqslant 0$, then for certain non-negative integer $m$ the polynomial $f(x)(1+x)^m$ has positive coefficients.

Proof. By Fundamental Theorem of Algebra, $f(x)=C\prod_i (x+a_i)\prod_j (x^2-2b_jx+c_j)$ for some $C>0$, $a_i>0$ and $c_j>b_j^2$. So it suffices to find such $m$ for a quadratic trinomial $x^2-2bx+c$, $c>b^2$. The positiveness of the coefficients reads as $${n\choose k-1}-2b{n\choose k}+c{n\choose k+1}>0, k=0,1,\ldots,n.$$ This is equivalent, after multiplying by $(k+1)!(n-k+1)!/n!$, to $$k(k+1)-2b(k+1)(n-k+1)+c(n-k)(n-k+1)>0.$$ This inequality is quadratic in $k$, with the leading coefficient $c+1-2b\geqslant 2\sqrt{c}-2b>0$ and the discriminant of the form $4n^2(b^2-c)+An+B$ which is negative for large $n$.

Note that the proof also suggests some bound for $m$ which suffices for sure in terms of quadratic factors of $f$.

Now we may reduce the finite interval to the infinite interval by a fractional linear change of variables.

Namely, if $p(x)>0$ for $x\in [0,1]$, and $\deg p=d$, then the polynomial $h(x)=p((1+x)^{-1})(1+x)^d$ is a positive for $x\geqslant 0$ polynomial of degree $d$, so by Theorem 1 we may find $m\in \mathbb{Z}_+$ for which $$p((1+x)^{-1})(1+x)^{d+m}=h(x)(1+x)^m=\sum_{k=0}^{d+m} c_k x^k, c_k>0.$$ It remains to substitute $x=(1-t)/t$.

Theorem 1 was proposed by Netherlands (namely by N. G. de Brujin) to IMO 1997, though I admit that it was known before.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.