I am trying to understand the lower bound of a Bloom filter and want to know how this rewriting is possible from this article (page 6-7 (or 490)).
If $$m\geq n\mathrm{log}_2(1/\epsilon)$$ is some minumum size of a bitvector and we have $f$ as a false positive rate with $m$ as a power: $$f=(1/2)^{m\ln/2}$$ How does $m$ becomes (after plugging it into $f$): $$m\geq n\frac{\log_2(1/\epsilon)}{\ln2}=n\log_2e\cdot\log_2(1/\epsilon)$$And what does it mean when $m$ is within a factor of $\log_2e \approx1.44$ of the asymptotic lower bound assuming that the right hand side of the last equation above is the lower bound?
The asymptopic lower bound for $m$ is $n \log_2(1/\epsilon)$. That is the amount required number of bits required to represent all sets of $n$ elements allowing false positives for at most a fraction of $\epsilon$.
Now, the expected false positive rate is $f=(1/2)^k \ge (1/2)^{m \ln 2/ n}$. To achieve $f \le \epsilon$. We need
$$(1/2)^{m \ln 2/n} \le \epsilon$$
Taking reciprocal,
$$2^{m \ln 2/n} \ge \frac1\epsilon$$
Taking log with base $2$, $$m \ln 2/n \ge \log_2(1/\epsilon)$$
$$m \ge \frac{n}{\ln 2}\log_2(1/\epsilon)$$
Now $\ln 2=\frac{\log_2 2}{\log_2 e}=\frac1{\log_2 e}$,
Hence we requires $$ m \ge n \log_2 e \log_2(1/\epsilon).$$
The asymptotic lower bound was $n\log_2(\frac1/\epsilon)$.
Now, for space-wise Bloom filters, it is $\log_2 e$ times that.