Kraft inequality

ilyasu1 · P versus NP Offline Joined: 03 Jun 2004 Posts: 36

For each $i \in \{1,\ldots,n\}$ you are given a binary string $b_i$ of lenght $l_i$ .

Let $C(a_1,\ldots,a_k) = b_{a_1}\cdot b_{a_2} \cdot\ldots\cdot b_{a_k}$ , where
$\cdot$ stands for concatenation, $k$ is arbitrary and $1\leq a_j \leq n$ .

Prove that if $C$ is injective then $\sum_{i=1}^n \frac 1 {2^{l_i}}\leq 1.$

The solution is nice and not hard.

**Posted:** Mon Feb 28, 2005 4:21 pm

Myth

I have invented a stupid solution.
Let $f_s$ be a number of different strings $C(a_1,\ldots,a_k)$ s.t. $|C(a_1,\ldots,a_k)|=s$ . We have $f_s=\sum_{i=1}^n f_{s-l_i}$ . We know that $f_s=\sum_{j=1}^{d} a_j\lambda_j^d$ . Since $f_s\leq 2^s$ we conclude $|\lambda_j|\leq 2$ for all $j$ . But numbers $\lambda_j$ are roots of characteristic equation $P(x)=x^d-\sum_{i=1}^n x^{d-l_i}=0$ , where $d=\max l_i$ . Therefore, $P(2)\geq 0$ (otherwise the equation has a root >2). But $P(2)\geq 0$ means $\sum_{i=1}^n \frac 1 {2^{l_i}}\leq 1$ .

**Posted:** Tue Mar 01, 2005 8:24 am

_________________
Myth is out of here

ilyasu1 · P versus NP Offline Joined: 03 Jun 2004 Posts: 36

Yea, looks like you are right.

The solution I have is almost the same but in a different shell:

If $S = \sum_{k=1}^n 2^{-l_k}$ , then
$S^N = \sum_{1 \leq b_1,\ldots,b_N \leq n } 2^{-(l_{b_1}+\cdots+l_{b_N})} = \sum 2^{-i}f_i$ .

Each term in the last sum is less than 1 ( $2^i$ are all binary strings and $f_i$ is merely a subset of them) and the total number of terms is at most $N\cdot \max l_i$ . So $S^N$ is bounded by a linear function which can only be if $S\leq 1$ .

**Posted:** Wed Mar 02, 2005 4:56 pm