Polynomial Freiman-Ruzsa, Reed-Muller codes and Shannon capacity

1. Problem Statement

The paper addresses a fundamental open problem in coding theory: Do Reed-Muller (RM) codes achieve the Shannon capacity of the Binary Symmetric Channel (BSC)?

• Context: Shannon's 1948 theorem proved the existence of codes achieving capacity using random coding arguments. However, explicit deterministic constructions (like RM codes) have been difficult to prove achieve capacity, particularly regarding block-error probability (decoding the entire message correctly).
• The Gap: While Polar codes were proven to achieve capacity via "polarization theory," RM codes were only partially understood. Previous work established that RM codes achieve capacity in the weak sense (vanishing bit-error probability) but lacked a proof for the strong sense (vanishing block-error probability) with efficient decoding.
• Specific Goal: The authors aim to establish a rigorous polarization theory for RM codes to prove that they achieve capacity in the weak sense (vanishing bit-error) with an improved error exponent, and to lay the groundwork for strong capacity results.

2. Methodology

The authors develop a novel proof framework that bridges Information Theory (entropy, polarization) and Additive Combinatorics (Polynomial Freiman-Ruzsa conjecture).

A. Entropy Extraction and Polarization

The core idea is to analyze the conditional entropy of the message layers of the RM code.

• Layered Structure: RM codes are constructed based on polynomials of increasing degree. The message $U$ is decomposed into layers $U_{\leq r}$ (polynomials of degree $\leq r$) and $U_{> r}$.
• Conditional Entropy: The authors study $H(U_{\leq r} \mid Y, U_{> r})$, where $Y$ is the noisy received word. This measures the uncertainty of the lower-degree coefficients given the higher-degree coefficients (which are "frozen" to 0 in the code construction) and the channel output.
• Polarization Phenomenon: They aim to show that as the code length $n=2^m$ grows, these conditional entropies "polarize" to either 0 (perfectly recoverable) or 1 (completely random), similar to Polar codes.

B. The Additive Combinatorics Connection

The proof relies heavily on the recently proven Polynomial Freiman-Ruzsa (PFR) Conjecture (by Gowers, Green, Manners, and Tao [40]).

• Ruzsa Distance: The authors utilize the Ruzsa distance $d(X, Y)$, which measures how close the sum of two independent random variables is to the individual variables in terms of entropy.
• The Link: They show that if the conditional entropy of the sum of two independent noise vectors (related to the RM structure) is close to the individual entropy, the distribution must be close to a uniform distribution on a subspace.
• Orbit Localization Lemma: A key technical contribution is a new lemma (Lemma 3.2) stating that if a probability distribution over subspaces is invariant under a group of linear transformations (specifically affine transformations relevant to RM codes), the distribution must concentrate on a specific invariant subspace.
  • For RM codes, the only subspaces invariant under all affine transformations are the trivial subspace $\{0\}$ and the entire space.
  • This forces the conditional entropy to polarize to the extremes (0 or the dimension of the layer).

C. Recursive Structure

The proof exploits the recursive construction of RM codes (Plotkin construction):
$$RM(m, r) \leftrightarrow (RM(m-1, r), RM(m-1, r-1))$$
This allows the authors to derive a recurrence relation for the layer entropies, linking the entropy at dimension $m$ to dimension $m-1$.

3. Key Contributions

1. Establishment of Polarization for RM Codes:
   The paper provides the first proof of a layer polarization inequality for Reed-Muller codes. It demonstrates that the conditional entropies of the code layers satisfy a recurrence that forces them to converge to 0 or their maximum possible value.

2. Connection to PFR Conjecture:
   The authors explicitly link the capacity-achieving property of RM codes to the Polynomial Freiman-Ruzsa theorem. They show that the "entropy extraction" mechanism in RM codes is a direct consequence of the structural rigidity of sets with small doubling in additive combinatorics.

3. Small Orbit Localization Lemma:
   A new lemma in additive combinatorics is introduced. It states that for a distribution over subspaces invariant under a group of linear transformations, the expected distance to a fixed invariant subspace is bounded by the expected distance between two independent samples. This lemma is of independent interest for combinatorial number theory.

4. Improved Error Bounds:
   The paper proves that RM codes achieve capacity in the weak sense (vanishing bit-error probability) with an error exponent of $2^{-\Omega(\sqrt{m})}$ (where $n=2^m$). This is a significant improvement over previous results (e.g., [56]) which had much slower convergence rates (e.g., $O(\log \log n / \sqrt{\log n})$).

4. Main Results

• Theorem 3.1 (Layer Polarization Inequality):
  For a BSC with error $\delta$, if the code rate is below capacity ($R < 1-H(\delta)$), the layer entropies satisfy a recurrence inequality:
  $$a_{m+1, r+1} \leq a_{m, r+1} + a_{m, r} - \frac{1}{140} \min\left(f_{m,r}, \binom{m}{r} - f_{m,r}\right)$$
  where $a_{m,r}$ is the conditional entropy and $f_{m,r}$ is the difference between layers. This inequality drives the polarization.

• Theorem 3.1 (Weak Capacity):
  The bit-error probability $P_{bit}$ for the sequence of RM codes $\{RM(m, r_m)\}$ satisfies:
  $$P_{bit} = 2^{-\Omega(\sqrt{m})}$$
  This confirms that RM codes achieve the Shannon capacity in the weak sense (reliable communication with vanishing bit errors).

• New Conjecture (Section 7):
  The authors propose a new additive combinatorics conjecture (Conjecture 7.1) that, if proven, would tighten the constants in the PFR application. This would potentially improve the error exponent to $2^{-\Omega(\sqrt{m} \log m)}$, which is sufficient to prove strong capacity (vanishing block-error probability) using existing bit-to-block conversion techniques.

5. Significance

• Resolution of a Decades-Old Conjecture: The paper provides a definitive proof that Reed-Muller codes, one of the oldest and most studied families of codes, achieve the Shannon capacity of the BSC (in the bit-error sense).
• Bridging Fields: It creates a profound connection between coding theory and additive combinatorics. The proof strategy suggests that deep structural results in combinatorics (like PFR) are essential for understanding the performance limits of algebraic codes.
• New Tools: The "Small Orbit Localization Lemma" and the specific application of the PFR theorem to entropy extraction provide new tools for analyzing other recursive code structures and symmetric channels.
• Path to Strong Capacity: While the current result is for bit-error, the framework and the proposed conjecture offer a clear roadmap to proving that RM codes also achieve strong capacity (block-error), which would make them theoretically competitive with Polar codes for practical applications.

In summary, this paper settles the capacity question for Reed-Muller codes by leveraging the recent breakthrough in the Polynomial Freiman-Ruzsa conjecture, proving that these codes effectively "polarize" their entropy to achieve the theoretical limits of communication.