Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 69 / 3 / b / Solution

The Chebyshev alternation theorem states that $p\in {\mathcal{P}}_n$ is a best uniform approximation to real $f$ precisely when there are $n+2$ increasingly ordered points $x_0<\cdots <x_{n+1}$ withFor sufficiency, an improving polynomial direction $h$ would have to share these alternating signs, by the Kolmogorov criterion for uniform approximation. The intermediate value theorem would give at least $n+1$ distinct roots of a polynomial between consecutive points. A nonzero polynomial of degree at most $n$ cannot do that. If $E=0$, no improvement is possible anyway.

For necessity, suppose $E>0$ and the active set $M$ has no alternating sequence of length $n+2$. Its positive-error and negative-error subsets are disjoint compact sets, hence separated by a positive distance. Reading them from left to right splits $M$ into finitely many consecutive sign blocks. If there are $L$ blocks, choosing one point per block gives an alternating sequence, so $L\le n+1$. Choose $z_j$ in the gap between each consecutive pair of blocks. The polynomial $h(x)=C{\prod }_{j=1}^{L-1}(x-z_j)$ has degree at most $n$; choose the sign of $C$ to match the error on the first block. Its sign then matches the error on every block, and it is nonzero throughout $M$. Thus $rh>0$ on $M$, contradicting the Kolmogorov criterion for uniform approximation. There must therefore be $n+2$ alternating extrema.