# Encoding two 6-bit positive integers compactly

Is it possible to encode two 6-bit wide positive integers a and b guaranteed to be in [0, 63] in a way that a and b are recoverable -- in fewer than 12 bits? We could obviously concatenate the binary representations (a << 6 | b). The scheme would have to allow any two arbitrary values within the given range. Can we do better than 12 bits?

• There are $2^{12}$ options, and you need a different encoding for each option, so no. Of course, if you have some prior knowledge (e.g. how often each pair appears), you can improve average encoding length by using non-fixed length encodings (see e.g. Huffman codes).
– user114966
Oct 14, 2020 at 14:55

Suppose that $$H\colon \{0,1\}^6 \times \{0,1\}^6 \to \{0,1\}^n$$ is such that $$a,b \in \{0,1\}^6$$ can be recovered from $$H(a,b)$$. In particular, $$H(a,b) \neq H(c,d)$$ whenever $$(a,b) \neq (c,d)$$. Since there are $$2^{12}$$ possible inputs, and the value of $$H$$ on each of them is different, it follows that the range of $$H$$ must consist of at least $$2^{12}$$ different points. Since $$\{0,1\}^n$$ has $$2^n$$ points, we conclude that $$n \geq 12$$.