\section{Proofs from Section~\ref{section:preliminaries}}

\subsection{Proof of Proposition~\ref{proposition:vector_exit_properties_1}}
\label{appendix:proof_vector_exit_properties_1}

For the first statement, we start by using chain rule of entropy to write
\begin{align*}
  \ent{\ul{X} | \ul{Y}(\ul{p})} = \ent{X_i | \ul{Y}(\ul{p})} + \ent{\ul{X}_{\sim i} | X_i, \ul{Y}(\ul{p}) }.
\end{align*}
Then, we observe that 
\begin{align*}
  \ent{\ul{X}_{\sim i} | X_i, \ul{Y}(\ul{p})} = \ent{\ul{X}_{\sim i} | X_i, \ul{Y}_{\sim i}(\ul{p}_{\sim i})}, 
\end{align*}
is independent of $p_i$.
Since
\begin{align*}
  \ent{X_i | \ul{Y}(\ul{p})} &= \Pr(Y_i=*) \ent{X_i | \ul{Y}_{\sim i}(\ul{p}_{\sim i}) , Y_i=*} \\
  & \quad + \Pr(Y_i=X_i) \ent{X_i | \ul{Y}_{\sim i}(\ul{p}_{\sim i}) , Y_i=X_i} \\
  &= p_i \ent{X_i | \ul{Y}_{\sim i}(\ul{p}_{\sim i})},
\end{align*}
we find that
\begin{align*}
  \pderi{\ent{X_i | \ul{Y}(\ul{p})}}{p_i} = \ent{X_i | \ul{Y}_{\sim i}(\ul{p}_{\sim i})} = h_i(\ul{p}).
\end{align*}
The second statement now follows directly from vector calculus.

\subsection{Proof of Proposition~\ref{proposition:vector_exit_properties_2}}
\label{appendix:proof_vector_exit_properties_2}

For part a, the definition of $h_i$ implies
\begin{align*}
  h_i(\ul{p}) &= \ent{X_i | \ul{Y}_{\sim i}(p_{\sim i}) } \\
  &=\sum_{\ul{y}_{\sim i}\in \mathcal{Y}^{N-1}} \Pr(\ul{Y}_{\sim i}=\ul{y}_{\sim i}) \ent{X_i | \ul{Y}_{\sim i}=\ul{y}_{\sim i}} .
\end{align*}
The fact that the decoding process is successful depends only on the erasure pattern in $\ul{Y}=\ul{y}$.
Hence, we can assume that the all-zero codeword has been transmitted.
In such a case, for $\ell \in [N]$, either $y_\ell=0$ or $y_\ell=*$.
Let $A \subseteq [N] \backslash \{i\}$ be the set of indices where $y_\ell=*$ so that
\begin{align*}
  \Pr(\ul{Y}_{\sim i}=\ul{y}_{\sim i}) = \prod_{\ell \in A} p_\ell \prod_{\ell \in A^c \backslash \{i\}} (1-p_\ell) .
\end{align*}

If $A \cup \{i\}$ covers a codeword in $\mc{C}$ whose $i$-th bit is non-zero, then bit-MAP decoder fails to decode bit $i$.
Also, since the posterior probability of $X_i$ given $\ul{Y}_{\sim i} = \ul{y}_{\sim i}$ is uniform, $H(X_i | \ul{Y}_{\sim i}=\ul{y}_{\sim i})=1$.

If $A \cup \{i\}$ does not cover any codeword in $\mc{C}$ with non-zero bit $i$, then the MAP estimate of $X_i$ given $\ul{Y}_{\sim i} = \ul{y}_{\sim i}$ is equal to $X_i$ and $H(X_i | \ul{Y}_{\sim i}=\ul{y}_{\sim i})=0$.

Thus, the EXIT function $h_i (\ul{p})$ is given by summing over the first set of erasure patterns where the entropy is $1$.
This set is precisely $\Omega_i$, the set of all erasure patterns that cover a codeword whose $i$-th bit is non-zero.

For part b, we evaluate the partial derivative using the explicit evaluation of $h_i(\ul{p})$ from part a.
Suppose $A \in \Omega_i$.
To simplify things, we handle the two groups separately.

If $A\cup\{j\} \in \Omega_{i}$ and $A\backslash\{j\}  \in \Omega_i$, then we observe that
\begin{align*}
  \sum_{B\in \{A\cup\{j\},A\backslash\{j\}\}} & \;\;\, \prod_{\ell \in B} p_\ell \prod_{\ell \in B^c\backslash \{i\}} (1-p_\ell) \\
  = & \prod_{\ell \in A \backslash \{j\}} p_\ell \prod_{\ell \in A^c\backslash \{i,j\}} (1-p_\ell)
\end{align*}
is independent of the variable $p_j$.
Thus, its partial derivative with respect to $p_j$ is zero.

On the other hand, if $A \cup \{j\} \in \Omega_i$ but $A \backslash \{j\} \notin \Omega_i$, then $j \in A$.
In this case, the contribution of $A$ to $h_i(\ul{p})$ can be written as 
\begin{align*}
  h_{i,A}(\ul{p}) = \prod_{\ell \in A} p_\ell \prod_{\ell \in A^c\backslash \{i\} } (1 - p_\ell) .
\end{align*}
Since $j \in A$, we find that
\begin{align}
	\label{equation:dhia}
  \pderi{h_{i,A}(\ul{p})}{p_j} = \prod_{\ell \in A \backslash \{j\} } p_\ell \prod_{\ell \in A^c\backslash \{i\} } (1 - p_\ell) 
\end{align}
and, since the derivative is zero for patterns in the first group, we get 
\begin{align}
  \label{equation:dhip_sum}
  \pderi{h_i(\ul{p})}{p_j} \!= \! \sum_{A\in \{B \in \Omega_i  \, | B \backslash \{j\} \notin \Omega_i \} } \pderi{h_{i,A}(\ul{p})}{p_j}.
\end{align}
We can also rewrite~\eqref{equation:dhia} as
\begin{align}
	\label{equation:dhia2}
  \pderi{h_{i,A}(\ul{p})}{p_j} = \sum_{B\in \{A\cup\{j\},A\backslash\{j\}\}} \prod_{\ell \in B} p_\ell \prod_{\ell \in B^c\backslash \{i\} } (1 - p_\ell) ,
\end{align}
where the effect of $p_j$ is removed by summing over $A \cup \{j\}$ and $A \backslash \{j\}$.
Substituting~\eqref{equation:dhia2} into~\eqref{equation:dhip_sum} gives the desired result because
$\partial_j \Omega_i$ is equal to the union of $\{A \in \Omega_i  \, | A \backslash \{j\} \notin \Omega_i \}$ and $\{A \not\in \Omega_i  \, | A \cup \{j\} \in \Omega_i \}$.

\subsection{Proof of Proposition~\ref{proposition:capacity_equivalence}}
\label{appendix:proof_capacity_equivalence}

S1 $\Longrightarrow$ S2:
The relation $P_b(p)=ph(p)$ together with $P_b^{(n)}(p) \to 0$ and $h^{(n)}(0)=0$ implies
\begin{align*}
  \lim_{n \to \infty} h^{(n)}(p) = 0 \quad \text{for $0 \leq p < 1-r$}.
\end{align*}

Now, we focus on the limit of $h^{(n)} (p)$ for $1-r < p \leq 1$.
Fix $q\in(1-r,1]$ and choose $n_0$ large enough so that, for all $n>n_0$, we have $r_n > r - \epsilon$ and $h^{(n)}(1-r - \epsilon) \leq \epsilon$.
Such an $n_0$ exists because $r_n \to r$ and $h^{(n)}(p) \to 0$ for $0 \leq p<1-r$.
Since the function $h^{(n)}$ is increasing for all $n$, the EXIT area theorem (i.e., Proposition \ref{proposition:scalar_exit_properties}(c)) implies that, for all $n>n_0$, we have
\begin{align*}
  \allowdisplaybreaks
  r - \epsilon < r_n &= \int_0^1 h^{(n)}(p) \diff{p} \\
  &= \int_0^{1-r-\epsilon} h^{(n)}(p)\diff{p} + \int_{1-r-\epsilon}^{q} h^{(n)}(p) \diff{p} \\
  & \qquad \qquad + \int_{q}^{1} h^{(n)}(p)\diff{p} \\
  &\leq (1-r-\epsilon) \epsilon + (q-(1-r)+\epsilon) h^{(n)}(q) \\
  & \qquad \qquad + (1-q).
\end{align*}
This implies
\begin{align*}
  h^{(n)}(q) & \geq \frac{q-(1-r) - \epsilon(2-r-\epsilon)}{q-(1-r)+\epsilon} \\
  &\geq 1 - \frac{3\epsilon}{q-(1-r)} .
\end{align*}
As such, $\lim_{n\to\infty} h^{(n)}(q) = 1$, for any $1-r<q\leq 1$.

S2 $\Longrightarrow$ S3: Since $p_{1-\epsilon}^{(n)} - p_{\epsilon}^{(n)}$ is the width of the erasure probability interval over which $h^{(n)}$ transitions from $\epsilon$ to $1-\epsilon$, this follows immediately from S2.

S3 $\Longrightarrow$ S1: It suffices to show that for any $q < 1-r$ and $\epsilon>0$, $p^{(n)}_{\epsilon} \geq q$ for large enough $n$.
This shows that $P^{(n)}_b(q) = q h^{(n)}(q) \leq h^{(n)}(q) \leq h^{(n)}(p^{(n)}_{\epsilon}) = \epsilon$ for large enough $n$, as desired.

Fix $q<1-r$ and choose a small $\epsilon>0$ such that 
\begin{align*}
 \frac{1-r-2\epsilon}{1-\epsilon} - \epsilon \geq q 
\end{align*}
From the hypothesis, let $n_0$ be such that for all $n>n_0$,
\begin{align*}
  p_{1-\epsilon}^{(n)} - p_{\epsilon}^{(n)} &\leq \epsilon, & r_n &\leq r + \epsilon .
\end{align*}
From Proposition \ref{proposition:scalar_exit_properties}(c), we have
\begin{align}
  \label{equation:pepsilon_lower_bound}
  r_n &= \int_{0}^{1} h^{(n)}(\alpha) \diff{\alpha} \geq \left(1-p_{1-\epsilon}^{(n)} \right) (1-\epsilon),
\end{align}
which implies $p_{1-\epsilon}^{(n)} \geq \frac{1-r_n-\epsilon}{1-\epsilon}$.
Thus, for $n>n_0$,
\begin{align*}
  p_\epsilon^{(n)} &\geq p_{1-\epsilon}^{(n)} - (p_{1-\epsilon}^{(n)} - p_{\epsilon}^{(n)})   \\
  &\geq \frac{1-r_n-\epsilon}{1-\epsilon} - \epsilon \geq \frac{1-r - 2\epsilon}{1-\epsilon} - \epsilon \geq q,
\end{align*}
by the choice of $\epsilon$, which gives the desired result.

\subsection{Proof of Proposition \ref{proposition:code_modification}}
\label{appendix:proof_code_modification}
We begin by deriving a relationship between average EXIT functions of the original code and of the punctured code.
Let $\hat{\mc{C}}$ be a code obtained by puncturing $\ell$ bits from $\mc{C}$.
Let $N$ be the blocklength of $\mc{C}$.
Also, let the average and bit EXIT functions of $\mc{C}$, $\hat{\mc{C}}$ be denoted by $h$, $\hat{h}$ and $h_i$, $\hat{h}_i$, respectively.
Without loss of generality, assume that the punctured bits are indexed by $N-(\ell-1),\dots,N$.
For $1 \leq i \leq N - \ell$,
\begin{align*}
  h_i(p) &= H(X_i | Y_1,\dots,Y_{i-1},Y_{i+1},\dots,Y_{N}), \\
  \hat{h}_i(p) &= H(X_i | Y_1,\dots,Y_{i-1},Y_{i+1},\dots,Y_{N-\ell}) .
\end{align*}
As such, $h_i \leq \hat{h}_i$ for $1 \leq i \leq N-\ell$.
Since $0 \leq h_i \leq 1$,
\begin{align*}
  N h=\sum_{i=1}^N h_i \leq \sum_{i=1}^{N-\ell}\hat{h}_i + \sum_{N-(\ell-1)}^{N} h_i \leq (N-\ell)\hat{h} + \ell .
\end{align*}
Thus,
\begin{align}
  \label{equation:exit_punctured_relation}
  h \leq \frac{N-\ell}{N} \hat{h} + \frac{\ell}{N} \leq \hat{h} + \frac{\ell}{N}.
\end{align}

Suppose $\{\mc{C}_n\}$ achieves capacity under bit-MAP decoding.
From statement S2 of Proposition~\ref{proposition:capacity_equivalence}(b), $h^{(n)}(p) \to 1$ for all $1-r < p \leq 1$.
Together with \eqref{equation:exit_punctured_relation}, since $\ell_n/N_n \to 0$, we have $\hat{h}^{(n)}(p) \to 1$ for all $1-r < p \leq 1$.
Using Proposition~\ref{proposition:scalar_exit_properties}(c), one can show that $\hat{h}^{(n)}(p) \to 0$ for all $0 \leq p < 1-r$.
Then, Proposition~\ref{proposition:capacity_equivalence} implies that $\{ \hat{\mc{C}}_n \}$ achieves capacity under bit-MAP decoding.

Now, suppose $\{ \hat{\mc{C}}_n \}$ achieves capacity under bit-MAP decoding.
From statement S2 of Proposition~\ref{proposition:capacity_equivalence}(b), $\hat{h}^{(n)}(p) \to 0$ for all $0 \leq p < 1-r$.
From \eqref{equation:exit_punctured_relation}, since $\ell_n/N_n \to 0$, we have $h^{(n)}(p) \to 0$ for all $0 \leq p < 1-r$.
Then, $P_b^{(n)}(p) = p h^{(n)}(p) \to 0$.
Thus, $\{\mc{C}_n\}$ is capacity achieving under bit-MAP decoding.

\section{Proofs from Section~\ref{section:sharp_threshold}}
\label{appendix:proofs_section_inequalities}

