Introduction
Scalar maximum-distance-separable (MDS) codes are a basic model for storage-optimal erasure protection. An ( n , k ) (n,k) ( n , k ) scalar MDS code over a field K K K stores one K K K -symbol in each of n n n nodes and allows the original k k k information symbols to be recovered from any k k k nodes. Equivalently, it tolerates any n − k n-k n − k node erasures with the minimum possible redundancy. This global recovery property, however, does not ensure communication-efficient repair of an individual failed node. A direct repair procedure downloads one complete K K K -symbol from each of k k k surviving nodes and reconstructs the entire codeword, even though only one symbol is missing.
This inefficiency motivates the array-code viewpoint. In an MDS array code over a base field F F F , each node stores a vector of ℓ \ell ℓ subsymbols, and a helper may transmit functions of its stored vector rather than its entire contents. The regenerating-code framework of Dimakis et al. [1 ] formalizes the resulting tradeoff between storage and repair communication. If a failed node is repaired from d d d helpers and γ \gamma γ denotes the total number of downloaded F F F -symbols, then every MDS array code satisfies the cut-set bound
γ ≥ d ℓ d + 1 − k . (1) \gamma\ge\frac{d\ell}{d+1-k}. \tag*{(1)} γ ≥ d + 1 − k d ℓ . (1)
This work was supported in part by the National Key Research and Development Program of China under Grants 2022YFA1004900 and 2022YFA1005000; by the National Natural Science Foundation of China under Grants 62571298, 62571301, and 62371259; by the Fundamental Research Funds for the Central Universities of China (Nankai University); by the Nankai Zhide Foundation; and by the China Postdoctoral Science Foundation under Grant 2025M773088. (Corresponding author: Jing Qiu.)
Weijun Fang is with the State Key Laboratory of Cryptography and Digital Economy Security, the Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, and the School of Cyber Science and Technology, Shandong University, Qingdao 266237, China (e-mail: fwj@sdu.edu.cn).
Jing Qiu and Shu-Tao Xia are with the Tsinghua Shenzhen International Graduate School, Tsinghua University, Shenzhen, Guangdong 518055, China (e-mails: {jing_qiu, xiast}@sz.tsinghua.edu.cn).
Fang-Wei Fu is with the Chern Institute of Mathematics and LPMC, Nankai University, Tianjin 300071, China (e-mail: fwfu@nankai.edu.cn). An MDS array code attaining equality in (1) is a minimum-storage regenerating (MSR) code. Much of the literature on exact-repair MSR codes has focused on MDS array codes; representative constructions include the product-matrix construction [2 ] and high-rate constructions with optimal repair bandwidth [3 ] . The node size ℓ \ell ℓ , called the subpacketization , determines the granularity available to a repair scheme and is a principal measure of its algebraic and implementation complexity. Fundamental lower bounds on the subpacketization of MSR array codes were developed in [4 , 5 , 6 ] . On the construction side, Liu, Li, and Tang constructed high-rate optimal-access MSR codes over small finite fields [7 ] , while Li, Tang, and Tian developed a generic transformation that, when applied iteratively, enables optimal repair of all nodes with controlled subpacketization [8 ] . Liu, Li, and Tang later extended this line to MDS array codes supporting multiple repair degrees, with smaller subpacketization than earlier multidegree constructions [9 ] . More recently, Wang, Li, Hu, and Ye constructed MSR codes with d = k + 1 d=k+1 d = k + 1 and subpacketization 2 ⌈ n / 3 ⌉ 2^{\lceil n/3\rceil} 2 ⌈ n /3 ⌉ while maintaining a field size linear in n n n [10 ] . With s = d + 1 − k s=d+1-k s = d + 1 − k , Li, Wang, Hu, and Ye subsequently gave, for every admissible repair degree, optimal-access MSR codes over fields of size O s ( n ) O_s(n) O s ( n ) with subpacketization ℓ = s ⌈ n / s ⌉ \ell=s^{\lceil n/s\rceil} ℓ = s ⌈ n / s ⌉ and also non-optimal-access MSR codes with the smaller subpacketization s ⌈ n / ( s + 1 ) ⌉ s^{\lceil n/(s+1)\rceil} s ⌈ n / ( s + 1 )⌉ [11 ] . These developments highlight the central role of subpacketization in general MSR array-code design and motivate the corresponding minimum subpacketization problem for the much more rigid class of scalar Reed-Solomon codes.
Reed-Solomon (RS) codes [12 ] are one of the most important families of scalar MDS codes and are widely used in communication and storage systems. Let F = F q F=\mathbb{F}_q F = F q and K = F q ℓ K=\mathbb{F}_{q^\ell} K = F q ℓ . Although an RS code is a scalar code over K K K , after fixing an F F F -basis of K K K , each symbol in K K K can be represented as a vector in F ℓ F^\ell F ℓ . Thus, the same code can be viewed as an MDS array code over F F F with subpacketization ℓ \ell ℓ . This scalar-to-array viewpoint has also been used more generally in the repair of scalar MDS codes [13 ] .
This viewpoint allows the repair of RS codes to be studied within the regenerating-code framework. However, unlike unrestricted MDS array codes, RS codes are subject to additional algebraic constraints arising from their scalar extension field and polynomial-evaluation structure. Consequently, the repair bandwidth and subpacketization of RS codes have attracted substantial attention. In this paper, we require exact F F F -linear repair of every coordinate from every set of d d d helper nodes with bandwidth meeting the cut-set bound in (1) , and seek the minimum possible extension degree ℓ = [ K : F ] \ell=[K:F] ℓ = [ K : F ] .
Linear Repair of Reed-Solomon Codes
The systematic study of bandwidth-efficient linear repair of scalar RS codes was initiated by Guruswami and Wootters [14 ] . They established a dual-code characterization of exact F F F -linear repair, reducing the design of a repair scheme to the construction of suitable collections of dual codewords, and used trace maps to obtain nontrivial repair schemes for full-length RS codes. Building on this framework, Dau and Milenkovic [15 ] , and later Dau et al. [16 ] , developed optimal repair schemes for additional families of full-length RS codes, including constructions based on subspace polynomials. Here optimality refers to their full-length families and specified redundancy ranges under their linear-repair lower bounds; it need not mean equality in (1) . Li, Wang, and Jafarkhani [17 ] further investigated explicit tradeoffs between repair bandwidth and subpacketization.
A major breakthrough was achieved by Tamo, Ye, and Barg [18 ] , [19 ] , who constructed RS codes attaining the cut-set bound for the repair of any single failed node from any prescribed set of d d d helper nodes. With s = d + 1 − k s=d+1-k s = d + 1 − k , the subpacketization of their construction is
ℓ = s ∏ i = 1 n p ~ i \ell=s\prod_{i=1}^{n}\tilde{p}_i ℓ = s i = 1 ∏ n p ~ i
where p ~ 1 , … , p ~ n \tilde{p}_1,\ldots,\tilde{p}_n p ~ 1 , … , p ~ n are distinct primes satisfying p ~ i ≡ 1 ( m o d s ) \tilde{p}_i\equiv1\pmod{s} p ~ i ≡ 1 ( mod s ) . Their framework also extends to multiple erasures. Subsequent work developed optimal-access and error-resilient repair schemes [20 ] , while near-optimal repair bandwidth with substantially smaller subpacketization was studied in [21 ] .
In our prior work [22 ] , we developed a basis-transformation method for constructing the required repair subspaces for every integer relative extension degree p ≥ s p\ge s p ≥ s , without the congruence restriction p ≡ 1 ( m o d s ) p\equiv1\pmod{s} p ≡ 1 ( mod s ) . Applying this method to the Tamo-Ye-Barg framework, we obtained RS codes attaining the cut-set bound using arbitrary distinct prime degrees p i ≥ s p_i\ge s p i ≥ s .
These constructions establish the existence of cut-set-optimal RS repair schemes, but do not determine the least possible subpacketization: assigning distinct prime degrees is only one way to meet the repair requirements. The present paper studies the minimum over all RS evaluation sets, allowing more general degree assignments and deriving lower bounds that apply to every such code.
Main Results
For a prime power q q q and integers $3 \le k < d \le n - 1$, let ℓ min ( n , k , d ; q ) \ell_{\min}(n,k,d;q) ℓ m i n ( n , k , d ; q ) denote the smallest integer ℓ \ell ℓ for which an ( n , k ) (n,k) ( n , k ) RS code over F q ℓ \mathbb{F}_q^\ell F q ℓ admits cut-set-optimal exact F q \mathbb{F}_q F q -linear repair of every coordinate from every d d d -helper set. Write s = d + 1 − k ≥ 2 s = d + 1 - k \ge2 s = d + 1 − k ≥ 2 .
Our results are expressed in terms of two arithmetic quantities. For m ≥ 1 m \ge1 m ≥ 1 , define
G s ( m ) = min { ∏ i = 1 m g i : g i ∈ Z , g i ≥ s , gcd ( g i , g j ) = 1 for i ≠ j } . G_s(m) = \min\left\{\prod_{i=1}^{m} g_i : g_i \in\mathbb{Z},\ g_i \ge s,\ \gcd(g_i,g_j) = 1\text{ for }i \ne j\right\}. G s ( m ) = min { i = 1 ∏ m g i : g i ∈ Z , g i ≥ s , g cd( g i , g j ) = 1 for i = j } .
with G s ( 0 ) = 1 G_s(0) = 1 G s ( 0 ) = 1 . For 1 ≤ t < N 1 \le t < N 1 ≤ t < N , let Δ s ( N , t ) \Delta_s(N,t) Δ s ( N , t ) be the minimum of lcm ( a 1 , … , a N ) \operatorname{lcm}(a_1,\ldots,a_N) lcm ( a 1 , … , a N ) over positive integers a 1 , … , a N a_1,\ldots,a_N a 1 , … , a N satisfying
lcm ( a j : j ∈ J ∪ { i } ) ≥ s lcm ( a j : j ∈ J ) (2) \operatorname{lcm}(a_j : j \in J \cup\{i\}) \ge s\operatorname{lcm}(a_j : j \in J) \tag*{(2)} lcm ( a j : j ∈ J ∪ { i }) ≥ s lcm ( a j : j ∈ J ) (2)
for every i ∈ [ N ] i \in[N] i ∈ [ N ] and every t t t -subset J ⊆ [ N ] ∖ { i } J \subseteq[N] \setminus\{i\} J ⊆ [ N ] ∖ { i } . The first quantity minimizes a product of pairwise coprime degrees; the second permits shared factors, subject to the relative-degree requirement imposed by every failed-coordinate/helper-set pair. In particular, Δ s ( n , d ) ≤ G s ( n ) \Delta_s(n,d) \le G_s(n) Δ s ( n , d ) ≤ G s ( n ) .
Our principal result determines the minimum subpacketization exactly. For every prime power q q q and all $3 \le k < d \le n - 1$ satisfying d ( d + 2 ) ≥ 4 ( n + 1 ) d(d + 2) \ge4(n + 1) d ( d + 2 ) ≥ 4 ( n + 1 ) , or equivalently d ≥ 4 n + 5 − 1 d \ge\sqrt{4n + 5} - 1 d ≥ 4 n + 5 − 1 , we prove
ℓ min ( n , k , d ; q ) = s Δ s ( n , d ) = s G s ( n ) . (3) \ell_{\min}(n,k,d;q) = s\Delta_s(n,d) = sG_s(n). \tag*{(3)} ℓ m i n ( n , k , d ; q ) = s Δ s ( n , d ) = s G s ( n ) . (3)
Thus the exact formula applies even when the number of helpers is of order n \sqrt{n} n . For full-helper repair (d = n − 1 d = n - 1 d = n − 1 ), this yields
ℓ min ( n , k , n − 1 ; q ) = ( n − k ) G n − k ( n ) , 3 ≤ k < n − 1. \ell_{\min}(n,k,n - 1;q) = (n - k)G_{n-k}(n), \qquad3 \le k < n - 1. ℓ m i n ( n , k , n − 1 ; q ) = ( n − k ) G n − k ( n ) , 3 ≤ k < n − 1.
This settles the exact F q \mathbb{F}_q F q -linear repair case, in the stated dimension range, of Open Problem 20 posed by Ramkumar et al. [23 Open Problem 20] .
The main ingredients of the proof and our further contributions are as follows.
Our lower bounds come from the divisibility and relative-degree constraints imposed by cut-set-optimal repair on the fields generated by projective cross-ratios of the evaluation points. Applying these constraints to a punctured ( d + 1 , k ) (d + 1,k) ( d + 1 , k ) RS code in which every coordinate admits cut-set-optimal full-helper repair yields
ℓ min ( n , k , d ; q ) ≥ s G s ( d + 1 ) . \ell_{\min}(n,k,d;q) \ge sG_s(d + 1). ℓ m i n ( n , k , d ; q ) ≥ s G s ( d + 1 ) .
which strengthens the lower bound of Tamo, Ye, and Barg [18 Theorem 5] for scalar MDS codes when specialized to RS codes. By using the constraints from all failed-coordinate/helper-set pairs, we first establish ℓ min ( n , k , d ; q ) ≥ s Δ s ( n , d ) \ell_{\min}(n,k,d;q) \ge s\Delta_s(n,d) ℓ m i n ( n , k , d ; q ) ≥ s Δ s ( n , d ) for 2 d ≥ n + 3 2d \ge n + 3 2 d ≥ n + 3 . To go beyond this range, we combine compositum identities for cross-ratio fields with a finer analysis of the private and shared prime factors of their degrees. Consequently, we establish ℓ min ( n , k , d ; q ) ≥ s G s ( n ) \ell_{\min}(n,k,d;q) \ge sG_s(n) ℓ m i n ( n , k , d ; q ) ≥ s G s ( n ) whenever d ( d + 2 ) ≥ 4 ( n + 1 ) d(d + 2) \ge4(n + 1) d ( d + 2 ) ≥ 4 ( n + 1 ) .
For the matching upper bound, we extend the distinct-prime constructions to general feasible degree assignments. Our prior work [22 Theorem 3] provides the necessary repair-subspace decomposition for every integer relative degree p ≥ s p \ge s p ≥ s . We show that every tuple satisfying (2) with ( N , t ) = ( n , d ) (N,t) = (n,d) ( N , t ) = ( n , d ) yields an RS code with subpacketization s lcm ( a 1 , … , a n ) s\operatorname{lcm}(a_1,\ldots,a_n) s lcm ( a 1 , … , a n ) that achieves the cut-set bound for every repair configuration. Unlike the earlier constructions with pairwise distinct prime degrees, these tuples may contain composite degrees with shared prime factors. Minimizing over all feasible tuples, we obtain
ℓ min ( n , k , d ; q ) ≤ s Δ s ( n , d ) \ell_{\min}(n,k,d;q) \le s\Delta_s(n,d) ℓ m i n ( n , k , d ; q ) ≤ s Δ s ( n , d )
for every admissible parameter set and every prime power q q q . Together with the lower bounds, this proves (3).
We also study the arithmetic quantity G s ( m ) G_s(m) G s ( m ) appearing in the exact formula. In addition to a finite formula valid for all m m m , we determine the exact threshold for the closed-form expression given below. Let p j p_j p j denote the j j j -th prime, and write p m # = ∏ j = 1 m p j p_m^{\#} = \prod_{j=1}^{m} p_j p m # = ∏ j = 1 m p j for m ≥ 1 m \ge1 m ≥ 1 , with p 0 # = 1 p_0^{\#} = 1 p 0 # = 1 . Also put A s = lcm ( 1 , … , s − 1 ) A_s = \operatorname{lcm}(1,\ldots,s-1) A s = lcm ( 1 , … , s − 1 ) . For s ≥ 3 s \ge3 s ≥ 3 , let u s u_s u s and v s v_s v s be the largest prime and the largest prime power, respectively, strictly below s s s , and set u 2 = v 2 = 1 u_2 = v_2 = 1 u 2 = v 2 = 1 . Then
G s ( m ) = A s p m # ⟺ m ≥ π ( u s v s ) , G_s(m) = A_s p_m^{\#} \quad\Longleftrightarrow\quad m \ge\pi(u_s v_s), G s ( m ) = A s p m # ⟺ m ≥ π ( u s v s ) ,
where π ( x ) \pi(x) π ( x ) counts the primes at most x x x . In particular, G 2 ( m ) = p m # G_2(m) = p_m^{\#} G 2 ( m ) = p m # for every m m m , giving an explicit expression for (3) when s = 2 s = 2 s = 2 .
For fixed k k k and d d d (and any fixed prime power q q q ), we further prove
log ℓ min ( n , k , d ; q ) = Θ k , d ( log n log log n ) ( n → ∞ ) . \log\ell_{\min}(n,k,d;q) = \Theta_{k,d}(\log n \log\log n) \qquad(n \to\infty). log ℓ m i n ( n , k , d ; q ) = Θ k , d ( log n log log n ) ( n → ∞ ) .
The lower bound has leading coefficient ( d − 3 ) / log 2 (d - 3)/\log2 ( d − 3 ) / log 2 , and the matching-order upper bound follows from cover-free families and our degree construction. By comparison, for fixed s s s , the earlier constructions using the smallest admissible distinct prime degrees satisfy log ℓ = Θ ( n log n ) \log\ell= \Theta(n \log n) log ℓ = Θ ( n log n ) .
Finally, the equality ℓ min ( n , k , d ; q ) = s G s ( n ) \ell_{\min}(n,k,d;q) = sG_s(n) ℓ m i n ( n , k , d ; q ) = s G s ( n ) does not hold for all admissible parameters. An affine-plane construction in Appendix B exhibits parameters for which Δ s ( n , d ) < G s ( n ) \Delta_s(n,d) < G_s(n) Δ s ( n , d ) < G s ( n ) and hence ℓ min ( n , k , d ; q ) < s G s ( n ) \ell_{\min}(n,k,d;q) < sG_s(n) ℓ m i n ( n , k , d ; q ) < s G s ( n ) . This distinction suggests that Δ s ( n , d ) \Delta_s(n,d) Δ s ( n , d ) , rather than G s ( n ) G_s(n) G s ( n ) , governs the general problem. We conjecture that
ℓ min ( n , k , d ; q ) = s Δ s ( n , d ) \ell_{\min}(n,k,d;q) = s\Delta_s(n,d) ℓ m i n ( n , k , d ; q ) = s Δ s ( n , d )
for every prime power q q q and all $3 \le k < d \le n - 1$.
Organization
Section II reviews linear repair and the basis-transformation result used in our construction. Section III develops the cross-ratio constraints and proves the general and parameter-dependent lower bounds. Section IV constructs RS codes from feasible degree tuples, establishes (3) , and derives exact formulas for G s ( m ) G_s(m) G s ( m ) . Section V determines the fixed-parameter asymptotic order of the minimum subpacketization. The appendices give auxiliary prime-product estimates and an affine-plane construction exhibiting Δ s ( n , d ) < G s ( n ) \Delta_s(n,d) < G_s(n) Δ s ( n , d ) < G s ( n ) .
Preliminaries
We write Z \mathbb{Z} Z for the integers and [ m ] = { 1 , … , m } [m] = \{1,\ldots,m\} [ m ] = { 1 , … , m } for any positive integer m m m . All logarithms without an explicitly indicated base are natural. Table I summarizes the principal notation; symbols specific to individual arguments are defined where needed.
Table I. Principal notation.
Reed-Solomon Codes and Linear Repair
Throughout, let F = F q ⊆ K = F q ℓ F = \mathbb{F}_{q} \subseteq K = \mathbb{F}_{q^{\ell}} F = F q ⊆ K = F q ℓ and let α 1 , … , α n \alpha_{1},\ldots,\alpha_{n} α 1 , … , α n be pairwise distinct elements of K K K , and put Ω = { α 1 , … , α n } \Omega= \{\alpha_{1},\ldots,\alpha_{n}\} Ω = { α 1 , … , α n } . The Reed-Solomon code with evaluation set Ω \Omega Ω is defined as
C = RS K ( n , k , Ω ) = { ( f ( α 1 ) , … , f ( α n ) ) : f ∈ K [ x ] , deg f < k } . C = \operatorname{RS}_{K}(n,k,\Omega) = \{(f(\alpha_{1}),\ldots,f(\alpha_{n})) : f \in K[x],\ \deg f < k\}. C = RS K ( n , k , Ω ) = {( f ( α 1 ) , … , f ( α n )) : f ∈ K [ x ] , deg f < k } .
Its Euclidean dual, with respect to the inner product ∑ j = 1 n x j y j \sum_{j=1}^{n}x_{j}y_{j} ∑ j = 1 n x j y j , is the generalized RS code
C ⊥ = { ( w 1 g ( α 1 ) , … , w n g ( α n ) ) : g ∈ K [ x ] , deg g < n − k } , C^{\perp} = \{(w_{1}g(\alpha_{1}),\ldots,w_{n}g(\alpha_{n})) : g \in K[x],\ \deg g < n-k\}, C ⊥ = {( w 1 g ( α 1 ) , … , w n g ( α n )) : g ∈ K [ x ] , deg g < n − k } ,
where w j = ∏ t ≠ j ( α j − α t ) − 1 w_{j} = \prod_{t\ne j}(\alpha_{j}-\alpha_{t})^{-1} w j = ∏ t = j ( α j − α t ) − 1 .
Viewing K K K as an ℓ \ell ℓ -dimensional vector space over F F F turns each code coordinate into a node containing ℓ \ell ℓ F F F -symbols. An F F F -linear repair scheme for a failed coordinate i i i downloads F F F -linear functionals of the symbols stored in a helper set H ⊆ [ n ] ∖ { i } H \subseteq[n] \setminus\{i\} H ⊆ [ n ] ∖ { i } and reconstructs the missing element of K K K . For ∣ H ∣ = d |H| = d ∣ H ∣ = d , put
s = d + 1 − k . s = d+1-k. s = d + 1 − k .
The cut-set bound requires any exact repair scheme to download at least d ℓ / s d\ell/s d ℓ / s F F F -symbols in total. We call a repair scheme cut-set optimal if equality holds. Throughout, we require cut-set-optimal F F F -linear repair of every coordinate from every d d d -helper set.
We use the following dual-code characterization of linear repair from [14 Theorem 4] .
Theorem 1 ([14 Theorem 4] ). Let C ⊆ K n C \subseteq K^{n} C ⊆ K n be a scalar linear MDS code with [ K : F ] = ℓ [K:F] = \ell [ K : F ] = ℓ , and fix i ∈ [ n ] i \in[n] i ∈ [ n ] . Then coordinate i i i admits exact F F F -linear repair from the other n − 1 n-1 n − 1 coordinates with bandwidth at most b b b if and only if there exist ℓ \ell ℓ codewords p ( 1 ) , … , p ( ℓ ) ∈ C ⊥ p^{(1)},\ldots,p^{(\ell)} \in C^{\perp} p ( 1 ) , … , p ( ℓ ) ∈ C ⊥ such that
dim F Span F { p i ( t ) : 1 ≤ t ≤ ℓ } = ℓ \dim_{F}\operatorname{Span}_{F}\{p_{i}^{(t)} : 1 \le t \le\ell\} = \ell dim F Span F { p i ( t ) : 1 ≤ t ≤ ℓ } = ℓ and
∑ j ≠ i dim F Span F { p j ( t ) : 1 ≤ t ≤ ℓ } ≤ b . \sum_{j\ne i}\dim_{F}\operatorname{Span}_{F}\{p_{j}^{(t)} : 1 \le t \le\ell\} \le b. j = i ∑ dim F Span F { p j ( t ) : 1 ≤ t ≤ ℓ } ≤ b .
In particular, in the full-helper case d = n − 1 d = n-1 d = n − 1 , if the repair is cut-set optimal and s = n − k s = n-k s = n − k , then the codewords in Theorem 1 satisfy
Span F { p i ( t ) : 1 ≤ t ≤ ℓ } = K \operatorname{Span}_{F}\{p_{i}^{(t)} : 1 \le t \le\ell\} = K Span F { p i ( t ) : 1 ≤ t ≤ ℓ } = K
and
∑ j ≠ i dim F Span F { p j ( t ) : 1 ≤ t ≤ ℓ } = ( n − 1 ) ℓ s . \sum_{j\ne i}\dim_{F}\operatorname{Span}_{F}\{p_{j}^{(t)} : 1 \le t \le\ell\} = \frac{(n-1)\ell}{s}. j = i ∑ dim F Span F { p j ( t ) : 1 ≤ t ≤ ℓ } = s ( n − 1 ) ℓ .
Remark 1. A simple but useful consequence is the following. If coordinate i i i admits cut-set-optimal repair from a d d d -helper set H H H , then puncturing all coordinates outside H ∪ { i } H \cup\{i\} H ∪ { i } yields a length-( d + 1 ) (d+1) ( d + 1 ) MDS code with cut-set-optimal full-helper repair of the same coordinate. The parameter s = d + 1 − k s = d+1-k s = d + 1 − k remains unchanged. This reduction allows us to focus on full-helper repair in many of the subsequent lower-bound arguments.
As in the Introduction, ℓ min ( n , k , d ; q ) \ell_{\min}(n,k,d;q) ℓ m i n ( n , k , d ; q ) denotes the minimum subpacketization for cut-set-optimal F F F -linear repair of every coordinate from every d d d -helper set. Coordinate permutations and nonzero coordinate scalings preserve F F F -linear repair bandwidth. Consequently, a generalized RS code and the ordinary RS code obtained by removing its coordinate multipliers are equivalent for the present purpose.
Finite-Field Degrees and Local Repair Subspaces
Let F ‾ \overline{F} F be an algebraic closure of F F F . For x 1 , … , x t ∈ F ‾ x_{1},\ldots,x_{t} \in\overline{F} x 1 , … , x t ∈ F and every nonempty I ⊆ [ t ] I \subseteq[t] I ⊆ [ t ] , the finite-field compositum formula [24 Chapter 2] gives
[ F ( x i : i ∈ I ) : F ] = lcm ( [ F ( x i ) : F ] : i ∈ I ) . [F(x_{i}:i \in I):F] = \operatorname{lcm}([F(x_{i}):F]:i \in I). [ F ( x i : i ∈ I ) : F ] = lcm ([ F ( x i ) : F ] : i ∈ I ) .
In particular,
F q a F q b = F q lcm ( a , b ) . \mathbb{F}_{q^{a}}\mathbb{F}_{q^{b}} = \mathbb{F}_{q^{\operatorname{lcm}(a,b)}}. F q a F q b = F q lcm ( a , b ) .
For a finite extension K / L K/L K / L and x ∈ K x \in K x ∈ K , write
Tr K / L ( x ) = ∑ j = 0 [ K : L ] − 1 x ∣ L ∣ j . \operatorname{Tr}_{K/L}(x)=\sum_{j=0}^{[K:L]-1}x^{|L|^j}. Tr K / L ( x ) = j = 0 ∑ [ K : L ] − 1 x ∣ L ∣ j .
Finite-field extensions are separable, so the pairing K × K ⟶ L K \times K \longrightarrow L K × K ⟶ L , ( x , y ) ↦ Tr K / L ( x y ) (x,y) \mapsto\operatorname{Tr}_{K/L}(xy) ( x , y ) ↦ Tr K / L ( x y ) , is nondegenerate [24 Chapter 2] .
In the construction of Tamo, Ye, and Barg [19 ] , the evaluation points are assigned distinct prime degrees p ~ i \widetilde{p}_i p i satisfying
p ~ i ≡ 1 ( m o d s ) . \widetilde{p}_i \equiv1 \pmod{s}. p i ≡ 1 ( mod s ) .
This congruence condition is used in constructing the local repair-enabling subspaces and restricts the available degree choices.
Our prior work [22 Theorem 3] removed this restriction by a basis-transformation argument and established the following subspace decomposition for every integer relative degree r ≥ s r \ge s r ≥ s .
Theorem 2 ([22 Theorem 3] ). Let F 0 ⊂ E 0 = F 0 ( α ) ⊂ K 0 F_0 \subset E_0 = F_0(\alpha) \subset K_0 F 0 ⊂ E 0 = F 0 ( α ) ⊂ K 0 be finite fields with
[ E 0 : F 0 ] = r ≥ s = [ K 0 : E 0 ] . [E_0:F_0]=r \ge s=[K_0:E_0]. [ E 0 : F 0 ] = r ≥ s = [ K 0 : E 0 ] . Then there exists an explicitly constructible F 0 F_0 F 0 -subspace S 0 ⊆ K 0 S_0 \subseteq K_0 S 0 ⊆ K 0 satisfying
dim F 0 S 0 = r , K 0 = ⨁ u = 0 s − 1 α u S 0 . \dim_{F_0} S_0=r,\qquad K_0=\bigoplus_{u=0}^{s-1}\alpha^u S_0. dim F 0 S 0 = r , K 0 = u = 0 ⨁ s − 1 α u S 0 .
In Section IV, this result will be applied with the relative extension degree of a failed evaluation point over the field generated by the chosen helpers.
Lower Bounds on Subpacketization
In this section, we establish lower bounds on the subpacketization. We first translate cut-set-optimal repair into degree constraints on cross-ratio fields. Applying these constraints to a punctured ( d + 1 , k ) (d+1,k) ( d + 1 , k ) RS code yields a lower bound valid for all admissible parameters. We then combine the constraints from all helper sets. For 2 d ≥ n + 3 2d \ge n+3 2 d ≥ n + 3 , we obtain the lower bound s Δ s ( n , d ) s\Delta_s(n,d) s Δ s ( n , d ) . Finally, a more detailed analysis of the same degree system yields the stronger bound s G s ( n ) sG_s(n) s G s ( n ) whenever d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2) \ge4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 ) .
Cross-Ratio Constraints
We begin with the full-helper case, which will later be applied to a failed coordinate together with a chosen helper set. Throughout this subsection, assume
d = n − 1 , k ≥ 3 , s = n − k ≥ 2 , d=n-1,\qquad k\ge3,\qquad s=n-k\ge2, d = n − 1 , k ≥ 3 , s = n − k ≥ 2 ,
and write
C = RS K ( n , k , Ω ) , Ω = { α 1 , … , α n } . C=\operatorname{RS}_K(n,k,\Omega),\qquad\Omega=\{\alpha_1,\ldots,\alpha_n\}. C = RS K ( n , k , Ω ) , Ω = { α 1 , … , α n } .
Fix i ∈ [ n ] i \in[n] i ∈ [ n ] and consider cut-set-optimal F F F -linear repair of coordinate i i i . We write K [ x ] < s K[x]_{<s} K [ x ] < s for the space of polynomials over K K K of degree less than s s s , including the zero polynomial. The following lemma records the dimension properties of the evaluation spaces that follow from equality in the cut-set bound. The underlying argument is essentially the one used by Tamo, Ye, and Barg [18 proof of Theorem 5] ; we state it in the polynomial form needed below. See also [19 ] .
Lemma 1. Suppose that the failed coordinate i ∈ [ n ] i \in[n] i ∈ [ n ] , with evaluation point α i \alpha_i α i , admits cut-set-optimal F F F -linear repair from the other n − 1 n-1 n − 1 coordinates. Then s ∣ ℓ s \mid\ell s ∣ ℓ , and there exists an ℓ \ell ℓ -dimensional F F F -subspace P i ⊆ K [ x ] < s \mathcal{P}_i \subseteq K[x]_{<s} P i ⊆ K [ x ] < s whose evaluation spaces, defined for y ∈ K y \in K y ∈ K by
U y : = { f ( y ) : f ∈ P i } , U_y:=\{f(y):f\in\mathcal{P}_i\}, U y := { f ( y ) : f ∈ P i } ,
satisfy U α i = K U_{\alpha_i}=K U α i = K and
dim F U y = ℓ s for every y ∈ Ω ∖ { α i } . \dim_F U_y=\frac{\ell}{s}\quad\text{for every }y\in\Omega\setminus\{\alpha_i\}. dim F U y = s ℓ for every y ∈ Ω ∖ { α i } .
Moreover, for every s s s -subset B = { b 1 , … , b s } ⊆ Ω ∖ { α i } B=\{b_1,\ldots,b_s\}\subseteq\Omega\setminus\{\alpha_i\} B = { b 1 , … , b s } ⊆ Ω ∖ { α i } and every choice of a u ∈ U b u a_u\in U_{b_u} a u ∈ U b u , 1 ≤ u ≤ s 1\le u\le s 1 ≤ u ≤ s , there is an f ∈ P i f\in\mathcal{P}_i f ∈ P i such that f ( b u ) = a u f(b_u)=a_u f ( b u ) = a u for all u u u .
Proof. By Theorem 1 and the dual form of RS codes, choose polynomials f 1 , … , f ℓ ∈ K [ x ] < s f_1,\ldots,f_\ell\in K[x]_{<s} f 1 , … , f ℓ ∈ K [ x ] < s whose values at α i \alpha_i α i form an F F F -basis of K K K and whose helper evaluation spans have total dimension at most ( n − 1 ) ℓ / s (n-1)\ell/s ( n − 1 ) ℓ / s . Nonzero dual multipliers do not change these dimensions. Set
P i = Span F { f 1 , … , f ℓ } . \mathcal{P}_i=\operatorname{Span}_F\{f_1,\ldots,f_\ell\}. P i = Span F { f 1 , … , f ℓ } .
Then dim F P i = ℓ \dim_F\mathcal{P}_i=\ell dim F P i = ℓ and U α i = K U_{\alpha_i}=K U α i = K .
For each helper point y ∈ Ω ∖ { α i } y\in\Omega\setminus\{\alpha_i\} y ∈ Ω ∖ { α i } , put
t y = dim F U y . t_y=\dim_F U_y. t y = dim F U y .
The selected polynomials yield a repair scheme with bandwidth ∑ y t y \sum_y t_y ∑ y t y . The preceding upper bound and the cut-set bound therefore force
∑ y ∈ Ω ∖ { α i } t y = ( n − 1 ) ℓ s . \sum_{y\in\Omega\setminus\{\alpha_i\}}t_y=\frac{(n-1)\ell}{s}. y ∈ Ω ∖ { α i } ∑ t y = s ( n − 1 ) ℓ .
Let B B B be any s s s -subset of the helper points. A polynomial of degree less than s s s is determined by its values on B B B , so evaluation on B B B is injective on P i \mathcal{P}_i P i . Its image has dimension ℓ \ell ℓ and is contained in the space of all tuples with values in U y U_y U y at each y ∈ B y\in B y ∈ B . Hence
ℓ ≤ ∑ y ∈ B t y . (4) \ell\le\sum_{y\in B}t_y. \tag*{(4)} ℓ ≤ y ∈ B ∑ t y . (4)
Summing the nonnegative differences over all such B B B gives
∑ B ⊆ Ω ∖ { α i } ∣ B ∣ = s ( ∑ y ∈ B t y − ℓ ) = ( n − 2 s − 1 ) ( n − 1 ) ℓ s − ( n − 1 s ) ℓ = 0. \sum_{\substack{B\subseteq\Omega\setminus\{\alpha_i\}\\|B|=s}}\left(\sum_{y\in B}t_y-\ell\right)
=\binom{n-2}{s-1}\frac{(n-1)\ell}{s}-\binom{n-1}{s}\ell=0. B ⊆ Ω ∖ { α i } ∣ B ∣ = s ∑ y ∈ B ∑ t y − ℓ = ( s − 1 n − 2 ) s ( n − 1 ) ℓ − ( s n − 1 ) ℓ = 0.
Thus ∑ y ∈ B t y = ℓ \sum_{y\in B}t_y=\ell ∑ y ∈ B t y = ℓ for every B B B .
Given distinct helper points y , y ′ y,y' y , y ′ , choose an ( s − 1 ) (s-1) ( s − 1 ) -subset B ′ B' B ′ of the remaining helper points; this is possible since n − 3 ≥ s − 1 n-3\ge s-1 n − 3 ≥ s − 1 . Comparing B ′ ∪ { y } B'\cup\{y\} B ′ ∪ { y } and B ′ ∪ { y ′ } B'\cup\{y'\} B ′ ∪ { y ′ } shows that t y = t y ′ t_y=t_{y'} t y = t y ′ . The total sum then yields t y = ℓ / s t_y=\ell/s t y = ℓ / s for every helper point.
Finally, fix B = { b 1 , … , b s } B=\{b_1,\ldots,b_s\} B = { b 1 , … , b s } . The space of all tuples with entries in the corresponding U b u U_{b_u} U b u has dimension ℓ \ell ℓ . By injectivity, the evaluation tuples from P i \mathcal{P}_i P i form a subspace of the same dimension. The two spaces therefore coincide, so every prescribed tuple is attained. □
We next derive relations among the helper evaluation spaces. For a field L L L , the projective line P 1 ( L ) \mathbb{P}^1(L) P 1 ( L ) consists of nonzero vectors in L 2 L^2 L 2 modulo nonzero scalar multiples. For column vectors u = ( u 0 , u 1 ) T ∈ L 2 u=(u_0,u_1)^{\mathsf{T}}\in L^2 u = ( u 0 , u 1 ) T ∈ L 2 and v = ( v 0 , v 1 ) T ∈ L 2 v=(v_0,v_1)^{\mathsf{T}}\in L^2 v = ( v 0 , v 1 ) T ∈ L 2 , write
det ( u , v ) : = det [ u v ] = u 0 v 1 − u 1 v 0 . \det(u,v):=\det\begin{bmatrix}u&v\end{bmatrix}=u_0v_1-u_1v_0. det ( u , v ) := det [ u v ] = u 0 v 1 − u 1 v 0 .
Here GL 2 ( L ) \operatorname{GL}_2(L) GL 2 ( L ) is the group of invertible 2 × 2 2\times2 2 × 2 matrices over L L L , and PGL 2 ( L ) \operatorname{PGL}_2(L) PGL 2 ( L ) is its quotient by nonzero scalar matrices. For four distinct points x , z , a , b ∈ P 1 ( F ‾ ) x,z,a,b\in\mathbb{P}^1(\overline{F}) x , z , a , b ∈ P 1 ( F ) , choose nonzero column-vector representatives, denoted by the same symbols, and define
χ ( x , z ; a , b ) = det ( x , b ) det ( z , a ) det ( x , a ) det ( z , b ) . \chi(x,z;a,b)=\frac{\det(x,b)\det(z,a)}{\det(x,a)\det(z,b)}. χ ( x , z ; a , b ) = det ( x , a ) det ( z , b ) det ( x , b ) det ( z , a ) .
This is independent of the chosen representatives. If T ∈ PGL 2 ( F ‾ ) T\in\operatorname{PGL}_2(\overline{F}) T ∈ PGL 2 ( F ) is induced by A ∈ GL 2 ( F ‾ ) A\in\operatorname{GL}_2(\overline{F}) A ∈ GL 2 ( F ) , then det ( A u , A v ) = det ( A ) det ( u , v ) \det(Au,Av)=\det(A)\det(u,v) det ( A u , A v ) = det ( A ) det ( u , v ) , and hence
χ ( x , z ; a , b ) = χ ( T ( x ) , T ( z ) ; T ( a ) , T ( b ) ) . \chi(x,z;a,b)=\chi\bigl(T(x),T(z);T(a),T(b)\bigr). χ ( x , z ; a , b ) = χ ( T ( x ) , T ( z ) ; T ( a ) , T ( b ) ) .
Under the affine chart t ↔ [ t : 1 ] t \leftrightarrow[t : 1] t ↔ [ t : 1 ] , with ∞ = [ 1 : 0 ] \infty= [1 : 0] ∞ = [ 1 : 0 ] , this becomes
χ ( x , z ; a , b ) = ( x − b ) ( z − a ) ( x − a ) ( z − b ) \chi(x,z;a,b)=\frac{(x-b)(z-a)}{(x-a)(z-b)} χ ( x , z ; a , b ) = ( x − a ) ( z − b ) ( x − b ) ( z − a )
when all four points are affine.
Fix an s s s -subset B = { b 1 , … , b s } ⊆ Ω ∖ { α i } B=\{b_1,\ldots,b_s\}\subseteq\Omega\setminus\{\alpha_i\} B = { b 1 , … , b s } ⊆ Ω ∖ { α i } . For u ∈ [ s ] u\in[s] u ∈ [ s ] , let h u ( x ) ∈ K [ x ] < s h_u(x)\in K[x]_{<s} h u ( x ) ∈ K [ x ] < s be the Lagrange basis polynomial
h u ( x ) = ∏ 1 ≤ t ≤ s t ≠ u x − b t b u − b t . h_u(x)=\prod_{\substack{1\leq t\leq s\\t\ne u}}\frac{x-b_t}{b_u-b_t}. h u ( x ) = 1 ≤ t ≤ s t = u ∏ b u − b t x − b t .
Fix y ∈ K y\in K y ∈ K . For f ∈ P i f\in\mathcal{P}_i f ∈ P i , f ( y ) = ∑ u = 1 s h u ( y ) f ( b u ) f(y)=\sum_{u=1}^{s}h_u(y)f(b_u) f ( y ) = ∑ u = 1 s h u ( y ) f ( b u ) . By Lemma 1, every tuple of values from the spaces U b u U_{b_u} U b u is realized by a polynomial in P i \mathcal{P}_i P i . Therefore
U y = ∑ u = 1 s h u ( y ) U b u . (5) U_y=\sum_{u=1}^{s}h_u(y)U_{b_u}. \tag*{(5)} U y = u = 1 ∑ s h u ( y ) U b u . (5)
The sum on the right is a sum of F F F -subspaces of K K K . Here h u ( y ) h_u(y) h u ( y ) is a scalar and
h u ( y ) U b u = { h u ( y ) a : a ∈ U b u } h_u(y)U_{b_u}=\{h_u(y)a:a\in U_{b_u}\} h u ( y ) U b u = { h u ( y ) a : a ∈ U b u }
is its scalar multiple of the F F F -subspace U b u U_{b_u} U b u .
At a helper point outside B B B , equality of dimensions forces the summands in (5) to coincide. This is the helper-space alignment used in [18 proof of Theorem 5] . Comparing the identities at two helper points yields the following relation.
Lemma 2. Let B = { b 1 , … , b s } ⊆ Ω ∖ { α i } B=\{b_1,\ldots,b_s\}\subseteq\Omega\setminus\{\alpha_i\} B = { b 1 , … , b s } ⊆ Ω ∖ { α i } and let z ∈ Ω ∖ ( B ∪ { α i } ) z\in\Omega\setminus(B\cup\{\alpha_i\}) z ∈ Ω ∖ ( B ∪ { α i }) . Then
h 1 ( z ) U b 1 = ⋯ = h s ( z ) U b s . h_1(z)U_{b_1}=\cdots=h_s(z)U_{b_s}. h 1 ( z ) U b 1 = ⋯ = h s ( z ) U b s . Denote this common subspace by A = U z A=U_z A = U z . For every x ∈ Ω ∖ ( B ∪ { α i , z } ) x\in\Omega\setminus(B\cup\{\alpha_i,z\}) x ∈ Ω ∖ ( B ∪ { α i , z }) and every distinct u , v ∈ [ s ] u,v\in[s] u , v ∈ [ s ] ,
χ ( x , z ; b u , b v ) A = A . (6) \chi(x,z;b_u,b_v)A=A. \tag*{(6)} χ ( x , z ; b u , b v ) A = A . (6)
Proof. Taking y = z y=z y = z in (5) , each nonzero scalar multiple h u ( z ) U b u h_u(z)U_{b_u} h u ( z ) U b u has dimension ℓ / s \ell/s ℓ / s , while their sum U z U_z U z also has dimension ℓ / s \ell/s ℓ / s . Hence
h 1 ( z ) U b 1 = ⋯ = h s ( z ) U b s = U z = A . h_1(z)U_{b_1}=\cdots=h_s(z)U_{b_s}=U_z=A. h 1 ( z ) U b 1 = ⋯ = h s ( z ) U b s = U z = A .
The same argument at x x x yields
h u ( x ) U b u = h v ( x ) U b v . h_u(x)U_{b_u}=h_v(x)U_{b_v}. h u ( x ) U b u = h v ( x ) U b v .
Using h u ( z ) U b u = h v ( z ) U b v = A h_u(z)U_{b_u}=h_v(z)U_{b_v}=A h u ( z ) U b u = h v ( z ) U b v = A , we obtain
h u ( x ) h v ( z ) h v ( x ) h u ( z ) A = A . \frac{h_u(x)h_v(z)}{h_v(x)h_u(z)}A=A. h v ( x ) h u ( z ) h u ( x ) h v ( z ) A = A .
A direct calculation using the Lagrange basis shows that
h u ( x ) h v ( z ) h v ( x ) h u ( z ) = ( x − b v ) ( z − b u ) ( x − b u ) ( z − b v ) = χ ( x , z ; b u , b v ) , \frac{h_u(x)h_v(z)}{h_v(x)h_u(z)}
=\frac{(x-b_v)(z-b_u)}{(x-b_u)(z-b_v)}
=\chi(x,z;b_u,b_v), h v ( x ) h u ( z ) h u ( x ) h v ( z ) = ( x − b u ) ( z − b v ) ( x − b v ) ( z − b u ) = χ ( x , z ; b u , b v ) ,
which proves (6) . □
For a finite set X ⊆ P 1 ( F ‾ ) X\subseteq\mathbb{P}^{1}(\overline{F}) X ⊆ P 1 ( F ) , define
R F ( X ) = F ( χ ( x , z ; a , b ) : x , z , a , b ∈ X distinct ) , \mathcal{R}_{F}(X)=F\bigl(\chi(x,z;a,b):x,z,a,b\in X\text{ distinct}\bigr), R F ( X ) = F ( χ ( x , z ; a , b ) : x , z , a , b ∈ X distinct ) ,
with the convention R F ( X ) = F \mathcal{R}_{F}(X)=F R F ( X ) = F when ∣ X ∣ ≤ 3 |X|\leq3 ∣ X ∣ ≤ 3 . We call R F ( X ) \mathcal{R}_{F}(X) R F ( X ) the cross-ratio field of X X X over F F F .
Fix distinct a , b , c ∈ P 1 ( F ‾ ) a,b,c\in\mathbb{P}^{1}(\overline{F}) a , b , c ∈ P 1 ( F ) . For y ∈ P 1 ( F ‾ ) y\in\mathbb{P}^{1}(\overline{F}) y ∈ P 1 ( F ) , define
ϕ a , b , c ( y ) = [ det ( y , b ) det ( c , a ) : det ( y , a ) det ( c , b ) ] . \phi_{a,b,c}(y)=\left[\det(y,b)\det(c,a):\det(y,a)\det(c,b)\right]. ϕ a , b , c ( y ) = [ det ( y , b ) det ( c , a ) : det ( y , a ) det ( c , b ) ] .
The two homogeneous coordinate functions are linearly independent linear forms in y y y , so ϕ a , b , c \phi_{a,b,c} ϕ a , b , c is a projective transformation. It satisfies
ϕ a , b , c ( a ) = ∞ , ϕ a , b , c ( b ) = 0 , ϕ a , b , c ( c ) = 1. \phi_{a,b,c}(a)=\infty,\qquad\phi_{a,b,c}(b)=0,\qquad\phi_{a,b,c}(c)=1. ϕ a , b , c ( a ) = ∞ , ϕ a , b , c ( b ) = 0 , ϕ a , b , c ( c ) = 1.
For y ∉ { a , b , c } y\notin\{a,b,c\} y ∈ / { a , b , c } , its affine coordinate is
ϕ a , b , c ( y ) = det ( y , b ) det ( c , a ) det ( y , a ) det ( c , b ) = χ ( y , c ; a , b ) . (7) \phi_{a,b,c}(y)=\frac{\det(y,b)\det(c,a)}{\det(y,a)\det(c,b)}=\chi(y,c;a,b). \tag*{(7)} ϕ a , b , c ( y ) = det ( y , a ) det ( c , b ) det ( y , b ) det ( c , a ) = χ ( y , c ; a , b ) . (7)
For y ≠ a y\ne a y = a , we henceforth also use ϕ a , b , c ( y ) \phi_{a,b,c}(y) ϕ a , b , c ( y ) to denote its affine coordinate. Although the cross-ratio field is defined using all quadruples, it is generated after fixing any three points.
Lemma 3. Let X ⊆ P 1 ( F ‾ ) X\subseteq\mathbb{P}^{1}(\overline{F}) X ⊆ P 1 ( F ) contain distinct points a , b , c a,b,c a , b , c and write ϕ = ϕ a , b , c \phi=\phi_{a,b,c} ϕ = ϕ a , b , c . Then
R F ( X ) = F ( ϕ ( y ) : y ∈ X ∖ { a , b , c } ) = F ( χ ( y , c ; a , b ) : y ∈ X ∖ { a , b , c } ) . \mathcal{R}_{F}(X)=F\bigl(\phi(y):y\in X\setminus\{a,b,c\}\bigr)=F\bigl(\chi(y,c;a,b):y\in X\setminus\{a,b,c\}\bigr). R F ( X ) = F ( ϕ ( y ) : y ∈ X ∖ { a , b , c } ) = F ( χ ( y , c ; a , b ) : y ∈ X ∖ { a , b , c } ) . Proof. Let
L = F ( ϕ ( y ) : y ∈ X ∖ { a , b , c } ) . L=F\bigl(\phi(y):y\in X\setminus\{a,b,c\}\bigr). L = F ( ϕ ( y ) : y ∈ X ∖ { a , b , c } ) . By (7) , every generator of L L L is a cross-ratio of points of X X X , so L ⊆ R F ( X ) L\subseteq\mathcal{R}_{F}(X) L ⊆ R F ( X ) . Conversely, ϕ ( X ) ⊆ P 1 ( L ) \phi(X)\subseteq\mathbb{P}^{1}(L) ϕ ( X ) ⊆ P 1 ( L ) because ϕ ( a ) = ∞ \phi(a)=\infty ϕ ( a ) = ∞ , ϕ ( b ) = 0 \phi(b)=0 ϕ ( b ) = 0 , ϕ ( c ) = 1 \phi(c)=1 ϕ ( c ) = 1 , and all remaining images belong to L L L . For any four distinct points x 1 , x 2 , x 3 , x 4 ∈ X x_{1},x_{2},x_{3},x_{4}\in X x 1 , x 2 , x 3 , x 4 ∈ X , projective invariance implies
χ ( x 1 , x 2 ; x 3 , x 4 ) = χ ( ϕ ( x 1 ) , ϕ ( x 2 ) ; ϕ ( x 3 ) , ϕ ( x 4 ) ) ∈ L . \chi(x_{1},x_{2};x_{3},x_{4})=\chi\bigl(\phi(x_{1}),\phi(x_{2});\phi(x_{3}),\phi(x_{4})\bigr)\in L. χ ( x 1 , x 2 ; x 3 , x 4 ) = χ ( ϕ ( x 1 ) , ϕ ( x 2 ) ; ϕ ( x 3 ) , ϕ ( x 4 ) ) ∈ L . Thus every generator of R F ( X ) \mathcal{R}_{F}(X) R F ( X ) lies in L L L , proving the result.
We now apply this field to the helper configuration Ω ∖ { α i } \Omega\setminus\{\alpha_i\} Ω ∖ { α i } . The use of the stabilizer of an aligned repair space to obtain a field-divisibility condition already appears in the lower-bound argument of Tamo, Ye, and Barg [18 ] , proof of Theorem 5. Here the relevant field is identified with the cross-ratio field of the helper points.
Proposition 1. For every choice of B B B and z z z as in Lemma 2, the corresponding space A A A is a R F ( Ω ∖ { α i } ) \mathcal{R}_{F}(\Omega\setminus\{\alpha_i\}) R F ( Ω ∖ { α i }) -linear subspace of K K K . Consequently,
[ R F ( Ω ∖ { α i } ) : F ] ∣ ℓ s . [\mathcal{R}_{F}(\Omega\setminus\{\alpha_i\}):F]\mid\frac{\ell}{s}. [ R F ( Ω ∖ { α i }) : F ] ∣ s ℓ . Proof. Let L = F ( χ ( x , z ; b u , b v ) : x ∈ Ω ∖ ( B ∪ { α i , z } ) , 1 ≤ u ≠ v ≤ s ) L=F\bigl(\chi(x,z;b_u,b_v):x\in\Omega\setminus(B\cup\{\alpha_i,z\}),\ 1\leq u\ne v\leq s\bigr) L = F ( χ ( x , z ; b u , b v ) : x ∈ Ω ∖ ( B ∪ { α i , z }) , 1 ≤ u = v ≤ s ) . By Lemma 2, multiplication by each of these scalars maps A A A onto itself. Consider
S A = { λ ∈ K : λ A ⊆ A } . S_A=\{\lambda\in K:\lambda A\subseteq A\}. S A = { λ ∈ K : λ A ⊆ A } . Since dim F A = ℓ / s > 0 \dim_F A=\ell/s>0 dim F A = ℓ / s > 0 , the space A A A is nonzero. The set S A S_A S A contains F F F and is closed under addition and multiplication. If 0 ≠ λ ∈ S A 0\ne\lambda\in S_A 0 = λ ∈ S A , then dim F ( λ A ) = dim F A \dim_F(\lambda A)=\dim_F A dim F ( λ A ) = dim F A , so λ A = A \lambda A=A λ A = A and λ − 1 A = A \lambda^{-1}A=A λ − 1 A = A . Hence S A S_A S A is a subfield of K K K , and L ⊆ S A L\subseteq S_A L ⊆ S A .
We claim that
L = R F ( Ω ∖ { α i } ) . L=\mathcal{R}_{F}(\Omega\setminus\{\alpha_i\}). L = R F ( Ω ∖ { α i }) . The inclusion L ⊆ R F ( Ω ∖ { α i } ) L\subseteq\mathcal{R}_{F}(\Omega\setminus\{\alpha_i\}) L ⊆ R F ( Ω ∖ { α i }) is immediate. For the reverse inclusion, let ϕ = ϕ b 1 , b 2 , z \phi=\phi_{b_1,b_2,z} ϕ = ϕ b 1 , b 2 , z . By Lemma 3, it is enough to show that ϕ ( y ) ∈ L \phi(y)\in L ϕ ( y ) ∈ L for every y ∈ Ω ∖ { α i , b 1 , b 2 , z } y\in\Omega\setminus\{\alpha_i,b_1,b_2,z\} y ∈ Ω ∖ { α i , b 1 , b 2 , z } . If y ∉ B y\notin B y ∈ / B , then
ϕ ( y ) = χ ( y , z ; b 1 , b 2 ) ∈ L . \phi(y)=\chi(y,z;b_1,b_2)\in L. ϕ ( y ) = χ ( y , z ; b 1 , b 2 ) ∈ L . Now let y = b u y=b_u y = b u with u ≥ 3 u\geq3 u ≥ 3 . Since
∣ Ω ∖ ( B ∪ { α i , z } ) ∣ = k − 2 ≥ 1 , \left|\Omega\setminus(B\cup\{\alpha_i,z\})\right|=k-2\geq1, ∣ Ω ∖ ( B ∪ { α i , z }) ∣ = k − 2 ≥ 1 , choose w w w in this set. Then
ϕ ( w ) = χ ( w , z ; b 1 , b 2 ) ∈ L , c u : = χ ( w , z ; b 1 , b u ) ∈ L . \phi(w)=\chi(w,z;b_1,b_2)\in L,\qquad c_u:=\chi(w,z;b_1,b_u)\in L. ϕ ( w ) = χ ( w , z ; b 1 , b 2 ) ∈ L , c u := χ ( w , z ; b 1 , b u ) ∈ L . Using ϕ ( b 1 ) = ∞ \phi(b_1)=\infty ϕ ( b 1 ) = ∞ , ϕ ( b 2 ) = 0 \phi(b_2)=0 ϕ ( b 2 ) = 0 , and ϕ ( z ) = 1 \phi(z)=1 ϕ ( z ) = 1 , projective invariance gives
c u = ϕ ( w ) − ϕ ( b u ) 1 − ϕ ( b u ) . c_u=\frac{\phi(w)-\phi(b_u)}{1-\phi(b_u)}. c u = 1 − ϕ ( b u ) ϕ ( w ) − ϕ ( b u ) .
If c u = 1 c_u=1 c u = 1 , then ϕ ( w ) = 1 = ϕ ( z ) \phi(w)=1=\phi(z) ϕ ( w ) = 1 = ϕ ( z ) , contrary to the injectivity of ϕ \phi ϕ and w ≠ z w\ne z w = z . Hence c u ≠ 1 c_u\ne1 c u = 1 , and
ϕ ( b u ) = ϕ ( w ) − c u 1 − c u ∈ L . \phi(b_u)=\frac{\phi(w)-c_u}{1-c_u}\in L. ϕ ( b u ) = 1 − c u ϕ ( w ) − c u ∈ L .
This proves the claim. Therefore A A A is R F ( Ω ∖ { α i } ) \mathcal{R}_F(\Omega\setminus\{\alpha_i\}) R F ( Ω ∖ { α i }) -linear. Finally, dim F A = ℓ / s \dim_F A=\ell/s dim F A = ℓ / s , so
ℓ s = [ R F ( Ω ∖ { α i } ) : F ] dim R F ( Ω ∖ { α i } ) A , \frac{\ell}{s}=[\mathcal{R}_F(\Omega\setminus\{\alpha_i\}):F]\dim_{\mathcal{R}_F(\Omega\setminus\{\alpha_i\})} A, s ℓ = [ R F ( Ω ∖ { α i }) : F ] dim R F ( Ω ∖ { α i }) A ,
which proves the divisibility.
The failed coordinate imposes one further constraint. Fix B , z , A B,z,A B , z , A as in Lemma 2. Put ρ 1 = 1 \rho_1=1 ρ 1 = 1 and, for 2 ≤ u ≤ s 2\le u\le s 2 ≤ u ≤ s , define
ρ u = h u ( α i ) h 1 ( z ) h 1 ( α i ) h u ( z ) = χ ( α i , z ; b u , b 1 ) . (8) \rho_u=\frac{h_u(\alpha_i)h_1(z)}{h_1(\alpha_i)h_u(z)}=\chi(\alpha_i,z;b_u,b_1). \tag*{(8)} ρ u = h 1 ( α i ) h u ( z ) h u ( α i ) h 1 ( z ) = χ ( α i , z ; b u , b 1 ) . (8)
Proposition 2. The elements ρ 1 , … , ρ s \rho_1,\ldots,\rho_s ρ 1 , … , ρ s are linearly independent over R F ( Ω ∖ { α i } ) \mathcal{R}_F(\Omega\setminus\{\alpha_i\}) R F ( Ω ∖ { α i }) . Consequently,
[ R F ( Ω ) : R F ( Ω ∖ { α i } ) ] ≥ s . [\mathcal{R}_F(\Omega):\mathcal{R}_F(\Omega\setminus\{\alpha_i\})]\ge s. [ R F ( Ω ) : R F ( Ω ∖ { α i })] ≥ s .
Proof. Setting y = α i y=\alpha_i y = α i in (5) yields a surjective map
⨁ u = 1 s U b u ⟶ K , ( v 1 , … , v s ) ⟼ ∑ u = 1 s h u ( α i ) v u . \bigoplus_{u=1}^{s}U_{b_u}\longrightarrow K,\qquad(v_1,\ldots,v_s)\longmapsto\sum_{u=1}^{s}h_u(\alpha_i)v_u. u = 1 ⨁ s U b u ⟶ K , ( v 1 , … , v s ) ⟼ u = 1 ∑ s h u ( α i ) v u .
Both spaces have F F F -dimension ℓ \ell ℓ , so this map is an isomorphism. Equivalently,
K = ⨁ u = 1 s h u ( α i ) U b u . (9) K=\bigoplus_{u=1}^{s}h_u(\alpha_i)U_{b_u}. \tag*{(9)} K = u = 1 ⨁ s h u ( α i ) U b u . (9)
Set
A ′ = h 1 ( α i ) h 1 ( z ) A . A'=\frac{h_1(\alpha_i)}{h_1(z)}A. A ′ = h 1 ( z ) h 1 ( α i ) A .
By Proposition 1, A ′ A' A ′ is R F ( Ω ∖ { α i } ) \mathcal{R}_F(\Omega\setminus\{\alpha_i\}) R F ( Ω ∖ { α i }) -linear. Since A = h u ( z ) U b u A=h_u(z)U_{b_u} A = h u ( z ) U b u , (8) gives
ρ u A ′ = h u ( α i ) U b u , 1 ≤ u ≤ s . \rho_u A'=h_u(\alpha_i)U_{b_u},\qquad1\le u\le s. ρ u A ′ = h u ( α i ) U b u , 1 ≤ u ≤ s .
Thus (9) becomes
K = ⨁ u = 1 s ρ u A ′ . K=\bigoplus_{u=1}^{s}\rho_u A'. K = u = 1 ⨁ s ρ u A ′ .
If
∑ u = 1 s c u ρ u = 0 , c u ∈ R F ( Ω ∖ { α i } ) , \sum_{u=1}^{s}c_u\rho_u=0,\qquad c_u\in\mathcal{R}_F(\Omega\setminus\{\alpha_i\}), u = 1 ∑ s c u ρ u = 0 , c u ∈ R F ( Ω ∖ { α i }) ,
choose 0 ≠ a ∈ A ′ 0\ne a\in A' 0 = a ∈ A ′ . Multiplying the relation by a a a and using c u a ∈ A ′ c_u a\in A' c u a ∈ A ′ , the direct sum forces ρ u c u a = 0 \rho_u c_u a=0 ρ u c u a = 0 for every u u u . Since ρ u a ≠ 0 \rho_u a\ne0 ρ u a = 0 , we obtain c u = 0 c_u=0 c u = 0 . Therefore the ρ u \rho_u ρ u are linearly independent over the helper cross-ratio field. Since ρ u ∈ R F ( Ω ) \rho_u\in\mathcal{R}_F(\Omega) ρ u ∈ R F ( Ω ) , the relative degree is at least s s s .
We have proved that, whenever a coordinate has cut-set-optimal full-helper repair,
[ R F ( Ω ∖ { α i } ) : F ] ∣ ℓ s , [ R F ( Ω ) : R F ( Ω ∖ { α i } ) ] ≥ s . [\mathcal{R}_F(\Omega\setminus\{\alpha_i\}):F]\mid\frac{\ell}{s},\qquad[\mathcal{R}_F(\Omega):\mathcal{R}_F(\Omega\setminus\{\alpha_i\})]\ge s. [ R F ( Ω ∖ { α i }) : F ] ∣ s ℓ , [ R F ( Ω ) : R F ( Ω ∖ { α i })] ≥ s .
These two degree constraints will be used repeatedly below.
A General Lower Bound
To combine the degree constraints for different deleted coordinates, we first record a simple identity for cross-ratio fields.
Lemma 4. Let A , B ⊆ P 1 ( F ‾ ) A,B\subseteq\mathbb{P}^{1}(\overline{F}) A , B ⊆ P 1 ( F ) be finite sets with ∣ A ∩ B ∣ ≥ 3 |A\cap B|\ge3 ∣ A ∩ B ∣ ≥ 3 . Then
R F ( A ∪ B ) = R F ( A ) R F ( B ) . \mathcal{R}_{F}(A\cup B)=\mathcal{R}_{F}(A)\mathcal{R}_{F}(B). R F ( A ∪ B ) = R F ( A ) R F ( B ) . where the right-hand side is the compositum inside F ‾ \overline{F} F . In particular, if
X = { α 1 , … , α m } ⊆ P 1 ( F ‾ ) , m ≥ 5 , X=\{\alpha_{1},\ldots,\alpha_{m}\}\subseteq\mathbb{P}^{1}(\overline{F}),\qquad m\ge5, X = { α 1 , … , α m } ⊆ P 1 ( F ) , m ≥ 5 , then, for distinct i , j ∈ [ m ] i,j\in[m] i , j ∈ [ m ] ,
R F ( X ) = R F ( X ∖ { α i } ) R F ( X ∖ { α j } ) . \mathcal{R}_{F}(X)=\mathcal{R}_{F}(X\setminus\{\alpha_{i}\})\mathcal{R}_{F}(X\setminus\{\alpha_{j}\}). R F ( X ) = R F ( X ∖ { α i }) R F ( X ∖ { α j }) .
Proof. The inclusion R F ( A ) R F ( B ) ⊆ R F ( A ∪ B ) \mathcal{R}_{F}(A)\mathcal{R}_{F}(B)\subseteq\mathcal{R}_{F}(A\cup B) R F ( A ) R F ( B ) ⊆ R F ( A ∪ B ) follows from the definition. Choose distinct a , b , c ∈ A ∩ B a,b,c\in A\cap B a , b , c ∈ A ∩ B and let ϕ = ϕ a , b , c \phi=\phi_{a,b,c} ϕ = ϕ a , b , c . By Lemma 3,
R F ( A ) = F ( ϕ ( y ) : y ∈ A ∖ { a , b , c } ) , \mathcal{R}_{F}(A)=F\bigl(\phi(y):y\in A\setminus\{a,b,c\}\bigr), R F ( A ) = F ( ϕ ( y ) : y ∈ A ∖ { a , b , c } ) ,
R F ( B ) = F ( ϕ ( y ) : y ∈ B ∖ { a , b , c } ) , \mathcal{R}_{F}(B)=F\bigl(\phi(y):y\in B\setminus\{a,b,c\}\bigr), R F ( B ) = F ( ϕ ( y ) : y ∈ B ∖ { a , b , c } ) ,
R F ( A ∪ B ) = F ( ϕ ( y ) : y ∈ ( A ∪ B ) ∖ { a , b , c } ) . \mathcal{R}_{F}(A\cup B)=F\bigl(\phi(y):y\in(A\cup B)\setminus\{a,b,c\}\bigr). R F ( A ∪ B ) = F ( ϕ ( y ) : y ∈ ( A ∪ B ) ∖ { a , b , c } ) .
The last field is generated by the first two, proving equality. The special case follows by taking A = X ∖ { α i } A=X\setminus\{\alpha_i\} A = X ∖ { α i } and B = X ∖ { α j } B=X\setminus\{\alpha_j\} B = X ∖ { α j } .
For a configuration admitting cut-set-optimal full-helper repair of every coordinate, the degree lost when one evaluation point is deleted is at least s s s . This leads to the following arithmetic quantity.
Definition 1. For integers s ≥ 2 s\ge2 s ≥ 2 , define G s ( 0 ) = 1 G_s(0)=1 G s ( 0 ) = 1 . For an integer m ≥ 1 m\ge1 m ≥ 1 , minimize over integer tuples ( g 1 , … , g m ) (g_1,\ldots,g_m) ( g 1 , … , g m ) :
G s ( m ) = min { ∏ j = 1 m g j : g j ≥ s , gcd ( g i , g j ) = 1 for i ≠ j } . G_s(m)=\min\left\{\prod_{j=1}^{m}g_j:g_j\ge s,\ \gcd(g_i,g_j)=1\text{ for }i\ne j\right\}. G s ( m ) = min { j = 1 ∏ m g j : g j ≥ s , g cd( g i , g j ) = 1 for i = j } . Let p j p_j p j be the j j j -th prime and write
p m # = ∏ j = 1 m p j , p 0 # = 1. p_m^{\#}=\prod_{j=1}^{m}p_j,\qquad p_0^{\#}=1. p m # = j = 1 ∏ m p j , p 0 # = 1. In particular, G 2 ( m ) = p m # G_2(m)=p_m^{\#} G 2 ( m ) = p m # , and G s ( m ) ≥ p m # G_s(m)\ge p_m^{\#} G s ( m ) ≥ p m # for every s ≥ 2 s\ge2 s ≥ 2 .
Theorem 3. Let F = F q F=\mathbb{F}_q F = F q and K = F q ℓ K=\mathbb{F}_{q^\ell} K = F q ℓ . Let k ≥ 3 k\ge3 k ≥ 3 , s = n − k ≥ 2 s=n-k\ge2 s = n − k ≥ 2 , and let Ω ⊆ K \Omega\subseteq K Ω ⊆ K be an evaluation set of size n n n . Suppose that RSK ( n , k , Ω ) \operatorname{RSK}(n,k,\Omega) RSK ( n , k , Ω ) admits cut-set-optimal F F F -linear repair of every coordinate from all other n − 1 n-1 n − 1 coordinates. Then
ℓ ≥ s G s ( n ) . \ell\ge sG_s(n). ℓ ≥ s G s ( n ) . More precisely, there exist pairwise coprime integers g 1 , … , g n ≥ s g_1,\ldots,g_n\ge s g 1 , … , g n ≥ s such that
∏ i = 1 n g i ∣ [ R F ( Ω ) : F ] ∣ ℓ s . \prod_{i=1}^{n}g_i\mid[\mathcal{R}_{F}(\Omega):F]\mid\frac{\ell}{s}. i = 1 ∏ n g i ∣ [ R F ( Ω ) : F ] ∣ s ℓ .
Proof. Put
m = [ R F ( Ω ) : F ] , m i = [ R F ( Ω ∖ { α i } ) : F ] , g i = m m i . m=[\mathcal{R}_{F}(\Omega):F],\qquad m_i=[\mathcal{R}_{F}(\Omega\setminus\{\alpha_i\}):F],\qquad g_i=\frac{m}{m_i}. m = [ R F ( Ω ) : F ] , m i = [ R F ( Ω ∖ { α i }) : F ] , g i = m i m .
By Propositions 1 and 2,
g i ≥ s , m i ∣ ℓ s . g_i\ge s,\qquad m_i\mid\frac{\ell}{s}. g i ≥ s , m i ∣ s ℓ .
For distinct i , j i,j i , j , Lemma 4 gives
R F ( Ω ) = R F ( Ω ∖ { α i } ) R F ( Ω ∖ { α j } ) . (10) \mathcal{R}_{F}(\Omega)=\mathcal{R}_{F}(\Omega\setminus\{\alpha_i\})\mathcal{R}_{F}(\Omega\setminus\{\alpha_j\}). \tag*{(10)} R F ( Ω ) = R F ( Ω ∖ { α i }) R F ( Ω ∖ { α j }) . (10)
Finite subfields of F ‾ \overline{F} F are determined by their degrees over F F F , and the degree of their compositum is the least common multiple. Hence
m = lcm ( m i , m j ) . m=\operatorname{lcm}(m_i,m_j). m = lcm ( m i , m j ) .
Since m i , m j ∣ ℓ / s m_i,m_j\mid\ell/s m i , m j ∣ ℓ / s , this also shows m ∣ ℓ / s m\mid\ell/s m ∣ ℓ / s . Moreover,
g i = m j gcd ( m i , m j ) , g j = m i gcd ( m i , m j ) , g_i=\frac{m_j}{\gcd(m_i,m_j)},\qquad g_j=\frac{m_i}{\gcd(m_i,m_j)}, g i = g cd( m i , m j ) m j , g j = g cd( m i , m j ) m i ,
so gcd ( g i , g j ) = 1 \gcd(g_i,g_j)=1 g cd( g i , g j ) = 1 . Thus the g i g_i g i are pairwise coprime. Each g i g_i g i divides m m m , so their product divides m m m :
∏ i = 1 n g i ∣ m ∣ ℓ s . \prod_{i=1}^{n}g_i\mid m\mid\frac{\ell}{s}. i = 1 ∏ n g i ∣ m ∣ s ℓ .
By the definition of G s ( n ) G_s(n) G s ( n ) , ∏ i g i ≥ G s ( n ) \prod_i g_i\ge G_s(n) ∏ i g i ≥ G s ( n ) , and therefore ℓ ≥ s G s ( n ) \ell\ge sG_s(n) ℓ ≥ s G s ( n ) .
A bound for arbitrary d d d follows from the full-helper result by puncturing to one failed coordinate and its helpers.
Corollary 1. Let k ≥ 3 k\ge3 k ≥ 3 and s = d + 1 − k ≥ 2 s=d+1-k\ge2 s = d + 1 − k ≥ 2 . If an ( n , k ) (n,k) ( n , k ) RS code admits cut-set-optimal F F F -linear repair of every coordinate from every d d d -helper set, then
ℓ ≥ s G s ( d + 1 ) . \ell\ge sG_s(d+1). ℓ ≥ s G s ( d + 1 ) .
Proof. Puncture the code to any d + 1 d+1 d + 1 coordinates. For every coordinate in the punctured code, the other d d d coordinates form an allowed helper set in the original code. Thus the punctured ( d + 1 , k ) (d+1,k) ( d + 1 , k ) RS code admits cut-set-optimal full-helper repair of every coordinate. Applying Theorem 3 with n = d + 1 n=d+1 n = d + 1 proves the claim.
Remark 2. Tamo, Ye, and Barg [18 Theorem 5] proved that every scalar linear MDS code admitting cut-set-optimal F F F -linear repair of every coordinate from every d d d -helper set satisfies
ℓ ≥ ∏ r = 1 k − 1 p r . \ell\ge\prod_{r=1}^{k-1}p_r. ℓ ≥ r = 1 ∏ k − 1 p r .
Any d + 1 d+1 d + 1 pairwise coprime integers at least s ≥ 2 s\ge2 s ≥ 2 collectively contain at least d + 1 d+1 d + 1 distinct prime divisors, and hence
G s ( d + 1 ) ≥ ∏ r = 1 d + 1 p r > ∏ r = 1 k − 1 p r . G_s(d+1)\ge\prod_{r=1}^{d+1}p_r>\prod_{r=1}^{k-1}p_r. G s ( d + 1 ) ≥ r = 1 ∏ d + 1 p r > r = 1 ∏ k − 1 p r .
Thus, for RS codes, the general lower bound in Corollary 1 is stronger than that of [18 Theorem 5] .
An Improved Lower Bound for 2 d ≥ n + 3 2d\ge n+3 2 d ≥ n + 3
The preceding bound uses only one set of d + 1 d+1 d + 1 coordinates. We now use the constraints from all failed-coordinate/helper-set pairs. When 2 d ≥ n + 3 2d\ge n+3 2 d ≥ n + 3 , the resulting cross-ratio degrees admit an LCM representation, leading to the lower bound ℓ ≥ s Δ s ( n , d ) \ell\ge s\Delta_s(n,d) ℓ ≥ s Δ s ( n , d ) . We first record the degree constraints obtained from every punctured repair configuration.
Proposition 3. Let k ≥ 3 k\ge3 k ≥ 3 and s = d + 1 − k ≥ 2 s=d+1-k\ge2 s = d + 1 − k ≥ 2 . Suppose that RSK ( n , k , Ω ) \operatorname{RSK}(n,k,\Omega) RSK ( n , k , Ω ) admits cut-set-optimal F F F -linear repair of every coordinate from every d d d -helper set. Then, for every x ∈ Ω x\in\Omega x ∈ Ω and every H ⊆ Ω ∖ { x } H\subseteq\Omega\setminus\{x\} H ⊆ Ω ∖ { x } with ∣ H ∣ = d |H|=d ∣ H ∣ = d ,
[ R F ( H ) : F ] ∣ ℓ s , [ R F ( H ∪ { x } ) : R F ( H ) ] ≥ s . [\mathcal{R}_F(H):F]\mid\frac{\ell}{s},\qquad[\mathcal{R}_F(H\cup\{x\}):\mathcal{R}_F(H)]\ge s. [ R F ( H ) : F ] ∣ s ℓ , [ R F ( H ∪ { x }) : R F ( H )] ≥ s . Moreover,
[ R F ( Ω ) : F ] ∣ ℓ s . [\mathcal{R}_F(\Omega):F]\mid\frac{\ell}{s}. [ R F ( Ω ) : F ] ∣ s ℓ .
Proof. Puncture to H ∪ { x } H\cup\{x\} H ∪ { x } . The resulting length-( d + 1 ) (d+1) ( d + 1 ) RS code admits cut-set-optimal full-helper repair of each of its coordinates. Applying Propositions 1 and 2 with target x x x yields
[ R F ( H ) : F ] ∣ ℓ s , [ R F ( H ∪ { x } ) : R F ( H ) ] ≥ s . [\mathcal{R}_F(H):F]\mid\frac{\ell}{s},\qquad[\mathcal{R}_F(H\cup\{x\}):\mathcal{R}_F(H)]\ge s. [ R F ( H ) : F ] ∣ s ℓ , [ R F ( H ∪ { x }) : R F ( H )] ≥ s .
It remains to prove the global divisibility. Since d ≥ 4 d \ge4 d ≥ 4 , every four-point subset of Ω \Omega Ω lies in some d d d -subset H H H . Thus R F ( Ω ) \mathcal{R}_F(\Omega) R F ( Ω ) is the compositum of the fields R F ( H ) \mathcal{R}_F(H) R F ( H ) over all d d d -subsets. By the finite-field compositum formula and the first part,
[ R F ( Ω ) : F ] = l c m H ⊆ Ω ∣ H ∣ = d [ R F ( H ) : F ] ∣ ℓ s . [\mathcal{R}_F(\Omega):F]=\mathop{\mathrm{lcm}}_{\substack{H\subseteq\Omega\\ |H|=d}}[\mathcal{R}_F(H):F]\mid\frac{\ell}{s}. [ R F ( Ω ) : F ] = lcm H ⊆ Ω ∣ H ∣ = d [ R F ( H ) : F ] ∣ s ℓ .
We next define the arithmetic quantity that will also appear in the construction.
Definition 2. Let s s s , N N N , t t t be integers with s ≥ 2 s\ge2 s ≥ 2 and 1 ≤ t < N 1\le t<N 1 ≤ t < N . A tuple of positive integers ( a 1 , … , a N ) (a_1,\ldots,a_N) ( a 1 , … , a N ) is feasible for ( N , t , s ) (N,t,s) ( N , t , s ) if
lcm ( a j : j ∈ J ∪ { i } ) lcm ( a j : j ∈ J ) ≥ s \frac{\operatorname{lcm}(a_j:j\in J\cup\{i\})}{\operatorname{lcm}(a_j:j\in J)}\ge s lcm ( a j : j ∈ J ) lcm ( a j : j ∈ J ∪ { i }) ≥ s for every i ∈ [ N ] i\in[N] i ∈ [ N ] and every t t t -subset J ⊆ [ N ] ∖ { i } J\subseteq[N]\setminus\{i\} J ⊆ [ N ] ∖ { i } . Define Δ s ( N , t ) \Delta_s(N,t) Δ s ( N , t ) as the minimum of lcm ( a 1 , … , a N ) \operatorname{lcm}(a_1,\ldots,a_N) lcm ( a 1 , … , a N ) over all feasible tuples.
Thus Δ s ( N , t ) \Delta_s(N,t) Δ s ( N , t ) is the minimum lcm compatible with all the above relative-degree inequalities. Any N N N pairwise coprime integers at least s s s form a feasible tuple, so
Δ s ( N , t ) ≤ G s ( N ) . (11) \Delta_s(N,t)\le G_s(N). \tag*{(11)} Δ s ( N , t ) ≤ G s ( N ) . (11)
The following elementary lemma converts identities of the form m S ∩ T = lcm ( m S , m T ) m_{S\cap T}=\operatorname{lcm}(m_S,m_T) m S ∩ T = lcm ( m S , m T ) into a representation by coordinate labels.
Lemma 5. Let 0 ≤ r < n 0\le r<n 0 ≤ r < n , and let m T m_T m T be a positive integer for every T ⊆ [ n ] T\subseteq[n] T ⊆ [ n ] with ∣ T ∣ ≤ r |T|\le r ∣ T ∣ ≤ r . The following are equivalent:
for every such S , T S,T S , T ,
m S ∩ T = lcm ( m S , m T ) ; m_{S\cap T}=\operatorname{lcm}(m_S,m_T); m S ∩ T = lcm ( m S , m T ) ; there exist positive integers b 1 , … , b n b_1,\ldots,b_n b 1 , … , b n such that
m T = lcm ( b i : i ∉ T ) m_T=\operatorname{lcm}(b_i:i\notin T) m T = lcm ( b i : i ∈ / T ) for every ∣ T ∣ ≤ r |T|\le r ∣ T ∣ ≤ r .
One possible choice is
b i = gcd ( m R : ∣ R ∣ ≤ r , i ∉ R ) . b_i=\gcd(m_R:|R|\le r,\ i\notin R). b i = g cd( m R : ∣ R ∣ ≤ r , i ∈ / R ) . Proof. Assume the first condition. If R ⊆ V R\subseteq V R ⊆ V , then
m R = lcm ( m R , m V ) , m_R=\operatorname{lcm}(m_R,m_V), m R = lcm ( m R , m V ) , so m V ∣ m R m_V\mid m_R m V ∣ m R . Fix a prime p p p . For a positive integer a a a , v p ( a ) v_p(a) v p ( a ) denotes the exponent of p p p in the prime factorization of a a a . Write
e T = v p ( m T ) , λ i = min ∣ R ∣ ≤ r i ∉ R e R . e_T=v_p(m_T),\qquad\lambda_i=\min_{\substack{|R|\le r\\i\notin R}}e_R. e T = v p ( m T ) , λ i = ∣ R ∣ ≤ r i ∈ / R min e R . For i ∉ T i\notin T i ∈ / T , we have λ i ≤ e T \lambda_i\le e_T λ i ≤ e T . We claim that equality holds for at least one such i i i . Otherwise, for each i ∉ T i\notin T i ∈ / T choose R i R_i R i with i ∉ R i i\notin R_i i ∈ / R i and e R i = λ i < e T e_{R_i}=\lambda_i<e_T e R i = λ i < e T , and put
R = ⋂ i ∉ T R i . R=\bigcap_{i\notin T}R_i. R = i ∈ / T ⋂ R i . For every i ∉ T i\notin T i ∈ / T , the point i i i is missing from R i R_i R i , hence from R R R ; therefore R ⊆ T R\subseteq T R ⊆ T . Repeated application of the first condition yields
e R = max i ∉ T e R i < e T . e_R=\max_{i\notin T}e_{R_i}<e_T. e R = i ∈ / T max e R i < e T . But R ⊆ T R\subseteq T R ⊆ T implies m T ∣ m R m_T\mid m_R m T ∣ m R , hence e T ≤ e R e_T\le e_R e T ≤ e R , a contradiction. Thus
e T = max i ∉ T λ i . e_T=\max_{i\notin T}\lambda_i. e T = i ∈ / T max λ i .
Since v p ( b i ) = λ i v_p(b_i)=\lambda_i v p ( b i ) = λ i , this is exactly the p p p -adic valuation of lcm ( b i : i ∉ T ) \operatorname{lcm}(b_i : i \notin T) lcm ( b i : i ∈ / T ) . As this holds for every prime,
m T = lcm ( b i : i ∉ T ) . m_T=\operatorname{lcm}(b_i : i \notin T). m T = lcm ( b i : i ∈ / T ) .
Conversely, if such a representation holds, then
[ n ] ∖ ( S ∩ T ) = ( [ n ] ∖ S ) ∪ ( [ n ] ∖ T ) , [n]\setminus(S\cap T)=([n]\setminus S)\cup([n]\setminus T), [ n ] ∖ ( S ∩ T ) = ([ n ] ∖ S ) ∪ ([ n ] ∖ T ) ,
and the desired lcm identity follows immediately.
Suppose now that 2 d ≥ n + 3 2d\ge n+3 2 d ≥ n + 3 . If S , T ⊆ [ n ] S,T\subseteq[n] S , T ⊆ [ n ] have ∣ S ∣ , ∣ T ∣ ≤ n − d |S|,|T|\le n-d ∣ S ∣ , ∣ T ∣ ≤ n − d , then at least three evaluation points remain after deleting S ∪ T S\cup T S ∪ T . This allows the preceding lcm representation to be applied simultaneously to all relevant cross-ratio fields.
Theorem 4. Let 3 ≤ k < d ≤ n − 1 3\le k<d\le n-1 3 ≤ k < d ≤ n − 1 , put s = d + 1 − k s=d+1-k s = d + 1 − k , and suppose that RSK ( n , k , Ω ) \operatorname{RSK}(n,k,\Omega) RSK ( n , k , Ω ) admits cut-set-optimal F F F -linear repair of every coordinate from every d d d -helper set. If
then there exist positive integers b 1 , … , b n b_1,\ldots,b_n b 1 , … , b n such that, for any T ⊆ [ n ] T\subseteq[n] T ⊆ [ n ] with ∣ T ∣ ≤ n − d |T|\le n-d ∣ T ∣ ≤ n − d ,
[ R F ( { α j : j ∉ T } ) : F ] = lcm ( b j : j ∉ T ) (12) [\mathcal{R}_F(\{\alpha_j:j\notin T\}):F]=\operatorname{lcm}(b_j:j\notin T) \tag*{(12)} [ R F ({ α j : j ∈ / T }) : F ] = lcm ( b j : j ∈ / T ) (12) and
lcm ( b 1 , … , b n ) = [ R F ( Ω ) : F ] ∣ ℓ s (13) \operatorname{lcm}(b_1,\ldots,b_n)=[\mathcal{R}_F(\Omega):F]\mid\frac{\ell}{s} \tag*{(13)} lcm ( b 1 , … , b n ) = [ R F ( Ω ) : F ] ∣ s ℓ (13) Moreover, ( b 1 , … , b n ) (b_1,\ldots,b_n) ( b 1 , … , b n ) is feasible for ( n , d , s ) (n,d,s) ( n , d , s ) . Consequently,
ℓ ≥ s Δ s ( n , d ) , \ell\ge s\Delta_s(n,d), ℓ ≥ s Δ s ( n , d ) , and hence
ℓ min ( n , k , d ; q ) ≥ s Δ s ( n , d ) . \ell_{\min}(n,k,d;q)\ge s\Delta_s(n,d). ℓ m i n ( n , k , d ; q ) ≥ s Δ s ( n , d ) .
Proof. Put r = n − d r=n-d r = n − d . For T ⊆ [ n ] T\subseteq[n] T ⊆ [ n ] with ∣ T ∣ ≤ r |T|\le r ∣ T ∣ ≤ r , put
X T = { α j : j ∉ T } , m T = [ R F ( X T ) : F ] . X_T=\{\alpha_j:j\notin T\},\qquad m_T=[\mathcal{R}_F(X_T):F]. X T = { α j : j ∈ / T } , m T = [ R F ( X T ) : F ] .
For two such sets S , T S,T S , T ,
∣ X S ∩ X T ∣ = n − ∣ S ∪ T ∣ ≥ n − 2 r = 2 d − n ≥ 3. |X_S\cap X_T|=n-|S\cup T|\ge n-2r=2d-n\ge3. ∣ X S ∩ X T ∣ = n − ∣ S ∪ T ∣ ≥ n − 2 r = 2 d − n ≥ 3.
Moreover, X S ∪ X T = X S ∩ T X_S\cup X_T=X_{S\cap T} X S ∪ X T = X S ∩ T . Hence Lemma 4 gives
R F ( X S ∩ T ) = R F ( X S ) R F ( X T ) , \mathcal{R}_F(X_{S\cap T})=\mathcal{R}_F(X_S)\mathcal{R}_F(X_T), R F ( X S ∩ T ) = R F ( X S ) R F ( X T ) ,
and therefore, since the fields are finite,
m S ∩ T = lcm ( m S , m T ) . m_{S\cap T}=\operatorname{lcm}(m_S,m_T). m S ∩ T = lcm ( m S , m T ) .
By Lemma 5, there are positive integers b 1 , … , b n b_1,\ldots,b_n b 1 , … , b n satisfying (12) . Taking T = ∅ T=\varnothing T = ∅ yields the first equality in (13) , while Proposition 3 shows that [ R F ( Ω ) : F ] [\mathcal{R}_F(\Omega):F] [ R F ( Ω ) : F ] divides ℓ / s \ell/s ℓ / s .
It remains to verify feasibility. Let H ⊆ [ n ] H\subseteq[n] H ⊆ [ n ] have size d d d and let i ∉ H i\notin H i ∈ / H . Put T = [ n ] ∖ H T=[n]\setminus H T = [ n ] ∖ H , so ∣ T ∣ = r |T|=r ∣ T ∣ = r and i ∈ T i\in T i ∈ T . Applying (12) to T T T and T ∖ { i } T\setminus\{i\} T ∖ { i } gives
lcm ( b i , { b h : h ∈ H } ) lcm ( b h : h ∈ H ) = [ R F ( { α h : h ∈ H } ∪ { α i } ) : R F ( { α h : h ∈ H } ) ] . \frac{\operatorname{lcm}(b_i,\{b_h:h\in H\})}{\operatorname{lcm}(b_h:h\in H)}
=
[\mathcal{R}_F(\{\alpha_h:h\in H\}\cup\{\alpha_i\}):\mathcal{R}_F(\{\alpha_h:h\in H\})]. lcm ( b h : h ∈ H ) lcm ( b i , { b h : h ∈ H }) = [ R F ({ α h : h ∈ H } ∪ { α i }) : R F ({ α h : h ∈ H })] .
The right-hand side is at least s s s by Proposition 3. Thus the tuple is feasible, and
Δ s ( n , d ) ≤ lcm ( b 1 , … , b n ) = [ R F ( Ω ) : F ] ≤ ℓ s , \Delta_s(n,d)\le\operatorname{lcm}(b_1,\ldots,b_n)=[\mathcal{R}_F(\Omega):F]\le\frac{\ell}{s}, Δ s ( n , d ) ≤ lcm ( b 1 , … , b n ) = [ R F ( Ω ) : F ] ≤ s ℓ ,
where the divisibility underlying the last inequality was established in (13) . □ \square □
A Stronger Lower Bound for d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2) \ge4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 )
We now establish the bound ℓ ≥ s G s ( n ) \ell\ge sG_s(n) ℓ ≥ s G s ( n ) under d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2) \ge4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 ) , extending beyond the range 2 d ≥ n + 3 2d \ge n+3 2 d ≥ n + 3 . When 2 d < n + 3 2d < n+3 2 d < n + 3 , two d d d -subsets may intersect in fewer than three points, so the preceding LCM representation is no longer guaranteed by the overlap argument. We therefore work directly with the degrees of the cross-ratio fields and track how they change when individual evaluation points are deleted.
For every Y ⊆ Ω Y \subseteq\Omega Y ⊆ Ω with ∣ Y ∣ ≥ 3 |Y| \ge3 ∣ Y ∣ ≥ 3 , write
m ( Y ) = [ R F ( Y ) : F ] , M = m ( Ω ) . m(Y) = [\mathcal{R}_F(Y) : F], \qquad M = m(\Omega). m ( Y ) = [ R F ( Y ) : F ] , M = m ( Ω ) .
For i ∈ [ n ] i \in[n] i ∈ [ n ] , put
m i = m ( Ω ∖ { α i } ) , g i = M m i . m_i = m(\Omega\setminus\{\alpha_i\}), \qquad g_i = \frac{M}{m_i}. m i = m ( Ω ∖ { α i }) , g i = m i M .
Thus g i g_i g i measures the part of the total degree that disappears when α i \alpha_i α i is deleted. We call coordinate i i i nondeficient if g i ≥ s g_i \ge s g i ≥ s , and deficient if g i < s g_i < s g i < s . Let
B = { i : g i < s } , b = ∣ B ∣ . \mathcal{B} = \{i : g_i < s\}, \qquad b = |\mathcal{B}|. B = { i : g i < s } , b = ∣ B ∣.
The nondeficient coordinates already contribute individual factors of size at least s s s . For a deficient coordinate, the additional factor required by the repair constraint must come from prime powers shared with other coordinates. The next lemma makes this decomposition precise.
Lemma 6. The integers g 1 , … , g n g_1,\ldots,g_n g 1 , … , g n are pairwise coprime. Put
M 0 : = M ∏ i = 1 n g i . M_0 := \frac{M}{\prod_{i=1}^{n} g_i}. M 0 := ∏ i = 1 n g i M . Then M 0 M_0 M 0 is a positive integer satisfying
M 0 = gcd ( m 1 , … , m n ) , ⋂ i = 1 n R F ( Ω ∖ { α i } ) = F q M 0 . M_0 = \gcd(m_1,\ldots,m_n), \qquad\bigcap_{i=1}^{n} \mathcal{R}_F(\Omega\setminus\{\alpha_i\}) = \mathbb{F}_{q^{M_0}}. M 0 = g cd( m 1 , … , m n ) , i = 1 ⋂ n R F ( Ω ∖ { α i }) = F q M 0 . Moreover,
M ≥ M 0 G s ( n − b ) . (14) M \ge M_0G_s(n-b). \tag*{(14)} M ≥ M 0 G s ( n − b ) . (14) Proof. For distinct i , j i,j i , j , the sets Ω ∖ { α i } \Omega\setminus\{\alpha_i\} Ω ∖ { α i } and Ω ∖ { α j } \Omega\setminus\{\alpha_j\} Ω ∖ { α j } intersect in at least three points. By Lemma 4,
M = lcm ( m i , m j ) . M = \operatorname{lcm}(m_i,m_j). M = lcm ( m i , m j ) . Fix a prime p ∣ M p \mid M p ∣ M , and write E = v p ( M ) E = v_p(M) E = v p ( M ) and e i = v p ( m i ) e_i = v_p(m_i) e i = v p ( m i ) . Thus E = max { e i , e j } E = \max\{e_i,e_j\} E = max { e i , e j } for every i ≠ j i \ne j i = j , so at most one e i e_i e i is smaller than E E E . As v p ( g i ) = E − e i v_p(g_i) = E-e_i v p ( g i ) = E − e i , at most one g i g_i g i is divisible by p p p . Hence the g i g_i g i are pairwise coprime and ∏ i = 1 n g i ∣ M \prod_{i=1}^{n} g_i \mid M ∏ i = 1 n g i ∣ M . Furthermore,
v p ( M 0 ) = E − ∑ i = 1 n ( E − e i ) = min 1 ≤ i ≤ n e i = v p ( gcd ( m 1 , … , m n ) ) . v_p(M_0) = E-\sum_{i=1}^{n}(E-e_i) = \min_{1\le i\le n} e_i = v_p(\gcd(m_1,\ldots,m_n)). v p ( M 0 ) = E − i = 1 ∑ n ( E − e i ) = 1 ≤ i ≤ n min e i = v p ( g cd( m 1 , … , m n )) . The same equality is immediate for p ∤ M p \nmid M p ∤ M , proving the gcd identity. The finite-field intersection formula now yields
⋂ i = 1 n R F ( Ω ∖ { α i } ) = ⋂ i = 1 n F q m i = F q gcd ( m 1 , … , m n ) = F q M 0 . \bigcap_{i=1}^{n} \mathcal{R}_F(\Omega\setminus\{\alpha_i\}) = \bigcap_{i=1}^{n} \mathbb{F}_{q^{m_i}} = \mathbb{F}_{q^{\gcd(m_1,\ldots,m_n)}} = \mathbb{F}_{q^{M_0}}. i = 1 ⋂ n R F ( Ω ∖ { α i }) = i = 1 ⋂ n F q m i = F q g c d ( m 1 , … , m n ) = F q M 0 . Finally, the n − b n-b n − b nondeficient g i g_i g i are pairwise coprime and at least s s s , whence
M = M 0 ∏ i = 1 n g i ≥ M 0 G s ( n − b ) . M = M_0\prod_{i=1}^{n}g_i \ge M_0G_s(n-b). M = M 0 i = 1 ∏ n g i ≥ M 0 G s ( n − b ) .
Although the g i g_i g i are pairwise coprime, they need not be coprime to M 0 M_0 M 0 . The factor M 0 M_0 M 0 is common to the cross-ratio fields obtained by deleting any one point. The next lemma tracks how much of this common degree is generated by an arbitrary subset.
Lemma 7. For Y ⊆ Ω Y \subseteq\Omega Y ⊆ Ω with ∣ Y ∣ ≥ 3 |Y| \ge3 ∣ Y ∣ ≥ 3 , define
D ( Y ) = gcd ( m ( Y ) , M 0 ) . D(Y)=\gcd(m(Y),M_0). D ( Y ) = g cd( m ( Y ) , M 0 ) . Then
D ( Y ) = [ R F ( Y ) ∩ F q M 0 : F ] . D(Y)=[\mathcal{R}_F(Y)\cap\mathbb{F}_{q^{M_0}}:F]. D ( Y ) = [ R F ( Y ) ∩ F q M 0 : F ] . For every Y ⊆ Ω Y\subseteq\Omega Y ⊆ Ω with ∣ Y ∣ ≥ 4 |Y|\ge4 ∣ Y ∣ ≥ 4 ,
m ( Y ) = D ( Y ) ∏ α i ∈ Y g i . (15) m(Y)=D(Y)\prod_{\alpha_i\in Y}g_i. \tag*{(15)} m ( Y ) = D ( Y ) α i ∈ Y ∏ g i . (15) Moreover, D ( A ) ∣ D ( B ) D(A)\mid D(B) D ( A ) ∣ D ( B ) whenever A ⊆ B A\subseteq B A ⊆ B and ∣ A ∣ ≥ 3 |A|\ge3 ∣ A ∣ ≥ 3 ; if ∣ A ∩ B ∣ ≥ 3 |A\cap B|\ge3 ∣ A ∩ B ∣ ≥ 3 , then
D ( A ∪ B ) = lcm ( D ( A ) , D ( B ) ) . D(A\cup B)=\operatorname{lcm}(D(A),D(B)). D ( A ∪ B ) = lcm ( D ( A ) , D ( B )) . In particular, for every i i i and every d d d -subset H ⊆ Ω ∖ { α i } H\subseteq\Omega\setminus\{\alpha_i\} H ⊆ Ω ∖ { α i } ,
m ( H ∪ { α i } ) m ( H ) = g i D ( H ∪ { α i } ) D ( H ) . (16) \frac{m(H\cup\{\alpha_i\})}{m(H)}
=g_i\frac{D(H\cup\{\alpha_i\})}{D(H)}. \tag*{(16)} m ( H ) m ( H ∪ { α i }) = g i D ( H ) D ( H ∪ { α i }) . (16) Proof. The finite-field intersection formula gives
R F ( Y ) ∩ F q M 0 = F q gcd ( m ( Y ) , M 0 ) = F q D ( Y ) , \mathcal{R}_F(Y)\cap\mathbb{F}_{q^{M_0}}
=\mathbb{F}_{q^{\gcd(m(Y),M_0)}}
=\mathbb{F}_{q^{D(Y)}}, R F ( Y ) ∩ F q M 0 = F q g c d ( m ( Y ) , M 0 ) = F q D ( Y ) , which proves the claimed field interpretation.
To prove (15) , fix a prime p ∣ M p\mid M p ∣ M and write
E = v p ( M ) , e i = v p ( m i ) , C p = v p ( M 0 ) = min i e i . E=v_p(M),\qquad e_i=v_p(m_i),\qquad C_p=v_p(M_0)=\min_i e_i. E = v p ( M ) , e i = v p ( m i ) , C p = v p ( M 0 ) = i min e i . By the proof of Lemma 6, at most one e i e_i e i is smaller than E E E , and v p ( g i ) = E − e i v_p(g_i)=E-e_i v p ( g i ) = E − e i . Also,
v p ( D ( Y ) ) = min { v p ( m ( Y ) ) , C p } . v_p(D(Y))=\min\{v_p(m(Y)),C_p\}. v p ( D ( Y )) = min { v p ( m ( Y )) , C p } . If every e i = E e_i=E e i = E , then C p = E C_p=E C p = E and p p p divides none of the g i g_i g i ; both sides of (15) have p p p -adic exponent v p ( m ( Y ) ) v_p(m(Y)) v p ( m ( Y )) . Otherwise, let j j j be the unique index with e j = C p < E e_j=C_p<E e j = C p < E . Then v p ( g j ) = E − C p v_p(g_j)=E-C_p v p ( g j ) = E − C p , while v p ( g i ) = 0 v_p(g_i)=0 v p ( g i ) = 0 for i ≠ j i\ne j i = j . If α j ∉ Y \alpha_j\notin Y α j ∈ / Y , then Y ⊆ Ω ∖ { α j } Y\subseteq\Omega\setminus\{\alpha_j\} Y ⊆ Ω ∖ { α j } , so v p ( m ( Y ) ) ≤ C p v_p(m(Y))\le C_p v p ( m ( Y )) ≤ C p and v p ( D ( Y ) ) = v p ( m ( Y ) ) v_p(D(Y))=v_p(m(Y)) v p ( D ( Y )) = v p ( m ( Y )) . If α j ∈ Y \alpha_j\in Y α j ∈ Y and ∣ Y ∣ ≥ 4 |Y|\ge4 ∣ Y ∣ ≥ 4 , then
Y ∪ ( Ω ∖ { α j } ) = Ω , ∣ Y ∩ ( Ω ∖ { α j } ) ∣ ≥ 3. Y\cup(\Omega\setminus\{\alpha_j\})=\Omega,\qquad
|Y\cap(\Omega\setminus\{\alpha_j\})|\ge3. Y ∪ ( Ω ∖ { α j }) = Ω , ∣ Y ∩ ( Ω ∖ { α j }) ∣ ≥ 3. Therefore Lemma 4 yields
M = lcm ( m ( Y ) , m j ) , M=\operatorname{lcm}(m(Y),m_j), M = lcm ( m ( Y ) , m j ) , so v p ( m ( Y ) ) = E v_p(m(Y))=E v p ( m ( Y )) = E because C p < E C_p<E C p < E . The exponent on the right of (15) is then C p + ( E − C p ) = E C_p+(E-C_p)=E C p + ( E − C p ) = E . The equality is trivial for p ∤ M p\nmid M p ∤ M , proving (15) .
If A ⊆ B A\subseteq B A ⊆ B , then m ( A ) ∣ m ( B ) m(A)\mid m(B) m ( A ) ∣ m ( B ) , and hence D ( A ) ∣ D ( B ) D(A)\mid D(B) D ( A ) ∣ D ( B ) . If ∣ A ∩ B ∣ ≥ 3 |A\cap B|\ge3 ∣ A ∩ B ∣ ≥ 3 , Lemma 4 gives m ( A ∪ B ) = lcm ( m ( A ) , m ( B ) ) m(A\cup B)=\operatorname{lcm}(m(A),m(B)) m ( A ∪ B ) = lcm ( m ( A ) , m ( B )) . For any prime p p p , writing c = v p ( M 0 ) c=v_p(M_0) c = v p ( M 0 ) , we have
v p ( D ( A ∪ B ) ) = min { max ( v p ( m ( A ) ) , v p ( m ( B ) ) ) , c } = max { min ( v p ( m ( A ) ) , c ) , min ( v p ( m ( B ) ) , c ) } = v p ( lcm ( D ( A ) , D ( B ) ) ) . \begin{aligned}
v_p(D(A\cup B))
&=\min\{\max(v_p(m(A)),v_p(m(B))),c\}\\
&=\max\{\min(v_p(m(A)),c),\min(v_p(m(B)),c)\}\\
&=v_p(\operatorname{lcm}(D(A),D(B))).
\end{aligned} v p ( D ( A ∪ B )) = min { max ( v p ( m ( A )) , v p ( m ( B ))) , c } = max { min ( v p ( m ( A )) , c ) , min ( v p ( m ( B )) , c )} = v p ( lcm ( D ( A ) , D ( B ))) . This proves the lcm identity. Finally, d ≥ 4 d\ge4 d ≥ 4 ensures that both H H H and H ∪ { α i } H\cup\{\alpha_i\} H ∪ { α i } satisfy (15) . Dividing the two factorizations yields (16) .
For a deficient coordinate i i i , the factor g i g_i g i in (16) is strictly smaller than s s s . On the other hand, Proposition 3 requires
m ( H ∪ { α i } ) m ( H ) ≥ s \frac{m(H\cup\{\alpha_i\})}{m(H)}\ge s m ( H ) m ( H ∪ { α i }) ≥ s
for every d d d -helper set H H H . By (16) , this forces D ( H ∪ { α i } ) / D ( H ) ≥ s / g i > 1 D(H\cup\{\alpha_i\})/D(H)\ge s/g_i>1 D ( H ∪ { α i }) / D ( H ) ≥ s / g i > 1 : the missing factor must come from the shared part. The next lemma quantifies how many distinct prime divisors of M 0 M_0 M 0 are forced in this way. For a positive integer N N N , let ω ( N ) \omega(N) ω ( N ) denote the number of distinct prime divisors of
Lemma 8. Use the notation above. Let W ⊆ Ω W \subseteq\Omega W ⊆ Ω satisfy 4 ≤ w : = ∣ W ∣ ≤ d + 1 4 \le w := \lvert W\rvert\le d+1 4 ≤ w := ∣ W ∣ ≤ d + 1 . For every deficient coordinate i ∈ B i \in B i ∈ B with α i ∈ W \alpha_i \in W α i ∈ W , put
W i = W ∖ { α i } , q i ( W ) = D ( W ) D ( W i ) . W_i = W \setminus\{\alpha_i\}, \qquad q_i(W) = \frac{D(W)}{D(W_i)}. W i = W ∖ { α i } , q i ( W ) = D ( W i ) D ( W ) . Then q i ( W ) q_i(W) q i ( W ) is a positive integer dividing M 0 M_0 M 0 , and
ω ( q i ( W ) ) ≥ d − w + 2. (17) \omega(q_i(W)) \ge d-w+2. \tag*{(17)} ω ( q i ( W )) ≥ d − w + 2. (17) If i ≠ j i \ne j i = j are deficient coordinates with α i , α j ∈ W \alpha_i,\alpha_j \in W α i , α j ∈ W and w ≥ 5 w \ge5 w ≥ 5 , then
gcd ( q i ( W ) , q j ( W ) ) = 1. \gcd(q_i(W),q_j(W))=1. g cd( q i ( W ) , q j ( W )) = 1. Consequently, if b ≥ 1 b \ge1 b ≥ 1 , then
ω ( M 0 ) ≥ d − 2 , (18) \omega(M_0) \ge d-2, \tag*{(18)} ω ( M 0 ) ≥ d − 2 , (18) and, for every 1 ≤ u ≤ min { b , d + 1 } 1 \le u \le\min\{b,d+1\} 1 ≤ u ≤ min { b , d + 1 } ,
ω ( M 0 ) ≥ u ( d + 2 − max { 5 , u } ) . (19) \omega(M_0) \ge u(d+2-\max\{5,u\}). \tag*{(19)} ω ( M 0 ) ≥ u ( d + 2 − max { 5 , u }) . (19) Proof. Since W i ⊆ W W_i \subseteq W W i ⊆ W , Lemma 7 gives D ( W i ) ∣ D ( W ) D(W_i)\mid D(W) D ( W i ) ∣ D ( W ) , so q i ( W ) q_i(W) q i ( W ) is an integer. Moreover D ( W ) ∣ M 0 D(W)\mid M_0 D ( W ) ∣ M 0 , and hence every prime divisor of q i ( W ) q_i(W) q i ( W ) divides M 0 M_0 M 0 .
We first prove (17) . Suppose, to the contrary, that
r : = ω ( q i ( W ) ) ≤ d − w + 1. r := \omega(q_i(W)) \le d-w+1. r := ω ( q i ( W )) ≤ d − w + 1. Because ∣ W i ∣ = w − 1 ≥ 3 \lvert W_i\rvert=w-1\ge3 ∣ W i ∣ = w − 1 ≥ 3 , all sets W i ∪ { y } W_i\cup\{y\} W i ∪ { y } with y ∈ Ω ∖ { α i } y\in\Omega\setminus\{\alpha_i\} y ∈ Ω ∖ { α i } contain the same three-point subset. Repeated application of the lcm identity for D D D yields
lcm y ∈ Ω ∖ { α i } D ( W i ∪ { y } ) = D ( Ω ∖ { α i } ) . \operatorname{lcm}_{y\in\Omega\setminus\{\alpha_i\}}D(W_i\cup\{y\})=D(\Omega\setminus\{\alpha_i\}). lcm y ∈ Ω ∖ { α i } D ( W i ∪ { y }) = D ( Ω ∖ { α i }) . By Lemma 6, M 0 ∣ m i M_0\mid m_i M 0 ∣ m i . Therefore
D ( Ω ∖ { α i } ) = gcd ( m i , M 0 ) = M 0 , D(\Omega\setminus\{\alpha_i\})=\gcd(m_i,M_0)=M_0, D ( Ω ∖ { α i }) = g cd( m i , M 0 ) = M 0 , and hence
lcm y ∈ Ω ∖ { α i } D ( W i ∪ { y } ) = M 0 . (20) \operatorname{lcm}_{y\in\Omega\setminus\{\alpha_i\}}D(W_i\cup\{y\})=M_0. \tag*{(20)} lcm y ∈ Ω ∖ { α i } D ( W i ∪ { y }) = M 0 . (20) For each prime p ∣ q i ( W ) p\mid q_i(W) p ∣ q i ( W ) , choose a point y p ≠ α i y_p\ne\alpha_i y p = α i such that
D ( W i ∪ { y p } ) = v p ( M 0 ) ; D(W_i\cup\{y_p\})=v_p(M_0); D ( W i ∪ { y p }) = v p ( M 0 ) ; such a point exists by (20) . Let
S = W i ∪ { y p : p ∣ q i ( W ) } . S=W_i\cup\{y_p:p\mid q_i(W)\}. S = W i ∪ { y p : p ∣ q i ( W )} . Then
∣ S ∣ ≤ ( w − 1 ) + r ≤ ( w − 1 ) + ( d − w + 1 ) = d . \lvert S\rvert\le(w-1)+r\le(w-1)+(d-w+1)=d. ∣ S ∣ ≤ ( w − 1 ) + r ≤ ( w − 1 ) + ( d − w + 1 ) = d . Since S ⊆ Ω ∖ { α i } S\subseteq\Omega\setminus\{\alpha_i\} S ⊆ Ω ∖ { α i } , we can extend S S S to a d d d -subset
H ⊆ Ω ∖ { α i } . H\subseteq\Omega\setminus\{\alpha_i\}. H ⊆ Ω ∖ { α i } . We claim that D ( W ) ∣ D ( H ) D(W)\mid D(H) D ( W ) ∣ D ( H ) . If p ∣ q i ( W ) p\mid q_i(W) p ∣ q i ( W ) , the choice of y p y_p y p and D ( H ) ∣ M 0 D(H)\mid M_0 D ( H ) ∣ M 0 give
v p ( D ( H ) ) = v p ( M 0 ) ≥ v p ( D ( W ) ) . v_p(D(H))=v_p(M_0)\ge v_p(D(W)). v p ( D ( H )) = v p ( M 0 ) ≥ v p ( D ( W )) . If p ∤ q i ( W ) p\nmid q_i(W) p ∤ q i ( W ) , then
v p ( D ( W ) ) = v p ( D ( W i ) ) ≤ v p ( D ( H ) ) , v_p(D(W))=v_p(D(W_i))\le v_p(D(H)), v p ( D ( W )) = v p ( D ( W i )) ≤ v p ( D ( H )) , since W i ⊆ H W_i\subseteq H W i ⊆ H . Thus D ( W ) ∣ D ( H ) D(W)\mid D(H) D ( W ) ∣ D ( H ) . Moreover, H ∩ W = W i H\cap W=W_i H ∩ W = W i has at least three points, so
D ( H ∪ { α i } ) = lcm ( D ( H ) , D ( W ) ) = D ( H ) . D(H\cup\{\alpha_i\})=\operatorname{lcm}(D(H),D(W))=D(H). D ( H ∪ { α i }) = lcm ( D ( H ) , D ( W )) = D ( H ) .
Using (16) , we now obtain
m ( H ∪ { α i } ) m ( H ) = g i D ( H ∪ { α i } ) D ( H ) = g i < s , \frac{m(H \cup\{\alpha_i\})}{m(H)} = g_i \frac{D(H \cup\{\alpha_i\})}{D(H)} = g_i < s, m ( H ) m ( H ∪ { α i }) = g i D ( H ) D ( H ∪ { α i }) = g i < s ,
which contradicts Proposition 3. Hence ω ( q i ( W ) ) ≥ d − w + 2 \omega(q_i(W)) \ge d-w+2 ω ( q i ( W )) ≥ d − w + 2 .
It remains to prove the separation assertion. Let i ≠ j i \ne j i = j be deficient coordinates in W W W , with w ≥ 5 w \ge5 w ≥ 5 . Since ∣ W i ∩ W j ∣ = w − 2 ≥ 3 |W_i \cap W_j|=w-2 \ge3 ∣ W i ∩ W j ∣ = w − 2 ≥ 3 , the lcm identity yields
D ( W ) = lcm ( D ( W i ) , D ( W j ) ) . D(W)=\operatorname{lcm}(D(W_i),D(W_j)). D ( W ) = lcm ( D ( W i ) , D ( W j )) .
Since both D ( W i ) D(W_i) D ( W i ) and D ( W j ) D(W_j) D ( W j ) divide D ( W ) D(W) D ( W ) ,
gcd ( q i ( W ) , q j ( W ) ) = D ( W ) lcm ( D ( W i ) , D ( W j ) ) = 1. \gcd(q_i(W),q_j(W))=\frac{D(W)}{\operatorname{lcm}(D(W_i),D(W_j))}=1. g cd( q i ( W ) , q j ( W )) = lcm ( D ( W i ) , D ( W j )) D ( W ) = 1.
If b ≥ 1 b \ge1 b ≥ 1 , choose a deficient coordinate i i i and a four-point set W W W containing α i \alpha_i α i . Then (17) gives
ω ( M 0 ) ≥ ω ( q i ( W ) ) ≥ d − 2 , \omega(M_0) \ge\omega(q_i(W)) \ge d-2, ω ( M 0 ) ≥ ω ( q i ( W )) ≥ d − 2 ,
which proves (18) .
Finally, fix 1 ≤ u ≤ min { b , d + 1 } 1 \le u \le\min\{b,d+1\} 1 ≤ u ≤ min { b , d + 1 } and choose u u u distinct deficient coordinates. Extend their evaluation points to a set W W W of size
w = max { 5 , u } . w=\max\{5,u\}. w = max { 5 , u } .
Such a set exists because w ≤ d + 1 ≤ n w \le d+1 \le n w ≤ d + 1 ≤ n . For these u u u coordinates, the quotients q i ( W ) q_i(W) q i ( W ) are pairwise coprime, each divides M 0 M_0 M 0 , and each has at least d − w + 2 d-w+2 d − w + 2 distinct prime divisors. Therefore
ω ( M 0 ) ≥ u ( d − w + 2 ) = u ( d + 2 − max { 5 , u } ) , \omega(M_0) \ge u(d-w+2)=u(d+2-\max\{5,u\}), ω ( M 0 ) ≥ u ( d − w + 2 ) = u ( d + 2 − max { 5 , u }) ,
which is (19) .
Let
c s = π ( s − 1 ) . c_s=\pi(s-1). c s = π ( s − 1 ) .
We first record two elementary estimates for G s G_s G s . The first compares G s ( n ) G_s(n) G s ( n ) with G s ( n − b ) G_s(n-b) G s ( n − b ) ; the second supplies the prime products needed in the proof of the degree bound.
Lemma 9. For s ≥ 2 s \ge2 s ≥ 2 , n ≥ 1 n \ge1 n ≥ 1 , and 0 ≤ b ≤ n 0 \le b \le n 0 ≤ b ≤ n ,
G s ( n ) ≤ G s ( n − b ) p n + c s b . (21) G_s(n) \le G_s(n-b)p_{n+c_s}^{b}. \tag*{(21)} G s ( n ) ≤ G s ( n − b ) p n + c s b . (21) Moreover,
G s ( n ) ≤ ∏ j = 1 n p c s + j ≤ p n + c s # . (22) G_s(n) \le\prod_{j=1}^{n}p_{c_s+j} \le p_{n+c_s}^{\#}. \tag*{(22)} G s ( n ) ≤ j = 1 ∏ n p c s + j ≤ p n + c s # . (22)
Proof. Choose pairwise coprime integers a 1 , … , a n − b ≥ s a_1,\ldots,a_{n-b} \ge s a 1 , … , a n − b ≥ s whose product is G s ( n − b ) G_s(n-b) G s ( n − b ) . If some a j a_j a j has a prime divisor p ≥ s p \ge s p ≥ s and a j ≠ p a_j \ne p a j = p , then replacing a j a_j a j by p p p preserves pairwise coprimality and the condition a j ≥ s a_j \ge s a j ≥ s , while decreasing the product. Thus, in a minimizing family, every member having a prime divisor at least s s s is itself such a prime.
The primes
p c s + 1 , … , p c s + n p_{c_s+1},\ldots,p_{c_s+n} p c s + 1 , … , p c s + n
are the first n n n primes at least s s s . At most n − b n-b n − b of them occur among the a j a_j a j , so at least b b b are unused. Append any b b b unused primes to the family. They remain coprime to all the a j a_j a j , and each is at most p n + c s p_{n+c_s} p n + c s . Therefore
G s ( n ) ≤ G s ( n − b ) p n + c s b , G_s(n) \le G_s(n-b)p_{n+c_s}^{b}, G s ( n ) ≤ G s ( n − b ) p n + c s b ,
which proves (21) . The first n n n primes at least s s s form a feasible family, so
G s ( n ) ≤ ∏ j = 1 n p c s + j ≤ p n + c s # . G_s(n) \le\prod_{j=1}^{n}p_{c_s+j} \le p_{n+c_s}^{\#}. G s ( n ) ≤ j = 1 ∏ n p c s + j ≤ p n + c s # .
proving (22) .
The preceding comparison bounds the loss from the b b b deficient coordinates, while Lemma 8 forces additional prime factors into M 0 M_0 M 0 . The following estimates show that these shared factors compensate for the missing private factors. We state only the comparisons needed below; their proof, including the auxiliary prime-product estimates, is given in Appendix A.
Lemma 10. Let s ≥ 2 s \ge2 s ≥ 2 , n ≥ 1 n \ge1 n ≥ 1 , and t ≥ 3 t \ge3 t ≥ 3 be integers, and suppose n + c s ≤ 4 t 2 n+c_s \le4t^2 n + c s ≤ 4 t 2 . Then
G s ( n ) < G s ( n − 1 ) p t + 1 # . (23) G_s(n) < G_s(n-1)p_{t+1}^{\#}. \tag*{(23)} G s ( n ) < G s ( n − 1 ) p t + 1 # . (23) Moreover, for every 2 ≤ b ≤ n 2 \le b \le n 2 ≤ b ≤ n ,
G s ( n ) < G s ( n − b ) p b t # . (24) G_s(n) < G_s(n-b)p_{bt}^{\#}. \tag*{(24)} G s ( n ) < G s ( n − b ) p b t # . (24)
We now combine the structural and arithmetic estimates to obtain the cross-ratio degree bound in the entire quadratic parameter range.
Proposition 4. Suppose that RSK ( n , k , Ω ) \operatorname{RSK}(n,k,\Omega) RSK ( n , k , Ω ) admits cut-set-optimal F F F -linear repair of every coordinate from every d d d -helper set, where 3 ≤ k < d ≤ n − 1 3 \le k < d \le n-1 3 ≤ k < d ≤ n − 1 and s = d + 1 − k s=d+1-k s = d + 1 − k . If
d ( d + 2 ) ≥ 4 ( n + 1 ) , d(d+2) \ge4(n+1), d ( d + 2 ) ≥ 4 ( n + 1 ) , then
[ R F ( Ω ) : F ] ≥ G s ( n ) . [\mathcal{R}_F(\Omega):F] \ge G_s(n). [ R F ( Ω ) : F ] ≥ G s ( n ) . For d ≥ 6 d \ge6 d ≥ 6 , the same conclusion holds under the more general condition
n + c s ≤ ( ⌊ d 2 ⌋ + 2 ) ⌈ d 2 ⌉ . n+c_s \le\left(\left\lfloor\frac{d}{2}\right\rfloor+2\right)\left\lceil\frac{d}{2}\right\rceil. n + c s ≤ ( ⌊ 2 d ⌋ + 2 ) ⌈ 2 d ⌉ .
Proof. Write M = [ R F ( Ω ) : F ] M=[\mathcal{R}_F(\Omega):F] M = [ R F ( Ω ) : F ] , and let b b b be the number of deficient coordinates. If n = d + 1 n=d+1 n = d + 1 , Theorem 3 gives M ≥ G s ( n ) M \ge G_s(n) M ≥ G s ( n ) . Hence assume n ≥ d + 2 n \ge d+2 n ≥ d + 2 . The case d = 4 d=4 d = 4 is impossible under the quadratic condition, which would imply n ≤ 5 n \le5 n ≤ 5 .
First suppose d ≥ 6 d \ge6 d ≥ 6 . Put
t = ⌊ d 2 ⌋ , r = ⌈ d 2 ⌉ + 2. t=\left\lfloor\frac{d}{2}\right\rfloor,\qquad r=\left\lceil\frac{d}{2}\right\rceil+2. t = ⌊ 2 d ⌋ , r = ⌈ 2 d ⌉ + 2.
Since 2 ≤ s ≤ d − 2 2 \le s \le d-2 2 ≤ s ≤ d − 2 and every prime other than 2 2 2 is odd, we have c s = π ( s − 1 ) ≤ t − 1 c_s=\pi(s-1) \le t-1 c s = π ( s − 1 ) ≤ t − 1 . In particular, d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2) \ge4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 ) implies
n + c s ≤ ⌊ ( d + 1 ) 2 4 ⌋ + t = r t . \begin{aligned}
n+c_s \le\left\lfloor\frac{(d+1)^2}{4}\right\rfloor+t \\
&=rt.
\end{aligned} n + c s ≤ ⌊ 4 ( d + 1 ) 2 ⌋ + t = r t .
It therefore suffices to assume n + c s ≤ r t n+c_s \le rt n + c s ≤ r t , as in the more general assertion. Moreover, r ≥ 5 r \ge5 r ≥ 5 , t ≥ 3 t \ge3 t ≥ 3 , r + t = d + 2 r+t=d+2 r + t = d + 2 , d − 2 ≥ t + 1 d-2 \ge t+1 d − 2 ≥ t + 1 , and r t ≤ 2 t 2 < 4 t 2 rt \le2t^2 < 4t^2 r t ≤ 2 t 2 < 4 t 2 .
If b = 0 b=0 b = 0 , (13) immediately implies M ≥ G s ( n ) M \ge G_s(n) M ≥ G s ( n ) . If b = 1 b=1 b = 1 , (17) yields
ω ( M 0 ) ≥ d − 2 ≥ t + 1. \omega(M_0) \ge d-2 \ge t+1. ω ( M 0 ) ≥ d − 2 ≥ t + 1.
Consequently, by (13) and (22),
M ≥ M 0 G s ( n − 1 ) ≥ p t + 1 # G s ( n − 1 ) > G s ( n ) . M \ge M_0G_s(n-1) \ge p_{t+1}^{\#}G_s(n-1) > G_s(n). M ≥ M 0 G s ( n − 1 ) ≥ p t + 1 # G s ( n − 1 ) > G s ( n ) .
If 2 ≤ b < r 2 \le b < r 2 ≤ b < r , then max { 5 , b } ≤ r \max\{5,b\} \le r max { 5 , b } ≤ r , and (18) with u = b u=b u = b gives
ω ( M 0 ) ≥ b ( d + 2 − max { 5 , b } ) ≥ b t . \omega(M_0) \ge b(d+2-\max\{5,b\}) \ge bt. ω ( M 0 ) ≥ b ( d + 2 − max { 5 , b }) ≥ b t .
Hence (23) implies
M ≥ M 0 G s ( n − b ) ≥ p b t # G s ( n − b ) > G s ( n ) . M \ge M_0G_s(n-b) \ge p_{bt}^{\#}G_s(n-b) > G_s(n). M ≥ M 0 G s ( n − b ) ≥ p b t # G s ( n − b ) > G s ( n ) .
Finally, if b ≥ r b \ge r b ≥ r , taking u = r u=r u = r in (18) yields
ω ( M 0 ) ≥ r ( d + 2 − r ) = r t . \omega(M_0) \ge r(d+2-r)=rt. ω ( M 0 ) ≥ r ( d + 2 − r ) = r t .
Therefore, by (22) ,
M ≥ M 0 ≥ p r t # ≥ p n + c s # ≥ G s ( n ) . M \ge M_0 \ge p_{r_t}^{\#} \ge p_{n+c_s}^{\#} \ge G_s(n). M ≥ M 0 ≥ p r t # ≥ p n + c s # ≥ G s ( n ) .
This proves the assertion for d ≥ 6 d \ge6 d ≥ 6 .
It remains to consider d = 5 d=5 d = 5 : the parameter condition and n ≥ d + 2 n \ge d+2 n ≥ d + 2 force n = 7 n=7 n = 7 , while s ∈ { 2 , 3 } s \in\{2,3\} s ∈ { 2 , 3 } and c s ≤ 1 c_s \le1 c s ≤ 1 . For distinct i , j ∈ [ 7 ] i,j \in[7] i , j ∈ [ 7 ] , set
Y i j = Ω ∖ { α i , α j } , h i j = M 0 D ( Y i j ) . Y_{ij}=\Omega\setminus\{\alpha_i,\alpha_j\}, \qquad h_{ij}=\frac{M_0}{D(Y_{ij})}. Y ij = Ω ∖ { α i , α j } , h ij = D ( Y ij ) M 0 .
By Lemmas 6 and 7, D ( Ω ∖ { α j } ) = M 0 D(\Omega\setminus\{\alpha_j\})=M_0 D ( Ω ∖ { α j }) = M 0 . Thus, if i ∈ B i \in\mathcal{B} i ∈ B and j ≠ i j \ne i j = i , then (16) and Proposition 3 imply
s ≤ m ( Ω ∖ { α j } ) m ( Y i j ) = g i h i j , s \le\frac{m(\Omega\setminus\{\alpha_j\})}{m(Y_{ij})}=g_i h_{ij}, s ≤ m ( Y ij ) m ( Ω ∖ { α j }) = g i h ij ,
so h i j > 1 h_{ij}>1 h ij > 1 .
For two distinct unordered pairs { i , j } \{i,j\} { i , j } and { u , v } \{u,v\} { u , v } , the sets Y i j Y_{ij} Y ij and Y u v Y_{uv} Y uv intersect in at least three points, while their union is either Ω \Omega Ω or Ω \Omega Ω with one point removed. In either case its D D D -value is M 0 M_0 M 0 . The lcm identity in Lemma 7 therefore gives
M 0 = lcm ( D ( Y i j ) , D ( Y u v ) ) , M_0=\operatorname{lcm}(D(Y_{ij}),D(Y_{uv})), M 0 = lcm ( D ( Y ij ) , D ( Y uv )) ,
which implies gcd ( h i j , h u v ) = 1 \gcd(h_{ij},h_{uv})=1 g cd( h ij , h uv ) = 1 . Thus the nontrivial h i j h_{ij} h ij indexed by pairs meeting B \mathcal{B} B contribute distinct prime divisors of M 0 M_0 M 0 . Consequently,
ω ( M 0 ) ≥ ( 7 2 ) − ( 7 − b 2 ) = { 6 , b = 1 , ≥ 11 , b ≥ 2. \omega(M_0)\ge\binom{7}{2}-\binom{7-b}{2}
=\begin{cases}
6, & b=1,\\
\ge11, & b\ge2.
\end{cases} ω ( M 0 ) ≥ ( 2 7 ) − ( 2 7 − b ) = { 6 , ≥ 11 , b = 1 , b ≥ 2.
The case b = 0 b=0 b = 0 again follows from (14) . If b = 1 b=1 b = 1 , then p 7 + c s ≤ p 8 = 19 < p 6 # p_{7+c_s}\le p_8=19<p_6^{\#} p 7 + c s ≤ p 8 = 19 < p 6 # , and (21) gives
M ≥ M 0 G s ( 6 ) ≥ p 6 # G s ( 6 ) > p 7 + c s G s ( 6 ) ≥ G s ( 7 ) . M\ge M_0G_s(6)\ge p_6^{\#}G_s(6)>p_{7+c_s}G_s(6)\ge G_s(7). M ≥ M 0 G s ( 6 ) ≥ p 6 # G s ( 6 ) > p 7 + c s G s ( 6 ) ≥ G s ( 7 ) .
If b ≥ 2 b\ge2 b ≥ 2 , (22) gives directly
M ≥ M 0 ≥ p 11 # > p 7 + c s # ≥ G s ( 7 ) . M\ge M_0\ge p_{11}^{\#}>p_{7+c_s}^{\#}\ge G_s(7). M ≥ M 0 ≥ p 11 # > p 7 + c s # ≥ G s ( 7 ) .
This completes the proof.
Together with the fact that the cross-ratio degree divides ℓ / s \ell/s ℓ / s , Proposition 4 yields the lower bound on subpacketization in the same parameter range.
Theorem 5. For every prime power q q q and all 3 ≤ k < d ≤ n − 1 3\le k<d\le n-1 3 ≤ k < d ≤ n − 1 , if
d ( d + 2 ) ≥ 4 ( n + 1 ) , d(d+2)\ge4(n+1), d ( d + 2 ) ≥ 4 ( n + 1 ) , then
ℓ min ( n , k , d ; q ) ≥ s G s ( n ) ≥ s Δ s ( n , d ) . \ell_{\min}(n,k,d;q)\ge sG_s(n)\ge s\Delta_s(n,d). ℓ m i n ( n , k , d ; q ) ≥ s G s ( n ) ≥ s Δ s ( n , d ) . Proof. Let F = F q F=\mathbb{F}_q F = F q , K = F q ℓ K=\mathbb{F}_{q^\ell} K = F q ℓ , and let RSK ( n , k , Ω ) \operatorname{RSK}(n,k,\Omega) RSK ( n , k , Ω ) admit cut-set-optimal F F F -linear repair of every coordinate from every d d d -helper set. By Proposition 4,
[ R F ( Ω ) : F ] ≥ G s ( n ) . [\mathcal{R}_F(\Omega):F]\ge G_s(n). [ R F ( Ω ) : F ] ≥ G s ( n ) . By Proposition 3, this degree divides ℓ / s \ell/s ℓ / s . It follows that ℓ ≥ s G s ( n ) \ell\ge sG_s(n) ℓ ≥ s G s ( n ) . Minimizing over all such codes and using (11) completes the proof.
The condition d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2)\ge4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 ) contains the entire range 2 d ≥ n + 3 2d\ge n+3 2 d ≥ n + 3 . Indeed, 2 d ≥ n + 3 2d\ge n+3 2 d ≥ n + 3 implies n ≤ 2 d − 3 n\le2d-3 n ≤ 2 d − 3 , and since d ≥ 4 d\ge4 d ≥ 4 ,
d ( d + 2 ) − 4 ( n + 1 ) ≥ ( d − 2 ) ( d − 4 ) ≥ 0. d(d+2)-4(n+1)\ge(d-2)(d-4)\ge0. d ( d + 2 ) − 4 ( n + 1 ) ≥ ( d − 2 ) ( d − 4 ) ≥ 0.
Construction and Minimum Subpacketization
In this section, we construct RS codes with subpacketization s Δ s ( n , d ) s\Delta_s(n,d) s Δ s ( n , d ) for every admissible choice of parameters. Combining this construction with the lower bound from § 3 determines the minimum subpacketization when d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2)\ge4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 ) . We then derive an exact threshold for a closed-form expression for G s ( m ) G_s(m) G s ( m ) and a finite formula valid for all m m m .
Construction from Feasible Degree Tuples
The feasibility condition defining Δ s ( n , d ) \Delta_s(n,d) Δ s ( n , d ) is exactly the relative-degree condition needed to apply Theorem 2. Indeed, for a failed coordinate i i i and a helper set H H H , if [ F ( α j ) : F ] = a j [F(\alpha_j):F]=a_j [ F ( α j ) : F ] = a j and F H = F ( α h : h ∈ H ) F_H=F(\alpha_h:h\in H) F H = F ( α h : h ∈ H ) , then the compositum rule for finite fields gives
[ F H ( α i ) : F H ] = lcm ( a i , { a h : h ∈ H } ) lcm ( a h : h ∈ H ) . [F_H(\alpha_i):F_H]=\frac{\operatorname{lcm}(a_i,\{a_h:h\in H\})}{\operatorname{lcm}(a_h:h\in H)}. [ F H ( α i ) : F H ] = lcm ( a h : h ∈ H ) lcm ( a i , { a h : h ∈ H }) .
Thus feasibility guarantees that this relative degree is at least s s s . Consequently, Theorem 2 provides the required repair subspace for every such pair ( i , H ) (i,H) ( i , H ) . A dual check polynomial vanishing at the nonhelpers then restricts the parity-check equations to H ∪ { i } H\cup\{i\} H ∪ { i } .
Theorem 6. Let q q q be a prime power and F = F q F=\mathbb{F}_q F = F q . Let 3 ≤ k < d ≤ n − 1 3\le k<d\le n-1 3 ≤ k < d ≤ n − 1 and set s = d + 1 − k ≥ 2 s=d+1-k\ge2 s = d + 1 − k ≥ 2 . Suppose that positive integers a 1 , … , a n a_1,\ldots,a_n a 1 , … , a n form a feasible ( n , d , s ) (n,d,s) ( n , d , s ) -tuple. Put
M = lcm ( a 1 , … , a n ) , E = F q M , K = F q s M . M=\operatorname{lcm}(a_1,\ldots,a_n),\qquad E=\mathbb{F}_{q^M},\qquad K=\mathbb{F}_{q^{sM}}. M = lcm ( a 1 , … , a n ) , E = F q M , K = F q s M . Choose α i ∈ E \alpha_i\in E α i ∈ E with [ F ( α i ) : F ] = a i [F(\alpha_i):F]=a_i [ F ( α i ) : F ] = a i and set
C = RS K ( n , k , { α 1 , … , α n } ) . C=\operatorname{RS}_K(n,k,\{\alpha_1,\ldots,\alpha_n\}). C = RS K ( n , k , { α 1 , … , α n }) . Then C C C repairs every failed coordinate from every d d d -element helper set by an F F F -linear scheme meeting the cut-set bound. Its subpacketization is ℓ = s M \ell=sM ℓ = s M . Consequently,
ℓ min ( n , k , d ; q ) ≤ s Δ s ( n , d ) . \ell_{\min}(n,k,d;q)\le s\Delta_s(n,d). ℓ m i n ( n , k , d ; q ) ≤ s Δ s ( n , d ) .
Proof. Feasibility first implies that a 1 , … , a n a_1,\ldots,a_n a 1 , … , a n are pairwise distinct. Indeed, if a i = a j a_i=a_j a i = a j for some i ≠ j i\ne j i = j , choose a d d d -helper set H H H that contains j j j but not i i i . Then
lcm ( a i , { a h : h ∈ H } ) lcm ( a h : h ∈ H ) = 1 , \frac{\operatorname{lcm}(a_i,\{a_h:h\in H\})}{\operatorname{lcm}(a_h:h\in H)}=1, lcm ( a h : h ∈ H ) lcm ( a i , { a h : h ∈ H }) = 1 ,
contradicting s ≥ 2 s\ge2 s ≥ 2 .
Since every a i a_i a i divides M M M , the field E = F q M E=\mathbb{F}_{q^M} E = F q M contains the subfield F q a i \mathbb{F}_{q^{a_i}} F q a i , and hence contains elements of exact degree a i a_i a i over F F F . Choose such an element α i \alpha_i α i for every i i i . Because the degrees a i a_i a i are distinct, the chosen evaluation points are automatically pairwise distinct.
Fix a failed coordinate i ∈ [ n ] i\in[n] i ∈ [ n ] and a helper set H ⊆ [ n ] ∖ { i } H\subseteq[n]\setminus\{i\} H ⊆ [ n ] ∖ { i } with ∣ H ∣ = d |H|=d ∣ H ∣ = d . The following fields and subspaces refer to this fixed pair ( i , H ) (i,H) ( i , H ) . Put
L H = lcm ( a h : h ∈ H ) , L = lcm ( L H , a i ) . L_H=\operatorname{lcm}(a_h:h\in H),\qquad L=\operatorname{lcm}(L_H,a_i). L H = lcm ( a h : h ∈ H ) , L = lcm ( L H , a i ) .
Since the compositum of finite subfields has degree equal to the least common multiple of their degrees,
F ( α h : h ∈ H ) = F q L H , F ( α h : h ∈ H , α i ) = F q L . F(\alpha_h:h\in H)=\mathbb{F}_{q^{L_H}},\qquad F(\alpha_h:h\in H,\alpha_i)=\mathbb{F}_{q^L}. F ( α h : h ∈ H ) = F q L H , F ( α h : h ∈ H , α i ) = F q L .
Since L H ∣ L ∣ M L_H\mid L\mid M L H ∣ L ∣ M , we have the tower
F H : = F q L H ⊂ E H : = F q L ⊂ K 0 : = F q s L ⊆ K . F_H:=\mathbb{F}_{q^{L_H}}\subset E_H:=\mathbb{F}_{q^L}\subset K_0:=\mathbb{F}_{q^{sL}}\subseteq K. F H := F q L H ⊂ E H := F q L ⊂ K 0 := F q s L ⊆ K .
Here E H = F H ( α i ) E_H=F_H(\alpha_i) E H = F H ( α i ) , and feasibility gives [ E H : F H ] = L / L H ≥ s [E_H:F_H]=L/L_H\ge s [ E H : F H ] = L / L H ≥ s . We first work in K 0 K_0 K 0 because [ K 0 : E H ] = s [K_0:E_H]=s [ K 0 : E H ] = s , as required by Theorem 2. That theorem provides an F H F_H F H -subspace S 0 ⊆ K 0 S_0\subseteq K_0 S 0 ⊆ K 0 such that
dim F H S 0 = L L H , K 0 = ⨁ u = 0 s − 1 α i u S 0 . \dim_{F_H}S_0=\frac{L}{L_H},\qquad K_0=\bigoplus_{u=0}^{s-1}\alpha_i^uS_0. dim F H S 0 = L H L , K 0 = u = 0 ⨁ s − 1 α i u S 0 .
Let
r = [ K : K 0 ] = M L , r=[K:K_0]=\frac{M}{L}, r = [ K : K 0 ] = L M ,
choose a K 0 K_0 K 0 -basis γ 1 , … , γ r \gamma_1,\ldots,\gamma_r γ 1 , … , γ r of K K K , and define
S = ⨁ v = 1 r γ v S 0 . S=\bigoplus_{v=1}^{r}\gamma_vS_0. S = v = 1 ⨁ r γ v S 0 .
Then
K = ⨁ v = 1 r γ v K 0 = ⨁ u = 0 s − 1 α i u S . K = \bigoplus_{v=1}^{r} \gamma_v K_0 = \bigoplus_{u=0}^{s-1} \alpha_i^u S. K = v = 1 ⨁ r γ v K 0 = u = 0 ⨁ s − 1 α i u S .
and
dim F H S = r L L H = M L H = [ K : F H ] s . \dim_{F_H} S = r\frac{L}{L_H} = \frac{M}{L_H} = \frac{[K:F_H]}{s}. dim F H S = r L H L = L H M = s [ K : F H ] .
We next realize this local decomposition by dual parity checks supported on the failed coordinate and the chosen helpers. Let
Z = [ n ] ∖ ( H ∪ { i } ) , Λ i , H ( x ) = ∏ z ∈ Z ( x − α z ) . Z = [n] \setminus(H \cup\{i\}), \qquad\Lambda_{i,H}(x) = \prod_{z\in Z}(x-\alpha_z). Z = [ n ] ∖ ( H ∪ { i }) , Λ i , H ( x ) = z ∈ Z ∏ ( x − α z ) .
The empty product is understood to be 1. For 0 ≤ u ≤ s − 1 0 \le u \le s-1 0 ≤ u ≤ s − 1 ,
deg ( x u Λ i , H ( x ) ) ≤ ( s − 1 ) + ( n − d − 1 ) = n − k − 1. \deg(x^u\Lambda_{i,H}(x)) \le(s-1)+(n-d-1)=n-k-1. deg ( x u Λ i , H ( x )) ≤ ( s − 1 ) + ( n − d − 1 ) = n − k − 1.
Thus, for every scalar e ∈ K e \in K e ∈ K , the evaluation vector of e x u Λ i , H ( x ) e x^u\Lambda_{i,H}(x) e x u Λ i , H ( x ) with the dual multipliers w j w_j w j lies in C ⊥ C^\perp C ⊥ .
Set t H = M / L H t_H=M/L_H t H = M / L H and choose an F H F_H F H -basis e 1 , … , e t H e_1,\ldots,e_{t_H} e 1 , … , e t H of S S S . For a codeword c = ( c 1 , … , c n ) ∈ C c=(c_1,\ldots,c_n)\in C c = ( c 1 , … , c n ) ∈ C , define the values downloaded from helper h ∈ H h\in H h ∈ H by
D h , m = Tr K / F H ( c h e m w h Λ i , H ( α h ) ) , 1 ≤ m ≤ t H . D_{h,m}=\operatorname{Tr}_{K/F_H}(c_he_mw_h\Lambda_{i,H}(\alpha_h)), \qquad1\le m\le t_H. D h , m = Tr K / F H ( c h e m w h Λ i , H ( α h )) , 1 ≤ m ≤ t H .
The parity checks from e m x u Λ i , H ( x ) e_mx^u\Lambda_{i,H}(x) e m x u Λ i , H ( x ) give, for 1 ≤ m ≤ t H 1\le m\le t_H 1 ≤ m ≤ t H and 0 ≤ u ≤ s − 1 0\le u\le s-1 0 ≤ u ≤ s − 1 ,
c i e m w i α i u Λ i , H ( α i ) = − ∑ h ∈ H c h e m w h α h u Λ i , H ( α h ) , c_ie_mw_i\alpha_i^u\Lambda_{i,H}(\alpha_i)
=-\sum_{h\in H}c_he_mw_h\alpha_h^u\Lambda_{i,H}(\alpha_h), c i e m w i α i u Λ i , H ( α i ) = − h ∈ H ∑ c h e m w h α h u Λ i , H ( α h ) ,
because Λ i , H ( α z ) = 0 \Lambda_{i,H}(\alpha_z)=0 Λ i , H ( α z ) = 0 for every nonhelper z ∈ Z z\in Z z ∈ Z . Taking Tr K / F H \operatorname{Tr}_{K/F_H} Tr K / F H and using α h ∈ F H \alpha_h\in F_H α h ∈ F H yields
Tr K / F H ( c i e m w i α i u Λ i , H ( α i ) ) = − ∑ h ∈ H α h u D h , m . \operatorname{Tr}_{K/F_H}(c_ie_mw_i\alpha_i^u\Lambda_{i,H}(\alpha_i))
=-\sum_{h\in H}\alpha_h^uD_{h,m}. Tr K / F H ( c i e m w i α i u Λ i , H ( α i )) = − h ∈ H ∑ α h u D h , m .
The direct-sum decomposition of K K K shows that
{ e m α i u : 1 ≤ m ≤ t H , 0 ≤ u ≤ s − 1 } \{e_m\alpha_i^u: 1\le m\le t_H,\ 0\le u\le s-1\} { e m α i u : 1 ≤ m ≤ t H , 0 ≤ u ≤ s − 1 }
is an F H F_H F H -basis of K K K . Since w i Λ i , H ( α i ) ≠ 0 w_i\Lambda_{i,H}(\alpha_i)\ne0 w i Λ i , H ( α i ) = 0 , multiplying this basis by that scalar produces another F H F_H F H -basis of K K K . The trace pairing
K × K ⟶ F H , ( x , y ) ⟼ Tr K / F H ( x y ) , K\times K\longrightarrow F_H,\qquad(x,y)\longmapsto\operatorname{Tr}_{K/F_H}(xy), K × K ⟶ F H , ( x , y ) ⟼ Tr K / F H ( x y ) ,
is nondegenerate. Hence the s t H = [ K : F H ] st_H=[K:F_H] s t H = [ K : F H ] trace values on the left uniquely determine c i c_i c i : if all of them vanish, c i c_i c i is orthogonal under the trace pairing to an F H F_H F H -basis of K K K , and therefore c i = 0 c_i=0 c i = 0 .
Thus the t H t_H t H values D h , m D_{h,m} D h , m from each helper suffice for all u = 0 , … , s − 1 u=0,\ldots,s-1 u = 0 , … , s − 1 . Each D h , m D_{h,m} D h , m is one symbol over F H F_H F H , hence represents [ F H : F ] = L H [F_H:F]=L_H [ F H : F ] = L H symbols over F F F . Moreover, after fixing an F F F -basis of F H F_H F H , its coordinate maps are F F F -linear functionals of the helper symbol c h c_h c h . Thus each helper sends
t H [ F H : F ] = M L H L H = M = ℓ s t_H[F_H:F]=\frac{M}{L_H}L_H=M=\frac{\ell}{s} t H [ F H : F ] = L H M L H = M = s ℓ
symbols over F F F . The total repair bandwidth is therefore d M = d ℓ / s dM=d\ell/s d M = d ℓ / s , exactly the cut-set bound. Since ( i , H ) (i,H) ( i , H ) was arbitrary, the code admits optimal F F F -linear repair in every required repair configuration.
Remark 3. The values Λ i , H ( α h ) \Lambda_{i,H}(\alpha_h) Λ i , H ( α h ) need not lie in F H F_H F H , because only the factors α h u \alpha_h^u α h u are moved through the trace. Moreover, the repair subspace may depend on ( i , H ) (i,H) ( i , H ) : the model requires an optimal scheme for every repair scenario, not a common repair space across all scenarios.
Exact Minimum Subpacketization for d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2) \ge4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 )
The construction above and the lower bound from Theorem 5 together yield the following exact formula.
Theorem 7. Let 3 ≤ k < d ≤ n − 1 3 \le k < d \le n-1 3 ≤ k < d ≤ n − 1 , put s = d + 1 − k s=d+1-k s = d + 1 − k , and let q q q be any prime power. If
d ( d + 2 ) ≥ 4 ( n + 1 ) , d(d+2) \ge4(n+1), d ( d + 2 ) ≥ 4 ( n + 1 ) , then
ℓ min ( n , k , d ; q ) = s Δ s ( n , d ) = s G s ( n ) . \ell_{\min}(n,k,d;q)=s\Delta_s(n,d)=sG_s(n). ℓ m i n ( n , k , d ; q ) = s Δ s ( n , d ) = s G s ( n ) .
Proof. By Theorems 5 and 6 and (11) ,
s G s ( n ) ≤ ℓ min ( n , k , d ; q ) ≤ s Δ s ( n , d ) ≤ s G s ( n ) . sG_s(n) \le\ell_{\min}(n,k,d;q) \le s\Delta_s(n,d) \le sG_s(n). s G s ( n ) ≤ ℓ m i n ( n , k , d ; q ) ≤ s Δ s ( n , d ) ≤ s G s ( n ) .
Hence equality holds throughout.
In their survey, Ramkumar et al. [23, Open Problem 20] asked for the minimum subpacketization of an RS code that attains the cut-set bound in the full-helper case d = n − 1 d=n-1 d = n − 1 . For exact linear repair in the range 3 ≤ k < n − 1 3 \le k < n-1 3 ≤ k < n − 1 , the preceding theorem resolves the corresponding case of Open Problem 20. The resulting formula is recorded below.
Corollary 2. Let d = n − 1 d=n-1 d = n − 1 and s = n − k s=n-k s = n − k , where 3 ≤ k < n − 1 3 \le k < n-1 3 ≤ k < n − 1 . Then, for every prime power q q q ,
ℓ min ( n , k , n − 1 ; q ) = s Δ s ( n , n − 1 ) = s G s ( n ) . \ell_{\min}(n,k,n-1;q)=s\Delta_s(n,n-1)=sG_s(n). ℓ m i n ( n , k , n − 1 ; q ) = s Δ s ( n , n − 1 ) = s G s ( n ) .
Proof. Here n ≥ 5 n \ge5 n ≥ 5 , and
( n − 1 ) ( n + 1 ) − 4 ( n + 1 ) = ( n + 1 ) ( n − 5 ) ≥ 0. (n-1)(n+1)-4(n+1)=(n+1)(n-5) \ge0. ( n − 1 ) ( n + 1 ) − 4 ( n + 1 ) = ( n + 1 ) ( n − 5 ) ≥ 0.
Hence the quadratic condition holds with d = n − 1 d=n-1 d = n − 1 , and Theorem 7 applies.
By Theorem 7, the minimum subpacketization equals s G s ( n ) sG_s(n) s G s ( n ) whenever d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2) \ge4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 ) . We now determine the exact threshold for the identity G s ( m ) = A s p m # G_s(m)=A_sp_m^{\#} G s ( m ) = A s p m # and derive a finite formula valid for all m m m .
We first introduce some notation. For s ≥ 3 s \ge3 s ≥ 3 , let
u s = max { p < s : p is prime } , v s = max { p a < s : p is prime , a ≥ 1 } . u_s=\max\{p<s:p\text{ is prime}\}, \qquad v_s=\max\{p^a<s:p\text{ is prime},\ a\ge1\}. u s = max { p < s : p is prime } , v s = max { p a < s : p is prime , a ≥ 1 } .
Thus u s u_s u s and v s v_s v s are, respectively, the largest prime and the largest prime power below s s s . Set u 2 = v 2 = 1 u_2=v_2=1 u 2 = v 2 = 1 and define
A s = lcm ( 1 , … , s − 1 ) , σ s = π ( u s v s ) . A_s=\operatorname{lcm}(1,\ldots,s-1), \qquad\sigma_s=\pi(u_sv_s). A s = lcm ( 1 , … , s − 1 ) , σ s = π ( u s v s ) .
For each prime p < s p<s p < s , put
a p = p ⌈ log p s ⌉ , a_p=p^{\lceil\log_p s\rceil}, a p = p ⌈ l o g p s ⌉ ,
and, for every nonempty set B B B of primes below s s s , let μ s ( B ) \mu_s(B) μ s ( B ) denote the smallest integer at least s s s whose prime-divisor set is exactly B B B . We determine the exact point at which G s ( m ) G_s(m) G s ( m ) is attained by taking the smallest prime power at least s s s for each prime below $s, and then adjoining successive primes at least s s s .
Theorem 8. For all integers s ≥ 2 s \ge2 s ≥ 2 and m ≥ 0 m \ge0 m ≥ 0 ,
G s ( m ) = A s p m # ⟺ m ≥ σ s . G_s(m)=A_sp_m^{\#} \Longleftrightarrow m \ge\sigma_s. G s ( m ) = A s p m # ⟺ m ≥ σ s . In particular, m ≥ ⌊ s 2 / 4 ⌋ m \ge\lfloor s^2/4\rfloor m ≥ ⌊ s 2 /4 ⌋ is sufficient.
Proof. For s = 2 s=2 s = 2 , the product of any m m m pairwise coprime integers at least 2 is at least p m # p_m^{\#} p m # , and equality is attained by the first m m m primes. Since A 2 = 1 A_2=1 A 2 = 1 and σ 2 = 0 \sigma_2=0 σ 2 = 0 , the assertion follows. Henceforth assume s ≥ 3 s \ge3 s ≥ 3 , and recall that
c s = π ( s − 1 ) . c_s=\pi(s-1). c s = π ( s − 1 ) .
We first record two consequences of the definitions. Bertrand’s postulate [25 ] implies 2 u s > s − 1 2u_s>s-1 2 u s > s − 1 , and hence
u s < s ≤ 2 u s ≤ u s 2 , u s ≤ v s < 2 u s . u_s<s\le2u_s\le u_s^2,\qquad u_s\le v_s<2u_s. u s < s ≤ 2 u s ≤ u s 2 , u s ≤ v s < 2 u s .
In particular, u s v s ≥ s u_sv_s \ge s u s v s ≥ s , and u s v s u_sv_s u s v s is composite. By definition, a p a_p a p is the smallest power of p p p not less than s s s ; accordingly, a p / p a_p/p a p / p is the largest power of p p p strictly below s s s . It follows that
a p p ≤ v s , a p ≤ p v s ≤ u s v s , and a u s = u s 2 . \frac{a_p}{p} \le v_s,\qquad a_p \le pv_s \le u_sv_s,\qquad\text{and}\qquad a_{u_s}=u_s^2. p a p ≤ v s , a p ≤ p v s ≤ u s v s , and a u s = u s 2 .
Since A s A_s A s is the product of the largest powers below s s s of the distinct primes p < s p<s p < s , we also have
A s p c s # = ∏ p < s a p . (25) A_sp_{c_s}^{\#}=\prod_{p<s}a_p. \tag*{(25)} A s p c s # = p < s ∏ a p . (25)
For m ≥ c s m\ge c_s m ≥ c s , the m m m integers
{ a p : p < s } ∪ { p c s + 1 , … , p m } \{a_p:p<s\}\cup\{p_{c_s+1},\ldots,p_m\} { a p : p < s } ∪ { p c s + 1 , … , p m }
are at least s s s and pairwise coprime. Their product is A s p m # A_sp_m^{\#} A s p m # by (25) , so
G s ( m ) ≤ A s p m # ( m ≥ c s ) . G_s(m)\le A_sp_m^{\#}\qquad(m\ge c_s). G s ( m ) ≤ A s p m # ( m ≥ c s ) .
Conversely, if 0 ≤ m < c s 0\le m<c_s 0 ≤ m < c s , the first m m m numbers a p 1 , … , a p m a_{p_1},\ldots,a_{p_m} a p 1 , … , a p m form an admissible family and give
G s ( m ) ≤ ∏ j = 1 m a p j = p m # ∏ j = 1 m a p j p j < p m # ∏ p < s a p p = A s p m # . G_s(m)\le\prod_{j=1}^{m}a_{p_j}=p_m^{\#}\prod_{j=1}^{m}\frac{a_{p_j}}{p_j}<p_m^{\#}\prod_{p<s}\frac{a_p}{p}=A_sp_m^{\#}. G s ( m ) ≤ j = 1 ∏ m a p j = p m # j = 1 ∏ m p j a p j < p m # p < s ∏ p a p = A s p m # .
The inequality is strict because at least one prime p < s p<s p < s is omitted and every a p / p > 1 a_p/p>1 a p / p > 1 . Thus equality in the theorem is possible only for m ≥ c s m\ge c_s m ≥ c s .
We next bound the cost of separating a nonempty set B B B of small prime divisors. We claim that
∏ p ∈ B a p ≤ μ s ( B ) ( u s v s ) ∣ B ∣ − 1 . (26) \prod_{p\in B}a_p\le\mu_s(B)(u_sv_s)^{|B|-1}. \tag*{(26)} p ∈ B ∏ a p ≤ μ s ( B ) ( u s v s ) ∣ B ∣ − 1 . (26)
When B = { p } B=\{p\} B = { p } , we have μ s ( B ) = a p \mu_s(B)=a_p μ s ( B ) = a p , so equality holds. Suppose next that B = { p , q } B=\{p,q\} B = { p , q } , where p ≠ q p\ne q p = q . Since p q ∣ μ s ( B ) pq\mid\mu_s(B) pq ∣ μ s ( B ) ,
a p a q μ s ( B ) ≤ a p a q p q . \frac{a_pa_q}{\mu_s(B)}\le\frac{a_pa_q}{pq}. μ s ( B ) a p a q ≤ pq a p a q .
If either a p / p ≤ u s a_p/p\le u_s a p / p ≤ u s or a q / q ≤ u s a_q/q\le u_s a q / q ≤ u s , the right-hand side is at most u s v s u_sv_s u s v s , as required. Otherwise, a p / p > u s ≥ p a_p/p>u_s\ge p a p / p > u s ≥ p and a q / q > u s ≥ q a_q/q>u_s\ge q a q / q > u s ≥ q . Since these quotients are powers of p p p and q q q , respectively, we obtain
p 2 ≤ a p p ≤ v s , q 2 ≤ a q q ≤ v s . p^2\le\frac{a_p}{p}\le v_s,\qquad q^2\le\frac{a_q}{q}\le v_s. p 2 ≤ p a p ≤ v s , q 2 ≤ q a q ≤ v s .
Therefore p q ≤ v s < s pq\le v_s<s pq ≤ v s < s . As μ s ( B ) \mu_s(B) μ s ( B ) is a multiple of p q pq pq and is at least s s s , necessarily μ s ( B ) ≥ 2 p q \mu_s(B)\ge2pq μ s ( B ) ≥ 2 pq . Consequently,
a p a q μ s ( B ) ≤ 1 2 a p p a q q ≤ v s 2 2 < u s v s , \frac{a_pa_q}{\mu_s(B)}\le\frac{1}{2}\frac{a_p}{p}\frac{a_q}{q}\le\frac{v_s^2}{2}<u_sv_s, μ s ( B ) a p a q ≤ 2 1 p a p q a q ≤ 2 v s 2 < u s v s ,
where the last inequality follows from v s < 2 u s v_s<2u_s v s < 2 u s . Finally, if ∣ B ∣ ≥ 3 |B|\ge3 ∣ B ∣ ≥ 3 , then μ s ( B ) ≥ ∏ p ∈ B p \mu_s(B)\ge\prod_{p\in B}p μ s ( B ) ≥ ∏ p ∈ B p , so
∏ p ∈ B a p μ s ( B ) ≤ ∏ p ∈ B a p p ≤ v s ∣ B ∣ ≤ ( u s v s ) ∣ B ∣ − 1 . \frac{\prod_{p\in B}a_p}{\mu_s(B)}
\le\prod_{p\in B}\frac{a_p}{p}
\le v_s^{|B|}
\le(u_sv_s)^{|B|-1}. μ s ( B ) ∏ p ∈ B a p ≤ p ∈ B ∏ p a p ≤ v s ∣ B ∣ ≤ ( u s v s ) ∣ B ∣ − 1 .
For the last inequality we used v s < 2 u s ≤ u s 2 ≤ u s ∣ B ∣ − 1 v_s<2u_s\le u_s^2\le u_s^{|B|-1} v s < 2 u s ≤ u s 2 ≤ u s ∣ B ∣ − 1 . This proves (26) for every nonempty B B B .
We first show that the closed form holds for m ≥ σ s = π ( u s v s ) m\ge\sigma_s=\pi(u_sv_s) m ≥ σ s = π ( u s v s ) . Since u s v s ≥ s u_sv_s\ge s u s v s ≥ s , this implies m ≥ c s m\ge c_s m ≥ c s . Choose pairwise coprime integers x 1 , … , x m ≥ s x_1,\ldots,x_m\ge s x 1 , … , x m ≥ s whose product is G s ( m ) G_s(m) G s ( m ) . If some x j x_j x j has a prime divisor p ≥ s p\ge s p ≥ s , then x j = p x_j=p x j = p : otherwise replacing x j x_j x j by p p p would preserve both admissibility conditions and strictly reduce the product. Similarly, if every prime divisor of x j x_j x j is below s s s , then x j x_j x j must be the smallest integer at least s s s with exactly the same set of prime divisors. Otherwise, replacing x j x_j x j by that integer would preserve admissibility and strictly reduce the product. Thus, after reordering, exactly r r r of the x j x_j x j have the form μ s ( B 1 ) , … , μ s ( B r ) \mu_s(B_1),\ldots,\mu_s(B_r) μ s ( B 1 ) , … , μ s ( B r ) , with nonempty pairwise disjoint sets B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r of primes below s s s ; the remaining m − r m-r m − r integers are distinct primes at least s s s . Necessarily 0 ≤ r ≤ c s 0\le r\le c_s 0 ≤ r ≤ c s . Apply (26) to each B j B_j B j and use a p ≤ u s v s a_p\le u_sv_s a p ≤ u s v s for every prime p < s p<s p < s outside their union. By (25) ,
A s p c s # = ∏ p < s a p ≤ ( ∏ j = 1 r μ s ( B j ) ) ( u s v s ) ∑ j = 1 r ( ∣ B j ∣ − 1 ) + c s − ∑ j ∣ B j ∣ = ( u s v s ) c s − r ∏ j = 1 r μ s ( B j ) . \begin{aligned}
A_sp_{c_s}^{\#}=\prod_{p<s}a_p\le\left(\prod_{j=1}^{r}\mu_s(B_j)\right)(u_sv_s)^{\sum_{j=1}^{r}(|B_j|-1)+c_s-\sum_j|B_j|} \\
&=(u_sv_s)^{c_s-r}\prod_{j=1}^{r}\mu_s(B_j).
\end{aligned} A s p c s # = p < s ∏ a p ≤ ( j = 1 ∏ r μ s ( B j ) ) ( u s v s ) ∑ j = 1 r ( ∣ B j ∣ − 1 ) + c s − ∑ j ∣ B j ∣ = ( u s v s ) c s − r j = 1 ∏ r μ s ( B j ) .
The same estimate holds for r = 0 r=0 r = 0 , with empty products interpreted as 1.
Since the other m − r m-r m − r factors are distinct primes at least s s s , their product is bounded below by the product of the first m − r m-r m − r primes at least s s s , namely
∏ j = c s + 1 c s + m − r p j = p m + c s − r # p c s # . \prod_{j=c_s+1}^{c_s+m-r}p_j=\frac{p_{m+c_s-r}^{\#}}{p_{c_s}^{\#}}. j = c s + 1 ∏ c s + m − r p j = p c s # p m + c s − r # .
Multiplying the two estimates yields
G s ( m ) ≥ A s p c s # ( u s v s ) c s − r p m + c s − r # p c s # = A s p m # ∏ j = 1 c s − r p m + j u s v s . (27) G_s(m)\ge\frac{A_sp_{c_s}^{\#}}{(u_sv_s)^{c_s-r}}\frac{p_{m+c_s-r}^{\#}}{p_{c_s}^{\#}}=A_sp_m^{\#}\prod_{j=1}^{c_s-r}\frac{p_{m+j}}{u_sv_s}. \tag*{(27)} G s ( m ) ≥ ( u s v s ) c s − r A s p c s # p c s # p m + c s − r # = A s p m # j = 1 ∏ c s − r u s v s p m + j . (27)
Because u s v s u_sv_s u s v s is composite and m ≥ π ( u s v s ) m\ge\pi(u_sv_s) m ≥ π ( u s v s ) , we have p m + 1 > u s v s p_{m+1}>u_sv_s p m + 1 > u s v s . Every factor in the final product is therefore at least 1 (and the product is 1 if r = c s r=c_s r = c s ). Hence G s ( m ) ≥ A s p m # G_s(m)\ge A_sp_m^{\#} G s ( m ) ≥ A s p m # , and equality follows from the explicit construction above.
Conversely, suppose G s ( m ) = A s p m # G_s(m)=A_sp_m^{\#} G s ( m ) = A s p m # . The argument before (26) shows that m ≥ c s m\ge c_s m ≥ c s . Assume, for a contradiction, that m < σ s m<\sigma_s m < σ s . Since u s v s u_sv_s u s v s is composite, m < π ( u s v s ) m<\pi(u_sv_s) m < π ( u s v s ) implies p m + 1 < u s v s p_{m+1}<u_sv_s p m + 1 < u s v s ; and m ≥ c s m\ge c_s m ≥ c s implies p m + 1 ≥ s p_{m+1}\ge s p m + 1 ≥ s . Thus
s ≤ p m + 1 < u s v s . s\le p_{m+1}<u_sv_s. s ≤ p m + 1 < u s v s .
Starting from the admissible family
{ a p : p < s } ∪ { p c s + 1 , … , p m } , \{a_p:p<s\}\cup\{p_{c_s+1},\ldots,p_m\}, { a p : p < s } ∪ { p c s + 1 , … , p m } ,
whose product is A s p m # A_sp_m^{\#} A s p m # , we construct a strictly smaller admissible family of the same size.
If v s = u s v_s=u_s v s = u s , replace the factor a u s = u s 2 = u s v s a_{u_s}=u_s^2=u_sv_s a u s = u s 2 = u s v s by p m + 1 p_{m+1} p m + 1 . The new factor is at least s s s by the preceding inequality. It is coprime to every remaining factor, since p m + 1 p_{m+1} p m + 1 does not occur in the original family. The product decreases by the factor p m + 1 / ( u s v s ) < 1 p_{m+1}/(u_sv_s)<1 p m + 1 / ( u s v s ) < 1 .
If v s > u s v_s>u_s v s > u s , let p < s p<s p < s be the prime for which v s v_s v s is a power of p p p . Since v s v_s v s is the largest prime power below s s s , we have a p / p = v s a_p/p=v_s a p / p = v s . Also p ≠ u s p\ne u_s p = u s , as a u s / u s = u s < v s a_{u_s}/u_s=u_s<v_s a u s / u s = u s < v s . Replace the two factors a p = p v s a_p=pv_s a p = p v s and a u s = u s 2 a_{u_s}=u_s^2 a u s = u s 2 by p u s pu_s p u s and p m + 1 p_{m+1} p m + 1 . Both new factors are at least s s s , since
p u s ≥ 2 u s ≥ s , p m + 1 ≥ s . pu_s\ge2u_s\ge s,\qquad p_{m+1}\ge s. p u s ≥ 2 u s ≥ s , p m + 1 ≥ s .
They are relatively prime to one another and to the unchanged factors: the primes p p p and u s u_s u s occur only in the two removed factors, and p m + 1 > u s p_{m+1}>u_s p m + 1 > u s is a new prime. The ratio of the new product to the original product is
p u s p m + 1 ( p v s ) u s 2 = p m + 1 u s v s < 1. \frac{pu_sp_{m+1}}{(pv_s)u_s^2}=\frac{p_{m+1}}{u_sv_s}<1. ( p v s ) u s 2 p u s p m + 1 = u s v s p m + 1 < 1.
Either replacement contradicts the optimality of A s p m # A_sp_m^{\#} A s p m # . Hence m ≥ σ s m\ge\sigma_s m ≥ σ s .
It remains to verify the stated sufficient condition m ≥ ⌊ s 2 / 4 ⌋ m\ge\lfloor s^2/4\rfloor m ≥ ⌊ s 2 /4 ⌋ . The case s = 2 s=2 s = 2 is immediate, and for 3 ≤ s ≤ 10 3\le s\le10 3 ≤ s ≤ 10 we have σ s ≤ ⌊ s 2 / 4 ⌋ \sigma_s\le\lfloor s^2/4\rfloor σ s ≤ ⌊ s 2 /4 ⌋ by the values listed below. For s ≥ 11 s\ge11 s ≥ 11 , the prime bound p j > j log j p_j>j\log j p j > j log j for j ≥ 2 j\ge2 j ≥ 2 [30 (3.12)] gives
p ⌊ s 2 / 4 ⌋ + 1 > s 2 4 log s 2 4 > ( s − 1 ) 2 ≥ u s v s . p_{\lfloor s^2/4\rfloor+1}>\frac{s^2}{4}\log\frac{s^2}{4}>(s-1)^2\ge u_sv_s. p ⌊ s 2 /4 ⌋ + 1 > 4 s 2 log 4 s 2 > ( s − 1 ) 2 ≥ u s v s .
The middle inequality holds for s > 11 s>11 s > 11 : the difference between its two sides is positive at s = 11 s=11 s = 11 and has derivative s ( log ( s / 2 ) − 3 / 2 ) + 2 > 0 s(\log(s/2)-3/2)+2>0 s ( log ( s /2 ) − 3/2 ) + 2 > 0 for s ≥ 11 s\ge11 s ≥ 11 . Thus σ s = π ( u s v s ) ≤ ⌊ s 2 / 4 ⌋ \sigma_s=\pi(u_sv_s)\le\lfloor s^2/4\rfloor σ s = π ( u s v s ) ≤ ⌊ s 2 /4 ⌋ , as required. ∎
The threshold can be read off explicitly for small s s s :
For instance, when s = 9 s=9 s = 9 , the largest prime below s s s is 7 and the largest prime power below s s s is 8, so the threshold is determined by 7 ⋅ 8 = 56 7\cdot8=56 7 ⋅ 8 = 56 . In the family used above, the factors corresponding to 2 and 7 are 16 and 49. Replacing them by 14 and the next unused prime decreases the product exactly while that prime is below 56, which illustrates why the product u s v s u_sv_s u s v s appears in the exact threshold.
Combining the threshold with Theorem 7 yields the following closed form whenever d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2)\geq4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 ) .
Corollary 3. Let q q q be a prime power, 3 ≤ k < d ≤ n − 1 3\leq k<d\leq n-1 3 ≤ k < d ≤ n − 1 , and s = d + 1 − k s=d+1-k s = d + 1 − k . Assume d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2)\geq4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 ) . Then
ℓ min ( n , k , d ; q ) = s A s p n # ⟺ n ≥ σ s . \ell_{\min}(n,k,d;q)=sA_sp_n^\# \iff n\geq\sigma_s. ℓ m i n ( n , k , d ; q ) = s A s p n # ⟺ n ≥ σ s . In particular, for n ≥ 5 n\geq5 n ≥ 5 ,
ℓ min ( n , n − 2 , n − 1 ; q ) = 2 p n # . \ell_{\min}(n,n-2,n-1;q)=2p_n^\#. ℓ m i n ( n , n − 2 , n − 1 ; q ) = 2 p n # .
For fixed s s s , the closed form also determines the asymptotic behavior of G s ( m ) G_s(m) G s ( m ) directly.
Corollary 4. For every fixed integer s ≥ 2 s\geq2 s ≥ 2 , as m → ∞ m\to\infty m → ∞ ,
log G s ( m ) = ( 1 + o ( 1 ) ) m log m . \log G_s(m)=(1+o(1))m\log m. log G s ( m ) = ( 1 + o ( 1 )) m log m .
Proof. For m ≥ σ s m\geq\sigma_s m ≥ σ s , use Theorem 8 and log p m # ∼ m log m \log p_m^\#\sim m\log m log p m # ∼ m log m from the prime number theorem [25 ] .
The preceding theorem provides a closed form for G s ( m ) G_s(m) G s ( m ) when m ≥ σ s m\geq\sigma_s m ≥ σ s . We now give a finite formula valid also below this threshold. For each nonempty set B B B of primes below s s s , the integer μ s ( B ) \mu_s(B) μ s ( B ) can be computed by
μ s ( B ) = min { ∏ p ∈ B p e p : 1 ≤ e p ≤ ⌈ log p s ⌉ , ∏ p ∈ B p e p ≥ s } . \mu_s(B)=\min\left\{\prod_{p\in B}p^{e_p}:1\leq e_p\leq\lceil\log_p s\rceil,\ \prod_{p\in B}p^{e_p}\geq s\right\}. μ s ( B ) = min ⎩ ⎨ ⎧ p ∈ B ∏ p e p : 1 ≤ e p ≤ ⌈ log p s ⌉ , p ∈ B ∏ p e p ≥ s ⎭ ⎬ ⎫ .
where the exponents are integers. Indeed, an exponent exceeding ⌈ log p s ⌉ \lceil\log_p s\rceil ⌈ log p s ⌉ can be reduced to this value without changing the set of prime divisors or making the product less than s s s .
Theorem 9. Let s ≥ 2 s\geq2 s ≥ 2 and m ≥ 0 m\geq0 m ≥ 0 . For each integer 0 ≤ r ≤ min { m , c s } 0\leq r\leq\min\{m,c_s\} 0 ≤ r ≤ min { m , c s } , let B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r range over pairwise disjoint nonempty subsets of { p 1 , … , p c s } \{p_1,\ldots,p_{c_s}\} { p 1 , … , p c s } . Then
G s ( m ) = min 0 ≤ r ≤ min { m , c s } B 1 , … , B r ( ∏ j = 1 r μ s ( B j ) ) p m + c s − r # p c s # . (28) G_s(m)=\min_{\substack{0\leq r\leq\min\{m,c_s\}\\ B_1,\ldots,B_r}}\left(\prod_{j=1}^{r}\mu_s(B_j)\right)\frac{p_{m+c_s-r}^\#}{p_{c_s}^\#}. \tag*{(28)} G s ( m ) = 0 ≤ r ≤ m i n { m , c s } B 1 , … , B r min ( j = 1 ∏ r μ s ( B j ) ) p c s # p m + c s − r # . (28) For r = 0 r=0 r = 0 , the tuple is empty and its product is 1. If m ≥ σ s m\geq\sigma_s m ≥ σ s , a minimizing choice is r = c s r=c_s r = c s and B j = { p j } B_j=\{p_j\} B j = { p j } for 1 ≤ j ≤ c s 1\leq j\leq c_s 1 ≤ j ≤ c s .
Proof. Choose pairwise coprime integers x 1 , … , x m ≥ s x_1,\ldots,x_m\geq s x 1 , … , x m ≥ s whose product is G s ( m ) G_s(m) G s ( m ) . As in the proof of Theorem 8, any x j x_j x j with a prime divisor at least s s s must equal that prime: otherwise, replacing x j x_j x j by the prime would decrease the product and preserve admissibility. Likewise, if all prime divisors of x j x_j x j are below s s s , minimality forces x j = μ s ( B ) x_j=\mu_s(B) x j = μ s ( B ) , where B B B is its set of prime divisors.
After reordering, suppose the latter type occurs r r r times, with prime-divisor sets B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r . These sets are nonempty, pairwise disjoint, and contained in { p 1 , … , p c s } \{p_1,\ldots,p_{c_s}\} { p 1 , … , p c s } ; in particular, 0 ≤ r ≤ min { m , c s } 0\leq r\leq\min\{m,c_s\} 0 ≤ r ≤ min { m , c s } . The remaining m − r m-r m − r factors are distinct primes at least s s s . Their product is at least the product of the first m − r m-r m − r primes at least s s s , namely
∏ j = c s + 1 c s + m − r p j = p m + c s − r # p c s # . \prod_{j=c_s+1}^{c_s+m-r}p_j=\frac{p_{m+c_s-r}^\#}{p_{c_s}^\#}. j = c s + 1 ∏ c s + m − r p j = p c s # p m + c s − r # .
Consequently,
G s ( m ) ≥ ( ∏ j = 1 r μ s ( B j ) ) p m + c s − r # p c s # , G_s(m) \ge\left(\prod_{j=1}^{r}\mu_s(B_j)\right)\frac{p_{m+c_s-r}^{\#}}{p_{c_s}^{\#}}, G s ( m ) ≥ ( j = 1 ∏ r μ s ( B j ) ) p c s # p m + c s − r # ,
which is at least the minimum on the right-hand side of (28) .
Conversely, fix any r r r and B 1 , … , B r B_1,\ldots,B_r B 1 , … , B r allowed in the theorem. The m m m integers
μ s ( B 1 ) , … , μ s ( B r ) , p c s + 1 , … , p c s + m − r \mu_s(B_1),\ldots,\mu_s(B_r),\ p_{c_s+1},\ldots,p_{c_s+m-r} μ s ( B 1 ) , … , μ s ( B r ) , p c s + 1 , … , p c s + m − r
are all at least s s s and are pairwise coprime: the B j B_j B j are disjoint and contain only primes below s s s , while the remaining factors are distinct primes at least s s s . Their product equals the corresponding expression in (28) , proving the reverse inequality.
Finally, let m ≥ σ s m\ge\sigma_s m ≥ σ s and choose r = c s r=c_s r = c s and B j = { p j } B_j=\{p_j\} B j = { p j } . Since μ s ( { p j } ) = a p j \mu_s(\{p_j\})=a_{p_j} μ s ({ p j }) = a p j , (25) gives
( ∏ j = 1 c s μ s ( { p j } ) ) p m # p c s # = A s p m # = G s ( m ) , \left(\prod_{j=1}^{c_s}\mu_s(\{p_j\})\right)\frac{p_m^{\#}}{p_{c_s}^{\#}}=A_sp_m^{\#}=G_s(m), ( j = 1 ∏ c s μ s ({ p j }) ) p c s # p m # = A s p m # = G s ( m ) ,
where the last equality follows from Theorem 8. Hence this choice attains the minimum.
We illustrate the formula for small s s s , including the exact threshold values. For s = 3 s=3 s = 3 , μ 3 ( { 2 } ) = 4 \mu_3(\{2\})=4 μ 3 ({ 2 }) = 4 , and hence
G 3 ( 1 ) = 3 , G 3 ( 2 ) = 12 = 2 p 2 # . G_3(1)=3,\qquad G_3(2)=12=2p_2^{\#}. G 3 ( 1 ) = 3 , G 3 ( 2 ) = 12 = 2 p 2 # .
For s = 4 s=4 s = 4 , the possible nonempty sets of small primes have
μ 4 ( { 2 } ) = 4 , μ 4 ( { 3 } ) = 9 , μ 4 ( { 2 , 3 } ) = 6 , \mu_4(\{2\})=4,\qquad\mu_4(\{3\})=9,\qquad\mu_4(\{2,3\})=6, μ 4 ({ 2 }) = 4 , μ 4 ({ 3 }) = 9 , μ 4 ({ 2 , 3 }) = 6 ,
which yields
G 4 ( 1 ) = 4 , G 4 ( 2 ) = 20 , G 4 ( 3 ) = 140 , G 4 ( 4 ) = 1260. G_4(1)=4,\qquad G_4(2)=20,\qquad G_4(3)=140,\qquad G_4(4)=1260. G 4 ( 1 ) = 4 , G 4 ( 2 ) = 20 , G 4 ( 3 ) = 140 , G 4 ( 4 ) = 1260.
For s = 5 s=5 s = 5 , the corresponding values are
μ 5 ( { 2 } ) = 8 , μ 5 ( { 3 } ) = 9 , μ 5 ( { 2 , 3 } ) = 6 , \mu_5(\{2\})=8,\qquad\mu_5(\{3\})=9,\qquad\mu_5(\{2,3\})=6, μ 5 ({ 2 }) = 8 , μ 5 ({ 3 }) = 9 , μ 5 ({ 2 , 3 }) = 6 ,
and thus
G 5 ( 1 ) = 5 , G 5 ( 2 ) = 30 , G 5 ( 3 ) = 210 , G_5(1)=5,\qquad G_5(2)=30,\qquad G_5(3)=210, G 5 ( 1 ) = 5 , G 5 ( 2 ) = 30 , G 5 ( 3 ) = 210 ,
G 5 ( 4 ) = 2310 , G 5 ( 5 ) = 27720. G_5(4)=2310,\qquad G_5(5)=27720. G 5 ( 4 ) = 2310 , G 5 ( 5 ) = 27720.
In particular, G 5 ( 2 ) = 6 ⋅ 5 < 5 ⋅ 7 G_5(2)=6\cdot5<5\cdot7 G 5 ( 2 ) = 6 ⋅ 5 < 5 ⋅ 7 : combining the small primes 2 and 3 in the factor 6 is better than using only primes at least 5. The values at m = σ 3 = 2 m=\sigma_3=2 m = σ 3 = 2 , m = σ 4 = 4 m=\sigma_4=4 m = σ 4 = 4 , and m = σ 5 = 5 m=\sigma_5=5 m = σ 5 = 5 agree with the closed form in Theorem 8.
Asymptotics for Fixed k and d
Fix a prime power q q q and integers 3 ≤ k < d 3\le k<d 3 ≤ k < d , put s = d + 1 − k s=d+1-k s = d + 1 − k , and let n → ∞ n\to\infty n → ∞ with k k k and d d d fixed. We determine the order of log ℓ min ( n , k , d ; q ) \log\ell_{\min}(n,k,d;q) log ℓ m i n ( n , k , d ; q ) . The lower bound comes from counting distinct subset least common multiples, while the upper bound uses cover-free families. All logarithms in this section are natural.
Let τ ( M ) \tau(M) τ ( M ) denote the number of positive divisors of a positive integer M M M . For x ≥ 1 x\ge1 x ≥ 1 , define
D ( x ) = min { M ∈ Z : M ≥ 1 , τ ( M ) ≥ x } . (29) \mathcal{D}(x)=\min\{M\in\mathbb{Z}:M\ge1,\ \tau(M)\ge x\}. \tag*{(29)} D ( x ) = min { M ∈ Z : M ≥ 1 , τ ( M ) ≥ x } . (29)
Lemma 11. Let ( a 1 , … , a N ) (a_1,\ldots,a_N) ( a 1 , … , a N ) be a feasible ( N , t , s ) (N,t,s) ( N , t , s ) -tuple, where s ≥ 2 s\ge2 s ≥ 2 and 1 ≤ t < N 1\le t<N 1 ≤ t < N , and put M = lcm ( a 1 , … , a N ) M=\operatorname{lcm}(a_1,\ldots,a_N) M = lcm ( a 1 , … , a N ) . Then
τ ( M ) ≥ ∑ r = 0 t ( N r ) . \tau(M)\ge\sum_{r=0}^{t}\binom{N}{r}. τ ( M ) ≥ r = 0 ∑ t ( r N ) . Consequently,
Δ s ( N , t ) ≥ D ( ∑ r = 0 t ( N r ) ) . \Delta_s(N,t)\ge\mathcal{D}\left(\sum_{r=0}^{t}\binom{N}{r}\right). Δ s ( N , t ) ≥ D ( r = 0 ∑ t ( r N ) ) .
Proof. For A ⊆ [ N ] A \subseteq[N] A ⊆ [ N ] , write L A = lcm ( a i : i ∈ A ) L_A = \operatorname{lcm}(a_i : i \in A) L A = lcm ( a i : i ∈ A ) , with L ∅ = 1 L_{\varnothing} = 1 L ∅ = 1 . We claim that for ∣ A ∣ , ∣ B ∣ ≤ t |A|, |B| \le t ∣ A ∣ , ∣ B ∣ ≤ t ,
L A ∣ L B ⟹ A ⊆ B . L_A \mid L_B \quad\Longrightarrow\quad A \subseteq B. L A ∣ L B ⟹ A ⊆ B .
Otherwise, take i ∈ A ∖ B i \in A \setminus B i ∈ A ∖ B . Since ∣ B ∣ ≤ t < N |B| \le t < N ∣ B ∣ ≤ t < N , we may extend B B B to a t t t -subset J ⊆ [ N ] ∖ { i } J \subseteq[N]\setminus\{i\} J ⊆ [ N ] ∖ { i } . Then a i ∣ L A ∣ L B ∣ L J a_i \mid L_A \mid L_B \mid L_J a i ∣ L A ∣ L B ∣ L J , and hence
L J ∪ { i } L J = 1 < s , \frac{L_{J\cup\{i\}}}{L_J}=1<s, L J L J ∪ { i } = 1 < s ,
contrary to feasibility. In particular, L A = L B L_A = L_B L A = L B implies A = B A = B A = B whenever ∣ A ∣ , ∣ B ∣ ≤ t |A|, |B| \le t ∣ A ∣ , ∣ B ∣ ≤ t . These ∑ r = 0 t ( N r ) \sum_{r=0}^{t}\binom{N}{r} ∑ r = 0 t ( r N ) distinct values are all divisors of M M M , which proves the first assertion. The second follows from (29) and the definition of Δ s ( N , t ) \Delta_s(N,t) Δ s ( N , t ) .
To use this counting bound, we need the asymptotic growth of D ( x ) \mathcal{D}(x) D ( x ) . The following lemma is a direct consequence of Wigert’s theorem on the maximal order of the divisor function.
Lemma 12. As x → ∞ x \to\infty x → ∞ ,
log D ( x ) = ( 1 log 2 + o ( 1 ) ) log x log log x . (30) \log\mathcal{D}(x)=\left(\frac{1}{\log2}+o(1)\right)\log x\log\log x. \tag*{(30)} log D ( x ) = ( log 2 1 + o ( 1 ) ) log x log log x . (30)
Proof. For Y ≥ 1 Y \ge1 Y ≥ 1 , let
H ( Y ) = max 1 ≤ M ≤ Y log τ ( M ) . H(Y)=\max_{1\le M\le Y}\log\tau(M). H ( Y ) = 1 ≤ M ≤ Y max log τ ( M ) .
Wigert’s theorem [26 ] , in the formulation given in [27 ] , states that
H ( Y ) = ( log 2 + o ( 1 ) ) log Y log log Y ( Y → ∞ ) . H(Y)=(\log2+o(1))\frac{\log Y}{\log\log Y}\qquad(Y\to\infty). H ( Y ) = ( log 2 + o ( 1 )) log log Y log Y ( Y → ∞ ) .
For x ≥ 1 x \ge1 x ≥ 1 and Y ≥ 1 Y \ge1 Y ≥ 1 , the definitions yield the equivalence
H ( Y ) ≥ log x ⟺ D ( x ) ≤ Y . H(Y)\ge\log x\quad\Longleftrightarrow\quad\mathcal{D}(x)\le Y. H ( Y ) ≥ log x ⟺ D ( x ) ≤ Y .
Fix ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and, for x x x sufficiently large, set
Y ± = exp ( 1 ± ε log 2 log x log log x ) . Y_{\pm}=\exp\left(\frac{1\pm\varepsilon}{\log2}\log x\log\log x\right). Y ± = exp ( log 2 1 ± ε log x log log x ) .
Since
log log Y ± = log log x + log log log x + O ε ( 1 ) = ( 1 + o ( 1 ) ) log log x , \log\log Y_{\pm}=\log\log x+\log\log\log x+O_{\varepsilon}(1)=(1+o(1))\log\log x, log log Y ± = log log x + log log log x + O ε ( 1 ) = ( 1 + o ( 1 )) log log x ,
Wigert’s theorem yields
H ( Y ± ) = ( 1 ± ε + o ( 1 ) ) log x . H(Y_{\pm})=(1\pm\varepsilon+o(1))\log x. H ( Y ± ) = ( 1 ± ε + o ( 1 )) log x .
Thus, for all sufficiently large x x x ,
H ( Y − ) < log x < H ( Y + ) , H(Y_{-})<\log x<H(Y_{+}), H ( Y − ) < log x < H ( Y + ) ,
and the preceding equivalence gives
Y − < D ( x ) ≤ Y + . Y_{-}<\mathcal{D}(x)\le Y_{+}. Y − < D ( x ) ≤ Y + .
Taking logarithms and then letting ε → 0 \varepsilon\to0 ε → 0 proves (30) .
For the upper bound, recall that a family A = { A 1 , … , A N } ⊆ 2 [ m ] \mathcal{A}=\{A_1,\ldots,A_N\}\subseteq2^{[m]} A = { A 1 , … , A N } ⊆ 2 [ m ] is t t t -cover-free if
A i ⊈ ⋃ j ∈ J A j A_i\not\subseteq\bigcup_{j\in J}A_j A i ⊆ j ∈ J ⋃ A j
for every i ∈ [ N ] i\in[N] i ∈ [ N ] and every t t t -subset J ⊆ [ N ] ∖ { i } J\subseteq[N]\setminus\{i\} J ⊆ [ N ] ∖ { i } . Let m c f f ( N , t ) m_{\mathrm{cff}}(N,t) m cff ( N , t ) be the minimum possible size m m m of the ground set.
Lemma 13. For integers s ≥ 2 s\ge2 s ≥ 2 and 1 ≤ t < N 1\le t<N 1 ≤ t < N ,
Δ s ( N , t ) ≤ G s ( m c f f ( N , t ) ) . (31) \Delta_s(N,t)\le G_s(m_{\mathrm{cff}}(N,t)). \tag*{(31)} Δ s ( N , t ) ≤ G s ( m cff ( N , t )) . (31)
Consequently, for every prime power q q q and $3 \le k < d \le n - 1$, with s = d + 1 − k s = d + 1 - k s = d + 1 − k ,
ℓ min ( n , k , d ; q ) ≤ s G s ( m cff ( n , d ) ) . (32) \ell_{\min}(n,k,d;q) \le sG_s(m_{\operatorname{cff}}(n,d)). \tag*{(32)} ℓ m i n ( n , k , d ; q ) ≤ s G s ( m cff ( n , d )) . (32)
Proof. Choose a t t t -cover-free family A = { A 1 , … , A N } \mathcal{A} = \{A_1,\ldots,A_N\} A = { A 1 , … , A N } on [ m ] [m] [ m ] and pairwise coprime integers g 1 , … , g m ≥ s g_1,\ldots,g_m \ge s g 1 , … , g m ≥ s such that ∏ r = 1 m g r = G s ( m ) \prod_{r=1}^{m} g_r = G_s(m) ∏ r = 1 m g r = G s ( m ) . Set
a i = ∏ r ∈ A i g r , i ∈ [ N ] . a_i = \prod_{r \in A_i} g_r,\qquad i \in[N]. a i = r ∈ A i ∏ g r , i ∈ [ N ] .
For any i ∉ J i \notin J i ∈ / J with ∣ J ∣ = t |J| = t ∣ J ∣ = t , pairwise coprimality implies
lcm ( a j : j ∈ J ∪ { i } ) lcm ( a j : j ∈ J ) = ∏ r ∈ A i ∖ ⋃ j ∈ J A j g r ≥ s , \frac{\operatorname{lcm}(a_j : j \in J \cup\{i\})}{\operatorname{lcm}(a_j : j \in J)}
= \prod_{r \in A_i \setminus\bigcup_{j \in J} A_j} g_r \ge s, lcm ( a j : j ∈ J ) lcm ( a j : j ∈ J ∪ { i }) = r ∈ A i ∖ ⋃ j ∈ J A j ∏ g r ≥ s ,
since the set in the last product is nonempty by the cover-free property. Thus ( a 1 , … , a N ) (a_1,\ldots,a_N) ( a 1 , … , a N ) is feasible. Moreover,
lcm ( a 1 , … , a N ) = ∏ r ∈ ⋃ i = 1 N A i g r ≤ G s ( m ) . \operatorname{lcm}(a_1,\ldots,a_N) = \prod_{r \in\bigcup_{i=1}^{N} A_i} g_r \le G_s(m). lcm ( a 1 , … , a N ) = r ∈ ⋃ i = 1 N A i ∏ g r ≤ G s ( m ) .
Taking m = m cff ( N , t ) m = m_{\operatorname{cff}}(N,t) m = m cff ( N , t ) proves (31) . The bound (32) follows from Theorem 6.
Cover-free families are the set-system counterpart of disjunct matrices in nonadaptive group testing and are closely related to superimposed codes [28 ] . Porat and Rothschild [29 ] gave explicit t t t -disjunct constructions with O ( t 2 log N ) O(t^2 \log N) O ( t 2 log N ) rows. In particular, for fixed t t t ,
m cff ( N , t ) = O t ( log N ) . (33) m_{\operatorname{cff}}(N,t) = O_t(\log N). \tag*{(33)} m cff ( N , t ) = O t ( log N ) . (33)
Theorem 10. Fix a prime power q q q and integers 3 ≤ k < d 3 \le k < d 3 ≤ k < d . Put s = d + 1 − k s = d + 1 - k s = d + 1 − k and let n → ∞ n \to\infty n → ∞ . There is a constant C d > 0 C_d > 0 C d > 0 depending only on d d d such that
( d − 3 log 2 + o ( 1 ) ) log n log log n ≤ log ℓ min ( n , k , d ; q ) ≤ ( C d + o ( 1 ) ) log n log log n . (34) \left(\frac{d-3}{\log2} + o(1)\right)\log n\log\log n \le\log\ell_{\min}(n,k,d;q) \le(C_d + o(1))\log n\log\log n. \tag*{(34)} ( log 2 d − 3 + o ( 1 ) ) log n log log n ≤ log ℓ m i n ( n , k , d ; q ) ≤ ( C d + o ( 1 )) log n log log n . (34) In particular,
log ℓ min ( n , k , d ; q ) = Θ k , d ( log n log log n ) . \log\ell_{\min}(n,k,d;q) = \Theta_{k,d}(\log n\log\log n). log ℓ m i n ( n , k , d ; q ) = Θ k , d ( log n log log n ) . Proof. For the lower bound, consider any RS code satisfying the repair requirement. Fix three distinct anchors a , b , c ∈ Ω a,b,c \in\Omega a , b , c ∈ Ω , write the remaining evaluation points as ω 1 , … , ω n − 3 \omega_1,\ldots,\omega_{n-3} ω 1 , … , ω n − 3 , and let ϕ \phi ϕ be the projective normalization from Lemma 3. Put
x i = ϕ ( ω i ) , e i = [ F ( x i ) : F ] , t = d − 3. x_i = \phi(\omega_i),\qquad e_i = [F(x_i):F],\qquad t = d - 3. x i = ϕ ( ω i ) , e i = [ F ( x i ) : F ] , t = d − 3. For any i ∈ [ n − 3 ] i \in[n-3] i ∈ [ n − 3 ] and any t t t -subset J ⊆ [ n − 3 ] ∖ { i } J \subseteq[n-3] \setminus\{i\} J ⊆ [ n − 3 ] ∖ { i } , choose the helper set
H = { a , b , c } ∪ { ω j : j ∈ J } . H = \{a,b,c\} \cup\{\omega_j : j \in J\}. H = { a , b , c } ∪ { ω j : j ∈ J } . By Lemma 3 and the finite-field degree formula,
R F ( H ) = F ( x j : j ∈ J ) , R F ( H ∪ { ω i } ) = F ( x i , x j : j ∈ J ) . \mathcal{R}_F(H) = F(x_j : j \in J),\qquad\mathcal{R}_F(H \cup\{\omega_i\}) = F(x_i,x_j : j \in J). R F ( H ) = F ( x j : j ∈ J ) , R F ( H ∪ { ω i }) = F ( x i , x j : j ∈ J ) . Hence Proposition 3 gives
lcm ( e j : j ∈ J ∪ { i } ) lcm ( e j : j ∈ J ) = [ R F ( H ∪ { ω i } ) : R F ( H ) ] ≥ s . \frac{\operatorname{lcm}(e_j : j \in J \cup\{i\})}{\operatorname{lcm}(e_j : j \in J)}
= [\mathcal{R}_F(H \cup\{\omega_i\}) : \mathcal{R}_F(H)] \ge s. lcm ( e j : j ∈ J ) lcm ( e j : j ∈ J ∪ { i }) = [ R F ( H ∪ { ω i }) : R F ( H )] ≥ s . Thus ( e 1 , … , e n − 3 ) (e_1,\ldots,e_{n-3}) ( e 1 , … , e n − 3 ) is a feasible ( n − 3 , d − 3 , s ) (n-3,d-3,s) ( n − 3 , d − 3 , s ) -tuple. The three-anchor identity also gives
M : = lcm ( e 1 , … , e n − 3 ) = [ R F ( Ω ) : F ] ∣ ℓ s , M := \operatorname{lcm}(e_1,\ldots,e_{n-3}) = [\mathcal{R}_F(\Omega):F] \mid\frac{\ell}{s}, M := lcm ( e 1 , … , e n − 3 ) = [ R F ( Ω ) : F ] ∣ s ℓ , where the divisibility is from Proposition 3. Applying Lemma 11 yields
ℓ ≥ s M ≥ s D ( X n ) , X n : = ∑ r = 0 d − 3 ( n − 3 r ) . \ell\ge sM \ge s\mathcal{D}(X_n),\qquad X_n := \sum_{r=0}^{d-3} \binom{n-3}{r}. ℓ ≥ s M ≥ s D ( X n ) , X n := r = 0 ∑ d − 3 ( r n − 3 ) .
Since d d d is fixed,
X n = ( 1 ( d − 3 ) ! + o ( 1 ) ) n d − 3 , X_n = \left(\frac{1}{(d-3)!}+o(1)\right)n^{d-3}, X n = ( ( d − 3 )! 1 + o ( 1 ) ) n d − 3 ,
so that
log X n = ( d − 3 ) log n + O ( 1 ) , log log X n = ( 1 + o ( 1 ) ) log log n . \log X_n=(d-3)\log n+O(1),\qquad\log\log X_n=(1+o(1))\log\log n. log X n = ( d − 3 ) log n + O ( 1 ) , log log X n = ( 1 + o ( 1 )) log log n .
By Lemma 12 ,
log D ( X n ) = ( d − 3 log 2 + o ( 1 ) ) log n log log n . \log\mathcal{D}(X_n)=\left(\frac{d-3}{\log2}+o(1)\right)\log n\log\log n. log D ( X n ) = ( log 2 d − 3 + o ( 1 ) ) log n log log n .
This proves the lower bound in (34) .
For the upper bound, (33) ensures the existence of a constant C d > 0 C_d>0 C d > 0 for which m c f f ( n , d ) ≤ C d log n m_{\mathrm{cff}}(n,d)\le C_d\log n m cff ( n , d ) ≤ C d log n for all sufficiently large n n n . Set m n = ⌈ C d log n ⌉ m_n=\lceil C_d\log n\rceil m n = ⌈ C d log n ⌉ . The function G s ( m ) G_s(m) G s ( m ) is increasing: deleting one factor from a minimizing ( m + 1 ) (m+1) ( m + 1 ) -tuple shows that G s ( m + 1 ) ≥ s G s ( m ) G_s(m+1)\ge sG_s(m) G s ( m + 1 ) ≥ s G s ( m ) . Therefore, by Lemma 13 ,
ℓ min ( n , k , d ; q ) ≤ s G s ( m c f f ( n , d ) ) ≤ s G s ( m n ) . \ell_{\min}(n,k,d;q)\le sG_s(m_{\mathrm{cff}}(n,d))\le sG_s(m_n). ℓ m i n ( n , k , d ; q ) ≤ s G s ( m cff ( n , d )) ≤ s G s ( m n ) .
Since s s s is fixed and m n = ( C d + o ( 1 ) ) log n m_n=(C_d+o(1))\log n m n = ( C d + o ( 1 )) log n , Corollary 4 yields
log ℓ min ( n , k , d ; q ) ≤ ( C d + o ( 1 ) ) log n log log n . \log\ell_{\min}(n,k,d;q)\le(C_d+o(1))\log n\log\log n. log ℓ m i n ( n , k , d ; q ) ≤ ( C d + o ( 1 )) log n log log n .
This proves the upper bound.
The order of log ℓ min ( n , k , d ; q ) \log\ell_{\min}(n,k,d;q) log ℓ m i n ( n , k , d ; q ) is thus determined for fixed k k k and d d d ; the optimal leading constant remains open.
Conclusion
In this paper, we studied the minimum subpacketization of Reed-Solomon codes admitting cut-set-optimal exact F F F -linear repair of every coordinate from any d d d helper nodes. By translating the repair requirements into degree constraints on cross-ratio fields and combining the resulting lower bounds with a basis-transformation construction, we established
ℓ min ( n , k , d ; q ) = s Δ s ( n , d ) = s G s ( n ) \ell_{\min}(n,k,d;q)=s\Delta_s(n,d)=sG_s(n) ℓ m i n ( n , k , d ; q ) = s Δ s ( n , d ) = s G s ( n )
whenever d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2)\ge4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 ) . In particular, this determines the minimum subpacketization in the full-helper case d = n − 1 d=n-1 d = n − 1 with 3 ≤ k < n − 1 3\le k<n-1 3 ≤ k < n − 1 , resolving the corresponding exact linear-repair case of Open Problem 20 of Ramkumar et al. [23 Open Problem 20] . We also obtained explicit formulas for G s ( n ) G_s(n) G s ( n ) and determined the asymptotic order of log ℓ min ( n , k , d ; q ) \log\ell_{\min}(n,k,d;q) log ℓ m i n ( n , k , d ; q ) for fixed k k k and d d d .
The expression s G s ( n ) sG_s(n) s G s ( n ) , however, is not valid for all parameters. The affine-plane construction in Appendix B provides admissible parameters for which
ℓ min ( n , k , d ; q ) ≤ s Δ s ( n , d ) < s G s ( n ) . \ell_{\min}(n,k,d;q)\le s\Delta_s(n,d)<sG_s(n). ℓ m i n ( n , k , d ; q ) ≤ s Δ s ( n , d ) < s G s ( n ) .
Thus, although s G s ( n ) sG_s(n) s G s ( n ) is exact in the range above, s Δ s ( n , d ) s\Delta_s(n,d) s Δ s ( n , d ) is the natural candidate for a general formula. This motivates the following conjecture.
Conjecture 1. For every prime power q q q and all integers 3 ≤ k < d ≤ n − 1 3\le k<d\le n-1 3 ≤ k < d ≤ n − 1 , with s = d + 1 − k s=d+1-k s = d + 1 − k ,
ℓ min ( n , k , d ; q ) = s Δ s ( n , d ) . \ell_{\min}(n,k,d;q)=s\Delta_s(n,d). ℓ m i n ( n , k , d ; q ) = s Δ s ( n , d ) .
Our main result proves this conjecture whenever d ( d + 2 ) ≥ 4 ( n + 1 ) d(d+2)\ge4(n+1) d ( d + 2 ) ≥ 4 ( n + 1 ) . Since the matching upper bound holds for all admissible parameters, it remains to establish ℓ min ( n , k , d ; q ) ≥ s Δ s ( n , d ) \ell_{\min}(n,k,d;q)\ge s\Delta_s(n,d) ℓ m i n ( n , k , d ; q ) ≥ s Δ s ( n , d ) outside this range.
Acknowledgment
We used OpenAI’s ChatGPT (GPT-6) to assist with polishing the exposition throughout the manuscript and checking some of the main proofs. The authors take full responsibility for the correctness, originality, and proper attribution of all content in this manuscript.
Appendix A: Proof of Lemma 10
Proof. We first establish
p 4 t 2 < p t + 1 # , p 4 t 2 2 < p 2 t # ( t ≥ 3 ) . (35) p_{4t^2}<p_{t+1}^{\#},\qquad p_{4t^2}^{2}<p_{2t}^{\#}\qquad(t\ge3). \tag*{(35)} p 4 t 2 < p t + 1 # , p 4 t 2 2 < p 2 t # ( t ≥ 3 ) . (35)
For t = 3 t=3 t = 3 , these inequalities follow from p 36 = 151 < 210 = p 4 # p_{36}=151<210=p_{4}^{\#} p 36 = 151 < 210 = p 4 # and 151 2 = 22801 < 30030 = p 6 # 151^2=22801<30030=p_{6}^{\#} 15 1 2 = 22801 < 30030 = p 6 # . It remains to consider t ≥ 4 t\ge4 t ≥ 4 . All logarithms in this proof are natural.
For an even integer x = 2 m ≥ 4 x=2m\ge4 x = 2 m ≥ 4 , put B x = ( 2 m m ) B_x=\binom{2m}{m} B x = ( m 2 m ) . The central binomial coefficient exceeds the average of all x + 1 x+1 x + 1 binomial coefficients, so B x > 2 x / ( x + 1 ) B_x>2^x/(x+1) B x > 2 x / ( x + 1 ) . For each prime p p p , the factorial valuation formula yields
v p ( B x ) = ∑ j ≥ 1 ( ⌊ x p j ⌋ − 2 ⌊ x / 2 p j ⌋ ) . v_p(B_x)=\sum_{j\ge1}\left(\left\lfloor\frac{x}{p^j}\right\rfloor-2\left\lfloor\frac{x/2}{p^j}\right\rfloor\right). v p ( B x ) = j ≥ 1 ∑ ( ⌊ p j x ⌋ − 2 ⌊ p j x /2 ⌋ ) .
Each summand is 0 or 1 and vanishes when p j > x p^j>x p j > x . Thus p v p ( B x ) ≤ x p^{v_p(B_x)}\le x p v p ( B x ) ≤ x for every prime p p p , and B x ≤ x π ( x ) B_x\le x^{\pi(x)} B x ≤ x π ( x ) . Taking logarithms and using log 2 > 2 / 3 \log2>2/3 log 2 > 2/3 and x + 1 < x 2 x+1<x^2 x + 1 < x 2 , we obtain
π ( x ) > x log 2 − log ( x + 1 ) log x > 2 x 3 log x − 2. (36) \pi(x)>\frac{x\log2-\log(x+1)}{\log x}>\frac{2x}{3\log x}-2. \tag*{(36)} π ( x ) > log x x log 2 − log ( x + 1 ) > 3 log x 2 x − 2. (36)
Set x t = ( t + 2 ) ! x_t=(t+2)! x t = ( t + 2 )! and F t = 2 x t / ( 3 log x t ) F_t=2x_t/(3\log x_t) F t = 2 x t / ( 3 log x t ) . Since log 720 < 7 \log720<7 log 720 < 7 , we have F 4 > 480 / 7 > 66 F_4>480/7>66 F 4 > 480/7 > 66 . For t ≥ 4 t\ge4 t ≥ 4 , the inequality x t ≥ t + 3 x_t\ge t+3 x t ≥ t + 3 implies
F t + 1 F t = t + 3 1 + log ( t + 3 ) / log x t ≥ t + 3 2 ≥ 7 2 . \frac{F_{t+1}}{F_t}=\frac{t+3}{1+\log(t+3)/\log x_t}\ge\frac{t+3}{2}\ge\frac{7}{2}. F t F t + 1 = 1 + log ( t + 3 ) / log x t t + 3 ≥ 2 t + 3 ≥ 2 7 .
Moreover,
7 2 ( 4 t 2 + 2 ) − ( 4 ( t + 1 ) 2 + 2 ) = 10 t 2 − 8 t + 1 > 0. \frac{7}{2}(4t^2+2)-(4(t+1)^2+2)=10t^2-8t+1>0. 2 7 ( 4 t 2 + 2 ) − ( 4 ( t + 1 ) 2 + 2 ) = 10 t 2 − 8 t + 1 > 0.
Induction therefore proves F t > 4 t 2 + 2 F_t>4t^2+2 F t > 4 t 2 + 2 for every t ≥ 4 t\ge4 t ≥ 4 . Applying (36) to x t x_t x t yields π ( x t ) > 4 t 2 \pi(x_t)>4t^2 π ( x t ) > 4 t 2 , and hence
p 4 t 2 < x t = ( t + 2 ) ! ≤ p t + 1 # , p_{4t^2}<x_t=(t+2)!\le p_{t+1}^{\#}, p 4 t 2 < x t = ( t + 2 )! ≤ p t + 1 # ,
where the last inequality follows from p j ≥ j + 1 p_j\ge j+1 p j ≥ j + 1 .
To prove the second inequality in (35) , put
R t = p 2 t # ( p t + 1 # ) 2 . R_t=\frac{p_{2t}^{\#}}{(p_{t+1}^{\#})^2}. R t = ( p t + 1 # ) 2 p 2 t # .
We have R 4 = 4199 / 2310 > 1 R_4=4199/2310>1 R 4 = 4199/2310 > 1 , and, for t ≥ 4 t\ge4 t ≥ 4 ,
R t + 1 R t = p 2 t + 1 p 2 t + 2 p t + 2 2 > 1. \frac{R_{t+1}}{R_t}=\frac{p_{2t+1}p_{2t+2}}{p_{t+2}^2}>1. R t R t + 1 = p t + 2 2 p 2 t + 1 p 2 t + 2 > 1.
Thus R t ≥ R 4 > 1 R_t\ge R_4>1 R t ≥ R 4 > 1 , so
p 4 t 2 2 < ( p t + 1 # ) 2 < p 2 t # . p_{4t^2}^2<(p_{t+1}^{\#})^2<p_{2t}^{\#}. p 4 t 2 2 < ( p t + 1 # ) 2 < p 2 t # .
Together with the case t = 3 t=3 t = 3 , this proves (35) .
Now let s , n , t s,n,t s , n , t satisfy the hypotheses of the lemma and set x = p n + c s x=p_{n+c_s} x = p n + c s . Since n + c s ≤ 4 t 2 n+c_s\le4t^2 n + c s ≤ 4 t 2 , we have x ≤ p 4 t 2 x\le p_{4t^2} x ≤ p 4 t 2 . By (21) ,
G s ( n ) ≤ G s ( n − 1 ) x < G s ( n − 1 ) p t + 1 # , G_s(n)\le G_s(n-1)x<G_s(n-1)p_{t+1}^{\#}, G s ( n ) ≤ G s ( n − 1 ) x < G s ( n − 1 ) p t + 1 # ,
which proves (23) . The sequence ( p m # ) 1 / m (p_m^{\#})^{1/m} ( p m # ) 1/ m is increasing, since p m + 1 > ( p m # ) 1 / m p_{m+1}>(p_m^{\#})^{1/m} p m + 1 > ( p m # ) 1/ m . Therefore, for 2 ≤ b ≤ n 2\le b\le n 2 ≤ b ≤ n ,
p b t # ≥ ( p 2 t # ) b / 2 > p 4 t 2 b ≥ x b . p_{bt}^{\#}\ge(p_{2t}^{\#})^{b/2}>p_{4t^2}^{b}\ge x^b. p b t # ≥ ( p 2 t # ) b /2 > p 4 t 2 b ≥ x b .
Combining this with (21) proves (24) . □
Appendix B: Strict Inequality Between Δ s ( n , d ) \Delta_s(n,d) Δ s ( n , d ) and G s ( n ) G_s(n) G s ( n )
An affine-plane construction yields feasible degree tuples with Δ s ( n , d ) < G s ( n ) \Delta_s(n,d) < G_s(n) Δ s ( n , d ) < G s ( n ) for a family of parameters. Together with Theorem 6, this shows that ℓ min ( n , k , d ; q ) = s G s ( n ) \ell_{\min}(n,k,d;q) = sG_s(n) ℓ m i n ( n , k , d ; q ) = s G s ( n ) is not valid for all admissible parameters.
Proposition 5. Let T ≥ 2 T \ge2 T ≥ 2 be a prime power, and let n , d , s n,d,s n , d , s be integers with
n ≥ T 2 + 1 , 1 ≤ d ≤ T − 1 , s ≥ 2. n \ge T^2 + 1,\qquad1 \le d \le T - 1,\qquad s \ge2. n ≥ T 2 + 1 , 1 ≤ d ≤ T − 1 , s ≥ 2. Put v = max { T 2 , n − T } v = \max\{T^2,n-T\} v = max { T 2 , n − T } . Then
Δ s ( n , d ) ≤ G s ( v ) ≤ s − ( n − v ) G s ( n ) < G s ( n ) . (37) \Delta_s(n,d) \le G_s(v) \le s^{-(n-v)}G_s(n) < G_s(n). \tag*{(37)} Δ s ( n , d ) ≤ G s ( v ) ≤ s − ( n − v ) G s ( n ) < G s ( n ) . (37) If additionally 4 ≤ d ≤ T − 1 4 \le d \le T-1 4 ≤ d ≤ T − 1 and 2 ≤ s ≤ d − 2 2 \le s \le d-2 2 ≤ s ≤ d − 2 , then, with k = d + 1 − s k=d+1-s k = d + 1 − s , for every prime power q q q ,
ℓ min ( n , k , d ; q ) ≤ s Δ s ( n , d ) < s G s ( n ) . (38) \ell_{\min}(n,k,d;q) \le s\Delta_s(n,d) < sG_s(n). \tag*{(38)} ℓ m i n ( n , k , d ; q ) ≤ s Δ s ( n , d ) < s G s ( n ) . (38) Here T T T need not be related to the repair base-field size q q q .
Proof. In the affine plane F T 2 \mathbb{F}_T^2 F T 2 , consider the T 2 T^2 T 2 nonvertical lines
L a , b = { ( x , a x + b ) : x ∈ F T } , a , b ∈ F T , L_{a,b}=\{(x,ax+b):x\in\mathbb{F}_T\},\qquad a,b\in\mathbb{F}_T, L a , b = {( x , a x + b ) : x ∈ F T } , a , b ∈ F T ,
and the T T T vertical lines
V c = { ( c , y ) : y ∈ F T } , c ∈ F T . V_c=\{(c,y):y\in\mathbb{F}_T\},\qquad c\in\mathbb{F}_T. V c = {( c , y ) : y ∈ F T } , c ∈ F T .
Each line has T T T points, and two distinct lines meet in at most one point.
Put h = min { T , n − T 2 } h=\min\{T,n-T^2\} h = min { T , n − T 2 } and z = n − T 2 − h z=n-T^2-h z = n − T 2 − h . Take all T 2 T^2 T 2 nonvertical lines, any h h h vertical lines, and z z z singleton sets on distinct new points outside F T 2 \mathbb{F}_T^2 F T 2 . These sets form a family A \mathcal{A} A of exactly T 2 + h + z = n T^2+h+z=n T 2 + h + z = n members. Since the nonvertical lines cover F T 2 \mathbb{F}_T^2 F T 2 , the ground set U = ⋃ A ∈ A A \mathcal{U}=\bigcup_{A\in\mathcal{A}}A U = ⋃ A ∈ A A satisfies
∣ U ∣ = T 2 + z = n − h = max { T 2 , n − T } = v . |\mathcal{U}|=T^2+z=n-h=\max\{T^2,n-T\}=v. ∣ U ∣ = T 2 + z = n − h = max { T 2 , n − T } = v .
For each line A ∈ A A\in\mathcal{A} A ∈ A , any d d d other members cover at most d < T d<T d < T of its points. Each singleton contains a point belonging to no other member. Hence, for every A ∈ A A\in\mathcal{A} A ∈ A and every H ⊆ A ∖ { A } \mathcal{H}\subseteq\mathcal{A}\setminus\{A\} H ⊆ A ∖ { A } with ∣ H ∣ = d |\mathcal{H}|=d ∣ H ∣ = d ,
A ∖ ⋃ B ∈ H B ≠ ∅ . A\setminus\bigcup_{B\in\mathcal{H}}B\ne\varnothing. A ∖ B ∈ H ⋃ B = ∅ .
Choose pairwise coprime integers γ u ≥ s \gamma_u\ge s γ u ≥ s ( u ∈ U ) (u\in\mathcal{U}) ( u ∈ U ) with ∏ u ∈ U γ u = G s ( v ) \prod_{u\in\mathcal{U}}\gamma_u=G_s(v) ∏ u ∈ U γ u = G s ( v ) , and define
a A = ∏ u ∈ A γ u ( A ∈ A ) . a_A=\prod_{u\in A}\gamma_u\qquad(A\in\mathcal{A}). a A = u ∈ A ∏ γ u ( A ∈ A ) .
Since the weights are pairwise coprime, the least common multiple over any subfamily equals the product of the weights on its union. Thus
lcm ( a B : B ∈ H ∪ { A } ) lcm ( a B : B ∈ H ) = ∏ u ∈ A ∖ ⋃ B ∈ H B γ u ≥ s . \frac{\operatorname{lcm}(a_B:B\in\mathcal{H}\cup\{A\})}{\operatorname{lcm}(a_B:B\in\mathcal{H})}
=\prod_{u\in A\setminus\bigcup_{B\in\mathcal{H}}B}\gamma_u\ge s. lcm ( a B : B ∈ H ) lcm ( a B : B ∈ H ∪ { A }) = u ∈ A ∖ ⋃ B ∈ H B ∏ γ u ≥ s .
Therefore ( a A ) A ∈ A (a_A)_{A\in\mathcal{A}} ( a A ) A ∈ A is feasible for ( n , d , s ) (n,d,s) ( n , d , s ) . Because A \mathcal{A} A covers U \mathcal{U} U ,
Δ s ( n , d ) ≤ lcm ( a A : A ∈ A ) = ∏ u ∈ U γ u = G s ( v ) . \Delta_s(n,d)\le\operatorname{lcm}(a_A:A\in\mathcal{A})=\prod_{u\in\mathcal{U}}\gamma_u=G_s(v). Δ s ( n , d ) ≤ lcm ( a A : A ∈ A ) = u ∈ U ∏ γ u = G s ( v ) .
In a minimizing tuple for G s ( n ) G_s(n) G s ( n ) , any v v v entries have product at least G s ( v ) G_s(v) G s ( v ) , while each remaining entry is at least s s s . Consequently,
G s ( n ) ≥ s n − v G s ( v ) . G_s(n)\ge s^{n-v}G_s(v). G s ( n ) ≥ s n − v G s ( v ) .
Since n − v = h ≥ 1 n-v=h\ge1 n − v = h ≥ 1 and s ≥ 2 s\ge2 s ≥ 2 , we have s − ( n − v ) < 1 s^{-(n-v)}<1 s − ( n − v ) < 1 . This proves (37) .
Under the additional assumptions, 3 ≤ k = d + 1 − s ≤ d − 1 3\le k=d+1-s\le d-1 3 ≤ k = d + 1 − s ≤ d − 1 and d ≤ T − 1 < n d\le T-1<n d ≤ T − 1 < n . The coding bound then follows from Theorem 6. □ \square □