Intereting Posts

How prove this $S_{\Delta ABC}\ge\frac{3\sqrt{3}}{4\pi}$
Orders of subgroups of Infinite Profinite Groups
What is the order when doing $x^{y^z}$ and why?
First axiom of sheaves: in noetherian topological spaces the direct limit presheaf is a sheaf.
Calculating the max and min of $\sin(x)+\sin(y)+\sin(z)$
Axes of Symmetry for a General Ellipse
An example of a regular function over an open set
Prove that every number between two factors of primes is composite.
Why do engineers use the Z-transform and mathematicians use generating functions?
What is the connection between linear algebra and geometry?
Prove that there is exactly one perpendicular line
Proof negation in Gentzen system
Is a morphism between schemes of finite type over a field closed if it induces a closed map between varieties?
Nature of the series $\sum\limits_{n}(g_n/p_n)^\alpha$ with $(p_n)$ primes and $(g_n)$ prime gaps
What is limit of $\sum \limits_{n=0}^{\infty}\frac{1}{(2n)!} $?

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.

- How to get from Chebyshev to Ihara?
- Extending a Chebyshev-polynomial determinant identity
- How to best approximate higher-degree polynomial in space of lower-degree polynomials?
- First kind Chebyshev polynomial to Monomials
- Prove that there exist a constant $c$ such that all the roots of $P(x)+c.T_n(x)$ are real

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}$.

- If $F$ be a field, then $F$ is a principal ideal domain. Does $F$ have to be necessarily a field?
- How to best approximate higher-degree polynomial in space of lower-degree polynomials?
- Convert segment of parabola to quadratic bezier curve
- $f,g,h$ are polynomials. Show that…
- Show $x^6 + 1.5x^5 + 3x - 4.5$ is irreducible in $\mathbb Q$.
- Test for an Integer Solution
- Factorizing a polynomial $f$ in $A$ (with $A$ commutative), where $f$ has a zero in its field of fractions
- If $f(x)=x^2-x-1$ and $f^n(x)=f(f(\cdots f(x)\cdots))$, find all $x$ for which $f^{3n}(x)$ converges.
- What is a real world application of polynomial factoring?
- Is a polynomial $f$ zero at $(a_1,\ldots,a_n)$ iff $f$ lies in the ideal $(X_1-a_1,\ldots,X_n-a_n)$?

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$.

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.

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.

$$

- How can I prove this relation between the elementary set theory and the elementary logic?
- What is meant by parameter in this context?
- Integrating $\frac{x dx}{\sin x+\cos x}$
- In simple English, what does it mean to be transcendental?
- Does the series $\sum_{n=1}^{\infty}\frac{\sin(\cos(n))}{n}$ converge?
- If $f$ is continuous & $\lim_{|x|\to {\infty}}f(x)=0$ then $f$ is uniformly continuous or NOT?
- Coset representatives for $\mathcal{O}_K/(\alpha)$.
- Easier proof about suspension of a manifold
- The application of Nimbers to Nim strategy
- Volumes of cones, spheres, and cylinders
- Are there statements that are undecidable but not provably undecidable
- Completeness of the Natural Numbers
- What is a geometric explanation of complex integration in plain English?
- Prove that if $f$ is a real continuous function such that $|f|\le 1$ then $|\int_{|z|=1} f(z)dz| \le 4$
- Factoring with fractional exponents