Algebraic Expander Codes

1. Problem Statement

The paper addresses a fundamental limitation in the design of Expander (Tanner) Codes.

• The Rate Barrier: Standard expander codes are constructed by placing local constraints (codes of rate $r$) on the edges of a sparse expander graph. A standard constraint-counting argument yields a lower bound on the global code rate $R \ge 2r - 1$.
• The Low-Rate Regime: This bound implies that to guarantee a positive global rate ($R > 0$), the local code rate must satisfy $r > 1/2$. If $r \le 1/2$, the bound becomes non-positive, offering no guarantee of a positive-rate code.
• The Motivation: The regime $r \le 1/2$ is critical for applications requiring specific algebraic structures, most notably the multiplication property (Schur product) of Reed–Solomon (RS) codes. In quantum error correction (e.g., transversal non-Clifford gates) and High-Dimensional Expanders (HDX), local constraints often need to be low-rate RS codes so that the product of two codewords remains in a structured code space.
• The Challenge: Constructing explicit expander codes that maintain low-rate RS local constraints ($r \le 1/2$) while achieving a positive, constant global rate and linear distance.

2. Methodology

The authors propose a purely algebraic construction, termed Algebraic Expander Codes, which departs from the standard "graph + local code" paradigm.

A. Algebraic Framework

Instead of choosing a graph and local codes independently, the code is defined as an orbit-evaluation code:

1. Group Action: The code is defined over a finite field $\mathbb{F}$ using the affine group $AGL(1, \mathbb{F})$.
2. Non-Commutative Subgroups: The construction utilizes two subgroups of opposing algebraic types:
   • $G$: An additive subgroup (translations: $x \mapsto x + g$).
   • $H$: A multiplicative subgroup (scalings: $x \mapsto hx$).
   • Crucially, $G$ and $H$ do not commute. This non-commutativity generates a group $A = \langle G, H \rangle$ that is significantly larger than the product $|G| \cdot |H|$, leading to a sparse underlying geometry.
3. Evaluation Domain: The code coordinates correspond to an orbit $\Omega$ of a point $\alpha$ under the action of $A$. The block length is $n = |A|$.
4. Message Space: The code consists of evaluations of polynomials $f(X)$ that satisfy specific degree constraints relative to the invariant polynomials of $G$ and $H$.

B. Key Technical Innovations

• $u$-Base Degree: To prove the code has positive rate even when $r \le 1/2$, the authors introduce a new notion of polynomial degree. A polynomial $f(X)$ is expanded in a "base" $u(X)$ (where $u$ is the invariant polynomial of a subgroup). The $u$-base degree is the maximum degree of the coefficients in this expansion.
  • The message space is defined by polynomials with small $g$-base degree and small $h$-base degree.
  • The authors prove the sub-additivity of this degree measure, allowing them to translate local constraints into linear constraints on the coefficients.
• Rate Analysis via Polytope Volume: The dimension of the message space is lower-bounded by approximating the volume of a high-dimensional polytope defined by the degree constraints. This avoids the failure of standard dimension-counting arguments in the low-rate regime.
• Spectral Expansion via Character Sums: The expansion of the underlying bipartite graph (the coset graph of $G$ and $H$) is proven by analyzing the second largest singular value of its adjacency operator. This is achieved by bounding additive character sums over the multiplicative subgroup $H$ (using Gauss sums and orthogonality relations).

3. Key Contributions

1. Breaking the $2r-1$ Barrier: The paper provides the first explicit construction of expander codes that achieve a positive global rate for any fixed local rate $r \in (0, 1)$, including the challenging regime $r \le 1/2$.
2. Reed–Solomon Locality: The local constraints are explicitly Reed–Solomon codes. This ensures the code inherits the multiplication property, making it suitable for quantum LDPC codes and HDX applications.
3. Sparse Coset Geometry: By using non-commuting subgroups (translations and scalings), the construction yields a sparse bipartite graph (degrees are polynomial in $n$, specifically $O(n^{1/(m+1)})$), in contrast to previous algebraic constructions using commuting subgroups which resulted in dense, grid-like graphs with linear degrees.
4. Two Explicit Instantiations:
   • Instantiation I: Uses $H = \mathbb{F}_{p^m}^\times$ (full multiplicative group). Yields balanced degrees and relies on additive character orthogonality.
   • Instantiation II: Uses a subgroup $H \le \mathbb{F}_{p^{m+1}}^\times$ of constant index. Allows tuning of the degree via a parameter $\gamma$ and relies on Gauss sum bounds.

4. Main Results

For any fixed local rate $r \in (0, 1)$ and sparsity parameter $m \ge 2$, the authors construct a family of codes with block length $n$ (where $n \to \infty$ as the field characteristic $p \to \infty$) satisfying:

• Local Constraints: Every coordinate participates in two local RS constraints of rate $r + o(1)$.
• Global Rate: The global rate $R$ is bounded below by an explicit positive constant depending on $r$ and $m$.
  • Specifically, for $D=n$, $R \ge \frac{r^{2m+1}}{(2m+1)!}$ (Instantiation I).
  • This bound remains positive even when $r \le 1/2$.
• Global Distance: The relative distance satisfies $\delta \ge (1-r)^2 - o(1)$.
• Spectral Expansion: The underlying bipartite graph is a strong spectral expander with normalized second singular value $\sigma_2 \le O(1/\sqrt{p})$.

5. Significance and Implications

• Theoretical Breakthrough: The work resolves the tension between local algebraic structure and global expansion in the low-rate regime, a problem that standard combinatorial expander code theory could not solve.
• Practical Applications:
  • Quantum Computing: Enables the construction of Quantum LDPC codes with transversal non-Clifford gates, which require local codes with $r < 1/2$ and the multiplication property.
  • High-Dimensional Expanders: Provides a new algebraic method for constructing HDXs with multiplicative structure, relevant for property testing and derandomization.
• Limitations & Open Problems:
  • The alphabet size grows polynomially with the block length (not constant).
  • The graph degree is polynomial in $n$ (though sublinear), not constant.
  • The derived rate bound is likely not tight (it vanishes factorially as $m$ increases, whereas the standard bound $2r-1$ is constant for $r > 1/2$).

In summary, Kopparty and Tamo introduce a novel algebraic framework that leverages non-commutative group actions to construct expander codes with low-rate Reed–Solomon local constraints, successfully achieving positive global rates where previous methods failed. This opens new avenues for algebraic coding theory in quantum and high-dimensional settings.