We prove lower bounds on the redundancy necessary to
represent a set $S$ of objects using a number of bits
close to the information-theoretic minimum $\log_2 |S|$,
while answering various queries by probing few bits. Our
main results are:

\begin{itemize}
\item To represent $n$ ternary values $t \in
\zot^n$ in terms of $u$ bits $b \in \zo^u$ while accessing
a single value $t_i \in \zot$ by probing $q$ bits of $b$,
one needs
$$u \geq (\log_2 3)n + n/2^{O(q)}.$$ This matches an exciting representation by P{\v a}tra{\c s}cu
(FOCS 2008) where $u \leq (\log_2 3)n +
n/2^{q^{\Omega(1)}}$. We also note that results on logarithmic forms imply the lower bound
$u \geq (\log_2 3)n + n/\log^{O(1)} n$ if we access $t_i$ by probing one cell of $\log n$ bits.

\item To represent sets of size $n/3$ from a universe
of $n$ elements in terms of $u$ bits $b \in \zo^u$ while
answering membership queries by probing $q$ bits of $b$, one needs
$$u \geq \log_2 \binom{n}{n/3} + n/2^{O(q)} - \log n.$$
\end{itemize}

Both results above hold even if the probe locations are determined adaptively.

Ours are the first lower bounds for these fundamental problems; we
obtain them drawing on ideas used in lower bounds for
locally decodable codes.