PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Weijun Fang

arXiv:2610.31531v1cs.ITmath.IT

TL;DR

Existing results did not settle the entire below-half range over extension fields. The proof combines tangent-envelope differential constraints with local-syndrome compatibility and combinatorial counting. It classifies deep holes in the remaining range and, with known high-dimensional results, establishes the corrected conjecture in all nonexceptional dimensions.

  • Problem

    Existing results do not settle the entire below-half range over extension fields.

    Source: B. Main Result and Proof Outline · p. 2

  • Method

    The proof uses tangent-envelope differential constraints and, beyond their range, local-syndrome restrictions with exact matching counts and a restricted sum–product argument.

    Source: §VIII · p. 21

  • Results

    For prime powers q and 3 ≤ k ≤ ⌊q/2⌋, a word is a deep hole of RSq(k) exactly when its canonical representative has degree k.

    Source: B. Main Result and Proof Outline · p. 2

  • Takeaways & Limitations

    Together with known high-dimensional results, the classification establishes the corrected Cheng–Murray conjecture for every prime power q and every nonexceptional dimension 3 ≤ k ≤ q − 2.

    Source: B. Main Result and Proof Outline · p. 2

Abstract

from arXiv · show

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.

I. INTRODUCTION

The Cheng–Murray conjecture asks whether deep holes of full-length Reed–Solomon codes are exactly the words whose canonical representatives have degree k, apart from a known even-characteristic exception. This paper fills the remaining below-half range over finite fields, combining marked-arc and tangent-envelope methods with local-syndrome counting.

I. INTRODUCTION

  • A word is an expected deep hole when its canonical representative has degree k; the conjecture asks whether any others exist, excluding even q and k=q−3.The conjecture concerns dimensions 3≤k≤q−2.Source: §I · p. 1

A. Related Work

  • Earlier geometric and counting methods excluded deep holes only under conditions on field size, dimension, and interpolation degree, leaving arbitrary interpolation degrees unclassified.Earlier work also left the entire below-half range over extension fields unsettled.Source: A. Related Work · pp. 1–2, B. Main Result and Proof Outline · p. 2

B. Main Result and Proof Outline

  • For every prime power q and 3≤k≤⌊q/2⌋, a word is a deep hole if and only if its canonical representative has degree k.Together with known high-dimensional results, this proves the conjecture in all nonexceptional dimensions 3≤k≤q−2.Source: B. Main Result and Proof Outline · p. 2
  • The proof uses a marked arc and its tangent envelope to derive differential constraints, then uses compatible local syndromes and matching-graph counts in the remaining odd-characteristic range.The tangent-envelope constraints settle even characteristic and the odd-characteristic range q>3(k−1); matching counts address the remaining range when q≥41, with small fields handled separately.Source: B. Main Result and Proof Outline · p. 2

C. Organization

  • The paper proceeds from the arc reformulation through envelope identities and differential constraints, then develops local-syndrome, counting, and small-field arguments.The uniform matching estimate is proved in Appendix A.Source: C. Organization · p. 2

II. DEEP HOLES AND MARKED ARCS

  • A deep hole is equivalent to its associated marked set A_U being a (q+1)-arc in PG(k,q).The set consists of the points [1:x:…:x^(k−1):U(x)] for x in F, together with the marked point at infinity.Source: §II · p. 3

III. TANGENT-ENVELOPE IDENTITIES

The tangent-envelope theorem provides a homogeneous form whose restrictions to tangent pencils encode their tangent hyperplanes. The projection from the marked point determines the envelope’s boundary restriction, which the section identifies explicitly.

III. TANGENT-ENVELOPE IDENTITIES

  • A nonzero homogeneous form Φ on the dual projective space restricts on each tangent pencil to a product vanishing at its tangent hyperplanes, each with multiplicity ε.The theorem gives Φ degree ε(k−1).Source: A. Existence and boundary of the… · p. 4

A. Existence and boundary of the envelope

  • Projection of A_U from its marked point determines the boundary restriction Φ(g,0) of the envelope.The section normalizes this restriction using the product form B(g) on the stated range of the proposition.Source: A. Existence and boundary of the… · pp. 4–5
  • A homogeneous form of degree e in r+1 coefficients is determined by its values on the specified polynomials P_T when q≥e+r.The proof uses the forms L_T as a basis, extending identities from those polynomials to arbitrary polynomials of degree at most k−1.Source: A. Existence and boundary of the… · p. 5

B. The first transverse coefficient

The section computes the envelope’s first-order variation transverse to its boundary. Comparing this variation with the tangent-pencil identity yields a formula for the first transverse coefficient Φ1.

B. The first transverse coefficient

  • For each (k−1)-subset S, the quotient QS is injective on F\S because equal values at two outside points would contradict the deep-hole condition.The relevant overlapping extensions are therefore distinct; their omitted values enter the first-order tangent-pencil product.Source: B. The first transverse coefficient · p. 6
  • The section obtains first-order variations of the discriminant forms by perturbing the roots of PS, with separate expressions for even and odd characteristic.It tracks roots in F[η]/(η²), where η²=0.Source: B. The first transverse coefficient · pp. 7–8
  • The missing-value identity and boundary differentials determine Φ1 through a first-order comparison of the tangent-pencil identity.The comparison perturbs the interpolating polynomial at a fixed (k−1)-subset.Source: B. The first transverse coefficient · p. 9
  • The coefficient degree of Φ1 is at most k−2 in even characteristic and at most 2k−3 in odd characteristic.These bounds follow from the degree of the homogeneous envelope form.Source: B. The first transverse coefficient · p. 9

