As in Theorem 43 we work with codes whose weight distribution deviates only slightly from that of a uniformly random code, but here we need both an upper and a lower bound on the \(\Delta _i\).

Write \(p = 2^{-(n-k)}\) and \(p' = 2^{-(n-k)}(1 - 2^{-k})\). For \(1 \leq i \leq n\), \(\binom {n}{i}p' \leq \mathbb {E}_\mathcal{C}[\Delta _i] = \binom {n}{i}\frac{2^k-1}{2^n-1}\leq \binom {n}{i}p\), and \(\operatorname {Var}_\mathcal{C}[\Delta _i]\leq \binom {n}{i}p\) by the negative correlation of distinct nonzero vectors (Lemma 19). Fix \(\tau {\gt} 0\). Markov (Lemma 23) gives \(\Pr [\Delta _i \geq 2^{\tau n}\binom {n}{i}p]\leq 2^{-\tau n}\), and Chebyshev (Lemma 24) gives \(\Pr [\Delta _i \leq \binom {n}{i}p/2^{\tau n}]\leq \frac{1}{(1 - 2^{-\tau n} - 2^{-k})^2\binom {n}{i}p}\). Fixing \(1 \leq \ell \leq n/2\) and union bounding (Lemma 25), with probability at least \(1 - \frac{n}{2^{\tau n}} - \frac{n}{(1 - 2^{-\tau n} - 2^{-k})^2\binom {n}{\ell }p}\),

Choosing \(\tau = \min \big\{ \frac18\gamma ^2(h_2^{-1}(1 - k/n))^2, \frac{k\gamma }{n} - \frac{\log n}{n}\big\} \) and \(\ell = \lfloor h_2^{-1}(1 - \frac23\frac{k}{n})n\rfloor \), the failure probability is \(2^{-\Omega (\gamma k + \gamma ^2 n + \sqrt n)}\), using \(h_2^{-1}(1-x)\geq \frac12 - 5x^2\) (Lemma 36) to lower bound \(h_2^{-1}(1 - k/n)\geq \frac14\) from \(k \leq n/5\), and the bounds \(\binom {n}{\ell }p \geq 2^{k/4}\) from \(k\) large.

Item 1. Equation (19) makes \(\mathcal{C}^\perp \) effectively \(\tau \)-nice, and by (19), to bound \(j^\star \) it suffices to solve \(\sum _{i=0}^j\binom {n}{i} 2^{-(n-k-\tau n)}\geq T\) for \(j\). Writing \(j = \alpha n\) and using \(\sum _{i\leq \alpha n}\binom {n}{i}\leq 2^{nh_2(\alpha )}\) (Lemma 32; sharpened to \(2^{h_2(\alpha )n - \frac12 \log n - 1}\)), the smallest such \(\alpha \) satisfies \(\alpha \geq h_2^{-1}\big(1 - \tau - \frac{k - \log T + \log n}{n}\big)\geq h_2^{-1}\big(1 - 2\frac{k - \log T}{n}\big)\), using \(\tau \leq \frac{k\gamma }{n} - \frac{\log n}{n}\leq \frac{k - \log T - \log n}{n}\).

Item 2. Let \(j' = \lceil \alpha (1 - \gamma )n\rceil \). By (19), \(A \triangleq \sum _{i=0}^{j'-1}\Delta _i \leq \sum _{i=0}^{j'-1}\binom {n}{i} 2^{-(n-k+\tau n)}\leq 2^{n(h_2(\alpha (1-\gamma )) + \tau + k/n - 1)}\). By Item 1 and \(T \geq 2^{2k/3}\), \(j^\star = \alpha n \geq h_2^{-1}(1 - 2\frac{k-\log T}{n}) n \geq h_2^{-1}(1 - \frac23\frac{k}{n})n \geq \ell \), so (20) yields \(\Delta _{j^\star }\geq \binom {n}{j^\star }p\, 2^{-\tau n}\), hence \(B \triangleq \sum _{i=j'+1}^{j^\star }\Delta _i \geq \Delta _{j^\star }\geq 2^{n(h_2(\alpha ) - \frac{\log (2n)}{2n} - 1 + k/n - \tau )}\) (Lemma 33). Therefore

