# encodings testable by querying few bits

Suppose you want an encoding of the integers $\{0,1,2,\ldots,N-1\}$ into bitstrings. Two ways to do this are standard binary place value and unary encoding. The binary place value method is efficient in that it uses only $\log_2 N$ bits. However, given an $x \in \{0,1,2,\ldots,N-1\}$, to check whether a bitstring encodes $x$ you have to read all $\log_2 N$ bits.The unary coding is the other extreme: the encoding is very space-inefficient in that it uses $N$ bits, but to check whether the string represents $x$ you only have to read two of the bits, namely bit $x$ and bit $x+1$ which must be 1 and 0 respectively if the bitstring encodes $x$. My question is: what is known about encodings in between these two extremes? Can we encode the the integers $\{0,\ldots,N-1\}$ into bitstrings of length scaling less than linearly with $N$ such that we can check whether the bitstring encodes $x$ by looking at only a constant number of bits? I assume that somehow by squinting at this question the right way it can be mapped onto a well-studied question about error correcting codes, combinatorial designs, or something of that sort.

• A related concept in computer science is probabilistically checkable proofs (PCPs) where, after reading just a few bits of a proof (randomly chosen), one can tell with good probability if it is valid or not.
– usul
Oct 2, 2016 at 19:50

Fix $k$ which will be your constant. Assume that the string length is $d$. Set $N={d\choose k}$, and to every $x\in \{0,\dots,N-1\}$ put into bijective correspondence a $k$-tuple of positions $F_x$. Now you may encode $x$ by pussing ones eactly at the positions from $F_x$, and then check `$x$-ness' by the same positions.