IV. DIFFERENTIAL RIGIDITY AND CLASSIFICATION

For k≥3, differential constraints derived from the envelope formula are used to classify deep holes in the stated characteristic ranges.

IV. DIFFERENTIAL RIGIDITY AND CLASSIFICATION

  • Fixing k−2 roots and varying the remaining root yields differential constraints whose kernels settle the classification in the relevant even- and odd-characteristic ranges.In characteristic two, the paper identifies W_P(U) with the ordinary derivative of P_U.Source: §IV · p. 10

A. Differential constraints on deep holes

The section derives differential constraints on a deep hole’s canonical representative, with separate identities in even and odd characteristic. Spanning arguments extend constraints from root polynomials to broader polynomial spaces.

A. Differential constraints on deep holes

  • A moving root yields a Wronskian term, while the fixed roots contribute a polynomial of degree at most 2k − 5.The resulting identities extend across the field in even characteristic, and after multiplication by P(x) in odd characteristic.Source: A. Differential constraints on deep… · pp. 10–11
  • The even-characteristic identity is equivalently an evaluation constraint on (P_B U)′, while the odd-characteristic identity constrains the evaluation vector derived from 2H U′ − H′ U.The identities are statements about evaluation vectors, not formal polynomial degrees.Source: A. Differential constraints on deep… · pp. 11–12
  • The spanning lemma uses a Vandermonde matrix and induction to show that powers of root polynomials span all polynomials up to the required degree.Its stated conditions include d < char F and q ≥ r + d.Source: A. Differential constraints on deep… · pp. 11–12
  • For q ≥ (ε + 1)(k − 1), the derived constraints extend to all H of degree ≤ k − 2 in even characteristic and ≤ 2k − 4 in odd characteristic.The extensions follow from the characteristic-specific identities and a spanning lemma for root polynomials.Source: A. Differential constraints on deep… · p. 12

B. Degree bounds and classification

The differential constraints bound the degree of deep-hole representatives and establish the classification in the stated even- and odd-characteristic ranges. The odd-characteristic degree constraints allow a possible degree-k+1 solution in characteristic three, which the proof rules out as a deep hole.

B. Degree bounds and classification

  • When q is even and q ≥ 2k, the solutions to the differential constraint are exactly the polynomials of degree at most k.The proof uses the constraints for H = 1 and H = X, then excludes degrees above k.Source: B. Degree bounds and classification · p. 12
  • For even q and 3 ≤ k ≤ q/2, a word is a deep hole of RS_q(k) exactly when its canonical representative has degree k.The proof combines Proposition 3 and Lemma 7 to bound the degree by k; representatives of lower degree are codewords.Source: B. Degree bounds and classification · p. 13
  • For odd q > 3(k − 1), solutions to the odd-characteristic constraint have degree at most k, except that degree k + 1 is also possible when char F = 3.The proof first bounds the degree by k + 1, then tests the degree-k+1 case directly.Source: B. Degree bounds and classification · p. 13
  • For odd q with 3 ≤ k ≤ (q − 1)/2 and q > 3(k − 1), a word is a deep hole exactly when its canonical representative has degree k.The proof rules out the possible degree-k+1 case in characteristic three using Li and Zhu’s formula [12, Theorem 1].Source: B. Degree bounds and classification · p. 13

V. LOCAL SYNDROMES AND TEMPLATE UNIQUENESS

For odd characteristic in the lower-half range, the section recasts the deep-hole condition using local syndromes on subsets of field elements. These syndromes are nonzero for deep holes and depend only on the representative’s coset modulo the code.

A. Local syndromes and the deep-hole condition

B. Existence and uniqueness of local templates

Local restrictions of a deep-hole representative are captured by polynomial or rational templates. The section gives a test for when a set admits a template and establishes uniqueness once templates agree on enough points.

B. Existence and uniqueness of local templates

  • A template is either a degree-k polynomial or a rational function with a linear denominator and a nonzero numerator coefficient.The rational form is defined away from its pole ζ and includes a polynomial of degree less than k.Source: B. Existence and uniqueness of local… · p. 15
  • A set W is good when a template defined on W agrees with U there; otherwise, it is bad.The text connects goodness to the stated local-syndrome condition.Source: B. Existence and uniqueness of local… · p. 15
  • The local syndrome of a deep hole matches neither the zero vector nor a projective class corresponding to a pole inside W.For the latter case, choosing T to contain that point contradicts the local-syndrome identity.Source: B. Existence and uniqueness of local… · p. 16
  • The two template types correspond to restrictions that are a nonzero multiple of X^k plus a lower-degree polynomial, or of (X − ζ)^−1 plus one.The rational-template pole ζ must lie outside W.Source: B. Existence and uniqueness of local… · pp. 15–16
  • Two distinct templates agree on at most k + 1 points of their common domain.Their reduced forms yield a nonzero polynomial of degree at most k + 1 whose roots include the agreement points.Source: B. Existence and uniqueness of local… · p. 16
  • Every (k + 2)-subset of F has a unique template agreeing with a deep-hole representative on that subset.Existence follows from the local-template result, and uniqueness from the bound on agreement between distinct templates.Source: B. Existence and uniqueness of local… · p. 16
  • Local syndromes on overlapping sets satisfy a deletion identity used to count failed template extensions.The identity is obtained by deleting z from W and comparing the corresponding syndrome expressions.Source: B. Existence and uniqueness of local… · p. 16

