# Lower bound on prefix code lengths

For a prefix code $C:\{0,1\}^*\to\{0,1\}^*$, define $f(n)$ as the length of the longest encoding of a number with up to $n$ bits: $$f(n)=\max_{|k|\le n}\left|C(k)\right|.$$

(Note that by taking input as $\{0,1\}^*$ rather than $\mathbb{Z}^+$ I'm distinguishing between the 1-bit number 1 and the 2-bit number 01.)

The counting bound gives $f(n) \ge \left\lceil\log\left(2^n+2^{n-1}+\cdots+2^0\right)\right\rceil = \left\lceil\log\left(2^{n+1}-1\right)\right\rceil = n+1$ for $n>0$ where, throughout this post, $\log$ denotes the binary logarithm.

It's easy to construct $C$ such that $f(n)=O(n)$, $f(n)=n+O(\log n)$, $f(n)=n+\log n+O(\log\log n),$ etc. by recursion (starting from, say, Elias gamma coding). Is there a prefix-free code with $f(n)\le n+(1-\varepsilon)\log n$ for some $\varepsilon>0$ and large $n$?

• No. Not even for $\epsilon = 0$. Hint: use Kraft's inequality. Apr 22, 2016 at 3:52
• @PeterShor: Thank you! I suspected this was the case, but the proof is not evident to me. Apr 22, 2016 at 4:33
• You can take a look at my paper on the area: arxiv.org/pdf/1308.1600.pdf. Apr 22, 2016 at 15:10

I'll try to show this, hope I interpreted the question correctly.

Let $A_k=\{0,1\}^k.$ If $f(n)\leq n+\log n$ for $n$ large enough this implies $$\max\{\ell(c(x)):x \in A_1 \cup A_2\cup \ldots \cup A_k \}\leq k+ \log k,$$ for $k\geq N$, for some finite $N$, where $\ell(c(x))$ is the length of the codeword $c(x)$ assigned to $x.$ So this means that $$\sum_{N\leq k ~~} \sum_{x \in A_1\cup A_2 \cup \ldots \cup A_k} 2^{-\ell(c(x))}\geq \sum_{N \leq k~~} \sum_{x \in A_1\cup A_2 \cup \ldots \cup A_k} 2^{-(k+\log k)}$$ which is equal to $$\sum_{N\leq k} |A_1 \cup A_2 \cup \ldots \cup A_k|~ 2^{-(k+\log k)}= \sum_{N\leq k} (2^{k+1}-1)~ 2^{-(k+\log k)}$$ which is equal to $$\sum_{N\leq k} 2^{1-\log k} - 2^{-(k+\log k)}=2 \sum_{N\leq k} \frac{1}{k} - \sum_{N\leq k}\frac{2^{-k}}{k}=2 \left(\sum_{N\leq k} \frac{1}{k}\right) -\ln 2$$ which is unbounded, since the harmonic series diverges.

• I don't know whether interpreted it correctly ... I would have thought the sum should run for k from n to infinity, and not from 1 to n, because the requirement is that f(n) <= n + log n for large n. But the OP gives the counting bound from 1 to n, so you might be right. Either way, this proof works with small modifications. Apr 22, 2016 at 13:54