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$?

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

1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$ Commented Apr 22, 2016 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.