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$ – Peter Shor Apr 22 '16 at 3:52
  • $\begingroup$ @PeterShor: Thank you! I suspected this was the case, but the proof is not evident to me. $\endgroup$ – Charles Apr 22 '16 at 4:33
  • 2
    $\begingroup$ You can take a look at my paper on the area: arxiv.org/pdf/1308.1600.pdf. $\endgroup$ – Yuval Filmus Apr 22 '16 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.

  • $\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$ – Peter Shor Apr 22 '16 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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