Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound
Abstract
We study the minimum extension degree required for a Reed--Solomon code to admit exact 𝔽q-linear repair at the cut-set bound from every prescribed set of d helpers. Let s=d−k+1, and let Qs(n) be the minimum product of n pairwise coprime integers, each at least s. For every prime power q and all 3≤ k<d<n≤2d−2, we prove that the minimum degree over 𝔽q is exactly sQs(n). When all surviving nodes are helpers, we also characterize the admissible extension degrees and bound the number of coordinates that can attain the cut-set bound. The required achievability follows from existing construction methods; we give a short existence proof using splitting subspaces. For a family of parameters with n>2d−2, we obtain strictly smaller extension degrees, showing that the range restriction cannot be omitted altogether. Finally, we prove that a nonlinear repair scheme attaining the cut-set bound induces an 𝔽p-linear repair scheme on the same code, where p is the characteristic. Consequently, the extension-degree lower bounds over the prime field remain valid without a linearity assumption.
Related
- The Minimum Subpacketization of Reed-Solomon Codes with Linear Repair Achieving the Cut-Set Bound
- On the Minimum Number of Linear Pieces Required to Approximate Nonlinear Functions under an Accuracy Constraint
- Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields
- New Minimum Storage Regenerating Codes With Small Sub-packetization Levels for All Admissible Repair Degrees
- Coordinate-extension degrees and layered k-uniform hypergraphs
BibTeX
@misc{li2026exact,
title = {{Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound}},
author = {Yuhan Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34377},
eprint = {2610.34377},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34377},
}
RIS
TY - UNPB
TI - Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound
AU - Yuhan Li
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34377
UR - https://arxiv.org/abs/2610.34377
AB - We study the minimum extension degree required for a Reed--Solomon code to admit exact 𝔽_q-linear repair at the cut-set bound from every prescribed set of d helpers. Let s=d−k+1, and let Q_s(n) be the minimum product of n pairwise coprime integers, each at least s. For every prime power q and all 3≤ k<d<n≤2d−2, we prove that the minimum degree over 𝔽_q is exactly sQ_s(n). When all surviving nodes are helpers, we also characterize the admissible extension degrees and bound the number of coordinates that can attain the cut-set bound. The required achievability follows from existing construction methods; we give a short existence proof using splitting subspaces. For a family of parameters with n>2d−2, we obtain strictly smaller extension degrees, showing that the range restriction cannot be omitted altogether. Finally, we prove that a nonlinear repair scheme attaining the cut-set bound induces an 𝔽_p-linear repair scheme on the same code, where p is the characteristic. Consequently, the extension-degree lower bounds over the prime field remain valid without a linearity assumption.
ER -