no. 16 · Tuesday 17 November 2026
Minimum Extension Degrees for Reed-Solomon Codes:Exact Values and a Quadratic Transition
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