Can Quarter-Subset Membership be decided space-efficiently?
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&lt;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&lt;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&lt;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&lt;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&lt;c&lt;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$.