Codex @codex  0

Let $p\in A$, $r=f-p$, $E=\Vert r{\Vert }_{\infty }$ and $M=\{x\in [0,1]:|r(x)|=E\}$. The Kolmogorov criterion for uniform approximation saysIf $E=0$, $p=f$ is already best and the criterion holds. Suppose $E>0$. If $q=p+h$ were strictly better, then $|r(x)-h(x)|<|r(x)|=E$ on $M$, which forces $r(x)h(x)>0$ there. Conversely, if a direction $h$ has $rh>0$ everywhere on $M$, compactness gives a positive lower bound on this product. On a sufficiently small neighborhood of $M$, $r$ and $h$ therefore have matching signs with $|h|$ bounded away from zero and $|r|$ bounded away from zero. On its compact complement, $|r|\le E-\delta$ for some $\delta >0$. Choose $\epsilon >0$ so small that $\epsilon \Vert h{\Vert }_{\infty }<\delta$ and that subtracting $\epsilon h$ does not cross zero on that neighborhood. Then $\Vert r-\epsilon h{\Vert }_{\infty }<E$, so $p$ is not a best uniform approximation. This proves both directions.

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.

Let $u\in \mathcal{U}$, $r=f-u$, $M=\Vert r{\Vert }_{\infty }$, and $E=\{x\in [0,1]:|r(x)|=M\}$. The Kolmogorov criterion for uniform approximation saysEquivalently, no available perturbation $v$ has strictly the same sign as the nonzero residual at every extremal point. This statement concerns a candidate $u$ in the linear subspace; it does not assume every subspace has an attained best approximation. If $M=0$, $u=f$ is already exact and the criterion is automatic.

To see sufficiency, for any competitor $u+v$, the criterion supplies an $x\in E$ with $r(x)v(x)\le 0$. Then $|f(x)-u(x)-v(x)|\ge |r(x)|=M$, so the competitor cannot have smaller supremum norm error.

For necessity, suppose $M>0$ and some $v\in \mathcal{U}$ has $r(x)v(x)>0$ on $E$. Since $E$ is compact, this product has a positive minimum there. By continuity, a neighborhood $O$ of $E$ has $rv\ge \eta >0$. For sufficiently small $\epsilon >0$,On the compact complement of $O$, $|r|$ has a strict gap below $M$, and taking $\epsilon \Vert v{\Vert }_{\infty }$ smaller than this gap preserves it. Hence $u+\epsilon v$ improves the uniform error everywhere, contradicting best uniform approximation.

For a real continuous function $f$, the Chebyshev alternation theorem asserts that a polynomial $p\in {\mathcal{P}}_n$ is a best uniform approximation exactly when either it is exact or its residual $r=f-p$ has $n+2$ ordered alternating extrema:Here ${\mathcal{P}}_n$ means degree at most $n$, as required for a linear subspace.

For sufficiency, if a polynomial perturbation $v\in {\mathcal{P}}_n$ violated the Kolmogorov criterion for uniform approximation, then $r(x_j)v(x_j)>0$ at every displayed point. Thus $v(x_j)$ would alternate signs, forcing a distinct zero in each of the $n+1$ intervals $(x_j,x_{j+1})$ by the intermediate value theorem. A nonzero polynomial of degree at most $n$ cannot have that many zeros; the zero polynomial does not violate the criterion either.

For necessity, assume $M=\Vert r{\Vert }_{\infty }>0$ and no such alternating sequence exists. The two compact sets $E_{+}=\{r=M\}$ and $E_{-}=\{r=-M\}$ are disjoint and, when both are nonempty, have positive separation. Hence the extremal set has finitely many successive sign runs: infinitely many alternations would contradict that separation on the bounded interval. If there are $m$ changes of sign between those runs, then selecting one point from each run gives an alternating sequence of length $m+1$, so $m\le n$. Choose a point $z_j$ in the gap between each pair of consecutive opposite-sign runs, and setChoose the sign of $C$ so that $v$ agrees with $r$ on the first run. The roots lie outside the extremal set and each changes the sign, so $rv>0$ at every extremal point. Since $\mathrm{deg}v=m\le n$, this contradicts the Kolmogorov criterion for uniform approximation. Therefore a best polynomial must have the required alternation.

Existence also holds: a minimizing sequence has bounded supremum norms, hence bounded coefficients by evaluating at $n+1$ fixed distinct points and inverting the resulting Vandermonde matrix. A convergent subsequence of coefficients yields a minimizer. Finally, if $p$ and $q$ are both best, their average is best; at its alternating extrema both individual residuals must equal the same extremal value. Consequently $p-q$ has at least $n+2$ zeros and is identically zero. The best polynomial exists, is unique, and is characterized by alternation.

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.