\begin{lemma}
\label{lemma:exit_integral_generic}
Suppose $h \colon [0,1] \to [0,1]$ is a strictly increasing function with $h(0)=0$ and $h(1)=1$.
Additionally, for $0 \leq a < p < b \leq 1$, let
\begin{align*}
  \deri{h(p)}{p} \geq w h(p) (1-h(p)) .
\end{align*}
If $p_t = h^{-1}(t)$, then for $0 < \epsilon_1 \leq \epsilon_2 \leq 1$,
\begin{align}
  \label{equation:width_upper_bound}
  p_{\epsilon_2} \!-\! p_{\epsilon_1} \leq a + (1\!-\!b) + \frac{1}{w} \left[ \log\frac{\epsilon_2}{1\!-\!\epsilon_2} + \log\frac{1\!-\!\epsilon_1}{\epsilon_1} \right] .
\end{align}
Moreover, for $0 \leq \gamma \leq p_{1/2}$,
\begin{align*}
  h(\gamma) \leq \exp \left[ -w \left( [p_{1/2} - \gamma] -[a + 1-b] \right) \right] .
\end{align*}
\end{lemma}
\begin{IEEEproof}
Let $g (p) = \log \frac{h(p)}{1-h(p)}$ and observe that, for $a < p < b$, we have
\begin{align*}
 \deri{g(p)}{p}=\frac{1}{h(p)(1-h(p))} \deri{h(p)}{p} \geq w .
\end{align*}
Let $p_t=h^{-1}(t)$.
We would like to obtain an upper bound on $p_{\epsilon_2} - p_{\epsilon_1}$ by integrating $dg/dp$.

If $a < p_{\epsilon_1} \leq p_{\epsilon_2} < b$, then integrating $dg/dp$ from $p_{\epsilon_1}$ to $p_{\epsilon_2}$ gives
\begin{align*}
  w (p_{\epsilon_2} \!-\! p_{\epsilon_1}) \leq \int_{p_{\epsilon_1}}^{p_{\epsilon_2}} \frac{dg}{dp} \diff{p} = \log \frac{\epsilon_2}{1\!-\!\epsilon_2} - \log \frac{\epsilon_1}{1\!-\!\epsilon_1} ,
\end{align*}
which immediately shows \eqref{equation:width_upper_bound}.

Suppose $p_{\epsilon_1} \leq a < p_{\epsilon_2} < b$, and note that since $g$ is increasing $\epsilon_1 = h(p_{\epsilon_1}) \leq h(a)$.
Then, integrating $dg/dp$ from $a$ to $p_{\epsilon_2}$ gives
\begin{align*}
  w (p_{\epsilon_2} - a) &\leq \int_{a}^{p_{\epsilon_2}} \frac{dg}{dp} \diff{p} \\
  &= \log \frac{\epsilon_2}{1-\epsilon_2} - \log \frac{h(a)}{1-h(a)} \\
  &\leq \log \frac{\epsilon_2}{1-\epsilon_2} - \log \frac{\epsilon_1}{1-\epsilon_1} . \quad \text{(Since $\epsilon_1 \leq h(a)$)}
\end{align*}
Using $p_{\epsilon_2} - p_{\epsilon_1} \leq a + (p_{\epsilon_2} - a)$ with the above inequality gives \eqref{equation:width_upper_bound}.

By considering other cases where $p_{\epsilon_1}$ and $p_{\epsilon_2}$ lie, it is straightforward to obtain \eqref{equation:width_upper_bound}.
Also, substituting $\epsilon_2=1/2$ and $\epsilon_1=h(\gamma)$ in \eqref{equation:width_upper_bound} gives the desired upper bound on $h(\gamma)$.
\end{IEEEproof}

\subsection{Proof of Theorem~\ref{theorem:capacity_blockerror_dmin}}
\label{appendix:proof_capacity_blockerror_dmin}

Let $p^{(n)}_t$ be the functional inverse of $h^{(n)}$ from \eqref{equation:h_inverse}.
Using Lemma~\ref{lemma:exit_integral_generic} with $a_n=0$ and $b_n=1$ gives
\begin{align*}
  p^{(n)}_{1-\epsilon} - p^{(n)}_{\epsilon} \leq \frac{2 \log \frac{1- \epsilon}{\epsilon}}{C \log N_n} .
\end{align*}
By hypothesis, $N_n \to \infty$.
Thus, for any $\epsilon \in (0,1/2]$, we have $p^{(n)}_{1-\epsilon}-p^{(n)}_{\epsilon} \to 0$.
Using this, we apply statement S2 of Proposition~\ref{proposition:capacity_equivalence} to see that $p^{(n)}_{1/2}\to 1-r$.

Now, we can choose $\epsilon_n = d_{\mathrm{min}}^{(n)}/(N_n \log N_n)$ and observe that
\begin{align*}
  p^{(n)}_{1-\epsilon_n}- p^{(n)}_{\epsilon_n} &\leq \frac{2}{C \log N_n} \log \frac{1-\epsilon_n}{\epsilon_n} \\
  &\leq \frac{2}{C \log N_n} \log \frac{N_n \log N_n}{d_{\mathrm{min}}^{(n)}} \\
  &= \frac{2}{C} \frac{\log N_n + \log \log N_n - \log d_{\mathrm{min}}^{(n)}}{\log N_n} .
\end{align*}
By hypothesis, $\log d_{\mathrm{min}}^{(n)}/\log N_n \to 1$.
Thus, $p^{(n)}_{1-\epsilon_n}-p^{(n)}_{\epsilon_n} \to 0$.
Combining this with $p^{(n)}_{\epsilon_n} \leq p^{(n)}_{1/2} \leq p^{(n)}_{1-\epsilon_n}$ shows that $p^{(n)}_{\epsilon_n} \to 1-r$.

Also, from \eqref{equation:biterasure_exit_relation},
\begin{align*}
  P_b^{(n)}(p^{(n)}_{\epsilon_n}) = p^{(n)}_{\epsilon_n} h^{(n)}(p^{(n)}_{\epsilon_n}) \leq h^{(n)}(p^{(n)}_{\epsilon_n}) = \epsilon_n .
\end{align*}
Recall from \eqref{equation:erasure_prob_dmin} that $P_B \leq N P_b / d_{\mathrm{min}}$.
Hence, for any $p \in [0,1-r)$, one finds that $p^{(n)}_{\epsilon_n} > p$ for sufficiently large $n$ and thereafter
$$P_B^{(n)}(p) \leq \frac{N_n}{d_{\mathrm{min}}^{(n)}} P_b^{(n)}(p) \leq \frac{N_n}{d_{\mathrm{min}}^{(n)}} \epsilon_n = \frac{1}{\log N_n} \to 0.$$
Thus, we conclude that $\{\mc{C}_n\}$ is capacity achieving on the BEC under block-MAP decoding.

\subsection{Proof of Theorem~\ref{theorem:capacity_blockerror_wn}}
\label{appendix:proof_capacity_blockerror_wn}

Let $p^{(n)}_t$ be the functional inverse of $h^{(n)}$ from \eqref{equation:h_inverse}.
From Lemma~\ref{lemma:exit_integral_generic},
\begin{align*}
  p^{(n)}_{1-\epsilon} - p^{(n)}_{\epsilon} \leq a_n + (1-b_n) + \frac{2 \log \frac{1- \epsilon}{\epsilon}}{w_n \log N_n} .
\end{align*}
By hypothesis, $a_n \to 0$, $1-b_n \to 0$, and $w_n \log N_n \to \infty$.
Thus, for any $\epsilon \in (0,1/2]$, we have $p^{(n)}_{1-\epsilon}-p^{(n)}_{\epsilon} \to 0$.
Using this, we apply statement S2 of Proposition~\ref{proposition:capacity_equivalence} to see that $p^{(n)}_{1/2}\to 1-r$.

Now, we can choose $\epsilon_n = 1/N_n^2$ and observe that
\begin{align*}
  p^{(n)}_{1-\epsilon_n}- p^{(n)}_{\epsilon_n} &\leq a_n \!+\! (1-b_n) \!+\! \frac{1}{w_n\log N_n} 2 \log \frac{1-\epsilon_n}{\epsilon_n} \\
  &\leq a_n \!+\! (1-b_n) + \frac{1}{w_n \log N_n} 4 \log N_n \\
  &= a_n \!+\! (1-b_n) \!+\! \frac{4}{w_n}.
\end{align*}
Combining $p^{(n)}_{\epsilon_n} \leq p^{(n)}_{1/2} \leq p^{(n)}_{1-\epsilon_n}$ with $p^{(n)}_{1-\epsilon_n}-p^{(n)}_{\epsilon_n} \to 0$ shows that $p^{(n)}_{\epsilon_n} \to 1-r$.

Also, from \eqref{equation:biterasure_exit_relation},
\begin{align*}
  P_b^{(n)}(p^{(n)}_{\epsilon_n}) = p^{(n)}_{\epsilon_n} h^{(n)}(p^{(n)}_{\epsilon_n}) \leq h^{(n)}(p^{(n)}_{\epsilon_n}) = \epsilon_n .
\end{align*}
Recall from \eqref{equation:erasure_prob_relations} that $P_B \leq N P_b$.
Hence, for any $p \in [0,1-r)$, one finds that $p^{(n)}_{\epsilon_n} > p$ for sufficiently large $n$ and thereafter
$$P_B^{(n)}(p) \leq N_n P_b^{(n)}(p) \leq N_n \epsilon_n = N_n/N_n^2 \to 0.$$
Thus, we conclude that $\{\mc{C}_n\}$ is capacity achieving on the BEC under block-MAP decoding.


\section{Proofs from Section~\ref{section:applications}}

\subsection{Proof of Lemma~\ref{lemma:rm_2transitive}}
\label{appendix:proof_rm_2transitive}

Take any distinct $i,j,k \in [N]$.
Below, we will produce a $\pi \in \mc{G}$ such that $\pi(i)=i$ and $\pi(j)=k$.

It is well known that for any vector space with two ordered bases $(\ul{u}_1,\dots,\ul{u}_m)$ and $(\ul{u}'_1,\dots,\ul{u}'_m)$, there exists an invertible $m\times m$ matrix $T$ such that
\begin{align*}
  \ul{u}_i = T \ul{u}'_i , \quad \text{for all $i \in [m]$} .
\end{align*}

Note that since $i,j,k$ are distinct, $\ul{e}_j-\ul{e}_i \neq 0^m$ and $\ul{e}_k-\ul{e}_i \neq 0^m$.
Therefore, there exists an invertible $m \times m$ binary matrix $T$ such that
  $T(\ul{e}_j-\ul{e}_i) = \ul{e}_k - \ul{e}_i$.
For such a $T$, we construct $\pi \colon [N] \to [N]$ by defining $\pi(\ell) = \ell'$ for the unique $\ell'$ such that 
\begin{align*}
  \ul{e}_{\ell'}= T (\ul{e}_{\ell} - \ul{e}_i) + \ul{e}_i .
\end{align*}
Note that $\pi \in S_N$ since $T$ is invertible.
Also, by construction, $\pi(i)=i$ and $\pi(j)=k$.

It remains to show that $\pi \in \mc{G}$.
For this, consider a codeword in $\mr{RM}(v,m)$ given by $f \in P(m,v)$.
It suffices to produce a $g \in P(m,v)$ such that $g(\ul{e}_{\pi(\ell)})=f(\ul{e}_{\ell})$ for all $\ell \in [N]$.
Let
\begin{align*}
  g(x_1,\dots,x_m)=f(T^{-1}[x_1,\dots,x_m]^{\mr{T}} - T^{-1}\ul{e}_i + \ul{e}_i) , 
\end{align*}
and note that $\text{degree}(f)=\text{degree}(g)$, $g(\ul{e}_{\pi(\ell)})=f(\ul{e}_{\ell})$.
Thus, we have the desired $g \in P(m,v)$.
Hence, $\mc{G}$ is doubly transitive.

\subsection{Proof of Lemma~\ref{lemma:gl_gN}}
\label{appendix:proof_gl_gN}

For a given $T \in \mr{GL}(m,\mbb{F}_2)$, associate $\pi_T \in S_{N-1}$, where 
\begin{align*}
  \pi_T(\ell) = \ell', \quad \text{where $\ul{e}_{\ell'} = T \ul{e}_{\ell}$}.
\end{align*}
Note that $\pi_T$ is well-defined since $T$ is invertible.
Moreover, it is easy to check that $\pi_{T_1} \circ \pi_{T_2} = \pi_{T_1 T_2}$ for $T_1,T_2 \in \mr{GL}(m,\mbb{F}_2)$.
As such, the collection of permutations
\begin{align*}
  \mc{H} = \{ \pi_T \in S_{N-1} \mid T \in \mr{GL}(m,\mbb{F}_2)\}
\end{align*}
is a subgroup of $S_{N-1}$ isomorphic to $\mr{GL}(m,\mbb{F}_2)$.
Also, for $i,j \in [N-1]$, there exists $T \in \mr{GL}(m,\mbb{F}_2)$ such that $\ul{e}_{j}=T\ul{e}_{i}$.
For such a $T$, $\pi_T(i)=j$.
Therefore, $\mc{H}$ is transitive.

It remains to show that $\mc{H} \subseteq \mc{G}_N$.
For this, associate $\pi_T \in \mc{H}$ with $\pi'_T \in S_{N}$ where
\begin{align*}
  \pi'_T(\ell) &= \pi_T(\ell)\quad \text{for $\ell \in [N-1]$}, & \pi'_T(N)&=N.
