3 A Useful Moment Computation

Throughout this chapter \(\mathcal{C}_{\mathrm{out}}\subseteq \mathbb {F}_q^n\) and \(\mathcal{C}_{\mathrm{in}}\subseteq \mathbb {F}_2^{n_0}\) are fixed linear codes of rate \(\varepsilon \) (with \(q = 2^{k_0}\), \(k = \varepsilon n\), \(k_0 = \varepsilon n_0\), \(N = n_0 n\)); the only randomness is in a uniform nonzero message \(m \in \mathbb {F}_q^k \setminus \{ 0\} \).

Definition 38 The set \(\Omega \), Definition 3.1

Let \(G_0 \in \mathbb {F}_2^{n_0 \times k_0}\) be a generator matrix of \(\mathcal{C}_{\mathrm{in}}\), so that \(\mathcal{C}_{\mathrm{in}}= \{ G_0 x : x \in \mathbb {F}_2^{k_0}\} \). Let \(\Omega \subseteq \mathbb {F}_2^{k_0}\) be the set of rows of \(G_0\), so \(|\Omega | = n_0\). Identifying \(\mathbb {F}_2^{k_0}\) with \(\mathbb {F}_q\) via a self-dual basis, we also view \(\Omega \subseteq \mathbb {F}_q\). We call \(\Omega \) the set derived from \(\mathcal{C}_{\mathrm{in}}\).

Definition 39 Bias variable \(X_m\), Definition 3.2

For a message \(m \in \mathbb {F}_q^k\), define

\[ X_m \triangleq \sum _{\alpha \in [n]}\sum _{b \in \Omega } (-1)^{\langle \mathcal{C}_{\mathrm{out}}(m)_\alpha , b\rangle } . \]

Then \(X_m\) is the bias (number of zeros minus number of ones) of the codeword \(\mathcal{C}(m) = (\mathcal{C}_{\mathrm{out}}\circ \mathcal{C}_{\mathrm{in}})(m)\): the weight of \(\mathcal{C}(m)\) is at least \(\frac12 - O(\varepsilon )\) iff \(X_m = O(\varepsilon N)\). For an ordered list \(\mathcal{V}\) of pairs in \([n]\times \Omega \) and \(\alpha \in [n]\), let \(\mathcal{V}_\alpha \) be the multiset \(\{ b : (\alpha ,b) \in \mathcal{V}\} \) (with multiplicity).

Lemma 40 Moment formula, Lemma 3.3

Suppose \(\Omega \) is derived from \(\mathcal{C}_{\mathrm{in}}\). For every integer \(r \geq 1\),

\[ \mathbb {E}_{m \sim \mathbb {F}_q^k \setminus \{ 0\} }\! \big[X_m^r\big] = \frac{1}{q^k - 1}\sum _{\mathcal{V}\in ([n]\times \Omega )^r} \Big(q^k\cdot \mathbf{1}\big[g_\mathcal{V}\in \mathcal{C}_{\mathrm{out}}^\perp \big] - 1\Big), \]

where \(\mathcal{V}\) ranges over tuples \(((\alpha _1,b_1),\dots ,(\alpha _r,b_r))\) and \(g_\mathcal{V}\in \mathbb {F}_q^n\) is defined by \((g_\mathcal{V})_\alpha = \sum _{b \in \mathcal{V}_\alpha } b\).

Proof ▶

Expanding the \(r\)-th power,

\[ X_m^r = \sum _{\mathcal{V}= ((\alpha _1,b_1),\dots ,(\alpha _r,b_r))} \prod _{j=1}^r (-1)^{\langle \mathcal{C}_{\mathrm{out}}(m)_{\alpha _j}, b_j\rangle } . \]

Taking the expectation over \(m \in \mathbb {F}_q^k \setminus \{ 0\} \) and grouping the \(b_j\) by their coordinate \(\alpha \),

