Cheng-Murray conjecture solved for deep holes in Reed-Solomon codes
The Cheng-Murray Conjecture on Deep Holes of Full-Length Reed-Solomon Codes
Information Theory
Summary
The paper deals with a question about Reed-Solomon codes, which are used to detect and fix errors in digital communication. It focuses on special problematic cases called deep holes. The Cheng-Murray conjecture predicted exactly which received words are deep holes in most cases, and previous work solved it for some fields and dimensions. The authors complete the proof for all remaining cases, using geometric and combinatorial methods.
What this means in practice
- •For error correction engineers: Improve design and analysis of error-correcting algorithms by fully characterizing challenging cases in Reed-Solomon decoding.
- •For communication system designers: Build more reliable communication protocols by understanding rare error patterns that limit Reed-Solomon code decoding.
A theory result. No direct application yet.
Authors
Weijun Fang
Abstract
For full-length Reed--Solomon codes, every received word whose interpolation polynomial has degree equal to the code dimension is a deep hole. The Cheng--Murray conjecture asserts that these are the only deep holes in dimensions $3\le k\le q-2$, except when $q$ is even and $k=q-3$. Earlier results settled the conjecture over odd prime fields and in the high-dimensional range. We resolve the remaining cases $3\le k\le\lfloor q/2\rfloor$ over every finite field $\F_q$, thereby completing the classification in all nonexceptional dimensions. Our proof combines two complementary approaches. The tangent envelope of a marked arc yields differential constraints that settle the even-characteristic range $3\le k\le q/2$ and the odd-characteristic range $3\le k\le q/3$. In the remaining odd-characteristic range, local syndrome compatibility and combinatorial counting rule out additional deep holes.