De la Vallée Poussin lower bound

Remarks

The idea of the proof: let $\mu$ be the minimum on the right and suppose some polynomial $q$ of degree at most $n$ has $\norm{f - q}_\infty < \mu$. At each $x_i$, the difference $q - p = (f - p) - (f - q)$ has the sign of $f(x_i) - p(x_i)$, because $\abs{f(x_i) - q(x_i)} < \mu \le \abs{f(x_i) - p(x_i)}$. So $q - p$ alternates in sign at $n + 2$ points and has at least $n + 1$ zeros, hence $q = p$. But then $\norm{f - q}_\infty \ge \mu$, a contradiction.

Example: for $f(x) = x^2$ on $[0, 1]$, $n = 1$ and $p(x) = x - 1/10$, the error $x^2 - x + 1/10$ takes the values $1/10, -3/20, 1/10$ at $0, 1/2, 1$. So $E_1(f) \ge 1/10$, while $\norm{f - p}_\infty = 3/20$ gives $E_1(f) \le 3/20$; the true value is $1/8$.

The number of points matters: with only $n + 1$ alternation points no lower bound follows. For $f(x) = x$, $n = 1$ and $p = 1/2$, the error $x - 1/2$ takes the values $-1/2, 1/2$ at $0, 1$, but $E_1(f) = 0$.

Going deeper

For a student

The bound is the easy half of the equioscillation theorem: when all the alternating values equal $\norm{f - p}_\infty$, it shows $p$ is best. In the Remez algorithm it certifies progress, since each iteration produces a polynomial and a set of $n + 2$ alternation points, and the lower and upper bounds squeeze $E_n(f)$. The same argument works for any Haar subspace of dimension $n + 1$.