<p>There are <span class="math-container">$\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \cdot (1 - o(1))$</span> possible <span class="math-container">$n$</span>-element subsets of a <span class="math-container">$2n$</span>-element set. Therefore, any data structure storing such a set must use at least <span class="math-container">$2n - O(\log n)$</span> bits.</p>
<p>It’s easy to store such a set in <span class="math-container">$2n$</span> bits by using a bitvector while getting <span class="math-container">$O(1)$</span> membership queries. Is there a way to store such a set in <span class="math-container">$2n - \omega(1)$</span> bits, so that membership queries are “fast” for some reasonable definition of “fast?” (E.g. <span class="math-container">$O(1)$</span> time, polylog <span class="math-container">$n$</span>, etc.)</p>

CC BY-SA 4.0
2024-02-27T08:39:01.870Z
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: https://en.wikipedia.org/wiki/Succinct_data_structure#:~:text=the%20heap.-,Succinct%20indexable%20dictionaries,-%5Bedit%5D. 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**.
TheHolyJoker
CC BY-SA 4.0
2024-02-27T09:28:36.810Z
@TheHolyJoker Actually, this part of the Wikipedia article seems to directly answer the question: https://en.wikipedia.org/wiki/Succinct_data_structure#Entropy-compressed_solutions . It references https://doi.org/10.1137/S0097539795294165 and (for support of more operations) https://doi.org/10.1145/1290672.1290680 .
Emil Jeřábek
CC BY-SA 4.0
2024-02-27T10:34:29.597Z
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 https://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$.
Emil Jeřábek
CC BY-SA 4.0
2024-02-27T10:47:21.787Z
Further references are in https://cstheory.stackexchange.com/a/19317 , but I haven’t checked if they are any good.
Emil Jeřábek
CC BY-SA 4.0
2024-02-27T22:57:37.177Z
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
CC BY-SA 4.0
2024-02-28T08:34:55.567Z
@orlp Not really. You can save one bit for all $n\ge1$, two bits for all $n\ge5$, etc. This can save a number of percent of your storage if you have a compact list of many such sets with small $n$. But of course, I know nothing about the motivation of the OP.
Emil Jeřábek
CC BY-SA 4.0
2024-02-28T10:11:14.103Z
@Emil Jeřábek Your assumption with "many such sets" is that there is recursive substructure, but there isn't. While only $n$ out of $2n$ bits may be set globally, the first five bits may have any pattern - incompressible. A lower bound from *Elements of Information Theory* by Cover & Thomas (Example 11.1.3) gives us $\binom{2n}n \geq \frac{2^{2n}}{2n+1}$, and thus $\lceil \log_2 \binom{2^{64}}{2^{63}}\rceil \geq 2^{64} - 64$. This lower bound isn't as tight as it could be, but it shows that information theoretically you can't save more than 64 bits of storage even with $2^{64}$ bits of input.
orlp
CC BY-SA 4.0
2024-02-28T10:28:36.343Z
I don’t see any connection of your comment to mine. I’m not talking about any recursive structure. I mean literally what I wrote: if I need to store 1,000,000 5-element subsets of [10], I can use 8,000,000 bits instead of 10,000,000.
Emil Jeřábek
CC BY-SA 4.0
2024-02-28T11:43:37.057Z
Ah I see, you meant many instances of the problem instead of a single large instance. If that is OP's scenario then yes you could do some meaningful savings if the instances are truly tiny.
orlp
<ds.data-structures><succinct>
Can an $n$-element subset of a $2n$-element set be stored in $2n - \omega(1)$ bits?
templatetypedef
# Can an $n$-element subset of a $2n$-element set be stored in $2n - \omega(1)$ bits?

(Asked by: username_0 on 2024-02-26)

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.)

**Tags:** ds.data-structures, succinct
> **Comments:**
> **username_1**: 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: https://en.wikipedia.org/wiki/Succinct_data_structure#:~:text=the%20heap.-,Succinct%20indexable%20dictionaries,-%5Bedit%5D. 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**.  
> **username_2**: @TheHolyJoker Actually, this part of the Wikipedia article seems to directly answer the question: https://en.wikipedia.org/wiki/Succinct_data_structure#Entropy-compressed_solutions . It references https://doi.org/10.1137/S0097539795294165 and (for support of more operations) https://doi.org/10.1145/1290672.1290680 .  
> **username_2**: 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 https://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$.  
> **username_2**: Further references are in https://cstheory.stackexchange.com/a/19317 , but I haven’t checked if they are any good.  
> **username_3**: 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.  
> **username_2**: @orlp Not really. You can save one bit for all $n\ge1$, two bits for all $n\ge5$, etc. This can save a number of percent of your storage if you have a compact list of many such sets with small $n$. But of course, I know nothing about the motivation of the OP.  
> **username_3**: @Emil Jeřábek Your assumption with "many such sets" is that there is recursive substructure, but there isn't. While only $n$ out of $2n$ bits may be set globally, the first five bits may have any pattern - incompressible. A lower bound from *Elements of Information Theory* by Cover & Thomas (Example 11.1.3) gives us $\binom{2n}n \geq \frac{2^{2n}}{2n+1}$, and thus $\lceil \log_2 \binom{2^{64}}{2^{63}}\rceil \geq 2^{64} - 64$. This lower bound isn't as tight as it could be, but it shows that information theoretically you can't save more than 64 bits of storage even with $2^{64}$ bits of input.  
> **username_2**: I don’t see any connection of your comment to mine. I’m not talking about any recursive structure. I mean literally what I wrote: if I need to store 1,000,000 5-element subsets of [10], I can use 8,000,000 bits instead of 10,000,000.  
> **username_3**: Ah I see, you meant many instances of the problem instead of a single large instance. If that is OP's scenario then yes you could do some meaningful savings if the instances are truly tiny.  

---

## 0 answers

