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 ${\mathbb{F}}_{q^{\ell }}$ admitting cut-set-optimal exact ${\mathbb{F}}_q$-linear repair of every coordinate from any $d$ helpers. For $3\le k<d\le n-1$, write $s=d+1-k$ and denote this minimum by ${\ell }_{min}(n,k,d;q)$. Using divisibility and relative-degree constraints on cross-ratio fields of evaluation sets, we establish ${\ell }_{min}(n,k,d;q)\ge s{G}_s(d+1)$, where $G_s(m)$ is the minimum product of $m$ pairwise coprime integers, each at least $s$. Let ${\Delta }_s(n,d)$ be the minimum of $lcm(a_1,\dots ,a_n)$ over positive integers $a_1,\dots ,a_n$ satisfying $lcm(a_j:j\in J\cup \{i\})\ge slcm(a_j:j\in J)$ for every $d$-subset $J\subseteq [n]$ and every $i\in [n]\setminus J$. We construct RS codes with subpacketization $s{\Delta }_s(n,d)$ and further prove that ${\ell }_{min}(n,k,d;q)=s{\Delta }_s(n,d)=s{G}_s(n)$ whenever $d(d+2)\ge 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 {\ell }_{min}(n,k,d;q)={\Theta }_{k,d}(\log n\log \log n)$ as $n\to \infty$, using divisor-function estimates and cover-free families. An affine-plane construction shows that ${\Delta }_s(n,d)<G_s(n)$ for some parameters, so $s{G}_s(n)$ is not a universal formula. We conjecture that ${\ell }_{min}(n,k,d;q)=s{\Delta }_s(n,d)$ for every prime power $q$ and all $3\le k<d\le n-1$.

arXiv comment33 pages