5
$\begingroup$

In the book Proofs from The Book by Aigner and Ziegler there is a proof of 'Chebyshev's Theorem' which states that if $p(x)$ is a real polynomial of degree n with leading coefficient $1$ then

$$ \max_{-1 \leq x \leq 1} |p(x)| \geq \frac{1}{2^{n-1}}$$

In the proof $g( \theta ) = p( \cos \theta )$ is written as a cosine polynomial $ \sum_{k=0}^n \lambda_k \cos(k \theta)$ and it is then proved that this can't be less than $|\lambda_n|$ (which happens to be $\frac{1}{2^{n-1}}$) everywhere.

Afterwards it is claimed that 'The reader can easily complete the analysis' to show that the Chebyshev polynomials are the only ones for which equality occurs in the above inequality. I haven't been able to figure this out. Can someone explain why this is true? (preferably building on the proof as it was done in the book or by some other simple argument.)

edit: here by Chebyshev polynomial I actually mean the monic polynomial that you get after dividing the $n$-th Chebyshev polynomial by $2^{n-1}$.

$\endgroup$
4
$\begingroup$

Let $p(x)$ be a monic polynomial of degree $n$. Let $T_n(x)$ be the Chebyshev polynomial of degree $n$. Assume that $|p(x)|\leq 1/2^{n-1}$ for all $x\in[-1,1]$.

Set $q(x)=T_n(x)-p(x)$. Then since $T_n$ and $p$ are both monic polynomials of degree $n$, $q$ is a polynomial of degree at most $n-1$.

Now let $x_k=\cos(k\pi/n)$ for $k=0, 1, \ldots, n$. At these points $T_n(x_k)=(-1)^k/2^{n-1}$ by $T_n$'s definition. Now $$q(x_k)=T_n(x_k)-p(x_k)=(-1)^k/2^{n-1}-p(x_k)$$

But $|p(x_k)|\leq 1/2^{n-1}$ for each $k=0, 1,\ldots, n$. So that $q(x_k)\leq 0$ when $k$ is odd and $q(x_k)\geq 0$ when $k$ is even.

The Intermediate Value theorem implies that for each $k=0, 1,\ldots, n-1$ the polynomial $q(x)$ has at least one zero between $x_k$ and $x_{k+1}$. Thus $q(x)$ has at least $n$ zeros in the interval $[-1,1]$. But the degree of $q$ is less than $n$. Thus $q$ is equivalently $0$. Thus $T_n=p$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This is quite similar to how the inequality was proved in the book, but I see a problem here. You proved that $q$ has at least one zero in each of the intervals $ [ x_1 , x_0 ] , [x_2, x_1 ] , \dots , [ x_{n} , x_{n-1} ]$. But some of those zeros mights coincide, giving us a total of less than $n$ zeros. (e.g. if $x_1$ is a zero then it lies in both of the first two intervals.) $\endgroup$ – Brusko651 Oct 11 '14 at 13:06
  • $\begingroup$ That's a pointed observation. I'm trying to account for it. $\endgroup$ – Robert Wolfe Oct 11 '14 at 16:55
4
+50
$\begingroup$

An alternative proof works by interpolation (it can also be formulated using divided differences) and the case of equality can be handled more easily.

Let $M=\max\limits_{[-1,1]}p$.

