WorksComputer Science
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 surviving coordinates at the cut-set bound. Write , and let be the minimum product of pairwise coprime integers, each at least . We locate the transition for the formula near : for every fixed and sufficiently large , the formula is exact up to , whereas strict improvement is possible at every length at least , 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.