By Lemma 40, \(\mathbb {E}_{m}[X_m^r] = \frac{1}{q^k-1} \sum _\mathcal{V}(q^k\mathbf{1}[g_\mathcal{V}\in \mathcal{C}_{\mathrm{out}}^\perp ]-1)\). For \(r\) even, \(X_m^r = |X_m|^r\), and Markov’s inequality (Lemma 23) gives \(\Pr _m[|X_m|\geq c\varepsilon N] = \Pr _m[X_m^r \geq (c\varepsilon N)^r]\leq \frac{1}{q^k}\mathcal{B}_r(\mathcal{C}_{\mathrm{out}},\mathcal{C}_{\mathrm{in}})\). The number of bad \(m\) equals \((q^k-1)\Pr _m[|X_m|\geq c\varepsilon N]\leq \frac{q^k-1}{q^k} \mathcal{B}_r(\mathcal{C}_{\mathrm{out}},\mathcal{C}_{\mathrm{in}})\leq \mathcal{B}_r(\mathcal{C}_{\mathrm{out}},\mathcal{C}_{\mathrm{in}})\).

View choosing the \((\alpha _i,b_i)\) as dropping \(r\) balls into the \(N = |[n]\times \Omega |\) bins. Since \(r \sim \operatorname {Poi}(\tilde c\varepsilon ^2 N)\), by Poisson splitting (Lemma 30) the occupancy \(Y_{\alpha ,b}\) of each bin \((\alpha ,b)\) is independent and distributed as \(\operatorname {Poi}(\tilde c\varepsilon ^2)\). Since \(Y_{\alpha ,b}\) is the number of times \(b\) appears in \(\mathcal{V}_\alpha \), working over a field of characteristic \(2\) we have \(g_\alpha = \sum _b Y_{\alpha ,b}\, b = \sum _b \zeta _{\alpha ,b}\, b\) with \(\zeta _{\alpha ,b} = Y_{\alpha ,b}\bmod 2\). The \(\zeta _{\alpha ,b}\) are independent, and by Lemma 29, \(\Pr [\zeta _{\alpha ,b} = 1] = \Pr [Y_{\alpha ,b}\text{ odd}] = \frac12(1 - e^{-2\tilde c\varepsilon ^2})\).

For fixed \(r\), the event \(g = 0\) is exactly that all rows of \(B(\mathcal{V})\) lie in \(\mathcal{C}_{\mathrm{in}}^\perp \), so by Claim 42 (dividing the bound on \(|W|\) by \(N^r\)),

Let \(\lambda = \tilde c\varepsilon ^2 N\) be the Poisson mean. Taking the expectation over \(r \sim \operatorname {Poi}(\lambda )\) and using the Poisson pmf (Lemma 26),

Splitting the sum at \(r = \varepsilon ^2 N/e\): the first part (where the maximum is \(1\)) is bounded, using \(r \leq \varepsilon ^2 N/e\), by \(\sum _{r}\frac{1}{r!}\big(\frac{8\lambda \sqrt{\varepsilon ^2/e}}{c\varepsilon }\big)^r = \exp (\frac{8}{c\sqrt e}\lambda )\). The second part (where the maximum is \(\frac{er}{\varepsilon ^2 N}\)), using \(r! \geq (r/e)^r\), is bounded by \(\sum _{r {\gt} \varepsilon ^2 N/e}\big(\frac{8e\sqrt e\, \tilde c}{c}\big)^r \leq 2^{-\varepsilon ^2 N/e} {\lt} 1\) provided \(c \geq 16 e\sqrt e\, \tilde c\). Hence

using \(q^k = 2^{\varepsilon ^2 N}\), \(\lambda = \tilde c\varepsilon ^2 N\), the hypotheses \(\tilde c \geq 4\ln 2\), \(c \geq 16\), and finally \(n_0 \geq 64/\varepsilon ^4\). The factor \(1 + \frac{1}{q^k-1}\leq 2\) only changes the constant.

The rate is \(\varepsilon ^2\) by construction, so we bound the distance via the number of bad messages. By Observation 46 it suffices to find \(r\) with \(\mathcal{B}_r(\mathcal{C}_{\mathrm{out}},\mathcal{C}_{\mathrm{in}}) {\lt} 1\), since then there are no bad messages and the relative distance is at least \(\frac{1-c\varepsilon }{2}\) (Definition 44). Choose \(r \sim \operatorname {Poi}(\lambda )\) with \(\lambda = \tilde c\varepsilon ^2 N\). Splitting (12) into the events \(g = 0\) and \(g \neq 0\) gives \(\mathcal{B}_r(\mathcal{C}_{\mathrm{out}},\mathcal{C}_{\mathrm{in}}) = (13) + (14)\) with \((13)\) as in Claim 49 and

By Claim 49, \(\mathbb {E}_r[(13)]\leq 2^{-\varepsilon ^2 N/2}\), so by Markov’s inequality, with probability at least \(1 - 2^{-\varepsilon ^2 N/4}\) over \(r\),

For \((14)\): by Claim 48, when \(r \sim \operatorname {Poi}(\lambda )\) the distribution \(\mathcal{D}_r\) equals the product distribution \(\mathcal{D}^n\) of the theorem, so by hypothesis (11), \(q^k\Pr _{r\sim \operatorname {Poi}(\lambda ),g\sim \mathcal{D}_r}[g\in \mathcal{C}_{\mathrm{out}}^\perp \setminus \{ 0\} ] - 1 \leq \Delta \leq (\frac{c\varepsilon }{2})^{\lambda + 100\sqrt\lambda }\). By the Poisson Chernoff bound (Lemma 31), \(\Pr [r \geq \lambda + 100\sqrt\lambda ]\leq \exp (-100^2/2)\). Union bounding over (15) and the event \(r \leq \lambda + 100\sqrt\lambda \), with positive probability over \(r\) we have

using \(r \leq \lambda + 100\sqrt\lambda \) and \(c\varepsilon {\lt} 1\) so that \((\frac{1}{c\varepsilon })^r(\frac{c\varepsilon }{2})^{\lambda +100\sqrt\lambda } \leq 2^{-(\lambda +100\sqrt\lambda )}\leq 2^{-\lambda }\). Thus some \(r\) gives \(\mathcal{B}_r {\lt} 1\), proving the theorem.

Let \(\mathcal{C}_{\mathrm{out}}\) be a random linear code of dimension \(k = \varepsilon n\). Then \(\mathcal{C}_{\mathrm{out}}^\perp \) is a random linear code of dimension \(n - k\), and for each fixed nonzero \(x\), \(\Pr _\mathcal{C}_{\mathrm{out}}[x\in \mathcal{C}_{\mathrm{out}}^\perp ] = \frac{q^{n-k}-1}{q^n-1}\leq q^{-k}\). Taking the expectation over \(\mathcal{C}_{\mathrm{out}}\),

Hence some fixed \(\mathcal{C}_{\mathrm{out}}\) of dimension \(k\) achieves \(\Pr _{x\sim \mathcal{D}^n}[x\in \mathcal{C}_{\mathrm{out}}^\perp \setminus \{ 0\} ]\leq q^{-k}\), i.e. (11) with \(\Delta = 0\) (the condition only requires this probability not be much larger than \(1/q^k\)).