We consider the problem of approximating the support size of a distribution from a small number of samples, when each element in the distribution appears with probability at least \frac{1} {n}. This problem is closely related to the problem of approximating the number of distinct elements in a sequence of length n. For both problems, we prove a nearly linear in n lower bound on the query complexity, applicable even for approximation with additive error.

At the heart of the lower bound is a construction of two positive integer random variables, E[X_1 ]/E[X_2 ] = E[X_1^2 ]/E[X_2^2 ] = \ldots = E[X_1^k /E[X_2^k ]. Our lower bound method is also applicable to other problems. In particular, it gives new lower bounds for the sample complexity of (1) approximating the entropy of a distribution and (2) approximating how well a given string is compressed by the Lempel-Ziv scheme.