The Minimum Subpacketization of Reed-Solomon Codes with Linear Repair Achieving the Cut-Set Bound
Abstract
In this paper, we study the minimum subpacketization of (n,k) Reed-Solomon (RS) codes over 𝔽qℓ admitting cut-set-optimal exact 𝔽q-linear repair of every coordinate from any d helpers. For 3≤ k<d≤ n−1, write s=d+1−k and denote this minimum by ℓmin(n,k,d;q). Using divisibility and relative-degree constraints on cross-ratio fields of evaluation sets, we establish ℓmin(n,k,d;q)≥ sGs(d+1), where Gs(m) is the minimum product of m pairwise coprime integers, each at least s. Let Δs(n,d) be the minimum of lcm(a1,…,an) over positive integers a1,…,an satisfying lcm(aj:j∈ J∪{i})≥ s lcm(aj:j∈ J) for every d-subset J⊆[n] and every i∈[n]∖ J. We construct RS codes with subpacketization sΔs(n,d) and further prove that ℓmin(n,k,d;q)=sΔs(n,d)=sGs(n) whenever d(d+2)≥ 4(n+1), for every prime power q. In particular, this determines the minimum subpacketization in the full-helper case d=n−1, resolving the corresponding exact linear-repair case of Open Problem 20 posed by Ramkumar et al. in their survey on codes for distributed storage. We further give a finite formula for Gs(n) and determine the exact threshold for its closed-form expression in terms of the first n primes. For fixed k and d, we prove logℓmin(n,k,d;q)= Θk,d(log nloglog n) as n→∞, using divisor-function estimates and cover-free families. An affine-plane construction shows that Δs(n,d)<Gs(n) for some parameters, so sGs(n) is not a universal formula. We conjecture that ℓmin(n,k,d;q)=sΔs(n,d) for every prime power q and all 3≤ k<d≤ n−1.
Related
- Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound
- From Linear Exact Repair to Mixed-Alphabet Codes: The Bandwidth-Subpacketization Tradeoff of MDS Array Codes
- New Minimum Storage Regenerating Codes With Small Sub-packetization Levels for All Admissible Repair Degrees
- Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
- A new perspective in linear Cauchy Elasticity: variational minimum principles for statics, dynamics, and heterogeneous materials
BibTeX
@misc{fang2026minimum,
title = {{The Minimum Subpacketization of Reed-Solomon Codes with Linear Repair Achieving the Cut-Set Bound}},
author = {Weijun Fang and Jing Qiu and Shu-Tao Xia and Fang-Wei Fu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37522},
eprint = {2610.37522},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37522},
note = {CC0},
}
RIS
TY - UNPB
TI - The Minimum Subpacketization of Reed-Solomon Codes with Linear Repair Achieving the Cut-Set Bound
AU - Weijun Fang
AU - Jing Qiu
AU - Shu-Tao Xia
AU - Fang-Wei Fu
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37522
UR - https://arxiv.org/abs/2610.37522
AB - In this paper, we study the minimum subpacketization of (n,k) Reed-Solomon (RS) codes over 𝔽_q^ℓ admitting cut-set-optimal exact 𝔽_q-linear repair of every coordinate from any d helpers. For 3≤ k<d≤ n−1, write s=d+1−k and denote this minimum by ℓ_min(n,k,d;q). Using divisibility and relative-degree constraints on cross-ratio fields of evaluation sets, we establish ℓ_min(n,k,d;q)≥ sG_s(d+1), where G_s(m) is the minimum product of m pairwise coprime integers, each at least s. Let Δ_s(n,d) be the minimum of lcm(a_1,…,a_n) over positive integers a_1,…,a_n satisfying lcm(a_j:j∈ J∪{i})≥ s lcm(a_j:j∈ J) for every d-subset J⊆[n] and every i∈[n]∖ J. We construct RS codes with subpacketization sΔ_s(n,d) and further prove that ℓ_min(n,k,d;q)=sΔ_s(n,d)=sG_s(n) whenever d(d+2)≥ 4(n+1), for every prime power q. In particular, this determines the minimum subpacketization in the full-helper case d=n−1, resolving the corresponding exact linear-repair case of Open Problem 20 posed by Ramkumar et al. in their survey on codes for distributed storage. We further give a finite formula for G_s(n) and determine the exact threshold for its closed-form expression in terms of the first n primes. For fixed k and d, we prove logℓ_min(n,k,d;q)= Θ_k,d(log nloglog n) as n→∞, using divisor-function estimates and cover-free families. An affine-plane construction shows that Δ_s(n,d)<G_s(n) for some parameters, so sG_s(n) is not a universal formula. We conjecture that ℓ_min(n,k,d;q)=sΔ_s(n,d) for every prime power q and all 3≤ k<d≤ n−1.
ER -