Packing bound for separated randomized message rows

Let $D$ be any probability row with $\mathrm{\parallel }D{\mathrm{\parallel }}_2\le 0.1$. For every probability vector $p$, each coordinate lies in $[0,1]$, so $-p_i\ln p_i\ge 0$ when $p_i>0$, and the defined zero terms are also nonnegative; hence $H(p)\ge 0$. In particular this holds for $DA$ and each $D^{(j)}A$. The output entropy satisfies $H(DA)\le \ln m$, because $D(DA\mathrm{\parallel }u)=\ln m-H(DA)\ge 0$ for uniform $u$, and nonnegativity follows by summing [F3]. Apply [F2]. Set $L=\{j:H(D^{(j)}A)\le H(DA)-1\mathrm{/}4\}$ and $s={\sum }_{j\in L}{q}_j$. Since the average child entropy is nonnegative and at most $H(DA)-1\mathrm{/}2$, first $H(DA)\ge 1\mathrm{/}2$; then we have $(1-s)(H(DA)-1\mathrm{/}4)\le H(DA)-1\mathrm{/}2$, so $s\ge 1\mathrm{/}(4\ln m)$.

Nonnegative coordinates and $D={\sum }_j{q}_j{D}^{(j)}$ imply ${\sum }_{j\in L}{q}_j\mathrm{\parallel }{D}^{(j)}{\mathrm{\parallel }}_2\le \sqrt{m}\mathrm{\parallel }D{\mathrm{\parallel }}_2\mathrm{.}$ Indeed Cauchy–Schwarz bounds the left side by $\sqrt{m}({\sum }_j{q}_j^2\mathrm{\parallel }{D}^{(j)}{\mathrm{\parallel }}_2^2{)}^{1\mathrm{/}2}$, and the square under the radical is at most $\mathrm{\parallel }{\sum }_j{q}_j{D}^{(j)}{\mathrm{\parallel }}_2^2$ because all pairwise coordinate inner products are nonnegative. Dividing by $s$ shows some $j\in L$ with positive weight has both entropy drop at least $1\mathrm{/}4$ and $\mathrm{\parallel }{D}^{(j)}{\mathrm{\parallel }}_2\le R\mathrm{\parallel }D{\mathrm{\parallel }}_2$, where $R=4\sqrt{m}\ln m$.

Start from the uniform distribution $D^{(0)}$ on $[N]$, of norm $N^{-1\mathrm{/}2}$. While the norm is at most $0.1$, step 2.1 selects a child with entropy reduced by at least $1\mathrm{/}4$ and norm multiplied by at most $R$. Since the initial entropy is at most $\ln m$, after at most $K=\lfloor 4\ln m\rfloor +1$ such reductions the entropy would be negative; therefore either $N<100$ initially, or some $D^{(k)}$ with $k\le K$ has norm greater than $0.1$. In the latter case $0.1<N^{-1\mathrm{/}2}{R}^K$, so $N<100R^{2K}$.

For $m\ge 2$, $K\le 5.45\ln m$, $\ln R=\ln 4+\frac{1}{2}\ln m+\ln \ln m\le 3.5\ln m$, and $\ln 100\le 9.6(\ln m{)}^2$. Thus $\ln (100R^{2K})\le 47.8(\ln m{)}^2<60(\ln m{)}^2$. The initial case $N<100$ also satisfies this bound. Therefore $N\le \exp (60(\ln m{)}^2)$.