Let \(W' = \{ V(\mathcal{V}) : \mathcal{V}\in W\} \). Since \(V(\mathcal{V})\) retains all of \(\mathcal{V}\) up to ordering, \(|W| \leq r!\, |W'|\). We bound \(|W'|\).

Fix \(V \in W'\) and write \(V = B + E\) where \(B \in \{ 0,1\} ^{n\times n_0}\) is the parity matrix and \(E\) has all entries even. The total entry-sum of \(V\) is \(r\); write \(p = r/N\), so the entry-sum is \(Np\). For \(0 \leq m \leq Np\) let \(W'_m\) be the set of \(V = B+E \in W'\) with \(\| B\| = m\). We count the choices of \(E\) and \(B\) separately.

Choosing \(E\). The matrix \(E\) has entry-sum \(Np - m\). Each nonzero entry of \(E\) is even, hence \(\geq 2\), so \(E\) has at most \(\frac{Np-m}{2}\) nonzero entries. The number of ways to choose their positions is at most \(\sum _{t=0}^{(Np-m)/2}\binom {N}{t} \leq 2^{N\cdot h_2\left(\frac{Np-m}{2N}\right)}\) by Lemma 32. Given the positions, the number of even value-assignments is at most \(\binom {\frac{Np-m}{2}+Np-m-1}{Np-m}\leq 2^{3Np/2}\) by Lemma 37.

Choosing \(B\). Let \(I = \{ i \in [n] : B_i \neq 0\} \) be the set of nonzero rows; the number of choices of \(I\) is at most \(2^n\). Write \(|I| = \gamma n\). Given \(m\) and \(I\), we claim there are at most \(2^{N\gamma (h_2(m/\gamma N) - \varepsilon + 1/\sqrt{n_0})}\) choices for \(B\). Indeed, every row of \(B\) must lie in \(\mathcal{C}_{\mathrm{in}}^\perp \). Let \(B'\) be a uniformly random matrix among those of weight \(m\) whose nonzero rows are exactly \(I\); the number of such matrices is at most \(\binom {n_0|I|}{m} = \binom {\gamma n n_0}{m}\leq 2^{\gamma Nh_2(m/\gamma N)}\). Conditioning on the weight \(w\) of each row, \(\tau \)-niceness with \(\tau = 1/\sqrt{n_0}\) gives, for each \(i \in I\),

Since the rows are independent under this conditioning, the probability that all \(\gamma n\) nonzero rows of \(B'\) lie in \(\mathcal{C}_{\mathrm{in}}^\perp \) is at most \(2^{\gamma n(-n_0\varepsilon + \sqrt{n_0})} = 2^{\gamma N(-\varepsilon + 1/\sqrt{n_0})}\) (using \(n\sqrt{n_0} = N/\sqrt{n_0}\)). Multiplying the count of weight-\(m\) matrices by this probability proves the claim.

Combining. Writing \(m = \alpha N\) and combining the bounds,

Using \(h_2(x) \leq -x\log _2 x + 2x\) (Lemma 34) and optimising over \(\gamma \) (the choice \(\gamma = \alpha /(\varepsilon \ln 2)\) maximises the bracket) gives, after simplification,

The last expression is maximised at \(\alpha = \max \{ p - \varepsilon ^2/e, 0\} \): its derivative in \(\alpha \) is \(\frac{1}{2\ln 2}\big(1 + \ln \frac{p-\alpha }{ \varepsilon ^2}\big)\), which is negative throughout \([0,p]\) when \(p {\lt} \varepsilon ^2/e\) (so the max is at \(\alpha = 0\)), and vanishes at \(\alpha = p - \varepsilon ^2/e\) when \(p \geq \varepsilon ^2/e\). Plugging in each case yields

Therefore, summing over \(0 \leq m \leq Np\) and using \(|W| \leq r!\, |W'| \leq (Np)!\sum _{m}|W'_m|\),

where we substituted \(p = r/N\) and used \(n = N/n_0 \leq N/\sqrt{n_0}\).

Choose \(r = \varepsilon ^2 N\) (the smallest even integer larger than \(\varepsilon ^2 N\); assume WLOG equality). By Lemma 40, for any fixed \(\mathcal{C}_{\mathrm{in}}\) (hence fixed \(\Omega \)),

Take the expectation over the random \(\mathcal{C}_{\mathrm{out}}\). Since \(\mathcal{C}_{\mathrm{out}}^\perp \) is a random linear code of dimension \(n-k\), for any fixed \(\mathcal{V}\), \(\Pr _{\mathcal{C}_{\mathrm{out}}}[g_\mathcal{V}\in \mathcal{C}_{\mathrm{out}}^\perp ] = 1\) if \(g_\mathcal{V}= 0\) and \(\frac{q^{n-k}-1}{q^n-1}\) otherwise. Hence

Now \(g_\mathcal{V}= 0\) iff every row of \(B(\mathcal{V})\) is a left-kernel vector of \(G_0\), i.e. iff every row of \(B(\mathcal{V})\) lies in \(\mathcal{C}_{\mathrm{in}}^\perp \), i.e. iff \(\mathcal{V}\in W\) as in Claim 42. Thus \(\sum _\mathcal{V}\mathbf{1}[g_\mathcal{V}=0] = |W|\), and Claim 42 with \(r = \varepsilon ^2 N\) (so \(r/N = \varepsilon ^2\) and \(\max \{ 1,(re/\varepsilon ^2 N)^{r/2}\} = e^{r/2}\)) gives

using \(q \geq 2^{\tilde c/\varepsilon ^3} \Rightarrow n_0 \geq \tilde c/\varepsilon ^4\) (so \(2N/\sqrt{n_0}\leq 2N\varepsilon ^2/\sqrt{\tilde c}\)) and WLOG \(\tilde c \geq 1\) so that \(8\sqrt e\cdot 2^{2/\sqrt{\tilde c}}\leq 32\sqrt e\).

By Markov’s inequality (Lemma 23), using that \(r\) is even so \(X_m^r = |X_m|^r\), and \(q^k = 2^{N\varepsilon ^2} = 2^r\),

Plugging in (10) gives \(\big(\frac{64\sqrt e\, N\varepsilon }{c\varepsilon N}\big)^r\cdot N = (\frac{64\sqrt e}{c})^r\cdot N\). Choosing \(c = 128\sqrt e\) yields \(\Pr _\mathcal{C}_{\mathrm{out}}[\exists m\neq 0,\ X_m {\gt} c\varepsilon N]\leq N\cdot 2^{-r} = N\cdot 2^{-N\varepsilon ^2}\). Since \(n_0 \geq \tilde c/\varepsilon ^4\) implies \(n_0 \leq 2^{n_0\varepsilon ^2}\) (for small \(\varepsilon \)) and hence \(N = n n_0 \leq 2^{N\varepsilon ^2}\), for sufficiently large \(N\) we have \(N \leq 2^{N\varepsilon ^2/2}\), so the probability is at most \(2^{-N\varepsilon ^2/2} \leq 2^{-\varepsilon ^2 N/\bar c}\) for \(\bar c \geq 2\). When no message has \(X_m {\gt} c\varepsilon N\), every nonzero codeword of \(\mathcal{C}\) has weight at least \(\frac12 - c\varepsilon \) times \(N\) (by Definition 39), so the relative distance is at least \(\frac12 - c\varepsilon \).