find the polynomial $p(x) = x^2+px+q$ for which $\max|p(x)| $ is minimum

Question

Find the polynomial $p(x) = x^2+px+q$ for which $\max_{x\in[-1,1]}|p(x)| $ is minimum.

By trail and error I got $p(x)=x^2-\frac12$

Answer 1

Note that $p(x)=x^2-\frac12$ leads to $\max_{x\in[-1,1]}|p(x)|=\frac12$. It suffices to show that $\max_{x\in[-1,1]}|p(x)|>\frac12$ for all ther candidate polynomials.

Note that $|a|=\max\{-a,a\}$ implies $$\begin{align}\frac{|p(1)|+|p(-1)|}2&=\frac{|1+p+q|+|1-p+q|}2\\&=\frac12\max\{|(1+p+q)+(1-p+q)|, |(1+p+q)-(1-p+q)|\}\\&=\max\{|1+q|,|p|\}\end{align}$$ so that $$ \max_{x\in[-1,1]}|p(x)|\ge\max\{|p(-1)|,|p(1)|\}\ge \frac{|p(1)|+|p(-1)|}2\ge \max\{|1+q|,|p|\}.$$ Thus we need only consider $$|p|\le\frac12\qquad \text{and}\qquad -\frac32\le q\le-\frac12.$$ For such $p$, we have $-2p\in[-1,1]$, hence $$ \max_{x\in[-1,1]}|p(x)|\ge |p(-2p)|=|2p^2+q|\ge 2p^2-q\ge\frac12$$ where the last step turns into "$>$" if $q<-\frac12$ or if $p\ne0$. Therefore, $$ \max_{x\in[-1,1]}|p(x)|\ge \frac12\qquad\text{with equality iff }p=0, q=-\frac12.$$

Answer 2

Once you find a polynomial $p$ that differs by at most $\delta$ and the difference $\delta$ is achieved at three points $x_1$, $x_2$, $x_3$, with alternating signs then this is the optimal polynomial, and it is unique. Since if you have another one $q$ with error at most $\delta$, then at points $x_1$, $x_2$, $x_3$, $p-q$ has alternating signs. That implies $p-q$ has at least $2$ zeroes, so it is the $0$ polynomial. This works in general, with the easy lemma that polynomials with alternating values at $n+1$ points have at least $n$ zeroes.