Kolmogorov criterion for best approximation

Remarks

The idea of the proof: suppose some $p \in V$ has $(f - p^*) p > 0$ on $E$. By compactness this product is positive on an open set $U \supseteq E$, and $\abs{f - p^*}$ stays below $\norm{f - p^*} - \eta$ for some $\eta > 0$ off $U$. Then $\norm{f - p^* - t p} < \norm{f - p^*}$ for small $t > 0$, so $p^*$ is not best. Conversely, if $q \in V$ has $\norm{f - q} < \norm{f - p^*}$, then $p = q - p^*$ satisfies $(f - p^*) p = (f - p^*)^2 - (f - p^*)(f - q) > 0$ on $E$.

Example: for $f(x) = x^2$ on $[0, 1]$, $V$ the lines and $p^*(x) = x - 1/8$, the set $E$ is $\set{0, 1/2, 1}$ with error signs $+, -, +$. A line $p$ with $p(0) > 0$, $p(1/2) < 0$ and $p(1) > 0$ would have two zeros, so it does not exist, and the criterion shows $p^*$ is best.

For complex-valued functions the same criterion holds with $\operatorname{Re} \big( \overline{(f(x) - p^*(x))} \, p(x) \big)$ in place of the product.

Going deeper

For a student

The criterion holds for every linear subspace, not only for polynomials or Haar subspaces. For Haar subspaces it turns into the alternation property of the equioscillation theorem, because a function of a Haar subspace can follow any sign pattern with few sign changes. It is a form of the first-order optimality condition for the convex function $p \mapsto \norm{f - p}$. Similar criteria hold in other normed spaces with the norm's subdifferential in place of the product.