PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep holes of full-length Reed--Solomon codes

Bocong Chen, Jing Huang

arXiv:2610.29429v1cs.ITmath.IT

TL;DR

The paper addresses whether noncanonical deep holes exist for full-length Reed–Solomon codes, a question connected to extensions of normal rational curves. It combines contraction and planar-arc arguments to classify them for q > 19683, with explicit exceptions in even characteristic.

  • Problem

    The paper asks whether full-length Reed–Solomon codes have deep holes beyond the canonical degree-k words, a question also linked to which points extend q points of a normal rational curve.

    Source: §1 · pp. 2–3

  • Method

    The proof uses contraction arguments across dimensions and planar arc completion to transfer geometric completion results to deep-hole classification.

    Source: §3 · p. 7

  • Results

    For q > 19683, odd-characteristic deep holes are exactly the degree-k words, while even characteristic has an additional family at k = q − 3 and an o-polynomial parametrization at k = 2.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The classification implies that every normal rational curve in the stated range is complete except when q is even and k ∈ {3, q − 1}.

    Source: §1 · p. 4

    The all-dimensional classification in parts (i)–(ii) is established only for q > 19683, and the paper does not explicitly classify the normalized o-polynomials.

    Source: §1 · p. 3

Abstract

from arXiv · show

For every prime power $q>19683$, we settle the Cheng--Murray deep-hole problem for full-length Reed--Solomon codes in every dimension $2\le k\le q-2$, with the characteristic-two cases stated explicitly. For odd $q$, the deep holes are precisely the words of degree $k$. For even $q$ and $k\ge3$, the same conclusion holds except for an additional family when $k=q-3$. In even characteristic and dimension two, every deep hole has a unique expression $a h(X)+bX+c$, where $a\ne0$ and $h$ is a normalized $o$-polynomial. The proof combines quadratic quotient algebras, graph-theoretic weighted independent-set inequalities, and planar arc completion. We also obtain normal rational curve rigidity in the corresponding nonexceptional dimensions, the projective Reed--Solomon covering radii, and distinct-coordinate solvability and remainder criteria.

1 Introduction

The paper classifies deep holes of full-length Reed–Solomon codes for q > 19683 across dimensions 2 ≤ k ≤ q − 2, resolving the odd-characteristic conjecture and specifying the even-characteristic exceptions. It also derives consequences for normal rational curves, projective covering radii, and polynomial solvability criteria.

1 Introduction

  • For odd q > 19683, the deep holes in every dimension 2 ≤ k ≤ q − 2 are precisely the words of degree k.For even q in those dimensions, the same classification holds for k ≥ 3 apart from the additional family u(X) = λX^(q−2) + f(X), where λ ≠ 0, deg f < q − 3, when k = q − 3.Source: §1 · pp. 1, 3
  • For even q ≥ 4 and k = 2, part (iii) gives an exact and unique parametrization of the deep holes by Oq.It does not provide an explicit list of the o-polynomials in Oq.Source: §1 · p. 3
  • The proof combines quadratic and quartic contractions, graph-based bounds, multiplicity estimates, and planar arc completion to cover the dimension ranges.Explicit inequalities make the geometric and analytic ranges overlap for q > 19683.Source: §1 · pp. 3–4
  • For q > 19683, a (q + 1)-arc containing q points of a normal rational curve equals that curve in odd characteristic and in most even-characteristic dimensions.For even q and k = 3, the extra point can instead be the missing point of the conic or its nucleus; k = q − 2 is also excluded from the rigidity statement.Source: §1 · p. 4
  • The projective Reed–Solomon covering radius is q + 1 − k for even q with k ∈ {2, q − 2}, and q − k otherwise.Equivalently, every normal rational curve in the stated range is complete except when q is even and k ∈ {3, q − 1}.Source: §1 · p. 4
  • The classification yields distinct-coordinate solvability and remainder criteria, with the even-characteristic exceptions at k = 2 and k = q − 3.The remainder criterion fails precisely for the exceptional families stated for those dimensions.Source: §1 · pp. 4–5

2 Preliminaries

The preliminaries set up polynomial and projective notation, then recall deep-hole criteria and arc-completion and graph bounds used in the classification.

Polynomial notation

  • The setup encodes a functional through its values on powers of X and organizes quartic functionals in a 3-by-3 matrix.The matrix H_a,b(M) has entries M(X^i+j), with 0 ≤ i ≤ a and 0 ≤ j ≤ b.Source: §2 · p. 5

