Can Quarter-Subset Membership be decided space-efficiently?

Question

Consider the following decision problem. Let $q = \sum_{i=0}^{n/4} \binom{n}{i}$ and let $(C_0^n, C_1^n,\dots,C_{q-1}^n)$ be a suitable enumeration of those subsets of $\{0,1,\dots,n-1\}$ that have at most $n/4$ elements.

Quarter-Subset Membership
Input: tuple of non-negative integers $(i,j,n)$ represented in binary
Question: is $i \in C_j^n$?

By picking a "nice" enumeration $(C_i^n)$, can Quarter-Subset Membership be decided by a deterministic Turing machine using no more than $(0.99)n$ bits of workspace, for all large enough $n$?

---

Discussion

Let $\log x = \log_2 x$. It is easy to enumerate all subsets of at most $k$ elements chosen out of $n$ by keeping track of $k$ indices of size $\lceil \log n \rceil$ bits each. (See also the discussion in Knuth's TAOCP section 7.2.1.3.) When $k$ is constant this is just $O(\log n)$ bits. However, if we let $k = cn$ for some constant $c \le 1/4$, then such enumeration schemes use $\Omega(n\log n)$ space. One can also use an $n$-bit characteristic vector together with a check for the number of bits set. I'm interested in schemes that beat $n$ bits.

A closely related question is then:

For positive $c$ satisfying the inequality $c\log(e(1+c)/c) < 1$, is there a code representing subsets of at most $cn$ elements chosen from $n$ that uses $dn$ bits for some constant $d < 1$, and can be decoded efficiently?

Note that for large enough $n$, $$\sum_{i=0}^k\binom{n}{i} \le \left(\binom{n}{k}\right) = \binom{n+k-1}{k},$$ and since $$\log\binom{n+k-1}{k} \le \log[(e(n+k-1)/k)^k],$$ when $k = cn$ then information-theoretically it follows that $d \le c\log(e(1+c)/c)$ would be achieved with a perfect code. (This is less than $1$ if $0 < c \le 0.2728$.) I am therefore looking for a reasonably clean code that can be manipulated without using lots of space.

To obtain a perfect code, one could pick some enumeration of the subsets, run an index through the enumeration in increasing order, and then obtain each combination by decoding the index. However, decoding such a code when $k \ge \Omega(n/\log n)$ seems to require using at least $n$ bits of space for the enumerations I have looked at, such as via characteristic vectors ordered by increasing Hamming weight and then lexicographically, or via Gray codes.

There might be a way to do this with $o(n)$ space, but I think $(1-\varepsilon)n$ is more likely to be feasible. Note that since $\log \binom{n}{cn} \ge cn\log(1/c)$, the information-theoretic lower bound is already $\Omega(n)$ bits, so this really is about whether $(1-\varepsilon)n$ can be achieved for some $\varepsilon > 0$. A code that is nice enough (but not necessarily perfect) would seem to be enough to answer my question in the affirmative. It might also be the case that Quarter-Subset Membership can be decided efficiently without explicitly constructing a code. On the other hand, such an enumeration may not exist: for instance, every sequence of enumerations for values of $n$ might be inherently non-uniform, or it might be the case that any $(1-\varepsilon)n$-bit bound must be breached infinitely often.

Answer 1

I assume from the discussion that you are not actually interested in work space as claimed, but in total space including the size of the input. (Otherwise the trivial $n$-bit encoding scheme can be decoded in logarithmic space.)

Let $k$ be a sufficiently large constant, and consider the following encoding scheme for $X\subseteq\{0,\dots,n-1\}$. Split $\{0,\dots,n-1\}$ into $k$ blocks $B_u$, $u<k$, of size $n/k$ each, and put $X_u=X\cap B_u$. The encoding of $X$ consists of the sequence of the following numbers (written in binary) for each $u<k$:

• the size $s_u=|X_u|$;

• the number corresponding to $X_u$ in the combinatorial number system for $s_u$-size subsets.

As for the size of the encoding, assume $|X|\le n/4$. The numbers $s_u$ take $O(k\log(n/k))$ bits, which will be negligible. We have $s_u\le n/(3k)$ for at least $k/4$ of the $u$'s, in which case the encoding of $X_u$ takes about $H(1/3)\tfrac nk\approx0{.}92n/k$ bits; the remaining $X_u$ take at most $n/k$ bits each. The total is at most $0{.}98n$ bits.

Decoding amounts to deciding which block $i$ goes into, and then figuring out $X_u$; the latter be done easily in space $n/k+O(\log n)$, and one can reuse the space occupied by encodings of the remaining blocks (as long as the total space is at least $2n/k$, which is OK for $k$ large enough).

A better analysis shows that this scheme achieves space essentially $H(1/4)n\approx0{.}812n$: let $p_u=s_u/(n/k)$. Since $|X|/n\le1/4$, the average of $p_u$ over $u<k$ is at most $1/4$. The encoding of $X_u$ takes about $H(p_u)n/k$ bits. Now, the entropy function is concave, hence the average of $H(p_u)$ over $u<k$ is at most $H(1/4)$, and the total space is $H(1/4)n+O(\log n)$. This is optimal up to the $O(\log n)$.

There is of course nothing special about $1/4$. The same argument shows that for any constant $0<c<1/2$, there is an encoding scheme for $\le cn$-size subsets of $\{0,\dots,n-1\}$ that takes $H(c)n+O(\log n)$ bits, and can be decoded in-place. To some extent, it can even be used for $\le s(n)$-size subsets where $s(n)\ll n$, by taking a non-constant number of blocks ($k\ge 2/H(s(n)/n)$ or so), but then the $O(k\log(n/k))$ overhead gets more pronounced, and overtakes the main term when $s(n)$ drops below roughly $\sqrt n$.