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

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\mathrm{/}2\rfloor$ over every finite field ${\text{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\mathrm{/}2$ and the odd-characteristic range $3\le k\le q\mathrm{/}3$. In the remaining odd-characteristic range, local syndrome compatibility and combinatorial counting rule out additional deep holes.