= 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}$ with
$$
f(x_i)-p(x_i)=\eta(-1)^iE,\qquad \eta\in\{-1,1\},\quad E=\|f-p\|_\infty.
$$
For 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.
Back to article page
