Source-linked AI summary
Deep holes of full-length Reed--Solomon codes: uniform bounds and exact classifications
Xiang Fan
TL;DR
The paper seeks an unconditional classification of deep holes for full-length Reed–Solomon codes, while earlier results addressed only specified degrees or imposed field-size conditions. It uses agreement-count estimates and permutation-polynomial restrictions to establish uniform bounds and exact classifications, including an unconditional classification for m = 3, . . . , 7.
Problem
An unconditional classification of deep holes remained open beyond results limited to specified values of m or subject to field-size conditions.
Source: §1 · p. 2Method
The paper derives a sufficient threshold from an agreement estimate and uses polynomial obstructions to restrict exceptional parameters.
Source: §3.1 · p. 5, §4 · p. 13Results
For m = 3, . . . , 7, odd m has no deep holes, while even-m exceptions are confined to the characteristic-two dimension-two families; for arbitrary m, the paper proves uniform exclusion and classification bounds.
Source: §1 · p. 1, §10 · p. 41Takeaways & Limitations
These classifications apply to prescribed interpolation degrees, and the dimension-two exceptions occur over fields of characteristic two.
Source: §1 · p. 1, §10 · p. 41The arguments do not classify arbitrary m or extend to arbitrary punctured or generalized evaluation sets.
Source: §10 · p. 42
Abstract
from arXiv · showhide
Let $u$ be a received word for the full-length Reed--Solomon code $\operatorname{RS}_q(k)$, with interpolation polynomial $f_u$ of degree $k+m$. For each $m\in\{3,4,5,6,7\}$, we classify all such deep holes over every finite field, without a field-size hypothesis. None occur for odd $m$ in this range. At $m=4$ and $m=6$, the only exceptions are, respectively, the Segre sextic and Frobenius-power families; these occur only in dimension two over fields of characteristic two. For arbitrary $m\geqslant3$, we also establish two uniform bounds. If $\sqrt q\geqslant12(m+1)\log(2m+2)$, no word of interpolation degree $k+m$ is a deep hole when $q$ is odd, $k\geqslant3$, or $m$ is odd. If $q>16(m+2)^4$, we obtain the corresponding complete classification at every admissible $k$, including the explicit dimension-two exceptions. Our proofs use an agreement criterion expressed in complete homogeneous symmetric functions, agreement-count estimates, finite geometry, permutation-polynomial restrictions, and subset constructions for solving the resulting symmetric-function equations. The remaining finite cases are settled by finite computations with supplied certificates and deterministic verification programs.
1. Introduction
The paper studies deep holes of full-length Reed–Solomon codes at specified interpolation degrees, giving uniform field-size bounds and exact classifications for m = 3,...,7. The classifications leave only explicit dimension-two exceptions in characteristic two for even m in that range.
Uniform exclusion
- If √q ≥ 12(m + 1) log(2m + 2), no such word is a deep hole when q is odd, k ≥ 3, or m is odd.The bound applies for m ≥ 3 and admissible k.Source: §1 · pp. 1–2
Uniform classification
- If q > 16(m + 2)^4, the deep holes are exactly those in the two stated families, for every admissible k.The exceptional families require q = 2^e and k = 2; the Segre family has m = 4 and odd e, while the Frobenius family has m = 2r − 2 and gcd(r,e) = 1.Source: §1 · p. 1
Main classification
- For 3 ≤ m ≤ 7, no deep holes occur for odd m; for even m, only the specified characteristic-two dimension-two families remain.The exceptions are the Segre sextic at m = 4 and the Frobenius-power family at m = 6.Source: §1 · pp. 1–2
Scope
- The unconditional classification concerns specified interpolation degrees, not all deep holes of a fixed code or arbitrary evaluation sets.The paper makes no classification claim for arbitrary m without a field-size condition.Source: §1 · pp. 2–3
Relation to prior work
- For m = 3,...,7, the results extend exact classification to every finite field, including fields below the threshold in Chen and Huang’s broader large-field result [CH26].The paper’s proof uses independent methods and does not use Chen and Huang’s results.Source: §1 · pp. 2–3
Proof strategy
- The proof combines a symmetric-function agreement criterion with agreement counts, finite geometry, permutation-polynomial restrictions, and subset constructions.The reductions leave finite cases settled by computations with certificates and deterministic verification programs.Source: §1 · pp. 2–3
2. An agreement criterion from polynomial remainders
Polynomial remainders turn the question of whether a received word is a deep hole into a condition on symmetric functions of a subset. The criterion asks whether some (k + 1)-subset makes a specific remainder coefficient vanish.
Remainder coefficients
- For a set S of size k + 1, the coefficient of X^k in the remainder of X^(k+j) modulo P_S is h_j(S).The recurrence from reducing powers by P_S matches the recurrence defining complete homogeneous symmetric functions.Source: §2 · p. 4
General criterion
- For an interpolation polynomial with leading part X^(k+m) + a_1X^(k+m−1) + ··· + a_mX^k, the coefficient is H_m,f(S) = h_m(S) + a_1h_(m−1)(S) + ··· + a_m.This follows by linearity from the monomial remainder-coefficient identity.Source: §2 · p. 4
Agreement condition
- The word is not a deep hole exactly when H_m,f(S) = 0 for some (k + 1)-subset S of F_q.Vanishing makes the remainder have degree below k, yielding a codeword that agrees on S.Source: §2 · p. 4
Example: m = 4
- For m = 4, the coefficient condition is h_4(S) + ah_3(S) + bh_2(S) + ch_1(S) + d = 0 for some such set S.The displayed form corresponds to a monic interpolation polynomial whose terms from X^(k+4) through X^k have coefficients 1,a,b,c,d.Source: §2 · p. 4
3. Uniform bounds and the case k = 2
This section proves uniform exclusions for deep holes using agreement counts in middle dimensions and geometric arguments in smaller dimensions, and gives a separate classification for k = 2. In that case, deep holes are excluded for odd q and for even q with odd m; when q = 2^e > 16(m + 2)^4, they are exactly those with interpolation polynomials in families (1.1) or (1.2).
3.1. Direct agreement counts from Gao–Li.
- For every characteristic, the Gao–Li count guarantees a codeword agreement when N ≤ k + 1 ≤ floor(q/2), under the stated field-size bound.A refinement extends the valid range down to n_ad ≤ k + 1 when its stated condition holds.Source: §3.1 · pp. 6, 8
3.2. Projection and the small dimensions.
- For small dimensions under the field-size bound, no deep holes occur for odd q with k ≥ 2 or even q with k ≥ 3.The odd-characteristic argument forces a large retained arc onto a conic and then contradicts the resulting polynomial identity; in characteristic two, a unique hyperoval extension yields an o-polynomial restriction that rules out the cases.Source: §3.2 · pp. 9–10
- Theorem 1.1(1)’s uniform exclusion follows by combining the high-dimensional classification, agreement counts, small-dimension results, and a separate exclusion for even q, k = 2, and odd m.The conclusion holds in every case asserted by the theorem; the k = 2 exclusion is independent of the field-size condition.Source: §3.2 · p. 10
3.3. The case k = 2.
- The k = 2 classification proposition begins with 3 ≤ m ≤ q − 3 and interpolation degree m + 2.The supplied passage states these hypotheses but does not include the proposition’s classification outcome.Source: §3.3 · p. 10
- For k = 2, no deep holes occur when q is odd or when q is even and m is odd; if q = 2^e > 16(m + 2)^4, deep holes are exactly the families (1.1) and (1.2).The classification includes converses; the families’ o-polynomial criteria are e odd for X^6 and gcd(r, e) = 1 for X^(2^r).Source: §3.3 · pp. 10–11
- For k = 2, deep-hole graph points together with the vertical point form an oval; in even order it extends to a hyperoval whose o-polynomial parity excludes odd m [CS15, Lemma 2.1].For large q, Caullery–Schmidt’s classification [CS15, Theorem 1.2] yields X^6 or X^(2^r), giving the two families after undoing normalization.Source: §3.3 · pp. 10–11
- Under the field-size bound of Theorem 1.1 (2), Theorem 1.1 (1) leaves only even q, k = 2, and even m, where Proposition 3.9 gives families (1.1) and (1.2).This supplies the corresponding complete classification at every admissible k under that bound.Source: §3.3 · p. 11
4. Permutation-polynomial obstructions in small dimensions
The section uses permutation-polynomial restrictions and collision counts to exclude deep holes in small dimensions under explicit hypotheses. It also gives prime-degree bounds on exceptional secant quotients and effective exclusions for m = 6, 7.
4. Permutation-polynomial obstructions in small dimensions
- A collision of a quotient G_T at two distinct points produces a (k+1)-point agreement set, linking quotient restrictions to deep-hole exclusion.The collision-counting argument counts each agreement set with a controlled multiplicity.Source: §4 · p. 12
- For m ≥ 3, no degree k+m deep hole exists when F_d(q), gcd(d,q−1)>1, and q>d(k−1)+1 hold, with d=m+1.The proof turns nonpermuting quotients into collisions that yield agreement sets.Source: §4 · p. 12
- For odd q, the gcd condition is automatic for odd m, covering m = 5 and 7 without degree-specific permutation-polynomial lists.The section gives an explicit sufficient field-size condition for odd m ≥ 7, but it does not improve known degree-specific classifications.Source: §4 · p. 12
- For odd prime d ≥ 5 with p ∤ d, at most three or four parameters v yield exceptional secant quotients, under the respective coefficient conditions.The three-parameter bound applies when p ∤ C_d; the four-parameter bound applies when p ∤ (d+1).Source: §4 · p. 13
- For d = 11, q ≥ 5204 gives an explicit exclusion for m = 10 when the stated k range and characteristic condition hold.The range is 2 ≤ k ≤ min{q−11, ⌈(q−1)/11⌉}, with characteristic different from 11.Source: §4 · p. 14
4.1. Two effective bounds for m = 6, 7.
- For odd q, degree k+m deep holes are excluded for m = 6 when q ≥ 512 and for m = 7 when q ≥ 1331.These large-field cases combine permutation-polynomial classifications with quotient-counting arguments; Section 9 handles the remaining cases.Source: §4.1 · p. 14
5. Odd-characteristic reductions and finite certificates
The section combines established classification ranges with exact coefficient bounds and finite certificates to cover odd-characteristic cases. Its finite certificates are exhaustively verified using exact finite-field arithmetic.
5. Odd-characteristic reductions and finite certificates
- The cited classification ranges exclude deep holes of interpolation degree k+m in the full-length setting for m ≥ 3.The ranges are attributed to Zhuang–Cheng–Li and Kaipa.Source: §5 · p. 15
- For m ∈ {3, 4, 5}, the middle range q/8 ≤ k+1 ≤ q/2 is covered when q ≥ Q_m.The section uses the bound from Lemma 3.1 in this range.Source: §5 · p. 15
- An exact integer majorant turns coefficient bounds into a sufficient condition for agreement at n = k+1 points.Its coefficient recurrence evaluates the bounds without floating-point arithmetic.Source: §5 · p. 15
- Finite certificates use stored subsets to cover normalized coefficient vectors or realize prescribed second elementary symmetric values, with exhaustive exact verification.The paper supplies the subsets and deterministic verification programs, independent of the searches used to discover them.Source: §5 · p. 15
6.1. Opposite pairs in odd characteristic.
Opposite-pair constructions produce agreement sets by controlling the complete homogeneous symmetric functions. A distinguished point can be combined with suitable opposite pairs to make the required function vanish.
6.1. Opposite pairs in odd characteristic.
- With a suitable α and distinct elements satisfying the stated relation, a distinguished point and opposite pairs give a (k+1)-subset S with H_f(S)=0.The opposite pairs are disjoint and avoid α; when k is odd, adjoining zero preserves h1, h2, and h3.Source: §6.1 · p. 16
- The construction gives h1(S)=α, h2(S)=α²+S0, and h3(S)=α³+αS0.The opposite-pair union itself has h1=h3=0 and h2=S0.Source: §6.1 · p. 16
- When b=c=0, choosing α=−a if a≠0 makes H_f vanish; if a=b=c=0, opposite pairs can be chosen to make h3=0.A zero may be added to obtain the required cardinality without changing h3.Source: §6.1 · p. 16
6.2. Residual fields in odd characteristic.
The section resolves the residual odd-characteristic cases for m=3 through constructions in the smallest fields and exact bounds in larger residual fields. These arguments complete the odd-characteristic exclusion for m=3.
6.2. Residual fields in odd characteristic.
- For q=49 and 81, the remaining cases are handled by the exact Gao–Li bound.The residual ranges are n=k+1=14,…,24 for q=49 and n=22,…,40 for q=81.Source: §6.2 · p. 16, §6.2.2 · p. 18
- For q=9 and k=3, the normalized polynomial case satisfies the agreement criterion after an affine change preserving four agreement points.The proposition treats f(X)=X^6+aX^5+bX^4+cX^3 over F9.Source: §6.2.1 · pp. 16–17
- For q=25, every target is a sum of an s-subset of D for s=3, 4, or 5; for q=27, this holds for s=3, 4, 5, or 6.These subset-sum results supply agreement sets in the residual k ranges.Source: §6.2.2 · pp. 17, 19
- For q=25 and 27, additive-character coefficient estimates feed the subset-sum conclusions through equation (6.2).The q=27 bounds are |e3|<8, |e4|≤9, |e5|<11, and |e6|≤15 before the every-target conclusion.Source: §6.2 · p. 16, §6.2.2 · p. 18
- The m=3 case has no deep holes in odd characteristic.The proof combines the external ranges, low-dimensional exclusions, exact bounds, and small-field constructions to cover every odd prime power.Source: §6.2.2 · pp. 18–19
6.3. Characteristic two: Artin–Schreier fibers.
This section constructs trace-zero symmetric-function solutions in characteristic two using Artin–Schreier pairs, trace selection, and subset sums. It covers middle dimensions and dimensions k ≤ 5 under stated field-size conditions, including constructions of three pairwise-disjoint blocks preserving H_f for k ≤ 5.
6.3. Characteristic two: Artin–Schreier fibers.
- In characteristic two, Artin–Schreier fibers are pairs {w, w + 1} that partition Fq, and the associated block quantity Pδ(t) is independent of the root choice.Common-difference block identities encode the symmetric functions through degree three using the sum of the block parameters.Source: §6.3 · p. 19
6.3.1. Exact subset sums in the trace hyperplane.
- In a trace hyperplane V of size N ≥ 16, every target is an r-subset sum for 3 ≤ r ≤ N − 3, or from V \ {0} for 3 ≤ r ≤ N − 4.With N ≥ 32, the same holds from V \ {0, τ} for 3 ≤ r ≤ N − 5; explicit positive counts handle smaller cases used in the constructions.Source: §6.3.1 · pp. 19, 21
6.3.2. Trace selection.
- For q = 2^e ≥ 16, trace-selection lemmas provide trace-zero targets for odd R, including the exceptional a = 0 case via η ∉ F2 and δ ≠ 0.The exceptional construction uses R − 1 common-difference blocks together with singleton points 0 and ηδ.Source: §6.3.2 · p. 22
6.3.3. The middle dimensions.
- For even q ≥ 16 and 6 ≤ k < q/2, a (k + 1)-subset S ⊆ Fq exists with Hf(S) = 0.The construction combines common-difference blocks and, in some cases, singleton points; trace selection fixes a target sum, and subset-sum results supply the block parameters.Source: §6.3.3 · p. 23
6.3.4. The dimensions k ⩽5.
- For even q ≥ 8, the k = 2 case has a three-set with Hf(S) = 0; for q ≥ 16, k = 3 and 5 are solved, and k = 4 is solved for q ≥ 32 and q = 16.The k = 3, 4, and 5 constructions use Artin–Schreier pairs, sometimes with an added singleton.Source: §6.3.4 · pp. 23–24
- With |V| ≥ 8, choose t3 outside the at most four parameters whose pair partitions meet either of the first two disjoint pairs, yielding three disjoint blocks without changing H_f.The partitions pair points with difference λδ.Source: §6.3.4 · p. 25
6.4. Completion of the case m = 3.
The even-characteristic case for m=3 is established by constructing agreement sets across the admissible dimensions, completing the result together with the odd-characteristic case.
6.4. Completion of the case m = 3.
- Theorem 6.16 establishes the m=3 case in even characteristic.The proof constructs a (k + 1)-subset with Hf(S)=0, yielding the agreement criterion.Source: §6.4 · p. 26
- For q=8, q=16, and q≥32, small-k lemmas, Proposition 6.11, and Kaipa’s range cover the admissible dimensions.Each construction supplies a (k + 1)-subset with Hf(S)=0; the Kaipa range gives the same conclusion directly.Source: §6.4 · p. 26
- Theorems 6.5 and 6.16 together complete the m=3 result in odd and even characteristic.The odd- and even-characteristic cases are covered separately.Source: §6.4 · p. 26
7. Exact classification when m = 4
For interpolation degree k+4, the paper excludes deep holes in odd characteristic and classifies the characteristic-two cases, including the dimension-two exception.
7.1. Odd characteristic.
- For odd q≥11 with q>5k−4, a value-set bound forces the relevant quotient quintics to permute Fq, excluding deep holes.The low-dimensional exclusion applies for 2≤k≤q−5.Source: §7.1 · p. 26
- No received word of interpolation degree k+4 is a deep hole in odd characteristic for 2≤k≤q−5.The result holds for every odd prime power in the stated range.Source: §7.1 · p. 27
7.2.1. The dimension-two exception and quintic permutations.
- For q = 2^e ≥ 8, 3 ≤ k ≤ q − 5, and q > 5k − 4, no word of interpolation degree k + 4 is a deep hole.Source: §7.2.1 · p. 29
7.2.2. Two-point fibers and prescribed values of symmetric functions.
- If trace-hyperplane subsets can hold h1 fixed while attaining every h2 value, the resulting two-point fibers exclude deep holes for k=2r−1 or 2r.The subset condition supplies a set whose remainder equation vanishes for each coefficient choice.Source: §7.2.2 · p. 29
7.2.3. Affine planes, eight-point affine subspaces, and a Kloosterman bound.
- Affine planes represent quadratic-form values, while disjoint eight-point subspaces preserve h1 and h2, yielding the fixed-sum, arbitrary-h2 subset condition in the stated large-field ranges.The ranges are even e≥8 with 4≤r≤q/4−1, and odd e≥9 with 8≤r≤q/4−1.Source: §7.2.3 · p. 30
7.2. Characteristic two: the Segre exception.
- In characteristic two, degree k+4 deep holes occur exactly when k=2, e is odd, and the normalized coefficients satisfy a=c=0 and d=b^2.The dimension-two exception is the Segre sextic family; the classification does not cover all o-polynomials or unrestricted degrees.Source: §7.2.1 · p. 28, §7.2.4 · p. 31
7.2.4. The remaining fields of characteristic two.
- Finite certificates cover the remaining characteristic-two cases, completing the classification for every q=2^e and admissible k.The certificates verify constructed subsets or normalized coefficient classes, including the remaining cases at q=64 and q=128.Source: §7.2.4 · p. 31
8. Exact exclusion when m = 5
For m = 5, the paper excludes deep holes at every admissible dimension over every finite field. Odd and characteristic-two fields require distinct arguments, with finite certificates resolving remaining cases.
8. Exact exclusion when m = 5
- For every finite field and 2 ≤ k ≤ q − 6, no received word of interpolation degree k + 5 is a deep hole.The odd- and characteristic-two cases together establish the exact result.Source: §8 · p. 31, §8.1 · p. 32, §8.2 · p. 34
8.1. Odd characteristic: the remaining small fields.
- For odd q < 289, certificates cover residual parameter pairs after the low-range lemma and integer comparisons reduce the cases.The certificates cover 18 pairs for q = 9, 25, 27 and 44 further pairs for q = 49, 81, 121, 125.Source: §8.1 · p. 32
- In odd characteristic, paired elements and an added singleton or pair let the proof vary h2 while fixing the sum to solve the remainder equation.For the constructed sets, Hf(S) = D(z) + (z + a1)β.Source: §8.1 · p. 32
- Over odd fields, the proof combines dimension ranges, permutation-polynomial restrictions, and certificates for the remaining small cases.The small-field certificates check normalized coefficient vectors and prescribed symmetric-function values.Source: §8.1 · pp. 32–33
8.2. Characteristic two: symmetric functions of fibers and affine subspaces.
- In characteristic two, affine subspaces and trace-fiber pairs construct subsets with fixed sums and arbitrary h2 values, solving the remainder equation.The construction handles middle dimensions; planar projections and high-dimensional results cover other ranges.Source: §8.2 · pp. 33–34
- Finite certificates cover the residual characteristic-two cases, checking normalized coefficient classes and required symmetric-function values exhaustively.For q = 16 and 32, certificates check 589 and 3633 stored sets, respectively; certificates also cover residual dimensions for q = 64 and 128.Source: §8.2 · p. 34
9. Exact classifications for m = 6, 7
This section classifies the m = 6 and m = 7 cases over every finite field. It identifies a characteristic-two, dimension-two exception for m = 6, while the m = 7 classification rules out deep holes of interpolation degree k + 7, with paired-point constructions and finite verification covering the remaining cases.
9.2. The case m = 7: classification over all finite fields.
- For m = 7, paired-point constructions reduce exclusion to realizing every value of h3(T) + Ah2(T) + Bh1(T), with eight small cases checked directly.Adjoining a point to paired subsets handles cases where removing a parameter preserves the required condition; three-point multiplicative orbits provide further constructions.Source: §9 · p. 34, §9.2 · pp. 37–38
9.1. The case m = 6.
- In characteristic two, a small-dimension exclusion rules out degree k + m deep holes when h^2 < q and q > dh + 1, for h = k − 1 and d = m + 1.The lemma assumes m ≥ 3 and 3 ≤ k ≤ q − m − 1.Source: §9.1 · p. 35
- For m = 6, uniform and dimension-specific exclusions leave 265 parameter pairs for exact verification: 149 in odd characteristic and 116 in characteristic two.Subset certificates cover 147 odd-characteristic pairs and 103 characteristic-two pairs; the remaining cases receive exhaustive coefficient checks, with reproducible programs and certificates supplied.Source: §9.1 · pp. 35–37
- For m = 6, the only deep holes have q = 2^e, k = 2, 3 ∤ e, and interpolation polynomial AX^8 + BX + C with A ≠ 0.Conversely, this family has no collinear triple exactly when X^7 permutes F_q, equivalent to 3 ∤ e.Source: §9.1 · pp. 35, 37
9.2. The case m = 7: classification over all finite fields.
- For m = 7, the general exclusions leave 375 parameter pairs, and paired-point arguments cover 242 of them.Certificates on square subsets cover 18 more pairs for q = 169 and the pair (49, 7).Source: §9.2 · pp. 38–39
- Three-point multiplicative-orbit identities cover 81 of the 114 remaining m = 7 pairs, including 39 pairs for q = 169 and 42 for q = 256.The orbit construction varies h3(T) across every field value while keeping h1(T) and h2(T) fixed.Source: §9.2 · p. 39
- For m = 7, received words are not deep holes for the remaining 15 pairs with q = 243, nine pairs with q in {64, 81, 121, 125, 128}, and (q, k) = (256, 17).Source: §9.2 · p. 40
- For q = 16, 27, and 32, exhaustive coefficient verification establishes that the received words are not deep holes for the stated k values.The verifier checks 9,115,498 normalized choices of intermediate coefficients and confirms that all resulting a7 values are covered.Source: §9.2 · p. 41
- All 375 parameter pairs requiring separate treatment are covered, completing the result that degree k + 7 received words are not deep holes.The five disjoint collections exhaust the pairs identified by Lemma 9.8, and the finite verifiers check the required targets or normalized coefficient classes.Source: §9.2 · p. 41
10. Consequences, limitations, and reproducibility
The paper states the scope of its classifications and explains how its computer-assisted finite cases can be reproduced. The results do not cover arbitrary m or arbitrary evaluation sets.
10. Consequences, limitations, and reproducibility
- For m = 3, . . . , 7, odd m has no deep holes, while the only even-m exceptions are specified characteristic-two dimension-two polynomials.These conclusions apply to the stated interpolation degrees.Source: §10 · p. 41
- The arguments do not classify arbitrary m or arbitrary punctured or generalized evaluation sets.For m = 8, the pair construction requires h4, which current certificates using h1, h2, and h3 do not provide.Source: §10 · p. 42
Computational reproducibility.
- The finite parts of the classifications are computer-assisted, with exhaustive checks of stored subsets and normalized coefficient vectors.The verifiers check the required symmetric-function values and identities independently of randomness used to find the subsets.Source: Computational reproducibility · p. 42
- The supplied verification programs reproduce the finite checks using explicit field models, point-set arrays, manifests, and source code.The default verification command requires Python 3.10 or later, NumPy, and a C++17 compiler.Source: Computational reproducibility · p. 42