Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 339 / 3

First address the positivity request in part (a), which has no separate Solution heading in the stub. For $x\in [0,1]$, each $x^k(1-x{)}^{n-k}$ and each coefficient $c_k$ is nonnegative. Their sum is therefore nonnegative, including at the endpoints:This is the elementary direction of the positive Bernstein coefficients for a strictly positive polynomial criterion; the converse developed later needs strict positivity.

For completeness, the convergence fact listed as (i) also has a short proof. If $K\sim \mathrm{Bin}(n,x)$, the Bernstein polynomial is $B_n(f)(x)=\mathbb{E}[f(K/n)]$. Its mean argument is $x$ and $\mathrm{Var}(K/n)=x(1-x)/n\le 1/(4n)$. Given $ϵ>0$, uniform continuity of $f$ on the compact interval supplies $\delta >0$ such that $|f(s)-f(t)|<ϵ$ whenever $|s-t|\le \delta$. By Chebyshev's inequality, uniformly in $x$,Letting $n\to \infty$ and then $ϵ\downarrow 0$ proves $\boxed{\Vert B_n(f)-f{\Vert }_{\infty }\to 0}$. The two numbered items in the source are assumptions supplied for later parts, not additional exam questions; their stub sections contain these supporting derivations.

Consider $B_n$ on the finite-dimensional vector space $E=\mathbb{R}[x{]}_{\le d}$ and use the monomial basis. For $j\ge 1$, a binomial distribution and the falling factorial moment formula givewhere $S(j,\ell )$ is the Stirling number of the second kind and $(n{)}_{\ell }=n(n-1)\cdots (n-\ell +1)$. This follows by expanding $K^j={\sum }_{\ell }S(j,\ell )(K{)}_{\ell }$ and using $\mathbb{E}(K{)}_{\ell }=(n{)}_{\ell }{x}^{\ell }$. Also $B_n(1)=1$.

Each monomial maps to a polynomial of no larger degree. The resulting matrix is triangular with diagonal entries $1$ and $(n{)}_j/n^j$, $1\le j\le d$. When $n\ge d$ and $n\ge 1$, all entries are positive. ThereforeFor constant polynomials the conclusion is immediate. Taking positive indices avoids the undefined sample expression $k/n$ at $n=0$.

Let $E=\mathbb{R}[x{]}_{\le d}$ with the supremum norm. By equivalence of norms in finite dimensions, there is $C_d$ such that ${\sum }_{j=0}^d|a_j|\le C_d\Vert p{\Vert }_{\infty }$ whenever $p={\sum }_j{a}_j{x}^j$. Henceso ${\epsilon }_n:=\Vert B_n-I{\Vert }_{\mathrm{op}}\le C_d{\max }_{0\le j\le d}\Vert B_n(x^j)-x^j{\Vert }_{\infty }\to 0$. This upgrades convergence on fixed polynomials to operator norm convergence on the fixed space.

For sufficiently large $n$, ${\epsilon }_n<1$, and a Neumann series givesThus the inverse Bernstein approximation on a fixed-degree polynomial space satisfies $\Vert g_n-f{\Vert }_{\infty }\to 0$. By the extreme value theorem, strict positivity on the compact interval gives $\mu ={\min }_{[0,1]}f>0$. Eventually $\Vert g_n-f{\Vert }_{\infty }<\mu /2$, and consequentlyApplying pointwise convergence to the varying polynomials $g_n$ without this finite-dimensional operator argument would not justify the conclusion.

Choose a sufficiently large positive $n$ for which $g_n=B_n^{-1}f>0$ throughout the interval. Expanding $B_n(g_n)=f$ givesTherefore the coefficientssupply the requested representation, in particular with nonnegative coefficients. This proves positive Bernstein coefficients for a strictly positive polynomial. Strict positivity cannot generally be weakened to mere nonnegativity: a nonzero polynomial such as $(x-1/2{)}^2$ vanishes at an interior point, whereas every basis term is positive there, so no nonnegative-coefficient representation could vanish unless every coefficient were zero.

Let $f(x)={\sum }_{j=0}^d{a}_j{x}^j$. For $n\ge \max (1,d)$, express $f$ in the Bernstein basis as $f={\sum }_{k=0}^n{\beta }_{k,n}{b}_{k,n}$, where $b_{k,n}=\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^k(1-x{)}^{n-k}$. Its precomputed coefficients arewith the ratio for $j=0$ interpreted as one. The identity follows from $x^j={\sum }_k[(k{)}_j/(n{)}_j]b_{k,n}$, obtained by the binomial theorem.

At this level solve the linear programThere are exactly $n+1$ inequalities. Equivalently, $f-\lambda$ must have nonnegative coefficients in the unnormalized basis; its coefficients are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)({\beta }_{k,n}-\lambda )$. Since the basis functions are nonnegative and sum to one, every feasible $\lambda$ satisfies $\lambda \le f(x)$ for all $x\in [0,1]$, so $v_n\le f_{\min }$.

Degree elevation of Bernstein coefficients gives, for $1\le k\le n$,with endpoint coefficients unchanged. These convex combinations imply $v_{n+1}\ge v_n$.

To cover every positive index even when $d>1$, put $\ell =a_0-{\sum }_{j=1}^d|a_j|$. For $1\le n<d$, use the one-inequality LP $\max \{\lambda :\lambda \le \ell \}$, giving $v_n=\ell$. This is a lower bound on $f$; moreover the explicit coefficient formula has all its factorial ratios in $[0,1]$, so ${\beta }_{k,d}\ge \ell$. Thus the transition to level $d$ is also monotone and every level respects the requested bound of at most $n+1$ inequalities. Constants are handled by the main formula at all positive indices.

Finally, for every $ϵ>0$, $f-(f_{\min }-ϵ)$ is strictly positive on the interval. Part (c) supplies a nonnegative-coefficient representation at some degree, and degree elevation preserves it at every higher degree. Hence eventually $v_n\ge f_{\min }-ϵ$. Combining with the upper bound proves the Bernstein linear programming hierarchy for polynomial minimization: