We use the probabilistic method. Let \(\bar c {\gt} 0\) be a large enough constant (to be fixed at the end of the proof), and set

We pick \(G = (L,R,E)\) to be a random bipartite graph with \(|L|=n\), \(|R|=m\): for every \(\ell \in L\) we pick \(c\) random (with replacement) vertices in \(R\) and connect them to \(\ell \) (this may produce a multigraph, but this is easily remedied afterwards without hurting the expansion).

Fix an integer \(1 \le j \le \lfloor \gamma n \rfloor \) and an arbitrary \(S \subseteq L\) of size exactly \(j\). Let \(r_1,\ldots ,r_{jc}\) denote the \(jc\) (ordered) random neighbor choices made by the \(j\) vertices of \(S\). Call a choice \(r_i\) (for \(i{\gt}1\)) a repeat if \(r_i \in \{ r_1,\ldots ,r_{i-1}\} \). If the total number of repeats is at most \(\varepsilon j c\), then \(|N(S)| \ge c(1-\varepsilon )j\), since at most \(\varepsilon jc\) of the \(jc\) edges out of \(S\) can fail to reach a ‘new’ vertex of \(R\).

For any fixed \(i\), the probability that \(r_i\) is a repeat is at most \(\frac{i-1}{m} \le \frac{jc}{m}\), since \(r_i\) is uniform on \([m]\) and there are at most \(i - 1 \le jc\) earlier choices. Taking a union bound over the (at most) \(\binom {cj}{\varepsilon jc}\) choices of which indices are repeats, and using that each repeat has probability at most \(jc/m\), we get

where the second inequality is the standard binomial coefficient bound \(\binom {a}{b}\le (ea/b)^b\), and the last inequality uses \(2e\gamma n = \varepsilon m /c\), i.e., \(ec/(\varepsilon m) \le 1/(2\gamma n)\), which holds by our choice of \(\gamma \).

Taking a union bound over all \(\binom {n}{j}\) choices of \(S\) of size \(j\), the probability that there exists some \(S\) of size \(j\) that fails to expand by a factor of \(c(1-\varepsilon )\) is at most

where the last inequality is verified below. Taking a union bound over all \(1 \le j \le \gamma n\), the probability that \(G\) fails to be an \((n,m,c,\gamma ,c(1-\varepsilon ))\) bipartite expander is strictly smaller than \(\sum _{j\ge 1} 2^{-j} = 1\); hence, with strictly positive probability, the random \(G\) is such a bipartite expander, so one exists, as desired.

It remains to verify \(\left(\frac{en}{j}\right)\cdot \left(\frac{j}{2\gamma n}\right)^{\varepsilon c} \le \frac12\) for every \(1 \le j \le \gamma n\). Since \(\varepsilon c {\gt} 1\) by our choice of \(c\), the left-hand side is increasing in \(j\), so it suffices to check the inequality at \(j = \gamma n\):

which holds if

This is satisfied by our choice of \(c\) for a large enough constant \(\bar c\) (the \(\log c\) term on the right grows much more slowly in \(\bar c\) than the left-hand side, so a sufficiently large constant \(\bar c\) makes the inequality hold for all \(n,m,\varepsilon \) in the relevant range). This completes the proof.

