Deep holes of full-length Reed--Solomon codes
Abstract
For every prime power q>19683, we settle the Cheng--Murray deep-hole problem for full-length Reed--Solomon codes in every dimension 2≤ k≤ q−2, with the characteristic-two cases stated explicitly. For odd q, the deep holes are precisely the words of degree k. For even q and k≥3, the same conclusion holds except for an additional family when k=q−3. In even characteristic and dimension two, every deep hole has a unique expression a h(X)+bX+c, where a≠0 and h is a normalized o-polynomial. The proof combines quadratic quotient algebras, graph-theoretic weighted independent-set inequalities, and planar arc completion. We also obtain normal rational curve rigidity in the corresponding nonexceptional dimensions, the projective Reed--Solomon covering radii, and distinct-coordinate solvability and remainder criteria.
Related
- Deep holes of full-length Reed--Solomon codes: uniform bounds and exact classifications
- The Cheng-Murray Conjecture on Deep Holes of Full-Length Reed-Solomon Codes
- Covering Radius and Deep Holes of Hyperderivative Reed-Solomon Codes under the NRT Metric
- Extremal diagonal-coherent binary codes: shortened Hamming cores, deep holes, and the 64 I-Ching hexagrams
- Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
BibTeX
@misc{chen2026deep,
title = {{Deep holes of full-length Reed--Solomon codes}},
author = {Bocong Chen and Jing Huang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29429},
eprint = {2610.29429},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29429},
}
RIS
TY - UNPB
TI - Deep holes of full-length Reed--Solomon codes
AU - Bocong Chen
AU - Jing Huang
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29429
UR - https://arxiv.org/abs/2610.29429
AB - For every prime power q>19683, we settle the Cheng--Murray deep-hole problem for full-length Reed--Solomon codes in every dimension 2≤ k≤ q−2, with the characteristic-two cases stated explicitly. For odd q, the deep holes are precisely the words of degree k. For even q and k≥3, the same conclusion holds except for an additional family when k=q−3. In even characteristic and dimension two, every deep hole has a unique expression a h(X)+bX+c, where a≠0 and h is a normalized o-polynomial. The proof combines quadratic quotient algebras, graph-theoretic weighted independent-set inequalities, and planar arc completion. We also obtain normal rational curve rigidity in the corresponding nonexceptional dimensions, the projective Reed--Solomon covering radii, and distinct-coordinate solvability and remainder criteria.
ER -