\end{align*}
Also, it is easy to show that $\pi_T \in \mc{G}_N$ if $\pi'_T \in \mc{G}$, the permutation group of $\mr{RM}(v,m)$.
To see that $\pi'_T \in \mc{G}$, consider a codeword given by $f \in P(m,v)$.
It suffices to produce a $g \in P(m,v)$ where $g(\ul{e}_{\pi'_T(\ell)})=f(\ul{e}_\ell)$ for $\ell \in [N]$.
The desired $g$ is given by $g(x_1,\dots,x_m)=f(T^{-1}[x_1,\dots,x_m]^{\mr{T}})$, by observing that $\text{degree}(g)=\text{degree}(f)$ and $g(\ul{e}_N)=f(T^{-1}0^m)=f(\ul{e}_N)$.


\subsection{Affine-Invariant Codes}
\label{subsection:affine_invariant_codes}

Consider a code $\mc{C}$ of length $N=2^n$ and the Galois field $\mbb{F}_{N}$.
Let $\Theta \colon [N] \to \mbb{F}_N$ denote a bijection between the elements of the field and the code bits.
Take a pair $\beta, \gamma \in \mbb{F}_{N}$ with $\beta \neq 0$ and define $\pi_{\beta,\gamma} \in S_{N}$ such that
\begin{align*}
  \pi_{\beta,\gamma}(\ell)=\Theta^{-1}( \beta \Theta(\ell) + \gamma ) .
\end{align*}
Note that $\pi_{\beta,\gamma}$ is well-defined since $\Theta$ is bijective and $\beta \neq 0$, and observe that $\pi_{\beta_1,\gamma_1} \circ \pi_{\beta_2,\gamma_2} = \pi_{\beta_1\beta_2,\beta_1 \gamma_2 + \gamma_1}$.
As such, the collection of permutations $\pi_{\beta,\gamma}$ forms a group.
Now, the code $\mc{C}$ is called \emph{affine-invariant} if its permutation group contains the subgroup
\begin{align*}
  \{ \pi_{\beta,\gamma} \in S_N \mid \beta,\gamma \in \mbb{F}_{N}, \beta \neq 0 \} ,
\end{align*}
for some bijection $\Theta$ \cite[Section 4.7]{Huffman-2003}.

Affine-invariant codes are of interest to us because their permutation groups are doubly transitive.
To see this, consider distinct $i,j,k \in [N]$ and choose $\beta, \gamma \in \mbb{F}_{N}$ where
\begin{align*}
  \beta &= \frac{\Theta(i) - \Theta(k)}{\Theta(i) - \Theta(j)}, & \gamma &= \Theta(i) \left( \frac{\Theta(k) - \Theta(j)}{\Theta(i)-\Theta(j)} \right) ,
\end{align*}
and observe that $\pi_{\beta,\gamma}(i)=i$ and $\pi_{\beta,\gamma}(j)=k$.

Thus, by Theorem \ref{theorem:2transitive_capacity}, a sequence of affine-invariant codes of increasing length, rates converging to $r \in (0,1)$, achieve capacity on the BEC under bit-MAP decoding.
Some examples of great interest include generalized Reed-Muller codes \cite[Corollary 2.5.3]{Delsarte-ic70} and extended primitive narrow-sense BCH codes \cite[Theorem 5.1.9]{Huffman-2003}.
Below, we discuss Reed-Muller and BCH codes in more detail.

\subsection{Reed-Muller Codes}
\label{subsection:reed_muller_codes}

For integers $v,n$ satisfying $0\leq v \leq n$, the Reed-Muller code $\mr{RM}(v,n)$ is a binary linear code with length $N=2^n$ and rate $r = 2^{-n} \left(\binom{n}{0}+\dots+\binom{n}{v}\right)$.
Although it is possible to describe these codes from the perspective of affine-invariance \cite[Corollary 2.5.3]{Delsarte-ic70}, below, we treat them as polynomial codes \cite{Kasami-it68*2}.
This provides a far more powerful insight to their structure \cite{Delsarte-ic70,Delsarte-it70}.

Consider the set of $n$ variables, $x_1,\dots,x_n$.
For a monomial $x_1^{i_1}\cdots x_n^{i_n}$ in these variables, define its degree to be $i_1 + \cdots + i_n$.
A polynomial in $n$ variables is the linear combination (using coefficients from a field) of such monomials and the degree of a polynomial is defined to be the maximum degree of any monomial it contains.
It is well-known that the set of all $n$-variable polynomials of degree at most $v$ is a vector space over its field of coefficients.
In this section, the coefficient field is the Galois field $\mbb{F}_2$ and the vector space of interest is given by
\begin{align*}
  P(n,v) \!=\! \text{span} \{ x_1^{t_1}\dots x_n^{t_n} \mid t_1\!+\dots+\!t_n \leq v, t_i \in \{0,1\}\} .
\end{align*}
For a polynomial $f \in P(n,v)$, $f(\ul{x}) \in \{0,1\}$ denotes the evaluation of $f$ at $\ul{x}\in \{0,1\}^n$. 

Let the elements of the vector space $\{0,1\}^n$ over $\mbb{F}_2$ be enumerated by $\ul{e}_1,\ul{e}_2,\dots,\ul{e}_{N}$ with $\ul{e}_N=0^n$.
For any polynomial $f \in P(n,v)$, we can evaluate $f$ at $\ul{e}_i$ for all $i\in [N]$.
Then, the code $\mr{RM}(v,n)$ is defined to be the set 
\begin{align*}
  \mr{RM}(v,n) \triangleq \{ (f(\ul{e}_1),\dots,f(\ul{e}_{N})) \mid f \in P(n,v) \} .
\end{align*}

\begin{lemma} [{\hspace{-0.01cm}\cite[Corollary 4]{Kasami-it68}}]
\label{lemma:rm_2transitive}
The permutation group $\mc{G}$ of $\mr{RM}(v,n)$ is doubly transitive.
\end{lemma}
\begin{IEEEproof}
See Appendix~\ref{appendix:proof_rm_2transitive}.
\end{IEEEproof}

\begin{remark}
There is also a sequence of $\{\mr{RM}(v_n,n)\}$ codes with increasing blocklengths and rates approaching any $r\in(0,1)$.
To construct such a sequence, fix $r\in(0,1)$ and let $\{ Z_i \}$ be an iid sequence of Bernoulli($1/2$) random variables.
Then, the rate of the $\mr{RM}(v_n,n)$ code is
\begin{align*}
  r_n &= \frac{1}{2^n} \left(\binom{n}{0}+\dots+\binom{n}{v_n}\right) \\
  &= \Pr(Z_1+\dots+Z_n \leq v_n)
   \\
  &= \Pr\left( \frac{Z_1-\frac{1}{2} + \dots + Z_n-\frac{1}{2}}{\sqrt{n/4}} \leq \frac{v_n-\tfrac{n}{2}}{\sqrt{n/4}} \right) .
\end{align*}
Thus, by central limit theorem, if we choose 
\begin{align*}
  v_{n}=\max \left\{ \left\lfloor \frac{n}{2} + \frac{\sqrt{n}}{2} Q^{-1}(1-r) \right\rfloor , 0 \right\},
\end{align*}
then the rate of $\mr{RM}(v_n,n)$ satisfies $r_n \to r$ as $n \to \infty$.
Here, 
\begin{align*}
  Q(t) \triangleq \tfrac{1}{\sqrt{2\pi}} \int_t^\infty e^{-\tau^2/2} \diff{\tau}.  
\end{align*}
\end{remark}

\begin{theorem}
\label{theorem:rm_capacity_bitmap}
For any $r\in(0,1)$, the sequence of codes $\{ \mr{RM}(v_n,n) \}$ with
\begin{align*}
  v_{n} = \max \left\{ \left\lfloor \frac{n}{2} + \frac{\sqrt{n}}{2} Q^{-1}(1-r) \right\rfloor, 0 \right\},
\end{align*}
has rate $r_n \to r$ and is capacity achieving on the BEC under bit-MAP decoding.
\end{theorem}
\begin{IEEEproof}
This result follows as an immediate consequence of Lemma \ref{lemma:rm_2transitive} and Theorem \ref{theorem:2transitive_capacity}.
\end{IEEEproof}

We now analyze the block erasure probability of Reed-Muller codes.
The minimum distance of Reed-Muller codes is too small to utilize Theorem~\ref{theorem:capacity_blockerror_dmin}.
Thus, we use Theorem~\ref{theorem:capacity_blockerror_wn} instead.

For the code $\mr{RM}(v,n)$, consider the set $\Omega'_N$ from Definition \ref{definition:Omega} and \eqref{equation:Omega_prime}.
Let $\mc{G}_N$ be the permutation group of $\Omega'_N$ defined by
\begin{align*}
  \mc{G}_N \triangleq \{ \pi \in S_{N-1} \mid  \text{$\pi(\ul{a}) \in \Omega'_N$ for all $\ul{a} \in \Omega'_N$} \}.
\end{align*}

\begin{lemma}
\label{lemma:gl_gN}
For the permutation group $\mc{G}_N$ defined above, there is a transitive subgroup isomorphic to $\mr{GL}(n,\mbb{F}_2)$, the general linear group of degree $n$ over the Galois field $\mbb{F}_2$.
\end{lemma}
\begin{IEEEproof}
See Appendix~\ref{appendix:proof_gl_gN}.
\end{IEEEproof}

\begin{theorem}
\label{theorem:rm_capacity_blockmap}
For any $r \in (0,1)$, the sequence of codes $\{ \mr{RM}(v_n,n) \}$, with
\begin{align*}
  v_{n} = \max \left\{ \left\lfloor \frac{n}{2} + \frac{\sqrt{n}}{2} Q^{-1}(1-r) \right\rfloor, 0 \right\},
\end{align*}
has rate $r_n \to r$ and is capacity achieving on the BEC under block-MAP decoding.
\end{theorem}
\begin{IEEEproof}
Let the EXIT function associated with the last bit and the average EXIT function of the code $\mr{RM}(v_n,n)$ be $h_N$ and $h$, respectively.
Since the permutation group of $\mr{RM}(v_n,n)$ is transitive by Lemma \ref{lemma:rm_2transitive}, from Proposition \ref{proposition:transitive_exit}, $h=h_N$.
Moreover, by Lemma \ref{lemma:gl_gN}, $\mc{G}_N$ contains a transitive subgroup isomorphic to $\mr{GL}(n,\mbb{F}_2)$.

Now, we can exploit the $\mr{GL}(n,\mbb{F}_2)$ symmetry of $\Omega_N$ within the framework of \cite{Bourgain-gafa97}.
In particular, \cite[Theorem 1, Corollary 4.1]{Bourgain-gafa97} implies that there exists a universal constant $C>0$, independent of $n$ and $p$, such that 
\begin{align*}
  \deri{h_N(p)}{p} \!\geq\! C \log (\log N_n) \log (N_n) h_N(p)(1-h_N(p)),
\end{align*}
for $0 < a_n < p < b_n < 1$, where $N_n = 2^n $ and $a_n \to 0$, $b_n \to 1$ as $n \to \infty$.
Since $h=h_N$, Theorem~\ref{theorem:capacity_blockerror_wn} implies that $\{\mr{RM}(v_n,n)\}$ is capacity achieving on the BEC under block-MAP decoding.
\end{IEEEproof}
From this, we see that the block erasure probability goes to $0$ for $p<1-r$. 
For $p>1-r$, the average EXIT function $h(p)$ is bounded away from $0$.
Thus, Theorem~\ref{theorem:rm_capacity_bitmap} implies that the bit erasure probability $ph(p)$ is bounded away from $0$ but not converging to $1$.
The block erasure probability does converge to $1$, however.  This follows from the result in \cite{Tillich-cpc00} because the minimum distance of the code $\mr{RM}(v_n,n)$ tends to $\infty$ as $n\to \infty$.

\begin{remark}
The proof presented above of Theorem \ref{theorem:rm_capacity_blockmap} is based on the framework of \cite{Bourgain-gafa97}, which yields an extra factor of $\log(\log (N))$ in the expression of the derivative of the average EXIT function.
However, it is also possible to prove that the block erasure probability goes to $0$, for all $0\leq p<1-r$, by combining the analysis in Theorem~\ref{theorem:2transitive_capacity} with a careful upper bound on the weight distribution of Reed-Muller codes (see~\cite{Kudekar-isit16} for details).
\end{remark}

\subsection{Bose-Chaudhuri-Hocquengham Codes}
\label{subsection:bch_codes}

Let $\alpha$ be a primitive element of $\mbb{F}_{2^n}$.
Recall that a binary BCH code is \emph{primitive} if its blocklength is of the form $2^n-1$, and \emph{narrow-sense} if the roots of its generator polynomial include consecutive powers of a primitive element starting from $\alpha$.
In this article, we consider only primitive narrow-sense BCH codes and we follow closely the treatment of BCH codes in \cite{Huffman-2003}.

For integers $v$, $n$ with $1 \leq v \leq 2^n-1$, let $f(n,v)$ be the polynomial of lowest-degree over $\mbb{F}_2$ that has the roots
\begin{align*}
  \alpha,\alpha^2,\dots,\alpha^{v} .
\end{align*}
Then, $\mr{BCH}(v,n)$ is defined to be the binary cyclic code with the generator polynomial $f(n,v)$ and blocklength $N=2^n-1$.
This is precisely the primitive narrow-sense BCH code with blocklength $N$ and designed distance $v+1$.

The dimension $K$ of the cyclic code is determined by the degree of the generator polynomial according to \cite[Theorem 4.2.1]{Huffman-2003}
\begin{align*}
  K=N-\text{degree}(f(n,v)) .
\end{align*}
Moreover, the minimum distance $d_{\mathrm{min}}$ of $\mr{BCH}(v,n)$ is at least $v+1$ \cite[Theorem 5.1.1]{Huffman-2003}.

In addition, it is possible to construct a sequence of BCH codes whose rates converge to any $r \in (0,1)$.
Since $\mbb{F}_{2^n}$ is the splitting field of the polynomial $x^N-1$ \cite[Theorem 3.3.2]{Huffman-2003}, it is easy to see that $\text{degree}(f(n,N)) = N$.
Also, since the size of the cyclotomic coset of any element $\alpha^i$ is at most $n$ \cite[Section 3.7]{Huffman-2003}, we have that $\text{degree}(f(n,1)) \leq n$ and
\begin{align*}
  0 \leq \text{degree}(f(n,v+1))-\text{degree}(f(n,v)) \leq n.
\end{align*}
Thus, for any $r \in(0,1)$, one can choose $v_{n} \in [N]$ such that
\begin{align*}
  N(1-r) \leq \text{degree}(f(n,v_{n})) \leq N(1-r) + n .
\end{align*}
Now, it is easy to see that $v_{n} \geq N(1-r)/n$ and the rate of the code $\mr{BCH}(v_n,n)$ will be in $[r-\frac{n}{N},r]$.
Thus, the rates of $\{\mr{BCH}(v_n,n)\}$ converge to $r$.

Consider the length-$2^n$ extended BCH code, $\mr{eBCH}(v,n)$, which is formed by adding a single parity bit to the code $\mr{BCH}(v,n)$ so that the overall codeword parity is $0$~\cite[Section 5.1]{Huffman-2003}.
The code $\mr{eBCH}(v,n)$ has the same dimension as $\mr{BCH}(v,n)$ and a minimum distance of at least $v+1$.

Thus, for any $r\in(0,1)$, there exists a sequence of codes $\{ \mr{eBCH}(v_n,n) \}$ with blocklengths $N_n=2^n$, rates $r_n \to r$ and minimum distances
\begin{align}
  \label{equation:bch_dmin}
  d_{\mathrm{min}}^{(n)} \geq 1+v_{n} \geq 1+\frac{N_n(1-r)}{n} .
\end{align}

An important property of the extended BCH codes is that they are affine-invariant \cite[Theorem 5.1.9]{Huffman-2003}.
Thus, Section~\ref{subsection:affine_invariant_codes} shows that their permutation group is doubly transitive.
Therefore, we have the following theorem.
\begin{theorem}
\label{theorem:bch_capacity_bitmap}
For any $r \in (0,1)$, there is a sequence $\{v_n\}$ such that the code sequence $\{ \mr{eBCH}(v_n,n) \}$ has $r_n\to r$ and is capacity achieving on the BEC under bit-MAP decoding.
\end{theorem}

In the following, we discuss the block erasure probability of BCH codes.
It is possible to characterize the permutation group of the code $\mr{eBCH}(v,n)$ precisely.
According to \cite{Berger-it96,Berger-des99}, except in sporadic cases, the permutation group of the code $\mr{eBCH}(v,n)$ is equal to the affine semi-linear group.
Unfortunately, in the framework of \cite{Bourgain-gafa97}, this group does not produce any factors beyond order $\log(N)$.
This is in contrast with Reed-Muller codes where it was possible to exploit $\mr{GL}(n,\mbb{F}_2)$ symmetry to analyze their block erasure probability.
It is worth noting that the only primitive codes over a prime field whose permutation group includes the general linear group of degree $n$ are variants of generalized Reed-Muller codes~\cite{Delsarte-it70}.

For BCH codes, however, the minimum distance is large enough to use Theorem~\ref{theorem:capacity_blockerror_dmin}.
In fact, the minimum distance of the code $\mr{eBCH}(v_n,n)$ from \eqref{equation:bch_dmin} satisfies
\begin{align}
\label{equation:bch_dmin_limit}
  \lim_{n \to \infty} \frac{\log d_{\mathrm{min}}^{(n)}}{\log N_n} = 1.
\end{align}
Since the permutation group of the code $\mr{eBCH}(v_n,n)$ is doubly transitive from affine-invariance, by Theorem~\ref{theorem:width_bound} and the proof of Theorem \ref{theorem:2transitive_capacity}, its average EXIT function satisfies the hypothesis of Theorem~\ref{theorem:capacity_blockerror_dmin}.
Combining this observation with \eqref{equation:bch_dmin_limit} gives the following result.
\begin{theorem}
\label{theorem:bch_capacity_blockmap}
For any $r\in (0,1)$, there is a sequence $\{v_n\}$ such that the code sequence $\{ \mr{eBCH}(v_n,n) \}$ has $r_n\to r$ and is capacity achieving on the BEC under block-MAP decoding.
\end{theorem}

\begin{theorem}
\label{theorem:bch_capacity}
For any $r\in (0,1)$, there is a sequence $\{v_n\}$ such that the code sequence $\{ \mr{BCH}(v_n,n) \}$ has $r_n\to r$ and is capacity achieving on the BEC under both bit-MAP and block-MAP decoding.
\end{theorem}
\begin{IEEEproof}
The result for bit-MAP decoding follows from Theorem~\ref{theorem:bch_capacity_bitmap} and Proposition~\ref{proposition:code_modification}.
Also, by conditioning on the event that the overall parity bit is erased in the received vector, we observe that
\begin{align*}
  P_B^{\mr{eBCH}}(p) \geq p P_B^{\mr{BCH}}(p) ,
\end{align*}
where $P_B^{\mr{eBCH}}$ and $P_B^{\mr{BCH}}$ are the block error probabilities for the codes $\mr{eBCH}$ and $\mr{BCH}$, respectively.
The result for the block-MAP decoding follows.
\end{IEEEproof}

\begin{remark}
Theorem~\ref{theorem:bch_capacity} also shows that there are sequences of binary cyclic codes that achieve capacity on the BEC.
As far as the authors know, this is the first proof that such a sequence exists~\cite{Ordentlich-it12}.
\end{remark}

\subsection{Quadratic-Residue Codes}
\label{subsection:quadratic_residue}
For $a,b \in \mbb{N}$, $a$ is a \emph{quadratic residue} modulo $b$ if there exists $x \in \mbb{N}$ such that $x^2 \equiv a \bmod b$.
Let $q$ be a prime power and $N$ be an odd prime that does not divide $q$.
A quadratic-residue code of blocklength $N$ over $\mbb{F}_q$ exists if $q$ is a quadratic residue modulo $N$~\cite[Theorem~6.6.2]{Huffman-2003}.

The set of non-zero squares in $\mbb{F}_N$, $Q\triangleq\{ x^2 \, | \, x\in \mbb{F}_N \setminus \{0\} \}$, has $|Q|=(N-1)/2$ elements~\cite[Lemma~6.6.1]{Huffman-2003}.
Let $\alpha$ be a primitive $N$-th root of unity in the field $\mbb{F}_{q^n}$.
If $q$ is a quadratic residue modulo $N$ (i.e., $q\in Q$), then the polynomial
\begin{align*}
  g(x)=\prod_{i \in Q} (x - \alpha^i)
\end{align*}
has coefficients in $\mbb{F}_q$ and generates an $(N,(N+1)/2)$ cyclic quadratic-residue code~\cite[Section~6.9]{vanLint-1999}.
An extended quadratic-residue code is formed by adding a parity symbol that makes the blocklength $N+1$ and the rate~$1/2$~\cite[Section~6.6.3]{Huffman-2003}.
An important property of extended quadratic-residue codes is that their permutation group contains a subgroup isomorphic to $\mr{PSL}(2,\mbb{F}_N)$, the projective special linear group of degree $2$ over $\mbb{F}_N$ \cite{Blahut-it91,Huffman-2003,vanLint-1999,Macwilliams-1977}.
As such, their permutation group is doubly transitive.

To construct a capacity-achieving sequence\footnote{We refer the reader to Section~\ref{section:Fqlinear} for a discussion on the $\mbb{F}_q$ linear codes over the $q$-ary erasure channel.} (under symbol-MAP decoding) of quadratic-residue codes over $\mbb{F}_q$, one needs arbitrarily large prime numbers under which $q$ is a quadratic residue.
Using a variation of Euclid's proof that there are infinitely many prime numbers~\cite[Theorem 4]{Hardy-1979}, one can show the existence of arbitrarily large prime numbers that have $q$ as a quadratic residue.
Note that any prime factor of $M^2-q$ has $q$ as a quadratic residue.
Suppose, for the sake of contradiction, that there are only a finite number of distinct prime numbers $N_1,N_2,\ldots,N_m$ such that $q$ is a quadratic residue modulo $N_i$ and $N_i$ is coprime with $q$.
Then, let $M= \prod_{i=1}^m N_i$ and observe that $M^2 - q$ is not divisible by any $N_i$ because otherwise that $N_i$ must divide $q$.
However, $M^2 - q$ must be divisible by some prime $N'$ and $N'$ must be coprime with $q$, because otherwise $N'$ would divide $M$ and, thus, equal some $N_i$.
Hence, $q$ is a quadratic residue modulo $N'$ and one gets a contradiction.
This implies that there are infinitely many primes that are coprime with $q$ and have $q$ as a quadratic residue.

Therefore, any sequence of (extended) quadratic-residue codes over $\mbb{F}_q$ with increasing length must achieve capacity on the $q$-ary erasure channel. 



\section{Main Results}
\label{section:general}

At this point, we have all the ingredients to prove the main technical results of the paper. 

\begin{theorem}
\label{theorem:2transitive_capacity}
Let $\{\mc{C}_n\}$ be a sequence of codes where the blocklengths satisfy $N_n \to \infty$, the rates satisfy $r_n \to r$, and the permutation group $\mc{G}^{(n)}$ (of $\mc{C}_n$) is doubly transitive for each $n$.
If $r\in (0,1)$, then $\{\mc{C}_n\}$ is capacity achieving on the BEC under bit-MAP decoding.
\end{theorem}
\begin{IEEEproof}
Let the average EXIT function of $\mc{C}_n$ be $h^{(n)}$.
The quantities $N$, $\mc{G}$, $h$, $h_i$, $\Omega'_i$, and $p_t$ that appear in this proof are all indexed by $n$; we drop the index to avoid cluttering.
Fix some $i \in [N]$.
Since $\mc{G}$ is transitive, from Proposition \ref{proposition:transitive_exit},
\begin{align*}
  h(p) = h_i(p), \quad \text{for all $p \in [0,1]$.}
\end{align*}
Consider the sets $\Omega'_i$ from Definition \ref{definition:Omega} and \eqref{equation:Omega_prime}, and let $M=N-1$.
Observe that, from Proposition \ref{proposition:scalar_exit_properties},
\begin{align*}
  h_i(p) &= \mu_p(\Omega'_i), &  I_j^{(p)}(\Omega'_i) &= \pderi{h_i(\ul{p})}{p_{j'}} \Big{\lvert}_{\ul{p}=(p,\dots,p)} ,
\end{align*}
where $j'$ is given in \eqref{equation:jprime}.
Since $\mc{G}$ is doubly transitive, from Proposition \ref{proposition:2transitive_exit_deri},
\begin{align*}
  I_j^{(p)}(\Omega'_i) = I_k^{(p)}(\Omega'_i) \quad \text{for all $j,k \in [N-1]$}.
\end{align*}
Using Theorem \ref{theorem:width_bound}, we have
\begin{align}
  \label{equation:factorlog}
  p_{1-\epsilon} - p_{\epsilon} \leq \frac{2}{C} \frac{\log \frac{1-\epsilon}{\epsilon}}{ \log (N-1)} ,
\end{align}
where $p_t$ is the functional inverse of $h$ from \eqref{equation:h_inverse}.
Since $N \to \infty$ from the hypothesis,
\begin{align*}
  \lim_{n \to \infty} \left( p_{1-\epsilon} - p_{\epsilon} \right) = 0.
\end{align*}
Therefore, from Proposition \ref{proposition:capacity_equivalence}, $\{\mc{C}_n\}$ is capacity achieving on the BEC under bit-MAP decoding.
\end{IEEEproof}

We now focus on the block erasure probability.
Recall from \eqref{equation:erasure_prob_relations} and \eqref{equation:erasure_prob_dmin} that the block erasure probability satisfies the upper bounds
\begin{align*}
  P_B &\leq \frac{N P_b}{d_{\mathrm{min}}}, & P_B &\leq N P_b.
\end{align*}
Thus, if $P_b\to 0$ with sufficient speed, then $P_B \to 0$ as well.

Using \eqref{equation:differential_inequality}, one can derive the upper bound (see Lemma~\ref{lemma:exit_integral_generic} in Appendix \ref{appendix:proofs_section_inequalities} for a proof)
\begin{align}
  \label{equation:mu_decayrate}
  \mu_{p}(\Omega) \leq \exp \left( -w [p_{1/2} - p] \right),
\end{align}
where $p_{1/2} \in [0,1]$ is defined uniquely by $\mu_{p_{1/2}}(\Omega)=1/2$.
Combining \eqref{equation:mu_decayrate} with \eqref{equation:factorlog}, one can show that for any $0 \leq p < 1-r$, there exists $\delta >0$ such that for sufficiently large $N$,
\begin{align}
  \label{equation:pb_decayrate}
  P_b(p) \leq N^{-\delta}.
\end{align}

This observation motivates the following theorem, which proves that, if $d_{\mathrm{min}}$ satisfies $\log(d_{\mathrm{min}})/\log(N) \to 1$, then the decay rate of $P_b$ is also sufficient to show that $P_B \to 0$.

\begin{theorem}
\label{theorem:capacity_blockerror_dmin}
Let $\{\mc{C}_n\}$ be a sequence of codes where the blocklengths satisfy $N_n \to \infty$ and the rates satisfy $r_n \to r$ for $r\in (0,1)$.
Suppose that the average EXIT function of $\mc{C}_n$ also satisfies, for $0<p<1$,
\begin{align*}
  \deri{h^{(n)}(p)}{p} \geq  C \log (N_n) h^{(n)}(p) (1-h^{(n)}(p)),
\end{align*}
where $C>0$ is a constant independent of $p$ and $n$.
If the minimum distances $\{ d_{\mathrm{min}}^{(n)} \}$ satisfy
\begin{align*}
	\lim_{n \to \infty}  \frac{\log d_{\mathrm{min}}^{(n)}}{\log N_n} = 1,
\end{align*}
then $\{\mc{C}_n\}$ is capacity achieving on the BEC under block-MAP decoding.
\end{theorem}
\begin{IEEEproof}
  See Appendix \ref{appendix:proof_capacity_blockerror_dmin}.
\end{IEEEproof}

If $d_{\mathrm{min}}$ does not grow rapidly enough (e.g., sequences of Reed-Muller codes with rates $r_n \to r \in (0,1)$ have $d_{\mathrm{min}} = O(\sqrt{N}^{1+\delta})$ for any $\delta>0$), then the previous theorem does not apply.
Fortunately, it is possible to exploit symmetries, beyond the double transitivity of the permutation group, to obtain inequalities like \eqref{equation:differential_inequality} that grow asymptotically faster than $\log(N)$~\cite{Bourgain-gafa97}.
In particular, one obtains inequalities of type \eqref{equation:differential_inequality}, with factors of higher order than $\log(N)$, for all $p$ except a neighborhood around $0$ and $1$ that vanishes as $N\to \infty$.
The following theorem shows that this is sufficient to show that $P_B \to 0$ without imposing requirements on $d_{\mathrm{min}}$.

\begin{theorem}
\label{theorem:capacity_blockerror_wn}
Let $\{\mc{C}_n\}$ be a sequence of codes where the blocklengths satisfy $N_n \to \infty$ and the rates satisfy $r_n \to r$ for $r\in (0,1)$.
Suppose that the average EXIT function of $\mc{C}_n$ also satisfies, for $a_n<p<b_n$,
\begin{align*}
  \deri{h^{(n)}(p)}{p} \geq  w_n \log (N_n) h^{(n)}(p) (1-h^{(n)}(p)),
\end{align*}
where  $w_n \to \infty$, $a_n \to 0$, $b_n \to 1$ and $0 \leq a_n < b_n \leq 1$.
Then, $\{\mc{C}_n\}$ is capacity achieving on the BEC under block-MAP decoding.
\end{theorem}
\begin{IEEEproof}
See Appendix \ref{appendix:proof_capacity_blockerror_wn}.
\end{IEEEproof}

Combining Theorem~\ref{theorem:capacity_blockerror_dmin} or~\ref{theorem:capacity_blockerror_wn} with the results in \cite{Tillich-cpc00}, one can show that for any $ 0 \leq p  < 1-r$, there exists a $\delta > 0$ such that for sufficiently large $N$,
\begin{align*}
  P_B(p) \leq \exp(-\delta d_{\mathrm{min}}(N))  ,
\end{align*}
where $d_{\mathrm{min}}(N)$ is the minimum distance of codes in the sequence as a function of $N$.
In general, this provides a much faster decay rate than the one obtained in \eqref{equation:pb_decayrate}.


\subsection{Overview}
Since the introduction of channel capacity by Shannon in his seminal paper~\cite{Shannon-bell48}, theorists have been fascinated by the idea of constructing codes that achieve capacity (e.g., under optimal decoding). Ideally, one would also like these codes to have:
low-complexity encoding/decoding \emph{algorithms},
algebraic or geometric \emph{structure},
and \emph{deterministic} constructions.

\iffalse
\begin{itemize}
\item \emph{Capacity:} capacity-achieving under optimal decoding.
\item \emph{Structure:} structured codes (typical of algebraic or geometric nature) can often be exploited when designing encoding and decoding algorithms and helps in mapping the algorithm into hardware.
\item \emph{Deterministic:} this eliminates the need to choose a ``typical'' code from a given ensemble, a problem that has aptly been called the ``finding hay in a haystack problem''.
\item \emph{Algorithms:} codes with low-complexity encoding and decoding techniques that have good performance.
\end{itemize}
\fi

The advent of Turbo codes~\cite{Berrou-icc93} and low-density parity-check (LDPC) codes~\cite{Gallager-1963,Spielman-it96,Mackay-it99} has made it possible to construct practical codes that achieve good performance near the Shannon limit.
It was even proven that sequences of irregular LDPC codes can achieve \emph{capacity} on the binary erasure channel (BEC) using low-complexity message-passing 
\emph{algorithms}~\cite{Luby-it01}.

Recently, spatially-coupled LDPC codes were shown to achieve \emph{capacity} universally over the class of binary memoryless symmetric (BMS) channels using low-complexity message-passing \emph{algorithms}~\cite{Kudekar-it11,Lentmaier-it10,Kudekar-it13,Kumar-it14}.
In regards to the other desirable properties, these codes also have some \emph{structure} (e.g., low-density graph structure) but their construction is not \emph{deterministic}.

For an arbitrary BMS channel, however, polar codes~\cite{Arikan-it09} were the first codes proven to achieve \emph{capacity} with low-complexity encoding and decoding \emph{algorithms}.
In addition, polar codes inherit some \emph{structure} from the Hadamard matrix and also have a \emph{deterministic} construction.

This article considers the performance of \emph{structured} and \emph{deterministic} binary linear codes transmitted over the BEC under bitwise maximum-a-posteriori (MAP) decoding.
In particular, our primary technical result is the following.
\begin{theorem*}
 A sequence of linear codes achieves capacity on a memoryless erasure channel under bit-MAP decoding if its blocklengths are strictly increasing, its code rates converge to some $r\in(0,1)$, and the permutation group\footnote{The permutation group of a linear code is the set of permutations on code bits under which the code is invariant.} of each code is doubly transitive.	
\end{theorem*}
The analysis focuses primarily on the bit erasure rate under bit-MAP decoding, but it can be extended to the block erasure rate in some cases.
One important consequence is a proof of the fact that binary Reed-Muller codes achieve capacity on the BEC under block-MAP decoding, which settles a rather old conjecture in coding theory.

The main result extends naturally to $\mathbb{F}_q$-linear codes transmitted over a $q$-ary erasure channel under symbol-MAP decoding.
With this extension, one can show that sequences of Generalized Reed-Muller codes~\cite{Delsarte-ic70,Kasami-it68} over $\mathbb{F}_q$ also achieve capacity under block-MAP decoding.
For the class of affine-invariant $\mathbb{F}_q$-linear codes, which are precisely the codes whose permutation groups include a subgroup isomorphic to the affine linear group~\cite{Kasami-ic68}, one finds that these codes achieve capacity under symbol-MAP decoding.
This follows from the fact that the affine linear group is doubly transitive.
As it happens, this class also includes all extended primitive narrow-sense Bose-Chaudhuri-Hocquengham (BCH) codes~\cite{Kasami-ic68}.
Additionally, we show that sequences of extended primitive narrow-sense BCH codes over $\mathbb{F}_q$ achieve capacity under block-MAP decoding.
To keep the presentation simple, we present proofs for the binary case and discuss the generalization to $\mathbb{F}_q$ in Section~\ref{section:Fqlinear}.

These results are rather surprising.
Until the discovery of polar codes, it was unclear whether or not codes with a simple deterministic structure could even achieve capacity~\cite{Ahlswede-it82,Coffrey-it90}. 
But even though polar codes (as well as Reed-Muller codes) derive from the Hadamard matrix, the ability of polar codes to achieve capacity appears unrelated to the inherent symmetry of this matrix.
In contrast, the performance guarantees obtained here are a consequence only of linearity and the structure induced by the doubly-transitive permutation group.

\subsection{Reed-Muller Codes}
Reed-Muller codes were introduced by Muller in~\cite{Muller-ire54} and, soon after, Reed proposed a majority logic decoder in~\cite{Reed-ire54}.
A binary Reed-Muller code, parameterized by non-negative integers $n$ and $v$, is a linear code of length $2^n$ and dimension $\binom{n}{0}+\cdots+\binom{n}{v}$.
It is well known that the minimum distance of this code is $2^{n-v}$~\cite{Macwilliams-1977,Lin-2004,Delsarte-ic70}.
Thus, it is impossible to simultaneously have a non-vanishing rate and a minimum distance that scales linearly with blocklength.
This implies that for any such code sequence whose rate converges to a value in $(0,1)$ the minimum distance grows roughly like the square root of the blocklength.

The idea that Reed-Muller codes might achieve capacity appears to be rather old.
In a personal communication with Shu Lin, we learned that this possibility was discussed privately by Kasami, Lin, and Peterson in the late 1960s.
Later the idea was mentioned explicitly in a 1993 talk by Shu Lin, entitled ``RM Codes are Not So Bad'' \cite{Lin-itw93}.
To the best of the authors' knowledge, a 1994 paper by Dumer and Farrell contains the earliest printed discussion of this question~\cite{Dumer-ac94}.
In that paper, they show that some sequences of BCH codes with rates approaching 1 have a vanishing gap to capacity on the BEC.
They also suggest, as an open problem, the evaluation of a quantity which equals 1 if and only if Reed-Muller codes achieve capacity on the BEC.
Since then, similar ideas have been discussed by a variety of authors~\cite{Carlet-isit05,Didier-it06,Costello-proc07,Arikan-it09,Arikan-itw10,Mondelli-com14,Abbe-arxiv14,  Abbe-stoc15}.
In particular, short Reed-Muller codes with erasures were investigated in~\cite{Carlet-isit05,Didier-it06} and it was observed numerically that the block erasure rate is quite close to that of random codes.
In~\cite{Mondelli-com14}, a modified construction of polar codes is analyzed and the results again suggest that Reed-Muller codes achieve capacity on the BEC.
For rates approaching either $0$ or $1$ with sufficient speed, it has recently been shown by Abbe et al.\ that Reed-Muller codes can correct almost all erasure patterns up to the capacity limit\footnote{It requires some effort to define precisely what capacity limit is for rates approaching $0$ or $1$. See \cite[Definition 2.5]{Abbe-arxiv14} for details.} \cite{Abbe-arxiv14, Abbe-stoc15}.
Beyond erasure channels, it is conjectured in~\cite{Costello-proc07} that the sequence of rate-$1/2$ self-dual Reed-Muller codes achieves capacity on the binary-input AWGN channel.

Even 50 years after their discovery, Reed-Muller codes remain an active area of research in theoretical computer science and coding theory.
The early work in~\cite{Sloane-it70,Kasami-it70,Kasami-ic76} culminated in obtaining asymptotically tight bounds (fixed order $v$ and asymptotic $n$) for their weight distribution~\cite{Kaufman-it12}.
Also, there is considerable interest in constructing low-complexity decoding algorithms, see \cite{Sidelnikov-ppi92,Saptharishi-arxiv15} and a series of papers by Dumer et al.~\cite{Dumer-it04,Dumer-it06*2,Dumer-it06}.
Undoubtedly, interest in the coding theory community for these codes was rekindled by the tremendous success of polar codes and their close connection to Reed-Muller codes~\cite{Arikan-it09,Arikan-comlett08,Mondelli-com14}.

Due to their desirable structure, constructions based on these codes are used extensively in cryptography~\cite{Camion-acrypt92,Ta-shma-focs01,Shaltiel-focs01,Canteaut-it01,Carlet-isit05,Carlet-it06,Didier-fse06,Gerard-alc11}.
Reed-Muller codes are also known for their \emph{locality} \cite{Yekhanin-fnt11}.
Some of the earliest known constructions for locally correctable codes are based on these codes \cite{Gemmell-stoc91,Gemmell-ipl92}.
Interestingly, local correctability of Reed-Muller codes is also a consequence of its permutation group being doubly transitive \cite{Kaufman-approxrandom10}, a crucial requirement in our approach.
However, a doubly-transitive permutation group is not sufficient for local testability \cite{Grigorescu-ccc08}.

\subsection{Outline of the Proof}
The central object in our analysis is the extrinsic information transfer (EXIT) function.
EXIT charts were introduced by ten Brink in the context of turbo decoding as a visual tool to understand iterative decoding~\cite{tenBrink-elet99}.
For a given input bit, the EXIT function is defined to be the conditional entropy of the input bit given the outputs associated with \emph{all other} input bits.
The {\em average} EXIT function is formed by averaging all of the bit EXIT functions.
We note that these functions are also instrumental in the design and analysis of LDPC codes~\cite{RU-2008}.

The crucial property we exploit is the so called area theorem, originally proved in~\cite{Ashikhmin-it04} and further generalized in~\cite{Measson-it08}, which says that the area under the average EXIT function equals the rate of the code. The average EXIT function is also directly related to the bit erasure probability under MAP decoding.
Indeed, for a sequence of binary linear codes with rate $r$ to be capacity achieving, the average EXIT function must converge to 0 for any erasure rate below $1-r$.
Since the area under each average EXIT curve is fixed to $r$, the EXIT functions in the code sequence must converge to 1 for any erasure value above $1-r$.
Thus, the EXIT curves must exhibit a \emph{sharp transition} from $0$ to $1$ and, as a consequence of area theorem, this transition must occur at the erasure value $1-r$.

We investigate the threshold behavior of EXIT functions for certain binary linear codes via sharp thresholds for monotone boolean functions~\cite{Boucheron-2013,Kalai-05}.
The general method was pioneered by Margulis~\cite{Margulis-ppi74} and Russo~\cite{Russo-prf82}.
Later, it was significantly generalized in~\cite{Talagrand-gafa93} and~\cite{Talagrand-ap94}.
This approach has been applied to many problems in theoretical computer science with remarkable success \cite{Friedgut-procams96,Friedgut-jams99,Dinur-am05}.
In the context of coding theory, this technique was first introduced by Z\'emor in \cite{Zemor-94}, refined further in~\cite{Tillich-cpc00}, and also extended to AWGN channels in~\cite{Tillich-it04}.
For the BEC, it is shown in \cite{Zemor-94,Tillich-cpc00} that the block erasure rate jumps from $0$ to $1$ as the minimum distance of the code grows.
However, focusing on the block erasure rate does not allow one to establish the location of the threshold.
In order to show the threshold behavior for EXIT functions, we instead focus on symmetry~\cite{Friedgut-procams96} which follows if the codes have doubly-transitive permutation groups.

The article is organized as follows.
Section \ref{section:preliminaries} includes the necessary background on EXIT functions, permutation groups of linear codes, and capacity-achieving codes.
Section \ref{section:sharp_threshold} deals with the threshold behavior of monotone boolean functions.
Section \ref{section:general} presents the main technical results of the paper. 
In Section \ref{section:applications}, as an application of the hitherto analysis, we show that Reed-Muller codes, extended primitive narrow-sense BCH codes, and quadratic-residue codes achieve capacity.
Finally, we provide extensions, open problems in Section \ref{section:discussion}, and concluding remarks in Section \ref{section:conclusion}.


\section{Introduction}
\input{introduction}

\section{Preliminaries}
\input{preliminaries}

\section{Sharp Thresholds for Monotone Boolean Functions}
\input{inequalities}

\section{Applications}
\input{applications}

\section{Discussion}
\label{section:discussion}

\subsection{Comparison with the Work of Tillich and Z{\'e}mor}
\label{section:TillichZemor}
There is another popular approach, based on isoperimetric inequalities, to derive inequalities with the same form as~\eqref{equation:differential_inequality}.
This requires a different formulation of Margulis-Russo lemma.
First, let us define the function $g_{\Omega} \colon \{0,1\}^{M} \to \mathbb{N} \cup \{0\}$, which quantifies the boundary between $\Omega$ and $\Omega^c$,
\begin{align} \label{equation:boundary}
  g_{\Omega}(\ul{x}) \triangleq
  \begin{cases}
    \Big{\lvert}\{ \ul{y} \in \Omega^c \mid d_{\mathrm{H}}(\ul{x},\ul{y}) = 1 \}\Big{\rvert} & \text{if $\ul{x} \in \Omega$}, \\
    0 & \text{if $\ul{x} \notin \Omega$} ,
  \end{cases}
\end{align}
where $d_{\mathrm{H}}$ is the Hamming distance.
Margulis-Russo lemma (Lemma~\ref{lemma:margulis_russo}) can also stated in terms of $g_{\Omega}$:
\begin{align*}
  \frac{\diff{\mu_p(\Omega)}}{\diff{p}} = \frac{1}{p} \int g_{\Omega}(\ul{x}) \mu_p(\diff{\ul{x}}) .
\end{align*}
To obtain inequalities of type \eqref{equation:differential_inequality}, it is possible to find a lower bound on $g_{\Omega}$ that holds whenever it is non-zero~\cite{Margulis-ppi74,Russo-prf82}.

These techniques were introduced to coding by Tillich and Z{\'e}mor to analyze the block error rate of linear codes under block-MAP decoding~\cite{Zemor-94,Tillich-cpc00}.
In that case, the minimum non-zero value of $g_{\Omega}$ is proportional to the minimum distance of the code. 
Our initial attempts to prove a sharp threshold for EXIT functions focused on analyzing~\eqref{equation:boundary} with $\Omega=\Omega_i $.
In particular, our aim was to generalize~\cite{Tillich-cpc00} to EXIT functions by finding a lower bound on $g_{\Omega_i} (\ul{x})$ that holds uniformly over the boundary
$$\partial \Omega_i \triangleq \{ \ul{x}\in\{0,1\}^{N} \,|\, g_{\Omega_i} (\ul{x}) >0 \}.$$
For code sequences where $d_{\mathrm{min}} \to \infty$, we expected that $\min_{\ul{x}\in \partial \Omega_i} g_{\Omega_i} (\ul{x})$ would grow without bound and, thus, that the EXIT function would have a sharp threshold.
Unfortunately, this is not true.
In fact, the ensemble of $(j,k)$-regular LDPC codes provides a counterexample.
With high probability, their minimum distance grows linearly with $N$ but one iteration of iterative decoding shows that the EXIT function is upper bounded by $(1-(1-p)^{k-1})^j$ for all $p$ and $N$~\cite{RU-2008}. 

To understand this, first recall that a weight-$d$ codeword in the dual code defines a subset of $d$ code bits that sum to 0.
If only one of the bits in this dual codeword is erased, then that bit can be recovered indirectly from the other bits.
To see this in terms of the boundary, consider the indirect recovery of bit-$i$ and assume that it is contained in a weight-$d$ dual codeword with $d=d_{\mathrm{min}}^{\perp}\geq 3$.
Let $\ul{x}$ be an erasure pattern where $d-2$ of the $d-1$ other bits in the dual codeword are received correctly and all other bits are erased.
Then, $\ul{x} \in \Omega_i$ and bit-$i$ cannot be recovered indirectly.
Also, bit-$i$ can be recovered indirectly if the erased bit (say bit $j$) in the dual codeword is revealed.
Thus, $\ul{x}^{(j)} \notin \Omega_i$.
For the notation $\ul{x}^{(j)}$, see Definition~\ref{definition:influence}.

Now, let us consider $g_{\Omega_i} (\ul{x})$.
If there is any other bit (say bit $k$) for which $\ul{x}^{(k)} \notin \Omega_i$, then the pattern of correctly received symbols in $\ul{x}^{(k)}$ (along with bit $i$) must cover a dual codeword.
Since $\ul{x}^{(k)}$ contains exactly $d-1$ zero (i.e., unerased) symbols and the minimum dual distance is $d$, it follows that $\ul{x}^{(k)}$ must be a dual codeword.
Due to linearity, one can add the two vectors to get $\ul{x}^{(j)} + \ul{x}^{(k)}$, which clearly has weight 2.
However, this contradicts the assumption that the minimum dual distance is $d_{\mathrm{min}}^{\perp} \geq 3$.
Thus, we find that only bit $j$ is pivotal for $\ul{x}$ and
$$\min_{\ul{x} \in \partial \Omega_i} g_{\Omega_i} (\ul{x})=1.$$

This shows that the method of~\cite{Tillich-cpc00} does not extend automatically to prove sharp thresholds for EXIT functions.
While it is possible that there is a simple modification that overcomes this issue, we did not find it.

\subsection{Conditions of Theorem~\ref{theorem:2transitive_capacity}}
\label{section:relaxing_2transitivity}
One natural question is whether or not the conditions of Theorem~\ref{theorem:2transitive_capacity} can be weakened.
We make the following optimistic conjecture.
\begin{conjecture}
Let $\{\mc{C}_n\}$ be a sequence of binary linear codes where the blocklengths satisfy $N_n \to \infty$, the rates satisfy $r_n \to r$ for $r\in (0,1)$, and the permutation group of each code is transitive.
If the sequence of minimum distances satisfies $d_{\mathrm{min}}^{(n)} \to \infty$ and the sequence of minimum dual distances satisfies $d_{\mathrm{min}}^{\perp (n)} \to \infty$, then the sequence achieves capacity on the BEC under bit-MAP decoding.
\end{conjecture}

If the permutation groups of the codes in the sequence are not transitive, then different bits may have different EXIT functions with phase transitions at different values of $p$ (e.g., if some of the bits are protected by a random code of one rate and other bits with a random code of a different rate).
Even if the permutation groups are transitive, things can still go wrong.
Consider any sequence of codes with transitive permutation groups and increasing length.
Let $\{d_{\mathrm{min}}^{(n)}\}$ be the sequence of minimum distances.
Then, symmetry implies that the erasure rate of bit-MAP decoding is lower bounded by $p^{d_{\mathrm{min}}^{(n)}}$ for a BEC($p$) (e.g., every code bit is covered by a codeword with weight $d_{\mathrm{min}}$).
Thus, the sequence does not achieve capacity if $d_{\mathrm{min}}^{(n)}$ has a uniform upper bound.
Based on duality, a similar argument holds if the sequence of minimum dual distances $\{d_{\mathrm{min}}^{\perp (n)}\}$ is upper bounded.
Thus, to achieve capacity, a necessary condition is that $d_{\mathrm{min}}^{(n)} \to \infty$ and $d_{\mathrm{min}}^{\perp (n)} \to \infty$.

For two linear codes $\mathcal{C},\mathcal{C}'$ defined over the same field, the \emph{direct sum} equals $\{ (\ul{c},\ul{c}')\,|\, \ul{c}\in \mathcal{C},\ul{c}'\in\mathcal{C}'\}$~\cite[p.~76]{Macwilliams-1977}.
A linear code is called \emph{irreducible} if it is not equivalent to the direct sum of shorter codes.
By induction, any \emph{reducible} code is equivalent to the direct sum of irreducible component codes of shorter length.
If a code is reducible, then the minimum distance of each irreducible component is at least as large as the minimum distance of the overall code.
Likewise, if the permutation group of a reducible code is transitive, then the permutation group of each irreducible component code must also be transitive.
Moreover, transitivity implies that the EXIT function of each bit must equal both the EXIT function of the overall code and the EXIT function of any irreducible component code.
Thus, the rate of the overall code and the rate of each irreducible component code must all be equal to the integral of their common EXIT function.
This implies that, if the overall code satisfies the necessary conditions of the conjecture, then each of its irreducible component codes must also satisfy the necessary conditions.
Thus, it is sufficient to resolve the conjecture for irreducible codes.

\subsection{Beyond the Erasure Channel}
\label{section:general_channels}

Our results for the erasure channel also have implications for the decoding of Reed-Muller codes over the binary symmetric channel.
In particular, \cite[Theorem~1.8]{Abbe-arxiv14} shows that an error pattern can be corrected by~$\mr{RM}(n-(2t+2),n)$ under  block-MAP decoding whenever an erasure pattern with the same support can be corrected by~$\mr{RM}(n-(t+1),n)$ under block-MAP decoding.
Using the algorithm in~\cite{Saptharishi-arxiv15*2}, these error patterns can even be corrected efficiently.
Combined with our results for the BEC, \cite[Corollary 14]{Saptharishi-arxiv15*2} shows that there exists a deterministic algorithm that runs in time at most $n^4$ and is able to correct $(1/2 - o(1))2^n$ random errors in $\mr{RM}(n,o(\sqrt{n}))$ with probability $1-o(1)$.

Another interesting open question is whether or not one can extend this approach to binary-input memoryless symmetric channels via generalized EXIT (GEXIT) functions~\cite{Measson-it09}.
For this, some new ideas will certainly be required because the straightforward approach leads to the analysis of functions that are neither boolean nor monotonic.

It would also be very interesting to find boolean functions outside of coding theory where area theorems can be used to pinpoint sharp thresholds.

\subsection{$\mbb{F}_q$-Linear Codes over the $q$-ary Erasure Channel}
\label{section:Fqlinear}

While our exposition focuses on binary linear codes over the BEC, it is easy to extend all results to $\mbb{F}_q$-linear codes over the $q$-ary erasure channel.

First, the set $\Omega_i$ is redefined to be the set of erasure patterns that prevent indirect recovery of the symbol $X_i$.
Importantly, $\Omega_i$ is still a set of binary sequences (equivalently, set of subsets of $[N] \backslash \{i\}$), and \emph{not} a set of sequences over the alphabet $\{0,1,\dots,q-1\}$.
Note that, if indirect recovery is not possible, then the linearity of the code implies that the posterior marginal of symbol $i$ given the extrinsic observations is $\Pr (X_i=x|\ul{Y}_{\sim i}=\ul{y}_{\sim i})=1/q$.
Next, we rescale the logarithm in the entropy $\ent{\cdot}$ to base $q$ so that $H(X_i | \ul{Y}_{\sim i}=\ul{y}_{\sim i})=1$ when indirect recovery of $X_i$ is not possible.

Thus, the sharp threshold framework for monotone boolean functions can be applied without change.
With these straightforward modifications, the results in Sections~\ref{section:preliminaries}~and~\ref{section:general} hold true verbatim.

The concept of affine-invariance also extends naturally to $\mbb{F}_q$-linear codes of length $q^m$ over the Galois field $\mbb{F}_q$.
Similarly, affine-invariance implies that the permutation group is doubly transitive.
Thus, sequences of affine-invariant $\mbb{F}_q$-linear codes of increasing length, whose rates converge to $r \in (0,1)$, achieve capacity over the $q$-ary erasure channel under symbol-MAP decoding.
The results for the block-MAP decoder also extend without change.
Thus, one finds that Generalized Reed-Muller codes~\cite{Delsarte-ic70} and extended primitive narrow-sense BCH codes over $\mbb{F}_q$ achieve capacity on the $q$-ary erasure channel under block-MAP decoding.
Moreover, quadratic-residue codes over $\mbb{F}_q$ described in Section~\ref{subsection:quadratic_residue} have an asymptotic rate equal to $1/2$, and they achieve capacity on the $q$-ary erasure channel under symbol-MAP decoding.

\subsection{Rates Converging to Zero}
\label{section:rates_to_zero}
Consider a sequence of Reed-Muller codes $\{\mr{RM}(v_n,n)\}$ where the rate $r_n \to 0$ sufficiently fast.
A key result of \cite{Abbe-arxiv14} is that Reed-Muller codes are capacity achieving in this scenario.
That is, for any $\delta>0$,
\begin{align*}
  P_B^{(n)}(p_n) \to 0 \quad \text{for any $0 \leq p_n < 1-(1+\delta) r_n$} .
\end{align*}
Looking closely at~\cite[Corollary 5.1]{Abbe-arxiv14}, it appears that $r_n = O(N_n^{-\kappa})$ for some $\kappa>0$ is a necessary condition for this result, where the blocklength $N_n=2^n$.

Now, let us analyze the bit erasure probability using our method.
From the proof of Theorem \ref{theorem:capacity_blockerror_wn}, it is possible to deduce that $P_b^{(n)}(p_{\epsilon_n}) \to 0$ if we choose $\epsilon_n = o(1)$ such that $\log(1/\epsilon_n) = o(\log(N_n))$.

We can also obtain a lower bound on $p_{\epsilon_n}$.
From \eqref{equation:pepsilon_lower_bound} in the proof of Proposition \ref{proposition:capacity_equivalence}, we gather that
\begin{align*}
  p_{\epsilon_n} &\geq 1 - \frac{r_n}{1-\epsilon_n} - \left( p_{1-\epsilon_n} - p_{\epsilon_n} \right) .
\end{align*}
From Theorem \ref{theorem:width_bound} and the proof of Theorem \ref{theorem:2transitive_capacity}, we have 
\begin{align*}
  p_{1-\epsilon_n} - p_{\epsilon_n} \leq \frac{2\log \frac{1}{\epsilon_n} }{\log (N_n-1)} ,
\end{align*}
which implies that
\begin{align*}
  p_{\epsilon_n} \geq 1 - \frac{r_n}{1-\epsilon_n} - \frac{2 \log \frac{1}{\epsilon_n} }{\log (N_n-1)} 
  = 1 - (1+\delta_n) r_n  ,
\end{align*}
where 
\begin{align*}
  \delta_n = \frac{\epsilon_n}{1-\epsilon_n} + \frac{2 \log \frac{1}{\epsilon_n} }{r_n \log (N_n-1)} .
\end{align*}
Therefore,
\begin{align*}
  P_b^{(n)}(p_n) \to 0 \quad \text{for any $0 \leq p_n < 1 -  (1+\delta_n) r_n$} ,
\end{align*}
for any $\epsilon_n=o(1)$ such that $\log(1/\epsilon_n) = o(\log(N_n))$.

In order to obtain a capacity achieving result under bit-MAP decoding, we require that $\delta_n \to 0$.
This can be guaranteed if $r_n \log(N_n) \to \infty$.
Under this condition, we can choose $\epsilon_n = 1/\log(r_n \log(N_n))$ so that
\begin{align*}
  \epsilon_n & \to 0, & \frac{\log\tfrac{1}{\epsilon_n}}{\log(N_n)} & \to 0, & \delta_n &\to 0 .
\end{align*}
Thus, under the condition $r_n \log(N_n) \to \infty$, the sequence $\mr{RM}(v_n,n)$ achieves capacity on the BEC under bit-MAP decoding.

For $r_n \to 0$, our results require $r_n \log(N_n) \to \infty$ while the results in~\cite[Corollary 5.1]{Abbe-arxiv14} require $r_n = O(N_n^{-\kappa})$ for some $\kappa>0$.
Thus, the results in the two papers apply to distinct asymptotic rate regimes that are non-overlapping.

\section{Conclusion}
\label{section:conclusion}
In this paper, we show that a sequence of binary linear codes achieves capacity if its blocklengths are strictly increasing, its code rates converge to some $r\in(0,1)$, and the permutation group of each code is doubly transitive. As a consequence, we prove that Reed-Muller codes and BCH codes achieve capacity on the BEC both under bit-MAP and block-MAP decoding, thus settling a long standing conjecture.
This result guarantees the existence of a capacity-achieving sequence of cyclic codes over the erasure channel.

To achieve this goal, we use isoperimetric inequalities for monotone boolean functions to exploit the symmetry of the codes.
This approach was successful largely because the transition point of the limiting EXIT function for the capacity-achieving codes is known a priori due to the area theorem.
One remarkable aspect of this method is its simplicity.
In particular, this approach does not rely on the precise structure of the code.

The main result extends naturally to $\mathbb{F}_q$-linear codes transmitted over a $q$-ary erasure channel under symbol-MAP decoding.
The class of affine-invariant $\mathbb{F}_q$-linear codes also achieves capacity, since their permutation group is doubly transitive.
Our results also show that Generalized Reed-Muller codes and extended primitive narrow-sense BCH codes achieve capacity on the $q$-ary erasure channel under block-MAP decoding.

\section*{Acknowledgments}
The authors's interest in this problem was piqued by its listing as an open problem during the 2015 Simons Institute program on Information Theory.
We gratefully acknowledge discussions with Hamed Hassani and Tom Richardson.

\appendices
\input{appendix}

\bibliographystyle{IEEEtran}


\subsection{Bit and Block Erasure Probability}
\label{subsection:errorprobability}
The input and output alphabets of the BEC are denoted by $\mathcal{X}=\{0,1\}$ and $\mathcal{Y} = \{0,1,*\}$, respectively. 
Let $\ul{X}=(X_1,\dots,X_N) \in \mathcal{X}^N$ be a uniform random codeword and  $\ul{Y}= (Y_1,\dots,Y_N)\in \mathcal{Y}^N$ be the received sequence obtained by transmitting $\ul{X}$ through a $\mr{BEC}(p)$.
Our main interest is the bit-MAP decoder.
But, we will also obtain some results for the block-MAP decoder indirectly based on our analysis of the bit-MAP decoder.

For linear codes and erasure channels, it is possible to recover the transmitted codeword if and only if the erasure pattern does not cover any codeword.
To see this, fix an erasure pattern and observe that adding a codeword to the input sequence causes the output sequence to change if and only if the erasure pattern does not cover the codeword.
Similarly, it is possible to recover bit $i$ if and only if the erasure pattern does not cover any codeword where bit $i$ is non-zero.
Whenever bit $i$ cannot be recovered uniquely, the symmetry of a linear code implies that set of codewords matching the unerased observations has an equal number of $0$'s and $1$'s in bit position $i$.
In this case, the posterior marginal of bit $i$ given the observations contains no information about bit $i$.

Let $D_i \colon \mathcal{Y}^N \to \mathcal{X} \cup \{*\}$ denote the bit-MAP decoder for bit $i$ of $\mc{C}$.
For a received sequence $\ul{Y}$, if $X_i$ can be recovered uniquely, then $D_i(\ul{Y})=X_i$.
Otherwise, $D_i$ declares an erasure and returns $*$.
Let the erasure probability for bit $i \in [N]$ be 
\begin{align*}
  P_{b,i} \triangleq \Pr(D_i(\ul{Y}) \neq X_i) ,
\end{align*}
and the average bit erasure probability be
\begin{align*}
  P_b \triangleq \frac{1}{N} \sum_{i=1}^N P_{b,i} .
\end{align*}

Whenever bit $i$ can be recovered from a received sequence $\ul{Y}=\ul{y}$, $H(X_i | \ul{Y}=\ul{y})=0$.
Otherwise, the uniform codeword assumption implies that the posterior marginal of bit $i$ given the observations is $\Pr (X_i=x|\ul{Y}=\ul{y})=\frac{1}{2}$ and $H(X_i | \ul{Y}=\ul{y})=1$.
This immediately implies that
\begin{align*}
  P_{b,i} &= \ent{X_i \mid \ul{Y}}, & P_b &= \frac{1}{N} \sum_{i=1}^N \ent{X_i \mid \ul{Y}} .
\end{align*}

Let $D \colon \mathcal{Y}^N \to \mathcal{X}^N \cup \{*\}$ denote the block-MAP decoder for $\mc{C}$.
Given a received sequence $\ul{Y}$, the vector $D(\ul{Y})$ is equal to $\ul{X}$ whenever it is possible to uniquely recover $\ul{X}$ from $\ul{Y}$.
Otherwise, $D$ declares an erasure and returns $*$.
Therefore, the block erasure probability is given by
\begin{align*}
  P_B \triangleq \Pr(D(\ul{Y}) \neq \ul{X}) .
\end{align*}

Using the set equivalence
\begin{align*}
  \{ D(\ul{Y}) \neq \ul{X} \} = \bigcup_{i \in [N]} \{ D_i(\ul{Y}) \neq X_i \},
\end{align*}
it is easy to see that
\begin{align}
  \label{equation:erasure_prob_relations}
  P_{b,i} &\leq P_B, & P_b &\leq P_B, & P_B &\leq N P_b .
\end{align}
Also, if $D$ declares an erasure, there will be at least $d_{\mathrm{min}}$ bits in erasure.
Therefore,
\begin{align*}
  d_{\mathrm{min}} \indicator{D(\ul{Y}) \neq \ul{X}} \leq \sum_{i \in [N]} \indicator{D_i(\ul{Y}) \neq X_i} .
\end{align*}
Taking expectations on both sides gives a tighter bound on $P_B$ in terms of $P_b$,
\begin{align}
  \label{equation:erasure_prob_dmin}
  P_B \leq \frac{N}{d_{\mathrm{min}}} P_b .
\end{align}

\subsection{MAP EXIT Functions}
\label{subsection:exit_functions}
Again, let $\ul{X}=(X_1,\dots,X_N)$ denote a uniformly selected codeword from $\mc{C}$ and $\ul{Y}$ be the sequence obtained from observing $\ul{X}$ with some positions erased.
In this case, however, we assume $X_i$ is transmitted over the $\mr{BEC}(p_i)$ channel.
We refer to this as the $\mr{BEC}(\ul{p})$ channel where $\ul{p}=(p_1,\ldots,p_N)$ is the vector of channel erasure probabilities.
While one typically evaluates all quantities of interest at $\ul{p}=(p,\dots,p)$, such a parametrization provides a convenient mathematical framework for many derivations.

The vector EXIT function associated with bit $i$ of $\mc{C}$ is defined by
\begin{align*}
  h_i(\ul{p}) \triangleq \ent{X_i | \ul{Y}_{ \sim i}(\ul{p}_{\sim i})} .
\end{align*}
Also, the average vector EXIT function is defined by
\begin{align*}
  h(\ul{p}) \triangleq \frac{1}{N} \sum_{i=1}^{N} h_{i}(\ul{p}) .
\end{align*}
Note that, while we define $h_i$ as a function of $\ul{p}$ for uniformity, it does not depend on $p_i$.
In terms of vector EXIT functions, the standard scalar EXIT functions $h(p)$ and $h_i(p)$ (for $i \in [N]$) are given by
\begin{align*}
  h_i(p) &\triangleq h_i(\ul{p}) \Big{\lvert}_{\ul{p}=(p,\dots,p)}, & h(p) &\triangleq h(\ul{p}) \Big{\lvert}_{\ul{p}=(p,\dots,p)} .
\end{align*}

The bit erasure probabilities and the EXIT functions $h(p)$ and $h_i(p)$ have a close relationship.
Observe that
\begin{align*}
  \ent{X_i \mid \ul{Y}} &= \Pr(Y_i=*) \ent{X_i | \ul{Y}_{\sim i},Y_i=* } \\
  &\qquad + \Pr(Y_i=X_i) \ent{X_i | \ul{Y}_{\sim i}, Y_i = X_i} \\
  &= \Pr(Y_i=*) \ent{X_i | \ul{Y}_{\sim i}} .
\end{align*}
Therefore,
\begin{align}
\label{equation:biterasure_exit_relation}
P_{b,i}(p) &= ph_i(p), & P_b(p) &= ph(p) .
\end{align}

We now state several well-known properties of these EXIT functions~\cite{Ashikhmin-it04,Measson-it08}, which play a crucial role in the subsequent analysis.
It is worth noting that the original definition of EXIT charts in \cite{Ashikhmin-it04} focused on mutual information $I(\ul{X};\ul{Y})$ while later work on EXIT functions focused on the conditional entropy $H(\ul{X}|\ul{Y})$~\cite{Measson-it08}.
In our setting, this difference results only in trivial remappings of all discussed quantities.
\begin{proposition}
\label{proposition:vector_exit_properties_1}
For a code $\mc{C}$ on the $\mr{BEC}(\ul{p})$ channel, the EXIT function associated with bit $i$ satisfies
\begin{align*}
  h_i(\ul{p}) = \pderi{H(\ul{X}|\ul{Y}(\ul{p}))}{p_i} .
\end{align*}
For a parametrized path $\ul{p}(t)=(p_1(t),\dots,p_n(t))$ defined for $t \in [0,1]$, where $p'_i(t)$ is continuous, one finds
\begin{align*}
  \ent{\ul{X} | \ul{Y}(\ul{p}(1))} \!-\! \ent{\ul{X} | \ul{Y}(\ul{p}(0))} \!=\!\! \int_0^1 \!\!\left( \!\sum_{i=1}^{N} h_i(\ul{p}(t)) p'_i(t) \!\right) \!\!\diff{t} .
\end{align*}
\end{proposition}
\begin{IEEEproof}
This result is implied by the results of both~\cite{Ashikhmin-it04} and~\cite{Measson-it08}.
For completeness, we repeat the proof from~\cite[Theorem 2]{Measson-it08} using our notation in Appendix~\ref{appendix:proof_vector_exit_properties_1}.
\end{IEEEproof}

The following sets characterize the EXIT functions $h_i$ and we will refer to them throughout the article.
\begin{definition}
\label{definition:Omega}
Consider a code $\mc{C}$ and the \emph{indirect recovery} of $X_i$ from the subvector $\ul{Y}_{\sim i}$ (i.e., the bit-MAP decoding of $X_i$ from $\ul{Y}$ when $Y_i = *$).
For $i \in [N]$, the set of erasure patterns that prevent indirect recovery of $X_i$ under bit-MAP decoding is given by
  \begin{align*}
    \Omega_{i} \triangleq \Big{\{} A \subseteq [N]\backslash\{i\} \,|\, \exists B \subseteq A, B \cup \{i\} \in \mc{C} \Big{\}}.
  \end{align*}  
For distinct $i,j \in [N]$, the set of erasure patterns where the $j$-th bit is \emph{pivotal} for the indirect recovery of $X_i$ is given by
  \begin{align*}
    \partial_j \Omega_i \triangleq \left\{ A \subseteq [N]\backslash \{i\} \mid A \backslash\{j\} \notin \Omega_i , A\cup\{j\} \in \Omega_i \right\}.
  \end{align*}
These are erasure patterns where $X_i$ can be recovered from $\ul{Y}_{\sim i}$ if and only if $Y_j \neq *$ (i.e., the $j$-th bit is not erased).
Note that $\partial_j \Omega_i$ includes patterns from both $\Omega_i$ and $\Omega_i^c$.

\end{definition}
Intuitively, $\Omega_i$ is the set of all erasure patterns that cover some codeword whose $i$-th bit is $1$.
For $j\in [N] \backslash i$, the set $\partial_j \Omega_i$ characterizes the boundary erasure patterns where flipping the erasure status of the $j$-th bit moves the pattern between $\Omega_i$ and $\Omega_i^c$.

\begin{proposition}
\label{proposition:vector_exit_properties_2}
For a code $\mc{C}$ on the $\mr{BEC}(\ul{p})$ channel, we have the following explicit expressions.
\begin{enumerate}[a)]
\item For bit $i$, the EXIT function is given by
  \begin{align*}
    h_{i}(\ul{p}) = \sum_{A \in \Omega_i} \prod_{\ell \in A} p_\ell \prod_{\ell \in A^c\backslash \{i\}} (1-p_\ell).
  \end{align*}
\item For distinct $i$ and $j$, the mixed partial derivative satisfies
  \begin{align*}
    \frac{\partial^2 H(\ul{X} | \ul{Y}(\ul{p}))}{\partial p_j \partial p_i} \!=\! \pderi{h_i(\ul{p})}{p_j} \!= \!\sum_{A \in \partial_j \Omega_i} \prod_{\ell \in A} p_\ell \!\!\prod_{\ell \in A^c\backslash \{i\}} (1-p_\ell).
  \end{align*}
\end{enumerate}
\end{proposition}
\begin{IEEEproof}
See Appendix~\ref{appendix:proof_vector_exit_properties_2}.
\end{IEEEproof}

The following proposition restates some known results in our notation.
The area theorem, stated below as c), first appeared in \cite[Theorem 1]{Ashikhmin-it04}, and the explicit evaluation of $h_i(p)$, stated below in a), is a restatement of \cite[Lemma 3.74(iv)]{RU-2008}.
\begin{proposition}
\label{proposition:scalar_exit_properties}
For a code $\mc{C}$ and transmission over a $\mr{BEC}$, we have the following properties for the EXIT functions.
\begin{enumerate}[a)]
\item The EXIT function associated with bit $i$ satisfies
  \begin{align*}
    h_{i}(p) = \sum_{A \in \Omega_{i}} p^{|A|}(1-p)^{N-1-|A|}.
  \end{align*}
\item For $j\in[N]\backslash \{i\}$, the partial derivative satisfies
  \begin{align*}
    \pderi{h_i(\ul{p})}{p_j} \Big{\lvert}_{\ul{p}=(p,\dots,p)} = \sum_{A \in \partial_j \Omega_i} p^{|A|} (1-p)^{N-1-|A|} .
  \end{align*}
\item The average EXIT function satisfies the \emph{area theorem}
  \begin{align*}
    \int_{0}^{1} h(p) \diff{p} = \frac{K}{N}.
  \end{align*}
\end{enumerate}
\end{proposition}
\begin{IEEEproof}
The first two parts follow directly from Proposition \ref{proposition:vector_exit_properties_2}.
For the third part, we use Proposition \ref{proposition:vector_exit_properties_1} with the path $\ul{p}(t)=(t,\dots,t)$.
This gives
\begin{align*}
  \ent{\ul{X} | \ul{Y}(\ul{1})} - \ent{\ul{X} | \ul{Y}(\ul{0})} = \int_0^1 \left( \sum_{i=1}^N h_i(t) \right) \diff{t} .
\end{align*}
Also, $\ent{\ul{X} | \ul{Y}(\ul{1})} = \ent{\ul{X}} = K$ and $\ent{\ul{X} | \ul{Y}(\ul{0})} = 0$.
Combining these observations gives the desired result.
\end{IEEEproof}

Since the code $\mc{C}$ is proper by assumption, $\Omega_i$ is non-empty and, in particular, $[N]\backslash \{i\} \in \Omega_i$.
Thus, $h_i$ is not a constant function equal to $0$ and $h_i (1)=1$.
Since the minimum distance of the code $\mc{C}$ is at least $2$ by assumption, $\Omega_i$ does not contain the empty set.
This implies that $h_i$ is not a constant function equal to $1$ and that $h_i(0)=0$.
As such, $h_i$ is a non-constant polynomial.
Also, $h_i$ is non-decreasing because Proposition \ref{proposition:scalar_exit_properties}(b) implies that $dh_i/dp \geq 0$.
It follows that $h_i$ is strictly increasing because a non-constant non-decreasing polynomial must be strictly increasing.

Consequently, the EXIT functions $h_i(p)$, and therefore $h(p)$, are continuous, strictly increasing polynomial functions on $[0,1]$ with $h(0)=h_i(0)=0$ and $h(1)=h_i(1)=1$.

The inverse function for the average EXIT function is therefore well-defined on $[0,1]$.
For $t \in [0,1]$, let
\begin{align}
  \label{equation:h_inverse}
  p_t \triangleq h^{-1}(t) = \inf \{ p \in [0,1] \mid h(p) \geq t \} ,
\end{align}
and note that $h(p_t)=t$.

\subsection{Permutations of Linear Codes}
\label{subsection:permutations}

Let $S_N$ be the symmetric group on $N$ elements.
The permutation group of a code is defined as the subgroup of $S_N$ whose group action on the bit ordering preserves the set of codewords~\cite[Section 1.6]{Huffman-2003}.

\begin{definition}
The permutation group $\mc{G}$ of a code $\mc{C}$ is defined to be
\begin{align*}
  \mc{G} = \left\{ \pi \in S_N \mid \text{$\pi(A) \in \mc{C}$ for all $A \in \mc{C}$} \right\} .
\end{align*}
\end{definition}

\begin{definition}
Suppose $\mc{G}$ is a permutation group. Then, 
\begin{enumerate}[a)]
\item  $\mc{G}$ is \emph{transitive} if, for any $i,j \in [N]$, there exists a permutation $\pi \in \mc{G}$ such that $\pi(i) = j$, and
\item $\mc{G}$ is \emph{doubly transitive} if, for any distinct $i,j,k \in [N]$, there exists a $\pi \in \mc{G}$ such that $\pi(i) = i$ and $\pi(j)=k$. 
\end{enumerate}
\end{definition}

Note that any non-trivial code (i.e., $0<r<1$) whose permutation group is transitive must be proper and have minimum distance at least two.

In the following, we explore some interesting symmetries of EXIT functions when the permutation group of the code is transitive or doubly transitive.

\begin{proposition}
\label{proposition:transitive_exit}
Suppose the permutation group $\mc{G}$ of a code $\mc{C}$ is transitive.
Then, for any $i \in [N]$,
\begin{align*}
  h(p) = h_i(p) \qquad \text{for $0\leq p \leq 1$} .
\end{align*}
\end{proposition}
\begin{IEEEproof}
Since $\mc{G}$ is transitive, for any $i,j \in [N]$, there exists a permutation $\pi$ such that $\pi(i)=j$.
Using this, one can show that there is a bijection between $\Omega_i$ and $\Omega_j$ induced by the action of $\pi$ on the codeword indices.
To do this, we first show that $A \in \Omega_i$ implies $\pi(A) \in \Omega_j$.

Since $A \in \Omega_i$, by definition, there exists $B \subseteq A$ such that $B \cup \{ i \} \in \mc{C}$.
Since $\pi \in \mc{G}$, $\pi(B \cup \{i\}) \in \mc{C}$.
Also, $\pi(B \cup \{i\}) = \pi(B) \cup \{j\}$ and $\pi(B) \subseteq \pi(A)$.
Consequently, $\pi(A) \in \Omega_j$.

Similarly, if $A \in \Omega_j$, then $\pi^{-1}(A) \in \Omega_i$.
Thus, there is a bijection between $\Omega_i$ and $\Omega_j$ induced by $\pi$.
This bijection also preserves the weight of the vectors in each set (i.e., $|A|=|\pi(A)|$).

Since Proposition \ref{proposition:scalar_exit_properties}(a) implies that $h_i(p)$ only depends on the weights of elements in $\Omega_i$, it follows that $h_i(p)=h_j(p)$.
This also implies that $h(p)=h_i(p)$ for all $0 \leq p \leq 1$.
\end{IEEEproof}

\begin{proposition}
\label{proposition:2transitive_exit_deri}
Suppose that the permutation group $\mc{G}$ of a code $\mc{C}$ is doubly transitive.
Then, for distinct $i,j,k \in [N]$, and any $0 \leq p \leq 1$,
\begin{align*}
  \pderi{h_i(\ul{p})}{p_j} \Big{\lvert}_{\ul{p}=(p,\dots,p)} = \pderi{h_i(\ul{p})}{p_k} \Big{\lvert}_{\ul{p}=(p,\dots,p)} .
\end{align*}
\end{proposition}
\begin{IEEEproof}
Since $\mc{G}$ is doubly transitive, there exists a permutation $\pi \in \mc{G}$ such that $\pi(i)=i$ and $\pi(j)=k$.
Suppose $A \in \partial_j \Omega_i$.
Then, by definition, either 1) $A \in \Omega_i$ and $A \backslash \{j\} \notin \Omega_i$ or 2) $A \cup \{j\} \in \Omega_i$ and $A \notin \Omega_i$.
In either case, we claim that $\pi(A) \in \partial_k \Omega_i$.
We prove this for the first case.
The proof for the second case can be obtained verbatim by replacing $A$ with $A \cup \{j\}$.

