A sparse Hamming packing for every $1\le k\le d\mathrm{/}2$

Put $\mathcal{W}=[m{]}^k$ and fix a bijection from the finite initial segment of size $m^k$ onto $\mathcal{W}$, whose existence is [F2]. Scan that finite segment in its natural order, retaining a word exactly when its Hamming distance from every previously retained word is greater than $r$. The scan terminates; its retained set $\mathcal{C}$ has pairwise distances greater than $r$, and every word not retained lies in a radius-$r$ ball about an earlier retained word.

A Hamming ball of radius $r$ has cardinality $B={\sum }_{j=0}^r\left(\genfrac{}{}{0px}{}{k}{j}\right)(m-1{)}^j$: choose the $j$ coordinates that differ and then one of the other $m-1$ symbols at each such coordinate; different values of $j$ give disjoint sets, so [F3] counts the union.

Regard natural quantities as their real images under ${\iota }_{\mathbb{R}}$ as fixed in [F2]. Since $m\ge 2$ and $j\le r\le k\mathrm{/}4$, $\log ({\iota }_{\mathbb{R}}(m)-1)\ge 0$, and the natural-power bridge in [F2] and the integer-power identity in [F5] give ${\iota }_{\mathbb{R}}((m-1{)}^j)=\exp ({\iota }_{\mathbb{R}}(j)\log ({\iota }_{\mathbb{R}}(m)-1))\le \exp (({\iota }_{\mathbb{R}}(k)\mathrm{/}4)\log ({\iota }_{\mathbb{R}}(m)-1))$. Put $q=1\mathrm{/}4$ and $h=-q\log q-(1-q)\log (1-q)=\frac{1}{2}\log 2+\frac{3}{4}\log (4\mathrm{/}3)$. The binomial weight $q^j(1-q{)}^{k-j}$ equals $\exp ({\iota }_{\mathbb{R}}(j)\log q+({\iota }_{\mathbb{R}}(k)-{\iota }_{\mathbb{R}}(j))\log (1-q))$; its exponent decreases with $j$ because $\log q-\log (1-q)=\log (1\mathrm{/}3)<0$. Hence for every $j\le r\le k\mathrm{/}4$ this weight is at least $\exp (({\iota }_{\mathbb{R}}(k)\mathrm{/}4)\log q+(3{\iota }_{\mathbb{R}}(k)\mathrm{/}4)\log (1-q))=\exp (-{\iota }_{\mathbb{R}}(k)h)$. Applying [F4] and retaining only $j\le r$ gives ${\sum }_{j=0}^r{\iota }_{\mathbb{R}}\text{\hspace{0.17em}⁣}\left(\genfrac{}{}{0px}{}{k}{j}\right)\le \exp ({\iota }_{\mathbb{R}}(k)h)$. Since ${\iota }_{\mathbb{R}}$ preserves finite sums, products and natural powers, the ball count then satisfies ${\iota }_{\mathbb{R}}(B)\le \exp ({\iota }_{\mathbb{R}}(k)h+({\iota }_{\mathbb{R}}(k)\mathrm{/}4)\log ({\iota }_{\mathbb{R}}(m)-1))$.

Each greedy selection deletes at most $B$ words and all $m^k$ words are eventually deleted. Thus the natural counts satisfy $\mathrm{\mid }\mathcal{C}\mathrm{\mid }B\ge m^k$. The code is nonempty and $B\ge 1$, so after applying ${\iota }_{\mathbb{R}}$ all logarithms below have positive arguments; [F2] gives ${\iota }_{\mathbb{R}}(\mathrm{\mid }\mathcal{C}\mathrm{\mid }){\iota }_{\mathbb{R}}(B)\ge {\iota }_{\mathbb{R}}(m{)}^k$. Combining this with step 2.1 and the logarithm product and integer-power identities in [F5] yields $\log {\iota }_{\mathbb{R}}(\mathrm{\mid }\mathcal{C}\mathrm{\mid })\ge {\iota }_{\mathbb{R}}(k)f({\iota }_{\mathbb{R}}(m))$, where $f(t)=\log t-\frac{1}{4}\log (t-1)-h$ for real $t\ge 2$.

