Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 69 / 4

Let $u^{\ast }\in \mathcal{U}$, $e=f-u^{\ast }$, $d=\Vert e{\Vert }_{\infty }$, and $E=\{x:|e(x)|=d\}$. The real Kolmogorov criterion for uniform approximation says $u^{\ast }$ is best if and only ifEquivalently, no direction $v$ has the error's sign strictly at every extremal point. If $d=0$, the criterion is automatic.

For sufficiency, a point with $e(x)v(x)\le 0$ gives $|e(x)-v(x)|\ge d$, so $u^{\ast }+v$ cannot improve the norm. For necessity, suppose $e(x)v(x)>0$ on $E$. Compactness gives a positive lower bound there and on a neighbourhood of $E$. On that neighbourhood, $(e-\tau v{)}^2=e^2-2\tau ev+{\tau }^2{v}^2<d^2$ for sufficiently small positive $\tau$. Off the neighbourhood, $|e|$ has a strict gap below $d$, and small $\tau$ preserves that gap. Thus $u^{\ast }+\tau v$ has smaller error, a contradiction. This also explains why the criterion involves all active extrema.

Let $p\in {\mathcal{P}}_n$ and $e=f-p$, with $d=\Vert e{\Vert }_{\infty }>0$. The Chebyshev alternation theorem isIf such points exist and a polynomial $v\in {\mathcal{P}}_n$ had $e(x)v(x)>0$ at every extremum, its signs at those $n+2$ points would alternate. The intermediate value theorem would give at least $n+1$ distinct zeros, impossible for a nonzero degree-at-most-$n$ polynomial. The Kolmogorov criterion for uniform approximation therefore proves sufficiency.

For necessity, let $E_{+}=\{e=d\}$ and $E_{-}=\{e=-d\}$. They are disjoint compact sets. If one set is empty there is just one sign block. Otherwise their positive separation implies that, reading the extremal set from left to right, its signs form finitely many alternating blocks. If there are fewer than $n+2$ alternating extrema, there are at most $n+1$ blocks. Place one point ${\xi }_j$ in each extremum-free gap between consecutive blocks. A scalar multiple of $v(x)={\prod }_j(x-{\xi }_j)$ can be chosen to have exactly the sign of $e$ on every block. Its degree is at most $n$, and $ev>0$ throughout $E$, contradicting the Kolmogorov criterion for uniform approximation. Thus there must be at least $n+2$ alternating extrema. If $d=0$, the exact polynomial is already best and the equalities with zero error are automatic.

Fix the degree bound $n$. Existence can be proved without a general uniqueness theorem: a minimizing sequence in ${\mathcal{P}}_n$ is uniformly bounded because its distances from $f$ are bounded. Values at any fixed $n+1$ distinct points determine its coefficients through an invertible Vandermonde matrix, so those coefficients are bounded. A convergent subsequence supplies a polynomial attaining the minimum.

For uniqueness of best uniform polynomial approximation, suppose $p$ and $q$ attain the same minimum $d$, and let $r=(p+q)/2$. The triangle inequality makes $r$ another minimizer. If $d=0$, both polynomials equal $f$, so assume $d>0$. Put $e=f-r$ and $E=\{|e|=d\}$. At each $x\in E$, the two real errors $f-p$ and $f-q$ lie in $[-d,d]$ and their average equals an endpoint. Hence they are equal there, and $p(x)=q(x)$.

The set $E$ must contain at least $n+2$ points. Otherwise interpolate the values $\mathrm{sign}e(x)$ on its at most $n+1$ points by a polynomial $v\in {\mathcal{P}}_n$. Then $ev>0$ on $E$. Continuity gives this positivity on a neighbourhood of $E$, while the error has a strict gap below $d$ on the compact complement. A sufficiently small positive multiple of $v$ decreases the maximum error, contradicting optimality of $r$. This is an elementary perturbation argument, not an appeal to Haar's theorem.

Thus $p-q$ has at least $n+2$ distinct zeros. A polynomial of degree at most $n$ with that many zeros is identically zero. The best uniform polynomial is unique for every fixed degree bound: $\boxed{p=q}$.