The answer to this question should be well known, but it's a hard question to search for online.


Suppose we want to approximate the function $x^n$ by a polynomial of degree $d$ in the $L\_\infty$ norm on $[-1,1]$. What is a good estimate of the error of the best approximator, in terms of $n$ and $d$?


I know this question was solved exactly by Chebyshev for $d = n-1$ (the error is $2^{-d}$ I think). The range of interest for me is $\sqrt{n} \leq d \leq n$ and I don't mind log factors in the estimate. Thus I would be happy to have an estimate for the error of the Chebyshev expansion truncated to degree $d$. 


(A bonus would be an answer to the same question for $(1-x^2)^d$.)


Thanks!



Uniform approximation of $x^n$ by a degree $d$ polynomial: estimating the error 
For large $n$ and fixed $\epsilon > 0$ there is a polynomial of degree $d = O\_\epsilon(\sqrt{n})$ that uniformly approximates $x^n$ to within $\epsilon$ on all of $[-1,+1]$. The polynomial can be taken to be the truncated Čebyšev expansion of $x^n$, as the original proposer (OP) suggested. As $\epsilon \rightarrow 0$, the $O\_\epsilon$ constant grows only as $(\log(\epsilon^{-1}))^{1/2}$; for example, $d = 2.576 \sqrt{n}$ suffices to get $\epsilon = .01$ if I computed correctly.


The OP wrote that truncating the Čebyšev expansion will give the correct $L^\infty$ distance to within a log factor. I don't see *a priori* why this should be, but fortunately the coefficients of the expansion of $x^n$ in Čebyšev polynomials turn out to be elementary and familiar enough to work with explicitly.


It will be convenient to define $T\_k(x)$ for all $k \in \bf Z$ as the polynomial such that $T\_k(\cos u) = \cos ku$. Then $T\_{-k} = T\_k$ is a polynomial of degree $|k|$ satisfying $|T\_k(x)| \leq 1$ for all $x\in [-1,+1]$. Now the Čebyšev expansion of $x^n$ is simply
$$
x^n = \frac1{2^n} \sum\_{m=0}^n {n \choose m} T\_{2m-n}(x),
$$
which can be checked by writing $x = \cos u = \frac12(e^{iu}+e^{-iu})$ and $T\_k(x) = \frac12(e^{iku}+e^{-iku})$. So the coefficients form a binomial distribution, and truncating at degree $d$ eliminates only the tail of the distribution past $d^2/n$ standard deviations. Since each $|T\_{2m-n}(x)| \leq 1$, this tail also bounds the truncation error for all $x \in [-1,+1]$, and we conclude that this error can be brought below any positive $\epsilon$ by making $d$ a large enough multiple of $\sqrt{n}$, as claimed.


This might not be the optimal $L^\infty$ approximation (except for $d=n-1$, when its optimality is the result of Čebyšev that you quoted), but it's not too far, because it *is* the best $L^2$ approximation with respect to the Čebyšev measure $\pi^{-1} dx/ \sqrt{1-x^2}$, and the $L^\infty$ distance is at least as large as the $L^2$ distance. The $L^2$ distance can be computed from the sums of the squares of the coefficients in the tail.


Much the same technique should work for $(1-x^2)^n$; indeed I see that while I was writing this Andrew posted an answer for $(1-x^2)^n$ that looks very similar to what I did for $x^n$.