Deep-hole and arc criteria

  • Kaipa’s characterization connects deep holes to an arc formed by adjoining the received word to the Reed–Solomon evaluation columns.The paper includes an interpolation proof to fix the functional normalization.Source: §2 · p. 5

Planar arc bounds

  • Planar arc-completion results give conic containment in odd characteristic and hyperoval completion in even characteristic.The recalled bounds include separate thresholds for square and nonsquare fields, and the even-characteristic hyperoval need not be regular.Source: §2 · p. 6
  • The preliminaries recall additional conic-containment bounds for odd nonsquare fields and a hyperoval-completion threshold for even fields.For even q, arcs larger than q − √q + 1 extend to a hyperoval; for nonsquare q ≥ 8, the threshold is q − √2q + 2.Source: §2 · p. 6

Graph bounds

  • The proof’s detector argument invokes a weighted independent-set inequality for graphs without isolated vertices.An isolated vertex contributes 1 + λ to the bound.Source: §2 · p. 6

3 Dimension two and contraction multiplicities

This section characterizes dimension-two deep holes in even characteristic by a unique normalized o-polynomial form and develops contraction methods for higher-dimensional arguments. Under the stated dimension bounds, it constructs many nonsingular quartic contractions surviving a small excluded set and controls their multiplicities through equivalence-class bounds and counts of distinct projective classes.

Dimension two

  • A graph with no three collinear points has a unique common missing slope, and its interpolation polynomial has derivative equal to that slope.Subtracting the slope gives a permutation, whose values at zero and one fix the remaining affine normalization.Source: §3 · p. 7
  • In even characteristic, every dimension-two deep hole has a unique form u(X) = a h(X) + bX + c, with a ≠ 0 and normalized o-polynomial h.The parameters are fixed by b = [X]u, c = u(0), and a = u(1) + b + c; these words have no odd-degree term other than possibly bX, and their number is q^2(q − 1)|O_q|.Source: §3 · p. 8

Kernel multiplicities

  • Omitting two points yields a singular quartic contraction exactly when their one-dimensional kernel classes agree; each equivalence class C of size m forces rank H2,m(M) ≤ 2.The kernel forms a common left-kernel vector for the Hankel matrix.Source: §3 · pp. 9–10
  • Under Lemma 3.5’s setup, quotient-algebra product counting rules out multiplicity classes larger than H_q, including in the additive characteristic-two case.A rank-deficient quadratic Hankel matrix yields a quadratic kernel form and a two-dimensional quotient algebra; in the characteristic-two additive case, the argument selects three distinct factors before finding a distinct pair.Source: §3 · pp. 10–11

Quartic contractions

  • If quartic contractions from omission sets differing in j = 1 or 2 points are projectively equal, their 3 × 3 Hankel matrix has rank at most j.Thus full-rank quartic contractions from such omission sets cannot be projectively equal.Source: §3 · p. 12

Dimension two and contraction multiplicities

  • For q ≥ 16 and 2 + ι_q ≤ k < floor((q − 1)/2), every noncanonical L satisfying (NV) yields a set D ⊆ Fq \ A of size t − 4 whose contraction has a nonsingular 3 × 3 Hankel matrix and survives A.Here t = q − k − 1 and |A| ≤ k + 2.Source: §3 · pp. 12–13
  • Lemma 3.4 establishes that selecting u1 and u2 from different equivalence classes yields subset U \ {u1, u2}, whose associated quartic contraction L(pU\{u1,u2} · ) produces a nonsingular 3 × 3 Hankel matrix.Source: §3 · p. 13
  • The construction produces Hq(n − Hq) pairwise distinct projective classes of contractions, with n = t − 2.The dimension bounds give Hq < n ≤ 2Hq, so the extremal class-size partition is {Hq, n − Hq}; projective equivalence between the resulting contractions would contradict nonsingularity.Source: §3 · p. 13

4 Involution detectors

The section turns quartic functionals into projective involutions, then uses graph bounds to construct detectors and propagate canonicality across dimensions.

4 Involution detectors

  • For a functional surviving T, its singular pairs are mutually disjoint, limiting their number to ⌊s/2⌋ and improving the usable-pair lower bound.Source: §4 · p. 14
  • A usable pair defines a nonscalar projective involution: its matrix squares to a scalar identity and has projective order two.Source: §4 · pp. 13–14
  • Each usable pair contributes a matching to the graph, whose degree and edge bounds feed an upper bound on its independent-set polynomial.Source: §4 · p. 15
  • A nonsingular functional surviving T has at least max{0, s −5 −δq} exterior points that nullify it with three anchor points.Source: §4 · p. 16
  • A detector for one dimension can be enlarged one point at a time, propagating canonicality through intermediate dimensions.Source: §4 · p. 16
  • A second-moment estimate bounds the projective classes of functionals surviving T, whether or not nonsingularity is required.Source: §4 · p. 17
  • If Ψ(q; s, r, M) < Qf(q, k0), every deep word is canonical for k0 ≤ k < ⌊(q −1)/2⌋.Source: §4 · p. 19

