Approximation of monomials by lower degree polynomials

Our topic is the uniform approximation ofx ^k by polynomials of degreen (n on the interval –1, 1]. Our major result indicates that good approximation is possible whenk is much smaller thann ² and not possible otherwise. Indeed, we show that the approximation error is of the exact order of magnitude of a quantity,p _k,n , which can be identified with a certain probability. The numberp _k,n is in fact the probability that when a (fair) coin is tossedk times the magnitude of the difference between the number of heads and the number of tails exceedsn.