# Optional prefix code for the naturals

The naturals $\mathbb{N}$ can be encoded with a binary unary code such as

\begin{align} 1&=0_b\\ 2&=10_b\\ 3&=110_b\\ &... \end{align} The length this the encoding grows linearly with the natural number it represents. For example the length of $110_b$ is 3 and it also represents the number 3.

I am looking for an upper bound on the optimality of the prefix free encoding. For example, can we design a prefix coding of $\mathbb{N}$ such that the length of the encoding grows according to ~$\sqrt{n}$, instead of $n$. Is there an upper bound on the optimality that we can prove?

• You say that encoding is unary and then ask if you can make it sublinear? Simply, no, there is no way to do it without using arbitrary amount of 0's for each number. Yet $\sqrt n$ encoding is useless as usage of two symbols allows you logarithmic encoding. – rus9384 Aug 25 '17 at 15:13
• @rus9384 No, I am asking for the most compact prefix code for $\mathbb{N}$ – Alexandre H. Tremblay Aug 25 '17 at 15:23

Kraft's inequality states that there is a prefix code with word lengths $k_0,k_1,\ldots$ if and only if $$\sum_{n=0}^\infty 2^{-k_i} \leq 1.$$ This gives a positive answer to your question. Concretely, Elias gamma coding has code word length $O(\log n)$. The idea is simple: first you encode the bit-length of the integer using your method (using roughly $\log_2 n + 1$ bits), then you encode the number itself (using another roughly $\log_2 n$ bits), for a total of roughly $2\log_2n + 1$ bits.
• The problem is that this upper bound can be improved. Your bound shows that the length of the $n$th codeword must be at least roughly $\log n$, but you can improve it to $\log n + \log \log n$, for example. In contrast, there are codes in which the $n$th codeword has length roughly $2\log n$ and roughly $\log n + 2\log\log n$. – Yuval Filmus Aug 28 '17 at 14:34