Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

Abstract

Reed-Muller (RM) codes are a cornerstone of algebraic coding theory, yet their average-case performance has long remained a subject of conjecture. This paper provides a theoretical breakthrough by analyzing the "vanishing space" of random sets in high-dimensional binary spaces. The authors prove that for random sets of points, the space of polynomials that vanish on them has the minimum possible dimension with high probability. This result is used to show that high-degree Reed-Muller codes achieve Shannon capacity under the Binary Erasure Channel (BEC) and can be efficiently decoded from random errors, even when the error rate exceeds the code's design distance.

Introduction

Reed-Muller codes, defined by the evaluation of low-degree polynomials over the finite field $\mathbb{F}_2^m$, are among the oldest and most studied error-correcting codes. While their "worst-case" performance—such as minimum distance—is well-understood, their "average-case" performance has been a major open mystery in information theory. Specifically, the question of whether RM codes achieve Shannon capacity (the theoretical limit of communication) has persisted for decades.

A central challenge in resolving this mystery is understanding the vanishing space: given a set of $k$ points, what is the dimension of the space of polynomials that evaluate to zero on all those points? Previous bounds, such as those established by Wei in 1991, suggested that these spaces could be quite large if the points were arranged in specific structures, like subcubes. This paper shifts the focus from structured sets to random sets, asking: how do polynomials behave on points chosen uniformly at random?

Analytical Approach

The authors bridge the gap between algebraic geometry and coding theory through a multi-step probabilistic analysis:

  1. Linear Algebra Reformulation: The problem of the "vanishing space" is translated into a question about the rank of sub-matrices of the RM parity-check matrix. If the columns corresponding to a set of points are linearly independent, the vanishing space necessarily has the minimum possible dimension.
  2. Probabilistic Method: Rather than identifying specific "good" sets, the authors analyze the expected size of the vanishing space over a uniformly random choice of $k$ points.
  3. Weight Distribution Analysis: The core of the proof relies on technical lemmas regarding the "weight" of polynomials—the fraction of points where a polynomial is non-zero. The authors build upon recent breakthroughs by Sberlo and Shpilka (2020), which provided tight bounds on these distributions for low-degree polynomials. By showing that very few polynomials have low weight, they prove that a random set of points is unlikely to be contained within the zero-set of any unexpected polynomial.
  4. Channel Reduction: By establishing that random sets of points lead to linearly independent columns in the parity-check matrix, the authors directly link their algebraic results to the code's ability to recover from erasures (Binary Erasure Channel) and errors (Binary Symmetric Channel).

Theoretical Contributions

The "Full Rank" Phenomenon

The paper's primary insight is that random sets are significantly "better" than structured sets. While a subcube of points allows many polynomials to vanish on it (thereby reducing the rank of the parity-check matrix), a random set of the same size is almost certain to be linearly independent.

Theorem 1.1 states that for a random set $Z$ of $k$ points, where $k$ is slightly less than the total number of available monomials, the dimension of the vanishing space is exactly $\binom{m}{\le r} - k$ with probability $1 - o(1)$. This confirms that there is no "hidden" algebraic structure in a random set that polynomials can exploit.

Capacity Achievement and Resilience

This algebraic result provides the missing link to prove that high-degree RM codes (where the degree $d$ is close to the number of variables $m$) achieve Shannon capacity.

  • Erasure Resilience: High-degree RM codes (where $d > (1-\gamma)m$) can correct a number of random erasures that approaches the theoretical limit defined by the number of parity checks.
  • Error Correction: These codes are shown to be efficiently decodable from random errors even when the number of errors far exceeds the code's minimum distance—a property known as "decoding beyond the design distance."

Discussion and Future Work

While this work represents a significant leap forward, several challenges remain. The current results hold for degrees $r \le \gamma m$, where $\gamma$ is a small absolute constant. Extending these proofs to the "constant rate" regime (where $r \approx m/2$) remains a major open challenge in the field. Additionally, while the paper covers high-degree and low-degree regimes effectively, the "middle ground" of Reed-Muller parameters is not yet fully understood regarding capacity.

Finally, the authors note that their proof methodology is generalizable. Any linear code for which the weight distribution of the dual code is known could potentially be analyzed using these techniques. Applying this framework to other families of codes, such as Polar codes or BCH codes, represents a promising direction for future research in information theory.

Summary updated

BibTeX
@inproceedings{bhandari2022vanishing,
  author = {Siddharth Bhandari and Prahladh Harsha and Ramprasad Saptharishi and Srikanth Srinivasan},
  title = {{Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes}},
  booktitle = {CCC},
  year = {2022},
  doi = {10.4230/lipics.ccc.2022.31},
}
Figure