Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields

Minshen Zhu

Oct 11, 2026arXiv:2610.15815v1

cs.ITcs.CC

Scorecard· 15/16

8.0/10 impact

Resolves a well-posed open question about canonical RS codes over binary fields with a clean all-rate superpolynomial lower bound, directly relevant to proximity-gap debates, though limited to characteristic two and below-Johnson agreement.

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 $\varepsilon_R>0$ such that, for all sufficiently large $h$ , the full-field Reed--Solomon code over $\mathbb{F}_{2^h}$ has a received word with $n^{Ω_R(\log n)}$ codewords within relative distance $1-R-\varepsilon_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.

AI Impact Assessments

(1 model)

Core Contribution

The paper settles a basic open question about Reed–Solomon (RS) list decoding. Recent work showed that over prime fields, the canonical RS codes (full-field and primitive) have polynomial-size lists at any fixed gap above the rate. The paper asks whether this holds over extension fields. It shows that it does not, for binary extension fields.

For every fixed rate 0<R<1, the full-field RS code over F_{2^h} has a received word with n^{Ω_R(log n)} codewords at agreement R+ε_R. The result also covers primitive RS codes and robust dense puncturing and shortening. To my knowledge, earlier superpolynomial lower bounds either had vanishing rate (Guruswami–Rudra, Ben-Sasson–Kopparty–Radhakrishnan) or a shrinking agreement gap (Hamming-ball counting). This is the first with both fixed rate and fixed gap.

The proof has three ideas:

1. An exact BCH–RS correspondence. Weight-D codewords of extended binary BCH codes biject with RS messages of degree D/2 that agree with β↦β^{2^h−1} on D points (Prop. 2.1). The derivative argument b′≡1 is specific to characteristic two. This turns classical weight-enumerator counts into list sizes.

2. Schmidt's trace-quadratic forms. Their enumeration gives 2^{h²/8−O(h)} words at rate 1/4 and agreement near 1/2.

3. Common-kernel descent plus common-root padding. A double count finds one subspace W under which many forms are invariant. Descent to a smaller additive domain then yields low-rate anchors, and padding lifts these to all rates. The resulting agreement envelope α*(R) is computed and shown optimal within the construction.

Methodological Rigor

The paper is a self-contained theory paper, and the arguments appear careful and checkable.

The bijection, the degree and weight scaling under descent, the character-sum weight formula, and the incidence double count are all elementary and verifiable.

The exponent check works out: 2a(m−a) at a=m/2 gives h²/8, i.e. n^{(log n)/8}.

Padding is handled for both the disjoint and overlapping regimes, including the averaging step that retains at least a 1/n fraction of messages.

Optimality of the dyadic density is proved in the appendix.

The puncturing corollary is proved uniformly over deleted sets.

The main reliance is on Schmidt's rank-distribution theorems, which are imported from a published source. The parameter translation is documented.

One conceptual point deserves flagging. At R=1/4 the anchor's agreement of 1/2 matches the Johnson radius √R, so the construction is tight there. Elsewhere it sits well below Johnson (e.g. 5/8 vs 0.707 at R=1/2). The paper is honest about this gap.

Potential Impact

List decoding theory. It shows that polynomial list size near capacity is not determined by rate and alphabet-size scaling alone. Field arithmetic and the evaluation set matter. This is a clean negative counterpart to the Brakensiek et al. and Jeronimo prime-field results, and it redirects the research agenda: which fields admit polynomial lists, and what happens under puncturing and in odd characteristic.

Proximity gaps and cryptographic proof systems. FRI-type protocols are increasingly deployed over binary towers (e.g. Binius-style systems). Although the paper is careful to state that its claim is about ordinary list size and not proximity gaps, it is directly relevant to the security-conjecture debate (cf. Crites–Stewart, Krachun et al.).

Technique. The BCH-weight-to-RS-list dictionary and the invariant-subspace descent are reusable. They could yield further lower bounds in characteristic two and might inspire analogues elsewhere.

Real-world application. There is none directly. The value is as a guide to which parameter regimes cannot be trusted.

Timeliness

The problem sits at the center of a very active line of work. Capacity-achieving RS list decoding has been resolved for prime fields, and conjectures about proximity gaps are driving real protocol design. A fixed-gap, fixed-rate counterexample over binary fields is therefore timely. It was a natural open question, and the answer is mildly surprising.

Strengths

It resolves a precisely stated open question with a clear, all-rate theorem.

It is conceptually elegant: the exact correspondence is simple but not obvious.

It is quantitatively complete, with an explicit envelope α*(R), optimality within the construction, and the primitive, puncturing and shortening corollaries.

It is candid about limitations and has a good list of open directions.

Exposition is clear, with the three-stage overview, worked intuition and explicit parameter bookkeeping.

Limitations

The lower bound is only superpolynomial (n^{Θ(log n)}), not exponential.

The agreement stays below Johnson except at R=1/4, so a large window remains between α* and √R.

Only characteristic two is treated, and the key derivative argument fails in odd characteristic. The prime-power and fixed-extension-degree cases remain open.

The puncturing robustness covers only dense sets (n/q bounded below), and random-puncturing regimes remain unresolved.

There is no algorithmic or constructive angle beyond existence of the received word, though the received word is explicit (X^{2^h−1}).

The unusual authorship disclosure (the AI system credited for essentially all the mathematical ideas) does not affect the mathematical content, but it may draw scrutiny and could affect reception.

Overall

This is a strong, focused theory paper with a clean negative result on a central question. It is likely to be widely cited in RS list-decoding and proximity-gap discussions. It is not a paradigm shift, but it substantively changes what researchers believe about extension-field RS codes.

Rating:8/ 10

Significance 8Rigor 8.5Novelty 8Clarity 8

Generated Oct 14, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 15/16

8.0/10 impact