The Minimum Subpacketization of Reed-Solomon Codes with Linear Repair Achieving the Cut-Set Bound

arXiv:2610.37522 · cs.IT, math.IT · Submitted 2026-10-27 · Read on arXiv

cs.IT, math.IT

Submitted: 2026-10-27

Updated: 2026-10-27

Comments: 33 pages

License: http://creativecommons.org/publicdomain/zero/1.0/

The gist: In this paper, we study the minimum subpacketization of (n,k) Reed-Solomon (RS) codes over F q admitting cut-set-optimal exact F q-linear repair of every coordinate from any d helpers.

Abstract

In this paper, we study the minimum subpacketization of (n,k) Reed-Solomon (RS) codes over F q admitting cut-set-optimal exact F q-linear repair of every coordinate from any d helpers. For 3 at most k<d at most 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) at least 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 in J i) at least s lcm(a j:j in J) for every d-subset J [n] and every i in[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) at least 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 min(n,k,d;q)= Θ k,d(n n) as n to infinity, 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 at most k<d at most n-1.

Related papers