betaFeedback

WorksComputer Science

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

Abstract

Let RSq(k)RS_q(k) denote the full-length Reed–Solomon code over Fq\mathbb{F}_q. Every word u=(ux)x∈Fq∈Fqqu=(u_x)_{x\in \mathbb{F}_q} \in \mathbb{F}_q^q has a unique interpolation polynomial U(X)∈Fq[X]U(X)\in \mathbb{F}_q[X] of degree less than qq, satisfying U(x)=uxU(x)=u_x for all x∈Fqx\in \mathbb{F}_q. It is well known that every word with °U=k°U=k is a deep hole. The Cheng–Murray conjecture asserts that these are the only deep holes for 3≤k≤q−23\le k\le q-2, except when qq is even and k=q−3k=q-3. Previous results established the conjecture for k≤p−1k\le p-1 and for k≥⌊(q−1)/2⌋k\ge\lfloor(q-1)/2\rfloor, where pp is the characteristic of Fq\mathbb{F}_q. In this paper, we prove the Cheng–Murray conjecture in the remaining range 3≤k≤⌊q/2⌋3\le k\le\lfloor q/2\rfloor, 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/23\le k\le q/2 when qq is even, and for 3≤k≤⌈q/3⌉3\le k\le\lceil q/3\rceil when qq is odd. For the remaining cases with qq odd, we combine local syndrome compatibility with combinatorial arguments to rule out additional deep holes.

Introduction

Let Fq\mathbb{F}_q denote the finite field of order qq, where qq is a prime power. For a word u∈Fqnu\in\mathbb{F}_q^n and a linear code C⊆FqnC\subseteq\mathbb{F}_q^n, the distance from uu to CC is defined by

d(u,C)=min⁡c∈CdH(u,c).d(u,C)=\min_{c\in C}d_H(u,c).

where the Hamming distance dHd_H counts the coordinates in which its two arguments differ. The covering radius of CC is

ρ(C)=max⁡u∈Fqnd(u,C).\rho(C)=\max_{u\in\mathbb{F}_q^n}d(u,C).

A word uu satisfying d(u,C)=ρ(C)d(u,C)=\rho(C) is called a deep hole of CC. Thus deep holes are the words farthest from CC.

For 1≤k<q1\le k<q, the full-length Reed–Solomon code over Fq\mathbb{F}_q is defined as

RS⁡q(k)={(f(x))x∈Fq:f∈Fq[X], deg⁡f<k}.\operatorname{RS}_q(k)=\{(f(x))_{x\in\mathbb{F}_q}:f\in\mathbb{F}_q[X],\ \deg f<k\}.

Every word u=(ux)x∈Fq∈Fqqu=(u_x)_{x\in\mathbb{F}_q}\in\mathbb{F}_q^q has a unique interpolation polynomial U∈Fq[X]U\in\mathbb{F}_q[X] of degree less than qq such that U(x)=uxU(x)=u_x for all x∈Fqx\in\mathbb{F}_q. We call UU the canonical representative of uu. For k≤deg⁡U<qk\leq\deg U<q, we have

q−deg⁡U≤d(u,RS⁡q(k))≤q−k.q-\deg U\leq d(u,\operatorname{RS}_q(k))\leq q-k.

The lower bound follows from the root bound for U−fU-f, and the upper bound from interpolation on any kk coordinates. Consequently, ρ(RS⁡q(k))=q−k\rho(\operatorname{RS}_q(k))=q-k, and every word with deg⁡U=k\deg U=k is a deep hole. These are called the expected deep holes; all other deep holes are called nonexpected.

In 2007, Cheng and Murray [5] conjectured that these are the only deep holes of RS⁡q(k)\operatorname{RS}_q(k). We state the conjecture in its corrected form, excluding the known exception in even characteristic [10, 22].

Conjecture 1.1 (Cheng–Murray). Let 3≤k≤q−23\leq k\leq q-2, excluding the case where qq is even and k=q−3k=q-3. A word u∈Fqqu\in\mathbb{F}_q^q is a deep hole of RS⁡q(k)\operatorname{RS}_q(k) if and only if its canonical representative has degree kk.

