  Estimating the number of unseen species is an important problem in many
scientific endeavors. Its most popular formulation, introduced by Fisher, uses
$n$ samples to predict the number $U$ of hitherto unseen species that would be
observed if $t\cdot n$ new samples were collected. Of considerable interest is
the largest ratio $t$ between the number of new and existing samples for which
$U$ can be accurately predicted.
  In seminal works, Good and Toulmin constructed an intriguing estimator that
predicts $U$ for all $t\le 1$, thereby showing that the number of species can
be estimated for a population twice as large as that observed. Subsequently
Efron and Thisted obtained a modified estimator that empirically predicts $U$
even for some $t>1$, but without provable guarantees.
  We derive a class of estimators that $\textit{provably}$ predict $U$ not just
for constant $t>1$, but all the way up to $t$ proportional to $\log n$. This
shows that the number of species can be estimated for a population $\log n$
times larger than that observed, a factor that grows arbitrarily large as $n$
increases. We also show that this range is the best possible and that the
estimators' mean-square error is optimal up to constants for any $t$. Our
approach yields the first provable guarantee for the Efron-Thisted estimator
and, in addition, a variant which achieves stronger theoretical and
experimental performance than existing methodologies on a variety of synthetic
and real datasets.
  The estimators we derive are simple linear estimators that are computable in
time proportional to $n$. The performance guarantees hold uniformly for all
distributions, and apply to all four standard sampling models commonly used
across various scientific disciplines: multinomial, Poisson, hypergeometric,
and Bernoulli product.
