Uniqueness of minimal $\infty$-norm polynomial

Question

From this proof it is clear to me that Chebyshev polynomial $\frac{1}{2^{n-1}} T_n(x)$ is minimum $\infty$-norm in $[-1,1]$ among the monic polynomials of degree $n$.

How to prove the uniqueness (if true) of such minimizing polynomial? I found this question, but the answer is not completely related. I have no idea to start.

Answer 1

Let $P$ be a polynomial with degree at most $n-1$ such that $\|2^{1-n}T_n+P\|_{\infty} \leq 2^{1-n}$.

For every $0 \leq k \leq n$, define $t_k=\cos{\frac{k\pi}{n}}$. Then $t_0 > t_1 > \ldots > t_n$ and $T_n(t_k)=(-1)^k$.

Therefore, for each $0 \leq k \leq n$, $\left|2^{1-n}(-1)^k+P(t_k)\right|=|2^{1-n}+(-1)^kP(t_k)| \leq 2^{1-n}$.

As a consequence, for all $0 \leq k \leq n$, $(-1)^kP(t_k) \leq 0$.

We want to show that this implies that $P=0$.

Define, for all even $0 \leq k \leq n-2$, $m_k$ to be a local maximum of $P$ in $(t_k,t_{k+2})$ (so $P(m_k) \geq P(t_{k+1}) \geq 0$, $P’(m_k)=0$); define, for all odd $0 \leq k \leq n-2$, $m_k$ to be a local minimum of $P$ in $(t_k,t_{k+2})$ (similarly, $P(m_k) \leq P(t_{k+1}) \leq 0$).

The $m_k$ are by construction pairwise distinct, they are $n-1$ zeroes of $P’$, but $\deg{P’} \leq n-2$. So $P’=0$, so $P=0$ (else there are no sign changes).

Answer 2

Suppose there existed a second minimizing polynomial $g$. Then, since $\frac{1}{2}|f(x)+g(x)| \leq \max(|f(x)|,|g(x)|) \leq \lVert f \rVert_\infty = \lVert g \rVert_\infty$, the mean $\frac{f+g}{2}$ minimizes the $\infty$-norm as well. Now, by the equioscillation theorem, there exist $\xi_0, \dots, \xi_n$ such that $|(\frac{f+g}{2})(\xi_k)| = \lVert \frac{f+g}{2} \rVert_\infty$. Since $\lVert f \rVert_\infty = \lVert g \rVert_\infty = \lVert \frac{f+g}{2} \rVert_\infty$, this implies that $f(\xi_k) = g(\xi_k)$, thus $f$ and $g$ agree on $n+1$ points, hence $f=g$.

Let's prove the variant of the equioscillation theorem applied above, by contradiction. Suppose that $f$ is monic, minimizes $\lVert f \rVert_\infty=:M$ and $|f(z)| < \lVert f \rVert_\infty$ everywhere except maybe at $n$ points $\zeta_1,\dots,\zeta_n$. Let $g(x) = (x-\zeta_1)\dots(x-\zeta_n)$, and $\epsilon$ be such that $|g(x)| < \frac{M}{2}$ whenever $x \in \bigcup_{k=1}^n (\zeta_k-\epsilon,\zeta_k+\epsilon) =: O$ for some $k$. By compactness of $[-1,1]\setminus O$, we know that $|f(x)|\leq M-\kappa$ outside of $O$, therefore there exists $\delta \in (0,1)$ such that $|(1-\delta)f(x)+\delta g(x)| < M$ for all $x \in [-1,1]\setminus O$. For $x \in O$, we have that $|(1-\delta)f(x)+\delta g(x)| < (1-\delta)M + \delta \frac{M}{2} < M$. Again by compactness, $(1-\delta)f(x)+\delta g(x)$ is a monic polynomial with $\lVert (1-\delta)f(x)+\delta g(x) \rVert_\infty < M$, contradiction.