Introduction
Let F q \mathbb{F}_q F q denote the finite field of order q q q , where q q q is a prime power. For a word u ∈ F q n u\in\mathbb{F}_q^n u ∈ F q n and a linear code C ⊆ F q n C\subseteq\mathbb{F}_q^n C ⊆ F q n , the distance from u u u to C C C is defined by
d ( u , C ) = min c ∈ C d H ( u , c ) . d(u,C)=\min_{c\in C}d_H(u,c). d ( u , C ) = c ∈ C min d H ( u , c ) .
where the Hamming distance d H d_H d H counts the coordinates in which its two arguments differ. The covering radius of C C C is
ρ ( C ) = max u ∈ F q n d ( u , C ) . \rho(C)=\max_{u\in\mathbb{F}_q^n}d(u,C). ρ ( C ) = u ∈ F q n max d ( u , C ) .
A word u u u satisfying d ( u , C ) = ρ ( C ) d(u,C)=\rho(C) d ( u , C ) = ρ ( C ) is called a deep hole of C C C . Thus deep holes are the words farthest from C C C .
For 1 ≤ k < q 1\le k<q 1 ≤ k < q , the full-length Reed–Solomon code over F q \mathbb{F}_q F q is defined as
RS q ( k ) = { ( f ( x ) ) x ∈ F q : f ∈ F q [ X ] , deg f < k } . \operatorname{RS}_q(k)=\{(f(x))_{x\in\mathbb{F}_q}:f\in\mathbb{F}_q[X],\ \deg f<k\}. RS q ( k ) = {( f ( x ) ) x ∈ F q : f ∈ F q [ X ] , deg f < k } .
Every word u = ( u x ) x ∈ F q ∈ F q q u=(u_x)_{x\in\mathbb{F}_q}\in\mathbb{F}_q^q u = ( u x ) x ∈ F q ∈ F q q has a unique interpolation polynomial U ∈ F q [ X ] U\in\mathbb{F}_q[X] U ∈ F q [ X ] of degree less than q q q such that U ( x ) = u x U(x)=u_x U ( x ) = u x for all x ∈ F q x\in\mathbb{F}_q x ∈ F q . We call U U U the canonical representative of u u u . For k ≤ deg U < q k\leq\deg U<q k ≤ 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. q − deg U ≤ d ( u , RS q ( k )) ≤ q − k .
The lower bound follows from the root bound for U − f U-f U − f , and the upper bound from interpolation on any k k k coordinates. Consequently, ρ ( RS q ( k ) ) = q − k \rho(\operatorname{RS}_q(k))=q-k ρ ( RS q ( k )) = q − k , and every word with deg U = k \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) 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 − 2 3\leq k\leq q-2 3 ≤ k ≤ q − 2 , excluding the case where q q q is even and k = q − 3 k=q-3 k = q − 3 . A word u ∈ F q q u\in\mathbb{F}_q^q u ∈ F q q is a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) if and only if its canonical representative has degree k k k .
Equivalently, under the hypotheses of Conjecture 1.1, every polynomial U U U with k < deg U < q k<\deg U<q k < deg U < q agrees with some polynomial of degree less than k k k at k + 1 k+1 k + 1 distinct field elements. In the excluded even-characteristic case k = q − 3 k=q-3 k = q − 3 , the additional deep holes are represented by a X q − 2 + f ( X ) aX^{q-2}+f(X) a X q − 2 + f ( X ) , where a ∈ F q × a\in\mathbb{F}_q^\times a ∈ F q × and deg f < q − 3 \deg f<q-3 deg f < q − 3 [10 Theorem 1] .
For k = 2 k=2 k = 2 , the classification holds when q q q 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 + d k+d k + d , where d ≥ 1 d\geq1 d ≥ 1 . 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 = 1 d=1 d = 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 − 2 2\leq k\leq q-2 2 ≤ k ≤ q − 2 , the degree-( k + 1 ) (k+1) ( k + 1 ) deep holes are completely classified: none occur in odd characteristic, while in even characteristic they occur precisely when k = q − 3 k=q-3 k = q − 3 and the coefficient of X k X^k X k vanishes [14 Theorem 1] . For d = 2 d=2 d = 2 , Zhang, Fu, and Liao [19 ] constructed deep holes for proper evaluation sets and excluded degree-( k + 2 ) (k+2) ( k + 2 ) deep holes of full-length codes in odd characteristic when q > 5 q>5 q > 5 and 2 ≤ k ≤ q − 3 2\leq k\leq q-3 2 ≤ k ≤ q − 3 . Li and Zhu [14 ] subsequently determined the exact error distances of degree-( k + 1 ) (k+1) ( k + 1 ) words and obtained exact distances or upper bounds for degree-( k + 2 ) (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 p p p when k + 1 ≤ p k+1\leq p k + 1 ≤ p or 3 ≤ q − p + 1 ≤ k + 1 ≤ q − 2 3\leq q-p+1\leq k+1\leq q-2 3 ≤ q − p + 1 ≤ k + 1 ≤ 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 k ≥ ⌊( q − 1 ) /2 ⌋ , 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 3 ≤ k ≤ ⌊ q /2 ⌋ over extension fields. Our main theorem fills this gap.
Theorem 1.2. Let q q q be a prime power and 3 ≤ k ≤ ⌊ q / 2 ⌋ 3 \le k \le\lfloor q/2\rfloor 3 ≤ k ≤ ⌊ q /2 ⌋ . A word u ∈ F q q u \in\mathbb{F}_q^q u ∈ F q q is a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) if and only if its canonical representative U U U has degree k k k .
Together with the known classification for k ≥ ⌊ ( q − 1 ) / 2 ⌋ k \ge\lfloor(q-1)/2\rfloor k ≥ ⌊( q − 1 ) /2 ⌋ , 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 U U U be the canonical representative of a deep hole, and associate with it the marked set
A U = { [ 1 : x : ⋯ : x k − 1 : U ( x ) ] : x ∈ F q } ∪ { [ 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). A U = {[ 1 : x : ⋯ : x k − 1 : U ( x )] : x ∈ F q } ∪ {[ 0 : ⋯ : 0 : 1 ]} ⊆ PG ( k , q ) .
Here PG ( k , q ) \operatorname{PG}(k,q) PG ( k , q ) is the k k k -dimensional projective space over F q \mathbb{F}_q F q , and the last point is the marked point. The deep-hole condition is equivalent to A U \mathcal{A}_U A U being a ( q + 1 ) (q+1) ( q + 1 ) -arc, meaning that every k + 1 k+1 k + 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 U U U . These constraints establish the conjecture for 3 ≤ k ≤ q / 2 3 \le k \le q/2 3 ≤ k ≤ q /2 in even characteristic and q > 3 ( k − 1 ) q > 3(k-1) q > 3 ( k − 1 ) in odd characteristic, using the known error-distance result for degree-( k + 1 ) (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) ( k + 2 ) -subset of F q \mathbb{F}_q F q admits a unique template agreeing with U U U , either a degree-k k k polynomial or a rational function f ( X ) + c / ( X − ζ ) f(X) + c/(X-\zeta) f ( X ) + c / ( X − ζ ) with deg f < k \deg f < k deg f < k , c ∈ F q × c \in\mathbb{F}_q^{\times} c ∈ F q × , and ζ ∈ F q \zeta\in\mathbb{F}_q ζ ∈ 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) ( 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 ≥ 41 q \ge41 q ≥ 41 . The remaining odd proper extension fields q ∈ { 9 , 25 , 27 } q \in\{9,25,27\} q ∈ { 9 , 25 , 27 } are handled by elementary matching and counting arguments, together with a restricted sum–product lemma over F 27 \mathbb{F}_{27} 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 > 19683 q > 19683 q > 19683 and 3 ≤ k ≤ q − 2 3 \le k \le q - 2 3 ≤ k ≤ q − 2 , including the known even-characteristic exception. They also parametrize the dimension-two deep holes in even characteristic by normalized o o o -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 deg U = k + m , where m ≥ 3 m \ge3 m ≥ 3 . For 3 ≤ m ≤ 7 3 \le m \le7 3 ≤ m ≤ 7 , he classifies all such deep holes over every finite field, including the exceptional dimension-two families in even characteristic. For arbitrary m ≥ 3 m \ge3 m ≥ 3 , he excludes degree-( k + m ) (k+m) ( k + m ) deep holes when k ≥ 3 k \ge3 k ≥ 3 and q ≥ 12 ( m + 1 ) log ( 2 m + 2 ) \sqrt{q} \ge12(m+1)\log(2m+2) q ≥ 12 ( m + 1 ) log ( 2 m + 2 ) , and obtains a complete classification when q > 16 ( m + 2 ) 4 q > 16(m+2)^4 q > 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 > 19683 q > 19683 q > 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 q q q and every 3 ≤ k ≤ ⌊ q / 2 ⌋ 3 \le k \le\lfloor q/2\rfloor 3 ≤ k ≤ ⌊ q /2 ⌋ , 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) q > 3 ( k − 1 ) . § 5 establishes the existence and uniqueness of local templates, while § 6 uses quadratic obstructions to settle odd q ≥ 41 q \ge41 q ≥ 41 . § 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 m m m , let F q [ X ] ≤ m \mathbb{F}_q[X]_{\le m} F q [ X ] ≤ m denote the space of polynomials over F q \mathbb{F}_q F q of degree at most m m m . We write [ X j ] H [X^j]H [ X j ] H for the coefficient of X j X^j X j in H H H , and ( S r ) \binom{S}{r} ( r S ) for the family of r r r -subsets of a finite set S S S . For F ∈ F q [ X ] F \in\mathbb{F}_q[X] F ∈ F q [ X ] , write
ev ( F ) = ( F ( x ) ) x ∈ F q . \operatorname{ev}(F) = (F(x))_{x \in\mathbb{F}_q}. ev ( F ) = ( F ( x ) ) x ∈ F q .
For any S ⊆ F q S \subseteq\mathbb{F}_q S ⊆ F q , put
P S ( X ) = ∏ a ∈ S ( X − a ) , P ∅ ( X ) = 1. P_S(X) = \prod_{a \in S}(X-a), \qquad P_{\varnothing}(X) = 1. P S ( X ) = a ∈ S ∏ ( X − a ) , P ∅ ( X ) = 1.
For nonempty S S S and deg H < ∣ S ∣ \deg H < |S| deg H < ∣ S ∣ , Lagrange interpolation takes the form
H ( X ) = ∑ a ∈ S H ( a ) P S ( X ) ( X − a ) P S ′ ( a ) . H(X) = \sum_{a \in S} H(a)\frac{P_S(X)}{(X-a)P'_S(a)}. H ( X ) = a ∈ S ∑ H ( a ) ( X − a ) P S ′ ( a ) P S ( X ) .
Comparing the coefficients of X ∣ S ∣ − 1 X^{|S|-1} X ∣ S ∣ − 1 , we obtain
∑ a ∈ S H ( a ) P S ′ ( 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)} a ∈ S ∑ P S ′ ( a ) H ( a ) = [ X ∣ S ∣ − 1 ] H ( deg H < ∣ S ∣ ) . (1)
Since ρ ( RS q ( k ) ) = q − k \rho(\operatorname{RS}_q(k))=q-k ρ ( RS q ( k )) = q − k , a vector with canonical representative U U U is a deep hole precisely when no polynomial of degree less than k k k agrees with U U U at k + 1 k+1 k + 1 distinct elements of F q \mathbb{F}_q F q . Equivalently,
∣ { x ∈ F q : U ( x ) = f ( x ) } ∣ ≤ k for every f ∈ F q [ X ] , deg f < k . (2) \left|\{x\in\mathbb{F}_q:U(x)=f(x)\}\right|\leq k\qquad\text{for every }f\in\mathbb{F}_q[X],\ \deg f<k. \tag*{(2)} ∣ { x ∈ F q : U ( x ) = f ( x )} ∣ ≤ k for every f ∈ F q [ X ] , deg f < k . (2)
Associate with U U U the set
A U = { [ 1 : x : ⋯ : x k − 1 : U ( x ) ] : x ∈ F q } ∪ { P ∞ } ⊆ PG ( k , q ) , \mathcal{A}_U=\{[1:x:\cdots:x^{k-1}:U(x)]:x\in\mathbb{F}_q\}\cup\{P_\infty\}\subseteq\operatorname{PG}(k,q), A U = {[ 1 : x : ⋯ : x k − 1 : U ( x )] : x ∈ F q } ∪ { P ∞ } ⊆ PG ( k , q ) ,
where
P ∞ = [ 0 : ⋯ : 0 : 1 ] P_\infty=[0:\cdots:0:1] P ∞ = [ 0 : ⋯ : 0 : 1 ]
is the marked point . Recall that a set in PG ( k , q ) \operatorname{PG}(k,q) PG ( k , q ) is an arc if every k + 1 k+1 k + 1 of its points are projectively independent.
A hyperplane in PG ( k , q ) \operatorname{PG}(k,q) PG ( k , q ) has an equation
∑ i = 0 k − 1 a i Y i + z Y k = 0. \sum_{i=0}^{k-1}a_iY_i+zY_k=0. i = 0 ∑ k − 1 a i Y i + z Y k = 0.
Identify its dual coordinates with ( g , z ) (g,z) ( g , z ) , up to simultaneous nonzero scaling, where g ( X ) = ∑ i = 0 k − 1 a i X i g(X)=\sum_{i=0}^{k-1}a_iX^i g ( X ) = ∑ i = 0 k − 1 a i X i . It contains the finite point [ 1 : x : ⋯ : x k − 1 : U ( x ) ] [1:x:\cdots:x^{k-1}:U(x)] [ 1 : x : ⋯ : x k − 1 : U ( x )] if and only if g ( x ) + z U ( x ) = 0 g(x)+zU(x)=0 g ( x ) + z U ( x ) = 0 , and contains P ∞ P_\infty P ∞ if and only if z = 0 z=0 z = 0 .
When evaluating a form in the coefficients of a polynomial, we identify that polynomial with its coefficient vector. Thus, for a form F F F in a 0 , … , a r a_0,\ldots,a_r a 0 , … , a r and g ( X ) = ∑ i = 0 r a i X i g(X)=\sum_{i=0}^{r}a_iX^i g ( X ) = ∑ i = 0 r a i X i , we write F ( g ) = F ( a 0 , … , a r ) F(g)=F(a_0,\ldots,a_r) F ( g ) = F ( a 0 , … , a r ) . For a form Φ \Phi Φ in a 0 , … , a k − 1 , z a_0,\ldots,a_{k-1},z a 0 , … , a k − 1 , z , we similarly write Φ ( g , z ) = Φ ( a 0 , … , a k − 1 , z ) \Phi(g,z)=\Phi(a_0,\ldots,a_{k-1},z) Φ ( g , z ) = Φ ( a 0 , … , a k − 1 , z ) . This convention will also be used for the discriminant forms and their coefficient derivatives.
The following connection between deep holes and arcs is standard; see, for example, [18 , 10 ] .
Lemma 2.1. A vector u ∈ F q q u\in\mathbb{F}_q^q u ∈ F q q with canonical representative U U U is a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) if and only if A U \mathcal{A}_U A U is a ( q + 1 ) (q+1) ( q + 1 ) -arc in PG ( k , q ) \operatorname{PG}(k,q) PG ( k , q ) .
Proof. A set of k + 1 k+1 k + 1 finite points of A U \mathcal{A}_U A U is contained in a hyperplane precisely when
g ( x ) + z U ( x ) = 0 g(x)+zU(x)=0 g ( x ) + z U ( x ) = 0
holds at their k + 1 k+1 k + 1 distinct parameters for some deg g ≤ k − 1 \deg g\leq k-1 deg g ≤ k − 1 and ( g , z ) ≠ ( 0 , 0 ) (g,z)\ne(0,0) ( g , z ) = ( 0 , 0 ) . Necessarily z ≠ 0 z\ne0 z = 0 , since otherwise a nonzero polynomial of degree at most k − 1 k-1 k − 1 would have k + 1 k+1 k + 1 roots. Thus U U U agrees at these points with the polynomial − g / z -g/z − g / z of degree less than k k k , and (2) establishes the equivalence for finite subsets. If one of the k + 1 k+1 k + 1 points is P ∞ P_\infty P ∞ , expansion along its coordinate leaves a Vandermonde determinant on the remaining k k k distinct field elements, which is nonzero.
The original Cheng–Murray conjecture also included k = 2 k=2 k = 2 , but its predicted degree-two classification is false in even characteristic. Indeed, let q = 2 m q=2^m q = 2 m , m ≥ 3 m\geq3 m ≥ 3 , and set U ( X ) = X 2 m − 1 U(X)=X^{2^m-1} U ( X ) = X 2 m − 1 . For fixed x ∈ F q x\in\mathbb{F}_q x ∈ F q and y ≠ x y\ne x y = x ,
U ( y ) − U ( x ) y − x = ( y − x ) 2 m − 1 − 1 . \frac{U(y)-U(x)}{y-x}=(y-x)^{2^m-1-1}. y − x U ( y ) − U ( x ) = ( y − x ) 2 m − 1 − 1 .
Since gcd ( 2 m − 1 − 1 , 2 m − 1 ) = 1 \gcd(2^m-1-1,2^m-1)=1 g cd( 2 m − 1 − 1 , 2 m − 1 ) = 1 , these q − 1 q-1 q − 1 slopes are distinct. Thus no three finite points of A U \mathcal{A}_U A U are collinear; moreover, any line through P ∞ P_\infty P ∞ contains at most one finite point of A U \mathcal{A}_U A U . By Lemma 2.1, ev ( U ) \operatorname{ev}(U) ev ( U ) is a deep hole of RS q ( 2 ) \operatorname{RS}_q(2) RS q ( 2 ) although deg U > 2 \deg U>2 deg U > 2 .
Henceforth suppose k ≥ 3 k \ge3 k ≥ 3 and that U U U represents a deep hole. Let S ⊆ A U S \subseteq\mathcal{A}_U S ⊆ A U have size k − 1 k-1 k − 1 . Its points are projectively independent and span a ( k − 2 ) (k-2) ( k − 2 ) -dimensional subspace ⟨ S ⟩ ⊆ PG ( k , q ) \langle S\rangle\subseteq\operatorname{PG}(k,q) ⟨ S ⟩ ⊆ PG ( k , q ) . The hyperplanes containing ⟨ S ⟩ \langle S\rangle ⟨ S ⟩ form a pencil, naturally identified with a projective line in the dual space PG ( k , q ) ∨ \operatorname{PG}(k,q)^\vee PG ( k , q ) ∨ .
For each point P ∈ A U ∖ S P \in\mathcal{A}_U \setminus S P ∈ A U ∖ S , the span ⟨ S ∪ { P } ⟩ \langle S \cup\{P\}\rangle ⟨ S ∪ { P }⟩ is a hyperplane belonging to this pencil. Moreover, distinct points of A U ∖ S \mathcal{A}_U \setminus S A U ∖ S determine distinct hyperplanes: otherwise a single hyperplane would contain S S S together with two further points of A U \mathcal{A}_U A U , hence k + 1 k+1 k + 1 points of the arc, a contradiction. Thus exactly
∣ A U ∖ S ∣ = ( q + 1 ) − ( k − 1 ) = q − k + 2 \lvert\mathcal{A}_U \setminus S\rvert= (q+1)-(k-1)=q-k+2 ∣ A U ∖ S ∣ = ( q + 1 ) − ( k − 1 ) = q − k + 2
members of the pencil contain an additional point of A U \mathcal{A}_U A U .
Since a pencil contains q + 1 q+1 q + 1 hyperplanes, the remaining
( q + 1 ) − ( q − k + 2 ) = k − 1 (q+1)-(q-k+2)=k-1 ( q + 1 ) − ( q − k + 2 ) = k − 1
members meet A U \mathcal{A}_U A U precisely in the set S S S . We call these the tangent hyperplanes determined by S S S .
Tangent-Envelope Identities
In this section, we determine the boundary form and the first transverse coefficient of the tangent envelope of A U \mathcal{A}_U A U . These identities provide the basis for the differential argument in § 4 .
The Boundary Form of the Tangent Envelope
Put
ϵ = { 1 , q even , 2 , q odd . \epsilon=
\begin{cases}
1, & q\ \text{even},\\
2, & q\ \text{odd}.
\end{cases} ϵ = { 1 , 2 , q even , q odd .
We use the following specialization of [2 Theorem 7] ; see also [1 Theorem 39] . This follows by replacing the dimension parameter in those results by k + 1 k+1 k + 1 and taking t = k − 1 t=k-1 t = k − 1 and m = ϵ m=\epsilon m = ϵ .
Theorem 3.1 (Tangent-envelope theorem). Let q q q be a prime power, 3 ≤ k ≤ q − 2 3 \le k \le q-2 3 ≤ k ≤ q − 2 , and let U ∈ F q [ X ] U \in\mathbb{F}_q[X] U ∈ F q [ X ] , deg U < q \deg U < q deg U < q , be the canonical representative of a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) . Assume q ≥ ( ϵ + 1 ) ( k − 1 ) q \ge(\epsilon+1)(k-1) q ≥ ( ϵ + 1 ) ( k − 1 ) . Then there exists a nonzero homogeneous form Φ \Phi Φ of degree ϵ ( k − 1 ) \epsilon(k-1) ϵ ( k − 1 ) on the dual projective space PG ( k , q ) ∨ \operatorname{PG}(k,q)^\vee PG ( k , q ) ∨ with the following property.
For every ( k − 1 ) (k-1) ( k − 1 ) -subset S ⊆ A U S \subseteq\mathcal{A}_U S ⊆ A U , let ℓ S ⊆ PG ( k , q ) ∨ \ell_S \subseteq\operatorname{PG}(k,q)^\vee ℓ S ⊆ PG ( k , q ) ∨ denote the projective line parametrizing the hyperplanes containing ⟨ S ⟩ \langle S\rangle ⟨ S ⟩ , and let
τ 1 , … , τ k − 1 ∈ ℓ S \tau_1,\ldots,\tau_{k-1} \in\ell_S τ 1 , … , τ k − 1 ∈ ℓ S be the points corresponding to the tangent hyperplanes determined by S S S . Then
Φ ∣ ℓ S = c S ∏ i = 1 k − 1 L τ i ϵ \left.\Phi\right|_{\ell_S}=c_S\prod_{i=1}^{k-1}L_{\tau_i}^{\epsilon} Φ ∣ ℓ S = c S i = 1 ∏ k − 1 L τ i ϵ for some c S ∈ F q × c_S \in\mathbb{F}_q^\times c S ∈ F q × , where L τ i L_{\tau_i} L τ i is a linear form on ℓ S \ell_S ℓ S vanishing at τ i \tau_i τ i .
We refer to Φ \Phi Φ as a tangent-envelope form of A U \mathcal{A}_U A U .
Recall the dual coordinates introduced in § 2 . Here g ( X ) = ∑ i = 0 k − 1 a i X i g(X)=\sum_{i=0}^{k-1}a_iX^i g ( X ) = ∑ i = 0 k − 1 a i X i , and ( g , z ) (g,z) ( g , z ) represents the hyperplane ∑ i = 0 k − 1 a i Y i + z Y k = 0 \sum_{i=0}^{k-1}a_iY_i+zY_k=0 ∑ i = 0 k − 1 a i Y i + z Y k = 0 , up to simultaneous nonzero scaling. Thus Φ ( g , z ) \Phi(g,z) Φ ( g , z ) is homogeneous in a 0 , … , a k − 1 , z a_0,\ldots,a_{k-1},z a 0 , … , a k − 1 , z . The identity (3.1) is one of homogeneous polynomials; in particular, the tangent points are precisely the zeros of Φ ∣ ℓ S \left.\Phi\right|_{\ell_S} Φ ∣ ℓ S , each of multiplicity ϵ \epsilon ϵ .
The dual hyperplane z = 0 z=0 z = 0 parametrizes the hyperplanes through the marked point P ∞ P_\infty P ∞ . Since the projection of A U \mathcal{A}_U A U from P ∞ P_\infty P ∞ is prescribed, we can determine the boundary form Φ ( g , 0 ) \Phi(g,0) Φ ( g , 0 ) explicitly.
Definition 3.2 (Discriminant and its square root). For r ≥ 2 r \ge2 r ≥ 2 and g ( X ) = ∑ i = 0 r a i X i g(X) = \sum_{i=0}^{r} a_iX^i g ( X ) = ∑ i = 0 r a i X i with a r ≠ 0 a_r \ne0 a r = 0 , write g ( X ) = a r ∏ i = 1 r ( X − x i ) g(X) = a_r\prod_{i=1}^{r}(X-x_i) g ( X ) = a r ∏ i = 1 r ( X − x i ) over a splitting field. The discriminant form is
Disc r ( g ) = a r 2 r − 2 ∏ 1 ≤ i < j ≤ r ( x i − x j ) 2 . (3) \operatorname{Disc}_r(g) = a_r^{2r-2}\prod_{1\le i<j\le r}(x_i-x_j)^2. \tag*{(3)} Disc r ( g ) = a r 2 r − 2 1 ≤ i < j ≤ r ∏ ( x i − x j ) 2 . (3) In characteristic two, define its polynomial square root by
δ r ( g ) = a r r − 1 ∏ 1 ≤ i < j ≤ r ( x i + x j ) , Disc r ( g ) = δ r ( g ) 2 . (4) \delta_r(g) = a_r^{r-1}\prod_{1\le i<j\le r}(x_i+x_j), \qquad\operatorname{Disc}_r(g)=\delta_r(g)^2. \tag*{(4)} δ r ( g ) = a r r − 1 1 ≤ i < j ≤ r ∏ ( x i + x j ) , Disc r ( g ) = δ r ( g ) 2 . (4) These root expressions define polynomials in the coefficients and extend to a r = 0 a_r=0 a r = 0 . They are homogeneous of coefficient degrees 2 r − 2 2r-2 2 r − 2 and r − 1 r-1 r − 1 , respectively. Set Disc 1 = δ 1 = 1 \operatorname{Disc}_1=\delta_1=1 Disc 1 = δ 1 = 1 .
The following interpolation lemma allows us to extend identities established for the polynomials P T P_T P T to arbitrary polynomials of degree at most k − 1 k-1 k − 1 .
Lemma 3.3. Let e , r ≥ 0 e,r\ge0 e , r ≥ 0 and q ≥ e + r q\ge e+r q ≥ e + r . Fix a subset E ⊆ F q E\subseteq\mathbb{F}_q E ⊆ F q of size e + r e+r e + r . A homogeneous form of degree e e e in the r + 1 r+1 r + 1 coefficients of
g ( X ) = a 0 + a 1 X + ⋯ + a r X r g(X)=a_0+a_1X+\cdots+a_rX^r g ( X ) = a 0 + a 1 X + ⋯ + a r X r is uniquely determined by its values at the polynomials
P T ( X ) = ∏ x ∈ T ( X − x ) , T ∈ ( E r ) . P_T(X)=\prod_{x\in T}(X-x), \qquad T\in\binom{E}{r}. P T ( X ) = x ∈ T ∏ ( X − x ) , T ∈ ( r E ) . Equivalently, if a homogeneous degree-e e e form F ( a 0 , … , a r ) F(a_0,\ldots,a_r) F ( a 0 , … , a r ) vanishes at every P T P_T P T , then F ≡ 0 F\equiv0 F ≡ 0 .
Proof. For T ∈ ( E r ) T\in\binom{E}{r} T ∈ ( r E ) , define
L T ( g ) = ∏ x ∈ E ∖ T g ( x ) P T ( x ) . L_T(g)=\prod_{x\in E\setminus T}\frac{g(x)}{P_T(x)}. L T ( g ) = x ∈ E ∖ T ∏ P T ( x ) g ( x ) . Since ∣ E ∖ T ∣ = e |E\setminus T|=e ∣ E ∖ T ∣ = e , the polynomial L T L_T L T is a homogeneous form of degree e e e in a 0 , … , a r a_0,\ldots,a_r a 0 , … , a r . Moreover,
L T ( P T ′ ) = { 1 , T ′ = T , 0 , T ′ ≠ T . L_T(P_{T'})=
\begin{cases}
1, & T'=T,\\
0, & T'\ne T.
\end{cases} L T ( P T ′ ) = { 1 , 0 , T ′ = T , T ′ = T . Indeed, if T ′ ≠ T T'\ne T T ′ = T , then some x ∈ T ′ ∖ T x\in T'\setminus T x ∈ T ′ ∖ T belongs to E ∖ T E\setminus T E ∖ T , and the corresponding factor vanishes. Thus the forms L T L_T L T are linearly independent. Their number is ( e + r r ) \binom{e+r}{r} ( r e + r ) , which is the dimension of the space of homogeneous degree-e e e forms in r + 1 r+1 r + 1 variables. Hence they form a basis, and the assertion follows.
Proposition 3.4. Let q q q be a prime power, 3 ≤ k ≤ q − 2 3\le k\le q-2 3 ≤ k ≤ q − 2 , and let U ∈ F q [ X ] U\in\mathbb{F}_q[X] U ∈ F q [ X ] , deg U < q \deg U<q deg U < q , be the canonical representative of a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) . Assume q ≥ ( ϵ + 1 ) ( k − 1 ) q\ge(\epsilon+1)(k-1) q ≥ ( ϵ + 1 ) ( k − 1 ) . The envelope Φ \Phi Φ supplied by Theorem 3.1 may be scaled so that, for every
g ( X ) = ∑ i = 0 k − 1 a i X i , g(X)=\sum_{i=0}^{k-1}a_iX^i, g ( X ) = i = 0 ∑ k − 1 a i X i , one has
Φ ( g , 0 ) = { a k − 1 δ k − 1 ( g ) , q even , a k − 1 2 Disc k − 1 ( g ) , q odd . (5) \Phi(g,0)=
\begin{cases}
a_{k-1}\delta_{k-1}(g), & q\ \text{even},\\
a_{k-1}^{2}\operatorname{Disc}_{k-1}(g), & q\ \text{odd}.
\end{cases} \tag*{(5)} Φ ( g , 0 ) = { a k − 1 δ k − 1 ( g ) , a k − 1 2 Disc k − 1 ( g ) , q even , q odd . (5)
Proof. Let B ( g ) \mathcal{B}(g) B ( g ) denote the right-hand side of (5) . Fix B ⊆ F q B \subseteq\mathbb{F}_q B ⊆ F q with ∣ B ∣ = k − 2 \lvert B\rvert= k-2 ∣ B ∣ = k − 2 . A hyperplane through P ∞ P_{\infty} P ∞ and the finite arc points indexed by B B B has z = 0 z=0 z = 0 , and its polynomial g g g is divisible by P B P_B P B . Thus the corresponding pencil is
( g , z ) = ( P B ( X ) ( α + β X ) , 0 ) , [ α : β ] ∈ PG ( 1 , q ) . (g,z)=(P_B(X)(\alpha+\beta X),0),\qquad[\alpha:\beta]\in\operatorname{PG}(1,q). ( g , z ) = ( P B ( X ) ( α + β X ) , 0 ) , [ α : β ] ∈ PG ( 1 , q ) .
For β = 0 \beta=0 β = 0 , the roots of g g g are exactly B B B . If β ≠ 0 \beta\ne0 β = 0 , the only possible additional root is − α / β -\alpha/\beta − α / β , which already belongs to B B B precisely when α + β b = 0 \alpha+\beta b=0 α + β b = 0 for some b ∈ B b\in B b ∈ B . Consequently, the tangent members of the pencil are β = 0 \beta=0 β = 0 and α + β b = 0 \alpha+\beta b=0 α + β b = 0 (b ∈ B b\in B b ∈ B ). By Theorem 3.1 ,
Φ ( P B ( X ) ( α + β X ) , 0 ) = λ B ( β ∏ b ∈ B ( α + β b ) ) ϵ , λ B ∈ F q × . (6) \Phi(P_B(X)(\alpha+\beta X),0)=\lambda_B\left(\beta\prod_{b\in B}(\alpha+\beta b)\right)^{\epsilon},\qquad\lambda_B\in\mathbb{F}_q^{\times}. \tag*{(6)} Φ ( P B ( X ) ( α + β X ) , 0 ) = λ B ( β b ∈ B ∏ ( α + β b ) ) ϵ , λ B ∈ F q × . (6)
Applying the discriminant product formula to P B P_B P B and α + β X \alpha+\beta X α + β X , we obtain
δ k − 1 ( P B ( X ) ( α + β X ) ) = δ k − 2 ( P B ) ∏ b ∈ B ( α + β b ) ( q even ) , \delta_{k-1}(P_B(X)(\alpha+\beta X))=\delta_{k-2}(P_B)\prod_{b\in B}(\alpha+\beta b)\qquad(q\text{ even}), δ k − 1 ( P B ( X ) ( α + β X )) = δ k − 2 ( P B ) b ∈ B ∏ ( α + β b ) ( q even ) ,
Disc k − 1 ( P B ( X ) ( α + β X ) ) = Disc k − 2 ( P B ) ∏ b ∈ B ( α + β b ) 2 ( q odd ) . \operatorname{Disc}_{k-1}(P_B(X)(\alpha+\beta X))=\operatorname{Disc}_{k-2}(P_B)\prod_{b\in B}(\alpha+\beta b)^2\qquad(q\text{ odd}). Disc k − 1 ( P B ( X ) ( α + β X )) = Disc k − 2 ( P B ) b ∈ B ∏ ( α + β b ) 2 ( q odd ) .
These are polynomial identities in α , β \alpha,\beta α , β , so they also hold when β = 0 \beta=0 β = 0 . Since the coefficient of X k − 1 X^{k-1} X k − 1 in P B ( X ) ( α + β X ) P_B(X)(\alpha+\beta X) P B ( X ) ( α + β X ) is β \beta β , we obtain
B ( P B ( X ) ( α + β X ) ) = { δ k − 2 ( P B ) β ∏ b ∈ B ( α + β b ) , q even , Disc k − 2 ( P B ) β 2 ∏ b ∈ B ( α + β b ) 2 , q odd . \mathcal{B}(P_B(X)(\alpha+\beta X))=
\begin{cases}
\delta_{k-2}(P_B)\,\beta\prod_{b\in B}(\alpha+\beta b), & q\text{ even},\\
\operatorname{Disc}_{k-2}(P_B)\,\beta^2\prod_{b\in B}(\alpha+\beta b)^2, & q\text{ odd}.
\end{cases} B ( P B ( X ) ( α + β X )) = { δ k − 2 ( P B ) β ∏ b ∈ B ( α + β b ) , Disc k − 2 ( P B ) β 2 ∏ b ∈ B ( α + β b ) 2 , q even , q odd .
Both prefactors are nonzero because P B P_B P B is square-free. Comparison with (6) shows that Φ ( g , 0 ) = c B B ( g ) \Phi(g,0)=c_B\mathcal{B}(g) Φ ( g , 0 ) = c B B ( g ) on this pencil for some c B ≠ 0 c_B\ne0 c B = 0 .
If B , B ′ B,B' B , B ′ differ in one element, the two pencils contain the same monic polynomial P B ∪ B ′ P_{B\cup B'} P B ∪ B ′ , for which B \mathcal{B} B is nonzero. Hence c B = c B ′ c_B=c_{B'} c B = c B ′ . The graph of ( k − 2 ) (k-2) ( k − 2 ) -subsets with edges joining pairs that differ in one element is connected. All c B c_B c B are therefore equal to a single c ∈ F q × c\in\mathbb{F}_q^{\times} c ∈ F q × , and for any T ⊆ F q T\subseteq\mathbb{F}_q T ⊆ F q with ∣ T ∣ = k − 1 \lvert T\rvert=k-1 ∣ T ∣ = k − 1 , we have
Φ ( P T , 0 ) = c B ( P T ) . \Phi(P_T,0)=c\mathcal{B}(P_T). Φ ( P T , 0 ) = c B ( P T ) .
Both sides have coefficient degree ϵ ( k − 1 ) \epsilon(k-1) ϵ ( k − 1 ) . Since q ≥ ( ϵ + 1 ) ( k − 1 ) q\ge(\epsilon+1)(k-1) q ≥ ( ϵ + 1 ) ( k − 1 ) , Lemma 3.3 with e = ϵ ( k − 1 ) e=\epsilon(k-1) e = ϵ ( k − 1 ) and r = k − 1 r=k-1 r = k − 1 shows that Φ ( g , 0 ) = c B ( g ) \Phi(g,0)=c\mathcal{B}(g) Φ ( g , 0 ) = c B ( g ) for every g ∈ F q [ X ] g\in\mathbb{F}_q[X] g ∈ F q [ X ] of degree at most $k-1. Rescaling Φ \Phi Φ by c − 1 c^{-1} c − 1 proves the proposition.
The First Transverse Coefficient
We determine the first transverse coefficient of the envelope from a missing-value identity for local quotients.
Let U ∈ F q [ X ] U\in\mathbb{F}_q[X] U ∈ F q [ X ] , deg U < q \deg U<q deg U < q , be the canonical representative of a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) , where 3 ≤ k ≤ q − 2 3\le k\le q-2 3 ≤ k ≤ q − 2 . Fix S ⊆ F q S\subseteq\mathbb{F}_q S ⊆ F q with ∣ S ∣ = k − 1 \lvert S\rvert=k-1 ∣ S ∣ = k − 1 , and let
I S ( X ) = ∑ a ∈ S U ( a ) P S ( X ) ( X − a ) P S ′ ( a ) I_S(X)=\sum_{a\in S}U(a)\frac{P_S(X)}{(X-a)P'_S(a)} I S ( X ) = a ∈ S ∑ U ( a ) ( X − a ) P S ′ ( a ) P S ( X )
be the polynomial of degree at most k − 2 k-2 k − 2 interpolating U U U on S S S . Since U − I S U-I_S U − I S vanishes on S S S , we may define
Q S ( X ) = U ( X ) − I S ( X ) P S ( X ) ∈ F q [ X ] . Q_S(X)=\frac{U(X)-I_S(X)}{P_S(X)}\in\mathbb{F}_q[X]. Q S ( X ) = P S ( X ) U ( X ) − I S ( X ) ∈ F q [ X ] .
The restriction of Q S Q_S Q S to F q ∖ S \mathbb{F}_q\setminus S F q ∖ S is injective. Indeed, if Q S ( x ) = Q S ( y ) = c Q_S(x)=Q_S(y)=c Q S ( x ) = Q S ( y ) = c for distinct x , y ∉ S x,y\notin S x , y ∈ / S , then the polynomial I S + c P S I_S+cP_S I S + c P S , of degree at most k − 1 k-1 k − 1 , agrees with U U U on the k + 1 k+1 k + 1 points of S ∪ { x , y } S\cup\{x,y\} S ∪ { x , y } , contradicting (2) . Hence the set
M S = F q ∖ { Q S ( x ) : x ∈ F q ∖ S } M_S=\mathbb{F}_q\setminus\{Q_S(x):x\in\mathbb{F}_q\setminus S\} M S = F q ∖ { Q S ( x ) : x ∈ F q ∖ S }
has cardinality k − 1 k-1 k − 1 .
The first-order term of the tangent-pencil product will involve the sum of the values omitted by Q S Q_S Q S . The next lemma computes this sum.
Lemma 3.5. Let q q q be a prime power, 3 ≤ k ≤ q − 2 3\leq k\leq q-2 3 ≤ k ≤ q − 2 , and let U ∈ F q [ X ] U\in\mathbb{F}_q[X] U ∈ F q [ X ] , deg U < q \deg U<q deg U < q , be the canonical representative of a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) . For every ( k − 1 ) (k-1) ( k − 1 ) -subset S ⊆ F q S\subseteq\mathbb{F}_q S ⊆ F q , let M S M_S M S be defined as above. Then
∑ m ∈ M S m = ∑ a ∈ S U ′ ( a ) P S ′ ( a ) . (7) \sum_{m\in M_S}m=\sum_{a\in S}\frac{U'(a)}{P_S'(a)}. \tag*{(7)} m ∈ M S ∑ m = a ∈ S ∑ P S ′ ( a ) U ′ ( a ) . (7) Proof. Since deg Q S ≤ q − k < q − 1 \deg Q_S\leq q-k<q-1 deg Q S ≤ q − k < q − 1 , the standard power-sum identity ∑ x ∈ F q H ( x ) = 0 \sum_{x\in\mathbb{F}_q}H(x)=0 ∑ x ∈ F q H ( x ) = 0 for deg H < q − 1 \deg H<q-1 deg H < q − 1 implies
∑ x ∈ F q Q S ( x ) = 0. \sum_{x\in\mathbb{F}_q}Q_S(x)=0. x ∈ F q ∑ Q S ( x ) = 0. Since Q S Q_S Q S is injective on F q ∖ S \mathbb{F}_q\setminus S F q ∖ S and ∑ t ∈ F q t = 0 \sum_{t\in\mathbb{F}_q}t=0 ∑ t ∈ F q t = 0 ,
∑ m ∈ M S m = − ∑ x ∉ S Q S ( x ) = ∑ a ∈ S Q S ( a ) . \sum_{m\in M_S}m=-\sum_{x\notin S}Q_S(x)=\sum_{a\in S}Q_S(a). m ∈ M S ∑ m = − x ∈ / S ∑ Q S ( x ) = a ∈ S ∑ Q S ( a ) . Differentiating U − I S = P S Q S U-I_S=P_SQ_S U − I S = P S Q S at a ∈ S a\in S a ∈ S yields Q S ( a ) = U ′ ( a ) − I S ′ ( a ) P S ′ ( a ) Q_S(a)=\frac{U'(a)-I_S'(a)}{P_S'(a)} Q S ( a ) = P S ′ ( a ) U ′ ( a ) − I S ′ ( a ) . Therefore
∑ m ∈ M S m = ∑ a ∈ S U ′ ( a ) P S ′ ( a ) − ∑ a ∈ S I S ′ ( a ) P S ′ ( a ) . \sum_{m\in M_S}m=\sum_{a\in S}\frac{U'(a)}{P_S'(a)}-\sum_{a\in S}\frac{I_S'(a)}{P_S'(a)}. m ∈ M S ∑ m = a ∈ S ∑ P S ′ ( a ) U ′ ( a ) − a ∈ S ∑ P S ′ ( a ) I S ′ ( a ) . The second sum vanishes by (1) , since deg I S ′ ≤ k − 3 \deg I_S'\leq k-3 deg I S ′ ≤ k − 3 .
Under the hypotheses of Proposition 3.4, fix the envelope Φ \Phi Φ normalized as in that proposition. The dual pencil determined by the finite arc points indexed by S S S is
( g , z ) = ( α P S − z I S , z ) , [ α : z ] ∈ PG ( 1 , q ) . (g,z)=(\alpha P_S-zI_S,z),\qquad[\alpha:z]\in\operatorname{PG}(1,q). ( g , z ) = ( α P S − z I S , z ) , [ α : z ] ∈ PG ( 1 , q ) .
Indeed, a hyperplane ( g , z ) (g,z) ( g , z ) contains these points precisely when g + z I S g+zI_S g + z I S vanishes on S S S , and hence is a scalar multiple of P S P_S P S .
For x ∉ S x\notin S x ∈ / S ,
g ( x ) + z U ( x ) = P S ( x ) ( α + z Q S ( x ) ) . g(x)+zU(x)=P_S(x)(\alpha+zQ_S(x)). g ( x ) + z U ( x ) = P S ( x ) ( α + z Q S ( x )) .
so the corresponding hyperplane contains the additional finite arc point indexed by x x x if and only if
α + z Q S ( x ) = 0. \alpha+zQ_S(x)=0. α + z Q S ( x ) = 0.
The member z = 0 z=0 z = 0 contains the marked point P ∞ P_{\infty} P ∞ and is therefore not tangent to S S S . For z ≠ 0 z\ne0 z = 0 , injectivity of Q S Q_S Q S shows that the tangent members are precisely
[ α : z ] = [ − m : 1 ] , m ∈ M S . [\alpha:z]=[-m:1],\qquad m\in M_S. [ α : z ] = [ − m : 1 ] , m ∈ M S .
By Theorem 3.1 ,
Φ ( α P S − z I S , z ) = κ S ∏ m ∈ M S ( α + z m ) ϵ . \Phi(\alpha P_S-zI_S,z)=\kappa_S\prod_{m\in M_S}(\alpha+zm)^{\epsilon}. Φ ( α P S − z I S , z ) = κ S m ∈ M S ∏ ( α + z m ) ϵ .
for some κ S ∈ F q × \kappa_S\in\mathbb{F}_q^{\times} κ S ∈ F q × . Evaluating at ( α , z ) = ( 1 , 0 ) (\alpha,z)=(1,0) ( α , z ) = ( 1 , 0 ) and using Proposition 3.4 , we obtain
κ S = { δ k − 1 ( P S ) , q even , Disc k − 1 ( P S ) , q odd . \kappa_S=
\begin{cases}
\delta_{k-1}(P_S), & q\text{ even},\\
\operatorname{Disc}_{k-1}(P_S), & q\text{ odd}.
\end{cases} κ S = { δ k − 1 ( P S ) , Disc k − 1 ( P S ) , q even , q odd .
Therefore
Φ ( P S − z I S , z ) = { δ k − 1 ( P S ) ∏ m ∈ M S ( 1 + z m ) , q even , Disc k − 1 ( P S ) ∏ m ∈ M S ( 1 + z m ) 2 , q odd . (8) \Phi(P_S-zI_S,z)=
\begin{cases}
\delta_{k-1}(P_S)\prod_{m\in M_S}(1+zm), & q\text{ even},\\
\operatorname{Disc}_{k-1}(P_S)\prod_{m\in M_S}(1+zm)^2, & q\text{ odd}.
\end{cases} \tag*{(8)} Φ ( P S − z I S , z ) = { δ k − 1 ( P S ) ∏ m ∈ M S ( 1 + z m ) , Disc k − 1 ( P S ) ∏ m ∈ M S ( 1 + z m ) 2 , q even , q odd . (8)
The identity (8) describes the variation of Φ \Phi Φ along the pencil, where both g g g and z z z change. To isolate the coefficient of z z z with g g g fixed, we must also compute the first-order variation of the boundary forms appearing in Proposition 3.4 . For a form F F F in the coefficients of g ( X ) = ∑ i = 0 k − 1 a i X i g(X)=\sum_{i=0}^{k-1}a_iX^i g ( X ) = ∑ i = 0 k − 1 a i X i and a direction H ( X ) = ∑ i = 0 k − 1 h i X i H(X)=\sum_{i=0}^{k-1}h_iX^i H ( X ) = ∑ i = 0 k − 1 h i X i , its coefficient derivative is
d F ( g ) [ H ] = ∑ i = 0 k − 1 ∂ F ∂ a i ( g ) h i . dF(g)[H]=\sum_{i=0}^{k-1}\frac{\partial F}{\partial a_i}(g)h_i. d F ( g ) [ H ] = i = 0 ∑ k − 1 ∂ a i ∂ F ( g ) h i .
Equivalently, F ( g + η H ) = F ( g ) + η d F ( g ) [ H ] F(g+\eta H)=F(g)+\eta\,dF(g)[H] F ( g + η H ) = F ( g ) + η d F ( g ) [ H ] in F q [ η ] / ( η 2 ) \mathbb{F}_q[\eta]/(\eta^2) F q [ η ] / ( η 2 ) . We also use the second Hasse derivative, defined by
g ( X + Z ) = g ( X ) + g ′ ( X ) Z + g [ 2 ] ( X ) Z 2 + ⋯ . g(X+Z)=g(X)+g'(X)Z+g^{[2]}(X)Z^2+\cdots. g ( X + Z ) = g ( X ) + g ′ ( X ) Z + g [ 2 ] ( X ) Z 2 + ⋯ .
We compute these derivatives at P S P_S P S by tracking its roots under the perturbation P S + η H P_S+\eta H P S + η H .
Lemma 3.6. Let q q q be a prime power, 3 ≤ k ≤ q − 2 3\le k\le q-2 3 ≤ k ≤ q − 2 , and let S ⊆ F q S\subseteq\mathbb{F}_q S ⊆ F q have size k − 1 k-1 k − 1 . For any H ∈ F q [ X ] H\in\mathbb{F}_q[X] H ∈ F q [ X ] with deg H < k − 1 \deg H<k-1 deg H < k − 1 , in even characteristic,
d δ k − 1 ( P S ) [ H ] δ k − 1 ( P S ) = ∑ a ∈ S H ( a ) P S [ 2 ] ( a ) P S ′ ( a ) 2 . (9) \frac{d\delta_{k-1}(P_S)[H]}{\delta_{k-1}(P_S)}
=\sum_{a\in S}\frac{H(a)P_S^{[2]}(a)}{P_S'(a)^2}. \tag*{(9)} δ k − 1 ( P S ) d δ k − 1 ( P S ) [ H ] = a ∈ S ∑ P S ′ ( a ) 2 H ( a ) P S [ 2 ] ( a ) . (9) whereas in odd characteristic,
d Disc k − 1 ( P S ) [ H ] Disc k − 1 ( P S ) = − ∑ a ∈ S H ( a ) P S ′ ′ ( a ) P S ′ ( a ) 2 . (10) \frac{d\operatorname{Disc}_{k-1}(P_S)[H]}{\operatorname{Disc}_{k-1}(P_S)}
=-\sum_{a\in S}\frac{H(a)P_S''(a)}{P_S'(a)^2}. \tag*{(10)} Disc k − 1 ( P S ) d Disc k − 1 ( P S ) [ H ] = − a ∈ S ∑ P S ′ ( a ) 2 H ( a ) P S ′′ ( a ) . (10)
Proof. Work in F q [ η ] / ( η 2 ) \mathbb{F}_q[\eta]/(\eta^2) F q [ η ] / ( η 2 ) . Since deg H < k − 1 \deg H<k-1 deg H < k − 1 , the perturbation P S + η H P_S+\eta H P S + η H remains monic. Its roots are a + η v a a+\eta v_a a + η v a , where
v a = − H ( a ) P S ′ ( a ) . (11) v_a=-\frac{H(a)}{P_S'(a)}. \tag*{(11)} v a = − P S ′ ( a ) H ( a ) . (11)
Indeed, substituting a + η v a a+\eta v_a a + η v a into P S + η H P_S+\eta H P S + η H yields η ( v a P S ′ ( a ) + H ( a ) ) = 0 \eta(v_aP_S'(a)+H(a))=0 η ( v a P S ′ ( a ) + H ( a )) = 0 . Moreover, by Lagrange interpolation,
∏ a ∈ S ( X − a − η v a ) = P S ( X ) − η ∑ a ∈ S v a P S ( X ) X − a = P S ( X ) + η H ( X ) , \prod_{a\in S}(X-a-\eta v_a)=P_S(X)-\eta\sum_{a\in S}v_a\frac{P_S(X)}{X-a}=P_S(X)+\eta H(X), a ∈ S ∏ ( X − a − η v a ) = P S ( X ) − η a ∈ S ∑ v a X − a P S ( X ) = P S ( X ) + η H ( X ) ,
so these are all its roots, counted with multiplicity.
Order S = { a 1 , … , a k − 1 } S=\{a_1,\ldots,a_{k-1}\} S = { a 1 , … , a k − 1 } . Expanding the product of root differences to first order yields
∏ i < j ( ( a i − a j ) + η ( v a i − v a j ) ) = ∏ i < j ( a i − a j ) ∏ i < j ( 1 + η v a i − v a j a i − a j ) = ∏ i < j ( a i − a j ) ( 1 + η ∑ i < j v a i − v a j a i − a j ) , \begin{aligned}
\prod_{i<j}\bigl((a_i-a_j)+\eta(v_{a_i}-v_{a_j})\bigr)=\prod_{i<j}(a_i-a_j)\prod_{i<j}\left(1+\eta\frac{v_{a_i}-v_{a_j}}{a_i-a_j}\right) \\
&=\prod_{i<j}(a_i-a_j)\left(1+\eta\sum_{i<j}\frac{v_{a_i}-v_{a_j}}{a_i-a_j}\right),
\end{aligned} i < j ∏ ( ( a i − a j ) + η ( v a i − v a j ) ) = i < j ∏ ( a i − a j ) i < j ∏ ( 1 + η a i − a j v a i − v a j ) = i < j ∏ ( a i − a j ) ( 1 + η i < j ∑ a i − a j v a i − v a j ) ,
where the last equality follows from η 2 = 0 \eta^2=0 η 2 = 0 . If q q q is even, the root-difference product is δ k − 1 ( P S ) \delta_{k-1}(P_S) δ k − 1 ( P S ) and a i − a j = a i + a j a_i-a_j=a_i+a_j a i − a j = a i + a j . On the other hand, by the coefficient-differential definition,
δ k − 1 ( P S + η H ) = δ k − 1 ( P S ) + η d δ k − 1 ( P S ) [ H ] . \delta_{k-1}(P_S+\eta H)=\delta_{k-1}(P_S)+\eta\,d\delta_{k-1}(P_S)[H]. δ k − 1 ( P S + η H ) = δ k − 1 ( P S ) + η d δ k − 1 ( P S ) [ H ] .
Comparing the coefficients of η \eta η in these two expressions, we find
d δ k − 1 ( P S ) [ H ] δ k − 1 ( P S ) = ∑ { a , b } ⊆ S v a + v b a + b . \frac{d\delta_{k-1}(P_S)[H]}{\delta_{k-1}(P_S)}=\sum_{\{a,b\}\subseteq S}\frac{v_a+v_b}{a+b}. δ k − 1 ( P S ) d δ k − 1 ( P S ) [ H ] = { a , b } ⊆ S ∑ a + b v a + v b .
Collecting the terms involving each v a v_a v a and using (11) (with − 1 = 1 -1=1 − 1 = 1 ), we obtain
d δ k − 1 ( P S ) [ H ] δ k − 1 ( P S ) = ∑ a ∈ S v a ∑ b ∈ S ∖ { a } 1 a + b = ∑ a ∈ S H ( a ) P S ′ ( a ) ∑ b ∈ S ∖ { a } 1 a + b . (12) \frac{d\delta_{k-1}(P_S)[H]}{\delta_{k-1}(P_S)}
=\sum_{a\in S}v_a\sum_{b\in S\setminus\{a\}}\frac{1}{a+b}
=\sum_{a\in S}\frac{H(a)}{P_S'(a)}\sum_{b\in S\setminus\{a\}}\frac{1}{a+b}. \tag*{(12)} δ k − 1 ( P S ) d δ k − 1 ( P S ) [ H ] = a ∈ S ∑ v a b ∈ S ∖ { a } ∑ a + b 1 = a ∈ S ∑ P S ′ ( a ) H ( a ) b ∈ S ∖ { a } ∑ a + b 1 . (12)
For any a ∈ S a\in S a ∈ S , the expansion P S ( a + Z ) = Z P S ′ ( a ) ∏ b ∈ S ∖ { a } ( 1 + Z a − b ) P_S(a+Z)=ZP_S'(a)\prod_{b\in S\setminus\{a\}}\left(1+\frac{Z}{a-b}\right) P S ( a + Z ) = Z P S ′ ( a ) ∏ b ∈ S ∖ { a } ( 1 + a − b Z ) shows, on comparing the coefficients of Z 2 Z^2 Z 2 , that
P S [ 2 ] ( a ) P S ′ ( a ) = ∑ b ∈ S ∖ { a } 1 a − b . (13) \frac{P_S^{[2]}(a)}{P_S'(a)}=\sum_{b\in S\setminus\{a\}}\frac{1}{a-b}. \tag*{(13)} P S ′ ( a ) P S [ 2 ] ( a ) = b ∈ S ∖ { a } ∑ a − b 1 . (13)
In even characteristic, (12) and (13) prove (9) .
If q q q is odd, the discriminant is the square of the root-difference product. Its relative first-order variation is therefore twice the sum appearing in the product expansion:
d Disc k − 1 ( P S ) [ H ] Disc k − 1 ( P S ) = 2 ∑ i < j v a i − v a j a i − a j = 2 ∑ a ∈ S v a ∑ b ∈ S ∖ { a } 1 a − b = − ∑ a ∈ S H ( a ) P S ′ ′ ( a ) P S ′ ( a ) 2 , \frac{d\operatorname{Disc}_{k-1}(P_S)[H]}{\operatorname{Disc}_{k-1}(P_S)}
=2\sum_{i<j}\frac{v_{a_i}-v_{a_j}}{a_i-a_j}
=2\sum_{a\in S}v_a\sum_{b\in S\setminus\{a\}}\frac{1}{a-b}
=-\sum_{a\in S}\frac{H(a)P_S''(a)}{P_S'(a)^2}, Disc k − 1 ( P S ) d Disc k − 1 ( P S ) [ H ] = 2 i < j ∑ a i − a j v a i − v a j = 2 a ∈ S ∑ v a b ∈ S ∖ { a } ∑ a − b 1 = − a ∈ S ∑ P S ′ ( a ) 2 H ( a ) P S ′′ ( a ) ,
where the last equality follows from (11) , (13) , and P S ′ ′ = 2 P S [ 2 ] P_S''=2P_S^{[2]} P S ′′ = 2 P S [ 2 ] . This proves (10) .
Expand the normalized envelope in the transverse coordinate:
Φ ( g , z ) = ∑ j = 0 ϵ ( k − 1 ) z j Φ j ( g ) , \Phi(g,z)=\sum_{j=0}^{\epsilon(k-1)}z^j\Phi_j(g), Φ ( g , z ) = j = 0 ∑ ϵ ( k − 1 ) z j Φ j ( g ) ,
where Φ j \Phi_j Φ j is either zero or homogeneous of coefficient degree ϵ ( k − 1 ) − j \epsilon(k-1)-j ϵ ( k − 1 ) − j .
The missing-value identity and the boundary differentials determine Φ 1 ( P S ) \Phi_1(P_S) Φ 1 ( P S ) through a first-order comparison in (8) .
Proposition 3.7. Let q q q be a prime power, 3 ≤ k ≤ q − 2 3 \le k \le q - 2 3 ≤ k ≤ q − 2 , and let U ∈ F q [ X ] U \in\mathbb{F}_q[X] U ∈ F q [ X ] , deg U < q \deg U < q deg U < q , be the canonical representative of a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) . Suppose q ≥ ( ϵ + 1 ) ( k − 1 ) q \ge(\epsilon+ 1)(k - 1) q ≥ ( ϵ + 1 ) ( k − 1 ) , and normalize Φ \Phi Φ as in Proposition 3.4 . For every ( k − 1 ) (k - 1) ( k − 1 ) -subset S ⊆ F q S \subseteq\mathbb{F}_q S ⊆ F q ,
Φ 1 ( P S ) = δ k − 1 ( P S ) ( ∑ a ∈ S U ′ ( a ) P S ′ ( a ) + ∑ a ∈ S U ( a ) P S [ 2 ] ( a ) P S ( a ) 2 ) ( q even ) , (14) \Phi_1(P_S) = \delta_{k-1}(P_S)\left(\sum_{a \in S} \frac{U'(a)}{P'_S(a)} + \sum_{a \in S} \frac{U(a)P_S^{[2]}(a)}{P_S(a)^2}\right)
\qquad(q\ \text{even}), \tag*{(14)} Φ 1 ( P S ) = δ k − 1 ( P S ) ( a ∈ S ∑ P S ′ ( a ) U ′ ( a ) + a ∈ S ∑ P S ( a ) 2 U ( a ) P S [ 2 ] ( a ) ) ( q even ) , (14) and
Φ 1 ( P S ) = Disc k − 1 ( P S ) ( 2 ∑ a ∈ S U ′ ( a ) P S ′ ( a ) − ∑ a ∈ S U ( a ) P S ′ ′ ( a ) P S ′ ( a ) 2 ) ( q odd ) . (15) \Phi_1(P_S) = \operatorname{Disc}_{k-1}(P_S)\left(2\sum_{a \in S} \frac{U'(a)}{P'_S(a)} - \sum_{a \in S} \frac{U(a)P''_S(a)}{P'_S(a)^2}\right)
\qquad(q\ \text{odd}). \tag*{(15)} Φ 1 ( P S ) = Disc k − 1 ( P S ) ( 2 a ∈ S ∑ P S ′ ( a ) U ′ ( a ) − a ∈ S ∑ P S ′ ( a ) 2 U ( a ) P S ′′ ( a ) ) ( q odd ) . (15) The coefficient degree of Φ 1 \Phi_1 Φ 1 is at most k − 2 k - 2 k − 2 in even characteristic and at most 2 k − 3 2k - 3 2 k − 3 in odd characteristic.
Proof. Fix S S S and work in F q [ η ] / ( η 2 ) \mathbb{F}_q[\eta]/(\eta^2) F q [ η ] / ( η 2 ) . We substitute z = η z = \eta z = η in the affine chart α = 1 \alpha= 1 α = 1 of (8) . Expanding first in the transverse coordinate and then in the coefficients of P S − η I S P_S - \eta I_S P S − η I S , we obtain
Φ ( P S − η I S , η ) = Φ 0 ( P S − η I S ) + η Φ 1 ( P S − η I S ) = Φ 0 ( P S ) + η ( Φ 1 ( P S ) − d Φ 0 ( P S ) [ I S ] ) . \Phi(P_S - \eta I_S,\eta) = \Phi_0(P_S - \eta I_S) + \eta\Phi_1(P_S - \eta I_S) = \Phi_0(P_S) + \eta\left(\Phi_1(P_S) - d\Phi_0(P_S)[I_S]\right). Φ ( P S − η I S , η ) = Φ 0 ( P S − η I S ) + η Φ 1 ( P S − η I S ) = Φ 0 ( P S ) + η ( Φ 1 ( P S ) − d Φ 0 ( P S ) [ I S ] ) . On the other hand, (8) and Φ 0 ( P S ) ≠ 0 \Phi_0(P_S) \ne0 Φ 0 ( P S ) = 0 yield
Φ ( P S − η I S , η ) = Φ 0 ( P S ) ∏ m ∈ M S ( 1 + η m ) ϵ = Φ 0 ( P S ) ( 1 + ϵ η ∑ m ∈ M S m ) . \Phi(P_S - \eta I_S,\eta) = \Phi_0(P_S)\prod_{m \in M_S}(1+\eta m)^\epsilon= \Phi_0(P_S)\left(1+\epsilon\eta\sum_{m \in M_S}m\right). Φ ( P S − η I S , η ) = Φ 0 ( P S ) m ∈ M S ∏ ( 1 + η m ) ϵ = Φ 0 ( P S ) ( 1 + ϵη m ∈ M S ∑ m ) . Comparing the coefficients of η \eta η in the two identities, we obtain
Φ 1 ( P S ) Φ 0 ( P S ) = ϵ ∑ m ∈ M S m + d Φ 0 ( P S ) [ I S ] Φ 0 ( P S ) . (16) \frac{\Phi_1(P_S)}{\Phi_0(P_S)} = \epsilon\sum_{m \in M_S}m + \frac{d\Phi_0(P_S)[I_S]}{\Phi_0(P_S)}. \tag*{(16)} Φ 0 ( P S ) Φ 1 ( P S ) = ϵ m ∈ M S ∑ m + Φ 0 ( P S ) d Φ 0 ( P S ) [ I S ] . (16) It remains to evaluate the two terms on the right. By Lemma 3.5 ,
∑ m ∈ M S m = ∑ a ∈ S U ′ ( a ) P S ′ ( a ) . \sum_{m \in M_S}m = \sum_{a \in S}\frac{U'(a)}{P'_S(a)}. m ∈ M S ∑ m = a ∈ S ∑ P S ′ ( a ) U ′ ( a ) . By Proposition 3.4 , Φ 0 ( g ) \Phi_0(g) Φ 0 ( g ) is a k − 1 δ k − 1 ( g ) a_{k-1}\delta_{k-1}(g) a k − 1 δ k − 1 ( g ) in even characteristic and a k − 1 2 Disc k − 1 ( g ) a_{k-1}^2\operatorname{Disc}_{k-1}(g) a k − 1 2 Disc k − 1 ( g ) in odd characteristic. Since P S P_S P S is monic and deg I S ≤ k − 2 \deg I_S \le k - 2 deg I S ≤ k − 2 , the leading coefficient of P S − η I S P_S - \eta I_S P S − η I S remains 1 1 1 . Thus Lemma 3.6, together with I S ( a ) = U ( a ) I_S(a) = U(a) I S ( a ) = U ( a ) for a ∈ S a \in S a ∈ S , implies
d Φ 0 ( P S ) [ I S ] Φ 0 ( P S ) = { ∑ a ∈ S U ( a ) P S [ 2 ] ( a ) P S ( a ) 2 , q even , − ∑ a ∈ S U ( a ) P S ′ ′ ( a ) P S ′ ( a ) 2 , q odd . \frac{d\Phi_0(P_S)[I_S]}{\Phi_0(P_S)}
=
\begin{cases}
\sum_{a \in S}\frac{U(a)P_S^{[2]}(a)}{P_S(a)^2}, & q\ \text{even},\\[1.2em]
-\sum_{a \in S}\frac{U(a)P''_S(a)}{P'_S(a)^2}, & q\ \text{odd}.
\end{cases} Φ 0 ( P S ) d Φ 0 ( P S ) [ I S ] = ⎩ ⎨ ⎧ ∑ a ∈ S P S ( a ) 2 U ( a ) P S [ 2 ] ( a ) , − ∑ a ∈ S P S ′ ( a ) 2 U ( a ) P S ′′ ( a ) , q even , q odd . Substituting into (16) , with ϵ = 1 \epsilon= 1 ϵ = 1 or 2 2 2 as appropriate, proves (14) and (15) . Finally, Φ \Phi Φ is homogeneous of degree ϵ ( k − 1 ) \epsilon(k - 1) ϵ ( k − 1 ) , so Φ 1 \Phi_1 Φ 1 is either zero or homogeneous of coefficient degree ϵ ( k − 1 ) − 1 \epsilon(k - 1) - 1 ϵ ( k − 1 ) − 1 , as claimed.
Deep-Hole Classification via Differential Rigidity
In this section, we derive differential constraints on U U U by fixing k − 2 k-2 k − 2 roots and varying the remaining one in Proposition 3.7 . These constraints yield the deep-hole classification for 3 ≤ k ≤ q / 2 3 \le k \le q/2 3 ≤ k ≤ q /2 when q q q is even, and for 3 ≤ k ≤ ( q − 1 ) / 2 3 \le k \le(q-1)/2 3 ≤ k ≤ ( q − 1 ) /2 with q > 3 ( k − 1 ) q > 3(k-1) q > 3 ( k − 1 ) when q q q is odd.
For polynomials P , U ∈ F q [ X ] P,U \in\mathbb{F}_q[X] P , U ∈ F q [ X ] , write
W P ( U ) = P U ′ − P ′ U . W_P(U)=PU'-P'U. W P ( U ) = P U ′ − P ′ U .
In characteristic two this is the ordinary derivative of P U PU P U :
W P ( U ) = ( P U ) ′ . W_P(U)=(PU)'. W P ( U ) = ( P U ) ′ .
Differential Constraints for Deep Holes
Let U U U be the canonical representative of a deep hole under the hypotheses of Proposition 3.7 . Fix a set B ⊆ F q B \subseteq\mathbb{F}_q B ⊆ F q of size k − 2 k-2 k − 2 and put P = P B P=P_B P = P B . The polynomial P ( Y ) ( Y − X ) P(Y)(Y-X) P ( Y ) ( Y − X ) has degree k − 1 k-1 k − 1 in Y Y Y and depends affinely on X X X through its coefficients. Evaluating Φ 1 \Phi_1 Φ 1 at this coefficient vector therefore defines a polynomial of controlled degree:
J B ( X ) = { Φ 1 ( P ( Y ) ( Y − X ) ) δ k − 2 ( P ) , q even , Φ 1 ( P ( Y ) ( Y − X ) ) Disc k − 2 ( P ) , q odd . (17) J_B(X)=
\begin{cases}
\dfrac{\Phi_1(P(Y)(Y-X))}{\delta_{k-2}(P)}, & q\ \text{even},\\[6pt]
\dfrac{\Phi_1(P(Y)(Y-X))}{\operatorname{Disc}_{k-2}(P)}, & q\ \text{odd}.
\end{cases} \tag*{(17)} J B ( X ) = ⎩ ⎨ ⎧ δ k − 2 ( P ) Φ 1 ( P ( Y ) ( Y − X )) , Disc k − 2 ( P ) Φ 1 ( P ( Y ) ( Y − X )) , q even , q odd . (17)
The denominators are nonzero, and the coefficient-degree bound for Φ 1 \Phi_1 Φ 1 in Proposition 3.7 implies
deg J B ≤ { k − 2 , q even , 2 k − 3 , q odd . \deg J_B \le
\begin{cases}
k-2, & q\ \text{even},\\
2k-3, & q\ \text{odd}.
\end{cases} deg J B ≤ { k − 2 , 2 k − 3 , q even , q odd .
Apply Proposition 3.7 to S = B ∪ { x } S=B \cup\{x\} S = B ∪ { x } while keeping B B B fixed. The contribution of the moving root x x x produces a Wronskian, whereas the fixed roots contribute a polynomial of bounded degree.
Lemma 4.1. Let q q q be a prime power, 3 ≤ k ≤ q − 2 3 \le k \le q-2 3 ≤ k ≤ q − 2 , and let U ∈ F q [ X ] U \in\mathbb{F}_q[X] U ∈ F q [ X ] , deg U < q \deg U < q deg U < q , be the canonical representative of a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) . Suppose q ≥ ( ϵ + 1 ) ( k − 1 ) q \ge(\epsilon+1)(k-1) q ≥ ( ϵ + 1 ) ( k − 1 ) . For every B ⊆ F q B \subseteq\mathbb{F}_q B ⊆ F q with ∣ B ∣ = k − 2 |B|=k-2 ∣ B ∣ = k − 2 , put P = P B P=P_B P = P B and define J B J_B J B by (17) . Then there is a polynomial K B ∈ F q [ X ] K_B \in\mathbb{F}_q[X] K B ∈ F q [ X ] of degree at most 2 k − 5 2k-5 2 k − 5 such that, for every x ∈ F q ∖ B x \in\mathbb{F}_q \setminus B x ∈ F q ∖ B ,
W P ( U ) ( x ) = P ( x ) J B ( x ) + K B ( x ) ( q even ) , (18) W_P(U)(x)=P(x)J_B(x)+K_B(x) \qquad(q\ \text{even}), \tag*{(18)} W P ( U ) ( x ) = P ( x ) J B ( x ) + K B ( x ) ( q even ) , (18) 2 W P ( U ) ( x ) = J B ( x ) + K B ( x ) ( q odd ) . (19) 2W_P(U)(x)=J_B(x)+K_B(x) \qquad(q\ \text{odd}). \tag*{(19)} 2 W P ( U ) ( x ) = J B ( x ) + K B ( x ) ( q odd ) . (19) In even characteristic the first identity extends to all of F q \mathbb{F}_q F q ; in odd characteristic the second extends to all of F q \mathbb{F}_q F q after multiplication by P ( x ) P(x) P ( x ) .
Proof. Fix B B B and write P = P B P=P_B P = P B . For b ∈ B b \in B b ∈ B , put
R b ( X ) = P ( X ) X − b . R_b(X)=\frac{P(X)}{X-b}. R b ( X ) = X − b P ( X ) .
Thus deg R b = k − 3 \deg R_b=k-3 deg R b = k − 3 and R b ( b ) = P ′ ( b ) R_b(b)=P'(b) R b ( b ) = P ′ ( b ) . For j = k − 2 , k − 1 j=k-2,k-1 j = k − 2 , k − 1 , write D j = δ j D_j=\delta_j D j = δ j in even characteristic and D j = Disc j D_j=\operatorname{Disc}_j D j = Disc j in odd characteristic. Fix x ∈ F q ∖ B x \in\mathbb{F}_q \setminus B x ∈ F q ∖ B and let S = B ∪ { x } S=B\cup\{x\} S = B ∪ { x } , so that P S ( Y ) = P ( Y ) ( Y − x ) P_S(Y)=P(Y)(Y-x) P S ( Y ) = P ( Y ) ( Y − x ) . The root-difference product formulas give
D k − 1 ( P S ) = D k − 2 ( P ) P ( x ) ϵ . D_{k-1}(P_S)=D_{k-2}(P)P(x)^\epsilon. D k − 1 ( P S ) = D k − 2 ( P ) P ( x ) ϵ .
The ordinary and Hasse product rules yield
P S ′ ( x ) = P ( x ) , P S [ 2 ] ( x ) = P ′ ( x ) , P_S'(x)=P(x),\qquad P_S^{[2]}(x)=P'(x), P S ′ ( x ) = P ( x ) , P S [ 2 ] ( x ) = P ′ ( x ) ,
P S ′ ( b ) = ( b − x ) P ′ ( b ) , P S [ 2 ] ( b ) = ( b − x ) P [ 2 ] ( b ) + P ′ ( b ) ( b ∈ B ) . P_S'(b)=(b-x)P'(b),\qquad P_S^{[2]}(b)=(b-x)P^{[2]}(b)+P'(b)\quad(b\in B). P S ′ ( b ) = ( b − x ) P ′ ( b ) , P S [ 2 ] ( b ) = ( b − x ) P [ 2 ] ( b ) + P ′ ( b ) ( b ∈ B ) .
In both characteristics, Proposition 3.7 can be written in the unified form
Φ 1 ( P S ) D k − 1 ( P S ) = ϵ ∑ a ∈ S ( U ′ ( a ) P S ′ ( a ) − U ( a ) P S [ 2 ] ( a ) P S ′ ( a ) 2 ) . \frac{\Phi_1(P_S)}{D_{k-1}(P_S)}
=\epsilon\sum_{a\in S}\left(\frac{U'(a)}{P_S'(a)}-\frac{U(a)P_S^{[2]}(a)}{P_S'(a)^2}\right). D k − 1 ( P S ) Φ 1 ( P S ) = ϵ a ∈ S ∑ ( P S ′ ( a ) U ′ ( a ) − P S ′ ( a ) 2 U ( a ) P S [ 2 ] ( a ) ) .
Here the even-characteristic formula uses − 1 = 1 -1=1 − 1 = 1 , while the odd-characteristic formula uses P S ′ ′ = 2 P S [ 2 ] P_S''=2P_S^{[2]} P S ′′ = 2 P S [ 2 ] .
The summand corresponding to the moving root x x x is
ϵ ( U ′ ( x ) P ( x ) − U ( x ) P ′ ( x ) P ( x ) 2 ) = ϵ W P ( U ) ( x ) P ( x ) 2 . \epsilon\left(\frac{U'(x)}{P(x)}-\frac{U(x)P'(x)}{P(x)^2}\right)
=\frac{\epsilon\mathcal{W}_P(U)(x)}{P(x)^2}. ϵ ( P ( x ) U ′ ( x ) − P ( x ) 2 U ( x ) P ′ ( x ) ) = P ( x ) 2 ϵ W P ( U ) ( x ) .
For each fixed root b ∈ B b\in B b ∈ B , define
c b = ϵ ( U ′ ( b ) P ′ ( b ) − U ( b ) P [ 2 ] ( b ) P ′ ( b ) 2 ) . c_b=\epsilon\left(\frac{U'(b)}{P'(b)}-\frac{U(b)P^{[2]}(b)}{P'(b)^2}\right). c b = ϵ ( P ′ ( b ) U ′ ( b ) − P ′ ( b ) 2 U ( b ) P [ 2 ] ( b ) ) .
Its contribution is
ϵ ( U ′ ( b ) ( b − x ) P ′ ( b ) − U ( b ) ( ( b − x ) P [ 2 ] ( b ) + P ′ ( b ) ) ( b − x ) 2 P ′ ( b ) 2 ) = c b b − x − ϵ U ( b ) P ′ ( b ) ( b − x ) 2 . \epsilon\left(\frac{U'(b)}{(b-x)P'(b)}-\frac{U(b)((b-x)P^{[2]}(b)+P'(b))}{(b-x)^2P'(b)^2}\right)
=\frac{c_b}{b-x}-\frac{\epsilon U(b)}{P'(b)(b-x)^2}. ϵ ( ( b − x ) P ′ ( b ) U ′ ( b ) − ( b − x ) 2 P ′ ( b ) 2 U ( b ) (( b − x ) P [ 2 ] ( b ) + P ′ ( b )) ) = b − x c b − P ′ ( b ) ( b − x ) 2 ϵ U ( b ) .
By the definition of J B J_B J B in (17) , we therefore obtain, for x ∉ B x\notin B x ∈ / B ,
J B ( x ) P ( x ) ϵ = ϵ W P ( U ) ( x ) P ( x ) 2 + ∑ b ∈ B ( c b b − x − ϵ U ( b ) P ′ ( b ) ( b − x ) 2 ) . (20) \frac{J_B(x)}{P(x)^\epsilon}
=\frac{\epsilon\mathcal{W}_P(U)(x)}{P(x)^2}
+\sum_{b\in B}\left(\frac{c_b}{b-x}-\frac{\epsilon U(b)}{P'(b)(b-x)^2}\right). \tag*{(20)} P ( x ) ϵ J B ( x ) = P ( x ) 2 ϵ W P ( U ) ( x ) + b ∈ B ∑ ( b − x c b − P ′ ( b ) ( b − x ) 2 ϵ U ( b ) ) . (20)
Since P ( x ) / ( b − x ) = − R b ( x ) P(x)/(b-x)=-R_b(x) P ( x ) / ( b − x ) = − R b ( x ) , multiplying by P ( x ) 2 P(x)^2 P ( x ) 2 and rearranging gives
ϵ W P ( U ) ( x ) = P ( x ) 2 − ϵ J B ( x ) + K B ( x ) , \epsilon\mathcal{W}_P(U)(x)=P(x)^{2-\epsilon}J_B(x)+K_B(x), ϵ W P ( U ) ( x ) = P ( x ) 2 − ϵ J B ( x ) + K B ( x ) ,
where
K B ( X ) = P ( X ) ∑ b ∈ B c b R b ( X ) + ϵ ∑ b ∈ B U ( b ) P ′ ( b ) R b ( X ) 2 . K_B(X)=P(X)\sum_{b\in B}c_bR_b(X)+\epsilon\sum_{b\in B}\frac{U(b)}{P'(b)}R_b(X)^2. K B ( X ) = P ( X ) b ∈ B ∑ c b R b ( X ) + ϵ b ∈ B ∑ P ′ ( b ) U ( b ) R b ( X ) 2 .
As deg ( P R b ) = 2 k − 5 \deg(PR_b)=2k-5 deg ( P R b ) = 2 k − 5 and deg R b 2 = 2 k − 6 \deg R_b^2=2k-6 deg R b 2 = 2 k − 6 , we have deg K B ≤ 2 k − 5 \deg K_B\leq2k-5 deg K B ≤ 2 k − 5 .
If q q q is even, then ϵ = 1 \epsilon=1 ϵ = 1 and W P ( U ) = ( P U ) ′ \mathcal{W}_P(U)=(PU)' W P ( U ) = ( P U ) ′ . For b ∈ B b\in B b ∈ B , P ( b ) = 0 P(b)=0 P ( b ) = 0 , R a ( b ) = 0 R_a(b)=0 R a ( b ) = 0 for a ≠ b a\ne b a = b , and R b ( b ) = P ′ ( b ) R_b(b)=P'(b) R b ( b ) = P ′ ( b ) . Consequently,
K B ( b ) = U ( b ) P ′ ( b ) = − P ′ ( b ) U ( b ) = W P ( U ) ( b ) , K_B(b)=U(b)P'(b)=-P'(b)U(b)=\mathcal{W}_P(U)(b), K B ( b ) = U ( b ) P ′ ( b ) = − P ′ ( b ) U ( b ) = W P ( U ) ( b ) ,
where the middle equality uses characteristic two. Thus (18) also holds at every b ∈ B b\in B b ∈ B . If q q q is odd, then ϵ = 2 \epsilon=2 ϵ = 2 ; multiplying the identity by P ( x ) P(x) P ( x ) makes both sides vanish at x ∈ B x\in B x ∈ B . Hence the multiplied form of (19) holds throughout F q \mathbb{F}_q F q .
For 0 ≤ m < q 0 \le m < q 0 ≤ m < q , let
E m = { ev ( H ) : H ∈ F q [ X ] , deg H ≤ m } . \mathcal{E}_m = \{\operatorname{ev}(H) : H \in\mathbb{F}_q[X],\ \deg H \le m\}. E m = { ev ( H ) : H ∈ F q [ X ] , deg H ≤ m } .
Corollary 4.2. Let q q q be a prime power, 3 ≤ k ≤ q − 2 3 \le k \le q - 2 3 ≤ k ≤ q − 2 , and let U ∈ F q [ X ] U \in\mathbb{F}_q[X] U ∈ F q [ X ] , deg U < q \deg U < q deg U < q , be the canonical representative of a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) . Assume q ≥ ( ϵ + 1 ) ( k − 1 ) q \ge(\epsilon+ 1)(k - 1) q ≥ ( ϵ + 1 ) ( k − 1 ) and fix any B ⊆ F q B \subseteq\mathbb{F}_q B ⊆ F q with ∣ B ∣ = k − 2 |B| = k - 2 ∣ B ∣ = k − 2 . In even characteristic,
ev ( W P B ( U ) ) ∈ E 2 k − 4 , (21) \operatorname{ev}(\mathcal{W}_{P_B}(U)) \in\mathcal{E}_{2k-4}, \tag*{(21)} ev ( W P B ( U )) ∈ E 2 k − 4 , (21) whereas in odd characteristic,
ev ( P B W P B ( U ) ) ∈ E 3 k − 5 . (22) \operatorname{ev}(P_B\mathcal{W}_{P_B}(U)) \in\mathcal{E}_{3k-5}. \tag*{(22)} ev ( P B W P B ( U )) ∈ E 3 k − 5 . (22) In characteristic two, (21) is equivalently written as ev ( ( P B U ) ′ ) ∈ E 2 k − 4 \operatorname{ev}((P_B U)') \in\mathcal{E}_{2k-4} ev (( P B U ) ′ ) ∈ E 2 k − 4 .
Proof. The hypotheses ensure 2 k − 4 < q 2k - 4 < q 2 k − 4 < q in even characteristic and 3 k − 5 < q 3k - 5 < q 3 k − 5 < q in odd characteristic. In even characteristic, the first identity in Lemma 4.1 holds at every element of F q \mathbb{F}_q F q , and
deg ( P B J B ) ≤ 2 k − 4 , deg K B ≤ 2 k − 5. \deg(P_B J_B) \le2k - 4,\qquad\deg K_B \le2k - 5. deg ( P B J B ) ≤ 2 k − 4 , deg K B ≤ 2 k − 5.
This proves (21) . In odd characteristic, multiply the second identity by P B P_B P B . The resulting equality holds on the whole field, and
deg ( P B ( J B + K B ) ) ≤ 3 k − 5. \deg(P_B(J_B + K_B)) \le3k - 5. deg ( P B ( J B + K B )) ≤ 3 k − 5.
Since 2 2 2 is invertible, (22) follows. These are equalities of polynomial functions; no equality of formal polynomials is asserted.
The following spanning lemma extends these constraints from root polynomials to all polynomials of the required degrees.
Lemma 4.3. Let q q q be a prime power, p = char F q p = \operatorname{char}\mathbb{F}_q p = char F q , and let 1 ≤ d < p 1 \le d < p 1 ≤ d < p and r ≥ 0 r \ge0 r ≥ 0 be integers. If q ≥ r + d q \ge r + d q ≥ r + d , then
span F q { P B d : B ⊆ F q , ∣ B ∣ = r } = F q [ X ] ≤ d r . \operatorname{span}_{\mathbb{F}_q}\{P_B^d : B \subseteq\mathbb{F}_q,\ |B| = r\} = \mathbb{F}_q[X]_{\le dr}. span F q { P B d : B ⊆ F q , ∣ B ∣ = r } = F q [ X ] ≤ d r .
Proof. Suppose a linear functional ℓ : F q [ X ] ≤ d r → F q \ell: \mathbb{F}_q[X]_{\le dr} \to\mathbb{F}_q ℓ : F q [ X ] ≤ d r → F q vanishes on P B d P_B^d P B d for every r r r -subset B B B . Then
F ( a 0 , … , a r ) = ℓ ( ( ∑ i = 0 r a i X i ) d ) F(a_0,\ldots,a_r) = \ell\left(\left(\sum_{i=0}^{r} a_i X^i\right)^d\right) F ( a 0 , … , a r ) = ℓ ( i = 0 ∑ r a i X i ) d
is a homogeneous form of degree d d d vanishing at all P B P_B P B . Lemma 3.3 , with e = d e = d e = d , gives F ≡ 0 F \equiv0 F ≡ 0 . For each 0 ≤ t ≤ d r 0 \le t \le dr 0 ≤ t ≤ d r , choose nonnegative integers m 0 , … , m r m_0,\ldots,m_r m 0 , … , m r such that ∑ i m i = d \sum_i m_i = d ∑ i m i = d and ∑ i i m i = t \sum_i i m_i = t ∑ i i m i = t . The coefficient of ∏ i a i m i \prod_i a_i^{m_i} ∏ i a i m i in F F F is
( d m 0 , … , m r ) ℓ ( X t ) . \binom{d}{m_0,\ldots,m_r}\ell(X^t). ( m 0 , … , m r d ) ℓ ( X t ) .
Since d < p d < p d < p , this multinomial coefficient is nonzero in F q \mathbb{F}_q F q . Thus ℓ ( X t ) = 0 \ell(X^t) = 0 ℓ ( X t ) = 0 for every t t t , hence ℓ = 0 \ell= 0 ℓ = 0 . The claimed spanning property follows.
Proposition 4.4. Let q q q be a prime power, 3 ≤ k ≤ q − 2 3 \le k \le q - 2 3 ≤ k ≤ q − 2 , and let U ∈ F q [ X ] U \in\mathbb{F}_q[X] U ∈ F q [ X ] , deg U < q \deg U < q deg U < q , be the canonical representative of a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) . Assume q ≥ ( ϵ + 1 ) ( k − 1 ) q \ge(\epsilon+ 1)(k - 1) q ≥ ( ϵ + 1 ) ( k − 1 ) . In even characteristic, every H ∈ F q [ X ] H \in\mathbb{F}_q[X] H ∈ F q [ X ] with deg H ≤ k − 2 \deg H \le k - 2 deg H ≤ k − 2 satisfies
ev ( ( H U ) ′ ) ∈ E 2 k − 4 . (23) \operatorname{ev}((HU)') \in\mathcal{E}_{2k-4}. \tag*{(23)} ev (( H U ) ′ ) ∈ E 2 k − 4 . (23) In odd characteristic, every H ∈ F q [ X ] H \in\mathbb{F}_q[X] H ∈ F q [ X ] with deg H ≤ 2 k − 4 \deg H \le2k - 4 deg H ≤ 2 k − 4 satisfies
ev ( 2 H U ′ − H ′ U ) ∈ E 3 k − 5 . (24) \operatorname{ev}(2HU' - H'U) \in\mathcal{E}_{3k-5}. \tag*{(24)} ev ( 2 H U ′ − H ′ U ) ∈ E 3 k − 5 . (24)
Proof. When q q q is even, the identity W P ( U ) = ( P U ) ′ \mathcal{W}_{P}(U)=(PU)' W P ( U ) = ( P U ) ′ and Corollary 4.2 imply (23) for H = P B H=P_{B} H = P B . By Lemma 4.3 with d = 1 d=1 d = 1 these polynomials span F q [ X ] ≤ k − 2 \mathbb{F}_{q}[X]_{\leq k-2} F q [ X ] ≤ k − 2 , and the map H ↦ ( H U ) ′ H\mapsto(HU)' H ↦ ( H U ) ′ is linear. This proves the first assertion.
When q q q is odd, set H = P B 2 H=P_{B}^{2} H = P B 2 . Then
2 P B W P B ( U ) = 2 H U ′ − H ′ U . 2P_{B}\mathcal{W}_{P_{B}}(U)=2HU'-H'U. 2 P B W P B ( U ) = 2 H U ′ − H ′ U .
The second part of Corollary 4.2 therefore proves (24) for these squares. Since 2 < char F q 2<\operatorname{char}\mathbb{F}_{q} 2 < char F q , Lemma 4.3 with d = 2 d=2 d = 2 shows that they span F q [ X ] ≤ 2 k − 4 \mathbb{F}_{q}[X]_{\leq2k-4} F q [ X ] ≤ 2 k − 4 . Linearity in H H H completes the proof.
The constraints just obtained concern evaluation vectors, not formal polynomial degrees. We compare leading terms below only after verifying that the relevant polynomials have degree less than q q q .
Degree Bounds and Classification
For a canonical polynomial U U U , write u j = [ X j ] U u_j=[X^j]U u j = [ X j ] U for 0 ≤ j < q 0\leq j<q 0 ≤ j < q . We first treat characteristic two.
Lemma 4.5. Let q q q be an even prime power, k ≥ 3 k\geq3 k ≥ 3 , and q ≥ 2 k q\geq2k q ≥ 2 k . Among polynomials U ∈ F q [ X ] U\in\mathbb{F}_{q}[X] U ∈ F q [ X ] with deg U < q \deg U<q deg U < q , the solutions of (23) form exactly F q [ X ] ≤ k \mathbb{F}_{q}[X]_{\leq k} F q [ X ] ≤ k .
Proof. Every U U U of degree at most k k k satisfies the constraint: for deg H ≤ k − 2 \deg H\leq k-2 deg H ≤ k − 2 we have deg ( H U ) ≤ 2 k − 2 \deg(HU)\leq2k-2 deg ( H U ) ≤ 2 k − 2 , and the derivative of its leading term, if its degree is 2 k − 2 2k-2 2 k − 2 , vanishes in characteristic two. Thus deg ( H U ) ′ ≤ 2 k − 4 \deg(HU)'\leq2k-4 deg ( H U ) ′ ≤ 2 k − 4 .
Conversely, let U U U be a nonzero canonical solution and write D = deg U < q D=\deg U<q D = deg U < q . For H = 1 H=1 H = 1 and H = X H=X H = X , the polynomials U ′ U' U ′ and ( X U ) ′ (XU)' ( X U ) ′ have degree less than q q q . Their evaluation constraints therefore imply formal degree bounds. In characteristic two, U ′ U' U ′ detects the odd-degree terms of U U U , while ( X U ) ′ (XU)' ( X U ) ′ detects its even-degree terms; together they imply D ≤ 2 k − 3 D\leq2k-3 D ≤ 2 k − 3 .
If k = 3 k=3 k = 3 , the preliminary bound already gives D ≤ k D\leq k D ≤ k . Suppose henceforth that k ≥ 4 k\geq4 k ≥ 4 . If D ≥ k + 1 D\geq k+1 D ≥ k + 1 , put h = 2 k − 1 − D h=2k-1-D h = 2 k − 1 − D ; then 2 ≤ h ≤ k − 2 2\leq h\leq k-2 2 ≤ h ≤ k − 2 . The leading term of ( X h U ) ′ (X^hU)' ( X h U ) ′ has degree 2 k − 2 < q 2k-2<q 2 k − 2 < q and coefficient
( D + h ) u D = ( 2 k − 1 ) u D = u D ≠ 0 , (D+h)u_D=(2k-1)u_D=u_D\ne0, ( D + h ) u D = ( 2 k − 1 ) u D = u D = 0 ,
contrary to (23) . Hence D ≤ k D\leq k D ≤ k .
The even-characteristic classification follows at once.
Theorem 4.6. Let q q q be an even prime power and 3 ≤ k ≤ q / 2 3\leq k\leq q/2 3 ≤ k ≤ q /2 . Then a vector is a deep hole of RS q ( k ) \operatorname{RS}_{q}(k) RS q ( k ) if and only if its canonical representative has degree k k k .
Proof. Since q ≥ 2 k q\geq2k q ≥ 2 k , the size hypothesis of Proposition 4.4 holds. That proposition and Lemma 4.5 imply deg U ≤ k \deg U\leq k deg U ≤ k for a deep hole. A polynomial of degree less than k k k represents a codeword, so deg U = k \deg U=k deg U = k . The converse is the standard degree-k k k construction.
For odd characteristic, we now assume q > 3 ( k − 1 ) q>3(k-1) q > 3 ( k − 1 ) .
Lemma 4.7. Let q q q be an odd prime power, k ≥ 3 k\geq3 k ≥ 3 , and q > 3 ( k − 1 ) q>3(k-1) q > 3 ( k − 1 ) . Among polynomials U ∈ F q [ X ] U\in\mathbb{F}_{q}[X] U ∈ F q [ X ] with deg U < q \deg U<q deg U < q , the solutions of (24) form
{ F q [ X ] ≤ k , char F q ≠ 3 , F q [ X ] ≤ k + 1 , char F q = 3. \begin{cases}
\mathbb{F}_{q}[X]_{\leq k}, & \operatorname{char}\mathbb{F}_{q}\ne3,\\
\mathbb{F}_{q}[X]_{\leq k+1}, & \operatorname{char}\mathbb{F}_{q}=3.
\end{cases} { F q [ X ] ≤ k , F q [ X ] ≤ k + 1 , char F q = 3 , char F q = 3.
Proof. The indicated spaces satisfy (24) . Indeed, for deg U ≤ k \deg U \le k deg U ≤ k the expression 2 H U ′ − H ′ U 2HU' - H'U 2 H U ′ − H ′ U has degree at most 3 k − 5 3k - 5 3 k − 5 . If deg U = k + 1 \deg U = k + 1 deg U = k + 1 and char F q = 3 \operatorname{char}\mathbb{F}_q = 3 char F q = 3 , the only possible term of degree 3 k − 4 3k - 4 3 k − 4 occurs when deg H = 2 k − 4 \deg H = 2k - 4 deg H = 2 k − 4 . Its coefficient is 6 h 2 k − 4 u k + 1 = 0 6h_{2k-4}u_{k+1} = 0 6 h 2 k − 4 u k + 1 = 0 , where h 2 k − 4 = [ X 2 k − 4 ] H h_{2k-4} = [X^{2k-4}]H h 2 k − 4 = [ X 2 k − 4 ] H .
Conversely, take a nonzero canonical solution U U U and let D = deg U D = \deg U D = deg U . Set M = 3 k − 5 M = 3k - 5 M = 3 k − 5 . For H = 1 H = 1 H = 1 and H = X H = X H = X , the respective candidate leading terms of 2 H U ′ − H ′ U 2HU' - H'U 2 H U ′ − H ′ U have degrees D − 1 , D D - 1, D D − 1 , D and coefficients 2 D u D , ( 2 D − 1 ) u D 2Du_D, (2D - 1)u_D 2 D u D , ( 2 D − 1 ) u D . Both polynomials have degree less than q q q , and these coefficients cannot both vanish. Their evaluation constraints force D ≤ M + 1 D \le M + 1 D ≤ M + 1 .
If D ≥ k + 2 D \ge k + 2 D ≥ k + 2 , put h = M + 2 − D h = M + 2 - D h = M + 2 − D ; then 1 ≤ h ≤ 2 k − 5 1 \le h \le2k - 5 1 ≤ h ≤ 2 k − 5 . For H = X h H = X^h H = X h and H = X h + 1 H = X^{h+1} H = X h + 1 , the candidate leading degrees are M + 1 , M + 2 M + 1, M + 2 M + 1 , M + 2 , with respective coefficients ( 2 D − h ) u D (2D - h)u_D ( 2 D − h ) u D and ( 2 D − h − 1 ) u D (2D - h - 1)u_D ( 2 D − h − 1 ) u D . At least one is nonzero. Since q > 3 ( k − 1 ) q > 3(k - 1) q > 3 ( k − 1 ) , both degrees are less than q q q , contradicting (24) . Thus D ≤ k + 1 D \le k + 1 D ≤ k + 1 .
If D = k + 1 D = k + 1 D = k + 1 , take H = X 2 k − 4 H = X^{2k-4} H = X 2 k − 4 . Its degree-3 k − 4 3k - 4 3 k − 4 coefficient is 6 u D 6u_D 6 u D , which is nonzero unless char F q = 3 \operatorname{char}\mathbb{F}_q = 3 char F q = 3 . This proves the assertion.
Theorem 4.8. Let q q q be an odd prime power, 3 ≤ k ≤ ( q − 1 ) / 2 3 \le k \le(q - 1)/2 3 ≤ k ≤ ( q − 1 ) /2 , and q > 3 ( k − 1 ) q > 3(k - 1) q > 3 ( k − 1 ) . Then a vector is a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) if and only if its canonical representative has degree k k k .
Proof. Let U U U represent a deep hole. By Proposition 4.4 and Lemma 4.7, we have deg U ≤ k \deg U \le k deg U ≤ k , unless char F q = 3 \operatorname{char}\mathbb{F}_q = 3 char F q = 3 and deg U = k + 1 \deg U = k + 1 deg U = k + 1 . The latter possibility is excluded by Li and Zhu [14 Theorem 1] , who proved that every word of degree k + 1 k + 1 k + 1 has distance q − k − 1 q - k - 1 q − k − 1 from RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) in odd characteristic. Hence deg U = k \deg U = k deg U = k , since polynomials of degree less than k k k represent codewords. The converse follows from the degree-k k k construction.
Local Syndromes and Template Uniqueness
In this section, we use global and local syndromes to characterize deep holes, establish the existence and uniqueness of local templates, and derive compatibility identities. These results will be used in Section 6.
Throughout this section, q q q is odd, 3 ≤ k ≤ ( q − 1 ) / 2 3 \le k \le(q - 1)/2 3 ≤ k ≤ ( q − 1 ) /2 , and U U U is the canonical representative of a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) ; no restriction q ≤ 3 ( k − 1 ) q \le3(k - 1) q ≤ 3 ( k − 1 ) is imposed.
A Syndrome Characterization of Deep Holes
Definition 5.1 (Global and local syndromes). Put ν = q − k − 1 \nu= q - k - 1 ν = q − k − 1 . The global syndrome functional of U U U is
Λ U : F q [ X ] ≤ ν ⟶ F q , Λ U ( F ) = ∑ a ∈ F q U ( a ) F ( a ) . \Lambda_U:\mathbb{F}_q[X]_{\le\nu} \longrightarrow\mathbb{F}_q,\qquad\Lambda_U(F) = \sum_{a\in\mathbb{F}_q} U(a)F(a). Λ U : F q [ X ] ≤ ν ⟶ F q , Λ U ( F ) = a ∈ F q ∑ U ( a ) F ( a ) . For 1 ≤ m ≤ ν 1 \le m \le\nu 1 ≤ m ≤ ν and W ⊆ F q W \subseteq\mathbb{F}_q W ⊆ F q with ∣ W ∣ = k + m + 1 |W| = k + m + 1 ∣ W ∣ = k + m + 1 , the local syndrome functional on W W W is
L W : F q [ X ] ≤ m ⟶ F q , L W ( g ) = Λ U ( P F q ∖ W g ) . L_W:\mathbb{F}_q[X]_{\le m} \longrightarrow\mathbb{F}_q,\qquad L_W(g) = \Lambda_U(P_{\mathbb{F}_q\setminus W}g). L W : F q [ X ] ≤ m ⟶ F q , L W ( g ) = Λ U ( P F q ∖ W g ) . This is well defined since ∣ F q ∖ W ∣ + m = ν |\mathbb{F}_q \setminus W| + m = \nu ∣ F q ∖ W ∣ + m = ν .
If f ∈ F q [ X ] f \in\mathbb{F}_q[X] f ∈ F q [ X ] has degree less than k k k and deg F ≤ ν \deg F \le\nu deg F ≤ ν , then
deg ( f F ) ≤ q − 2 , \deg(fF) \le q - 2, deg ( f F ) ≤ q − 2 ,
and hence ∑ a ∈ F q f ( a ) F ( a ) = 0 \sum_{a\in\mathbb{F}_q} f(a)F(a) = 0 ∑ a ∈ F q f ( a ) F ( a ) = 0 by the standard power-sum identities over F q \mathbb{F}_q F q . Thus Λ U \Lambda_U Λ U depends only on the coset of ev ( U ) \operatorname{ev}(U) ev ( U ) modulo RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) .
The deep-hole condition admits a useful formulation in terms of Λ U \Lambda_U Λ U . Let A ⊆ F q A \subseteq\mathbb{F}_q A ⊆ F q have size ν \nu ν , and put
V = F q ∖ A , ∣ V ∣ = k + 1. V = \mathbb{F}_q \setminus A, \qquad|V| = k+1. V = F q ∖ A , ∣ V ∣ = k + 1.
Since
X q − X = P A ( X ) P V ( X ) , X^q-X=P_A(X)P_V(X), X q − X = P A ( X ) P V ( X ) ,
differentiating at v ∈ V v \in V v ∈ V , we obtain
P A ( v ) P V ′ ( v ) = − 1. P_A(v)P'_V(v)=-1. P A ( v ) P V ′ ( v ) = − 1.
Therefore
Λ U ( P A ) = − ∑ v ∈ V U ( v ) P V ′ ( v ) = − [ X k ] I V , (25) \Lambda_U(P_A)=-\sum_{v\in V}\frac{U(v)}{P'_V(v)}=-[X^k]I_V, \tag*{(25)} Λ U ( P A ) = − v ∈ V ∑ P V ′ ( v ) U ( v ) = − [ X k ] I V , (25)
where I V I_V I V is the polynomial of degree at most k k k interpolating U U U on V V V . By (2) ,
ev ( U ) is a deep hole ⟺ Λ U ( P A ) ≠ 0 for every A ∈ ( F q ν ) . (26) \operatorname{ev}(U)\text{ is a deep hole}\quad\Longleftrightarrow\quad\Lambda_U(P_A)\ne0\quad\text{for every }A\in\binom{\mathbb{F}_q}{\nu}. \tag*{(26)} ev ( U ) is a deep hole ⟺ Λ U ( P A ) = 0 for every A ∈ ( ν F q ) . (26)
Fix 1 ≤ m ≤ ν 1\le m\le\nu 1 ≤ m ≤ ν and W ⊆ F q W\subseteq\mathbb{F}_q W ⊆ F q with ∣ W ∣ = k + m + 1 |W|=k+m+1 ∣ W ∣ = k + m + 1 . Differentiating X q − X = P F q ∖ W P W X^q-X=P_{\mathbb{F}_q\setminus W}P_W X q − X = P F q ∖ W P W at x ∈ W x\in W x ∈ W , we find
P F q ∖ W ( x ) = − 1 P W ′ ( x ) . P_{\mathbb{F}_q\setminus W}(x)=-\frac{1}{P'_W(x)}. P F q ∖ W ( x ) = − P W ′ ( x ) 1 .
Hence
L W ( g ) = − ∑ x ∈ W U ( x ) g ( x ) P W ′ ( x ) . (27) L_W(g)=-\sum_{x\in W}\frac{U(x)g(x)}{P'_W(x)}. \tag*{(27)} L W ( g ) = − x ∈ W ∑ P W ′ ( x ) U ( x ) g ( x ) . (27)
More generally, for y = ( y x ) x ∈ W ∈ F q W \mathbf{y}=(y_x)_{x\in W}\in\mathbb{F}_q^W y = ( y x ) x ∈ W ∈ F q W , define
Ψ W ( y ) ( g ) : = − ∑ x ∈ W y x g ( x ) P W ′ ( x ) , g ∈ F q [ X ] ≤ m . \Psi_W(\mathbf{y})(g):=-\sum_{x\in W}\frac{y_xg(x)}{P'_W(x)},\qquad g\in\mathbb{F}_q[X]_{\le m}. Ψ W ( y ) ( g ) := − x ∈ W ∑ P W ′ ( x ) y x g ( x ) , g ∈ F q [ X ] ≤ m .
Thus
Ψ W : F q W ⟶ ( F q [ X ] ≤ m ) ∗ \Psi_W:\mathbb{F}_q^W\longrightarrow\left(\mathbb{F}_q[X]_{\le m}\right)^* Ψ W : F q W ⟶ ( F q [ X ] ≤ m ) ∗
is linear, and
L W = Ψ W ( ( U ( x ) ) x ∈ W ) . L_W=\Psi_W\left((U(x))_{x\in W}\right). L W = Ψ W ( ( U ( x ) ) x ∈ W ) .
Lemma 5.2. Let U U U represent a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) , let 1 ≤ m ≤ q − k − 1 1\le m\le q-k-1 1 ≤ m ≤ q − k − 1 , and let W ⊆ F q W\subseteq\mathbb{F}_q W ⊆ F q have size k + m + 1 k+m+1 k + m + 1 . Then Ψ W \Psi_W Ψ W has rank m + 1 m+1 m + 1 and
ker Ψ W = { ( f ( x ) ) x ∈ W : deg f < k } . \ker\Psi_W=\{(f(x))_{x\in W}:\deg f<k\}. ker Ψ W = {( f ( x ) ) x ∈ W : deg f < k } . Moreover, for every m m m -subset T ⊆ W T\subseteq W T ⊆ W , writing V = W ∖ T V=W\setminus T V = W ∖ T , we have
L W ( P T ) = Λ U ( P ( F q ∖ W ) ∪ T ) = − ∑ v ∈ V U ( v ) P V ′ ( v ) (28) L_W(P_T)=\Lambda_U(P_{(\mathbb{F}_q\setminus W)\cup T})=-\sum_{v\in V}\frac{U(v)}{P'_V(v)} \tag*{(28)} L W ( P T ) = Λ U ( P ( F q ∖ W ) ∪ T ) = − v ∈ V ∑ P V ′ ( v ) U ( v ) (28) = − [ X k ] I V ≠ 0. =-[X^k]I_V\ne0. = − [ X k ] I V = 0. In particular, L W ≠ 0 L_W\ne0 L W = 0 .
Proof. Relative to the monomial basis 1 , X , … , X m 1,X,\ldots,X^m 1 , X , … , X m of F q [ X ] ≤ m \mathbb{F}_q[X]_{\leq m} F q [ X ] ≤ m , the matrix of Ψ W \Psi_W Ψ W is
( − x j P W ′ ( x ) ) 0 ≤ j ≤ m x ∈ W \left(-\frac{x^j}{P'_W(x)}\right)_{\substack{0\leq j\leq m\\x\in W}} ( − P W ′ ( x ) x j ) 0 ≤ j ≤ m x ∈ W
This is a truncated Vandermonde matrix multiplied by an invertible diagonal matrix. Hence
rank Ψ W = m + 1. \operatorname{rank}\Psi_W=m+1. rank Ψ W = m + 1.
If y = ( f ( x ) ) x ∈ W \mathbf{y}=(f(x))_{x\in W} y = ( f ( x ) ) x ∈ W for some deg f < k \deg f<k deg f < k and deg g ≤ m \deg g\leq m deg g ≤ m , then
deg ( f g ) ≤ ( k − 1 ) + m = ∣ W ∣ − 2. \deg(fg)\leq(k-1)+m=|W|-2. deg ( f g ) ≤ ( k − 1 ) + m = ∣ W ∣ − 2.
By (1) ,
Ψ W ( y ) ( g ) = − ∑ x ∈ W f ( x ) g ( x ) P W ′ ( x ) = 0. \Psi_W(\mathbf{y})(g)=-\sum_{x\in W}\frac{f(x)g(x)}{P'_W(x)}=0. Ψ W ( y ) ( g ) = − x ∈ W ∑ P W ′ ( x ) f ( x ) g ( x ) = 0.
Thus the k k k -dimensional space of degree-< k <k < k evaluation vectors on W W W lies in ker Ψ W \ker\Psi_W ker Ψ W . Since
dim ker Ψ W = ∣ W ∣ − ( m + 1 ) = k , \dim\ker\Psi_W=|W|-(m+1)=k, dim ker Ψ W = ∣ W ∣ − ( m + 1 ) = k ,
these two spaces coincide.
Finally, since ∣ F q ∖ W ∣ = ν − m |\mathbb{F}_q\setminus W|=\nu-m ∣ F q ∖ W ∣ = ν − m and T ⊆ W T\subseteq W T ⊆ W , the disjoint union ( F q ∖ W ) ∪ T (\mathbb{F}_q\setminus W)\cup T ( F q ∖ W ) ∪ T has size ν \nu ν . Consequently
L W ( P T ) = Λ U ( P ( F q ∖ W ) ∪ T ) ≠ 0 L_W(P_T)=\Lambda_U\left(P_{(\mathbb{F}_q\setminus W)\cup T}\right)\ne0 L W ( P T ) = Λ U ( P ( F q ∖ W ) ∪ T ) = 0
by (26) . Its complementary set is V = W ∖ T V=W\setminus T V = W ∖ T , so the remaining identities in (28) follow from (25) . □ \square □
Template Characterization and Compatibility Identities
Two types of templates describe the evaluation-type local syndromes.
Definition 5.3. A template is either
a polynomial G ∈ F q [ X ] G\in\mathbb{F}_q[X] G ∈ F q [ X ] of degree exactly k k k , or
a rational function
R ( X ) = f ( X ) + c X − ζ , deg f < k , c ∈ F q × , ζ ∈ F q , R(X)=f(X)+\frac{c}{X-\zeta},\qquad\deg f<k,\quad c\in\mathbb{F}_q^\times,\quad\zeta\in\mathbb{F}_q, R ( X ) = f ( X ) + X − ζ c , deg f < k , c ∈ F q × , ζ ∈ F q , defined on $\mathbb{F}_q\setminus{\zeta}.
For a template R R R , write dom R = F q \operatorname{dom}R=\mathbb{F}_q dom R = F q in the polynomial case and dom R = F q ∖ { ζ } \operatorname{dom}R=\mathbb{F}_q\setminus\{\zeta\} dom R = F q ∖ { ζ } in the case of a template with pole ζ \zeta ζ . Relative to U U U , a subset W ⊆ F q W\subseteq\mathbb{F}_q W ⊆ F q is good if there exists a template R R R , defined on W W W , such that
U ( x ) = R ( x ) ( x ∈ W ) . U(x)=R(x)\qquad(x\in W). U ( x ) = R ( x ) ( x ∈ W ) . Otherwise W W W is bad .
Let 1 ≤ m ≤ ν 1 \le m \le\nu 1 ≤ m ≤ ν , and let W ⊆ F q W \subseteq\mathbb{F}_q W ⊆ F q have size k + m + 1 k+m+1 k + m + 1 . For ζ ∈ F q \zeta\in\mathbb{F}_q ζ ∈ F q , define the evaluation functional
λ ζ ( g ) = g ( ζ ) , g ∈ F q [ X ] ≤ m , \lambda_\zeta(g)=g(\zeta), \qquad g \in\mathbb{F}_q[X]_{\le m}, λ ζ ( g ) = g ( ζ ) , g ∈ F q [ X ] ≤ m ,
and let
λ ∞ ( g ) = [ X m ] g . \lambda_\infty(g)=[X^m]g. λ ∞ ( g ) = [ X m ] g .
With respect to the monomial basis 1 , X , … , X m 1,X,\ldots,X^m 1 , X , … , X m , their projective classes form
C m = { [ 1 : ζ : ⋯ : ζ m ] : ζ ∈ F q } ∪ { [ 0 : ⋯ : 0 : 1 ] } ⊆ PG ( m , q ) . \mathcal{C}_m=\{[1:\zeta:\cdots:\zeta^m]:\zeta\in\mathbb{F}_q\}\cup\{[0:\cdots:0:1]\}\subseteq\operatorname{PG}(m,q). C m = {[ 1 : ζ : ⋯ : ζ m ] : ζ ∈ F q } ∪ {[ 0 : ⋯ : 0 : 1 ]} ⊆ PG ( m , q ) .
Lemma 5.4. Let U U U represent a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) , 1 ≤ m ≤ q − k − 1 1\le m\le q-k-1 1 ≤ m ≤ q − k − 1 , and ∣ W ∣ = k + m + 1 |W|=k+m+1 ∣ W ∣ = k + m + 1 . Then W W W is good if and only if [ L W ] ∈ C m [L_W]\in\mathcal{C}_m [ L W ] ∈ C m .
Proof. The local syndrome is nonzero by Lemma 5.2. By Lagrange interpolation,
Ψ W ( ( x k ) x ∈ W ) = − λ ∞ , \Psi_W\left((x^k)_{x\in W}\right)=-\lambda_\infty, Ψ W ( ( x k ) x ∈ W ) = − λ ∞ ,
Ψ W ( ( 1 x − ζ ) x ∈ W ) = λ ζ P W ( ζ ) , ζ ∉ W . (29) \Psi_W\left(\left(\frac{1}{x-\zeta}\right)_{x\in W}\right)=\frac{\lambda_\zeta}{P_W(\zeta)},\qquad\zeta\notin W. \tag*{(29)} Ψ W ( ( x − ζ 1 ) x ∈ W ) = P W ( ζ ) λ ζ , ζ ∈ / W . (29)
For the first identity, apply (1) to H = X k g H=X^kg H = X k g with deg g ≤ m \deg g\le m deg g ≤ m and ∣ W ∣ = k + m + 1 |W|=k+m+1 ∣ W ∣ = k + m + 1 :
Ψ W ( ( x k ) x ∈ W ) ( g ) = − ∑ x ∈ W x k g ( x ) P W ′ ( x ) = − [ X k + m ] ( X k g ) = − [ X m ] g = − λ ∞ ( g ) . \Psi_W\left((x^k)_{x\in W}\right)(g)
=-\sum_{x\in W}\frac{x^kg(x)}{P_W'(x)}
=-[X^{k+m}](X^kg)=-[X^m]g=-\lambda_\infty(g). Ψ W ( ( x k ) x ∈ W ) ( g ) = − x ∈ W ∑ P W ′ ( x ) x k g ( x ) = − [ X k + m ] ( X k g ) = − [ X m ] g = − λ ∞ ( g ) .
For the second identity, evaluating the Lagrange formula at ζ ∉ W \zeta\notin W ζ ∈ / W yields
g ( ζ ) P W ( ζ ) = ∑ x ∈ W g ( x ) ( ζ − x ) P W ′ ( x ) , \frac{g(\zeta)}{P_W(\zeta)}
=\sum_{x\in W}\frac{g(x)}{(\zeta-x)P_W'(x)}, P W ( ζ ) g ( ζ ) = x ∈ W ∑ ( ζ − x ) P W ′ ( x ) g ( x ) ,
which is precisely (29) .
By Lemma 5.2, the kernel of Ψ W \Psi_W Ψ W consists of evaluations of polynomials of degree less than k k k . Thus the first identity says that [ L W ] = [ λ ∞ ] [L_W]=[\lambda_\infty] [ L W ] = [ λ ∞ ] exactly when U ∣ W U|_W U ∣ W is a nonzero multiple of X k X^k X k plus a polynomial of degree less than k k k . The second says that [ L W ] = [ λ ζ ] [L_W]=[\lambda_\zeta] [ L W ] = [ λ ζ ] , with ζ ∉ W \zeta\notin W ζ ∈ / W , exactly when U ∣ W U|_W U ∣ W is a nonzero multiple of ( X − ζ ) − 1 (X-\zeta)^{-1} ( X − ζ ) − 1 plus such a polynomial. These are precisely the two template types.
Finally, [ L W ] = [ λ ζ ] [L_W]=[\lambda_\zeta] [ L W ] = [ λ ζ ] with ζ ∈ W \zeta\in W ζ ∈ W is impossible: an m m m -subset T ⊆ W T\subseteq W T ⊆ W containing ζ \zeta ζ would satisfy L W ( P T ) = 0 L_W(P_T)=0 L W ( P T ) = 0 , contrary to (28) .
The following intersection bound ensures uniqueness of local templates that agree on at least k + 2 k+2 k + 2 points.
Lemma 5.5. Two distinct templates agree on at most k + 1 k+1 k + 1 points of their common domain.
Proof. Write each template in reduced form N i / D i N_i/D_i N i / D i , with deg N i ≤ k \deg N_i\le k deg N i ≤ k and deg D i ≤ 1 \deg D_i\le1 deg D i ≤ 1 . For distinct templates, N 1 D 2 − N 2 D 1 N_1D_2-N_2D_1 N 1 D 2 − N 2 D 1 is a nonzero polynomial of degree at most k + 1 k+1 k + 1 . Every point of agreement in the common domain is a root of this polynomial.
Although this section concerns odd characteristic and k ≥ 3 k\ge3 k ≥ 3 , the following local algebraic assertion holds for every prime power q q q and every 1 ≤ k ≤ q − 2 1\le k\le q-2 1 ≤ k ≤ q − 2 .
Corollary 5.6. Let U U U be the canonical representative of a deep hole of R S q ( k ) \mathrm{RS}_q(k) RS q ( k ) , with 1 ≤ k ≤ q − 2 1 \le k \le q - 2 1 ≤ k ≤ q − 2 . Every ( k + 2 ) (k + 2) ( k + 2 ) -subset of F q \mathbb{F}_q F q has a unique template agreeing with U U U on that subset.
Proof. The proofs of Lemmas 5.2 , 5.4 , and 5.5 apply without change to every prime power q q q and 1 ≤ k ≤ q − 2 1 \le k \le q - 2 1 ≤ k ≤ q − 2 . For m = 1 m = 1 m = 1 , the evaluation curve C 1 C_1 C 1 is the entire projective line, so existence follows from Lemma 5.4 . Uniqueness follows from Lemma 5.5 .
Local syndromes on overlapping sets satisfy a deletion identity used below to count failed template extensions.
Lemma 5.7. Let $2 \le m \le q - k - 1$, ∣ W ∣ = k + m + 1 |W| = k + m + 1 ∣ W ∣ = k + m + 1 , and z ∈ W z \in W z ∈ W . Then
L W ∖ { z } ( g ) = L W ( ( X − z ) g ) ( deg g ≤ m − 1 ) . (30) L_{W \setminus\{z\}}(g) = L_W((X-z)g) \qquad(\deg g \le m-1). \tag*{(30)} L W ∖ { z } ( g ) = L W (( X − z ) g ) ( deg g ≤ m − 1 ) . (30) Proof. Since
P F q ∖ ( W ∖ { z } ) = ( X − z ) P F q ∖ W , P_{\mathbb{F}_q \setminus(W \setminus\{z\})} = (X-z)P_{\mathbb{F}_q \setminus W}, P F q ∖ ( W ∖ { z }) = ( X − z ) P F q ∖ W , the definition of the local syndrome gives
L W ∖ { z } ( g ) = Λ U ( ( X − z ) P F q ∖ W g ) = L W ( ( X − z ) g ) . L_{W \setminus\{z\}}(g) = \Lambda_U\bigl((X-z)P_{\mathbb{F}_q \setminus W}g\bigr) = L_W((X-z)g). L W ∖ { z } ( g ) = Λ U ( ( X − z ) P F q ∖ W g ) = L W (( X − z ) g ) .
Deep-Hole Classification via Quadratic Obstructions
In this section, we combine local-syndrome compatibility with exact counts of quadratic obstructions to exclude nonexpected deep holes in the remaining odd-characteristic range for q ≥ 41 q \ge41 q ≥ 41 . The small-field cases are treated in § 7 . Unless stated otherwise, throughout this section q q q is an odd prime power, 3 ≤ k ≤ ( q − 1 ) / 2 3 \le k \le(q - 1)/2 3 ≤ k ≤ ( q − 1 ) /2 , and U U U is the canonical representative of a deep hole of R S q ( k ) \mathrm{RS}_q(k) RS q ( k ) .
Counting Quadratic Obstructions
A bad ( k + 3 ) (k + 3) ( k + 3 ) -subset W W W has [ L W ] ∉ C 2 [L_W] \notin C_2 [ L W ] ∈ / C 2 by Lemma 5.4 . We associate with such a syndrome a graph on the evaluation points.
Definition 6.1 (Quadratic obstruction graph). For 0 ≠ L ∈ ( F q [ X ] ≤ 2 ) ∗ 0 \ne L \in(\mathbb{F}_q[X]_{\le2})^* 0 = L ∈ ( F q [ X ] ≤ 2 ) ∗ , let H L \mathcal{H}_L H L be the simple graph on F q \mathbb{F}_q F q whose edges are the unordered pairs { x , y } \{x,y\} { x , y } of distinct elements satisfying L ( ( X − x ) ( X − y ) ) = 0 L((X-x)(X-y)) = 0 L (( X − x ) ( X − y )) = 0 . This graph depends only on the projective class [ L ] = [ a 0 : a 1 : a 2 ] [L] = [a_0 : a_1 : a_2] [ L ] = [ a 0 : a 1 : a 2 ] , where a i = L ( X i ) a_i = L(X^i) a i = L ( X i ) .
Expanding ( X − x ) ( X − y ) (X-x)(X-y) ( X − x ) ( X − y ) gives the edge equation
a 0 x y − a 1 ( x + y ) + a 2 = 0. (31) a_0xy-a_1(x+y)+a_2=0. \tag*{(31)} a 0 x y − a 1 ( x + y ) + a 2 = 0. (31)
For bad W W W , identity (28) shows that W W W is independent in H L W \mathcal{H}_{L_W} H L W . Suppose [ L ] ∉ C 2 [L] \notin C_2 [ L ] ∈ / C 2 , so that a 0 a 2 − a 1 2 ≠ 0 a_0a_2-a_1^2 \ne0 a 0 a 2 − a 1 2 = 0 . If a 0 ≠ 0 a_0 \ne0 a 0 = 0 , normalize a 0 = 1 a_0 = 1 a 0 = 1 and put α = a 1 \alpha= a_1 α = a 1 and Δ = α 2 − a 2 ≠ 0 \Delta= \alpha^2-a_2 \ne0 Δ = α 2 − a 2 = 0 . Then (31) becomes
( x − α ) ( y − α ) = Δ . (x-\alpha)(y-\alpha)=\Delta. ( x − α ) ( y − α ) = Δ.
The vertex α \alpha α is isolated. For each x ≠ α x \ne\alpha x = α , the unique possible neighbor is
σ ( x ) = α + Δ x − α . (32) \sigma(x)=\alpha+\frac{\Delta}{x-\alpha}. \tag*{(32)} σ ( x ) = α + x − α Δ . (32)
Since σ 2 = id \sigma^2=\operatorname{id} σ 2 = id , its two-element orbits form disjoint edges, while its fixed points are isolated, as loops are excluded. The fixed-point equation
( x − α ) 2 = Δ (x-\alpha)^2=\Delta ( x − α ) 2 = Δ
has two solutions if Δ \Delta Δ is a square in F q × \mathbb{F}_q^\times F q × , and none otherwise. Thus H L \mathcal{H}_L H L has three isolated vertices and ( q − 3 ) / 2 (q-3)/2 ( q − 3 ) /2 disjoint edges in the former case, and one isolated vertex and ( q − 1 ) / 2 (q-1)/2 ( q − 1 ) /2 disjoint edges in the latter.
If a 0 = 0 a_0=0 a 0 = 0 , then a 1 ≠ 0 a_1\ne0 a 1 = 0 , and (31) reduces to
x + y = c , c = a 2 a 1 . x+y=c,\qquad c=\frac{a_2}{a_1}. x + y = c , c = a 1 a 2 .
The involution x ↦ c − x x\mapsto c-x x ↦ c − x has the unique fixed point c / 2 c/2 c /2 . Hence H L \mathcal{H}_L H L has one isolated vertex and ( q − 1 ) / 2 (q-1)/2 ( q − 1 ) /2 disjoint edges.
For i ∈ { 1 , 3 } i\in\{1,3\} i ∈ { 1 , 3 } , let N i N_i N i denote the number of non-evaluation projective classes [ L ] [L] [ L ] for which H L \mathcal{H}_L H L has exactly i i i isolated vertices. In the chart a 0 = 1 a_0=1 a 0 = 1 , there are q q q choices of α \alpha α and ( q − 1 ) / 2 (q-1)/2 ( q − 1 ) /2 choices of Δ \Delta Δ of each quadratic character. The chart a 0 = 0 a_0=0 a 0 = 0 contributes another q q q classes, all with one isolated vertex. Consequently,
N 1 = q ( q + 1 ) 2 , N 3 = q ( q − 1 ) 2 . N_1=\frac{q(q+1)}{2},\qquad N_3=\frac{q(q-1)}{2}. N 1 = 2 q ( q + 1 ) , N 3 = 2 q ( q − 1 ) .
and
N 1 + N 3 = q 2 = ∣ PG ( 2 , q ) ∖ C 2 ∣ . N_1+N_3=q^2=\lvert\operatorname{PG}(2,q)\setminus\mathcal{C}_2\rvert. N 1 + N 3 = q 2 = ∣ PG ( 2 , q ) ∖ C 2 ∣ .
We can now count independent subsets in these matchings exactly. For i ∈ { 1 , 3 } i\in\{1,3\} i ∈ { 1 , 3 } , a graph with i i i isolated vertices has ( q − i ) / 2 (q-i)/2 ( q − i ) /2 disjoint edges. An independent w w w -subset containing j j j isolated vertices is obtained by choosing j j j isolated vertices, w − j w-j w − j edges, and one endpoint from each chosen edge. Hence the number of independent w w w -subsets is
A i ( q , w ) = ∑ j = 0 min { i , w } ( i j ) 2 w − j ( ( q − i ) / 2 w − j ) . (33) A_i(q,w)=\sum_{j=0}^{\min\{i,w\}}\binom{i}{j}2^{w-j}\binom{(q-i)/2}{w-j}. \tag*{(33)} A i ( q , w ) = j = 0 ∑ m i n { i , w } ( j i ) 2 w − j ( w − j ( q − i ) /2 ) . (33)
where out-of-range binomial coefficients are zero.
Define
Q ( q , w ) = N 1 A 1 ( q , w ) + N 3 A 3 ( q , w ) ( q w ) , 0 ≤ w ≤ q . (34) Q(q,w)=\frac{N_1A_1(q,w)+N_3A_3(q,w)}{\binom{q}{w}},\qquad0\le w\le q. \tag*{(34)} Q ( q , w ) = ( w q ) N 1 A 1 ( q , w ) + N 3 A 3 ( q , w ) , 0 ≤ w ≤ q . (34)
The formulas (6.2) and (34) , with N 1 = q ( q + 1 ) / 2 N_1=q(q+1)/2 N 1 = q ( q + 1 ) /2 and N 3 = q ( q − 1 ) / 2 N_3=q(q-1)/2 N 3 = q ( q − 1 ) /2 , also define Q ( q , w ) Q(q,w) Q ( q , w ) for every odd integer q ≥ 3 q\ge3 q ≥ 3 . We use this numerical extension in Appendix § 9 ; the finite-geometric interpretation applies when q q q is a prime power. For a uniformly random w w w -subset W ⊆ F q W\subseteq\mathbb{F}_q W ⊆ F q ,
Pr ( W is independent in H L ) = A i ( q , w ) ( q w ) \Pr(W\text{ is independent in }\mathcal{H}_L)=\frac{A_i(q,w)}{\binom{q}{w}} Pr ( W is independent in H L ) = ( w q ) A i ( q , w )
whenever H L \mathcal{H}_L H L has i i i isolated vertices. By linearity of expectation,
Q ( q , w ) = E [ # { [ L ] ∉ C 2 : W is independent in H L } ] . Q(q,w)=\mathbb{E}\left[\#\{[L]\notin\mathcal{C}_2: W\text{ is independent in }\mathcal{H}_L\}\right]. Q ( q , w ) = E [ # {[ L ] ∈ / C 2 : W is independent in H L } ] .
Thus Q ( q , w ) Q(q,w) Q ( q , w ) counts projective classes in expectation and may exceed one.
Lemma 6.2. For each odd prime power q q q , the function Q ( q , w ) Q(q,w) Q ( q , w ) is nonincreasing in $w.
Proof. Let W w + 1 W_{w+1} W w + 1 be a uniformly random ( w + 1 ) (w+1) ( w + 1 ) -subset, and obtain W w W_w W w by deleting a uniformly chosen element. Then W w W_w W w is uniformly distributed among all w w w -subsets. Since independence is preserved under deletion, for every [ L ] ∉ C 2 [L] \notin C_2 [ L ] ∈ / C 2 ,
Pr ( W w + 1 is independent in H L ) ≤ Pr ( W w is independent in H L ) . \operatorname{Pr}(W_{w+1}\text{ is independent in }\mathcal{H}_L) \le\operatorname{Pr}(W_w\text{ is independent in }\mathcal{H}_L). Pr ( W w + 1 is independent in H L ) ≤ Pr ( W w is independent in H L ) .
Summing over these projective classes gives Q ( q , w + 1 ) ≤ Q ( q , w ) Q(q,w+1) \le Q(q,w) Q ( q , w + 1 ) ≤ Q ( q , w ) .
Excluding Nonexpected Deep Holes
The deletion identity in § 5 first shows that distinct failed extensions give distinct quadratic obstructions.
Lemma 6.3. Let q q q be odd, 3 ≤ k ≤ ( q − 1 ) / 2 3 \le k \le(q-1)/2 3 ≤ k ≤ ( q − 1 ) /2 , and let U U U represent a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) . Fix a ( k + 2 ) (k+2) ( k + 2 ) -subset B B B . If z , z ′ ∉ B z,z' \notin B z , z ′ ∈ / B are distinct and both B ∪ { z } B \cup\{z\} B ∪ { z } and B ∪ { z ′ } B \cup\{z'\} B ∪ { z ′ } are bad, then
[ L B ∪ { z } ] ≠ [ L B ∪ { z ′ } ] . [L_{B\cup\{z\}}] \ne[L_{B\cup\{z'\}}]. [ L B ∪ { z } ] = [ L B ∪ { z ′ } ] .
Proof. Write F z = L B ∪ { z } F_z=L_{B\cup\{z\}} F z = L B ∪ { z } and suppose F z = c F z ′ F_z=cF_{z'} F z = c F z ′ for some c ∈ F q × c \in\mathbb{F}_q^\times c ∈ F q × . For every deg g ≤ 1 \deg g \le1 deg g ≤ 1 , applying (30) to both one-point deletions yields
F z ( ( X − z ) g ) = L B ( g ) = F z ′ ( ( X − z ′ ) g ) . F_z((X-z)g)=L_B(g)=F_{z'}((X-z')g). F z (( X − z ) g ) = L B ( g ) = F z ′ (( X − z ′ ) g ) .
Consequently
F z ′ ( ( ( c − 1 ) X + z ′ − c z ) g ) = 0 ( deg g ≤ 1 ) . (35) F_{z'}(((c-1)X+z'-cz)g)=0 \qquad(\deg g \le1). \tag*{(35)} F z ′ ((( c − 1 ) X + z ′ − cz ) g ) = 0 ( deg g ≤ 1 ) . (35)
The linear polynomial in parentheses is nonzero, since z ≠ z ′ z \ne z' z = z ′ . Writing it as α X + β \alpha X+\beta α X + β , with ( α , β ) ≠ ( 0 , 0 ) (\alpha,\beta)\ne(0,0) ( α , β ) = ( 0 , 0 ) , and taking g = 1 , X g=1,X g = 1 , X in (35) , we obtain
( F z ′ ( 1 ) F z ′ ( X ) F z ′ ( X ) F z ′ ( X 2 ) ) ( β α ) = 0. \begin{pmatrix}
F_{z'}(1) & F_{z'}(X) \\
F_{z'}(X) & F_{z'}(X^2)
\end{pmatrix}
\begin{pmatrix}
\beta\\
\alpha
\end{pmatrix}
=0. ( F z ′ ( 1 ) F z ′ ( X ) F z ′ ( X ) F z ′ ( X 2 ) ) ( β α ) = 0.
Thus this Hankel matrix is singular. Writing the moments of F z ′ F_{z'} F z ′ as ( a 0 , a 1 , a 2 ) (a_0,a_1,a_2) ( a 0 , a 1 , a 2 ) , this equality says a 0 a 2 = a 1 2 a_0a_2=a_1^2 a 0 a 2 = a 1 2 . Since F z ′ ≠ 0 F_{z'}\ne0 F z ′ = 0 , it follows that [ F z ′ ] [F_{z'}] [ F z ′ ] lies on C 2 C_2 C 2 : for a 0 ≠ 0 a_0\ne0 a 0 = 0 it is evaluation at a 1 / a 0 a_1/a_0 a 1 / a 0 , and for a 0 = 0 a_0=0 a 0 = 0 it is evaluation at infinity. This contradicts the badness of B ∪ { z ′ } B\cup\{z'\} B ∪ { z ′ } by Lemma 5.4 .
For each ( k + 2 ) (k+2) ( k + 2 ) -subset B ⊆ F q B\subseteq\mathbb{F}_q B ⊆ F q , let R B R_B R B be its unique template, given by Corollary 5.6 , and put
T B = { x ∈ dom R B : U ( x ) = R B ( x ) } . T_B=\{x\in\operatorname{dom}R_B:U(x)=R_B(x)\}. T B = { x ∈ dom R B : U ( x ) = R B ( x )} .
Thus B ⊆ T B B\subseteq T_B B ⊆ T B . To count the quadratic obstructions associated with B B B , define
N ( B ) = # { [ L ] ∈ PG ( 2 , q ) ∖ C 2 : B is independent in H L } . N(B)=\#\{[L]\in\operatorname{PG}(2,q)\setminus C_2:B\text{ is independent in }\mathcal{H}_L\}. N ( B ) = # {[ L ] ∈ PG ( 2 , q ) ∖ C 2 : B is independent in H L } .
Lemma 6.4. Let q q q be odd, 3 ≤ k ≤ ( q − 1 ) / 2 3 \le k \le(q-1)/2 3 ≤ k ≤ ( q − 1 ) /2 , and let U U U represent a deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) . Then, for every ( k + 2 ) (k+2) ( k + 2 ) -subset B B B ,
N ( B ) ≥ q − ∣ T B ∣ . (36) N(B)\ge q-|T_B|. \tag*{(36)} N ( B ) ≥ q − ∣ T B ∣. (36)
Proof. For each z ∈ F q ∖ T B z\in\mathbb{F}_q\setminus T_B z ∈ F q ∖ T B , the extension W z = B ∪ { z } W_z=B\cup\{z\} W z = B ∪ { z } is bad. Indeed, if W z W_z W z admitted a template, it would agree with R B R_B R B on the k + 2 k+2 k + 2 points of B B B and hence coincide with R B R_B R B by Lemma 5.5 . This would force z ∈ T B z\in T_B z ∈ T B , a contradiction. The argument also covers the pole of a rational template, where R B R_B R B is undefined.
Since W z W_z W z is bad, [ L W z ] ∉ C 2 [L_{W_z}] \notin C_2 [ L W z ] ∈ / C 2 . Moreover, by (28) , for distinct x , y ∈ B x,y \in B x , y ∈ B ,
L W z ( ( X − x ) ( X − y ) ) = − [ X k ] I W z ∖ { x , y } ≠ 0. L_{W_z}\bigl((X-x)(X-y)\bigr)=-[X^k]I_{W_z\setminus\{x,y\}}\ne0. L W z ( ( X − x ) ( X − y ) ) = − [ X k ] I W z ∖ { x , y } = 0.
Thus B B B is independent in H L W z \mathcal{H}_{L_{W_z}} H L W z . Consequently, the map
F q ∖ T B ⟶ { [ L ] ∉ C 2 : B is independent in H L } , z ⟼ [ L W z ] \mathbb{F}_q\setminus T_B\longrightarrow\{[L]\notin C_2:B\text{ is independent in }\mathcal{H}_L\},\qquad z\longmapsto[L_{W_z}] F q ∖ T B ⟶ {[ L ] ∈ / C 2 : B is independent in H L } , z ⟼ [ L W z ]
is well defined. It is injective by Lemma 6.3 , which proves (36) .
Lemma 6.5. Let U U U be a nonexpected deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) , where q q q is odd and 3 ≤ k ≤ ( q − 1 ) / 2 3\le k\le(q-1)/2 3 ≤ k ≤ ( q − 1 ) /2 . For k + 3 ≤ w ≤ q k+3\le w\le q k + 3 ≤ w ≤ q , let b w b_w b w denote the proportion of bad w w w -subsets of F q \mathbb{F}_q F q . Then
b w ≥ w q . (37) b_w\ge\frac{w}{q}. \tag*{(37)} b w ≥ q w . (37) Proof. A bad ( w + 1 ) (w+1) ( w + 1 ) -subset contains at most one good w w w -subset. Otherwise, two such good subsets would intersect in w − 1 ≥ k + 2 w-1\ge k+2 w − 1 ≥ k + 2 points. By Lemma 5.5 , their templates would coincide and hence cover their union, contradicting badness.
Thus every bad ( w + 1 ) (w+1) ( w + 1 ) -subset contains at least w w w bad w w w -subsets. Double-counting these inclusions gives
w b w + 1 ( q w + 1 ) ≤ ( q − w ) b w ( q w ) , w b_{w+1}\binom{q}{w+1}\le(q-w)b_w\binom{q}{w}, w b w + 1 ( w + 1 q ) ≤ ( q − w ) b w ( w q ) , and therefore
b w ≥ w w + 1 b w + 1 , k + 3 ≤ w < q . b_w\ge\frac{w}{w+1}b_{w+1},\qquad k+3\le w<q. b w ≥ w + 1 w b w + 1 , k + 3 ≤ w < q . Since U U U is nonexpected, the whole field is bad: a rational template has a pole, while a polynomial template agreeing with U U U everywhere would force deg U = k \deg U=k deg U = k . Hence b q = 1 b_q=1 b q = 1 , and iteration yields
b w ≥ ∏ t = w q − 1 t t + 1 b q = w q . b_w\ge\prod_{t=w}^{q-1}\frac{t}{t+1}b_q=\frac{w}{q}. b w ≥ t = w ∏ q − 1 t + 1 t b q = q w .
The preceding lemmas combine the local multiplicity of quadratic obstructions with the global density of bad subsets.
Theorem 6.6. Let q q q be odd, 3 ≤ k ≤ ( q − 1 ) / 2 3\le k\le(q-1)/2 3 ≤ k ≤ ( q − 1 ) /2 , and let U U U be a nonexpected deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) . Then
Q ( q , k + 2 ) ≥ ( q − k − 2 ) ( k + 3 ) q . (38) Q(q,k+2)\ge\frac{(q-k-2)(k+3)}{q}. \tag*{(38)} Q ( q , k + 2 ) ≥ q ( q − k − 2 ) ( k + 3 ) . (38) If, moreover, every template agrees with U U U at no more than M M M points of its domain, then
Q ( q , k + 2 ) ≥ q − M . (39) Q(q,k+2)\ge q-M. \tag*{(39)} Q ( q , k + 2 ) ≥ q − M . (39) Proof. Put r = k + 2 r=k+2 r = k + 2 . By the proof of Lemma 6.4 , for each r r r -subset B B B and z ∉ B z\notin B z ∈ / B ,
B ∪ { z } is bad ⟺ z ∉ T B . B\cup\{z\}\text{ is bad}\Longleftrightarrow z\notin T_B. B ∪ { z } is bad ⟺ z ∈ / T B .
Every bad ( r + 1 ) (r+1) ( r + 1 ) -subset arises from exactly r + 1 r+1 r + 1 such pairs ( B , z ) (B,z) ( B , z ) . Double-counting gives
1 ( q r ) ∑ ∣ B ∣ = r ( q − ∣ T B ∣ ) = ( r + 1 ) ( q r + 1 ) ( q r ) b r + 1 = ( q − r ) b r + 1 . (40) \begin{aligned}
\frac{1}{\binom{q}{r}}\sum_{\lvert B\rvert=r}(q-\lvert T_B\rvert)=\frac{(r+1)\binom{q}{r+1}}{\binom{q}{r}}b_{r+1} \\
&=(q-r)b_{r+1}. \tag*{(40)}
\end{aligned} ( r q ) 1 ∣ B ∣ = r ∑ ( q − ∣ T B ∣) = ( r q ) ( r + 1 ) ( r + 1 q ) b r + 1 = ( q − r ) b r + 1 . (40)
By the definition of Q Q Q in (34) ,
Q ( q , r ) = 1 ( q r ) ∑ ∣ B ∣ = r N ( B ) . Q(q,r)=\frac{1}{\binom{q}{r}}\sum_{\lvert B\rvert=r}N(B). Q ( q , r ) = ( r q ) 1 ∣ B ∣ = r ∑ N ( B ) .
Averaging (36) and applying (40) and Lemma 6.5, we obtain
Q ( q , r ) ≥ ( q − r ) b r + 1 ≥ ( q − r ) ( r + 1 ) q , Q(q,r)\ge(q-r)b_{r+1}\ge\frac{(q-r)(r+1)}{q}, Q ( q , r ) ≥ ( q − r ) b r + 1 ≥ q ( q − r ) ( r + 1 ) ,
which proves (38) . If ∣ T B ∣ ≤ M \lvert T_B\rvert\le M ∣ T B ∣ ≤ M for every B B B , then
Q ( q , r ) ≥ 1 ( q r ) ∑ ∣ B ∣ = r ( q − ∣ T B ∣ ) ≥ q − M , Q(q,r)\ge\frac{1}{\binom{q}{r}}\sum_{\lvert B\rvert=r}(q-\lvert T_B\rvert)\ge q-M, Q ( q , r ) ≥ ( r q ) 1 ∣ B ∣ = r ∑ ( q − ∣ T B ∣) ≥ q − M ,
proving (39) .
We apply this criterion to odd fields of order at least 41. The exact expression (34) admits the required uniform bound, proved by a recurrence in q q q in Appendix § 9 .
Lemma 6.7. For every odd integer q ≥ 41 q\ge41 q ≥ 41 , put w 0 = ⌈ q / 3 ⌉ + 3 w_0=\lceil q/3\rceil+3 w 0 = ⌈ q /3 ⌉ + 3 . Then
Q ( q , w 0 ) < 9 , (41) Q(q,w_0)<9, \tag*{(41)} Q ( q , w 0 ) < 9 , (41) and for w 0 ≤ r ≤ ( q + 3 ) / 2 w_0\le r\le(q+3)/2 w 0 ≤ r ≤ ( q + 3 ) /2 ,
( q − r ) ( r + 1 ) q > 10. (42) \frac{(q-r)(r+1)}{q}>10. \tag*{(42)} q ( q − r ) ( r + 1 ) > 10. (42)
Theorem 6.8. Let q ≥ 41 q\ge41 q ≥ 41 be an odd prime power and 3 ≤ k ≤ ( q − 1 ) / 2 3\le k\le(q-1)/2 3 ≤ k ≤ ( q − 1 ) /2 . Every deep hole of RS q ( k ) \operatorname{RS}_q(k) RS q ( k ) has interpolation degree k k k .
Proof. For k ≤ ⌈ q / 3 ⌉ k\le\lceil q/3\rceil k ≤ ⌈ q /3 ⌉ we have q > 3 ( k − 1 ) q>3(k-1) q > 3 ( k − 1 ) , so Theorem 4.8 applies. Otherwise put r = k + 2 r=k+2 r = k + 2 and w 0 = ⌈ q / 3 ⌉ + 3 w_0=\lceil q/3\rceil+3 w 0 = ⌈ q /3 ⌉ + 3 . Then w 0 ≤ r ≤ ( q + 3 ) / 2 w_0\le r\le(q+3)/2 w 0 ≤ r ≤ ( q + 3 ) /2 , and Lemma 6.2 yields
Q ( q , r ) ≤ Q ( q , w 0 ) < 9. Q(q,r)\le Q(q,w_0)<9. Q ( q , r ) ≤ Q ( q , w 0 ) < 9.
But a nonexpected deep hole would require
Q ( q , r ) ≥ ( q − r ) ( r + 1 ) q > 10 Q(q,r)\ge\frac{(q-r)(r+1)}{q}>10 Q ( q , r ) ≥ q ( q − r ) ( r + 1 ) > 10
by Theorem 6.6 and Lemma 6.7, a contradiction.
Completion of the Deep-Hole Classification
In this section, we settle the remaining odd extension-field cases q ∈ { 9 , 25 , 27 } q \in\{9,25,27\} q ∈ { 9 , 25 , 27 } and complete the proof of Theorem 1.2 .
For ( q , k ) = ( 27 , 10 ) (q,k)=(27,10) ( q , k ) = ( 27 , 10 ) , we use the following consequence of a restricted-sumset theorem for finite abelian groups.
Lemma 7.1 (Restricted sums and products over F 27 \mathbb{F}_{27} F 27 ). Let A ⊆ F 27 A \subseteq\mathbb{F}_{27} A ⊆ F 27 have size 14. Every element of F 27 \mathbb{F}_{27} F 27 is a sum of four distinct elements of A A A , and also of ten distinct elements of A A A . If A ⊆ F 27 ∗ A \subseteq\mathbb{F}_{27}^{*} A ⊆ F 27 ∗ , every nonzero field element is a product of four distinct elements of A A A , and also of ten distinct elements of A A A .
Proof. Let G G G be either ( F 27 , + ) (\mathbb{F}_{27},+) ( F 27 , + ) or ( F 27 ∗ , ⋅ ) (\mathbb{F}_{27}^{*},\cdot) ( F 27 ∗ , ⋅ ) , using additive notation for both groups in this proof. Their orders are 27 and 26, and the numbers of solutions of 2 g = 0 2g=0 2 g = 0 are 1 and 2, respectively. Thus 2 ∣ A ∣ = ∣ G ∣ + ∣ { g ∈ G : 2 g = 0 } ∣ = 28 2|A|=|G|+|\{g\in G:2g=0\}|=28 2∣ A ∣ = ∣ G ∣ + ∣ { g ∈ G : 2 g = 0 } ∣ = 28 in either case. By Guo’s restricted-sumset theorem [9 Theorem 1] ,
∣ A ( 2 ) ∣ ≥ ∣ G ∣ − 2 , A ( 2 ) = { a + b : a , b ∈ A , a ≠ b } . |A^{(2)}| \ge|G|-2,\qquad A^{(2)}=\{a+b:a,b\in A,\ a\ne b\}. ∣ A ( 2 ) ∣ ≥ ∣ G ∣ − 2 , A ( 2 ) = { a + b : a , b ∈ A , a = b } .
For g ∈ G g\in G g ∈ G , let μ ( g ) \mu(g) μ ( g ) count unordered pairs of distinct elements of A A A whose sum is g g g . Two distinct pairs with the same sum cannot share an element, by cancellation. Hence
μ ( g ) ≤ 7 , ∑ g ∈ G μ ( g ) = ( 14 2 ) = 91. \mu(g)\le7,\qquad\sum_{g\in G}\mu(g)=\binom{14}{2}=91. μ ( g ) ≤ 7 , g ∈ G ∑ μ ( g ) = ( 2 14 ) = 91.
Put P = { g ∈ G : μ ( g ) ≥ 3 } \mathcal{P}=\{g\in G:\mu(g)\ge3\} P = { g ∈ G : μ ( g ) ≥ 3 } . Then
91 ≤ 2 ( ∣ G ∣ − ∣ P ∣ ) + 7 ∣ P ∣ , 91\le2(|G|-|\mathcal{P}|)+7|\mathcal{P}|, 91 ≤ 2 ( ∣ G ∣ − ∣ P ∣ ) + 7∣ P ∣ ,
so ∣ P ∣ ≥ 8 |\mathcal{P}|\ge8 ∣ P ∣ ≥ 8 . In particular,
∣ P ∣ + ∣ A ( 2 ) ∣ ≥ ∣ G ∣ + 6 > ∣ G ∣ . |\mathcal{P}|+|A^{(2)}|\ge|G|+6>|G|. ∣ P ∣ + ∣ A ( 2 ) ∣ ≥ ∣ G ∣ + 6 > ∣ G ∣.
For any g ∈ G g\in G g ∈ G , the sets P \mathcal{P} P and g − A ( 2 ) g-A^{(2)} g − A ( 2 ) therefore intersect. Choose p ∈ P p\in\mathcal{P} p ∈ P with g − p = a 1 + a 2 g-p=a_1+a_2 g − p = a 1 + a 2 for distinct a 1 , a 2 ∈ A a_1,a_2\in A a 1 , a 2 ∈ A . The element p p p has at least three pairwise disjoint two-element representations. At most two of these meet { a 1 , a 2 } \{a_1,a_2\} { a 1 , a 2 } , so we can choose a representation p = a 3 + a 4 p=a_3+a_4 p = a 3 + a 4 with a 1 , a 2 , a 3 , a 4 a_1,a_2,a_3,a_4 a 1 , a 2 , a 3 , a 4 all distinct. Thus every element of G G G is a sum of four distinct elements of A A A .
Taking complements of four-element subsets in A A A , we obtain
{ ∑ a ∈ T a : T ⊆ A , ∣ T ∣ = 10 } = ∑ a ∈ A a − G = G . \left\{\sum_{a\in T}a:T\subseteq A,\ |T|=10\right\}=\sum_{a\in A}a-G=G. { a ∈ T ∑ a : T ⊆ A , ∣ T ∣ = 10 } = a ∈ A ∑ a − G = G .
Interpreting the group law as field addition or multiplication proves the asserted sum and product statements. □
Lemma 7.2. Let U U U be the canonical representative of a nonexpected deep hole of RS 27 ( 10 ) \operatorname{RS}_{27}(10) RS 27 ( 10 ) . Then every template agrees with U U U on at most 13 points of its domain.
Proof. Suppose a polynomial template G G G of degree 10 agrees with U U U on a 14-subset A A A . Let c ≠ 0 c\ne0 c = 0 be the leading coefficient of G G G . Since U U U is nonexpected, there exists z ∉ A z\notin A z ∈ / A such that G ( z ) ≠ U ( z ) G(z)\ne U(z) G ( z ) = U ( z ) . The fourteen elements z − x z-x z − x , x ∈ A x\in A x ∈ A , are distinct and nonzero. By Lemma 7.1 , there is a 10-subset T ⊆ A T\subseteq A T ⊆ A for which
P T ( z ) = ∏ x ∈ T ( z − x ) = G ( z ) − U ( z ) c . P_T(z)=\prod_{x\in T}(z-x)=\frac{G(z)-U(z)}{c}. P T ( z ) = x ∈ T ∏ ( z − x ) = c G ( z ) − U ( z ) .
Then G − c P T G-cP_T G − c P T has degree less than 10 and agrees with U U U on the 11 points of T ∪ { z } T\cup\{z\} T ∪ { z } , contrary to (2) .
Now suppose a pole template
R ( X ) = f ( X ) + c X − ζ , deg f < 10 , c ≠ 0 , R(X)=f(X)+\frac{c}{X-\zeta},\qquad\deg f<10,\qquad c\ne0, R ( X ) = f ( X ) + X − ζ c , deg f < 10 , c = 0 ,
agrees with U U U on a 14-subset A ⊆ F 27 ∖ { ζ } A\subseteq\mathbb{F}_{27}\setminus\{\zeta\} A ⊆ F 27 ∖ { ζ } . Applying Lemma 7.1 to the distinct nonzero elements ( ζ − x ) − 1 (\zeta-x)^{-1} ( ζ − x ) − 1 , x ∈ A x\in A x ∈ A , yields a 10-subset T ⊆ A T\subseteq A T ⊆ A such that
∑ x ∈ T 1 ζ − x = f ( ζ ) − U ( ζ ) c . \sum_{x\in T}\frac{1}{\zeta-x}=\frac{f(\zeta)-U(\zeta)}{c}. x ∈ T ∑ ζ − x 1 = c f ( ζ ) − U ( ζ ) .
The expression
h ( X ) = f ( X ) + c 1 − P T ( X ) / P T ( ζ ) X − ζ h(X)=f(X)+c\frac{1-P_T(X)/P_T(\zeta)}{X-\zeta} h ( X ) = f ( X ) + c X − ζ 1 − P T ( X ) / P T ( ζ )
is a polynomial of degree less than 10: the numerator vanishes at X = ζ X=\zeta X = ζ . Since P T ( x ) = 0 P_T(x)=0 P T ( x ) = 0 for x ∈ T x\in T x ∈ T , it agrees with R = U R=U R = U on T T T . Moreover,
h ( ζ ) = f ( ζ ) − c P T ′ ( ζ ) P T ( ζ ) = f ( ζ ) − c ∑ x ∈ T 1 ζ − x = U ( ζ ) . \begin{aligned}
h(\zeta)=f(\zeta)-c\frac{P_T'(\zeta)}{P_T(\zeta)} \\
&=f(\zeta)-c\sum_{x\in T}\frac{1}{\zeta-x}=U(\zeta).
\end{aligned} h ( ζ ) = f ( ζ ) − c P T ( ζ ) P T ′ ( ζ ) = f ( ζ ) − c x ∈ T ∑ ζ − x 1 = U ( ζ ) .
Thus h h h agrees with U U U at the 11 distinct points of T ∪ { ζ } T\cup\{\zeta\} T ∪ { ζ } , again contradicting (2) .
Corollary 7.3. Every deep hole of R S 27 ( 10 ) \mathrm{RS}_{27}(10) RS 27 ( 10 ) has interpolation degree 10.
Proof. Otherwise Lemma 7.2 and (39) imply Q ( 27 , 12 ) ≥ 14 Q(27,12)\ge14 Q ( 27 , 12 ) ≥ 14 , whereas (34) yields
Q ( 27 , 12 ) = 24576 1955 < 14 , Q(27,12)=\frac{24576}{1955}<14, Q ( 27 , 12 ) = 1955 24576 < 14 ,
a contradiction.
We now combine the preceding results to treat the remaining small extension fields.
Theorem 7.4. For q ∈ { 9 , 25 , 27 } q\in\{9,25,27\} q ∈ { 9 , 25 , 27 } and 3 ≤ k ≤ ( q − 1 ) / 2 3\le k\le(q-1)/2 3 ≤ k ≤ ( q − 1 ) /2 , every deep hole of R S q ( k ) \mathrm{RS}_q(k) RS q ( k ) has interpolation degree k k k .
Proof. Theorem 4.8 covers k ≤ ⌈ q / 3 ⌉ k\le\lceil q/3\rceil k ≤ ⌈ q /3 ⌉ , while Kaipa [10 ] covers k ≥ ( q − 1 ) / 2 k\ge(q-1)/2 k ≥ ( q − 1 ) /2 . In particular, no case remains for q = 9 q=9 q = 9 . The only remaining cases are
( q , k ) ∈ { ( 25 , 10 ) , ( 25 , 11 ) , ( 27 , 10 ) , ( 27 , 11 ) , ( 27 , 12 ) } . (q,k)\in\{(25,10),(25,11),(27,10),(27,11),(27,12)\}. ( q , k ) ∈ {( 25 , 10 ) , ( 25 , 11 ) , ( 27 , 10 ) , ( 27 , 11 ) , ( 27 , 12 )} .
For q = 25 q=25 q = 25 , put r = k + 2 ∈ { 12 , 13 } r=k+2\in\{12,13\} r = k + 2 ∈ { 12 , 13 } . By the monotonicity of Q Q Q ,
Q ( 25 , r ) ≤ Q ( 25 , 12 ) = 42496 7429 < 6 , Q(25,r)\le Q(25,12)=\frac{42496}{7429}<6, Q ( 25 , r ) ≤ Q ( 25 , 12 ) = 7429 42496 < 6 ,
whereas
( 25 − r ) ( r + 1 ) 25 ≥ 168 25 > 6. \frac{(25-r)(r+1)}{25}\ge\frac{168}{25}>6. 25 ( 25 − r ) ( r + 1 ) ≥ 25 168 > 6.
This contradicts (38) for a nonexpected deep hole. For q = 27 q=27 q = 27 , Corollary 7.3 settles k = 10 k=10 k = 10 . For k ∈ { 11 , 12 } k \in\{11,12\} k ∈ { 11 , 12 } , put r = k + 2 ∈ { 13 , 14 } r=k+2 \in\{13,14\} r = k + 2 ∈ { 13 , 14 } . Then
Q ( 27 , r ) ≤ Q ( 27 , 13 ) = 142848 37145 < 4 , Q(27,r) \le Q(27,13) = \frac{142848}{37145} < 4, Q ( 27 , r ) ≤ Q ( 27 , 13 ) = 37145 142848 < 4 ,
while
( 27 − r ) ( r + 1 ) 27 ≥ 65 9 > 4. \frac{(27-r)(r+1)}{27} \ge\frac{65}{9} > 4. 27 ( 27 − r ) ( r + 1 ) ≥ 9 65 > 4.
Again (38) excludes nonexpected deep holes.
Proof of Theorem 1.2. The root bound shows that every degree-k k k canonical polynomial represents a deep hole. Conversely, Theorem 4.6 covers even q q q , and Theorem 6.8 covers odd q ≥ 41 q \ge41 q ≥ 41 . The odd prime fields are settled by Zhuang, Cheng, and Li [18 ] . The only odd proper extension fields below 41 are 9, 25, 27, which are covered by Theorem 7.4 .
Concluding Remarks
In this paper, we have classified the deep holes of full-length Reed–Solomon codes for 3 ≤ k ≤ ⌊ q / 2 ⌋ 3 \le k \le\lfloor q/2 \rfloor 3 ≤ k ≤ ⌊ q /2 ⌋ over every finite field. Together with the earlier high-dimensional classifications, this proves the corrected Cheng–Murray conjecture. The proof uses the full evaluation set in two complementary ways. The marked point determines a boundary section of the tangent envelope, and its first transverse coefficient constrains the interpolation polynomial. Beyond the range of these differential constraints, overlapping local syndromes still impose restrictions: distinct failed template extensions correspond to distinct quadratic obstructions. Compatibility bounds and exact matching counts rule out nonexpected deep holes in the remaining range, while a restricted sum–product argument handles the last small-field case.
A natural next step concerns the primitive Reed–Solomon code RS ( F q × , k ) \operatorname{RS}(\mathbb{F}_q^{\times},k) RS ( F q × , k ) , evaluated at the nonzero field elements. For 2 ≤ k ≤ q − 3 2 \le k \le q-3 2 ≤ k ≤ q − 3 , Wu and Hong [17 ] showed that, besides the expected degree-k k k deep holes, the words represented by a X q − 2 + f ( X ) aX^{q-2}+f(X) a X q − 2 + f ( X ) , where a ∈ F q × a \in\mathbb{F}_q^{\times} a ∈ F q × and deg f < k \deg f < k deg f < k , are also deep holes. They conjectured that these two families are exhaustive when q q q is odd. The analogous classification fails in even characteristic: for q ≥ 8 q \ge8 q ≥ 8 , restricting the k = 2 k=2 k = 2 example U ( X ) = X q / 2 U(X)=X^{q/2} U ( X ) = X q /2 from § 2 to F q × \mathbb{F}_q^{\times} F q × gives an additional deep hole, while for k = q − 4 k=q-4 k = q − 4 the words represented by a X q − 3 + f ( X ) aX^{q-3}+f(X) a X q − 3 + f ( X ) form another family [19 , 10 ] . A complete classification in all characteristics remains a natural problem. The tangent-envelope and local-syndrome methods developed here may offer a route toward its resolution.
More generally, let D ⊆ F q D \subseteq\mathbb{F}_q D ⊆ F q have size n n n , and write RS ( D , k ) \operatorname{RS}(D,k) RS ( D , k ) for the corresponding evaluation code. By the equivalence between deep holes and one-coordinate MDS extensions of the dual code [10 Proposition 1] , the MDS-extension theorem of Seroussi and Roth [16 ] implies that, if 2 ≤ n − k 2 \le n-k 2 ≤ n − k and k ≥ ⌊ ( q − 1 ) / 2 ⌋ k \ge\lfloor(q-1)/2\rfloor k ≥ ⌊( q − 1 ) /2 ⌋ , excluding n − k = 3 n-k=3 n − k = 3 when q q q is even, every deep hole of RS ( D , k ) \operatorname{RS}(D,k) RS ( D , k ) is represented on D D D by one of the functions
a X k + f ( X ) , a X − β + f ( X ) , aX^k+f(X), \qquad\frac{a}{X-\beta}+f(X), a X k + f ( X ) , X − β a + f ( X ) ,
where a ∈ F q × a \in\mathbb{F}_q^{\times} a ∈ F q × , deg f < k \deg f < k deg f < k , and β ∈ F q ∖ D \beta\in\mathbb{F}_q \setminus D β ∈ F q ∖ D in the second case. Classifying deep holes for general D D D when k < ⌊ ( q − 1 ) / 2 ⌋ k < \lfloor(q-1)/2\rfloor k < ⌊( q − 1 ) /2 ⌋ remains an interesting problem, for which the structure of the evaluation set may play an essential role.
Another natural problem is to classify the deep holes of projective Reed–Solomon codes in general dimensions. These codes have length q + 1 q+1 q + 1 , with evaluation at infinity defined as the coefficient of X k − 1 X^{k-1} X k − 1 . Their covering-radius and deep-hole problems are closely related to normal rational curves. Although the deep holes are classified for redundancy at most four [10 , 21 ] , a complete classification in general dimensions remains open. It would be interesting to investigate whether the geometric and local-syndrome methods used here extend to the projective setting.
A Uniform Bound for Quadratic Matching Counts
Proof of Lemma 6.7 . Let q ≥ 41 q \ge41 q ≥ 41 be an odd integer and put w 0 ( q ) = ⌈ q / 3 ⌉ + 3 w_0(q)=\lceil q/3\rceil+3 w 0 ( q ) = ⌈ q /3 ⌉ + 3 . We first derive a closed form for Q ( q , w ) Q(q,w) Q ( q , w ) that is suitable for comparing successive values of q q q .
For i ∈ { 1 , 3 } i \in\{1,3\} i ∈ { 1 , 3 } , the graph counted by A i ( q , w ) A_i(q,w) A i ( q , w ) has i i i isolated vertices and ( q − i ) / 2 (q-i)/2 ( q − i ) /2 disjoint edges. An isolated vertex contributes a factor 1 + t 1+t 1 + t , whereas an edge contributes 1 + 2 t 1+2t 1 + 2 t to the independence polynomial. Thus, by (6.2),
A i ( q , w ) = [ t w ] ( 1 + t ) i ( 1 + 2 t ) ( q − i ) / 2 . A_i(q,w)=[t^w](1+t)^i(1+2t)^{(q-i)/2}. A i ( q , w ) = [ t w ] ( 1 + t ) i ( 1 + 2 t ) ( q − i ) /2 .
where [ t w ] [t^w] [ t w ] denotes the coefficient of t w t^w t w . Setting h = ( q − 3 ) / 2 h=(q-3)/2 h = ( q − 3 ) /2 , and using N 1 = q ( q + 1 ) / 2 N_1=q(q+1)/2 N 1 = q ( q + 1 ) /2 and N 3 = q ( q − 1 ) / 2 N_3=q(q-1)/2 N 3 = q ( q − 1 ) /2 in (34) , we obtain
Q ( q , w ) = q 2 q ( q w ) [ t w ] ( 1 + 2 t ) h ( 2 q + 6 q t + ( 5 q − 1 ) t 2 + ( q − 1 ) t 3 ) . (43) Q(q,w)=\frac{q}{2^{q} \binom{q}{w}}[t^w](1+2t)^h\left(2q+6qt+(5q-1)t^2+(q-1)t^3\right). \tag*{(43)} Q ( q , w ) = 2 q ( w q ) q [ t w ] ( 1 + 2 t ) h ( 2 q + 6 q t + ( 5 q − 1 ) t 2 + ( q − 1 ) t 3 ) . (43)
Assume that 3 ≤ w ≤ ( q + 3 ) / 2 3\le w\le(q+3)/2 3 ≤ w ≤ ( q + 3 ) /2 and put d = h − w + 3 d=h-w+3 d = h − w + 3 . By the binomial theorem, [ t m ] ( 1 + 2 t ) h = 2 m ( h m ) [t^m](1+2t)^h=2^m\binom{h}{m} [ t m ] ( 1 + 2 t ) h = 2 m ( m h ) , where ( h m ) = 0 \binom{h}{m}=0 ( m h ) = 0 for m > h m>h m > h . Hence
[ t w ] ( 1 + 2 t ) h ( 2 q + 6 q t + ( 5 q − 1 ) t 2 + ( q − 1 ) t 3 ) = 2 q [ t w ] ( 1 + 2 t ) h + 6 q [ t w − 1 ] ( 1 + 2 t ) h + ( 5 q − 1 ) [ t w − 2 ] ( 1 + 2 t ) h + ( q − 1 ) [ t w − 3 ] ( 1 + 2 t ) h = 2 q 2 w ( h w ) + 6 q 2 w − 1 ( h w − 1 ) + ( 5 q − 1 ) 2 w − 2 ( h w − 2 ) + ( q − 1 ) 2 w − 3 ( h w − 3 ) = 2 w − 3 ( 16 q ( h w ) + 24 q ( h w − 1 ) + 2 ( 5 q − 1 ) ( h w − 2 ) + ( q − 1 ) ( h w − 3 ) ) . \begin{aligned}
[t^w](1+2t)^h\left(2q+6qt+(5q-1)t^2+(q-1)t^3\right)
={}&2q[t^w](1+2t)^h+6q[t^{w-1}](1+2t)^h\\
&+(5q-1)[t^{w-2}](1+2t)^h+(q-1)[t^{w-3}](1+2t)^h\\
={}&2q\,2^w\binom{h}{w}+6q\,2^{w-1}\binom{h}{w-1}\\
&+(5q-1)2^{w-2}\binom{h}{w-2}+(q-1)2^{w-3}\binom{h}{w-3}\\
={}&2^{w-3}\left(16q\binom{h}{w}+24q\binom{h}{w-1}+2(5q-1)\binom{h}{w-2}+(q-1)\binom{h}{w-3}\right).
\end{aligned} [ t w ] ( 1 + 2 t ) h ( 2 q + 6 q t + ( 5 q − 1 ) t 2 + ( q − 1 ) t 3 ) = = = 2 q [ t w ] ( 1 + 2 t ) h + 6 q [ t w − 1 ] ( 1 + 2 t ) h + ( 5 q − 1 ) [ t w − 2 ] ( 1 + 2 t ) h + ( q − 1 ) [ t w − 3 ] ( 1 + 2 t ) h 2 q 2 w ( w h ) + 6 q 2 w − 1 ( w − 1 h ) + ( 5 q − 1 ) 2 w − 2 ( w − 2 h ) + ( q − 1 ) 2 w − 3 ( w − 3 h ) 2 w − 3 ( 16 q ( w h ) + 24 q ( w − 1 h ) + 2 ( 5 q − 1 ) ( w − 2 h ) + ( q − 1 ) ( w − 3 h ) ) .
The four binomial coefficients can be expressed relative to ( h w − 3 ) \binom{h}{w-3} ( w − 3 h ) using
( h w − 2 ) ( h w − 3 ) = d w − 2 , ( h w − 1 ) ( h w − 3 ) = d ( d − 1 ) ( w − 1 ) ( w − 2 ) , ( h w ) ( h w − 3 ) = d ( d − 1 ) ( d − 2 ) w ( w − 1 ) ( w − 2 ) . \frac{\binom{h}{w-2}}{\binom{h}{w-3}}=\frac{d}{w-2},\qquad
\frac{\binom{h}{w-1}}{\binom{h}{w-3}}=\frac{d(d-1)}{(w-1)(w-2)},\qquad
\frac{\binom{h}{w}}{\binom{h}{w-3}}=\frac{d(d-1)(d-2)}{w(w-1)(w-2)}. ( w − 3 h ) ( w − 2 h ) = w − 2 d , ( w − 3 h ) ( w − 1 h ) = ( w − 1 ) ( w − 2 ) d ( d − 1 ) , ( w − 3 h ) ( w h ) = w ( w − 1 ) ( w − 2 ) d ( d − 1 ) ( d − 2 ) .
Upon substitution, collecting terms over the denominator w ( w − 1 ) ( w − 2 ) w(w-1)(w-2) w ( w − 1 ) ( w − 2 ) and using d = ( q − 2 w + 3 ) / 2 d=(q-2w+3)/2 d = ( q − 2 w + 3 ) /2 yields the factor ( q − 1 ) ( q − w + 1 ) P ( q , w ) (q-1)(q-w+1)P(q,w) ( q − 1 ) ( q − w + 1 ) P ( q , w ) , where
P ( q , w ) = 2 q 2 − 4 q w + 6 q + w 2 − w . P(q,w)=2q^2-4qw+6q+w^2-w. P ( q , w ) = 2 q 2 − 4 q w + 6 q + w 2 − w .
Consequently,
Q ( q , w ) = 2 w − 4 q ( q − 1 ) ( q − w + 1 ) P ( q , w ) w ( w − 1 ) ( w − 2 ) ( ( q − 3 ) / 2 w − 3 ) ( q w ) . (44) Q(q,w)=\frac{2^{w-4}q(q-1)(q-w+1)P(q,w)}{w(w-1)(w-2)}
\frac{\binom{(q-3)/2}{w-3}}{\binom{q}{w}}. \tag*{(44)} Q ( q , w ) = w ( w − 1 ) ( w − 2 ) 2 w − 4 q ( q − 1 ) ( q − w + 1 ) P ( q , w ) ( w q ) ( w − 3 ( q − 3 ) /2 ) . (44)
The choice of the shift ( q , w ) ↦ ( q + 6 , w + 2 ) (q,w)\mapsto(q+6,w+2) ( q , w ) ↦ ( q + 6 , w + 2 ) is dictated by w 0 ( q + 6 ) = w 0 ( q ) + 2 w_0(q+6)=w_0(q)+2 w 0 ( q + 6 ) = w 0 ( q ) + 2 . For this shift, the required binomial ratios are
( h + 3 w − 1 ) ( h w − 3 ) = ( h + 1 ) ( h + 2 ) ( h + 3 ) ( w − 1 ) ( w − 2 ) ( h − w + 4 ) , \frac{\binom{h+3}{w-1}}{\binom{h}{w-3}}
=\frac{(h+1)(h+2)(h+3)}{(w-1)(w-2)(h-w+4)}, ( w − 3 h ) ( w − 1 h + 3 ) = ( w − 1 ) ( w − 2 ) ( h − w + 4 ) ( h + 1 ) ( h + 2 ) ( h + 3 ) ,
( q w ) ( q + 6 w + 2 ) = ( w + 1 ) ( w + 2 ) ∏ i = 1 4 ( q − w + i ) ∏ i = 1 6 ( q + i ) . \frac{\binom{q}{w}}{\binom{q+6}{w+2}}
=\frac{(w+1)(w+2)\prod_{i=1}^{4}(q-w+i)}{\prod_{i=1}^{6}(q+i)}. ( w + 2 q + 6 ) ( w q ) = ∏ i = 1 6 ( q + i ) ( w + 1 ) ( w + 2 ) ∏ i = 1 4 ( q − w + i ) .
Substituting these into the ratio of (A.2), we obtain
Q ( q + 6 , w + 2 ) Q ( q , w ) = ∏ i = 2 5 ( q − w + i ) q ( q + 2 ) ( q + 4 ) ( q − 2 w + 5 ) P ( q + 6 , w + 2 ) P ( q , w ) . (45) \frac{Q(q+6,w+2)}{Q(q,w)}=\frac{\prod_{i=2}^{5}(q-w+i)}{q(q+2)(q+4)(q-2w+5)}\frac{P(q+6,w+2)}{P(q,w)}. \tag*{(45)} Q ( q , w ) Q ( q + 6 , w + 2 ) = q ( q + 2 ) ( q + 4 ) ( q − 2 w + 5 ) ∏ i = 2 5 ( q − w + i ) P ( q , w ) P ( q + 6 , w + 2 ) . (45)
All denominators are positive in the parameter range used below.
We now prove (41) . Since q q q is odd, write q = 6 n + j q=6n+j q = 6 n + j with j ∈ { 1 , 3 , 5 } j\in\{1,3,5\} j ∈ { 1 , 3 , 5 } , and define
R j ( n ) = Q ( 6 n + j + 6 , w 0 ( 6 n + j ) + 2 ) Q ( 6 n + j , w 0 ( 6 n + j ) ) . R_j(n)=\frac{Q(6n+j+6,w_0(6n+j)+2)}{Q(6n+j,w_0(6n+j))}. R j ( n ) = Q ( 6 n + j , w 0 ( 6 n + j )) Q ( 6 n + j + 6 , w 0 ( 6 n + j ) + 2 ) .
For j = 1 , 3 , 5 j=1,3,5 j = 1 , 3 , 5 , the corresponding values of w 0 ( 6 n + j ) w_0(6n+j) w 0 ( 6 n + j ) are 2 n + 4 , 2 n + 4 , 2 n + 5 2n+4,2n+4,2n+5 2 n + 4 , 2 n + 4 , 2 n + 5 , respectively. Substitution into (A.3) gives
R 1 ( n ) = 4 n ( 4 n − 1 ) ( 4 n + 1 ) 3 ( n − 1 ) ( 6 n + 1 ) ( 6 n + 5 ) 14 n 2 + 13 n + 1 14 n 2 − 15 n + 2 , R_1(n)=\frac{4n(4n-1)(4n+1)}{3(n-1)(6n+1)(6n+5)}\frac{14n^2+13n+1}{14n^2-15n+2}, R 1 ( n ) = 3 ( n − 1 ) ( 6 n + 1 ) ( 6 n + 5 ) 4 n ( 4 n − 1 ) ( 4 n + 1 ) 14 n 2 − 15 n + 2 14 n 2 + 13 n + 1 ,
R 3 ( n ) = 4 ( n + 1 ) 2 ( 4 n + 1 ) ( 4 n + 3 ) 3 n 2 ( 6 n + 5 ) ( 6 n + 7 ) 14 n + 15 14 n + 1 , R_3(n)=\frac{4(n+1)^2(4n+1)(4n+3)}{3n^2(6n+5)(6n+7)}\frac{14n+15}{14n+1}, R 3 ( n ) = 3 n 2 ( 6 n + 5 ) ( 6 n + 7 ) 4 ( n + 1 ) 2 ( 4 n + 1 ) ( 4 n + 3 ) 14 n + 1 14 n + 15 ,
R 5 ( n ) = 4 ( n + 1 ) 2 ( 4 n + 3 ) ( 4 n + 5 ) 3 n 2 ( 6 n + 5 ) ( 6 n + 7 ) . R_5(n)=\frac{4(n+1)^2(4n+3)(4n+5)}{3n^2(6n+5)(6n+7)}. R 5 ( n ) = 3 n 2 ( 6 n + 5 ) ( 6 n + 7 ) 4 ( n + 1 ) 2 ( 4 n + 3 ) ( 4 n + 5 ) .
We show that each ratio is less than one in its admissible range.
For R 1 R_1 R 1 , we have n ≥ 7 n\ge7 n ≥ 7 and
n n − 1 ≤ 7 6 , 14 n 2 + 13 n + 1 14 n 2 − 15 n + 2 ≤ 7 5 . \frac{n}{n-1}\le\frac{7}{6},\qquad\frac{14n^2+13n+1}{14n^2-15n+2}\le\frac{7}{5}. n − 1 n ≤ 6 7 , 14 n 2 − 15 n + 2 14 n 2 + 13 n + 1 ≤ 5 7 .
Since ( 4 n − 1 ) / ( 6 n + 1 ) (4n-1)/(6n+1) ( 4 n − 1 ) / ( 6 n + 1 ) and ( 4 n + 1 ) / ( 6 n + 5 ) (4n+1)/(6n+5) ( 4 n + 1 ) / ( 6 n + 5 ) are both less than 2 / 3 2/3 2/3 , we obtain
R 1 ( n ) < 4 3 ⋅ 7 6 ⋅ ( 2 3 ) 2 ⋅ 7 5 = 392 405 < 1. R_1(n)<\frac{4}{3}\cdot\frac{7}{6}\cdot\left(\frac{2}{3}\right)^2\cdot\frac{7}{5}=\frac{392}{405}<1. R 1 ( n ) < 3 4 ⋅ 6 7 ⋅ ( 3 2 ) 2 ⋅ 5 7 = 405 392 < 1.
For R 3 R_3 R 3 , again n ≥ 7 n\ge7 n ≥ 7 , and
n + 1 n ≤ 8 7 , 14 n + 15 14 n + 1 < n + 1 n . \frac{n+1}{n}\le\frac{8}{7},\qquad\frac{14n+15}{14n+1}<\frac{n+1}{n}. n n + 1 ≤ 7 8 , 14 n + 1 14 n + 15 < n n + 1 .
The two remaining linear ratios are less than 2 / 3 2/3 2/3 . Hence
R 3 ( n ) < 4 3 ( 8 7 ) 3 ( 2 3 ) 2 = 8192 9261 < 1. R_3(n)<\frac{4}{3}\left(\frac{8}{7}\right)^3\left(\frac{2}{3}\right)^2=\frac{8192}{9261}<1. R 3 ( n ) < 3 4 ( 7 8 ) 3 ( 3 2 ) 2 = 9261 8192 < 1.
Finally, R 5 R_5 R 5 has n ≥ 6 n\ge6 n ≥ 6 . Then
n + 1 n ≤ 7 6 , 4 n + 3 6 n + 5 < 2 3 , 4 n + 5 6 n + 7 < 3 4 . \frac{n+1}{n}\le\frac{7}{6},\qquad\frac{4n+3}{6n+5}<\frac{2}{3},\qquad\frac{4n+5}{6n+7}<\frac{3}{4}. n n + 1 ≤ 6 7 , 6 n + 5 4 n + 3 < 3 2 , 6 n + 7 4 n + 5 < 4 3 .
Hence
R 5 ( n ) < 4 3 ( 7 6 ) 2 ⋅ 2 3 ⋅ 3 4 = 49 54 < 1. R_5(n)<\frac{4}{3}\left(\frac{7}{6}\right)^2\cdot\frac{2}{3}\cdot\frac{3}{4}=\frac{49}{54}<1. R 5 ( n ) < 3 4 ( 6 7 ) 2 ⋅ 3 2 ⋅ 4 3 = 54 49 < 1.
Thus Q ( q , w 0 ( q ) ) Q(q,w_0(q)) Q ( q , w 0 ( q )) decreases when q q q is increased by six within any odd residue class modulo six. The first admissible values are q = 43 , 45 , 41 q=43,45,41 q = 43 , 45 , 41 for j = 1 , 3 , 5 j=1,3,5 j = 1 , 3 , 5 , respectively, and by (A.2), we have
Q ( 43 , 18 ) = 19103744 4091349 < 5 , Q(43,18)=\frac{19103744}{4091349}<5, Q ( 43 , 18 ) = 4091349 19103744 < 5 ,
Q ( 45 , 18 ) = 476872704 58642669 < 9 , Q(45,18)=\frac{476872704}{58642669}<9, Q ( 45 , 18 ) = 58642669 476872704 < 9 ,
Q ( 41 , 17 ) = 229376 33263 < 7. Q(41,17)=\frac{229376}{33263}<7. Q ( 41 , 17 ) = 33263 229376 < 7.
It follows that Q ( q , w 0 ( q ) ) < 9 Q(q,w_0(q))<9 Q ( q , w 0 ( q )) < 9 for every odd q ≥ 41 q\ge41 q ≥ 41 , proving (41) .
It remains to prove (42) . For fixed q q q , set
T ( r ) = ( q − r ) ( r + 1 ) q . T(r)=\frac{(q-r)(r+1)}{q}. T ( r ) = q ( q − r ) ( r + 1 ) .
Since T ′ ′ ( r ) = − 2 / q < 0 T''(r)=-2/q<0 T ′′ ( r ) = − 2/ q < 0 , the minimum of T T T on [ w 0 ( q ) , ( q + 3 ) / 2 ] [w_0(q),(q+3)/2] [ w 0 ( q ) , ( q + 3 ) /2 ] occurs at an endpoint. Moreover, T ′ ( r ) = ( q − 1 − 2 r ) / q T'(r)=(q-1-2r)/q T ′ ( r ) = ( q − 1 − 2 r ) / q , so T T T is increasing for r ≤ ( q − 1 ) / 2 r\le(q-1)/2 r ≤ ( q − 1 ) /2 . As
q 3 + 3 ≤ w 0 ( q ) < q 3 + 4 ≤ q − 1 2 ( q ≥ 41 ) , \frac{q}{3}+3\le w_0(q)<\frac{q}{3}+4\le\frac{q-1}{2}\qquad(q\ge41), 3 q + 3 ≤ w 0 ( q ) < 3 q + 4 ≤ 2 q − 1 ( q ≥ 41 ) ,
we have
T ( w 0 ( q ) ) ≥ T ( q 3 + 3 ) = 2 q 9 + 5 3 − 12 q ≥ 3869 369 > 10 , T(w_0(q))\ge T\left(\frac{q}{3}+3\right)=\frac{2q}{9}+\frac{5}{3}-\frac{12}{q}\ge\frac{3869}{369}>10, T ( w 0 ( q )) ≥ T ( 3 q + 3 ) = 9 2 q + 3 5 − q 12 ≥ 369 3869 > 10 ,
T ( q + 3 2 ) = q 4 + 1 2 − 15 4 q ≥ 437 41 > 10. T\left(\frac{q+3}{2}\right)=\frac{q}{4}+\frac{1}{2}-\frac{15}{4q}\ge\frac{437}{41}>10. T ( 2 q + 3 ) = 4 q + 2 1 − 4 q 15 ≥ 41 437 > 10.
Both expressions used in the lower bounds are increasing in q q q , and their displayed constants are obtained at q = 41 q=41 q = 41 . Therefore T ( r ) > 10 T(r)>10 T ( r ) > 10 throughout the interval, which proves (42) .
Acknowledgments
This work was supported in part by the National Key Research and Development Program of China under Grant 2022YFA1004900, in part by the National Natural Science Foundation of China under Grant 62571301, and in part by the Shandong Provincial Natural Science Foundation under Grant ZR2025QA05.
AI Declaration
During the preparation of this manuscript, the author used OpenAI’s ChatGPT (GPT-6) to assist with exploratory discussions, checking some of the main proofs, and improving the exposition. The author independently verified the mathematical content and references and takes full responsibility for the manuscript.
References