It is well-known that for every polynomial $f(x)$ with degree at most $n$, and any $n+1$ distinct base points $a_0,a_1,\ldots,a_n$, the divided difference $$ f[a_0,a_1,\dots,a_n] = \sum_{k=0}^n \frac{f(a_k)}{\displaystyle\prod_{j\ne k}(a_k-a_j)} $$ is equal to the coefficient of $x^n$ in $f$. (Just read the coefficient of $x^n$ in Lagrange's interpolation formula.)

Define the base points $a_0,a_1,\dots,a_n$ by $a_k=\cos\frac{\pi k}{n}$. As $p$ is monic, we have $p[a_0,a_1,\dots,a_n]=1$ and similarly, since the leading coefficient in $T_n$ is $2^{n-1}$, we have $T_n[a_0,a_1,\dots,a_n]=2^{n-1}$. By the definition of the base points, $T_n(a_k)=(-1)^k$. The product $\displaystyle\prod_{j\ne k}(a_k-a_j)$ is positive if $k$ is even and negative if $k$ is odd. Hence, $$ 1 = p[a_0,a_1,\dots,a_n] = \sum_{k=0}^n \frac{p(a_k)}{\displaystyle\prod_{j\ne k}(a_k-a_j)} \le \sum_{k=0}^n \frac{\big|p(a_k)\big|}{\bigg|\displaystyle\prod_{j\ne k}(a_k-a_j)\bigg|} \le \sum_{k=0}^n \frac{M}{\displaystyle\bigg|\prod_{j\ne k}(a_k-a_j)\bigg|} \\ = M \sum_{k=0}^n \frac{(-1)^k}{\displaystyle\prod_{j\ne k}(a_k-a_j)} = M \sum_{k=0}^n \frac{T_n(a_k)}{\displaystyle\prod_{j\ne k}(a_k-a_j)} = M \cdot T_n[a_0,a_1,\dots,a_n]=M\cdot 2^{n-1}. $$ This proves $M\ge2^{-(n-1)}$. To establish equality you require $p(a_k)=(-1)^kM$ for every $k$; that determines the polynomial $p$ uniquely.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Starting from the function $$ p(\cos \theta) = g(\theta) = \sum_{k=0}^n \lambda_k \cos (k\theta), $$ like in the orginal approach, a discrete variant of Parseval's formula works, too.

Again, let $M=\max |g(\theta)|=\max\limits_{[-1,1]} |p(x)|$.

For every integer $m$, it is easy to verify that $$ S_m := \frac1{2n} \sum_{j=0}^{2n-1} \cos\frac{jm\pi}{n} = \begin{cases} 1 & 2n \,\, \text{divides}\,\, m \\ 0 & \text{otherwise.} \end{cases} $$

Then \begin{align*} M^2 &\ge \frac1{2n} \sum_{j=0}^{2n-1} \left| g\bigg(\frac{j\pi}{n}\bigg)\right|^2 \\ &= \frac1{2n} \sum_{j=0}^{2n-1} \left(\sum_{k=0}^n \lambda_k \cos \frac{jk\pi}{n} \right) \left(\sum_{\ell=0}^n \overline{\lambda_\ell} \cos \frac{j\ell\pi}{n} \right) \\ &= \sum_{k=0}^n \sum_{\ell=0}^n \lambda_k \overline{\lambda_\ell} \cdot \frac1{2n} \sum_{j=0}^{2n-1} \cos \frac{jk\pi}{n} \cos \frac{j\ell\pi}{n} \\ &= \sum_{k=0}^n \sum_{\ell=0}^n \lambda_k \overline{\lambda_\ell} \cdot \frac1{2n} \sum_{j=0}^{2n-1} \frac{\cos \frac{j(k+\ell)\pi}{n} +\cos \frac{j(k-\ell)\pi}{n}}{2} \\ &= \sum_{k=0}^n \sum_{\ell=0}^n \lambda_k \overline{\lambda_\ell} \frac{S_{k+\ell}+S_{k-\ell}}2. \end{align*} Since $0\le k,\ell\le n$, $2n$ divides $k+\ell$ if and only if $k=\ell=0$ or $k=\ell=n$, and $2n$ divides $k-\ell$ if and only if $k=\ell$. So, $$ M^2 \ge \sum_{k=0}^n \sum_{\ell=0}^n \lambda_k \overline{\lambda_\ell} \frac{S_{k+\ell}+S_{k-\ell}}2 = |\lambda_n|^2 + |\lambda_0|^2 +\sum_{k=1}^{n-1}\frac{|\lambda_k|^2}2. $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The first equation "$S_m = 1$ if ..." doesn't seem quite correct to me. Is it possible that it should be $2 \pi$ instead of $\pi$? $\endgroup$ – Brusko651 Oct 18 '14 at 13:34
  • $\begingroup$ Yes, you are right. I will fix it. $\endgroup$ – user141614 Oct 18 '14 at 14:08
  • $\begingroup$ Hope it is better now.. :-) We have to take the values of $g$ where the leading term $\cos (n\theta)$ is $\pm1$. $\endgroup$ – user141614 Oct 18 '14 at 14:12
  • $\begingroup$ Alright. Thank you very much for both of your answers! Both proofs are very interesting for me. $\endgroup$ – Brusko651 Oct 18 '14 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.