# Maximal uniquely decodable codes

This question is about the Kraft-McMillan inequality:

If $$w_1,\ldots,w_n$$ are words of lengths $$l_1,\ldots,l_n$$ from an alphabet with $$r$$ letters, which form a uniquely decodable code, then $$\sum_{i=1}^n \frac{1}{r^{l_i}} \leq 1.$$

(A set of words is uniquely decodable if any word in the alphabet can be broken into words from the set in at most one way.)

Let's say a uniquely decodable set of words is maximal if it is not possible to add another word to this set and still have it uniquely decodable. Also, let's say a uniquely decodable set of words is sharp if it attains equality in the McMillan inequality, i.e. $$\sum_{i=1}^n \frac{1}{r^{l_i}} = 1.$$

Question. It is obvious that sharp implies maximal. What about the converse: is every maximal uniquely decodable set sharp?

I know how to prove it if we're talking about "prefix-free" (Kraft version) instead of uniquely decodable, but I don't see how to prove this version, if it's even true.

Choose $$m$$ large. We have $$r^m$$ possible sequences of length $$m$$, and they can all appear as interior sequences in concatenations of codewords. We would like to make them line up, so as to find $$r^m$$ concatenations of codewords where each of these sequences appears starting with the $$C$$'th letter. By number theory (see the Frobenius coin problem), there is some constant $$C$$ so that we can arrange this independent of $$m$$. Let $$\ell$$ be the maximum codeword length. We thus have $$r^m$$ different sequences of length at most $$m+C+\ell$$, none of which is a prefix of another one, and which are all in the code. We can use these $$r^m$$ sequences of codewords to transmit information at rate at least $$\frac{m \log_2 r}{m+C+\ell}$$ bits per symbol. Since $$C+\ell$$ is fixed, then for any $$\alpha < 1$$, we can find $$m$$ large enough so that $$\frac{m \log_2 r}{m+C+\ell} > {\alpha} \log r,$$ showing that the information transmission rate for our original codewords is $$\log r$$. However, if the Kraft inequality is not sharp, then there is an $$\alpha<1$$ such that $$\sum_{i=1}^n \frac{1}{r^{\alpha \ell_i}} = 1\,.$$ And one can show that if this equation holds, then the code can only transmit information at a rate of $$\alpha \log r$$ bits per symbol. (It's possible to check this with calculus, although if you try to derive it with calculus the equations get really ugly.)
Case 2: the greatest common divisors of the lengths of the codewords is $$g>1$$.
Consider the new code formed by replacing every $$g$$ letters of the original code with a new letter in an alphabet of size $$r^g$$. We are now in case 1, so the Kraft-McMillan inequality holds with equality. The codeword lengths in our new code are $$\ell_i/g$$, so we have $$1 = \sum_i (r^g)^{\ell_i/g} = \sum_i r^{\ell_i},$$ proving the theorem.