The Cheng-Murray Conjecture on Deep Holes of Full-Length Reed-Solomon Codes

Abstract

Let RS_q(k) denote the full-length Reed--Solomon code over 𝔽_q. Every word u=(u_x)_{x∈ 𝔽_q} ∈ 𝔽_q^q has a unique interpolation polynomial U(X)∈ 𝔽_q[X] of degree less than q, satisfying U(x)=u_x for all x∈ 𝔽_q. It is well known that every word with °U=k is a deep hole. The Cheng--Murray conjecture asserts that these are the only deep holes for 3≤ k≤ q−2, except when q is even and k=q−3. Previous results established the conjecture for k≤ p−1 and for k≥⌊(q−1)/2⌋, where p is the characteristic of 𝔽_q. In this paper, we prove the Cheng--Murray conjecture in the remaining range 3≤ k≤⌊ q/2⌋, thereby resolving it completely. Our proof combines two complementary approaches. The tangent envelope of a marked arc yields differential constraints that establish the conjecture for 3≤ k≤ q/2 when q is even, and for 3≤ k≤⌈ q/3⌉ when q is odd. For the remaining cases with q odd, we combine local syndrome compatibility with combinatorial arguments to rule out additional deep holes.

Deep holes of full-length Reed--Solomon codes
Bocong Chen, Jing Huang
arXiv21 Oct 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
Deep holes of full-length Reed--Solomon codes: uniform bounds and exact classifications
Xiang Fan
arXiv22 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Covering Radius and Deep Holes of Hyperderivative Reed-Solomon Codes under the NRT Metric
Zhihao Zhu, Haojie Gu, Jun Zhang +1
arXiv12 Oct 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
On the length conjecture for twist knots
Samuel Panitch, Mauricio Romo
arXiv2 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Geometry & topologyarXiv
Two refined Wilf-equivalences for patterns of length 4 and a conjecture on Dumont permutations of the first kind
Zuo-Ru Zhang, Hongkuan Zhao
arXiv22 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{fang2026chengmurray,
  title = {{The Cheng-Murray Conjecture on Deep Holes of Full-Length Reed-Solomon Codes}},
  author = {Weijun Fang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.31531},
  eprint = {2610.31531},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.31531},
  note = {CC0},
}

RIS

TY  - UNPB
TI  - The Cheng-Murray Conjecture on Deep Holes of Full-Length Reed-Solomon Codes
AU  - Weijun Fang
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2610.31531
UR  - https://arxiv.org/abs/2610.31531
AB  - Let RS_q(k) denote the full-length Reed--Solomon code over 𝔽_q. Every word u=(u_x)_x∈ 𝔽_q ∈ 𝔽_q^q has a unique interpolation polynomial U(X)∈ 𝔽_q[X] of degree less than q, satisfying U(x)=u_x for all x∈ 𝔽_q. It is well known that every word with °U=k is a deep hole. The Cheng--Murray conjecture asserts that these are the only deep holes for 3≤ k≤ q−2, except when q is even and k=q−3. Previous results established the conjecture for k≤ p−1 and for k≥⌊(q−1)/2⌋, where p is the characteristic of 𝔽_q. In this paper, we prove the Cheng--Murray conjecture in the remaining range 3≤ k≤⌊ q/2⌋, thereby resolving it completely. Our proof combines two complementary approaches. The tangent envelope of a marked arc yields differential constraints that establish the conjecture for 3≤ k≤ q/2 when q is even, and for 3≤ k≤⌈ q/3⌉ when q is odd. For the remaining cases with q odd, we combine local syndrome compatibility with combinatorial arguments to rule out additional deep holes.
ER  -

Abstract

Related

Cite