Is there an intuitive explanation for an extremal property of Chebyshev polynomials?

Question

Consider the following optimization problem:

Problem: find a monic polynomial $p(x)$ of degree $n$ which minimizes $\max_{x \in [-1,1]} |p(x)|$.

The solution is given by Chebyshev polynomials:

Theorem: Let $T_n(x) = \cos (n \cdot \cos^{-1} x)$. Then $(1/2^{n-1}) T_n$ is a monic polynomial of degree $n$ which achieves the above minimum.

The proof of this fact is short and surprisingly free of messy calculations. From the definition of $T_n$ you derive a recurrence relation expressing $T_n$ in terms of $T_{n-1}, T_{n-2}$, which shows that $T_n$ are indeed polynomials. Then you argue that $(1/2^{n-1}) T_n$ is monic and achieves its extrema $\pm 1/2^{n-1}$ at least $n+1$ times in $[-1,1]$, from which the above theorem easily follows. If you'd like a nice exposition of this argument which does not skip any steps, this is short and clear.

However, I don't get much enlightenment from this proof: it feels pulled out of a hat. For example, it gives me no clue about which other polynomial optimization problems have similar solutions.

My question: Is there a natural and motivated sequence of steps which, starting from the above optimization problem, leads to Chebyshev polynomials?

Update: I changed the title to better reflect the question I am asking.

Answer 1

Well, let's try to avoid the hat.

Consider the dual (and obviously equivalent) problem: find the polynomial $p(x):[-1,1]\rightarrow [-1,1]$ of degree $n$ with the greatest possible leading coefficient. We have some information on values of $p$, and need something about its coefficient. Let's try Lagrange's interpolation. Take some $n+1$ values $t_1 < t_2 < \dots < t_{n+1}$ from $[-1,1]$ and write down (for $u(x)=(x-t_1)\dots(x-t_{n+1})$) the formula $$ p(x)=\sum p(t_i) \frac{u(x)/(x-t_i)}{u'(t_i)}. $$ Then take a look on coefficient of $x^n$. It equals $$ \sum \frac{p(t_i)}{u'(t_i)}. $$ We know that $|p(t_i)|\leq 1$, so the leading coefficient does not exceed $ \sum 1/|u'(t_i)|. $ Ok, when does equality occur? The answer is: $p$ should take values $(-1)^{n-i+1}$ in $t_i$. That is, we have to find a polynomial of degree $n$ with $n+1$ extremal values $\pm 1$ on $[-1,1]$. This may hold only if $t_1=-1$, $t_{n+1}=1$, and $t_2$, $\dots$, $t_n$ are roots of $p'$. So, $1-p^2(x)$ should be divisible by $(1-x^2)p'(x)$. Hereon the trigonometic substitution $x=\cos t$, $p=\cos f$ is very natural, as we know that $1-f^2$ is divisible by $f'$ for $f=\cos$. So we invent Chebyshev's polynomials.

Also, it is seen from Lagrange formula that they are extremal in many other problems with restrictions $|p(x)|\leq 1$ on $[-1,1]$. For example, the value in each specific point $x_0>1$ is maximized also for Chebyshev polynomial, it is proved by exactly the same way.

Answer 2

Alex, I hope you will allow for the option that there are natural explanations for the Chebyshev polynomials which are unrelated to optimization on $[-1,1]$. Here is what I think is the most natural characterizing feature of this family of polynomials.

Theorem (Ritt): If $F_n(x)$ is a family of monic polynomials with coefficients in a field of characteristic 0 such that $\deg F_n(x) = n$ and $F_m(F_n(x)) = F_n(F_m(x))$ for all $m$ and $n$, then up to a simple change of variables $F_n(x) = x^n$ for all $n$ or $F_n(x) = (1/2^{n-1})T_n(x)$ for all $n$.

Proof: See Ritt, "Prime and Composite Polynomials," Trans. Amer. Math. Soc. 23 (1922), 51--66.

Also see the chapter "Commuting Polynomials" in Kvant Selecta: Algebra and Analysis Volume II.

