Lower bound on prefix code lengths

Question

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

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.