Deep holes of full-length Reed--Solomon codes: uniform bounds and exact classifications
Abstract
Let u be a received word for the full-length Reed--Solomon code RSq(k), with interpolation polynomial fu of degree k+m. For each m∈{3,4,5,6,7}, we classify all such deep holes over every finite field, without a field-size hypothesis. None occur for odd m in this range. At m=4 and m=6, the only exceptions are, respectively, the Segre sextic and Frobenius-power families; these occur only in dimension two over fields of characteristic two. For arbitrary mgeqslant3, we also establish two uniform bounds. If √qgeqslant12(m+1)log(2m+2), no word of interpolation degree k+m is a deep hole when q is odd, kgeqslant3, or m is odd. If q>16(m+2)4, we obtain the corresponding complete classification at every admissible k, including the explicit dimension-two exceptions. Our proofs use an agreement criterion expressed in complete homogeneous symmetric functions, agreement-count estimates, finite geometry, permutation-polynomial restrictions, and subset constructions for solving the resulting symmetric-function equations. The remaining finite cases are settled by finite computations with supplied certificates and deterministic verification programs.
Related
- Deep holes of full-length Reed--Solomon codes
- The Cheng-Murray Conjecture on Deep Holes of Full-Length Reed-Solomon Codes
- Uniform lower bounds for the average length of finite Pierce expansions
- Covering Radius and Deep Holes of Hyperderivative Reed-Solomon Codes under the NRT Metric
- A Uniform Bound on Optimal Strategy Length in Water Transport Problem
BibTeX
@misc{fan2026deep,
title = {{Deep holes of full-length Reed--Solomon codes: uniform bounds and exact classifications}},
author = {Xiang Fan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31460},
eprint = {2610.31460},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31460},
}
RIS
TY - UNPB
TI - Deep holes of full-length Reed--Solomon codes: uniform bounds and exact classifications
AU - Xiang Fan
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.31460
UR - https://arxiv.org/abs/2610.31460
AB - Let u be a received word for the full-length Reed--Solomon code RS_q(k), with interpolation polynomial f_u of degree k+m. For each m∈{3,4,5,6,7}, we classify all such deep holes over every finite field, without a field-size hypothesis. None occur for odd m in this range. At m=4 and m=6, the only exceptions are, respectively, the Segre sextic and Frobenius-power families; these occur only in dimension two over fields of characteristic two. For arbitrary mgeqslant3, we also establish two uniform bounds. If √qgeqslant12(m+1)log(2m+2), no word of interpolation degree k+m is a deep hole when q is odd, kgeqslant3, or m is odd. If q>16(m+2)^4, we obtain the corresponding complete classification at every admissible k, including the explicit dimension-two exceptions. Our proofs use an agreement criterion expressed in complete homogeneous symmetric functions, agreement-count estimates, finite geometry, permutation-polynomial restrictions, and subset constructions for solving the resulting symmetric-function equations. The remaining finite cases are settled by finite computations with supplied certificates and deterministic verification programs.
ER -