We prove strong lower bounds for the space complexity of (\varepsilon ,\delta )-approximating the number of distinct elements F₀ in a data stream. Let m be the size of the universe from which the stream elements are drawn. We show that any one-pass streaming algorithm for (\varepsilon ,\delta )-approximating F₀ must use \Omega (\frac{1}{{\varepsilon ^2 }}) space when \varepsilon = \Omega (m^{ - \frac{1}{{9 + k}}} ), for any k > 0, improving upon the known lower bound of \Omega (\frac{1}{\varepsilon }) for this range of \varepsilon. This lower bound is tight up to a factor of log log m for small \varepsilon and log (\frac{1}{\varepsilon }) for large \varepsilon. Our lower bound is derived from a reduction from the one-way communication complexity of approximating a boolean function in Euclidean space. The reduction makes use of a low-distortion embedding from an \iota _2 to an \iota _1 norm.