Algebraic Expander Codes

arXiv:2603.24788v1 Announce Type: new
Abstract: Expander (Tanner) codes combine sparse graphs with local constraints, enabling linear-time decoding and asymptotically good distance–rate tradeoffs. A standard constraint-counting argument yields the global-rate lower bound $Rge 2r-1$ for a Tanner code with local rate $r$, which gives no positive-rate guarantee in the low-rate regime $rle 1/2$. This regime is nonetheless important in applications that require algebraic local constraints (e.g., Reed–Solomon locality and the Schur-product/multiplication property).
We introduce emph{Algebraic Expander Codes}, an explicit algebraic family of Tanner-type codes whose local constraints are Reed–Solomon and whose global rate remains bounded away from $0$ for every fixed $rin(0,1)$ (in particular, for $rle 1/2$), while achieving constant relative distance.
Our codes are defined by evaluating a structured subspace of polynomials on an orbit of a non-commutative subgroup of $mathrm{AGL}(1,mathbb{F})$ generated by translations and scalings. The resulting sparse coset geometry forms a strong spectral expander, proved via additive character-sum estimates, while the rate analysis uses a new notion of polynomial degree and a polytope-volume/dimension-counting argument.