  Consider the problem of estimating the Shannon entropy of a distribution over
$k$ elements from $n$ independent samples. We show that the minimax mean-square
error is within universal multiplicative constant factors of $$\Big(\frac{k }{n
\log k}\Big)^2 + \frac{\log^2 k}{n}$$ if $n$ exceeds a constant factor of
$\frac{k}{\log k}$; otherwise there exists no consistent estimator. This
refines the recent result of Valiant-Valiant \cite{VV11} that the minimal
sample size for consistent entropy estimation scales according to
$\Theta(\frac{k}{\log k})$. The apparatus of best polynomial approximation
plays a key role in both the construction of optimal estimators and, via a
duality argument, the minimax lower bound.