Suppose $A \in \Omega_i$ and $A \backslash \{j\} \notin \Omega_i$.
Since $\pi \in \mc{G}$ and $\pi(i)=i$, $\pi(A) \in \Omega_i$.
Also, $\pi(A \backslash \{j\}) \notin \Omega_i$; otherwise, $A \backslash\{j\}=\pi^{-1}(\pi(A \backslash \{ j \})) \in \Omega_i$ gives a contradiction.
Finally, $\pi(A \backslash \{j\}) = \pi(A) \backslash \{k\}$ implies that $\pi(A) \in \partial_k \Omega_i$.
Similarly, one finds that $A \in \partial_k \Omega_i$ implies $\pi^{-1}(A) \in \partial_j \Omega_i$.

Since Proposition \ref{proposition:scalar_exit_properties}(b) implies that $\tfrac{\partial h_i}{\partial p_j}|_{\ul{p}=(p,\dots,p)}$ only depends on the weights of elements in $\partial_j \Omega_i$ and $|A| = |\pi(A)|$, we obtain the desired result.
\end{IEEEproof}

\begin{remark}
  Codes with doubly-transitive permutation groups have many structural properties.
For example, it is worth noting that binary codes with doubly-transitive permutation groups also satisfy the distance inequality $(d_{\mathrm{min}} -1)(d_{\mathrm{min}}^{\perp} -1) \geq N-1$~\cite[Appendix E]{Vontobel-2003}, where $d_{\mathrm{min}}^{\perp}$ is the minimum distance of the dual code.
\end{remark}

