# Lower bounds for space with some probability of error

There is an information theoretic lower bound of $\log_2 {U \choose x}$ for the number of bits to represent a subset of $x$ elements chosen from a universe of size $U$. We can in principle use this representation (perhaps inefficiently) as a data structure to test if any query is part of this subset.

How can you show a similar information theoretic lower bound if we are happy to have false positives with some probability $p$?

• If you are happy to allow false positives, you are interested in a data structure called Bloom Filters, though sadly I am not familiar with the lower-bound in that framework. – user340082710 Jan 29 '15 at 14:12

In "Network applications of Bloom filters: A survey", Broder and Mitzenmacher show an $x \log_2 (1/p)$ lower bound on the space usage.