# Prove that the normalized Chebyshev polynomials are the best approximation to zero in $[-1,1]$

This is the exercise 13 of Analysis I of Amann and Escher, page 349.

Define the normalized Tchebyshev polynomials by $\tilde T_n:=T_n/2^{n-1}$ and $\tilde T_0:=T_0$. Let $\mathcal P_n\subset\Bbb R[X]$ for $n\in\Bbb N_{\ge 0}$ such that if $p\in\mathcal P_n$ then $\deg(p)=n$ and $[x^n]p(x)=1$. Prove that the $\tilde T_n$ is the best approximation of zero in $\mathcal P_n$ in $[-1,1]$, that is $$\|\tilde T_n\|_\infty\le \|p\|_\infty,\quad p\in\mathcal P_n$$

This exercise is killing me. Previous known facts:

• $T_n(x)=\cos(n\arccos x)=\sum_{k\ge 0}\binom{n}{2k}x^{n-2k}(x^2-1)^k$.

• $T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)$.

• The local extrema of $T_n$ are attained at $y_k:=\cos\frac{k\pi}{n}$ for $k=0,1,\ldots,n$, i.e. $T_n(y_k)=(-1)^k$.

• The zeros of $T_n$ are $x_k:=\cos\frac{(2k-1)\pi}{2n}$ for $k=1,2,\ldots,n$.

• If we define $\tilde T_n(x):=\sum_{k=0}^n a_kx^k$ then $a_n=1$.

• From above we have the identity $\tilde T_n(x)=\prod_{k=1}^{n}(x-x_k)$.

From all of this we know that $\|\tilde T_n\|_\infty=1/2^{n-1}$. But I dont know exactly where start or what to do to prove the statement of the exercise.

I tried to start proving that for each $p\in\mathcal P_n$ with some zero it must exists some $x_0\in[-1,1]$ such that $|p(x_0)|=1/2^{n-1}$ (but now Im not sure that this deduction was correct or useful).

I tried induction over $n$ for polynomials in $p_n\in\mathcal P_n$, writing something like $p_{n+1}=xp_n+c$, but I dont get something useful.

The exercise comes after some theory about Taylor theorem and some polynomial approximation based in Newton/Lagrange polynomials (there is no theory in the book, by now, related to integration). But trying to relate the exercise to the theory was fruitless.

Some hint (or solution) will be appreciated.

UPDATE: I think I get the way to do, but the proof below is not (by now) totally correct.

We knows that $\|\tilde T_n\|_\infty=1/2^{n-1}$, so the statement to prove must be re-written as

$$\frac1{2^{n-1}}\le \|p\|_\infty,\quad \forall p\in\mathcal P_n$$

Now define $p_n:=p$ for any $p\in\mathcal P_n$, i.e. the degree of $p_n$ is $n$. I define too $p_n(0):=c_n$. Then if $|c_n|\ge\frac1{2^{n-1}}$ we are done.

Then suppose that $|c_n|<\frac1{2^{n-1}}$. Now we prove by induction:

1. Base case: $\|p_1\|_\infty=\|x+c_1\|\ge 1$ for $x\in[-1,1]$.

2. Induction hypothesis: assume that $\|p_n\|_\infty\ge 1/2^{n-1}$.

3. Induction step: first observe that $p_{n+1}=xp_n+c_{n+1}$ for some $p_n$, then we want to prove that $$\|p_{n+1}\|_\infty=\|xp_n+c_{n+1}\|_\infty\ge1/2^n$$

Then

$$\|xp_n\|+|c_{n+1}|\ge\|xp_n+c_{n+1}\|_\infty\ge\big|\|xp_n\|_\infty-|c_{n+1}|\big|\ge\ldots \text{(working around)}$$

The version of your solution before your edit (that just occurred) was correct if you know that $x_0$, which was the largest $x$ such that $|p_n(x)|=\|p_n\|$ is $x_0=1$.

Proof that $|p_n(1)|=\|p_n\|$: Suppose instead that $|p_n(1)|<\|p_n\|.$

Let $|p_n(1)|< (1-s)\|p_n\|$ with $0<s<1.$ For some (sufficiently small) $r>0$ such that $(1+r/2)^n(1-s)=1-t$ ( with $0<t<1$) we have $$\forall x\in [1,1+r]\;(|p_n(x)|< (1-s)\|p_n\|).$$ Let $q_n(x)=(1+r/2)^{-n}p_n(y)$ where $y=(2+r)(x+1)/2-1.$

We have $x\in [-1,1]\iff y\in [-1,1+r].$ Then deg$(q_n)=n$. The leading coefficient of $q_n$ is $1.$ But $$\{|q_n(x)|:|x|\leq 1\}=\{|(1+r/2)^n p_n(y)|: y\in [-1,1+r]\} \subset [-(1-t)\|p_n|,(1-t)\|p_n\|]$$ implying $\|q_n\|<\|p_n\|,$ contradicting the minimality of $\|p_n\|.$

I only know this part because I worked on this problem once. Your inductive step was the one piece I couldn't find. You really should have written $x_n$ for $x_0$ in your earlier version.... I have read that there is a deeper theorem of Chebyshev, that if $P(n)$ is the set of polynomials of degree $\leq n,$ then for any $f\in C[-1,1]$ there is a unique $p\in P_n$ that minimizes $\{\|f-q\|_{\infty}:q\in P(n)\}.$ The uniqueness is the hard part, as closures of non-empty open balls in this norm are not strictly convex . (I.e. there are linearly independent $g,h\in C[-1,1]$ with $\|g\|=\|h\|=\|(g+h)/2\|$.)