The link provided in the original question mentions that the monic Chebyshev polnyomials commute, but doesn't emphasize that this is an incredibly special property of them. Pity.

Answer 3

Let's denote $\Pi_n$ the vector space of polynomial functions on $I:=[-1,1]$ of degree less than or equal to $n.$ The optimization problem you quoted is equivalent to:

Problem(2): Find $q\in\Pi_{n-1}$ that minimizes the uniform distance on I from the function $f(x)=x^n.$

While it is clear by compactness that Problem(2) has a solution, it's not obvious that the solution is unique, because the uniform norm is not uniformly convex (lack of unicity already appears in the analogous problem of point-line distance in $\mathbb{R}^2$ with the max norm). The magic of polynomials is that the solution is always unique, for any continuous function $f$. Not only, but Chebyshev also gave a characterization of the minimizer: it is the unique polynomial $q$ such that $f(x)-q(x)$ attains the maximum absolute value in at least n points, with alternate sign. (Polynomials are not the unique functions with this property; more generally one defines "Haar families", that span finite dimensional spaces analogous to the $\Pi_n$, and for them the argument works as well). Going back to your optimization problem, you have that $p(x)$ is the unique monic polynomial with all real simple zeros and that reaches the maximum absolute value with alternate sign between consecutive zeros. With a bit more work one arrives to $T_n/2^{n-1}$ (or, at this time, one pulls it out of the hat, but at this point I'd consider that quite more fair, and would have no objections, especially if the hat is the most noble one of Pafnuty Lvovich).

PS: Trying to answer the "psychology of mathematics" part of your question (how one arrives to the $T_n$ from the optimization problem). Once the problem is reduced to that of determining the $n$-th degree polynomial $T$ (say with positive leading coefficient) that oscillates n+1 times between it maximum value $1$ and its minimum value $-1$ on the interval $[-1,1],$ I guess that very soon one suspects that circles and trigonometric functions are around (I can't say it certainly, because I already know the answer!). But if one computes the first few such polynomials, and look at their graphs, they clearly look like sinusoidal curves drawn on a cylinder, and at that point one could recall from high school memories that $\cos(nx)$ is a trigonometric polynomial of $\cos(x),$ and observe it has clearly the wanted property.

Answer 4

The monic Chebyshev polynomial appears perhaps a bit more naturally as a unique minimizer in the following $L^2$-problem.

Problem: find a monic polynomial $P(x)$ of degree $n$ which minimizes the weighted norm $$\|P\|^2=\int_{-1}^{1}P^2(x)\frac{dx}{\sqrt{(1-x^2)}}.$$

The proof is straightforward. First, we check the orthogonality property $$\int_{-1}^{1}T_i(x)T_k(x)\frac{dx}{\sqrt{(1-x^2)}}=\delta_{ik}\frac{\pi}{2},\quad i,k=0,1,2,...,$$ which is equivalent to the orthogonality property of the sequence $\cos kx$ in $L^2(0,\pi)$. Next, we have for an arbitrary monic polynomial of degree $n$ $$P(x)=\sum\limits_{k=1}^n a_kT_k(x),\quad a_n=2^{1-n}.$$ Therefore $$\|P(x)-2^{1-n}T_n(x)\|^2=\|P\|^2+\|2^{1-n}T_n(x)\|^2-2^{2-n}\int_{-1}^{1}\sum\limits_{k=1}^n a_kT_k(x)T_n(x)\frac{dx}{\sqrt{(1-x^2)}}= $$ $$=\|P\|^2-\|2^{1-n}T_n(x)\|^2.$$ So $\|P\|\geq \|2^{1-n}T_n(x)\|,$ and the equality is possible if and only if $P(x)=2^{1-n}T_n(x)$.

---

Edit added. By the way, $2^{1-n}T_n(x)$ minimizes all weighted $L^p$-norms $$\left[\int_{-1}^{1}|P_n(x)|^p\frac{dx}{\sqrt{(1-x^2)}}\right]^{\frac{1}{p}},\quad 1\leq p\leq\infty,$$ over monic polynomials $P_n(x)$ of degree $n$. This book contains a survey of this and many other extremal properties of Chebyshev polynomials.