\subsection{Capacity-Achieving Codes}
\label{subsection:capacity}
\begin{figure}[!t]
  \centering
  \setlength\tikzheight{5.5cm}
  \setlength\tikzwidth{7cm}
  \input{./Figures/reed_muller_exit_simulation}
  \caption{The average EXIT function of the rate-$1/2$ Reed-Muller code with blocklength $N$.}
  \label{figure:reed_muller_exit_simulation}
\end{figure}
\begin{definition}
Suppose $\{ \mc{C}_n \}$ is a sequence of codes with rates $\{r_n\}$ where $r_n \to r$ for $r\in (0,1)$.
\begin{enumerate}[a)]
\item $\{ \mc{C}_n \}$ is said to be capacity achieving on the BEC under bit-MAP decoding, if for any $p \in [0,1-r)$, the average bit-erasure probabilities satisfy
  \begin{align*}
    \lim_{n \to \infty} P_b^{(n)}(p) = 0 .
  \end{align*}
\item $\{ \mc{C}_n \}$ is said to be capacity achieving on the BEC under block-MAP decoding, if for any $p \in [0,1-r)$, the block-erasure probabilities satisfy
  \begin{align*}
    \lim_{n \to \infty} P_B^{(n)}(p) = 0 .
  \end{align*}
\end{enumerate}
\end{definition}

