Suppose you want an encoding of the integers $ \{0,1,2,\ldots,N1\} $ 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,N1\}$, 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 spaceinefficient 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,N1\}$ 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 wellstudied question about error correcting codes, combinatorial designs, or something of that sort.

$\begingroup$ 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. $\endgroup$– usulOct 2, 2016 at 19:50
1 Answer
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,N1\}$ 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.

$\begingroup$ Ah, perhaps my question was more elementary than I realized. Thank you for this simple and very satisfactory answer. $\endgroup$– StephenJOct 2, 2016 at 19:49


$\begingroup$ For some error detection, I recommend checking K other bits to assure that they are zero. Which bits will depend on where the errors are likely to occur. Gerhard "Safety Is A Constant Concern" Paseman, 2016.10.02. $\endgroup$ Oct 2, 2016 at 21:14

$\begingroup$ @GerhardPaseman, at that point I think this begins to resemble the Bloom filter data structure. $\endgroup$– usulOct 2, 2016 at 22:13