Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes

1.2 The common interpolation theorem

• A common differential interpolant underlies decoding and the stronger exact-support MCA conclusion.The framework uses a hidden-derivative construction, with a free constant derivative order and optimized two-cutoff estimates; it also stacks constraints over point–symbol incidences for sparse list recovery.Source: §1 · p. 3, §1.2 · p. 5

1.1 Main results

• At radius 1 − k/n − γ, ordinary Reed–Solomon codes admit deterministic decoding with polynomial-size lists independent of q.The guarantee holds for sufficiently large n, prime q ≥ n, and 1 ≤ k ≤ (1 − γ)n; the decoder runs in q^{Oγ(1)} time.Source: §1.1 · pp. 3–4
• For fixed curve degree ℓ, only polynomially many parameters can have a nearby codeword whose exact support is not jointly explained.The stated exception budget depends on γ and ℓ; for lines, the MCA estimate becomes nonvacuous when q exceeds that budget.Source: §1.1 · p. 4

1.2 The common interpolation theorem

• Every degree-below-K polynomial with at least A list hits satisfies the constructed differential equation.The equation evaluates Q on the polynomial and its Hasse derivatives; degree padding keeps K = Θγ(n) even when the code dimension is smaller.Source: §1.2 · pp. 4–5

1.3 From differential equations to exact supports

• A specialization-safe differential equation places witnesses, outside polynomially many parameters, in varieties of dimension at most r + 1 and polynomial cumulative degree.This bounded-complexity cover supports subsequent support-hyperplane cuts for list bounds and exact-support analysis.Source: §1.3 · p. 5
• Support-preserving descent connects candidate counting to MCA: nonvertical curve branches force coefficientwise support equations, while Reed–Solomon uniqueness yields maximality.The paper says the geometric statements used here are proved in this paper, rather than invoked from the unpublished companion note.Source: §1.3 · p. 5

1.4 Context and scope

• The guarantee applies to ordinary Reed–Solomon encoding on every prescribed evaluation set over prime fields, unlike results limited to suitable, generic, or random sets.The paper presents its all-rate conclusion as an extension of the capacity-decoding framework of Brakensiek, Chen, Putterman, Zhang, and Zheng, not a replacement of its interpolation mechanism.Source: §1.4 · p. 6
• The theorems require fixed γ and sufficiently large n, and do not establish a uniform estimate as γ shrinks with n.The decoder is polynomial in q rather than log q, and the list bound is polynomial in n rather than constant.Source: §1.4 · p. 6

2.1 Hasse derivatives

• The preliminaries introduce Hasse derivatives and record a backward identity obtained by replacing X with X + T and T with −T.They also state that the relevant binomial coefficients are nonzero when the degree is below the field characteristic.Source: §2.1 · pp. 6–7

2.2 Sparse list recovery and padding

• Sparse list recovery specifies evaluation points, input lists, a degree bound, and an agreement threshold; ordinary list decoding is its singleton-list case.Degree padding permits solving at a larger degree ceiling K and filtering outputs to retain those below k.Source: §2.2 · p. 7

2.3 Agreement supports and mutual correlated agreement

• For an exact agreement support of size at least k, being jointly explained implies inclusion-maximality among explained supports.In the regime Aρ ≥ k, the paper identifies such supports with the defined collection of maximal correlated sets of size at least Aρ.Source: §2.3 · p. 8
• Reed–Solomon uniqueness underlies the maximality argument: two degree-below-k polynomials agreeing on at least k coordinates must coincide.The proof uses this to rule out a strict superset of the full agreement support that is also explained.Source: §2.3 · p. 8

3.1 The interpolation space

• The interpolation space reparameterizes the two-cutoff construction in [BCPZZ26, Eq. (18)], using a weighted derivative-tail cutoff and an ordinary-degree cutoff.The ordinary cutoff supports sharper monomial enumeration, while the gap between cutoffs is optimized later.Source: §3.1 · p. 8

3.2 Local constraints and root multiplicity

• At each point-symbol pair, homogeneous local constraints ensure that any agreeing polynomial makes the specialized differential polynomial vanish to multiplicity at least m.The substitution and multiplicity argument are parameterized versions of the hidden-derivative construction in [BCPZZ26, Lemma 3.1].Source: §3.2 · pp. 9–10

3.3 Dimension of the interpolation space

• For fixed constants u0 > s > 1, the interpolation-space dimension is at least a0 |T| (K−1)m^3 for sufficiently large m, with a0 = Ω(min{1, u0−s}^3).The lower bound comes from box-counting: the ordinary-degree buffer leaves a three-dimensional exponent box for each derivative-tail monomial.Source: §3.3 · p. 10

3.4 Tail-monomial geometry

• A uniform parameterized growth bound controls how the derivative-tail monomial set expands when its weighted cutoff is enlarged.The estimate holds uniformly over c in a compact interval J within (1, ∞).Source: §3.4 · p. 11

3.5 The local rank bound

• A triangular change of variables exposes independent kernel subspaces of the local constraint map, yielding a local rank bound uniform in the point-symbol pair.The kernel-space construction avoids counting all truncated coefficients directly.Source: §3.5 · pp. 12–13

3.6 The global interpolation theorem

• There is a nonzero interpolant satisfying every incidence constraint, and every degree-below-K polynomial with at least A list hits satisfies its differential equation.The fixed-shape version makes transparent the mechanism of comparing the dimension of Q with the sum of local ranks.Source: §3.6 · p. 14, §3.6.1 · p. 15

3.7 The coefficient-level interpolation interface

• Over any field, a fixed-basis homogeneous interpolation matrix has a nonzero kernel, and each nonzero kernel vector yields the differential equation for every degree-below-K polynomial with at least A list hits.For fixed r and B, the matrix has O_{r,B}(n) columns and O_{r,B}(M) rows, and its claims remain valid under coefficient-field extension.Source: §3.7 · p. 16, Every degree-below-K polynomial with… · p. 16

Every degree-below-K polynomial with at least A list hits satisfies

• For fixed r and B, each incidence contributes constantly many local rows, and the received symbol has degree at most B in the Y0 substitution.The local equations are identities over the coefficient field, so extending scalars preserves both those equations and the degree–multiplicity implication.Source: Every degree-below-K polynomial with… · p. 16

4.1 Padding at the actual rate

• Uniform fixed-slack parameters can be chosen independently of n, k, and A for sufficiently large n and total incidence M ≤ Ln.The same parameter choice makes the constants independent of the actual rate k/n.Source: §4.1 · pp. 16–17

4.2 Prime-field differential-equation root finding

• Kopparty’s prime-field root solver enumerates degree-bounded solutions to the interpolant’s differential equation, including candidates that fail the agreement test.The section distinguishes this raw root set from the smaller set retained by agreement filtering.Source: §4.2 · p. 17, §4.3 · p. 19

4.3 Sparse list recovery and its running time

• Directly counting admissible derivative tails as weak compositions gives r^O(r) possibilities, sharpening runtime without a new linear-algebra primitive.The two-cutoff derivative-tail space itself already appears in.Source: §4.3 · p. 19
• q^Oγ,L(1) field operations suffice for deterministic sparse list recovery, with the output list bounded by q4r+6.The result applies to prime fields and returns every degree-below-k polynomial meeting the specified list-hit threshold.Source: §4.3 · pp. 18–19

5.1 A primitive polynomial interpolant over Fq[Z]

• A primitive polynomial interpolant over Fq[Z] remains nonzero after every specialization and captures every nearby polynomial through a differential equation.Its polynomial-kernel construction preserves the interpolation constraints after specialization.Source: §5.1 · p. 20

5.2 Cumulative degree

• The cumulative-degree bounds control the complexity of graphs of rational maps and of intersections with bounded-degree equations.These bounds supply the geometric tools for covering solution loci.Source: §5.2 · pp. 20–21

5.3 Effective jet decomposition of the solution locus

• The parametric jet-decomposition theorem covers solutions outside finitely many exceptional parameters by affine algebraic sets of bounded dimension and cumulative degree.Exceptional parameters can occur when coefficients of the highest-derivative partial vanish after specialization.Source: §5.3 · p. 22

5.3.1 Triangular Hasse–Taylor lifting

• Hasse–Taylor lifting recursively expresses higher coefficients as rational functions of an initial jet on the open set where the triangular coefficient is nonzero.The lifted numerator degree is at most 4(D + B)t^2, and residual equations have polynomially bounded degrees.Source: §5.3.1 · pp. 23–24

5.3.2 Proof of the jet-decomposition theorem

• The proof handles singular solutions by induction on derivative-variable degree and bounds the resulting cover through constant-dimensional intersections.It accounts for only polynomially many exceptional parameter values and polynomial cumulative degree.Source: §5.3.2 · pp. 24–25

Counting candidates

• The geometric cover has bounded dimension and cumulative degree, and agreement equations isolate each candidate using its assigned support.At least k distinct evaluation equations determine a degree-below-k polynomial through an invertible Vandermonde system.Source: §6 · pp. 26–27

List bound and decoding radius

• n^{O_{γ,L}(1)} bounds the list size for sufficiently large n when q ≥ n and the input lists have size at most L.For singleton lists, this gives decoding at relative distance 1 − k/n − γ; the running time is q^{O_{γ,L}(1)}.Source: §6 · p. 27

Scope of the bound

• The field-independent bound counts roots that pass the agreement filter, whereas differential root enumeration can still require q^{O(r)} time.The geometric cover improves the count of actual list candidates, not the stated decoder's dependence on q.Source: §6 · pp. 26–27

7.1 Descent along the full agreement support

• A witness is branch-explained when its full assigned support equations vanish identically on a positive-dimensional nonvertical branch through it.Otherwise, successive proper intersections reach a zero-dimensional or vertical component after at most s cuts.Source: §7.1 · p. 28
• A nonvertical branch on which all support equations vanish identically yields coefficient polynomials that jointly explain the entire support.A Vandermonde system recovers their coefficients, and varying the parameter forces the support equations to hold coefficientwise.Source: §7.1 · p. 29

7.2 Proof of the MCA theorem

• For fixed curve degree ℓ, only polynomially many parameters can have a nearby witness whose exact support is not maximal and jointly explained.For lines, the uniform bad-parameter bound gives an MCA error estimate after maximizing over coefficient words and dividing by q.Source: §7.2 · p. 30

8.1 Coordinate transformations, punctures, and erasures

• Puncturing is covered by arbitrary evaluation sets, erased coordinates can be omitted, and coordinate scalings preserve the MCA supports described here.Arbitrary translations are allowed for list decoding and list recovery, but not stated for MCA.Source: §8.1 · p. 31

8.2 Fixed interleaving

• For fixed γ and h, interleaved lists have polynomial size in n and can be enumerated deterministically in q^{O_{γ,h}(1)} field operations.The construction takes products of the scalar lists and tests common-column agreement.Source: §8.2 · p. 31

8.3 Fixed-slack certificates for the proximity challenges

• The certified radii are 1/2 − γ at rate 1/2, 3/4 − γ at rate 1/4, 7/8 − γ at rate 1/8, and 15/16 − γ at rate 1/16.These are lower-bound certificates for the safe radius, not determinations of the largest safe radius.Source: §8.3 · p. 32

8.4 Field characteristic and the endpoint

• The characteristic conditions include p > k − 1 and p > B_{γ,L}, while the theorems require fixed slack γ rather than an untracked n-dependent slack.The fixed-slack statements do not address the shrinking near-capacity window or the exact integer-error boundary.Source: §8.4 · p. 32

8.5 Effectivity and remaining quantitative questions

• The constants are unoptimized, and the paper claims neither a useful certificate for prescribed small block lengths nor a poly(n, log q) decoder.Concrete applications must check the field-size inequality and sufficiently-large-length threshold; the list bound is polynomial in n, not constant.Source: §8.5 · p. 32

• ChatGPT 5.6 Pro interactions were crucial in obtaining the paper’s main results.Source: AI Disclosure · p. 33
• ChatGPT 5.6 and 6 Pro were also used as editorial assistants.Source: AI Disclosure · p. 33
• The authors take full responsibility for the results and say they verified all claims, proofs, and references.Source: AI Disclosure · p. 33

• Theorem A.1 transfers a root solver for degree-below-K solutions to sparse list recovery with actual degree bound k −1.The transfer assumes Equations (46) and (47), D ≥ r3A, and that the root solver applies to the interpolant from Proposition 3.8.Source: A Transfer to other root-enumeration… · p. 35
• The transferred algorithm’s output list is bounded by Lroot, the assumed root solver’s output bound.Source: A Transfer to other root-enumeration… · p. 35
• The proof constructs a nonzero interpolant, invokes the root solver, and filters outputs by degree and list agreement.The stated running time includes verification of returned roots rather than assuming that cost is included in Troot.Source: A Transfer to other root-enumeration… · p. 35

• For fixed ϑ, ε, and input-list bound L, the corollary gives list recovery up to A hits for sufficiently large n.It applies to instances with |Si| ≤ L and k ≤ K.Source: §B.1 · p. 35
• The runtime is q^Oϑ(r) over prime q ≥ n satisfying the degree conditions.The interpolation and root-enumeration stages each have this bound in the stated prime-field parameter range.Source: §B.1 · pp. 35–36
• The runtime is fixed-parameter polynomial, not polynomial in 1/ϑ or the additive capacity gap.Source: §B.1 · p. 36

B.2 Rounding and field-size thresholds

• At the capacity-minus-γ radius, choosing A = k + ⌈γn⌉ and K = ⌈(1 − γ/2)A⌉ ensures K ≥ k and K − 1 < (1 − γ/2)A.The same rounding lemma applies at smaller radii by increasing A up to n.Source: §B.2 · p. 36
• With γ and L fixed, r, m, and B are constants and K = Θγ(n), so the degree conditions hold for sufficiently large n when q ≥ n.The stricter field-size budget in Corollary 8.3 instead makes polynomially many exceptional parameters or a polynomial list small relative to q.Source: §B.2 · p. 36

B.3 Parameter ledger

• The parameter ledger defines γ, L, ℓ, A, K, ϑ, r, and m by their roles in slack, input lists, curve degree, hit thresholds, padding, and differential order.Source: §B.3 · p. 37
• The ledger identifies W as the weighted derivative-tail budget, B as the derivative-variable degree bound, and Δ as polynomial cumulative degree of the solution cover.SP and Sz denote full list-hit or exact agreement support; MCA uses the full support rather than an agreement subset.Source: §B.3 · p. 37