The following proposition encapsulates the approach we use to show that a sequence of codes achieves capacity.
It naturally bridges capacity-achieving codes, average EXIT functions, and the sharp transition framework presented in the next section, which allows one to show that the transition width\footnote{Defined as the width over which the function transitions from $\epsilon$ to $1-\epsilon$.} of certain functions converges to $0$.
The average EXIT functions of some rate-$1/2$ Reed-Muller codes are shown in Figure~\ref{figure:reed_muller_exit_simulation}.
Observe that as the blocklength increases, the transition width of the average EXIT function decreases.
According to the following proposition, if this width converges to $0$, then Reed-Muller codes achieve capacity on the BEC under bit-MAP decoding. 

\begin{proposition}
\label{proposition:capacity_equivalence}
Let $\{\mc{C}_n\}$ be a sequence of codes with rates $\{r_n\}$ where $r_n \to r$ for $r\in (0,1)$.
Then, the following statements are equivalent.
\begin{enumerate}[S1:]
\item $\{ \mc{C}_n \}$ is capacity achieving on the BEC under bit-MAP decoding.
\item The sequence of average EXIT functions satisfies
  \begin{align*}
    \lim_{n \to \infty} h^{(n)} (p) =
    \begin{cases}
      0 & \text{if $0 \leq p<1-r$}, \\
      1 & \text{if $1-r<p \leq 1$}. 
    \end{cases}
  \end{align*}
