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.