 Alternating-reference error bound

Let a polynomial $q$ of degree at most $n$ have errors $f(x_j)-q(x_j)=(-1{)}^{j}h$ at $n+2$ ordered distinct points. Then $|h|$ bounds below the error $E_n(f)$ of the best uniform approximation. Otherwise an improved polynomial $p$ with error strictly below $|h|$ would make $p-q$ alternate strictly in sign at all those points, giving at least $n+1$ distinct roots of a polynomial by the intermediate value theorem. Its degree is at most $n$, a contradiction. Moreover, if $q$ is not optimal, $|h|<E_n(f)$. In the equality case, an optimal $p$ gives weak alternating signs of $p-q$; its vanishing order-$(n+1)$ divided difference has same-sign summands, forcing every nodal value to vanish and hence $p=q$.