Equivalently, under the hypotheses of Conjecture 1.1, every polynomial UU with k<deg⁡U<qk<\deg U<q agrees with some polynomial of degree less than kk at k+1k+1 distinct field elements. In the excluded even-characteristic case k=q−3k=q-3, the additional deep holes are represented by aXq−2+f(X)aX^{q-2}+f(X), where a∈Fq×a\in\mathbb{F}_q^\times and deg⁡f<q−3\deg f<q-3 [10 Theorem 1].

For k=2k=2, the classification holds when qq is odd by [18 Theorem 10(1)], but fails in even characteristic; see the example following Lemma 2.1.

Related Work

Much of the early work on Reed–Solomon deep holes focused on words whose interpolation polynomials have degree k+dk+d, where d≥1d\geq1. Cheng and Murray [5] reduced the exclusion of such deep holes to the existence of rational points with distinct coordinates on certain algebraic hypersurfaces. Subsequent results based on character sums and distinct-coordinate counting were obtained by Li and Wan [13], Liao [15], and Zhu and Wan [23]. Cafure, Matera, and Privitelli [3] analyzed the singularities of related symmetric hypersurfaces to derive further deep-hole exclusions. In the reverse direction, Zhang and Wan [20] used connections with Reed–Solomon deep holes and finite geometry to obtain lower bounds for rational points on complete symmetric hypersurfaces. These approaches give deep-hole exclusions under various conditions on the field size, code dimension, and interpolation degree.

The first two excess degrees have received particular attention. For d=1d=1, Li and Wan [12] reduced the deep-hole question to a subset-sum problem and obtained explicit counting formulas. For full-length codes with 2≤k≤q−22\leq k\leq q-2, the degree-(k+1)(k+1) deep holes are completely classified: none occur in odd characteristic, while in even characteristic they occur precisely when k=q−3k=q-3 and the coefficient of XkX^k vanishes [14 Theorem 1]. For d=2d=2, Zhang, Fu, and Liao [19] constructed deep holes for proper evaluation sets and excluded degree-(k+2)(k+2) deep holes of full-length codes in odd characteristic when q>5q>5 and 2≤k≤q−32\leq k\leq q-3. Li and Zhu [14] subsequently determined the exact error distances of degree-(k+1)(k+1) words and obtained exact distances or upper bounds for degree-(k+2)(k+2) words in various parameter ranges. In a related direction, Li and Wan [11] studied the distance distribution of Reed–Solomon codes, while Gao and Li [8] improved the corresponding counting estimates and derived further degree-dependent deep-hole exclusions. These degree-restricted results do not, by themselves, yield a classification for arbitrary interpolation degrees.

A complementary approach relates deep holes to one-coordinate extensions of maximum-distance-separable (MDS) codes. Seroussi and Roth [16] established structural results on MDS extensions of generalized Reed–Solomon codes. Zhuang, Cheng, and Li [18 Theorem 10] used finite geometry to prove the full-length classification in odd characteristic pp when k+1≤pk+1\leq p or 3≤q−p+1≤k+1≤q−23\leq q-p+1\leq k+1\leq q-2. In particular, the Cheng–Murray conjecture holds over odd prime fields. Kaipa [10] exploited the correspondence between deep-hole syndromes and one-coordinate MDS extensions to obtain the classification for k≥⌊(q−1)/2⌋k \ge\lfloor(q-1)/2\rfloor, including the known even-characteristic exception. For a comprehensive survey of the deep-hole problem for generalized Reed–Solomon codes, including its connections with finite geometry and related computational questions, we refer to Zhang and Zhou [22].

Main Result and Proof Outline

The existing results do not settle the conjecture for all 3≤k≤⌊q/2⌋3 \le k \le\lfloor q/2\rfloor over extension fields. Our main theorem fills this gap.

Theorem 1.2. Let qq be a prime power and 3≤k≤⌊q/2⌋3 \le k \le\lfloor q/2\rfloor. A word u∈Fqqu \in\mathbb{F}_q^q is a deep hole of RS⁡q(k)\operatorname{RS}_q(k) if and only if its canonical representative UU has degree kk.

Together with the known classification for k≥⌊(q−1)/2⌋k \ge\lfloor(q-1)/2\rfloor, Theorem 1.2 completes the proof of Conjecture 1.1.

Our proof combines two complementary forms of rigidity arising from the deep-hole condition: the geometry of marked arcs and the compatibility of local syndromes.

We begin with the geometric approach. Let UU be the canonical representative of a deep hole, and associate with it the marked set