Now \(\frac{\log (A/B)}{n}\leq h_2(\alpha (1-\gamma )) - h_2(\alpha ) + 2\tau + \frac{\log (2n)}{2n}\leq h_2(\alpha (1-\gamma )) - h_2(\alpha ) + 4\tau \leq -(\alpha \gamma )^2 + 4\tau \leq -\frac12\gamma ^2(h_2^{-1}(1 - k/n))^2 \triangleq -\theta \), using \(h_2'\geq 0\), \(h_2''\leq -2\), Item 1, and the choice of \(\tau \). Hence \(\frac{\sum i\Delta _i}{\sum \Delta _i}\geq \frac{(1-\gamma )j^\star }{1 + 2^{-\theta n}}\geq (1-2\gamma )j^\star \), since \(2^{-\theta n}\leq \gamma \) from the lower bound on \(k\).

Item 3. For some \(\tau {\gt} 0\), (19) gives \(\Delta _{j^\star +1}\leq 2^{\tau n}\binom {n}{j^\star +1}p\) and (20) gives \(\Delta _{i}\geq 2^{-\tau n}\binom {n}{i}p\), with probability at least \(1 - \frac{1}{2^{\tau n}} - \frac{1}{(1 - 2^{-\tau n} - 2^{-k})^2\binom {n}{j^\star }p}\). Then

using \(j^\star \geq \frac14 n\). Setting \(\tau = \frac{1}{4\sqrt n}\) makes this at most \(2^{\sqrt n}\), and the success probability is at least \(1 - 2^{-\frac14\sqrt n} - \frac14 2^{-k/4}\), using \(\binom {n}{j^\star } 2^{-n+k}\geq 2^{-k/4}\).

Let \(\gamma = \bar c_\gamma \varepsilon \) and \(\eta = \bar c_\eta \varepsilon \). Since \(\mathcal{C}\) is linear it suffices to lower bound the weight of every nonzero codeword. Fix nonzero \(c \in \mathcal{C}_{\mathrm{out}}\) and consider \(w = (\mathcal{C}_{\mathrm{in}}(c_1),\dots ,\mathcal{C}_{\mathrm{in}}(c_n))\). Order \(\mathbb {F}_q= \{ \sigma _0,\dots ,\sigma _{q-1}\} \) with \(\Pr _{\mathcal{D}_c}[\sigma _0]\geq \cdots \geq \Pr _{\mathcal{D}_c}[\sigma _{q-1}]\) and set \(p_t(c) = \Pr _{\mathcal{D}_c}[\sigma _t]\).

Worst-case inner map. It suffices to lower bound \(\operatorname {weight}(w)\) under a worst-case (not necessarily linear) assignment of symbols of \(\mathbb {F}_q\) to codewords of \(\mathcal{C}_{\mathrm{in}}\): the most frequent symbols are mapped to the lowest-weight codewords. For \(j \in \{ 0,\dots ,n_0\} \) let \(\Delta _j = |\{ x\in \mathcal{C}_{\mathrm{in}}: \operatorname {weight}(x) = j\} |\) and \(\ell _j = \Delta _0 + \cdots + \Delta _j\) (with \(\ell _{-1} = 0\)). Assigning the symbols \(\{ \sigma _{\ell _{j-1}},\dots ,\sigma _{\ell _j - 1}\} \) to the weight-\(j\) codewords, the weight of \(w\) satisfies \(\operatorname {weight}(w)\geq d(c)\), where with \(d_{\mathrm{in}}\) the minimum distance of \(\mathcal{C}_{\mathrm{in}}\),

Worst-case distribution. Minimising over symbol distributions \(\mathbf p = (p_0\geq \cdots \geq p_{q-1}\geq 0)\) obeying the smoothed entropy constraint \(H_\infty ^\eta (\mathbf p)\leq b\) with \(b = (1-\gamma )\log q\),

The minimiser puts mass uniformly on the \(2^b\) lowest-weight symbols and shifts an \(\eta \)-fraction to the zero codeword’s symbol: \(p_t = \eta + 2^{-b}\) for \(t = 0\), \(p_t = 2^{-b}\) for \(1 \leq t \leq (1-\eta )2^b - 1\), and \(0\) otherwise. Set \(T = (1-\eta )2^b\), \(j^\star = \min \{ j \leq n_0 : \ell _j \geq T\} \), and define \(b'\) by \(\ell _{j^\star -1} = (1-\eta )2^{b'} \triangleq T'\). The worst case for \(b'\) is no better, and \(\frac{T}{T'}\leq 1 + \frac{\Delta _{j^\star }}{\ell _{j^\star -1}}\). Then

Applying Lemma 55. Apply Lemma 55 to \(\mathcal{C}_{\mathrm{in}}\) with this \(\gamma \) and \(T'\) (valid since \(\gamma \geq 8/\sqrt{n_0}\) and \(k_0 \geq 24\log n_0/\gamma \) by the lower bound on \(n_0\)). With probability \(1 - 2^{-\Omega (\gamma k_0 + \gamma ^2 n_0 + \sqrt{n_0})} = 1 - 2^{-\Omega _{\bar c_\gamma }(\varepsilon ^2 n_0 + \sqrt{n_0})}\) the conclusions hold. Item 1 gives \(j^\star - 1 = \alpha n_0\) with

using \(\log T - \log T'\leq \sqrt{n_0} + 1\) (Item 3), \(\log \frac{1}{1-\eta }\leq 2\eta \), \(n_0 \geq 4\varepsilon ^{-2}\), and \(h_2^{-1}(1 - x^2)\leq \frac12 - \frac{\sqrt{\ln 2}}{2}x\) (Lemma 35). Item 2 gives \(\sum _{j=0}^{j^\star -1}\Delta _j j\geq (1-2\gamma )(j^\star -1)\sum _{j=0}^{j^\star -1} \Delta _j\geq (1-2\gamma )\alpha n_0 T'\). Returning to (18),

using \(T' = (1-\eta )2^{b'}\). Since \(N = n_0 n\), the relative distance is at least

as desired.

For a fixed nonzero codeword, the probability that all \(n\) of its symbols fall inside a fixed set \(S \subseteq \mathbb {F}_q\) of size \(q^{1-\gamma }\) is at most \((|S|/q)^n = q^{-\gamma n}\); summing over the \(\binom {q}{q^{1-\gamma }}\) choices of \(S\) gives \(\sum _{i=1}^{q^{1-\gamma }}\binom {q}{i}(i/q)^n\approx q^{-\gamma (n - q^{1-\gamma })}\). Taking a union bound over the \(q^k = 2^{\varepsilon n\log q}\) nonzero codewords, with \(\gamma = \frac12\varepsilon \) and \(q = O(n)\), no nonzero codeword violates the constraint with high probability.