Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
Substitute x = cos t and write p(x) as a linear combination of terms of the form cos nt. As t varies these terms will go in and out of phase with respect to each other, and the only constraint you have is on the coefficient of cos nt, so to keep these phases from constructively interfering you get rid of all the other terms. That's my intuition, anyway. –  Qiaochu Yuan May 21 '10 at 22:56
    
My answer to your title question would be "orthogonalization with semicircular weighting" but now I prefer KConrad's answer. –  S. Carnahan May 21 '10 at 23:01
    
The Chebyshev polynomials form one family of orthogonal polynomials on $[-1,1]$, and are (with the Legendre polynomials) particular instances of Jacobi polynomials corresponding to the measure $dx/(1-x)^\alpha(1+x)^\beta$. The name "Chebyshev polynomials" is also used in the problem of minimizing sup norm by polynomials with integer coefficients; see math/0101166. –  Wadim Zudilin May 22 '10 at 7:41
3  
I feel as though none of the answers so far quite answers the question. There are many beautiful characterizations of the Chebyshev polynomials, but what does any of them have to do with the minimization problem in the question? But perhaps the answer to the OP is that the Chebyshev polynomials were thought of for a different reason, and it then became clear what else they could do. (I don't know whether that is the actual story -- does anyone know their history here?) –  gowers May 22 '10 at 9:30
add comment

4 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Thanks, Keith! I knew that Chebyshev polynomials had this property, but had no idea how special it was. –  alex May 21 '10 at 23:30
    
Huh, I didn't know that theorem of Ritt's. Just to emphasize the naturality of this point of view: one day during graduate school this question came up (somewhat randomly in discussion) and an officemate and I took one afternoon and proved exactly that. (Okay, not quite: we didn't ask the polynomials to be monic and also just asked for polynomials over the rings Z, Q, R, rather than an arbitrary field of Char 0. But the result is essentially the same. So our proof is considerably shorter [~4 pages].) –  Willie Wong May 22 '10 at 0:36
    
Willie, the article I cited from Kvant Selecta explains the result in just a few pages. –  KConrad May 22 '10 at 16:19
1  
It's maybe worth pointing out that whilst Ritt's original proofs rely on the topology of Riemann surfaces, it can be done purely algebraically. For references, see eg Clauwens, Commuting polynomials and $\lambda$-ring structures on Z[x] , J. Pure Appl. Algebra 95 (1994). This paper gives the following nice consequence: there are exactly two $\lambda$-ring structures on Z[x], one arising from powers and the other from the Chebyshev polynomials. –  dke May 22 '10 at 16:59
    
dke: The Kvant article I mention is also a simple treatment of the commuting family of polynomials problem. I gave the Ritt citation as a matter of historical precedence, not because I thought it was the ideal argument. –  KConrad May 22 '10 at 17:49
add comment

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.

share|improve this answer
add comment

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 Chebychev polynomials.

share|improve this answer
    
Andrey, your book ref does not work. So, what book do you mean? –  Wadim Zudilin May 28 '10 at 11:59
    
The link works on my PC. Anyway, it's "Chebyshev Polynomials" by J. C. Mason and D. C. Handscomb. –  Andrey Rekalo May 28 '10 at 12:43
    
I've never heard about the book. But if you really have a link to the book can you simply post it in the comment. (Your answer has a blue-lighted "This book" but it's not a link. :( ) Credit: +1. –  Wadim Zudilin May 30 '10 at 14:17
    
There you go: books.google.co.uk/… –  Andrey Rekalo May 30 '10 at 15:49
    
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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