<p>I'll try to show this, hope I interpreted the question correctly.</p>

<p>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.</p>

CC BY-SA 3.0
2016-04-22T13:54:20.677Z
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.
Peter Shor 
CC BY-SA 3.0
2016-04-22T10:05:22.323Z
2016-04-22T22:06:23.963Z
2016-04-22T22:06:23.963Z
kodlu
<p>For a <a href="https://en.wikipedia.org/wiki/Prefix_code">prefix code</a> $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|.
$$</p>

<p>(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.)</p>

<p>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&gt;0$ where, throughout this post, $\log$ denotes the binary logarithm.</p>

<p>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, <a href="https://en.wikipedia.org/wiki/Elias_gamma_coding">Elias gamma coding</a>). Is there a prefix-free code with $f(n)\le n+(1-\varepsilon)\log n$ for some $\varepsilon&gt;0$ and large $n$?</p>

CC BY-SA 3.0
2016-04-22T03:52:33.467Z
No. Not even for $\epsilon = 0$. Hint: use Kraft's inequality.
Peter Shor 
CC BY-SA 3.0
2016-04-22T04:33:43.550Z
@PeterShor: Thank you! I suspected this was the case, but the proof is not evident to me.
Charles
CC BY-SA 3.0
2016-04-22T15:10:54.783Z
You can take a look at my paper on the area: http://arxiv.org/pdf/1308.1600.pdf.
Yuval Filmus
<reference-request><it.information-theory><prefix-free-code>
Lower bound on prefix code lengths
Charles
# Lower bound on prefix code lengths

(Asked by: username_0 on 2016-04-21)

For a [prefix code](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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$?

**Tags:** reference-request, it.information-theory, prefix-free-code
> **Comments:**
> **username_1**: No. Not even for $\epsilon = 0$. Hint: use Kraft's inequality.  
> **username_0**: @PeterShor: Thank you! I suspected this was the case, but the proof is not evident to me.  
> **username_2**: You can take a look at my paper on the area: http://arxiv.org/pdf/1308.1600.pdf.  

---

## 1 answers

### Answer by username_3 on 2016-04-22. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_1**: 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.  

---