• The statement that $|p_n(1)|=\|p_n\|_\infty$ is not correct. By example take $p_1(x):=x-\epsilon$ for some $\epsilon>0$, then in this case $\|p_1\|_\infty=|p_1(-1)|$. But I think that we can prove by induction that $\|p_n\|=\max\{|p_n(-1)|,|p_n(1)|\}$. Jan 16, 2017 at 5:09
• Indeed it is neither true that $\|p_n\|_\infty=\max\{|p_n(1)|,|p_n(-1)|\}$, by example build some $p_3(x)=(x-1)(x+1)(x-\alpha)$. Jan 17, 2017 at 2:13
• @Masacroso. ???? What do you think $p_1$ is? Jan 17, 2017 at 3:01
• Well. I know what is $p_n$ because is my notation. Maybe you are defining something different than me with the same notation, what make this a lot confusing. Jan 17, 2017 at 3:38
• I thought that $p_n$ was a normalized polynomial of degree $n$ of smallest possible norm. Jan 17, 2017 at 3:48

I found a very elegant proof of this (old) question. I can see now what @DanielWainfleet was trying to show me.

We knows that $\|\tilde T_n\|_\infty=1/2^{n-1}$, so the statement to prove can be re-written as $$\frac1{2^{n-1}}\le \|p\|_\infty,\quad \forall p\in\mathcal P_n$$ Let $p\in\mathcal P_n$ and suppose that $\|p\|_\infty <\frac1{2^{n-1}}$, then because $T_n(y_k)=(-1)^k$ for $y_k$ defined as in the previous exercise for $k=0,1,\ldots,n$ we find that $g:=p-\tilde T_n$ belongs to $\mathcal P_{n-1}$ and $\operatorname{sign}(g(x_k))=(-1)^k$ for $k=0,1,\ldots,n$. Then $g$ changes of sign $n+1$ times so it must have $n$ distinct roots. However $\deg(g)=n-1$ so it is not possible that it have $n$ distinct roots. This shows that necessarily $\|p\|_\infty\ge\frac1{2^{n-1}}$, as desired.

\emph{Proof.} Per previous discussion we know that the coefficient of the highest degree term of $$T_{n}(x)$$ is $$2^{n-1}$$, so to make it monic, we define $$\tilde{T}_{n}(x)=\frac{1}{2^{n-1}}T_{n}(x)$$

Also we know that $$\max_{x\in[-1,1]}|T_{n}(x)|=1$$, then $$\max_{x\in[-1,1]}|\tilde{T}_{n}(x)|=\frac{1}{2^{n-1}}$$ So we only need to prove that for any (monic) polynomial of degree $$n$$ ($$P\in\mathcal{P}_{n}$$), $$\max_{x\in[-1,1]}|P_{n}(x)|\ge\frac{1}{2^{n-1}}$$

Try to use mathematical induction. At $$n=1$$, the polynomials must be in form $$P_{1}(x)=x+a$$. It is a straight line with no internal extremum; on interval $$[-1,1]$$, \begin{align*} P_{1}(-1)=-1+a=a-1\\ P_{1}(1)=1+a=a+1 \end{align*} Obviously, $$a>0\Rightarrow a+1>1$$, $$a<0\Rightarrow a-1<-1$$, so to let $$\max\{|a-1|,|a+1|\}$$ be the minimal, it is imperative to have $$a=0$$, which leads to $$P_{1}(x)=x$$, and $$\min\max|P_{1}(x)|=1=2^{1-1}$$.\

At $$n=2$$, we have $$P_{2}(x)=x^{2}+ax+b$$, which can always be written as $$P_{2}(x)=(x-p)^{2}+q$$. At $$x=p$$, $$P_{2}(x)$$ has minimal value $$q$$. Similar to the case of $$P_{1}(x)$$, To keep $$(x-p)^{2}$$ be minimal on $$[-1,1]$$, it is imperative that $$p=0$$: $$\begin{cases} p>0\Rightarrow -1-p<-1\\ p<0\Rightarrow 1+p>1 \end{cases}$$ At $$p=0$$, we have $$P_{2}(x)=x^{2}+q$$, so $$P_{2}(-1)=P_{2}(1)=1+q$$, while the internal extremum is $$P_{2}(0)=q$$. so $$\begin{cases} q>-\frac{1}{2}\Rightarrow 1+q>\frac{1}{2}\\ q<-\frac{1}{2}\Rightarrow |q|>\frac{1}{2} \end{cases}$$

Therefore we have returned to $$P_{2}(x)=\tilde{T}_{n}(x)=x-\frac{1}{2}$$ and $$\min\max|P_{2}(x)|=\frac{1}{2}$$.

Now assume this is correct up to $$P_{k}$$, ie, $$\min\max|P_{k}(x)|=\frac{1}{2^{k-1}}$$

At $$k+1$$, assume we have $$P_{k+1}(x)$$ such that $$\min\max|P_{k+1}(x)|<\frac{1}{2^{k}}$$ then consider polynomial $$g(x)=P_{k+1}(x)-\tilde{T}_{k+1}(x)$$

Since both $$P_{k+1}(x)$$ and $$\tilde{T}_{n+1}(x)$$ are monic, the highest degree term canceled, so $$\deg(g(x))=k$$ and \begin{align*} \min\max|g(x)|\le&\min\max|P_{k+1}(x)|+\min\max|T_{k+1}(x)|\\ <&\frac{1}{2^{k}}+\frac{1}{2^{k}}=\frac{2}{2^{k}}=\frac{1}{2^{k-1}} \end{align*}

Which contradicts the assumption that $$\min\max|P_{k}(x)|\ge\frac{1}{2^{k-1}}$$.Q.E.D.