\item For any $0< \epsilon \leq 1/2$,
  \begin{align*}
    \lim_{n \to \infty} \left( p_{1-\epsilon}^{(n)} - p_{\epsilon}^{(n)} \right) = 0 ,
  \end{align*}
  where $p_t^{(n)}$ is the functional inverse of $h^{(n)}$ given by \eqref{equation:h_inverse}.
\end{enumerate}
\end{proposition}
\begin{IEEEproof}
See Appendix \ref{appendix:proof_capacity_equivalence}.
\end{IEEEproof}

In a nutshell, the equivalence between the first two statements is due to the close relationship between the bit erasure probability and the average EXIT function in \eqref{equation:biterasure_exit_relation}, while the equivalence between the last two statements is a consequence of the area theorem in Proposition \ref{proposition:scalar_exit_properties}(c).

While the above result appears deceptively simple, our approach is successful largely because the transition point of the limiting EXIT function is known a priori due to the area theorem.
Even though the sharp transition framework presented in the next section is widely applicable in theoretical computer science and allows one to deduce that the transition width of certain functions goes to $0$, establishing the existence of a threshold and determining its precise location if it exists can be notoriously difficult\footnote{Existence of a threshold means for some $0 < a < 1$, $p_{\epsilon}^{(n)} \to a$ for all $\epsilon>0$. Note that this implies that the transition width $p_{1-\epsilon}^{(n)}-p_{\epsilon}^{(n)} \to 0$ and not vice versa.}~\cite{Achlioptas-nature05,Coja-Oghlan-stoc14,Ding-arxiv14}.