Let \(G = (L,R,E)\) and let us construct \(G' = (L,R',E')\) with the required properties. Define \(d = \left\lceil \frac{nc}{m}\right\rceil \). For each vertex \(r \in R\), let \(d_r\) be its degree. For each \(r \in R\), add \(\left\lceil \frac{d_r}{d}\right\rceil \) vertices to \(R'\); further, the \(d_r\) edges incident to vertex \(r\) are divided evenly among the corresponding \(\left\lceil \frac{d_r}{d}\right\rceil \) vertices in \(R'\) so that all but potentially one such vertex has degree exactly \(d\) (and at most one vertex has degree \({\lt} d\)).

The claim on the right degree bound in \(G'\) follows by construction. The claim on expansion follows since splitting the vertices this way can only increase vertex expansion: for any \(S \subseteq L\), \(N_{G'}(S)\) is the disjoint union of the split copies of the vertices in \(N_G(S)\), so \(|N_{G'}(S)| \ge |N_G(S)| \ge \alpha |S|\) whenever \(|S| \le \gamma n\).

It remains to show \(m' - m \le m\), where \(m' = |R'|\) and \(m = |R|\). We have

where the middle equality uses \(\sum _{r\in R} d_r = nc\) (both count the edges of \(G\)), and the last inequality follows from the definition of \(d\).

We inspect \(G\), the edge-vertex incidence graph of the double cover \(G'\) of \(X = (V,E)\), and state the expansion conditions of \(G\) in terms of the structure of \(X\). Let \(E'\) denote the edges of the double cover \(G'\) of \(X\), and thus the left vertices of \(G\); note \(|E'| = dn\). The right vertices of \(G\) correspond to the vertices of \(G'\); let \(V_1 \cup V_2\) denote these vertices, with \(|V_1| = |V_2| = n\), such that every left vertex of \(G\) has exactly one neighbor in each of \(V_1\) and \(V_2\). Thus \(G\) is indeed a graph with \(dn\) left vertices and \(2n\) right vertices that is \(2\)-left regular and \(d\)-right regular. It remains to show that sets containing at most \(\frac{\beta (\beta -\lambda )}{d^2}\) fraction of left vertices expand by a factor of at least \(2/\beta \). Specifically, let \(S \subseteq E'\) be an arbitrary set of left vertices of size at most \(\frac{\beta (\beta -\lambda )}{d^2}dn = \frac{\beta (\beta -\lambda )}{d}n\). Let \(N(S)\) denote the set of neighbors of \(S\) and let \(N(S) = A \cup B\) where \(A \subseteq V_1\) and \(B \subseteq V_2\). Our goal is to show \(|A|+|B| \ge (2/\beta )|S|\).

By the construction of \(G\), every vertex of \(S\) is an edge of \(X\) from the set \(A\) to the set \(B\). In particular \(|S| \le |E(A,B)|\), and so by the expander mixing lemma (Lemma 226) we have

We first argue \(|S| \le \beta \sqrt{|A||B|}\). Suppose for contradiction that \(|S| {\gt} \beta \sqrt{|A||B|}\). Then

Dividing both sides by \(\sqrt{|A||B|}\) and rearranging, \(\sqrt{|A||B|} {\gt} \frac{\beta -\lambda }{d}n\). Using \(|S| {\gt} \beta \sqrt{|A||B|}\) again, we get \(|S| {\gt} \frac{\beta (\beta -\lambda )}{d}n\), contradicting the given upper bound on \(|S|\). We conclude \(|S| \le \beta \sqrt{|A||B|}\).

Combining this with the AM-GM inequality \(\sqrt{|A||B|} \le (|A|+|B|)/2\) gives

and thus \(|A|+|B| \ge \frac{2}{\beta }|S|\), as desired. In other words, every set \(S\) with \(|S| \le \frac{\beta (\beta -\lambda )}{d^2}\cdot dn\) satisfies \(|N(S)| \ge \frac{2}{\beta }\cdot |S|\), so \(G\) is a \(d\)-right regular \(\left(dn,2n,2,\frac{\beta (\beta -\lambda )}{d^2},\frac{2}{\beta }\right)\)-expander.

Let \(U \subseteq N(S)\) be the unique neighbors of \(S\), i.e., those vertices in \(N(S)\) with exactly one neighbor in \(S\). We wish to show \(|U| \ge c(1-2\varepsilon )|S|\), which we do by counting the edges incident to \(S\).

The total number of edges going out of \(S\) is exactly \(c|S|\), since \(G\) is \(c\)-left regular. By the expansion property, \(|N(S)| \ge c(1-\varepsilon )|S|\). For every vertex \(v \in N(S)\), designate exactly one edge \((u,v)\) with \(u \in S\) as ‘special.’ The number of special edges is exactly \(|N(S)| \ge c(1-\varepsilon )|S|\), and so the number of non-special edges is at most \(\varepsilon c|S|\). Now note that if a vertex \(v \in N(S)\) is not a unique neighbor of \(S\) then \(v\) must have a non-special edge incident to it (since only one of the edges incident to it is special). So the total number of vertices in \(N(S)\) that are not unique neighbors is upper bounded by the number of non-special edges, which is at most \(\varepsilon c|S|\). Thus,

as desired.

This follows from the definition of \(C(G)\) as the code with parity check matrix \(A_G\) and the fact that \(c_j\) for every \(j \notin S\) does not contribute to any of the computed parities (each summand there is \(0\)).

The claim on the block length and the linearity of \(C(G)\) follows from the definition of expander codes. To lower bound the dimension, note that the space of codewords is the space of solutions to a homogeneous linear system over \(\mathbb {F}_2\) on \(n\) variables, namely \(c_1,\ldots ,c_n\), with \(n-k\) constraints, namely \(\sum _{\ell \in N(r)} c_\ell = 0\) for every \(r \in R\). The solution space has dimension \(k' \ge n - (n-k) = k\).

We now turn to showing that the distance of the code is at least \(\gamma n + 1\). For the sake of contradiction, assume that \(C(G)\) has distance at most \(\gamma n\). Then, by the linearity of \(C(G)\), there exists a non-zero codeword \(\mathbf{c} \in C(G)\) such that \(wt(\mathbf{c}) \le \gamma n\). Let \(S\) be the set of non-zero coordinates of \(\mathbf{c}\). Since \(G\) is an \((n,n-k,c,\gamma ,c(1-\varepsilon ))\) expander, by Lemma 234 we have

where the inequality follows from the fact that \(\varepsilon {\lt} \frac12\) and \(|S| \ge 1\) (since \(\mathbf{c}\) is non-zero). Thus \(U(S)\) is non-empty and so there exists \(r \in U(S)\). Let \(\ell \in S\) be the unique neighbor of \(r\) in \(S\) implied by the definition of \(U(S)\). Now the parity check corresponding to \(r\) is given by \(\sum _{\ell ' \in N(r) \cap S} c_{\ell '} = c_\ell = 1\) (where the first equality holds since \(N(r) \cap S = \{ \ell \} \) and the final equality holds since \(c_\ell = 1\) for \(\ell \in S\)). Thus the parity check condition corresponding to \(r\) is not satisfied, and so by Proposition 235 \(\mathbf{c} \notin C(G)\), a contradiction, as desired.

By Theorem 236, each \(C(G_i)\) is a \([n_i,k_i',\gamma n_i + 1]_2\) code for some \(k_i' \ge n_i - m_i\). Since \(m_i/n_i {\lt} 1-\rho \), the rate satisfies \(k_i'/n_i \ge (n_i - m_i)/n_i {\gt} \rho {\gt} 0\), bounded away from zero. Since \(\alpha {\gt} c/2\), the hypotheses of Theorem 236 apply to each \(G_i\) (with \(\varepsilon = 1-\alpha /c {\lt} 1/2\)), giving relative distance at least \(\gamma \), bounded away from zero. Hence \(\{ C(G_i)\} _{i\in \mathbb {Z}_+}\) is asymptotically good.

As in the proof of Theorem 236, for the sake of contradiction let us assume \(C(G)\) has distance \({\lt} 2\gamma (1-\varepsilon )n\). Then by linearity there exists a non-zero codeword \(\mathbf{c} \in C(G)\) with \(wt(\mathbf{c}) {\lt} 2\gamma (1-\varepsilon )n\). Let \(S\) be the set of non-zero coordinates of \(\mathbf{c}\); we will argue \(U(S) \ne \emptyset \), and then the rest of the argument proceeds exactly as in the proof of Theorem 236 to derive a contradiction.

If \(|S| \le \gamma n\), then we can just use the argument from the proof of Theorem 236. So let us assume there exists a subset \(T \subset S\) such that \(|T| = \gamma n\). Then, by Lemma 234,

Now, since the total number of edges emanating out of \(S\setminus T\) is at most \(c|S\setminus T|\), we have

where the last inequality follows from the facts that \(|S| {\lt} 2\gamma (1-\varepsilon )n\) and \(|T| = \gamma n\) (so \(|S \setminus T| {\lt} 2\gamma (1-\varepsilon )n - \gamma n\), and since \(\varepsilon {\lt} 1/2\) this quantity is at most \(2\gamma (1-2\varepsilon )n\), and more crudely bounded by \(2\gamma (1-\varepsilon )n\); the displayed chain reproduces the bound as stated in the book).

Now, note that

where the last inequality follows from combining the two displayed bounds above (both quantities are, up to the stated constants, \(c\gamma n\) times a factor depending on \(\varepsilon \), and the first dominates as \(\varepsilon \to 0\); this is exactly the computation carried out in the book). Hence \(U(S) \ne \emptyset \), and the argument concludes exactly as in the proof of Theorem 236.

For each \(u \in R\), the condition \(\mathbf{c}_{N(u)} \in C_0\) imposes \(d - \dim (C_0)\) independent linear constraints on the bits of \(\mathbf{c}\) (namely, the parity checks of \(C_0\) applied to \(\mathbf{c}_{N(u)}\)). Therefore, the condition that \(\mathbf{c}_{N(u)} \in C_0\) for all \(u \in R\) imposes a total of at most \(m(d - \dim (C_0))\) linear constraints on the coordinates of \(\mathbf{c}\), leaving \(X(G,C_0)\) as a space of dimension at least \(n - m(d-\dim (C_0))\). (Some of the \(m(d-\dim (C_0))\) constraints may be linearly dependent, but that only increases the dimension.)

We mimic the proof of Theorem 236 with modifications to exploit the fact that \(C_0\) has minimum distance \(\Delta \). Let the left vertices of \(G\) be \([n]\) and the right vertices be \([m]\). Let \(\mathbf{c} = (c_1,\ldots ,c_n) \in X(G,C_0)\) be a non-zero codeword and let \(S \subseteq [n]\) denote the set of non-zero coordinates of \(\mathbf{c}\), i.e., \(S = \{ i \in [n] \mid c_i \ne 0\} \). Now let \(W = N(S)\) be the neighbors of \(S\) in \(G\).

We first note that every vertex \(v \in W\) must have at least \(\Delta \) neighbors in \(S\). To see this, note that \(\mathbf{c}_{N(v)}\) is a codeword of \(C_0\) (by definition of the Tanner code \(X(G,C_0)\)), and furthermore it is a non-zero codeword since \(v\) has a neighbor in \(S\). Thus this codeword must have weight at least \(\Delta \) (by the distance of \(C_0\)), and since each non-zero coordinate of \(\mathbf{c}_{N(v)}\) corresponds to a distinct vertex of \(S\), we conclude that \(v\) has at least \(\Delta \) neighbors in \(S\).

Let \(s = |S|\) and \(w = |W|\). From the above we have that the number of edges incident to \(S\) equals \(cs \ge \Delta w\). If \(|S| \le \gamma n\), then by the expansion of \(G\) we would also have \(w \ge \alpha s\). Combining the two we would get \(cs \ge \alpha \Delta s\), which contradicts the assumption that \(\alpha {\gt} c/\Delta \). We thus conclude that \(|S| {\gt} \gamma n\), which in turn implies that \(\mathbf{c}\) has weight strictly greater than \(\gamma n\). Since this is true for every non-zero codeword of \(X(G,C_0)\), we conclude that \(X(G,C_0)\) has distance greater than \(\gamma n\).

Consider any \(\beta \) with \(\lambda \le \beta \le \delta _0 d\), and apply Theorem 230. We get that \(H\) is a \(\left(dn,2n,2,\frac{\beta (\beta -\lambda )}{d^2},\frac{2}{\beta }\right)\)-bipartite expander. Thus the dimension of the code \(X(H,C_0)\) is, by Lemma 240, at least \(dn - 2n(d-d\rho ) = (2\rho -1)dn\). Thus its rate is at least \(2\rho -1\).

Now we turn to the distance of \(X(H,C_0)\). Here, our choice of \(\beta \) ensures the expansion factor \(\alpha = 2/\beta {\gt} c/(\delta _0 d) = 2/(\delta _0 d)\) (using \(\beta {\lt} \delta _0 d\)), and so we can apply Theorem 241 to conclude that \(X(H,C_0)\) has relative distance strictly greater than \(\gamma = \frac{\beta (\beta -\lambda )}{d^2}\). Taking limits as \(\beta \to \delta _0 d\) yields the bound \(\delta _0(\delta _0-\lambda /d)\) on the distance and thus the theorem.

This follows from Theorem 242, from the explicit constructibility of spectral expanders (Theorem 227) and the existence of (constant-sized) asymptotically good codes on the Gilbert-Varshamov bound, with an appropriate setting of parameters, as follows. Given \(\delta \) and \(\varepsilon \), set \(\delta _0 = \sqrt\delta \) and choose \(d\) and \(\lambda \) such that \(\lambda /d \le \varepsilon /\delta _0\), where an \((n,d,\lambda )\)-spectral expander \(G\) exists (by Theorem 227, such a graph exists for sufficiently large \(d\) and infinitely many \(n\)). Let \(C_0\) be a code on the Gilbert-Varshamov bound with block length \(d\), relative distance \(\delta _0\) and rate \(1-h(\delta _0)\). Applying Theorem 242 we get that the Tanner code \(X(H,C_0)\), where \(H\) is the edge-vertex incidence graph of the double cover of \(G\), is a code of rate \(1-2h(\delta _0) = 1-2h(\sqrt\delta )\), and distance \(\delta _0^2 - \delta _0\lambda /d \ge \delta - \varepsilon \).

For the consequent part, we set \(\delta \) so that \(2h(\sqrt\delta ) = \tau \) and set \(\varepsilon = \delta /2\) and apply the previous part. This gives a code \(X(H,C_0)\) of rate \(1-\tau \) and distance \(\delta /2\). Note that the condition \(2h(\sqrt\delta ) = \tau \) is satisfied by setting \(\delta = h^{-1}(\tau /2)^2\). Using the bound \(h^{-1}(p) \ge p/\log p\) we get \(\delta = \Omega (\tau ^2/\log ^2(1/\tau ))\), and so the resulting code \(X(H,C_0)\) also has distance \(\Omega (\tau ^2/\log ^2(1/\tau ))\). We conclude the resulting family of codes is a polynomially constructible asymptotically good family of Tanner codes.

Let \(k = \dim (C)\) and \(n=|L|\), so \(R(C) = k/n\). The map \(\mathbf{w} \mapsto G(\mathbf{w})\) is injective (every left vertex has at least one incident edge, since \(G\) is \(c\)-left-regular with \(c \ge 1\), so the bits of \(\mathbf{w}\) can be recovered from \(G(\mathbf{w})\)), so \(G(C)\), viewed as a code over the alphabet \(\Sigma = \mathbb {F}_2^d\) of size \(2^d\), has \(\log _{2^d}|G(C)| = \log _{2^d}|C| = k/d\) symbols of message per codeword, over a block length of \(m = |R|\) symbols. Since \(G\) is \(c\)-left-regular and \(d\)-right-regular, double counting the edges of \(G\) gives \(cn = dm\). Hence

(1) Let \(S \subseteq L\) have size \(|S| \ge \gamma n\). Let \(T \subseteq S\) be any set of size \(|T| = \gamma n\). By the expansion condition we have \(|N(T)| \ge \alpha |T| = \alpha \gamma n\). Since \(N(S) \supseteq N(T)\), it follows that \(|N(S)| \ge \alpha \gamma n \ge (1-\varepsilon )m\). Thus \(G\) satisfies the definition of a \((\gamma ,\varepsilon )\)-disperser.

(2) For this we need the expander mixing lemma (Lemma 226). Let \(H = (L,R,E)\) be the double cover of \(G\) where \(G\) is an \((n,d,\lambda )\)-spectral expander. We need to prove that for each \(S \subseteq L\) with \(|S| \ge \gamma n\), we have \(N(S) \ge (1-\varepsilon )n\). As in the proof of Part (1) it suffices to consider the case of \(|S| = \gamma n\). Fix \(S\), let \(T = R\setminus N(S)\), and it suffices to prove that \(|T| \le \varepsilon n\). By the Expander Mixing Lemma (in particular the second displayed inequality of Lemma 226) and the fact that \(E(S,T) = \emptyset \) by definition of \(T\), we have

as desired.

Recall that Theorem 227 gives that for every \(\varepsilon ' {\gt} 0\), for every large enough \(d\) there exists an infinite family of explicitly constructible \((n,d,\lambda )\)-spectral expanders for \(\lambda = \varepsilon ' d\). We apply this theorem with \(\varepsilon ' = \sqrt{\varepsilon \gamma }\). Part (2) of Lemma 247 then implies that the double covers of the resulting family of graphs are an explicit (polynomial time constructible) family of \((\gamma ,\varepsilon )\)-dispersers (since \(\varepsilon = (\lambda /d)^2/\gamma = (\varepsilon ')^2/\gamma = \varepsilon \gamma /\gamma = \varepsilon \)). The furthermore part follows from the furthermore part of Theorem 227 (which gives \(d = O(1/(\varepsilon ')^2) = O(1/(\varepsilon \gamma ))\)).

Suppose \(\mathbf{c}\) and \(\mathbf{c}'\) are distinct codewords in \(C\), and let \(G(\mathbf{c})\) and \(G(\mathbf{c}')\) be the corresponding codewords in \(G(C)\). Let \(A \subseteq L\) be the positions where \(\mathbf{c}\) and \(\mathbf{c}'\) differ; since \(\Delta (C) \ge \gamma n\) we have \(|A| \ge \gamma n\). We have that \(G(\mathbf{c})\) and \(G(\mathbf{c}')\) differ in their \(j\)’th location whenever \(j \in N(A)\) (since position \(j\) reads off the value at some vertex of \(A\), which differs between \(\mathbf{c}\) and \(\mathbf{c}'\)). Since \(|N(A)| \ge (1-\varepsilon )m\) by the disperser property, the Hamming distance between \(G(\mathbf{c})\) and \(G(\mathbf{c}')\) is at least \((1-\varepsilon )m\). We thus conclude \(\Delta (G(C)) \ge (1-\varepsilon )m\).

Take \(C\) to be an explicit binary code of rate \(1/2\) and relative distance \(\delta _0 = .001\) (as furnished by concatenated codes on the Zyablov bound, Theorem 206). Take \(G\) to be a \(d\)-regular \((\delta _0,\varepsilon )\)-disperser furnished by Lemma 248 with \(d = O(1/(\delta _0\varepsilon )) = O(1/\varepsilon )\). By Lemma 245, \(G(C)\) has rate \(1/d = \Omega (\varepsilon )\). By Lemma 249 (applicable since \(\Delta (C) \ge \delta _0 n\)), \(G(C)\) has relative distance \(1-\varepsilon \). The alphabet size of \(G(C)\) is \(2^d = 2^{O(1/\varepsilon )}\).

We first note that since \(C_{\text{out}}\) and \(C_{\text{in}}\) are \(\mathbb {F}_2\)-linear, the \(C_{\text{in}}\)-coded \(G\)-amplification of \(C_{\text{out}}\) is \(\mathbb {F}_2\)-linear. So to analyze the distance it suffices to prove that the Hamming weight of the encoding of a non-zero vector \(\mathbf{u} \in \mathbb {F}_q^k\) has large weight. Fix such a non-zero \(\mathbf{u}\). Let \(\mathbf{v} = C_{\text{out}}(\mathbf{u})\) and let \(\mathbf{w} = (C_{\text{out}}\circ C_{\text{in}})(\mathbf{u})\) and \(\mathbf{x} = G_{\mathrm{mix}}(\mathbf{w})\) so that \(\mathbf{x} = \mathscr {CA}(C_{\text{out}},C_{\text{in}},G)(\mathbf{u})\). Let \(S = \{ i \in [n] \mid v_i \ne 0\} \) denote the subset of coordinates where \(\mathbf{v}\) (equivalently \(\mathbf{w}\)) is non-zero. Note \(|S| \ge \delta _{\text{out}}n\). Now consider \(T = \{ j \in [n] \mid \mathbf{x}_j \ne 0\} \); our goal is to prove \(|T| \ge (\delta _{\text{in}}-\varepsilon )n\).

We view \(S\) and \(T\) as subsets of the left and right vertices, respectively, of \(G\). The key observation is that every vertex \(i \in S\) has many edges going into \(T\): the mixing process associates the label \(w_i\) with the vertex \(i\) and spreads the symbols of \(w_i\) out over the edges incident to \(i\). On the one hand, for \(i \in S\), \(w_i\) is a non-zero codeword of \(C_{\text{in}}\) and so has at most \((1-\delta _{\text{in}})B\) coordinates \(a \in [B]\) such that \(w_i(a) = 0\). On the other hand, every symbol transmitted to vertices outside \(T\) is zero (by definition of \(T\)), and so if an edge goes from \(S\) to \(T^c\) it must transmit the zero symbol. It follows that every vertex \(i \in S\) has at most \((1-\delta _{\text{in}})B\) neighbors outside \(T\), and at least \(\delta _{\text{in}}B\) neighbors in \(T\). We thus get \(|E(S,T)| \ge \delta _{\text{in}}B|S|\). But by the expander mixing lemma (Lemma 226) we also have

Putting the two together,

where the second inequality uses \(T \subseteq [n]\) to get \(|T|\le n\), and the third inequality uses \(|S| \ge \delta _{\text{out}}n\) (or equivalently \(n \le |S|/\delta _{\text{out}}\)). Rearranging terms we get

where the second inequality uses \(\lambda \le \varepsilon \sqrt{\delta _{\text{out}}}B\). We conclude every non-zero codeword of \(\mathscr {CA}(C_{\text{out}},C_{\text{in}},G)\) has weight at least \((\delta _{\text{in}}-\varepsilon )n\) and thus \(\delta (\mathscr {CA}(C_{\text{out}},C_{\text{in}},G)) \ge \delta _{\text{in}}-\varepsilon \).

We choose parameters so that the code \(\mathscr {CA}(C_{\text{out}},C_{\text{in}},G)\) has rate \(r\) and relative distance \(1-r-\varepsilon \), with alphabet a power of two of size \(\exp \! \left(O(\varepsilon ^{-4}\log ^3(1/\varepsilon ))\right)\).

Fix the target rate \(r\) and proximity parameter \(\varepsilon {\gt} 0\). Let \(r_{\text{out}} = 1-\varepsilon /2\). Let \(\delta _{\text{out}}\) be chosen so that there exists an infinite family of explicitly constructible binary linear codes of rate \(r_{\text{out}}\) and relative distance \(\delta _{\text{out}}\); we may use the code given by Corollary 243 to achieve \(\delta _{\text{out}} = \Omega (\varepsilon ^2/\log ^2(1/\varepsilon ))\). Next we choose \(B\) and \(\lambda \) so that \(\lambda \le \frac\varepsilon 2\cdot \sqrt{\delta _{\text{out}}}B\) and an infinite family of explicitly constructible \((n,B,\lambda )\)-spectral expanders exists; by Theorem 227 it suffices to choose \(B = \Theta \left(\frac{1}{\delta _{\text{out}}\varepsilon ^2}\right) = \Theta (\varepsilon ^{-4}\log ^2(1/\varepsilon ))\). In particular we choose \(B=2^s\) for an integer \(s\). Let \(q=B\) and let \(r_{\text{in}} = r/r_{\text{out}}\). Let \(b = r_{\text{in}}\cdot B\) and let \(C_{\text{in}}\) be a Reed-Solomon code (Definition 128) over \(\mathbb {F}_q\) of rate \(r_{\text{in}}\) and relative distance \(\delta _{\text{in}} = 1-r_{\text{in}}\).

Given a sufficiently large \(k\) we let \(T:\mathbb {F}_2^{ks}\to \mathbb {F}_2^{ns}\) be an explicitly constructed linear code of rate \(r_{\text{out}}\) and distance \(\delta _{\text{out}}\). Note that by collecting together the symbols of the message as well as encodings into blocks of \(s\) symbols and using a linear map from \(\mathbb {F}_2^s\) to \(\mathbb {F}_q\), we can view \(T\) as a map \(C_{\text{out}} : \mathbb {F}_q^k \to \mathbb {F}_q^n\). This preserves the rate and distance, so \(C_{\text{out}}\) is an \(\mathbb {F}_2\)-linear code of rate \(r_{\text{out}}\) and distance \(\delta _{\text{out}}\). Let \(G\) be the double cover of an \((n,B,\lambda )\)-spectral expander. Let \(C^* = \mathscr {CA}(C_{\text{out}},C_{\text{in}},G)\). We claim \(C^*\) is the desired code for the message space \(\mathbb {F}_2^{ks}\).

By construction \(C^*\) is from an explicitly constructible family. As observed in the proof of Lemma 253, the code is \(\mathbb {F}_2\)-linear. Its rate is equal to the rate of \(C_{\text{out}}\circ C_{\text{in}}\), which in turn equals \(r_{\text{out}}\cdot r_{\text{in}} = r\) (by our choice of \(r_{\text{in}}\)). By Lemma 253 we have that the relative distance of \(C^*\) is at least \(\delta _{\text{in}}-\varepsilon /2\) (our choice of \(\lambda \) ensures \(\lambda \le \frac{\varepsilon }{2}\sqrt{\delta _{\text{out}}}B\)). Since

we get that the relative distance of \(C^*\) is at least \(\delta _{\text{in}}-\varepsilon /2 \ge 1-r-\varepsilon \). Finally the alphabet size is \(q^B = B^B = \exp (B\log B) = \exp \left(O\! \left(\varepsilon ^{-4}\log ^3\! \left(\frac1\varepsilon \right)\right)\right)\). This concludes the proof of the theorem.

Concatenate the outer code from Theorem 254 (of rate \(r\) and relative distance \(1-r-\varepsilon \) over an alphabet of size \(2^{O(1/\varepsilon )}\)) with an inner binary code of dimension \(\log _2|\Sigma | = O(1/\varepsilon )\) lying on the Gilbert-Varshamov bound (Theorem 105), constructed by brute-force search over a time depending only on \(\varepsilon \) (and hence, for fixed \(\varepsilon \), polynomial in the overall block length). By the distance property of concatenated codes (Definition 202), the resulting binary code has rate and relative distance within \(\varepsilon \) of the point \((r,1-r)\) traced out by the Zyablov bound (Theorem 206) for every choice of \(r \in (0,1)\), and is constructible in time polynomial in the block length and exponential in \(\mathrm{poly}(1/\varepsilon )\).