\begin{equation} \mathbb {E}_{m}[X_m^r] = \frac{1}{q^k-1}\sum _{m \neq 0}\sum _\mathcal{V}\prod _{\alpha \in [n]}(-1)^{\langle \mathcal{C}_{\mathrm{out}}(m)_\alpha , \sum _{b\in \mathcal{V}_\alpha }b\rangle }, \tag {4} \end{equation}

with the convention \(\sum _{b \in \mathcal{V}_\alpha } b = 0\) when \(\mathcal{V}_\alpha \) is empty. For \(\alpha \in [n]\) set \(\varphi _\alpha (x) = (-1)^{\langle x, \sum _{b\in \mathcal{V}_\alpha }b\rangle }\). Its Fourier transform over \(\mathbb {F}_2^{k_0}\) (Definition 20) is

\[ \widehat{\varphi _\alpha }(w) = \frac{1}{q}\sum _{x \in \mathbb {F}_2^{k_0}} (-1)^{\langle x, \sum _{b\in \mathcal{V}_\alpha }b\rangle + \langle w, x\rangle } = \mathbf{1}\Big[w = \sum _{b\in \mathcal{V}_\alpha }b\Big]. \]

Write \(\overline{m} = \mathcal{C}_{\mathrm{out}}(m)\). Substituting via Fourier inversion (Lemma 21) and exchanging the product and sum over \(g : [n] \to \mathbb {F}_2^{k_0}\),

\[ \mathbb {E}_m[X_m^r] = \frac{1}{q^k-1}\sum _{m\neq 0}\sum _\mathcal{V}\sum _{g \in \mathbb {F}_q^n} \Big(\prod _\alpha \widehat{\varphi _\alpha }(g_\alpha )\Big) \Big(\prod _\alpha (-1)^{\langle g_\alpha , \overline{m}_\alpha \rangle }\Big). \]

Moving the sum over \(m\) inside,

\begin{equation} \mathbb {E}_m[X_m^r] = \frac{1}{q^k-1}\sum _\mathcal{V}\sum _{g\in \mathbb {F}_q^n} \Big(\prod _\alpha \widehat{\varphi _\alpha }(g_\alpha )\Big) \Big(\sum _{m\neq 0}(-1)^{\langle g, \overline{m}\rangle }\Big). \tag {5} \end{equation}

Now by Lemma 22 applied to \(V = \mathcal{C}_{\mathrm{out}}\) (so \(|\mathcal{C}_{\mathrm{out}}| = q^k\)),

\begin{equation} \sum _{m \in \mathbb {F}_q^k \setminus \{ 0\} }(-1)^{\langle g, \overline{m}\rangle } = q^k\cdot \mathbf{1}[g \in \mathcal{C}_{\mathrm{out}}^\perp ] - 1, \tag {6} \end{equation}

since \(\sum _{m \in \mathbb {F}_q^k}(-1)^{\langle g, \overline{m}\rangle } = q^n \widehat{\mathbf{1}_{\mathcal{C}_{\mathrm{out}}}}(g) = |\mathcal{C}_{\mathrm{out}}|\mathbf{1}_{\mathcal{C}_{\mathrm{out}}^\perp }(g) = q^k \mathbf{1}_{\mathcal{C}_{\mathrm{out}}^\perp }(g)\) and we subtract the \(m=0\) term, which equals \(1\). Plugging (6) into (5),

\begin{equation} \mathbb {E}_m[X_m^r] = \frac{1}{q^k-1}\sum _\mathcal{V}\sum _{g\in \mathbb {F}_q^n} \Big(\prod _\alpha \widehat{\varphi _\alpha }(g_\alpha )\Big) \big(q^k\mathbf{1}[g\in \mathcal{C}_{\mathrm{out}}^\perp ]-1\big). \tag {7} \end{equation}

Finally \(\prod _\alpha \widehat{\varphi _\alpha }(g_\alpha ) = \mathbf{1}[\forall \alpha ,\ g_\alpha = \sum _{b\in \mathcal{V}_\alpha }b] = \mathbf{1}[g = g_\mathcal{V}]\), so the only surviving \(g\) is \(g_\mathcal{V}\), yielding the claimed formula.