Reed-Solomon Codes with Optimal Repair Bandwidth: A Basis-Transformation Approach
January 15, 2026
Abstract
Maximum distance separable (MDS) codes are widely used in distributed storage, but naively repairing a single failure in an \((n,k)\) MDS code requires downloading the full contents of \(k\) surviving nodes. Minimum storage regenerating (MSR) codes, introduced by Dimakis et al., minimize repair bandwidth while preserving the MDS property by contacting \(d>k\) helper nodes and downloading only a fraction of each helper. For scalar MDS codes, Guruswami and Wootters established a linear repair framework, and Tamo, Ye, and Barg subsequently gave the first explicit Reed-Solomon (RS) codes achieving the MSR point. Their construction yields RS-MSR codes with subpacketization \(\ell=s\prod_{i=1}^n p_i\), where \(s=d+1-k\) and the distinct primes \(p_i\) satisfy \(p_i\equiv 1\pmod{s}\). In this paper, we show that this congruence condition is not intrinsic to the RS repair problem. We develop a basis-transformation approach to the construction of repair-enabling subspaces. The approach consists of three deterministic operations—Euclidean Square Partition, Transposition, and Column Aggregation—which construct the required repair-enabling subspaces directly from the standard monomial basis of the repair field. Consequently, we obtain RS-MSR codes with subpacketization \(\ell=s\prod_{i=1}^n p_i\) for arbitrary distinct primes \(p_i>s\). For fixed \(s\), this improves the subpacketization of the Tamo–Ye–Barg construction by a factor asymptotic to \(\varphi(s)^{n+\mathrm{o}(n)}\), where \(\varphi(\cdot)\) denotes Euler’s totient function.
Minimum storage regenerating (MSR) codes, Reed-Solomon codes, basis transformation, optimal repair, subpacketization.
1 Introduction↩︎
Reed–Solomon (RS) codes are widely used in distributed storage systems due to their optimal storage efficiency. A major practical challenge is that recovering a single failed node requires downloading a large amount of data from the remaining nodes. Dimakis et al. [2] established the fundamental tradeoff between storage overhead and repair bandwidth, and Minimum Storage Regenerating (MSR) codes achieve the corresponding cut-set bound while maintaining the MDS property.
Assume the data are encoded by a code \(\mathcal{C}\) over a finite field \(F\), where each code symbol is either a single element of \(F\) or an \(\ell\)-dimensional vector over \(F\). In the former case, \(\mathcal{C}\) is called a scalar code; in the latter case, \(\mathcal{C}\) is called an array code with subpacketization \(\ell\). Most MSR constructions have focused on array codes, and many interesting results have been obtained; see, e.g., [3]–[18]. In contrast, constructing scalar MDS codes, particularly Reed-Solomon codes, that achieve the cut-set bound remained an open problem for years. A landmark result by Tamo, Ye, and Barg [19] provided the first explicit construction of \((n,k)\) Reed-Solomon codes that are MSR codes, utilizing the linear repair scheme for scalar codes proposed by Guruswami and Wootters [20]. As shown in [19] and reviewed in Section 2.2, for a Reed-Solomon code over a finite field \(\mathbb{K}\), optimal repair of a failed node \(i\) from \(d\) helper nodes requires the construction of an \(F_i\)-subspace (where \(F_i\) is a subfield of \(\mathbb{K}\)) \(S_i\subseteq\mathbb{K}\) satisfying \[\label{eq:key-subspace} \dim_{F_i}(S_i)=p_i,\qquad \mathbb{K}=\sum_{u=0}^{s-1}\alpha_i^u S_i,\tag{1}\] where \(s=d+1-k\). The construction in [19], which we refer to as the TYB construction, achieves Eq. 1 under the arithmetic restriction \(p_i\equiv1\pmod{s}\), and hence yields subpacketization \(\ell=s\prod_{i=1}^n p_i\). This raises a natural question: Is the congruence condition \(p_i\equiv1\pmod{s}\) intrinsic to optimal repair, or merely an artifact of the basis choice in the TYB construction?
In this paper, we adopt a basis-transformation approach. More precisely, we construct the required repair-enabling subspaces by applying an explicit change of \(\mathbb{F}\)-basis, realized through three deterministic operations: Euclidean Square Partition, Transposition, and Column Aggregation. This new viewpoint allows us to remove the congruence restriction \(p_i\equiv1\pmod{s}\) imposed in [19]. Consequently, for arbitrary distinct primes \(p_i>s\), we obtain RS-MSR codes with subpacketization \[\ell=s\prod_{i=1}^n p_i .\] For fixed \(s\), this improves the subpacketization of [19] by a factor asymptotic to \(\varphi(s)^{n+\mathrm{o}(n)}\) (see Table 1).
| Construction | Subpacketization |
|---|---|
| RS-MSR code in [19] | \((\varphi(s)n)^{n+\mathrm{o}(n)}\) |
| RS-MSR code in this paper | \(n^{n+\mathrm{o}(n)}\) |
The remainder of this paper is organized as follows. Section 2 provides the necessary preliminaries on RS codes and linear repair schemes. Section 3 presents our main results. Section 4 concludes this paper.
2 Preliminaries↩︎
Throughout this paper, we use the following notation unless stated otherwise.
For integers \(a,b\), define \[[a,b]:=\{a,a+1,\dots,b\},\] with the convention that \([a,b]=\emptyset\) whenever \(a>b\).
For a positive integer \(n\), define \([n] := \{1,\dots,n\}\).
For an array \(A\) of size \(a\times b\), we index its entries by \((i,j)\in \mathcal{I}(a,b)\), where \[\mathcal{I}(a,b) := [0,a-1]\times[0,b-1],\] and denote by \(A(i,j)\) the entry in row \(i\) and column \(j\).
2.1 RS Codes and Repair Bandwidth↩︎
We first recall how a Reed-Solomon code over an extension field can be viewed as an array code over its base field.
Let \(\mathbb{K}\) be a finite field. Let \(\Omega=\{\omega_1,\omega_2,\ldots,\omega_n\}\subseteq \mathbb{K}\) be a set of \(n\) pairwise distinct elements, and let \(v=(v_1,\ldots,v_n)\in (\mathbb{K}^*)^n\), where \(\mathbb{K}^*:=\mathbb{K}\setminus\{0\}\). The generalized Reed-Solomon code \(\operatorname{GRS}_{\mathbb{K}}(n,k,\Omega,v)\subseteq \mathbb{K}^n\) with evaluation set \(\Omega\) and column multipliers \(v\) is defined as the set \[\left\{\left(v_1 f(\omega_1),\ldots,v_n f(\omega_n)\right)\in \mathbb{K}^n:\;f\in \mathbb{K}[x],\;\deg f\le k-1\right\}.\] If \(v=(1,\ldots,1)\), then the GRS code is called a Reed-Solomon code and is denoted by \(\operatorname{RS}_{\mathbb{K}}(n,k,\Omega)\). It is well known (see [21]) that \[\left(\operatorname{RS}_{\mathbb{K}}(n,k,\Omega)\right)^{\perp} =\operatorname{GRS}_{\mathbb{K}}(n,n-k,\Omega,u),\] where \(u_i=\prod_{j\neq i}(\omega_i-\omega_j)^{-1}\) for \(i=1,\ldots,n\).
Let \(\mathcal{C}\) be an \((n,k)\) MDS array code over a finite field \(\mathbb{F}\) with subpacketization \(\ell\), i.e., each node stores a vector \(c_i\in \mathbb{F}^{\ell}\). If the \(i\)-th node \(c_i\) is erased, the repair bandwidth \(N(\mathcal{C}, i,\mathcal{H})\) of \(c_i\) is defined as the total amount of information (measured in symbols over \(\mathbb{F}\)) downloaded from a helper set \(\mathcal{H}\subseteq [n]\setminus\{i\}\) with \(|\mathcal{H}|=d\) to reconstruct \(c_i\). The cut-set bound of [2] states that the repair bandwidth \(N(\mathcal{C},i,\mathcal{H})\) satisfies \[\label{eq:cutset} N(\mathcal{C}, i, \mathcal{H}) \ge \frac{d\ell}{d-k+1}.\tag{2}\] We call \(\mathcal{C}\) an MSR code if it achieves the cut-set bound in Eq. 2 with equality for all \(i \in [n]\) and every helper set \(\mathcal{H}\subseteq[n]\setminus\{i\}\) with \(|\mathcal{H}|=d\).
If \(\mathbb{K}/\mathbb{F}\) is an extension of degree \(\ell\), then every RS code over \(\mathbb{K}\) can be regarded as an MDS array code over \(\mathbb{F}\) with subpacketization \(\ell\). An RS code over \(\mathbb{K}\) is called an RS-MSR code if it is an MSR code under this interpretation.
2.2 Reed-Solomon codes as MSR codes↩︎
The next theorem converts the linear repair of a scalar MDS code into a dual-code criterion. It is the starting point for both the TYB construction and our new construction.
Theorem 1 ([20]). Let \(\mathcal{C}\subset \mathbb{K}^n\) be a scalar linear MDS code of length \(n\). Let \(\mathbb{F}\) be a subfield of \(\mathbb{K}\) such that \([\mathbb{K}: \mathbb{F}]=\ell\). For a given \(i \in [n]\) and a helper set \(\mathcal{H}\subseteq [n]\setminus\{i\}\), the following statements are equivalent.
There is a linear repair scheme of the node \(c_i\) over \(\mathbb{F}\) such that the repair bandwidth \(N(\mathcal{C}, i, \mathcal{H}) \leq b\).
There is a subset of codewords \(P_i\subseteq \mathcal{C}^{\perp}\) with size \(|P_i|=\ell\) such that \[{\rm dim}_{\mathbb{F}}(\{x_i:x\in P_i\})=\ell,\] and \[b\geq \sum_{j\in \mathcal{H}}{\rm dim}_{\mathbb{F}}(\{x_j:x\in P_i\}).\]
We next recall the TYB construction, which formulates a sufficient subspace condition for optimal repair. Our basis-transformation approach, introduced in Section 3, will provide a new constructive procedure for satisfying this condition.
Let \(\mathbb{F}_{q}\) be a finite field. Denote \(s:=d-k+1\) and let \(p_1,\dots,p_n\) be \(n\) distinct primes such that \[\label{eq:pms} p_i\equiv 1 \;\text{mod}\, s \;\;\text{~for all~} i=1,2,\dots,n.\tag{3}\] For \(i=1,\dots,n\), let \(\alpha_i\) be an element of an extension field of \(\mathbb{F}_{q}\) such that \([\mathbb{F}_{q}(\alpha_i):\mathbb{F}_{q}]=p_i\), and let \[\mathbb{E}:=\mathbb{F}_{q}(\alpha_1,\dots,\alpha_n).\] Since the primes \(p_1,\ldots,p_n\) are distinct, \([\mathbb{E}:\mathbb{F}_{q}]=\prod_{i=1}^np_i\). For \(i=1,\dots,n\), define \[F_i=\mathbb{F}_{q}(\{\alpha_j:j\neq i\}).\] Then \(\mathbb{E}= F_i(\alpha_i)\) and \([\mathbb{E}: F_i]=p_i\). Let \(\mathbb{K}\) be the degree-\(s\) extension of the field \(\mathbb{E}\), i.e., there exists an element \(\beta\in \mathbb{K}\) of degree \(s\) over \(\mathbb{E}\) such that \(\mathbb{K}=\mathbb{E}(\beta)\). We also have \([\mathbb{K}: F_i]=s p_i\) for all \(i\).
The following theorem gives the exact TYB construction under the congruence condition Eq. 3 .
Theorem 2 ([19]). Let \(k,n,d\) be any positive integers such that \(k< d \leq n-1.\) Let \(\Omega=\{\alpha_1,\dots,\alpha_n\}\), where each \(\alpha_i\), for \(i=1,\dots,n\), is an element of degree \(p_i\) over \(\mathbb{F}_{q}\) and \(p_i\) is a prime satisfying Eq. 3 . The code \(\mathcal{C}:=\text{\rm RS}_{\mathbb{K}}(n,k,\Omega)\) achieves the cut-set bound for the repair of any single node from any \(d\) helper nodes. In other words, \(\mathcal{C}\) is an \((n,k)\) MSR code with repair degree \(d\) and subpacketization \(s\prod_{i=1}^{n}p_i\).
The following trace-expansion identity is fundamental to trace-based repair schemes for Reed-Solomon codes.
Lemma 1 ([22]). Let \(\mathbb{K}\) be an extension field of a finite field \(\mathbb{F}\) with \([\mathbb{K}:\mathbb{F}]=\ell\). Assume \(\{\zeta_1,\dots,\zeta_{\ell}\}\) and \(\{\epsilon_1,\dots,\epsilon_{\ell}\}\) are dual bases of \(\mathbb{K}\) over \(\mathbb{F}\), i.e., \({\rm tr}(\zeta_i\epsilon_j)=\delta_{ij}\), where \({\rm tr}(\cdot)\) denotes the trace function from \(\mathbb{K}\) to \(\mathbb{F}\) and \(\delta_{ij}\) is the Kronecker delta. Then for any \(\varepsilon\in \mathbb{K}\), \[\varepsilon=\sum_{i=1}^{\ell}{\rm tr}(\zeta_i\varepsilon)\epsilon_{i}.\]
Under the congruence condition Eq. 3 , Tamo, Ye, and Barg [19] provide the following optimal repair-enabling subspace for their construction.
Lemma 2 ([19]). Let \(\alpha_i,\beta,F_i\) be as above. Given \(i\in [n]\), define the following vector spaces over \(F_i\): \[\begin{gather} S_i^{(1)} =\mathop{\mathrm{Span}}_{F_i} \big(\beta^u \alpha_i^{u+rs}: u\in [0,s-1],\;r\in [0,\tfrac{p_i-1}{s}-1] \big) \\ S_i^{(2)} =\mathop{\mathrm{Span}}_{F_i} \Big(\sum_{u=0}^{s - 1}\beta^u \alpha_i^{p_i-1} \Big) \\ S_i =S_i^{(1)} + S_i^{(2)}. \end{gather}\] where \((p_i-1)/s\in\mathbb{Z}\) by Eq. 3 .
Then \[\label{eq:S} \dim_{F_i} S_i = p_i \text{ and } S_i + S_i\alpha_i+\dots + S_i\alpha_i^{s-1}=\mathbb{K}.\qquad{(1)}\]
We next explain how the subspace condition Eq. ?? , together with the trace-expansion identity, enables the repair process.
Let \(\mathcal{C}= {\rm RS}_{\mathbb{K}}(n,k,\Omega)\) and let \(c=(c_1,c_2,\dots,c_n)\) be a codeword of \(\mathcal{C}\). Assume that \(c_i\) is erased. The TYB repair argument proceeds as follows.
By Lemma 2, there exists an \(F_i\)-subspace \(S_i\subseteq\mathbb{K}\) such that \[\dim_{F_i} S_i= p_i \qquad\text{and}\qquad \mathbb{K}=S_i +S_i\alpha_i +\dots+ S_i\alpha_i^{s-1}.\] Let \(e_1, \dots, e_{p_i}\) be an arbitrary basis of the subspace \(S_i\) over the field \(F_i\).
Let \(\mathcal{H}=\{i_1,\dots,i_d\}\subset [n]\setminus \{i\}\) be any helper set of size \(d =s+ k-1\).
Let \[\Lambda(x)=\prod_{j\in [n]\setminus(\mathcal{H}\cup \{i\})}(x-\alpha_j).\] Then for each \(u\in[0,s-1]\), the vector \[(u_1\alpha_1^{u}\Lambda(\alpha_1),\dots , u_n\alpha_n^{u}\Lambda(\alpha_n))\] belongs to \(\mathcal{C}^{\perp}\) because \(\deg(x^u\Lambda(x))\le (s-1)+(n-d-1)=n-k-1\). Hence \[c_i u_i\alpha_i^u \Lambda(\alpha_i)+\sum_{j=1}^{d}c_{i_j}u_{i_j}\alpha_{i_j}^{u}\Lambda(\alpha_{i_j})=0.\]
Let \({\rm tr}_i := {\rm tr}_{\mathbb{K}/F_i}\). Multiplying the above identity by \(e_m\) and applying \({\rm tr}_i\) yields, for each \(u\in[0,s-1]\) and \(m\in[1,p_i]\), \[\begin{align} {\rm tr}_i(c_i e_m u_i \alpha_i^{u} \Lambda(\alpha_i))&=-\sum_{j=1}^{d}{\rm tr}_i(c_{i_j} e_m u_{i_j} \alpha_{i_j}^{u} \Lambda(\alpha_{i_j}))\\ &=-\sum_{j=1}^{d}\alpha_{i_j}^{u} \Lambda(\alpha_{i_j}){\rm tr}_i(c_{i_j} e_m u_{i_j}), \end{align}\] because \(\alpha_{i_j},\Lambda(\alpha_{i_j})\in F_i\) whenever \(i_j\neq i\).
Since \(\mathbb{K}=\sum_{u=0}^{s-1}\alpha_i^uS_i\) and \([\mathbb{K}:F_i]=sp_i\), the \(sp_i\) elements \[\left\{e_m\alpha_i^u:\;0\le u\le s-1,\;1\le m\le p_i\right\}\] form an \(F_i\)-basis of \(\mathbb{K}\); multiplying by the nonzero scalar \(u_i \Lambda(\alpha_i)\) preserves this basis. Therefore Lemma 1 shows that the traces \[\left\{{\rm tr}_i(c_i e_m u_i\alpha_i^{u}\Lambda(\alpha_i))\right\}_{0\le u\le s-1,\;1\le m\le p_i}\] determine \(c_i\).
From each helper node \(i_j\), where \(1\leq j\leq d\), the repair procedure downloads precisely \[\left\{\operatorname{tr}_i(c_{i_j} e_m u_{i_j})\right\}_{m=1}^{p_i},\] which are \(p_i\) symbols over \(F_i\). Since \([F_i:\mathbb{F}_{q}]=\prod_{j\ne i}p_j\) and \(\ell=[\mathbb{K}:\mathbb{F}_{q}]=s\prod_{j=1}^{n}p_j\), the total repair bandwidth, measured in \(\mathbb{F}_{q}\)-symbols, is \[d\cdot p_i\cdot [F_i:\mathbb{F}_{q}] =d\prod_{j=1}^{n}p_j =\frac{d\ell}{s} =\frac{d\ell}{d-k+1},\] which meets the cut-set bound Eq. 2 .
Remark 1. The argument above shows that the entire repair problem reduces to constructing, for each failed node \(i\), an \(F_i\)-subspace \(S_i\subseteq\mathbb{K}\) satisfying Eq. ?? . In [19], Lemma 2 provides such subspaces only under the congruence condition \(p_i\equiv 1\pmod{s}\). In Section 3, we remove this restriction by constructing the required subspaces via an explicit basis transformation technique.
3 Main results↩︎
In this section, we develop a basis-transformation technique to construct an optimal repair-enabling subspace satisfying the analogue of Eq. ?? , namely Eq. ?? under the sole condition \(p>s\).
We fix a tower of finite fields \(\mathbb{F}\subset\mathbb{E}\subset\mathbb{K}\) with \([\mathbb{E}:\mathbb{F}]=p\) and \([\mathbb{K}:\mathbb{E}]=s\), where \(p>s\). Let \(\alpha\) generate \(\mathbb{E}\) over \(\mathbb{F}\) and \(\beta\) generate \(\mathbb{K}\) over \(\mathbb{E}\). In the RS-MSR setting of Section 2.2, this tower corresponds to \(F_i\subset\mathbb{E}\subset\mathbb{K}\) with \(\alpha=\alpha_i\) for each node \(i\). As discussed in Section 2.2 (see Remark 1), the key step in optimal repair of Reed-Solomon codes is to construct an \(\mathbb{F}\)-subspace \(S\) of \(\mathbb{K}\) such that Eq. ?? holds. To this end, we introduce a technique composed of three operations—Euclidean Square Partition, Transposition, and Column Aggregation—that transform the standard monomial basis array of \(\mathbb{K}\) into a new basis array with the specified property. The \(\mathbb{F}\)-span of the first row of the transformed basis array is then exactly the desired subspace \(S\). Since all three operations are governed by the Euclidean algorithm for \((p,s)\), we fix the following notation throughout.
Write the Euclidean algorithm for \((p,s)\) as \[\label{eq:euclid} \begin{align} p &= a_0 s + b_1,\\ s &= a_1 b_1 + b_2,\\ b_1 &= a_2 b_2 + b_3,\\ &\;\vdots\\ b_{m-2} &= a_{m-1} b_{m-1} + b_m,\\ b_{m-1} &= a_m b_m, \end{align}\tag{4}\] where \(b_m=\gcd(p,s)\). Set \(\nu:=\lfloor m/2\rfloor\) and \(\nu':=\lceil m/2\rceil\).
Define \(C_0:=0\), and \[C_r:=\sum_{\mu=1}^{r} a_{2\mu}\, b_{2\mu},\quad 1\le r\le \nu.\]
Define \(Y_0:=0\), and \[Y_h:=\sum_{\gamma=1}^{h} a_{2\gamma-1}\, b_{2\gamma-1},\quad 1\le h\le \nu'.\]
For \(j\in[0,b_1-1]\), define \[\label{eq:j-iter} j^{(0)}:=j, \qquad j^{(2r)}:=j^{(2r-2)} \pmod{b_{2r}}, \quad 1\leq r\leq \nu.\tag{5}\]
We provide our main results as follows.
Theorem 3. Let \(\mathbb{F}\subset\mathbb{E}\subset\mathbb{K}\) be finite fields with \([\mathbb{E}:\mathbb{F}]=p>s=[\mathbb{K}:\mathbb{E}]\). Fix \(\alpha\in\mathbb{E}\) and \(\beta\in\mathbb{K}\) such that \(\mathbb{E}=\mathbb{F}(\alpha)\) and \(\mathbb{K}=\mathbb{E}(\beta)\). Then, there exists an \(\mathbb{F}\)-subspace \(S\) of \(\mathbb{K}\) such that \[\label{eq:smain} \dim_{\mathbb{F}} S = p \quad\text{and}\quad S + S\alpha + \dots + S\alpha^{s-1} = \mathbb{K}.\qquad{(2)}\] Furthermore, the explicit structure of \(S\) is given as follows: \[S =S^{(1)} + S^{(2)},\] where \[\begin{gather} S^{(1)} =\mathop{\mathrm{Span}}_{\mathbb{F}} \bigl(\alpha^{rs}(\alpha\beta)^{u}:\, r\in [0,a_0-1],\, u\in [0,s-1] \bigr), \\ S^{(2)} =\mathop{\mathrm{Span}}_{\mathbb{F}} \bigl(\mathcal{R}_j:\, j\in [0,b_1-1] \bigr), \end{gather}\] and for each \(j\in[0,b_1-1]\), the element \(\mathcal{R}_j\in\mathbb{K}\) is defined as follows.
If \(C_{r-1}\le j < C_r\) for some \(1\le r\le \nu\), then \[\mathcal{R}_j = \alpha^{a_0 s+j}\!\left( \sum_{h=0}^{r-1}\sum_{w=0}^{a_{2h+1}-1} \beta^{Y_h +w\,b_{2h+1}+j^{(2h)}} + \beta^{Y_r+j^{(2r)}} \right).\]
If \(C_{\nu}\le j\le b_1-1\) and \(m\) is odd, then \[\mathcal{R}_j = \alpha^{a_0s+j} \sum_{h=0}^{\nu'-1}\sum_{w=0}^{a_{2h+1}-1} \beta^{Y_h +w\,b_{2h+1}+j^{(2h)}}.\]
Corollary 1. When \(m=1\), from Theorem 3 we have that for \(j\in [0,b_1-1]\), \(\mathcal{R}_j =\alpha^{a_0s}(\alpha\beta)^j\sum_{t=0}^{a_1-1}\beta^{t b_1}\).
Proof. When \(m=1\), we have \(C_0=0\le j\le b_1-1\), so every column falls into case (2) of Theorem 3 with a single index \(h=0\) in the displayed sum. This gives the exponents \(w\,b_1+j\) for \(w=0,\dots,a_1-1\). Factoring out \(\alpha^{a_0s+j}\beta^j=\alpha^{a_0s}(\alpha\beta)^j\) yields the formula. ◻
Corollary 2. When \(m=2\), Theorem 3 gives \[\mathcal{R}_j =\alpha^{a_0s}(\alpha\beta)^j\Bigg(\sum_{w=0}^{a_1-1}\beta^{w b_1} +\beta^{a_1b_1-\left\lfloor j/b_2\right\rfloor b_2}\Bigg), \qquad j\in [0,b_1-1].\]
Proof. When \(m=2\), we have \(C_1=a_2b_2=b_1\). Since \(C_0=0\le j<C_1=b_1\), every column falls into case (1) of Theorem 3 with \(r=1\). The double sum contributes the exponents \(w\,b_1+j\) for \(w=0,\dots,a_1-1\), and the final term contributes \(a_1b_1+j^{(2)}\) where \(j^{(2)}=j\pmod {b_2}\). Factoring out \(\alpha^{a_0s}(\alpha\beta)^j\) and using \(j-j^{(2)}=\lfloor j/b_2\rfloor b_2\) yields the formula. ◻
3.1 A basis-transformation perspective↩︎
In this subsection, we formulate the basis-transformation problem. Given the standard monomial basis of \(\mathbb{K}\) arranged as a \(p\times s\) array, the goal is to transform it into an \(s\times p\) array whose rows are successive \(\alpha\)-multiples of the first row. The \(\mathbb{F}\)-span of the first row then serves as the optimal repair-enabling subspace \(S\).
We first introduce the monomial basis of \(\mathbb{K}\) over \(\mathbb{F}\). Note that \(\mathbb{K}=\mathbb{E}(\beta)\) and \(\mathbb{E}=\mathbb{F}(\alpha)\), thus \(\{\beta^u:0\le u\le s-1\}\) is an \(\mathbb{E}\)-basis of \(\mathbb{K}\) and \(\{\alpha^i:0\le i\le p-1\}\) is an \(\mathbb{F}\)-basis of \(\mathbb{E}\). Since \(\alpha\in\mathbb{E}^*\), we have \(\mathbb{E}(\alpha\beta)=\mathbb{E}(\beta)=\mathbb{K}\), so \(\{(\alpha\beta)^u:0\le u\le s-1\}\) is also an \(\mathbb{E}\)-basis of \(\mathbb{K}\). Therefore, the set \[\bigl\{ \alpha^{i}(\alpha\beta)^{j} : i=0,\dots,p-1;~ j=0,\dots,s-1 \bigr\}\] is an \(\mathbb{F}\)-basis of \(\mathbb{K}\). We arrange it as a \(p\times s\) array \(B\) (see Fig. 1), specifically, for each \((i,j)\in\mathcal{I}(p,s)\), \[\label{eq:B-def} B(i,j)=\alpha^{i}(\alpha\beta)^{j}.\tag{6}\] Accordingly, the problem of finding \(S\) satisfying Eq. ?? reduces to transforming the monomial basis array \(B\) into a new \(\mathbb{F}\)-basis that can be arranged as an \(s \times p\) array, whose rows are successive \(\alpha\)-multiples of the first row. The desired subspace \(S\) is then given by the \(\mathbb{F}\)-span of the first row (see Fig. [fig:basis1]). The target arrangement in Fig. [fig:basis1] is meaningful only when \(p>s\), because the number of successive \(\alpha\)-layers cannot exceed the dimension \(p=[\mathbb{E}:\mathbb{F}]\).
3.2 An illustrative example of the basis transformation technique↩︎
We present a basis-transformation technique that achieves the conversion described above. Before introducing the formal definitions, we illustrate the technique using the example \((p,s)=(7,5)\). Fig. 2 illustrates the entire transformation procedure for this example. The corresponding Euclidean algorithm is \(7=1\times 5+2\), \(5=2\times 2+1\), and \(2=2\times 1\). Then
Step 1. Partition \(B\) into square blocks whose side lengths are determined by the Euclidean algorithm for \((7,5)\), yielding one \(5 \times 5\) block, two \(2 \times 2\) blocks, and two \(1 \times 1\) blocks.
Step 2.1. Transpose the entire array \(B\) to obtain a \(5\times 7\) array \(B^{\top}\).
Step 2.2. Transpose each square block in \(B^{\top}\) individually. The resulting \(5\times 7\) array is denoted by \(R\).
Step 3. For each column of \(R\), we keep the \(\alpha\)-part of each entry unchanged and replace the \(\beta\)-part by the sum of all distinct powers of \(\beta\) appearing in that column. Specifically, the columns with indices \(0\) through \(4\) remain unchanged. In the column with index \(5\), the \(\beta\)-part of each entry is replaced by \(1+\beta^2+\beta^4\), and in the column with index \(6\), the \(\beta\)-part of each entry is replaced by \(\beta+\beta^3+\beta^4\). The resulting array is denoted by \(\overline{R}\).
Then the rows of \(\overline{R}\) are successive \(\alpha\)-multiples of the first row. Let \(S\) be the \(\mathbb{F}\)-subspace spanned by the first row. To verify Eq. ?? in this example, it remains to show that \[S+S\alpha+S\alpha^2+S\alpha^3+S\alpha^4=\mathbb{K}.\] Equivalently, it suffices to show that every entry of \(R\) is an \(\mathbb{F}\)-linear combination of entries of \(\overline{R}\).
The columns of \(R\) indexed by \(0,1,2,3,4\) coincide with those of \(\overline{R}\). Each entry in the columns of \(R\) with indices \(5\) and \(6\) can be expressed as an \(\mathbb{F}\)-linear combination of entries of \(\overline{R}\), as shown by the following recovery sequence.
\(R(0,5)=\alpha^5=\alpha^{5}(1+\beta^{2}+\beta^{4})-\alpha^{5}\beta^{2}-\alpha^{5}\beta^{4}=\overline{R}(0,5)-\overline{R}(3,2)-\overline{R}(1,4)\),
\(R(1,5)=\alpha^6=\alpha^{6}(1+\beta^{2}+\beta^{4})-\alpha^{6}\beta^{2}-\alpha^{6}\beta^{4}=\overline{R}(1,5)-\overline{R}(4,2)-\overline{R}(2,4)\),
\(R(2,5)=\alpha^7\beta^2=\alpha^{7}(1+\beta^{2}+\beta^{4})-\alpha^7-\alpha^7\beta^{4}=\overline{R}(2,5)-\alpha^7-\overline{R}(3,4)\),
\(R(3,5)=\alpha^8\beta^2=\alpha^{8}(1+\beta^{2}+\beta^{4})-\alpha^{8}-\alpha^{8}\beta^{4}=\overline{R}(3,5)-\alpha^8-\overline{R}(4,4)\),
\(R(4,5)=\alpha^9\beta^4=\alpha^{9}(1+\beta^{2}+\beta^{4})-\alpha^{9}-\alpha^{9}\beta^{2}=\overline{R}(4,5)-\alpha^9-\alpha^9\beta^2\),
\(R(0,6)=\alpha^6\beta=\alpha^{6}(\beta+\beta^{3}+\beta^{4})-\alpha^{6}\beta^{3}-\alpha^{6}\beta^{4}=\overline{R}(0,6)-\overline{R}(3,3)-\overline{R}(2,4)\),
\(R(1,6)=\alpha^7\beta=\alpha^{7}(\beta+\beta^{3}+\beta^{4})-\alpha^{7}\beta^{3}-\alpha^{7}\beta^{4}=\overline{R}(1,6)-\overline{R}(4,3)-\overline{R}(3,4)\),
\(R(2,6)=\alpha^8\beta^3=\alpha^{8}(\beta+\beta^{3}+\beta^{4})-\alpha^{8}\beta-\alpha^{8}\beta^{4}=\overline{R}(2,6)-\alpha^8\beta-\overline{R}(4,4)\),
\(R(3,6)=\alpha^9\beta^3=\alpha^{9}(\beta+\beta^{3}+\beta^{4})-\alpha^{9}\beta-\alpha^{9}\beta^{4}=\overline{R}(3,6)-\alpha^9\beta-R(4,5)\),
\(R(4,6)=\alpha^{10}\beta^4=\alpha^{10}(\beta+\beta^{3}+\beta^{4})-\alpha^{10}\beta-\alpha^{10}\beta^{3}=\overline{R}(4,6)-\alpha^{10}\beta-\alpha^{10}\beta^3\).
Thus \(R(0,5), R(1,5), R(0,6), R(1,6)\) are already \(\mathbb{F}\)-linear combinations of entries of \(\overline{R}\). For the remaining terms, note that \([\mathbb{F}(\alpha):\mathbb{F}]=p=7\), hence \(\mathbb{F}(\alpha)=\mathop{\mathrm{Span}}_{\mathbb{F}}\{1, \alpha, \cdots, \alpha^6\}\). In particular, \[\begin{align} \alpha^7,\alpha^8,\alpha^9 &\in \mathop{\mathrm{Span}}_{\mathbb{F}}\{1,\alpha,\cdots,\alpha^6\} = \mathop{\mathrm{Span}}_{\mathbb{F}}\bigl(\{\overline{R}(t,0):0\le t\le 4\}\cup\{R(0,5),R(1,5)\}\bigr),\\ \alpha^9\beta^2 &\in \mathop{\mathrm{Span}}_{\mathbb{F}}\{\alpha^2\beta^2,\alpha^3\beta^2,\cdots,\alpha^8\beta^2\} = \mathop{\mathrm{Span}}_{\mathbb{F}}\bigl(\{\overline{R}(t,2):0\le t\le 4\}\cup\{R(2,5),R(3,5)\}\bigr),\\ \alpha^8\beta,\alpha^9\beta,\alpha^{10}\beta &\in \mathop{\mathrm{Span}}_{\mathbb{F}}\{\alpha\beta,\alpha^2\beta,\cdots,\alpha^7\beta\} = \mathop{\mathrm{Span}}_{\mathbb{F}}\bigl(\{\overline{R}(t,1):0\le t\le 4\}\cup\{R(0,6),R(1,6)\}\bigr),\\ \alpha^{10}\beta^3 &\in \mathop{\mathrm{Span}}_{\mathbb{F}}\{\alpha^3\beta^3,\alpha^4\beta^3,\cdots,\alpha^9\beta^3\} = \mathop{\mathrm{Span}}_{\mathbb{F}}\bigl(\{\overline{R}(t,3):0\le t\le 4\}\cup\{R(2,6),R(3,6)\}\bigr). \end{align}\] Therefore every entry of \(R\) is an \(\mathbb{F}\)-linear combination of entries of \(\overline{R}\). The recovery above illustrates the general mechanism: each interference monomial subtracted from an entry of \(\overline{R}\) either lies in an already established \(\beta^{\theta}\)-layer (i.e.\(\beta^\theta \mathbb{E}\) for some integer \(\theta\)) or equals an entry recovered at an earlier step.
Next, we give formal definitions of the basis transformation technique.
3.3 Formal definition of the basis transformation technique↩︎
We now define the basis-transformation technique, which consists of three operations: Euclidean Square Partition, Transposition, and Column Aggregation.
3.3.0.1 Euclidean Square Partition
Partition the array \(B\) into square blocks whose side lengths are determined by the Euclidean algorithm for \((p,s)\).
Definition 1 (Euclidean Square Partition). Let \(h,w\) be positive integers and consider the rectangle \(\mathcal{I}(h,w)=[0,h-1]\times[0,w-1]\). Let \(t:=\min\{h,w\}\). Tile \(\mathcal{I}(h,w)\) by placing as many \(t\times t\) squares as possible along the longer side (left-to-right if \(w\ge h\), and top-to-bottom if \(h>w\)). This leaves a (possibly empty) residual rectangle \(\mathcal{I}(h',w')\); if it is nonempty, apply the same procedure recursively to \(\mathcal{I}(h',w')\). The resulting collection of squares forms a disjoint partition of \(\mathcal{I}(h,w)\), called the Euclidean Square Partition* of \(\mathcal{I}(h,w)\), and is denoted by \(\mathcal{P}(h,w)\). Each square in \(\mathcal{P}(h,w)\) is called a Euclidean square.*
Applying the above procedure to the index set of the basis array \(B\) defined as in Fig. 1, namely for \((h,w)=(p,s)\), yields a partition of \(B\) into squares whose side lengths are given by the multiset \[\Big\{\underbrace{s,\dots,s}_{a_0},\underbrace{b_1,\dots,b_1}_{a_1},\dots, \underbrace{b_m,\dots,b_m}_{a_m}\Big\},\] as induced by the Euclidean chain Eq. 4 .
3.3.0.2 Transposition
We introduce the Transposition operation on \(B\), which converts \(B\) into an \(s\times p\) array \(R\) by an overall transpose followed by a block-wise transpose.
Definition 2 (Transposition). Let \(B\) be the \(p\times s\) array defined as in Fig. 1 and let \(B^{\top}\) be the \(s\times p\) array defined by \(B^{\top}(i,j)=B(j,i)\). For each Euclidean square \(Q\) in \(B\) with top-left corner index \((x,y)\) and side length \(t\), let \(Q^{\top}\) be the corresponding \(t\times t\) square in \(B^{\top}\) with top-left corner index \((y,x)\). Define \(R=\mathsf{Trans}_{p,s}(B)\) as the array obtained from \(B^{\top}\) by transposing every square \(Q^{\top}\), equivalently, for every such \(Q\) and all \(0\le u,v\le t-1\), \[\label{eq:blockwise} R(y+u,\;x+v)=B(x+u,\;y+v).\qquad{(3)}\]
3.3.0.3 Column Aggregation
For each column of \(R\), we keep the \(\alpha\) part of each entry unchanged and replace the \(\beta\) part by the sum of all distinct \(\beta\)-powers appearing in that column.
Definition 3. Since every entry of \(R\) is a monomial in \(\alpha\) and \(\beta\), for \((i,j)\in \mathcal{I}(s,p)\) we write \[R(i,j) = \alpha^{\gamma(i,j)}\,\beta^{\tau(i,j)},\] where \(\gamma(i,j)\) and \(\tau(i,j)\) denote the exponents of \(\alpha\) and \(\beta\) in \(R(i,j)\), respectively.
Definition 4 (Column Aggregation). For a column \(c\) of \(R\), the column aggregation* operator \(\mathrm{Agg}(\cdot)\) replaces each entry \(R(i,c)\) by \[\mathrm{Agg}(R(i,c)) := \alpha^{\gamma(i,c)} \!\!\sum_{\theta\,\in\, \{\tau(i',c)\,:\,i'\in[0,s-1]\}} \!\!\beta^{\theta}.\] Applying \(\mathrm{Agg}(\cdot)\) to each column of \(R\) yields the \(s\times p\) array \(\overline{R}\).*
Example 1. In Fig. 2 with \((p,s)=(7,5)\), column \(5\) of \(R\) consists of entries \[\alpha^5,\;\alpha^6,\;\alpha^7\beta^2,\;\alpha^8\beta^2,\;\alpha^9\beta^4.\] Column aggregation replaces each entry by \[\alpha^5(1+\beta^2+\beta^4),\;\alpha^6(1+\beta^2+\beta^4),\;\dots,\; \alpha^9(1+\beta^2+\beta^4),\] as shown in the bottom array \(\overline{R}\) of Fig. 2.
Define the subspace \[\label{eq:S-def} S:=\mathop{\mathrm{Span}}_{\mathbb{F}}\{\overline{R}(0,c):\,0\le c\le p-1\},\tag{7}\] and we verify in Section 3.5 that \(S\) satisfies Eq. ?? .
3.4 Structure of the transposed array \(R\)↩︎
In this subsection, we characterize the properties of the transposed array \(R\) defined as in Definition 2 that will be used for the proof of Theorem 3.
We begin by recording two basic properties that follow directly from the definitions of \(R\) and \(B\) and will be used throughout.
Observation 1 (Structural properties of \(R\)). The transposed array \(R\) has the following properties:
The Euclidean Square Partition \(\mathcal{P}(p,s)\) of \(B\) induces a Euclidean Square Partition \(\mathcal{P}(s,p)\) of \(R\); the Euclidean square of \(B\) with top-left corner index \((x,y)\) becomes the Euclidean square of \(R\) whose top-left entry is \(R(y,x)=B(x,y)=\alpha^x(\alpha\beta)^y\).
Inside each Euclidean square of \(R\), the entry immediately to the right of any given entry is obtained by multiplying that entry by \(\alpha\beta\), while the entry immediately below it is obtained by multiplying that entry by \(\alpha\).
The preceding observations allow us to determine the \(\alpha\) and \(\beta\)-exponents of each entry of \(R\).
Lemma 3. Let \((i,j)\in \mathcal{I}(s,p)\) and \(Q=[\rho,\rho+\lambda-1]\times[\kappa,\kappa+\lambda-1]\) be the Euclidean square of \(\mathcal{P}(s,p)\) containing \((i,j)\). Then
\(\gamma(i,j)=i+j\).
\(\tau(i,j)=\rho+(j-\kappa).\)
In particular, \(\tau(i,j)\in [0,s-1]\).
Proof. Assume that \[i=\rho+r,\qquad j=\kappa+c,\] where \(0\le r,c\le \lambda-1\). By Observation 1(1), \[R(\rho,\kappa)=\alpha^{\rho+\kappa}\beta^\rho.\] By Observation 1(2), \[R(i,j)=R(\rho+r,\kappa+c) =\alpha^{\rho+\kappa}\beta^\rho\cdot \alpha^r(\alpha\beta)^c =\alpha^{\rho+\kappa+r+c}\beta^{\rho+c} =\alpha^{i+j}\beta^{\rho+(j-\kappa)}.\] Hence \[\gamma(i,j)=i+j, \qquad \tau(i,j)=\rho+(j-\kappa).\] Finally, since \(0\le \rho\le s-\lambda\) and \(0\le j-\kappa=c\le \lambda-1\), we obtain \[0\le \tau(i,j)=\rho+(j-\kappa)\le (s-\lambda)+(\lambda-1)=s-1.\] This completes the proof. ◻
From Lemma 3, we obtain the following proposition.
Proposition 1. Let \(R\) be the transposed array defined as in Definition 2. Then the following statements hold.
The \(\alpha\)-exponent is consecutive along every column of \(R\).
The \(\beta\)-exponent is constant along every column of each Euclidean square of \(R\).
The operator \(\mathrm{Agg}(\cdot)\) acts as the identity on the first \(a_0s\) columns of \(R\).
In each column of \(R\), entries in lower squares, if any, have larger \(\beta\)-exponents.
Proof. (1) By Lemma 3 (1), for any \((i,j)\in \mathcal{I}(s,p)\), the \(\alpha\)-exponent of \(R(i,j)\) is \(\gamma(i,j)=i+j\). Therefore, within any fixed column \(j\), the \(\alpha\)-exponents are consecutive.
(2) Let \[Q=[\rho,\rho+\lambda-1]\times[\kappa,\kappa+\lambda-1]\] be a Euclidean square of \(\mathcal{P}(s,p)\). By Lemma 3(2), for every \((i,j)\in Q\), \[\tau(i,j)=\rho+(j-\kappa).\] Hence \(\tau(i,j)\) depends only on the column index \(j\), so the \(\beta\)-exponent is constant along every column of \(Q\).
(3) Each of the first \(a_0s\) columns of \(R\) is contained in a single \(s\times s\) block induced by \(\mathcal{P}(p,s)\). By Part (2), the \(\beta\)-exponent is constant along every such column. Hence the set of \(\beta\)-components is a singleton for each of these columns, so \(\mathrm{Agg}(\cdot)\) acts as the identity on them.
(4) By Part (3), it is enough to consider the last \(b_1\) columns of \(R\). Fix a column \(j\in[a_0s,p-1]\). Let \[Q_{\mathrm{up}}=[\rho_{\mathrm{up}},\rho_{\mathrm{up}}+\lambda_{\mathrm{up}}-1]\times[\kappa_{\mathrm{up}},\kappa_{\mathrm{up}}+\lambda_{\mathrm{up}}-1]\] and \[Q_{\mathrm{low}}=[\rho_{\mathrm{low}},\rho_{\mathrm{low}}+\lambda_{\mathrm{low}}-1]\times[\kappa_{\mathrm{low}},\kappa_{\mathrm{low}}+\lambda_{\mathrm{low}}-1]\] be two squares of \(\mathcal{P}(s,p)\) crossed by column \(j\), with \(Q_{\mathrm{low}}\) strictly below \(Q_{\mathrm{up}}\). By Lemma 3 (2), the \(\beta\)-exponent in column \(j\) contributed by \(Q_{\mathrm{up}}\) is at most \[\rho_{\mathrm{up}}+\lambda_{\mathrm{up}}-1,\] while the \(\beta\)-exponent possessed by column \(j\) in \(Q_{\mathrm{low}}\) is at least \[\rho_{\mathrm{low}}.\] Since \(Q_{\mathrm{low}}\) lies strictly below \(Q_{\mathrm{up}}\), we have \[\rho_{\mathrm{up}}+\lambda_{\mathrm{up}}-1<\rho_{\mathrm{low}}.\] Therefore, in any column \(j\), the \(\beta\)-exponent possessed by \(Q_{\mathrm{low}}\) is strictly larger than that possessed by \(Q_{\mathrm{up}}\). ◻
3.5 Proof of Theorem 3↩︎
Recall that, by Eq. 7 , \(S\) is the \(\mathbb{F}\)-linear span of the first row of \(\overline{R}\), where \(R\) denotes the transposed array and \(\overline{R}\) denotes the array obtained from \(R\) by column aggregation. The explicit description of \(S\) stated in Theorem 3 is derived in Appendix 5. In this subsection, we prove the first assertion of Theorem 3, namely, \[\dim_{\mathbb{F}} S=p, \qquad \mathbb{K}=\sum_{u=0}^{s-1}\alpha^u S .\]
Since \(\mathrm{Agg}(\cdot)\) does not change the \(\alpha\)-exponents, Proposition 1 (1) implies that the entries in each column of \(\overline{R}\) have consecutive \(\alpha\)-powers. Hence, the \(u\)-th row of \(\overline{R}\) is equal to \(\alpha^u\) times the first row, i.e. \(\overline{R}(u,v)=\alpha^u\overline{R}(0,v)\) for any \((u,v)\in\mathcal{I}(s,p)\). Set \[\label{eq:K} K:=\sum_{u=0}^{s-1}\alpha^u S =\mathop{\mathrm{Span}}_{\mathbb{F}}\{\overline{R}(u,v):(u,v)\in\mathcal{I}(s,p)\}.\tag{8}\]
We first prove that \(K=\mathbb{K}\). Note that \(K \subseteq \mathbb{K}\) since every entry of \(\overline{R}\) is a sum of monomials in \(\mathbb{K}\). Moreover, since \(R\) is a rearrangement of the basis array \(B\), we have \[\mathop{\mathrm{Span}}_{\mathbb{F}}(R)=\mathop{\mathrm{Span}}_{\mathbb{F}}(B)=\mathbb{K}.\] Therefore, to prove \(\mathbb{K}\subseteq K\), it is enough to show that every entry of \(R\) lies in \(K\).
By Proposition 1(3), the operator \(\mathrm{Agg}(\cdot)\) acts as the identity on the first \(a_0s\) columns of \(R\). Hence, all entries in these columns already belong to \(K\). It remains to consider the last \(b_1\) columns. Define \[R_1:=\bigl(R(i,a_0s+j)\bigr)_{(i,j)\in\mathcal{I}(s,b_1)},\] that is, \(R_1\) is the \(s\times b_1\) subarray formed by the last \(b_1\) columns of \(R\). We use \((i,j)\in\mathcal{I}(s,b_1)\) as local coordinates on \(R_1\) via the identification \[R_1(i,j)\longleftrightarrow R(i,a_0s+j).\] For \(j\in[0,b_1-1]\), define \[\mathsf{Exp}(j):=\{t\in[0,s-1]:\beta^t \text{ appears in column }a_0s+j\text{ of }R\},\] and, for \((i,j)\in\mathcal{I}(s,b_1)\), set \[t_{i,j}:=\tau(i,a_0s+j).\] Thus \(\mathsf{Exp}(j)\) is the set of \(\beta\)-exponents occurring in the local column \(j\), and \(t_{i,j}\) is the \(\beta\)-exponent of the target entry \(R(i,a_0s+j)\). We shall prove \[\label{eq:goal} R(i,a_0s+j)\in K, \qquad(i,j)\in\mathcal{I}(s,b_1).\tag{9}\]
For every \((i,j)\in\mathcal{I}(s,b_1)\), column aggregation gives \[\label{eq:recover} R(i,a_0s+j) = \overline{R}(i,a_0s+j) - \alpha^{a_0s+i+j} \sum_{t\in\mathsf{Exp}(j)\setminus\{t_{i,j}\}}\beta^t,\tag{10}\] and, by Eq. 8 , we have \[\label{eq:AggSum} \overline{R}(i,a_0s+j)\in K.\tag{11}\] Therefore, to prove Eq. 9 , it suffices to show that the interference monomial \[M_t(i,j):=\alpha^{a_0s+i+j}\beta^t\in K\] for every \(t\in\mathsf{Exp}(j)\setminus\{t_{i,j}\}\).
We split the interference exponents \(t\in\mathsf{Exp}(j)\setminus\{t_{i,j}\}\) into the following three cases: \[\begin{array}{ll} \mathrm{(C1)} & i+j<t,\\[1mm] \mathrm{(C2)} & i+j\ge t \text{ and } t<t_{i,j},\\[1mm] \mathrm{(C3)} & i+j\ge t \text{ and } t>t_{i,j}. \end{array}\] These cases are pairwise disjoint and exhaustive. Indeed, if (C1) does not hold, then \(i+j\ge t\). Since \(t\ne t_{i,j}\), either \(t<t_{i,j}\) or \(t>t_{i,j}\).
The three cases are handled by different mechanisms. Case (C1) is direct. Case (C2) will be handled by proving that the whole \(\mathbb{E}\beta^t\)-layer is contained in \(K\). Case (C3) will be handled by proving that the required monomial \(M_t(i,j)\) is obtained from a predecessor with respect to an order to be defined on \(\mathcal{I}(s,b_1)\).
We also record that the condition \(i+j\ge t\) in Case (C2) is automatic. Fix \(t\in\mathsf{Exp}(j)\setminus\{t_{i,j}\}\) with \(t<t_{i,j}\). Let \[Q=[\rho,\rho+\lambda-1]\times[\kappa,\kappa+\lambda-1]\] be the Euclidean square of \(\mathcal{P}(s,b_1)\) whose entries lying in the local column \(j\) have \(\beta\)-exponent \(t\). Then, Lemma 3(2) implies \[t=\rho+(j-\kappa).\] By Proposition 1(4), the unique Euclidean square containing \((i,j)\) lies strictly below \(Q\). Hence \(i\ge \rho+\lambda\). Since \(j\ge\kappa\), we have \[i+j-t=i-\rho+\kappa\ge \lambda+\kappa\ge 1.\] Thus \(i+j>t\). Therefore, in the proof of Case (C2), it suffices to use the condition \(t<t_{i,j}\).
The following lemma supplies the direct argument for Case (C1).
Lemma 4. For all \(0\le u\le a_0s-1\) and \(0\le \theta\le s-1\), \[\alpha^u(\alpha\beta)^\theta\in K.\]
Proof. By Proposition 1(3) and Lemma 3, for \(0\le r\le a_0-1\) and \(0\le \theta\le s-1\), we have \[\overline{R}(0,rs+\theta)=R(0,rs+\theta)=\alpha^{rs}(\alpha\beta)^\theta\in S\subseteq K.\] Multiplying by \(\alpha^v\), \(0\le v\le s-1\), Eq. 8 implies \[\alpha^{rs+v}(\alpha\beta)^\theta\in K,\] which means \(\alpha^u(\alpha\beta)^\theta\in K\) for all \(0\le u\le a_0s-1\) and \(0\le \theta\le s-1\). ◻
We now apply Lemma 4 to Case (C1). If \(i+j<t\), then \[0\le a_0s+i+j-t\le a_0s-1.\] Applying Lemma 4 with \(u=a_0s+i+j-t\) and \(\theta=t\), we obtain \[\label{eq:c1} M_t(i,j) =\alpha^{a_0s+i+j}\beta^t =\alpha^{a_0s+i+j-t}(\alpha\beta)^t \in K .\tag{12}\]
The next lemma is used for the proof of Case (C2). In this case, we recover not only the monomial \(M_t(i,j)\), but the entire \(\mathbb{E}\beta^t\)-layer.
Lemma 5. Let \(\theta\in[0,s-1]\). If there exists \(z\in\mathbb{Z}\) such that \[\alpha^z\beta^\theta,\;\alpha^{z+1}\beta^\theta,\;\dots,\;\alpha^{z+p-1}\beta^\theta\in K,\] then \(\mathbb{E}\beta^\theta\subseteq K\).
Proof. Since \([\mathbb{E}:\mathbb{F}]=p\) and \(\alpha\) generates \(\mathbb{E}\) over \(\mathbb{F}\), the \(p\) consecutive powers \[\alpha^z,\alpha^{z+1},\dots,\alpha^{z+p-1}\] form an \(\mathbb{F}\)-basis of \(\mathbb{E}\). Hence \[\mathop{\mathrm{Span}}_{\mathbb{F}}\{\alpha^z\beta^\theta,\alpha^{z+1}\beta^\theta,\dots,\alpha^{z+p-1}\beta^\theta\} = \mathbb{E}\beta^\theta \subseteq K.\] ◻
The remaining arguments take place inside \(R_1\). We first identify the partition induced on this subarray.
Lemma 6 (Partition of \(R_1\)). The Euclidean squares induced on the subarray \(R_1\) are exactly the Euclidean Square Partition \(\mathcal{P}(s,b_1)\) on its local index set \(\mathcal{I}(s,b_1)\).
Proof. The transpose \((x,y)\mapsto (y,x)\) maps \(\mathcal{P}(p,s)\) onto \(\mathcal{P}(s,p)\). The Transposition operation transposes each square without changing the partition, so \(R\) is partitioned by \(\mathcal{P}(s,p)\). Removing the first \(a_0s\) columns leaves the rectangle \([0,s-1]\times[a_0s,p-1]\), namely the subarray \(R_1\); after reindexing its columns by \(j\mapsto j-a_0s\), its local index set becomes \(\mathcal{I}(s,b_1)=[0,s-1]\times[0,b_1-1]\). By Definition 1, the induced partition on this local index set is exactly \(\mathcal{P}(s,b_1)\). ◻
We next introduce the locating map.
Definition 5 (Locating map). Given \(\theta\in[0,s-1]\) and \(\xi\in[0,b_1-1]\), define \[\operatorname{Loc}(\theta, \xi):=(i_{\theta,\xi},j_{\theta,\xi})\in \mathcal{I}(s,b_1)\] as the local coordinates of the entry of \(R_1\) such that \(R(i_{\theta,\xi},a_0s+j_{\theta,\xi})=\alpha^{a_0s+\theta+\xi}\beta^\theta\).
By Eq. 6 , \(\alpha^{a_0s+\theta+\xi}\beta^\theta = B(a_0s+\xi,\,\theta)\), which lies in row \(a_0s+\xi\ge a_0s\) of \(B\), hence in the last \(b_1\) rows. By Eq. ?? , every entry in rows \([a_0s,p-1]\) of \(B\) is mapped by the Transposition to a column \(\ge a_0s\) in \(R\), so this monomial appears as an entry of \(R_1\). Since \(R\) is a rearrangement of the \(\mathbb{F}\)-basis \(B\), its entries are pairwise distinct, so the position is unique. Hence \(\operatorname{Loc}(\theta,\xi)\) is well-defined.
Lemma 7. Given \(\theta\in[0,s-1]\) and \(\xi\in[0,b_1-1]\), let \[Q_{\theta,\xi}=[\rho,\rho+\lambda-1]\times[\kappa,\kappa+\lambda-1]\in \mathcal{P}(s,b_1)\] be the unique square of \(\mathcal{P}(s,b_1)\) containing \((\theta,\xi)\) (ensured by Lemma 6). Let \(\operatorname{Loc}(\theta, \xi) =(i_{\theta,\xi},j_{\theta,\xi})\) be defined as in Definition 5. Then \[\label{eq:locsquare} (i_{\theta,\xi},j_{\theta,\xi}) = \bigl(\rho+(\xi-\kappa),\;\kappa+(\theta-\rho)\bigr)\in Q_{\theta,\xi}.\qquad{(4)}\]
Proof. By Lemma 3(1), \[\gamma(\rho+(\xi-\kappa),a_0s+\kappa+(\theta-\rho)) = a_0s+\theta+\xi.\] By Lemma 3(2), \[\tau(\rho+(\xi-\kappa),a_0s+\kappa+(\theta-\rho)) = \rho+\bigl(\kappa+(\theta-\rho)-\kappa\bigr) = \rho+(\theta-\rho) = \theta.\] Therefore, \[R(i_{\theta,\xi},a_0s+j_{\theta,\xi}) = \alpha^{a_0s+\theta+\xi}\beta^\theta =R(\rho+(\xi-\kappa),a_0s+\kappa+(\theta-\rho)).\] Since all entries of \(R_1\) are pairwise distinct, we have \((i_{\theta,\xi},j_{\theta,\xi}) = \bigl(\rho+(\xi-\kappa),\;\kappa+(\theta-\rho)\bigr)\).
Moreover, as \((\theta,\xi)\in Q_{\theta,\xi}\) and both \(\theta-\rho\) and \(\xi-\kappa\) belong to \([0,\lambda-1]\), it follows that \((i_{\theta,\xi},j_{\theta,\xi})\in Q_{\theta,\xi}\). ◻
Cases (C2) and (C3) will require induction. The induction is taken with respect to the column-major lexicographic order on \(\mathcal{I}(s,b_1)\), defined by \[(i',j')\prec(i,j) \quad\Longleftrightarrow\quad j'<j,\;\text{or}\;j'=j\;\text{and}\;i'<i.\] Both indices are bounded, so \(\prec\) is a well-order on \(\mathcal{I}(s,b_1)\).
The next two lemmas are crucial for the case analysis in the inductive step. Lemma 8 handles Case (C2) \(t<t_{i,j}\), and Lemma 9 handles Case (C3): \(t>t_{i,j}\) with \(i+j\ge t\). Their proofs are deferred to Appendix 6.
Lemma 8. Fix \((i,j)\in\mathcal{I}(s,b_1)\). If \(t\in\mathsf{Exp}(j)\) satisfies \(t<t_{i,j}\), then for every \(\xi\in[0,b_1-1]\), \[\operatorname{Loc}(t, \xi)=(i_{t,\xi},j_{t,\xi})\prec(i,j).\]
Lemma 9. Fix \((i,j)\in\mathcal{I}(s,b_1)\). If \(t\in\mathsf{Exp}(j)\) satisfies \(t>t_{i,j}\) and \(i+j\ge t\), and if we set \[\delta:=i+j-t,\] then \[0\le \delta\le b_1-1,\] and \[\operatorname{Loc}(t,\delta)=(i_{t,\delta},j_{t,\delta})\prec(i,j).\]
We now prove Eq. 9 by induction on \(\prec\).
3.5.0.1 Initial segment
We first prove Eq. 9 for \[(i,0),\qquad 0\le i\le b_1-1.\] Each such point lies in the top \(b_1\times b_1\) square of \(R_1\), whose corresponding index set in \(R\) is \[[0,b_1-1]\times [a_0s,p-1].\] Hence Lemma 3(2) gives \[t_{i,0}=\tau(i,a_0s)=0+(a_0s-a_0s)=0.\] Every exponent \[t\in \mathsf{Exp}(0)\setminus\{0\}\] is contributed by a Euclidean square of \(\mathcal{P}(s,b_1)\) that is strictly below the top \(b_1\times b_1\) square. Let this square be \[Q=[\rho,\rho+\lambda-1]\times[\kappa,\kappa+\lambda-1].\] Since \(Q\) is crossed by the local column \(0\), we must have \(\kappa=0\). Moreover, because \(Q\) is strictly below the top square, \(\rho\ge b_1\). By Lemma 3(2), the exponent contributed by \(Q\) to the local column \(0\) is \[t=\rho+(a_0s+0)-(a_0s+\kappa)=\rho\ge b_1.\] Thus, for \(0\le i\le b_1-1\), we have \[i+0\le b_1-1<t.\] Therefore Case (C1) applies. By Eq. 12 , we have \(M_t(i,0)\in K\), and Eq. 10 then shows that the corresponding entry \(R(i,a_0s)\) belongs to \(K\).
3.5.0.2 Inductive step
Now fix \((i,j)\in\mathcal{I}(s,b_1)\), and assume that \[R(i',a_0s+j')\in K \qquad \text{for all }(i',j')\prec(i,j).\] We show that \(R(i,a_0s+j)\in K\). By Eqs. 10 and 11 , it remains to prove that \[M_t(i,j)=\alpha^{a_0s+i+j}\beta^t\in K\] for every \(t\in\mathsf{Exp}(j)\setminus\{t_{i,j}\}\).
We distinguish the three cases for \(t\in\mathsf{Exp}(j)\setminus\{t_{i,j}\}\).
\(i+j<t\). By Eq. 12 , \(M_t(i,j)\in K\).
\(i+j\ge t\) and \(t<t_{i,j}\). Lemma 4 gives \[\alpha^t\beta^t,\;\alpha^{t+1}\beta^t,\;\dots,\;\alpha^{t+a_0s-1}\beta^t\in K.\] For each \(\xi\in[0,b_1-1]\), by Lemma 8, we have \((i_{t,\xi},j_{t,\xi})\prec(i,j)\), so the induction hypothesis gives \(R(i_{t,\xi},a_0s+j_{t,\xi})\in K\). Lemma 7 then yields \[R(i_{t,\xi},a_0s+j_{t,\xi}) = \alpha^{a_0s+t+\xi}\beta^t \in K, \qquad 0\le \xi\le b_1-1.\] Therefore \(K\) contains the \(p=a_0s+b_1\) consecutive elements \[\alpha^t\beta^t,\;\alpha^{t+1}\beta^t,\;\dots,\;\alpha^{t+p-1}\beta^t.\] Lemma 5 implies \(\mathbb{E}\beta^t\subseteq K\). Since \(\alpha^{a_0s+i+j}\in\mathbb{E}\), we obtain \[M_t(i,j)=\alpha^{a_0s+i+j}\beta^t\in K.\]
\(i+j\ge t\) and \(t>t_{i,j}\). Set \(\delta:=i+j-t\). By Lemma 9, we have \[\delta\in[0,b_1-1] \qquad\text{and}\qquad (i_{t,\delta},j_{t,\delta}):=\operatorname{Loc}(t,\delta)\prec(i,j).\] By the induction hypothesis, \(R(i_{t,\delta},a_0s+j_{t,\delta})\in K\). Lemma 7 gives \[R(i_{t,\delta},a_0s+j_{t,\delta}) = \alpha^{a_0s+t+\delta}\beta^t = \alpha^{a_0s+i+j}\beta^t.\] Hence \(M_t(i,j)=\alpha^{a_0s+i+j}\beta^t\in K\).
We have proved that every term in the summation on the right-hand side of Eq. 10 belongs to \(K\). Since \(\overline{R}(i,a_0s+j)\in K\) by Eq. 11 , it follows that \(R(i,a_0s+j)\in K\). The induction is complete, so Eq. 9 holds for all \((i,j)\in\mathcal{I}(s,b_1)\). Combined with the fact that the first \(a_0s\) columns of \(R\) are already in \(K\) (Proposition 1(3)), every entry of \(R\) lies in \(K\). Hence \[\mathbb{K}=\mathop{\mathrm{Span}}_{\mathbb{F}}(R)\subseteq K.\] Because \(K\subseteq \mathbb{K}\) by definition, we obtain \(K=\mathbb{K}\). Thus \[\mathbb{K}=\sum_{u=0}^{s-1}\alpha^u S.\]
Finally, \(S\) is spanned by the \(p\) elements \(\overline{R}(0,0),\dots,\overline{R}(0,p-1)\), so \(\dim_{\mathbb{F}}S\le p\). On the other hand, \[sp=\dim_{\mathbb{F}}\mathbb{K} =\dim_{\mathbb{F}}K \le \sum_{u=0}^{s-1}\dim_{\mathbb{F}}(\alpha^uS) = s\dim_{\mathbb{F}}S \le sp.\] Hence \(\dim_{\mathbb{F}}S=p\). This finishes the proof of Eq. ?? .
3.6 Application to the optimal repair of Reed-Solomon codes↩︎
Theorem 3 supplies the optimal repair-enabling subspaces needed in the TYB construction without the congruence condition \(p_i\equiv1\pmod{s}\).
Theorem 4. Let \(k,n,d\) be positive integers such that \(k< d \le n-1\), and set \(s:=d+1-k\). Given a finite field \(\mathbb{F}_{q}\), let \(p_1,\dots,p_n\) be any distinct primes with \(p_i>s\) for all \(i\). Choose elements \(\alpha_1,\dots,\alpha_n\) such that \([\mathbb{F}_{q}(\alpha_i):\mathbb{F}_{q}]=p_i\) for \(i=1,\dots,n\), and set \[\mathbb{E}:=\mathbb{F}_{q}(\alpha_1,\dots,\alpha_n).\] Let \(\mathbb{K}\) be an extension field of \(\mathbb{E}\) such that \([\mathbb{K}:\mathbb{E}]=s\), and let \(\Omega=\{\alpha_1,\dots,\alpha_n\}\subseteq \mathbb{E}\). Then the code \(\mathcal{C}:=\mathrm{RS}_{\mathbb{K}}(n,k,\Omega)\), viewed as an array code over \(\mathbb{F}_{q}\) via the extension \(\mathbb{K}/\mathbb{F}_{q}\), is an \((n,k)\) MSR code with repair degree \(d\) and subpacketization \(\ell=s\prod_{i=1}^{n}p_i\).
Proof. Fix a failed node \(i\in[n]\) and a helper set \(\mathcal{H}\subseteq[n]\setminus\{i\}\) with \(|\mathcal{H}|=d\). By the repair argument in Section 2.2, it is enough to construct an \(F_i\)-subspace \(S_i\subseteq\mathbb{K}\) satisfying Eq. ?? , where \(F_i=\mathbb{F}_{q}(\{\alpha_j:j\neq i\})\). Applying Theorem 3 to the tower \(F_i\subset \mathbb{E}\subset\mathbb{K}\) with \(\alpha=\alpha_i\) (noting \([\mathbb{E}:F_i]=p_i>s=[\mathbb{K}:\mathbb{E}]\)), we obtain an \(F_i\)-subspace \(S_i\subseteq\mathbb{K}\) with \[\dim_{F_i}(S_i)=p_i,\qquad \mathbb{K}=\sum_{u=0}^{s-1}\alpha_i^u S_i.\] Substituting \(S_i\) into the repair argument, each helper node in \(\mathcal{H}\) transmits \(p_i\) symbols over \(F_i\). Since \([F_i:\mathbb{F}_{q}]=\prod_{j\neq i}p_j\), the total repair bandwidth measured in \(\mathbb{F}_{q}\)-symbols is \[d\cdot p_i\cdot[F_i:\mathbb{F}_{q}] =d\prod_{j=1}^n p_j =\frac{d}{s}\cdot s\prod_{j=1}^n p_j =\frac{d\ell}{d-k+1},\] which meets the cut-set bound Eq. 2 . ◻
Remark 4. To minimize the subpacketization, one takes \(p_1,\dots,p_n\) to be the \(n\) smallest primes greater than \(s\).
Proposition 2 (Asymptotic comparison with [19] for fixed \(s\)). Fix \(s\ge 3\). Let \(p_i\) denote the \(i\)-th smallest prime greater than \(s\), and let \(p_i^{\prime}\) denote the \(i\)-th smallest prime satisfying \(p_i^{\prime} \equiv 1 \pmod{s}\). Then, as \(n\to\infty\), \[\label{eq:ratio} \frac{\ell_{\mathrm{TYB}}}{\ell_{\mathrm{new}}} =\frac{\prod_{i=1}^{n} p_i^{\prime}}{\prod_{i=1}^{n} p_i}=\varphi(s)^{n+\mathrm{o}(n)}.\qquad{(5)}\]
Proof. For fixed \(s\), the prime number theorem and its arithmetic-progression version [23] give \[p_n \sim n\log n, \qquad p_n' \sim \varphi(s)\, n\log n \qquad (n\to\infty).\] Hence \[\frac{p_n'}{p_n}\to \varphi(s) \qquad (n\to\infty),\] and therefore \[\log\frac{p_n'}{p_n}\to \log\varphi(s).\] By the Cesàro mean theorem, \[\frac{1}{n}\sum_{i=1}^{n}\log\frac{p_i'}{p_i}\to \log\varphi(s).\] Equivalently, \[\log\frac{\ell_{\mathrm{TYB}}}{\ell_{\mathrm{new}}} = \sum_{i=1}^{n}\log\frac{p_i'}{p_i} = n\log\varphi(s)+o(n).\] Exponentiating proves Eq. ?? . ◻
Example 2. For \(n=12\) and \(s\in\{3,4,6\}\), namely for all admissible \(s\) such that \(\varphi(s)=2\), the subpacketization of our construction is strictly smaller than that of [19]. More precisely, \[\renewcommand{\arraystretch}{1.15} \begin{array}{c|c|c|c} s & \ell_{\mathrm{new}} & \ell_{\mathrm{TYB}} & \ell_{\mathrm{TYB}}/\ell_{\mathrm{new}} \\ \hline 3 & 6.541\times 10^{15} & 6.024\times 10^{19} & 9.210\times 10^{3} \\ 4 & 8.722\times 10^{15} & 4.001\times 10^{19} & 4.588\times 10^{3} \\ 6 & 1.230\times 10^{17} & 1.205\times 10^{20} & 9.797\times 10^{2} \end{array}\]
4 Conclusion↩︎
In this paper, we formulated the construction of repair-enabling subspaces for optimal repair of Reed-Solomon codes as a basis-transformation problem over a tower of finite fields. We developed an explicit transformation procedure, consisting of Euclidean Square Partition, Transposition, and Column Aggregation, which establishes the existence of optimal repair-enabling subspaces under the single condition \(p>s\). This decouples the linear repair mechanism from the arithmetic constraints on the extension degrees used in previous constructions, yielding RS-MSR codes with subpacketization \(\ell=s\prod_{i=1}^n p_i\) for arbitrary distinct primes \(p_i>s\).
Several questions remain open. The exponential lower bound of Alrabiah and Guruswami [24] shows that some exponential dependence of the subpacketization on \(n\) is unavoidable for MSR codes. However, a gap remains between this lower bound and the subpacketization of our construction. Closing this gap is an interesting direction. It is also of interest to determine whether the proposed basis-transformation framework extends to multi-node or cooperative repair models, and whether it can support optimal-access repair in these more general settings.
5 Explicit form of the generators of S↩︎
In this appendix, we derive the explicit formula for the generators of \(S\) as shown in Eq. 7 , i.e., \(\overline{R}(0,c)\) for \(0\le c\le p-1\).
First, by Proposition 1(3), the operator \(\mathrm{Agg}(\cdot)\) acts as the identity on the first \(a_0s\) columns of \(R\). Hence \[\overline{R}(0,rs+u)=R(0,rs+u)=\alpha^{rs}(\alpha\beta)^u, \qquad 0\le r\le a_0-1,\;0\le u\le s-1,\] which are exactly the generators of \(S^{(1)}\). It remains to determine \[\mathcal{R}_j=\overline{R}(0,a_0s+j),\qquad 0\le j\le b_1-1.\] Retain the local coordinates \((i,j)\in\mathcal{I}(s,b_1)\) on \(R_1\) via the identification \[R_1(i,j)\longleftrightarrow R(i,a_0s+j).\] Recall that, for each local column \(j\in[0,b_1-1]\), \[\mathsf{Exp}(j) := \{t\in[0,s-1]:\beta^t\text{ appears in column }a_0s+j\text{ of }R\}.\] Therefore \[\label{eq:Rj-exp} \mathcal{R}_j = \alpha^{a_0s+j}\sum_{t\in\mathsf{Exp}(j)}\beta^t .\tag{13}\] Thus the problem reduces to determining \(\mathsf{Exp}(j)\) for each local column \(j\). By Proposition 1(2), within each Euclidean square of \(\mathcal{P}(s,b_1)\), the \(\beta\)-exponent is constant along each local column. Thus, for a fixed local column \(j\), every square crossed by that column contributes exactly one \(\beta\)-exponent to \(\mathsf{Exp}(j)\).
Let \[Q=[\rho,\rho+\lambda-1]\times[\kappa,\kappa+\lambda-1] \in\mathcal{P}(s,b_1)\] be a Euclidean square. We say that \(Q\) crosses the local column \(j\) if \[\kappa\le j\le \kappa+\lambda-1.\] In this case, the \(j\)-column contribution of \(Q\) is defined as \[\mathsf{ctr}_j(Q):=\rho+j-\kappa .\] Indeed, by Lemma 3(2), every entry of \(R_1\) lying in the intersection of \(Q\) with the local column \(j\) has \(\beta\)-exponent \[\rho+(a_0s+j)-(a_0s+\kappa)=\rho+j-\kappa.\]
Hence \[\label{eq:Exp-ctr} \mathsf{Exp}(j)=\{\mathsf{ctr}_j(Q):Q\in\mathcal{P}(s,b_1)\text{ crosses column }j\}.\tag{14}\]
Before proceeding, we recall the following notations from the Euclidean algorithm that will be frequently used in the proofs below.
\(\nu:=\lfloor m/2\rfloor,\nu':=\lceil m/2\rceil .\)
\(C_0 := 0\) and \(C_r := \sum_{\mu=1}^{r} a_{2\mu} b_{2\mu}\) for \(1\le r\le \nu\).
\(Y_0 := 0\) and \(Y_h := \sum_{\gamma=1}^{h} a_{2\gamma-1} b_{2\gamma-1}\) for \(1\le h\le \nu'.\)
For \(j\in[0,b_1-1]\), \[j^{(0)}:=j,\qquad j^{(2r)}:=j^{(2r-2)} \pmod{b_{2r}}, \qquad 1\le r\le \nu.\]
Next, we divide the squares of \(\mathcal{P}(s,b_1)\) into two types of layers according to their directions.
Definition 6 (Layers and column contributions of \(\mathcal{P}(s,b_1)\)). For \(1\le h\le \nu'\), the \(h\)-th vertical layer is the family \[\mathcal{V}_h=\{V_{h,w}:0\le w\le a_{2h-1}-1\},\] where \[V_{h,w} = [Y_{h-1}+wb_{2h-1},\,Y_{h-1}+(w+1)b_{2h-1}-1] \times [C_{h-1},\,b_1-1].\] Thus the squares in \(\mathcal{V}_h\) have side length \(b_{2h-1}\) and are placed from top to bottom.
For \(1\le h\le \nu\), the \(h\)-th horizontal layer is the family \[\mathcal{H}_h=\{H_{h,w}:0\le w\le a_{2h}-1\},\] where \[H_{h,w} = [Y_h,\,s-1] \times [C_{h-1}+wb_{2h},\,C_{h-1}+(w+1)b_{2h}-1].\] Thus the squares in \(\mathcal{H}_h\) have side length \(b_{2h}\) and are placed from left to right.
For a fixed local column \(j\), a contribution \(\mathsf{ctr}_j(Q)\) is called a vertical contribution* if \(Q\in\mathcal{V}_h\) for some \(h\), and a horizontal contribution if \(Q\in\mathcal{H}_h\) for some \(h\).*
By the recursive construction of the Euclidean Square Partition, the vertical and horizontal layers in Definition 6 exhaust all Euclidean squares of \(\mathcal{P}(s,b_1)\). Figure 3 illustrates this decomposition of \(\mathcal{P}(s,b_1)\), together with the notations \(C_r\) and \(Y_h\).
![Figure 3: Decomposition of\mathcal{P}(s,b_1).Subfigure ([fig:xxxx]) groups the horizontal layers, andsubfigure ([fig:yyyyy]) groups the vertical layers. The reddashed lines mark the column boundaries C_r, and the greendashed lines mark the row boundaries Y_h.](/article/2601.10685/_pdflatex/vfaihpwg.png "fig:")
With the above notation and definitions, we can now determine \(\mathsf{Exp}(j)\) for each column \(j\) of \(R_1\).
Lemma 10. Fix \(j\in[0,b_1-1]\).
If \(C_{r-1}\le j<C_r\) for some \(1\le r\le \nu\), then column \(j\) crosses all squares in the first \(r\) vertical layers and exactly one square in the \(r\)-th horizontal layer. More precisely, \[\mathsf{Exp}(j) = \Bigl\{ Y_{h-1}+wb_{2h-1}+j^{(2h-2)}: 1\le h\le r,\;0\le w\le a_{2h-1}-1 \Bigr\} \cup \{Y_r+j^{(2r)}\}.\]
If \(m\) is odd and \(C_\nu\le j\le b_1-1\), then column \(j\) crosses all squares in the \(\nu'\) vertical layers and no horizontal-layer square. In this case, \[\mathsf{Exp}(j) = \Bigl\{ Y_{h-1}+wb_{2h-1}+j^{(2h-2)}: 1\le h\le \nu',\;0\le w\le a_{2h-1}-1 \Bigr\}.\]
Proof. Let \[Q=[\rho,\rho+\lambda-1]\times[\kappa,\kappa+\lambda-1]\] be a square of \(\mathcal{P}(s,b_1)\) crossed by column \(j\). By the definition of \(\mathsf{ctr}_j(Q)\), the exponent contributed by \(Q\) to \(\mathsf{Exp}(j)\) is \[\label{eq:contribution-general} \mathsf{ctr}_j(Q)=\rho+j-\kappa.\tag{15}\]
We record a simple consequence of the recursive definition of \(j^{(2r)}\) in Eq. 5 . For \(0\le r\le \nu\), it holds that \[\label{eq:j-coordinate} j^{(2r)}=j-C_r, \qquad\text{whenever } C_r\le j\le b_1-1.\tag{16}\] Indeed, the case \(r=0\) is immediate. If the identity holds for \(r-1\) and suppose that \(C_r\le j\le b_1-1\), then \[j^{(2r-2)}=j-C_{r-1} =a_{2r}b_{2r}+(j-C_r).\] Note that \(b_1-C_{r-1}=b_{2r-1}\) and \(C_r-C_{r-1}=a_{2r}b_{2r}\), so \[0 \leq j-C_r<b_1-C_r=b_{2r-1}-a_{2r}b_{2r}<b_{2r}.\] Hence \[j^{(2r)} =j^{(2r-2)}\pmod {b_{2r}} =j-C_r.\]
First, consider a vertical-layer square \(V_{h,w}\) crossed by column \(j\), i.e., \(C_{h-1} \leq j \leq b_1-1\). By Eq. 16 with \(r=h-1\), we have \[j=C_{h-1}+j^{(2h-2)}.\] Substituting \[\rho=Y_{h-1}+wb_{2h-1} \text{ and } \kappa=C_{h-1}\] into Eq. 15 , we obtain the vertical contribution \[\label{eq:vertical-ctr} \mathsf{ctr}_j(V_{h,w}) = Y_{h-1}+wb_{2h-1}+j^{(2h-2)}.\tag{17}\]
Next, consider a horizontal-layer square \(H_{h,w}\) crossed by column \(j\), i.e., \[C_{h-1}+wb_{2h}\le j \le C_{h-1}+(w+1)b_{2h}-1.\] By Eq. 16 with \(r=h-1\), we have \[j^{(2h-2)}=j-C_{h-1}.\] Since \(j-C_{h-1}\in[wb_{2h},(w+1)b_{2h}-1]\), the recursive definition gives \[j=C_{h-1}+wb_{2h}+j^{(2h)}.\] Substituting \[\rho=Y_h, \text{ and } \kappa=C_{h-1}+wb_{2h}\] into Eq. 15 , we obtain the horizontal contribution \[\label{eq:horizontal-ctr} \mathsf{ctr}_j(H_{h,w})=Y_h+j^{(2h)}.\tag{18}\]
(1) \(C_{r-1}\le j<C_r\) for some \(1\le r\le\nu\).
Then \(j\) lies in the column range of every vertical layer \(\mathcal{V}_h\) with \(1\le h\le r\), and in the column range of no later vertical layer. Moreover, it lies in exactly one square of the \(r\)-th horizontal layer and in no horizontal layer with index different from \(r\). Substituting Eq. 17 and Eq. 18 to Eq. 14 give the first formula.
(2) \(m\) odd and \(C_\nu\le j\le b_1-1\).
Then \(\nu'=\nu+1\), and column \(j\) lies in the column range of every vertical layer \(\mathcal{V}_h\), \(1\le h\le \nu'\), while it lies in no horizontal layer. Substituting Eq. 17 to Eq. 14 gives the second formula. ◻
Finally, substituting the results of Lemma 10(1) and (2) into Eq. 13 , respectively, we obtain
If \(1\le r\le \nu\) and \(C_{r-1}\le j<C_r\), then \[\mathcal{R}_j = \alpha^{a_0 s+j}\!\left( \sum_{h=0}^{r-1}\sum_{w=0}^{a_{2h+1}-1} \beta^{Y_{h} +w\,b_{2h+1}+j^{(2h)}} + \beta^{Y_r+j^{(2r)}} \right).\]
If \(m\) is odd and \(C_{\nu}\le j\le b_1-1\), then \[\mathcal{R}_j = \alpha^{a_0s+j} \sum_{h=0}^{\nu'-1}\sum_{w=0}^{a_{2h+1}-1} \beta^{Y_h +w\,b_{2h+1}+j^{(2h)}},\]
which coincide with the formulas stated in Theorem 3.
6 Proofs of Lemmas 8 and 9↩︎
This appendix proves Lemmas 8 and 9, which are used in the induction argument of Section 3.5. We retain the notation of Section 3 and Appendix 5. In particular, \(R_1\) denotes the local subarray formed by the last \(b_1\) columns of \(R\), with local index set \(\mathcal{I}(s,b_1)\), and \[t_{i,j}:=\tau(i,a_0s+j), \qquad (i,j)\in\mathcal{I}(s,b_1).\] The common task in both lemmas is to show that the position produced by the locating map precedes the current position \((i,j)\) in the column-major order \[(i',j')\prec(i,j) \quad\Longleftrightarrow\quad j'<j\quad\text{or}\quad j'=j\text{ and }i'<i.\] Lemma 8 treats the case \(t<t_{i,j}\), whereas Lemma 9 treats the case \(t>t_{i,j}\) with \(i+j\ge t\).
We shall use the column-wise contribution notation introduced in Definition 6. Thus, when \(t\in\mathsf{Exp}(j)\), we say that \(t\) is produced by a square \(Q\) if \[t=\mathsf{ctr}_j(Q).\] Equivalently, \(t\) is the \(\beta\)-exponent of the entries lying in the intersection of \(Q\) with the local column \(j\).
The following two facts are useful for our proofs.
Fact 1. Fix \(j\in[0,b_1-1]\). If \(\mathsf{Exp}(j)\) contains a horizontal contribution, then that contribution is the unique maximal element of \(\mathsf{Exp}(j)\). Consequently, for every \((i,j)\in\mathcal{I}(s,b_1)\) and every \[t\in\mathsf{Exp}(j)\setminus\{t_{i,j}\},\] the inequality \(t<t_{i,j}\) implies that \(t\) is a vertical contribution.
Proof. By Lemma 10, the horizontal contribution comes from a square lying strictly below every vertical-layer square crossed by local column \(j\). By parts (2) and (4) of Proposition 1, each square contributes a single \(\beta\)-exponent per column, and lower squares contribute strictly larger exponents. Hence, in local column \(j\), the horizontal contribution, if it exists, is strictly greater than any vertical contribution and is therefore the unique maximum of \(\mathsf{Exp}(j)\). ◻
Fact 2. Fix \(r\in[1,\nu]\) and \(w\in[0,a_{2r}]\), and let \[D := C_{r-1}+w\,b_{2r}.\] Every Euclidean square of \(\mathcal{P}(s,b_1)\) whose row range meets \([Y_r,s-1]\) lies entirely in columns \([0,D-1]\) or entirely in columns \([D,b_1-1]\).
Proof. By Definition 6, the vertical layers \(1,\ldots,r\) of \(\mathcal{P}(s,b_1)\) have row ranges contained in \([0,Y_r-1]\), so they do not meet \([Y_r,s-1]\). The remaining squares that meet \([Y_r,s-1]\) fall into three groups.
Horizontal layers \(1,\ldots,r-1\). For \(1\leq h<r\), the \(h\)-th horizontal layer has column range \([C_{h-1},C_h-1]\subseteq[0,C_{r-1}-1]\subseteq[0,D-1]\) (since \(D\ge C_{r-1}\)).
The \(r\)-th horizontal layer. It partitions \([Y_r,s-1]\times[C_{r-1},C_r-1]\) into \(a_{2r}\) squares of width \(b_{2r}\); each occupies columns \([C_{r-1}+w'b_{2r},\,C_{r-1}+(w'+1)b_{2r}-1]\) for some \(w'\in[0,a_{2r}-1]\), and lies entirely on one side of \(D\) by the definition of \(D\).
All squares after the \(r\)-th horizontal layer. Their column ranges are contained in \([C_r,b_1-1]\subseteq[D,b_1-1]\) (since \(D\le C_r\)).
◻
Proof of Lemma 8. By Fact 1, \(t<t_{i,j}\) implies that \(t\) is a vertical contribution. Hence there exist \(h\in[1,\nu']\) and \(w\in[0,a_{2h-1}-1]\) such that \(t\) is produced by \[Q^*=V_{h,w} = [Y_{h-1}+wb_{2h-1},\,Y_{h-1}+(w+1)b_{2h-1}-1] \times [C_{h-1},\,b_1-1].\] Thus \[\label{eq:lemma8-tj} t = Y_{h-1}+wb_{2h-1}+j^{(2h-2)}, \qquad j=C_{h-1}+j^{(2h-2)}.\tag{19}\]
Fix \(\xi\in[0,b_1-1]\), and let \(Q'\) be the square of \(\mathcal{P}(s,b_1)\) containing \((t,\xi)\).
Case 1: \(\xi<C_{h-1}\). This case is void when \(h=1\), so assume \(h\ge 2\). Since \(t\ge Y_{h-1}\), the row range of \(Q'\) meets \([Y_{h-1},s-1]\). Applying Fact 2 with \(r=h-1\) and \(D=C_{h-1}\), the square \(Q'\) lies entirely on one side of column \(C_{h-1}\). The assumption \(\xi<C_{h-1}\) forces it onto the left side, giving column range \(\subseteq[0,C_{h-1}-1]\). By Eq. ?? , \((i_{t,\xi},j_{t,\xi})\in Q'\), hence \(j_{t,\xi}\le C_{h-1}-1<C_{h-1}\le j\). The column priority in \(\prec\) yields \(\operatorname{Loc}(t,\xi)\prec(i,j)\).
Case 2: \(\xi\ge C_{h-1}\). In this case, by Eq. 19 , \(t\) lies in the row range of \(Q^*\), since \[j^{(2h-2)}=j-C_{h-1}\le b_1-1-C_{h-1}=b_{2h-1}-1.\] Moreover, \(\xi\) lies in \([C_{h-1},b_1-1]\) by assumption. Hence \((t,\xi)\in Q^*\). The explicit locating formula from Lemma 7 gives \[j_{t,\xi} = C_{h-1}+\bigl(t-(Y_{h-1}+wb_{2h-1})\bigr) = C_{h-1}+j^{(2h-2)} = j,\] and \[i_{t,\xi} = Y_{h-1}+wb_{2h-1}+(\xi-C_{h-1}).\] Since \(\xi\le b_1-1=C_{h-1}+b_{2h-1}-1\), we have \[\label{eq:lemma8-itxi-upper} i_{t,\xi} \le Y_{h-1}+(w+1)b_{2h-1}-1.\tag{20}\] On the other hand, \(t<t_{i,j}\), together with Proposition 1(4), implies that the square containing \((i,j)\) lies strictly below \(Q^*\). Hence \[\label{eq:lemma8-i-lower} i\ge Y_{h-1}+(w+1)b_{2h-1}.\tag{21}\] Combining Eq. 20 and Eq. 21 , we obtain \(i_{t,\xi}<i\). Since \(j_{t,\xi}=j\), the row tie-breaker in the column-major order gives \[\mathsf{Loc}(t,\xi)=(i_{t,\xi},j_{t,\xi})\prec(i,j).\] ◻
Proof of Lemma 9. From \(\delta=i+j-t\) and \(i+j\ge t\), we have \(\delta\ge 0\). It remains to show \(\delta\le b_1-1\) and \(\operatorname{Loc}(t,\delta)\prec(i,j)\).
Since \(t>t_{i,j}\), Proposition 1(4) implies that the square producing \(t\) in column \(j\) lies strictly below the square containing \((i,j)\). We distinguish whether \(t\) is a vertical or horizontal contribution.
Vertical contribution. Suppose that \(t\) is produced by a vertical-layer square \(V_{h,w}\). By Lemma 10, \[t=Y_{h-1}+wb_{2h-1}+j^{(2h-2)}, \qquad j=C_{h-1}+j^{(2h-2)}.\] Since the square containing \((i,j)\) lies strictly above \(V_{h,w}\), we have \[i\le Y_{h-1}+wb_{2h-1}-1.\] Therefore \[\delta = i+j-t = i+C_{h-1}-(Y_{h-1}+wb_{2h-1}) \le C_{h-1}-1 \le b_1-1.\] Together with \(\delta\ge0\), this also shows that the present case can occur only when \(h\ge2\). Moreover, \(\delta<C_{h-1}\le j\). Since \(t\ge Y_{h-1}\), the square containing \((t,\delta)\) has row range meeting \([Y_{h-1},s-1]\). By Fact 2, applied with \(r=h-1\) and \(D=C_{h-1}\), this square lies entirely to the left of column \(C_{h-1}\). Therefore the column coordinate of \(\mathsf{Loc}(t,\delta)\) is at most \(C_{h-1}-1<j\), and hence \[\mathsf{Loc}(t,\delta)\prec(i,j).\]
Horizontal contribution. Suppose that \(t\) is produced by a horizontal-layer square \(H_{r,w}\). Put \[\kappa:=C_{r-1}+wb_{2r}.\] By Lemma 10, \[t=Y_r+j^{(2r)}, \qquad j=\kappa+j^{(2r)}.\] Since the square containing \((i,j)\) lies strictly above \(H_{r,w}\), we have \[i\le Y_r-1.\] Consequently, \[\delta = i+j-t = i+\kappa-Y_r \le \kappa-1 \le b_1-1.\] Again \(\delta\ge0\), and hence \(\delta<\kappa\le j\). Since \(t\ge Y_r\), the square containing \((t,\delta)\) has row range meeting \([Y_r,s-1]\). Applying Fact 2 with \(D=\kappa\), this square lies entirely to the left of column \(\kappa\). Therefore the column coordinate of \(\mathsf{Loc}(t,\delta)\) is at most \(\kappa-1<j\), and hence \[\mathsf{Loc}(t,\delta)\prec(i,j).\] This completes the proof. ◻
The following example provides a detailed walkthrough of the inductive recovery argument for a concrete instance, exercising every component of the proof machinery developed in Lemmas 3–9.
Example 3.
Let \(p=70\), \(s=29\). We show how \(R(14,68)\) can be recovered from \(\overline{R}\).
The Euclidean algorithm gives \[70=2\cdot 29+12,\quad 29=2\cdot 12+5,\quad 12=2\cdot 5+2,\quad 5=2\cdot 2+1,\quad 2=2\cdot 1,\] so \[a_0=2,\quad a_1=a_2=a_3=a_4=2,\quad b_1=12,\quad b_2=5,\quad b_3=2,\quad b_4=1,\] and \(a_0s=58\), \(\nu=\lfloor m/2\rfloor=2\). By Lemma 6, the local index set of \(R_1\) is \[\mathcal{I}(29,12)=[0,28]\times[0,11],\] and its partition is \(\mathcal{P}(29,12)\). Thus the first vertical layer consists of two \(12\times 12\) squares, the first horizontal layer consists of two \(5\times5\) squares, the second vertical layer consists of two \(2\times2\) squares, and the second horizontal layer consists of two \(1\times1\) squares.
Applying Lemma 3(2) to these squares gives the following local \(\beta\)-exponent profile: \[\tau(i,58+j)= \begin{cases} j, & 0\le i\le 11,\\ 12+j, & 12\le i\le 23,\\ 24+(j\bmod 5), & 24\le i\le 28,\;0\le j\le 9,\\ 24+(j-10), & 24\le i\le 25,\;j\in\{10,11\},\\ 26+(j-10), & 26\le i\le 27,\;j\in\{10,11\},\\ 28, & i=28,\;j\in\{10,11\}. \end{cases}\]
Next we calculate \(\mathsf{Exp}(10)\). Consider the local column \(j=10\), i.e., the global column \(58+10=68\). Here \[C_1=a_2b_2=10,\qquad C_2=a_2b_2+a_4b_4=12,\] and \[j^{(0)}=10,\qquad j^{(2)}=10\pmod 5=0,\qquad j^{(4)}=0\pmod 1=0.\] Since \(C_1\le 10<C_2\), Lemma 10(1) with \(r=2\) applies. The vertical contributions are \[0+0\cdot 12+10=10,\qquad 0+1\cdot 12+10=22,\] from the two \(12\times12\) squares, and \[24+0\cdot 2+0=24,\qquad 24+1\cdot 2+0=26,\] from the two \(2\times2\) squares. The second horizontal layer contributes \[28+j^{(4)}=28.\] Therefore \[\mathsf{Exp}(10)=\{10,22,24,26,28\}.\]
**The target local point.* Take \((i,j)=(14,10)\). By the exponent profile above, \[t_{14,10}=\tau(14,68)=22,\] and by Lemma 3(1), \[R(14,68)=\alpha^{58+14+10}\beta^{22}=\alpha^{82}\beta^{22}.\] Thus the recovery formula Eq. 10 becomes \[R(14,68) = \overline{R}(14,68) - \alpha^{82}\bigl(\beta^{10}+\beta^{24}+\beta^{26}+\beta^{28}\bigr).\] Moreover, \(\overline{R}(14,68)\in K\) by Eq. 11 . It remains to show that \[\alpha^{82}\beta^t\in K \qquad \text{for }t\in\{10,24,26,28\}.\] The four interference exponents fall into the three cases exactly as follows: \[\begin{array}{c|c|c} t & \text{condition} & \text{case} \\ \hline 26,28 & 14+10<t & \text{(C1)}\\ 10 & t<t_{14,10}=22 & \text{(C2)} \\ 24 & t>t_{14,10}=22\text{ and }14+10\ge 24 & \text{(C3)} \end{array}\]*
**Case (C1): \(t=26,28\).* For \(t\in\{26,28\}\), set \[q_t:=58+14+10-t=82-t.\] Then \(q_{26}=56\) and \(q_{28}=54\), both lying in \([0,a_0s-1]=[0,57]\). Lemma 4, applied with \(\theta=t\), gives \[\alpha^{q_t}(\alpha\beta)^t = \alpha^{82}\beta^t \in K.\] Hence \(\alpha^{82}\beta^{26},\alpha^{82}\beta^{28}\in K\).*
**Case (C2): \(t=10\).* Here \(10<t_{14,10}\), so Lemma 8 applies. We spell out the locating map to make the use of Lemma 7 explicit. For every \(\xi\in[0,11]\), the point \((10,\xi)\) lies in the top-left square \([0,11]\times[0,11]\) of \(\mathcal{P}(29,12)\). Thus Eq. ?? gives \[\operatorname{Loc}(10,\xi)=(\xi,10).\] Since \(\xi\le 11<14\), we have \((\xi,10)\prec(14,10)\) for every \(\xi\in[0,11]\). By the induction hypothesis and Lemma 7, \[R(\xi,58+10) = \alpha^{58+10+\xi}\beta^{10} = \alpha^{68+\xi}\beta^{10} \in K, \qquad 0\le \xi\le 11.\] On the other hand, Lemma 4 gives \[\alpha^{10+u}\beta^{10}\in K, \qquad 0\le u\le 57.\] Together these are the \(70=p\) consecutive elements \[\alpha^{10}\beta^{10},\alpha^{11}\beta^{10},\ldots,\alpha^{79}\beta^{10}\] in \(K\). Lemma 5 yields \(\mathbb{E}\beta^{10}\subseteq K\), and therefore \(\alpha^{82}\beta^{10}\in K\).*
**Case (C3): \(t=24\).* Here \[\delta:=14+10-24=0\in [0,b_1-1]=[0,11].\] Since \((24,0)\) lies in the square \([24,28]\times[0,4]\), formula Eq. ?? gives \[\operatorname{Loc}(24,0)=(24,0).\] This point precedes \((14,10)\) by column priority, since its column is \(0<10\). By the induction hypothesis and Lemma 7, \[R(24,58) = \alpha^{58+24+0}\beta^{24} = \alpha^{82}\beta^{24} \in K.\]*
We have proved that all interference monomials \[\alpha^{82}\beta^{10},\quad \alpha^{82}\beta^{24},\quad \alpha^{82}\beta^{26},\quad \alpha^{82}\beta^{28}\] belong to \(K\). Since \(\overline{R}(14,68)\in K\), the recovery formula Eq. 10 gives \(R(14,68)\in K\), as required by the inductive step.
References↩︎
This work was supported in part by the National Key Research and Development Program of China under Grants 2021YFA1001000 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: Weijun Fang.)↩︎
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?).↩︎
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).↩︎
Fang-Wei Fu is with the Chern Institute of Mathematics and LPMC, Nankai University, Tianjin 300071, China (e-mail: fwfu@nankai.edu.cn).↩︎
A preliminary conference version [1] of this work has been accepted for presentation at the 2026 IEEE International Symposium on Information Theory (ISIT).↩︎