AU={[1:x:⋯:xk−1:U(x)]:x∈Fq}∪{[0:⋯:0:1]}⊆PG⁡(k,q).\mathcal{A}_U = \{[1 : x : \cdots: x^{k-1} : U(x)] : x \in\mathbb{F}_q\} \cup\{[0 : \cdots: 0 : 1]\} \subseteq\operatorname{PG}(k,q).

Here PG⁡(k,q)\operatorname{PG}(k,q) is the kk-dimensional projective space over Fq\mathbb{F}_q, and the last point is the marked point. The deep-hole condition is equivalent to AU\mathcal{A}_U being a (q+1)(q+1)-arc, meaning that every k+1k+1 of its points are projectively independent. Projection from the marked point gives the affine part of a normal rational curve. Exploiting this prescribed projection and the tangent-envelope theorem in the form given by Ball and Lavrauw [2, 1], we explicitly determine the restriction of the tangent-envelope form to the dual hyperplane parametrizing hyperplanes through the marked point. The resulting boundary form is expressed in terms of the discriminant in odd characteristic and its polynomial square root in characteristic two, together with the appropriate leading-coefficient factors. We then compute the first transverse coefficient of the envelope and derive linear differential constraints on UU. These constraints establish the conjecture for 3≤k≤q/23 \le k \le q/2 in even characteristic and q>3(k−1)q > 3(k-1) in odd characteristic, using the known error-distance result for degree-(k+1)(k+1) words to eliminate the residual possibility in characteristic three.

For the remaining range, which occurs only in odd characteristic, we develop a local-syndrome approach. We show that every (k+2)(k+2)-subset of Fq\mathbb{F}_q admits a unique template agreeing with UU, either a degree-kk polynomial or a rational function f(X)+c/(X−ζ)f(X) + c/(X-\zeta) with deg⁡f<k\deg f < k, c∈Fq×c \in\mathbb{F}_q^{\times}, and ζ∈Fq\zeta\in\mathbb{F}_q. A failure to extend such a template to an additional point produces a quadratic local syndrome outside the conic of evaluation functionals. The associated obstruction graph is a disjoint union of edges and isolated vertices in which the original (k+2)(k+2)-subset is independent. The key step is a compatibility argument showing that distinct failed extensions of a fixed subset produce distinct projective quadratic syndromes. Combining this noncollision property with a lower bound on the density of bad subsets forces a quantitative lower bound on the number of available quadratic obstructions. On the other hand, the matching structure permits an exact count of the corresponding independent subsets. Comparing these bounds excludes nonexpected deep holes in the remaining range for all odd q≥41q \ge41. The remaining odd proper extension fields q∈{9,25,27}q \in\{9,25,27\} are handled by elementary matching and counting arguments, together with a restricted sum–product lemma over F27\mathbb{F}_{27}.

Recent independent work. Around the time the present manuscript was completed and posted on arXiv [7], two independently developed preprints on the Cheng–Murray conjecture also appeared.

Chen and Huang [4] establish the deep-hole classification for every prime power q>19683q > 19683 and 3≤k≤q−23 \le k \le q - 2, including the known even-characteristic exception. They also parametrize the dimension-two deep holes in even characteristic by normalized oo-polynomials. Their proof combines planar-arc completion, quadratic quotient algebras, and weighted independent-set estimates for involution graphs. Although both approaches use finite geometry and syndrome methods, our proof proceeds differently: we derive differential constraints from the tangent envelope of a marked arc, and use local template compatibility and exact matching counts for quadratic obstructions to handle the remaining cases.

Fan [6] approaches the problem by prescribing the interpolation degree deg⁡U=k+m\deg U = k + m, where m≥3m \ge3. For 3≤m≤73 \le m \le7, he classifies all such deep holes over every finite field, including the exceptional dimension-two families in even characteristic. For arbitrary m≥3m \ge3, he excludes degree-(k+m)(k+m) deep holes when k≥3k \ge3 and q≥12(m+1)log⁡(2m+2)\sqrt{q} \ge12(m+1)\log(2m+2), and obtains a complete classification when q>16(m+2)4q > 16(m+2)^4. His methods rely on complete homogeneous symmetric functions, agreement estimates, and finite-field arguments, supplemented by certified computations for certain small cases.

