Uniform approximation of $x^n$ by a degree $d$ polynomial: estimating the error  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!
 A: 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$.
A: For $P_n(x)=(1-x^2)^n$, large $n$ and $a>0$ it's possible to produce a polinomial of degree $a\sqrt{2n}$ with difference in $L_\infty$ less than $C(1-\mathrm{erf}\;a)$, where $C$ is an absolute constant. Taking any positive  sequence $a(n)\to+\infty$ as $n\to\infty$ leads to $L_\infty$ norm converging to zero. For large $a$ we have $1-\mathrm{erf}\;a \sim e^{-a^2}/(a\sqrt{\pi})\;$. So to obtain the uniform $\varepsilon$ estimate on $[0,1]$  the degree $\sim C(\log \varepsilon^{-1})^{1/2}\sqrt n\ $ is enough.
Namely, consider $P_n$ on the segment $[-1,1]$. Let $x=\sin y$. Now it is enough to approximate the function 
$$
\sin^{2n}y =\sum_{k=0}^n c_n^k\cos 2ky
$$
on $[0,2\pi]$ by suitable trigonometric polynomials. Here $c_n^0=\frac1{4^{n}}{2n\choose n}$, $c_n^k =(-1)^{n-k}\frac1{2^{2n-1}}{2n\choose n+k}$, $k=1,\ldots,n$. For degree $2m<2n$ we'll take the polynomial 
$$
Q_{2m}(x)=\sum_{k=0}^m c_n^k\cos 2ky.
$$
Then the $L_\infty$ norm 
$$
\|P_{2n}-Q_{2m}\| {} \le \sum_{k=m+1}^{n}  |c_n^k|=\frac1{2^{2n-1}}\sum_{k=m+1}^{n}{2n\choose n+k}.
$$
The last sum can be easily estimated since it is exactly the sum of the tails in the Bernoulli distribution with probability $p=1/2$ and $2n$ independent  trials. For $m=[ a\sqrt{2n}]$ and large $n$ by the central limit theorem it is equal approximately to $2(1-\mathrm{erf}\;a)$. From here the above estimates follow.
A: Only a comment, but too long to fit in the comments section: 
You sound unsure of the result for $d=n-1$.  See the end of the page http://mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKind.html.  This gives the result, but there is a nice explanation in Acton's book Numerical Methods That Work: The Chebyshev polynomial
$T_n(x)=2^{n-1}x^n+$terms in $x^{n-2}$ and lower

is known to have $Int(n/2)$ minima of $-1$ and $Int((n-1)/2)$ maxima of $+1$ in the range $[-1,1]$.  So, rearrange:

$x^n = 2^{-(n-1)}[T_n(x)-($terms in $x^{n-2}$ and lower$)]$
and you have an $(n-2)$-order polynomial approximation of $x^n$, with an error that oscillates between $\pm2^{-(n-1)}$ the correct number of times, which is therefore optimal.
Acton's book is a pleasure to read in any case, and will also lead you through Remes's algorithm if you want to generate minimax approximations for reasonably small $n$.  You might want to search for this algorithm (if you don't know it already).  For approximating polynomials (or just powers), search for "economization of series".  I think there's actually pseudocode of an algorithm for it in the first edition of Oldham and Spanier's  An Atlas of Functions.  This is another lovely book, so long as you check the errata -- see http://www.trentu.ca/chemistry/oldham/AAOF.html.  The second edition is better in some ways, but much less useful for algorithms.

