# Can an $n$-element subset of a $2n$-element set be stored in $2n - \omega(1)$ bits?

There are $$\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \cdot (1 - o(1))$$ possible $$n$$-element subsets of a $$2n$$-element set. Therefore, any data structure storing such a set must use at least $$2n - O(\log n)$$ bits.

It’s easy to store such a set in $$2n$$ bits by using a bitvector while getting $$O(1)$$ membership queries. Is there a way to store such a set in $$2n - \omega(1)$$ bits, so that membership queries are “fast” for some reasonable definition of “fast?” (E.g. $$O(1)$$ time, polylog $$n$$, etc.)

• This might not be relevent, but if I'm not mistaken, there is a datastructe that uses $n+o(n)$ space, and answers queries in constant time: en.wikipedia.org/wiki/…. If you allow one sided error, this is also known as static approximate membership query data structure, or a static filter. When the set of elements is not known in advance, and you need to support insertions as well this is called an incremental filter. A classical example of such is Bloom filter. Commented Feb 27 at 8:39
• @TheHolyJoker Actually, this part of the Wikipedia article seems to directly answer the question: en.wikipedia.org/wiki/… . It references doi.org/10.1137/S0097539795294165 and (for support of more operations) doi.org/10.1145/1290672.1290680 . Commented Feb 27 at 9:28
• No, wait, it doesn’t work: the error margins are too large. For the case at hand, $B(n,2n)+o(B(n,2n))$ just means the same as $2n+o(n)$, and is likely even larger than $2n$. The bounds in doi.org/10.1145/3357713.3384274 are much better, but still not good enough: $\log\binom{2n}n+\log n+O(\log\log\log\log\log n)$ is about $2n+\frac12\log n$. Commented Feb 27 at 10:34
• Further references are in cstheory.stackexchange.com/a/19317 , but I haven’t checked if they are any good. Commented Feb 27 at 10:47
• For the record, any algorithm/data structure for this is completely galactic. You'd need on the order of $2^{64}$ bits to save a single 32-bit register compared to the naive full storage.
– orlp
Commented Feb 27 at 22:57