# Proof of a lower bound of the norm of an arbitrary monic polynomial

In my course I have come across the following problem:

The Chebyshev polynomial of degree $n$, $T_n(x)$, is defined on $[-1,1]$ by $T_n(x)=\cos n\theta$.

Let $q_{n+1}(x)$ be any monic polynomial of degree $n+1$. Consider $2^n q_{n+1} - T_{n+1}$ to prove that $\|q_{n+1}\|\ge 2^{-n}$.

I have attempted to prove this in the following way:

$0\le \|2^n q_{n+1} -T_{n+1}\| \le \|2^n q_{n+1}\| - \|T_{n+1}\|$

$\implies \|T_{n+1}\|\le |2^n|\|q_{n+1}\|$

And using the fact that $\|T_{n+1}\| = 1 \space(*)$, we have:

$2^{-n}\le\|q_{n+1}\|$

Which was to be shown. However, I am not convinced by the step at $(*)$. I believe this is true for the infinity norm, but is it true for a norm in general? Are there any other steps in the proof that require more thought?

-
Some comments: First, the inequality $\|2^nq_{n+1} - T_{n+1}\|\leq \|2^nq_{n+1}\|-\|T_{n+1}\|$ seems highly suspect to me. Second, when you say "I believe this is true for the infinity norm, but is it true for a norm in general?", it makes it not so clear what norm you are using. So you should specify in the problem: what is $\|\cdot\|$? – froggie Dec 17 '12 at 21:56

I'll post the equivalent definitions of $T_n$ from Wikipedia for the benefit of other readers.

Definition. (Trigonometric.) $T_n$ is the unique polynomial so that $T_n(\cos{\theta})=\cos{n\theta}$, from which we can write $T_n(x)=\cos(n \cos^{-1}x).$

Definition. (Recurrence.) Equivalently, we can define $T_n$ through the following recurrence relation. $$\begin{eqnarray*}T_0(x)&=&1\\ T_1(x)&=&x \\ T_{n+1}(x)&=&2xT_n(x)-T_{n-1}(x)\end{eqnarray*}$$

So, I am assuming that you are using the supremum norm on $[1,1]$, $$\| f \|:=\sup_{x\in[1,1]}|f(x)|.$$ From the trigonometric definition, clearly $\| T_{n+1} \|=1$. It should also come as no surprise that $T_{n+1}$ achieves its extreme values at $x_k:=\cos{\frac{k\pi}{n+1}}$ for $k=0,\ldots, {n+1}$, at which the value of $T_{n+1}(x_k)$ alternates between $\pm 1$.

Now we are ready to do the problem. Note that I chose to do this with $q-2^{-n}T_{n+1}$, but the argument with $2^nq-T_{n+1}$ is identical.

Suppose that there exists a monic polynomial of degree $n+1$ so that $\| q \|<2^{-n}$.

From the recurrence relation definition, you can see that $T_{n+1}(x)$ is not monic; in fact, the coefficient of $x^{n+1}$ in $T_{n+1}(x)$ is $2^{n}$. So let's make $T_{n+1}$ monic by considering $2^{-n}T_{n+1}$.

Then $\left(q-2^{-n}T_{n+1}\right)(x)$ is a degree $n$ polynomial. However, since $\|q\|<2^{-n}<1$, we have that $\left(q-2^{-n}T_{n+1}\right)(x)$ still changes signs between each extreme point (the $x_k$ above) and thus must have $n+1$ zeros in $(-1,1)$. This is impossible unless $q-2^{-n}T_{n+1}=0$. But then $\|q\|=\|2^{-n}T_{n+1}\|=2^{-n}\|T_{n+1}\|=2^{-n}$, a contradiction.

-