VI. QUADRATIC SYNDROMES AND COMPATIBILITY BOUNDS

Quadratic local syndromes turn bad subsets into independent sets in obstruction graphs, while compatibility across overlapping subsets bounds failed template extensions. Exact matching counts then help rule out nonexpected deep holes.

C. Compatibility and failed extensions

  • Distinct failed extensions from a fixed (k + 2)-subset yield distinct quadratic obstructions, allowing compatibility and counting to bound failures.The section combines this bound with counts of independent sets in the obstruction graphs.Source: §VI · p. 16, C. Compatibility and failed extensions · p. 18

A. Quadratic obstruction graphs

  • Each non-evaluation quadratic obstruction graph is a matching with either one or three isolated vertices.There are q(q + 1)/2 projective classes with one isolated vertex and q(q − 1)/2 with three.Source: A. Quadratic obstruction graphs · p. 17

B. Exact matching counts

  • For odd q, Q(q, w), the expected number of non-evaluation quadratic graphs in which a uniform w-subset is independent, is nonincreasing in w.The section defines Q using exact matching counts.Source: B. Exact matching counts · p. 17

D. Odd fields of order at least 41

For odd fields of order at least 41, matching-count bounds exclude nonexpected deep holes throughout the below-half dimension range. Separate arguments settle the remaining small odd extension fields.

D. Odd fields of order at least 41

  • Every deep hole has interpolation degree k for odd prime powers q ≥ 41 and 3 ≤ k ≤ (q − 1)/2.The proof uses Q(q, w0) < 9 at w0 = ⌈q/3⌉ + 3 to exclude nonexpected deep holes beyond the range covered by Theorem 4.Source: D. Odd fields of order at least 41 · pp. 18–19

VII. THE REMAINING SMALL-FIELD CASES

  • For RS27(10), every template agrees with the canonical representative U of any nonexpected deep hole on at most 13 points of its domain.Source: §VII · p. 19
  • For q ∈ {9, 25, 27} and 3 ≤ k ≤ (q − 1)/2, every deep hole has interpolation degree k.Theorem 4 covers k ≤ ⌈q/3⌉; separate arguments handle the remaining dimensions.Source: §VII · p. 20
  • For q = 9, the remaining case k = 4 follows because every 7-subset is good, forcing its template to agree with U throughout F9.The proof uses the independence-number bound for non-evaluation quadratic graphs.Source: §VII · p. 20

VIII. CONCLUSION

The paper classifies deep holes for full-length Reed–Solomon codes below half the field size and, with earlier high-dimensional results, proves the corrected Cheng–Murray conjecture. Its proof combines tangent-envelope differential constraints with local-syndrome compatibility and combinatorial counting.

VIII. CONCLUSION

  • The classification covers 3 ≤ k ≤ ⌊q/2⌋ over every finite field and, together with earlier high-dimensional classifications, proves the corrected Cheng–Murray conjecture.The conclusion notes independent work by Chen and Huang on the same conjecture.Source: §VIII · p. 21
  • The marked point determines a boundary section of the tangent envelope, whose first transverse coefficient constrains the interpolation polynomial.This is one of the two complementary uses of the full evaluation set described in the conclusion.Source: §VIII · p. 21
  • Beyond the differential-constraint range, overlapping local syndromes yield distinct quadratic obstructions for distinct failed template extensions, which exact matching counts exclude.A restricted sum–product argument handles the last small-field case.Source: §VIII · p. 21

APPENDIX A THE UNIFORM MATCHING ESTIMATE

Appendix A establishes a uniform bound on the matching-count expression used in the odd-field argument. Strict recurrence bounds across residue classes yield the estimate for all odd q ≥ 41.

APPENDIX A THE UNIFORM MATCHING ESTIMATE

  • The exact binomial expression for Q admits a uniform bound over the interval needed for the main argument.The appendix proves the bound using a recurrence in q.Source: Appendix A · p. 21
  • The recurrence bounds are strict in each of the three cases, with the appendix verifying that the corresponding ratios are below one.These bounds complete the proof of the uniform estimate.Source: Appendix A · p. 22
  • For every odd integer q ≥ 41, applying the three strict recurrence bounds to the corresponding residue classes modulo six proves the paper’s result labeled (39).Source: Appendix A · p. 22

Related papers

Loading 2610.31531v1…