encodings testable by querying few bits

Question

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.

Answer 1

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.