5 Planar projections and completion of the proof

This section classifies words from prescribed planar projections and uses projection-completion bounds, detector estimates, and two lemmas to complete the proof across the remaining dimensions. Conic completion applies in odd characteristic, while even characteristic also requires hyperoval completion and includes the prescribed exception.

5 Planar projections and completion of the proof

  • If a prescribed projection of a deep word lies on a conic, completion yields u = fE + pE v for quadratic v and forces u to be canonical.The projection arc has size q − k + 3; the interpolation polynomial fE records the values on E.Source: §5 · p. 20
  • In even characteristic, a hyperoval through [0 : 0 : 1] has affine part [1 : x : v(x)] with v′ constant, so v belongs to Wq.The hyperoval also contains [0 : 1 : α], with v′ ≡ α.Source: §5 · p. 20
  • For 3 ≤ k ≤ ⌊q/2⌋, if all projections indexed by a fixed (k − 1)-subset complete to conics or hyperovals, then the original deep word is canonical.The common projection constraints first give deg u ≤ k; deepness forces equality.Source: §5 · p. 21
  • Thinning a nonconic arc while retaining six nonconic points yields a smaller arc on a curve coprime to the specified curve, enabling a Bézout bound.Lemma 5.7 bounds the resulting arc size by s(σ + h) under its stated hypotheses.Source: §5 · pp. 21–22
  • The detector estimate proves canonical classification from k0 = ⌈4√q/5⌉ + 1 through ⌊(q − 1)/2⌋ − 1 for q ≥ 8192.For larger fields, the argument is stated to establish Theorem 1.1 for every prime power q ≥ 215 without finite-field searches or field-dependent scalar certificates.Source: §5 · pp. 23–25
  • Theorem 1.1 is completed by joining geometric bounds, detector estimates, the even-field dimension-two case, and a check of the remaining intermediate field orders.For q ≥ 32768, Lemma 5.11 supplies the classification; the proof then handles 19683 < q < 32768 separately.Source: §5 · pp. 24–25
  • The geometric range reaches ⌈4√q/5⌉; Lemma 5.10 and Lemma 2.2 then cover the remaining dimensions and prove the theorem, including its prescribed even-characteristic exception.Lemma 5.10 covers dimensions from ⌈4√q/5⌉+1 through ⌊(q−1)/2⌋−1, and Lemma 2.2 covers the upper range.Source: §5 · p. 26

A Proofs of the corollaries

The corollary proofs translate the deep-hole classification into results on normal rational curves, projective Reed–Solomon codes, and polynomial criteria. They use the syndrome correspondence, completeness, and polynomial agreement to establish these consequences.

Proof of Corollary 1.2

  • In the nonexceptional dimensions, a deep-hole syndrome identifies the added MDS point with the missing point of the normal rational curve; for even q and m = 3, the exceptional family gives the nucleus instead.The proof represents possible extra columns as syndromes and applies the deep-hole classification.Source: A Proofs of the corollaries · p. 26

Proof of Corollary 1.3

  • Completeness yields the stated projective Reed–Solomon covering radii, with the remaining boundary cases handled directly and the even-characteristic exceptions arising from MDS extensions.The proof uses duality and Dür’s criterion; adjoining the nucleus to a conic gives extensions in dimensions 3 and q − 1.Source: A Proofs of the corollaries · pp. 26–27

Polynomial criteria

  • The functional criterion converts deep-hole exclusion into finding a solution with distinct coordinates, and the proof obtains a k-set satisfying L(p_A) = 0.The exclusions in even characteristic correspond to d not being q − 3 or 2 in the dual code dimension.Source: A Proofs of the corollaries · p. 27
  • A remainder of degree less than k exists exactly when a polynomial of degree less than k agrees with u at k + 1 evaluation points; for deg u > k, Theorem 1.1 leaves precisely the stated exceptions.The proof expresses agreement on evaluation points through polynomial division.Source: A Proofs of the corollaries · p. 27

Related papers

Loading 2610.29429v1…