Thus, Chen and Huang establish the classification for q>19683q > 19683, while Fan’s results either impose field-size conditions or concern specified excess degrees. In contrast, Theorem 1.2 establishes the classification for every prime power qq and every 3≤k≤⌊q/2⌋3 \le k \le\lfloor q/2\rfloor, without any field-size restriction or restriction on the interpolation degree. Combined with Kaipa’s high-dimensional result [10], it completely resolves Conjecture 1.1.

Organization

§ 2 characterizes deep holes by marked arcs. § 3 determines the boundary form and first transverse coefficient of the tangent envelope. § 4 proves the classification in even characteristic and for odd q>3(k−1)q > 3(k-1). § 5 establishes the existence and uniqueness of local templates, while § 6 uses quadratic obstructions to settle odd q≥41q \ge41. § 7 completes the remaining small-field cases and proves the main theorem. The uniform quadratic-matching estimate is proved in Appendix § 9.

A Marked-Arc Characterization of Deep Holes

In this section, we characterize deep holes in terms of marked projective arcs and describe their associated tangent hyperplanes. For a nonnegative integer mm, let Fq[X]≤m\mathbb{F}_q[X]_{\le m} denote the space of polynomials over Fq\mathbb{F}_q of degree at most mm. We write [Xj]H[X^j]H for the coefficient of XjX^j in HH, and (Sr)\binom{S}{r} for the family of rr-subsets of a finite set SS. For F∈Fq[X]F \in\mathbb{F}_q[X], write

ev⁡(F)=(F(x))x∈Fq.\operatorname{ev}(F) = (F(x))_{x \in\mathbb{F}_q}.

For any S⊆FqS \subseteq\mathbb{F}_q, put

PS(X)=∏a∈S(X−a),P∅(X)=1.P_S(X) = \prod_{a \in S}(X-a), \qquad P_{\varnothing}(X) = 1.

For nonempty SS and deg⁡H<∣S∣\deg H < |S|, Lagrange interpolation takes the form

