I don't think that shows that you can't make any definitive proof of size requirements. All it shows is that you have to make a statement about the accuracy. For example, it might be possible to prove that for all accuracies, an optimal bloom filter with a particular accuracy will always be smaller than an optimal inverse bloom filter of the same accuracy.
You have to define more specifically what you mean about accuracy here. Accuracy for the bloom filter would be probability of false positives. For the inverse it would be probability of false negatives.
For a bloom filter, if you're targeting a false probability f with n items, you want k = lg(1)/f hash functions, and m = 1.44 k*n bits.
That's the thing though. The bloom filter version scales up easily from the degenerate version (adding more bits increases accuracy). Unless I'm missing something, the inverse bloom filter doesn't scale up from the degenerate version in any natural way.
This will nag at me now. I'm going to need to give this some thought. If I come up with any proof on mem reqs. I'll let you know.