If $m=2$, then $f(2)=\frac{1}{2}\log 2-\frac{3}{4}\log (4\mathrm{/}3)>1\mathrm{/}24$: the lower right-endpoint sum on $[1,2]$ gives $\log 2>\frac{1}{2}(2\mathrm{/}3+1\mathrm{/}2)=7\mathrm{/}12$, while $\log (4\mathrm{/}3)={\int }_1^{4\mathrm{/}3}dt\mathrm{/}t<1\mathrm{/}3$. By [F1] and [F2], ${\iota }_{\mathbb{R}}(d)\mathrm{/}{\iota }_{\mathbb{R}}(k)<3$ and $\log (e{\iota }_{\mathbb{R}}(d)\mathrm{/}{\iota }_{\mathbb{R}}(k))=1+\log ({\iota }_{\mathbb{R}}(d)\mathrm{/}{\iota }_{\mathbb{R}}(k))<1+\log 3<3$, since $\log 3={\int }_1^{3}dt\mathrm{/}t<2$; also $1\mathrm{/}24>3\mathrm{/}1024$. Hence $f({\iota }_{\mathbb{R}}(m))>\frac{1}{1024}\log (e{\iota }_{\mathbb{R}}(d)\mathrm{/}{\iota }_{\mathbb{R}}(k))$.

For real $t\ge 3$, monotonicity of $\log$ gives $f(3)=\log 3-\frac{3}{4}\log (8\mathrm{/}3)>\frac{1}{4}\log 3>7\mathrm{/}48$, since $3>8\mathrm{/}3$ and step 4.1 gives $\log 3>\log 2>7\mathrm{/}12$. The chain and algebra rules in [F5] give $f^{\mathrm{\prime }}(t)=1\mathrm{/}t-1\mathrm{/}(4(t-1))\ge 1\mathrm{/}(4t)$ and $\frac{d}{dt}\{(1\mathrm{/}1024)(1+\log (4t\mathrm{/}3))\}=1\mathrm{/}(1024t)$, so the derivative of their difference is at least $255\mathrm{/}(1024t)>0$. The mean value theorem in [F5] makes $f(t)-(1\mathrm{/}1024)(1+\log (4t\mathrm{/}3))$ increasing for $t\ge 3$. At $t=3$, it exceeds $7\mathrm{/}48-4\mathrm{/}1024>0$, since $\log 4={\int }_1^{4}dt\mathrm{/}t<3$. Since $m\ge 3$, take $t={\iota }_{\mathbb{R}}(m)$. The division identity gives ${\iota }_{\mathbb{R}}(d)\mathrm{/}{\iota }_{\mathbb{R}}(k)<{\iota }_{\mathbb{R}}(m)+1\le 4{\iota }_{\mathbb{R}}(m)\mathrm{/}3$, so $f({\iota }_{\mathbb{R}}(m))\ge (1\mathrm{/}1024)\log (e{\iota }_{\mathbb{R}}(d)\mathrm{/}{\iota }_{\mathbb{R}}(k))$.

Steps 3.1, 4.1, and 5.1 prove the claimed cardinality bound. Index the coordinates by $[d]=\{0,1,\dots ,d-1\}$ and map each word to the vector specified in the Statement; the first $km$ coordinates contain the $k$ blocks because $km\le d$ by [F1]. Each word gives one nonzero coordinate in each block, so $u^{\omega }$ has exactly $k$ ones. If two words differ in $s$ blocks, their vectors differ in exactly two coordinates per such block. Since $s>r$, discreteness of $\mathbb{N}$ gives $s\ge r+1$, and [F1] gives $k<4(r+1)$; after applying the order-preserving map in [F2], ${\iota }_{\mathbb{R}}(s)\ge {\iota }_{\mathbb{R}}(r)+1>{\iota }_{\mathbb{R}}(k)\mathrm{/}4$. Therefore $\mathrm{\parallel }{u}^{\omega }-u^{{\omega }^{\mathrm{\prime }}}{\mathrm{\parallel }}_2^2=2{\iota }_{\mathbb{R}}(s)>{\iota }_{\mathbb{R}}(k)\mathrm{/}2$.