\begin{remark}
For erasure channels, the bit-error performance of a code and of its dual code are closely related.
According to \cite[Theorem 3.76]{RU-2008}, $h^{\perp}(p) = 1-h(1-p)$, where $h$ and $h^{\perp}$ are the average EXIT functions of a given code and of its dual, respectively.
Moreover, for a code of rate $r$, its dual code has rate $1-r$.
From statement S2 of Proposition \ref{proposition:capacity_equivalence}, it is immediate that a sequence of codes achieves capacity on the BEC under bit-MAP decoding if and only if the sequence of their dual codes achieves capacity on the BEC under bit-MAP decoding.
\end{remark}

Our main result depends crucially on the double transitivity of permutation groups of certain codes.
We note that the transitivity of a permutation group is sensitive to codebook operations such as addition or deletion of a few bits.
However, according to the following result, these operations do not affect the capacity achievability.

\begin{proposition}
\label{proposition:code_modification}
Suppose $\{\mc{C}_n\}$ is a sequence of codes with rates $r_n \to r$ for some $r \in (0,1)$ and blocklengths $N_n \to \infty$.
Let $\hat{\mc{C}}_n$ be a code obtained by puncturing $\ell_n$ bits from $\mc{C}_n$, where $\ell_n/N_n \to 0$. 
Then, under bit-MAP decoding on the BEC, $\{\mc{C}_n\}$ is capacity achieving if and only if $\{\hat{\mc{C}}_n\}$ is capacity achieving.
\end{proposition}
\begin{IEEEproof}
See Appendix \ref{appendix:proof_code_modification}.
\end{IEEEproof}


