Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields
Abstract
Recent work shows that ordinary Reed--Solomon codes over prime fields admit polynomial-size lists up to list-decoding capacity on every evaluation set. We show a contrasting phenomenon over binary extension fields. For every fixed rate 0<R<1, there exists εR>0 such that, for all sufficiently large h, the full-field Reed--Solomon code over 𝔽2h has a received word with nΩR(log n) codewords within relative distance 1−R−εR. To our knowledge, these are the first superpolynomial ordinary Reed--Solomon list-size lower bounds at fixed positive rate and a fixed positive agreement gap above the rate. Thus capacity-approaching polynomial list size for Reed--Solomon codes is not uniform over the underlying field, and the obstruction occurs at every fixed rate. As a puncturing consequence, the same holds for primitive Reed--Solomon codes; the obstruction is also robust under controlled dense puncturing. The proof begins with an exact correspondence that turns certain binary Bose--Chaudhuri--Hocquenghem weight-enumerator coefficients into sizes of single Reed--Solomon lists. A classical binary weight family gives the initial quarter-rate construction, while a quadratic-form enumeration supplies its superpolynomial multiplicity. A common-kernel quotient/descent argument and common-root padding then extend the construction to all rates. We also determine the optimized agreement envelope achieved by the construction.
Related
- Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound
- Sharp L2 → L4 extension inequality for quadratic surfaces in finite fields
- Sharp endpoint extension inequalities for the moment curve on finite fields II: an extremal property of the uniform distribution
- p-class groups in the cyclotomic ℤp-extension of imaginary quadratic fields
- Sharp spherical Lp→ L4 extension estimates over finite fields in odd dimensions
BibTeX
@misc{zhu2026superpolynomial,
title = {{Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields}},
author = {Minshen Zhu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15815},
eprint = {2610.15815},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15815},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields
AU - Minshen Zhu
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15815
UR - https://arxiv.org/abs/2610.15815
AB - Recent work shows that ordinary Reed--Solomon codes over prime fields admit polynomial-size lists up to list-decoding capacity on every evaluation set. We show a contrasting phenomenon over binary extension fields. For every fixed rate 0<R<1, there exists ε_R>0 such that, for all sufficiently large h, the full-field Reed--Solomon code over 𝔽_2^h has a received word with n^Ω_R(log n) codewords within relative distance 1−R−ε_R. To our knowledge, these are the first superpolynomial ordinary Reed--Solomon list-size lower bounds at fixed positive rate and a fixed positive agreement gap above the rate. Thus capacity-approaching polynomial list size for Reed--Solomon codes is not uniform over the underlying field, and the obstruction occurs at every fixed rate. As a puncturing consequence, the same holds for primitive Reed--Solomon codes; the obstruction is also robust under controlled dense puncturing. The proof begins with an exact correspondence that turns certain binary Bose--Chaudhuri--Hocquenghem weight-enumerator coefficients into sizes of single Reed--Solomon lists. A classical binary weight family gives the initial quarter-rate construction, while a quadratic-form enumeration supplies its superpolynomial multiplicity. A common-kernel quotient/descent argument and common-root padding then extend the construction to all rates. We also determine the optimized agreement envelope achieved by the construction.
ER -