H(X)=∑a∈SH(a)PS(X)(X−a)PS′(a).H(X) = \sum_{a \in S} H(a)\frac{P_S(X)}{(X-a)P'_S(a)}.

Comparing the coefficients of X∣S∣−1X^{|S|-1}, we obtain

∑a∈SH(a)PS′(a)=[X∣S∣−1]H(deg⁡H<∣S∣).(1)\sum_{a \in S}\frac{H(a)}{P'_S(a)} = [X^{|S|-1}]H \qquad(\deg H < |S|). \tag*{(1)}

Since ρ(RS⁡q(k))=q−k\rho(\operatorname{RS}_q(k))=q-k, a vector with canonical representative UU is a deep hole precisely when no polynomial of degree less than kk agrees with UU at k+1k+1 distinct elements of Fq\mathbb{F}_q. Equivalently,

References

  1. [1]S. Ball and M. Lavrauw, “Arcs in finite projective spaces,” EMS Surv. Math. Sci., vol. 6, no. 1–2, pp. 133–172, 2019. https://doi.org/10.4171/EMSS/33.
  2. [2]S. Ball and M. Lavrauw, “Arcs and tensors,” Des. Codes Cryptogr., vol. 88, no. 1, pp. 17–31, 2020. https://doi.org/10.1007/s10623-019-00668-z.
  3. [3]A. Cafure, G. Matera, and M. Privitelli, “Singularities of symmetric hypersurfaces and Reed–Solomon codes,” Adv. Math. Commun., vol. 6, no. 1, pp. 69–94, 2012. https://doi.org/10.3934/amc.2012.6.69.
  4. [4]B. Chen and J. Huang, “Deep holes of full-length Reed–Solomon codes,” arXiv:2610.29429, 2026. https://arxiv.org/abs/2610.29429.
  5. [5]Q. Cheng and E. Murray, “On deciding deep holes of Reed–Solomon codes,” in Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 4484. Berlin, Germany: Springer, 2007, pp. 296–305. https://doi.org/10.1007/978-3-540-72504-6_27.
  6. [6]X. Fan, “Deep holes of full-length Reed–Solomon codes: uniform bounds and exact classifications,” arXiv:2610.31460, 2026. https://arxiv.org/abs/2610.31460.
  7. [7]W. Fang, “The Cheng–Murray Conjecture on Deep Holes of Full-Length Reed–Solomon Codes,” arXiv:2610.31531, 2026. https://arxiv.org/abs/2610.31531.
  8. [8]Z. Gao and J. Li, “Improved error bounds for the distance distribution of Reed–Solomon codes,” IEEE Trans. Inf. Theory, vol. 69, no. 6, pp. 3590–3596, 2023. https://doi.org/10.1109/TIT.2023.3242612.
  9. [9]S.-G. Guo, “Restricted sumsets in a finite abelian group,” Discrete Math., vol. 309, nos. 23–24, pp. 6530–6534, 2009. https://doi.org/10.1016/j.disc.2009.06.028.
  10. [10]K. Kaipa, “Deep holes and MDS extensions of Reed–Solomon codes,” IEEE Trans. Inf. Theory, vol. 63, no. 8, pp. 4940–4948, 2017. https://doi.org/10.1109/TIT.2017.2706677.
  11. [11]J. Li and D. Wan, “Distance distribution in Reed–Solomon codes,” IEEE Trans. Inf. Theory, vol. 66, no. 5, pp. 2743–2750, 2020. https://doi.org/10.1109/TIT.2019.2933625.
  12. [12]J. Li and D. Wan, “On the subset sum problem over finite fields,” Finite Fields Appl., vol. 14, no. 4, pp. 911–929, 2008. https://doi.org/10.1016/j.ffa.2008.05.003.
  13. [13]Y. Li and D. Wan, “On error distance of Reed–Solomon codes,” Sci. China Ser. A Math., vol. 51, no. 11, pp. 1982–1988, 2008. https://doi.org/10.1007/s11425-008-0066-3.
  14. [14]Y. Li and G. Zhu, “On the error distance of extended Reed–Solomon codes,” Adv. Math. Commun., vol. 10, no. 2, pp. 413–427, 2016. https://doi.org/10.3934/amc.2016015.
  15. [15]Q. Liao, “On Reed–Solomon codes,” Chinese Ann. Math. Ser. B, vol. 32, no. 1, pp. 89–98, 2011. https://doi.org/10.1007/s11401-010-0622-3.
  16. [16]G. Seroussi and R. M. Roth, “On MDS extensions of generalized Reed–Solomon codes,” IEEE Trans. Inf. Theory, vol. 32, no. 3, pp. 349–354, 1986. https://doi.org/10.1109/TIT.1986.1057188.
  17. [17]R. Wu and S. Hong, “On deep holes of standard Reed–Solomon codes,” Sci. China Math., vol. 55, no. 12, pp. 2447–2455, 2012. https://doi.org/10.1007/s11425-012-4499-3.
  18. [18]J. Zhuang, Q. Cheng, and J. Li, “On determining deep holes of generalized Reed–Solomon codes,” IEEE Trans. Inf. Theory, vol. 62, no. 1, pp. 199–207, 2016. https://doi.org/10.1109/TIT.2015.2496325.
  19. [19]J. Zhang, F.-W. Fu, and Q.-Y. Liao, “Deep holes of generalized Reed–Solomon codes (in Chinese),” Sci. Sin. Math., vol. 43, no. 7, pp. 727–740, 2013. https://doi.org/10.1360/012012-30.
  20. [20]J. Zhang and D. Wan, “Rational points on complete symmetric hypersurfaces over finite fields,” Discrete Math., vol. 343, no. 11, Art. no. 112072, 2020. https://doi.org/10.1016/j.disc.2020.112072.
  21. [21]J. Zhang, D. Wan, and K. Kaipa, “Deep holes of projective Reed–Solomon codes,” IEEE Trans. Inf. Theory, vol. 66, no. 4, pp. 2392–2401, 2020. https://doi.org/10.1109/TIT.2019.2940962.
  22. [22]J. Zhang and H. Y. Zhou, “The deep hole problem of generalized Reed–Solomon codes (in Chinese),” Sci. Sin. Math., vol. 53, no. 11, pp. 1409–1424, 2023. https://doi.org/10.1360/SSM-2023-0118.
  23. [23]G. Zhu and D. Wan, “Computing error distance of Reed–Solomon codes,” in Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 7287. Berlin, Germany: Springer, 2012, pp. 214–224. https://doi.org/10.1007/978-3-642-29952-0_24.

Paper details

vlnc:W_je7hwryf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents