Paperlane

no. 16 · Tuesday 17 November 2026

Minimum Extension Degrees for Reed-Solomon Codes:Exact Values and a Quadratic Transition

Yuhan Li

math.IT · v2 · 34 pp

Abstract

We study the minimum extension degree of Reed-Solomon codes admitting exact linear repair of every failed coordinate from any $d$ surviving coordinates at the cut-set bound. Write $s=d-k+1$, and let $Q_s(n)$ be the minimum product of $n$ pairwise coprime integers, each at least $s$. We locate the transition for the formula $sQ_s(n)$ near $n=d^2$: for every fixed $0<\varepsilon<1$ and sufficiently large $d$, the formula is exact up to $(1-\varepsilon)d^2$, whereas strict improvement is possible at every length at least $(1+\varepsilon)d^2$, uniformly over the base field and code dimension. The lower bound follows from an inequality for the cost of residual prime powers; the upper bound follows from an existing affine-plane construction. We also show that the full-helper coordinate-count bound is attained over sufficiently large base fields. Finally, nonlinear repair at cut-set equality induces linear repair over the prime field. Thus the degree bounds over that field remain valid, and the same transition holds when the repair base field is prime.

comments
34 pages
fields
Information Theory
pdf ↗ page arXiv:2610.34377 ↗