Proof. The erasure patterns from Definition 5 are correctable by the constructions that we will give in Sections 4, 5 and 6. Therefore, the first part follows from Definition 5 (i.e., there exists some LRC for the corresponding parameter values that can correct such erasure patterns).

We set \(t=1\) for the remainder of the proof. Let \(\mathcal{E} \subseteq [n]\) be an erasure pattern that can be corrected by some LRC \(\mathcal{C} \subseteq \mathbb{F}^n\) of type \((r,\delta,N,t)\) with information \(N\)-availability. We only need to prove that \(\mathcal{E}\) is simple as in Definition 7.

We will modify \(\mathcal{E}\) successively in a way that, in each iteration, the next pattern is correctable and simple if, and only if, so was the previous pattern. We will arrive at a correctable pattern that is easy to see that is simple, and we will be done (i.e., the original pattern \(\mathcal{E}\) must be simple too).

Let \(i \in [g]\) and consider the case that \(|\mathcal{E} \cap R_i| \leq N(\delta - 1)\). There must exist \(j_i \in [N]\) such that \(|\mathcal{E} \cap R_{i,j_i}| \leq \delta - 1\). This is because if \(|\mathcal{E} \cap R_{i,j}| \geq \delta\), for all \(j \in [N]\), then \(|\mathcal{E} \cap R_i | \geq N(\delta - 1) + 1\), since \(|R_{i,j} \cap R_{i,\ell}| = |T_i| = t = 1\) if \(i \neq \ell\) (here we use the assumption \(t=1\)). Since \(\mathcal{C}\) is an LRC, we can remove the entire set \(\mathcal{E} \cap R_{i,j_i}\) from \(\mathcal{E}\) (i.e., locally correct it) and replace it by \(|\mathcal{E} \cap R_{i,j_i}|\) elements inside \(R_{i,j_i} \setminus T_i\) (recall that \(|R_{i,j_i} \setminus T_i| \geq \delta - 1\)). In this way, we may assume that \(\mathcal{E} \cap T_i = \varnothing\). Now, if \(| \mathcal{E} \cap (R_{i,j} \setminus T_i) | < \delta - 1\), for some \(j \in [N]\), then we may add elements to \(\mathcal{E} \cap (R_{i,j} \setminus T_i)\) until \(| \mathcal{E} \cap (R_{i,j} \setminus T_i) | = \delta - 1\), since in this case \(\mathcal{E} \cap (R_{i,j} \setminus T_i)\) is locally correctable and \(|R_{i,j} \setminus T_i| \geq \delta - 1\). Hence we may assume that \(| \mathcal{E} \cap (R_{i,j} \setminus T_i) | \geq \delta - 1\), for all \(j \in [N]\).

In other words, we may assume that \(|\mathcal{E} \cap R_i| \geq N(\delta - 1)\), i.e., \[| \mathcal{E} \cap R_i | = N(\delta - 1) + e_i,\] where \(e_i \geq 0\), for all \(i \in [g]\), and where \(| \mathcal{E} \cap (R_{i,j} \setminus T_i)| = \delta - 1\) for all \(j \in [N]\) if \(e_i=0\). Note that, since \(\mathcal{E}\) is correctable, then it must hold that \[\sum_{i=1}^g e_i \leq h.\]

Now let \(i \in [g]\) be such that \(e_i > 0\). We distinguish two cases. First, consider the case \(\mathcal{E} \cap T_i = \varnothing\). As before, since \(\mathcal{C}\) is locally correctable, we may assume that \(|\mathcal{E} \cap (R_{i,j} \setminus T_i) | \geq \delta - 1\), for all \(j \in [N]\). In this case, we set \[|\mathcal{E} \cap (R_{i,j} \setminus T_i)| = \delta - 1 + e_{i,j},\] where \(e_{i,j} \geq 0\), for all \(j \in [N]\). The other possible case is \(T_i \subseteq \mathcal{E}\) since \(|T_i| = t = 1\) (here we also use the assumption \(t=1\)). Once again, if \(|\mathcal{E} \cap (R_{i,j}\setminus T_i)| \leq \delta -2\), for some \(j \in [N]\), then we may again add elements to \(\mathcal{E} \cap (R_{i,j}\setminus T_i)\) until \(|\mathcal{E} \cap (R_{i,j}\setminus T_i)| = \delta -2\), which means \(|\mathcal{E} \cap R_{i,j}| = \delta - 1\). In this second case, we set \[|\mathcal{E} \cap (R_{i,j} \setminus T_i)| = \left\lbrace \begin{array}{ll} \delta - 1 + e_{i,1} - 1 & \textrm{ if } j = 1, \\ \delta - 1 + e_{i,j} & \textrm{ if } j > 1, \end{array} \right.\] where \(e_{i,j} \geq 0\) and \(e_{i,1} \geq 1\), for all \(j \in [N]\) (in a way, we “assign” the element in \(T_i \subseteq \mathcal{E}\) to \(\mathcal{E} \cap R_{i,1}\) and no other set \(\mathcal{E} \cap R_{i,j}\)). Note that, as we modified \(\mathcal{E}\), the values of \(e_i\) and \(e_{i,j}\), for \(i \in [g]\) and \(j \in [N]\), also changed.

In all cases, we have that \[e_i = \sum_{j=1}^N e_{i,j},\] for all \(i \in [g]\). Next, since \(\mathcal{E}\) is correctable by a code of length \(n\) and dimension \(k\), and \(n-k = h + gN(\delta - 1)\), then \[|\mathcal{E}| \leq h + gN(\delta- 1).\] Since \(|\mathcal{E} \cap R_i| = N(\delta - 1) + e_i\), for all \(i \in [g]\), then \[\sum_{i=1}^g e_i \leq h.\] Now, since \(|\mathcal{E} \cap (R_{i,j} \setminus T_i)| \geq \delta - 1\), we may define \(\mathcal{E}_2 \subseteq \mathcal{E}\) by choosing any \(\delta - 1\) elements in \(\mathcal{E} \cap (R_{i,j} \setminus T_i)\), for all \(i \in [g]\) and all \(j \in [N]\). Setting \(\mathcal{E}_1 = \mathcal{E} \setminus \mathcal{E}_2\), we deduce that \[|\mathcal{E}_1| = |\mathcal{E}| - |\mathcal{E}_2| = \sum_{i=1}^g e_i \leq h.\] It is obvious that \(\mathcal{E}_2\) is locally correctable since \(\mathcal{E}_2 \cap T_i = \varnothing\) and \(|\mathcal{E}_2 \cap (R_{i,j} \setminus T_i)| = \delta - 1\), for all \(i \in [g]\) and all \(j \in [N]\). Therefore, \(\mathcal{E}\) is simple by Definition 7.

Finally, the original erasure pattern must be simple too, since every time we modified it, if the next pattern was simple, then so was the previous one, hence we are done. ◻

Proof. We define the sets \(T_i\) and \(R_{i,j}\) as in (1 ). Clearly, \(\mathcal{C}_{glob}\) is an LRC of type \((r,\delta,N,t)\) with \(N\)-availability, and if \(k \leq gt\), it has information \(N\)-availability. Hence we only need to prove that it can correct any simple erasure pattern as in Definition 7.

Consider an erasure pattern \(\mathcal{E} \subseteq [n]\) that is locally correctable, as in Definition 4, and of maximum size, i.e., \(|\mathcal{E}| = gN(\delta - 1)\). By Remark 8, we only need to show that \(\mathcal{C}_{glob}|_{\overline{\mathcal{E}}}\) is MDS, where \(\overline{\mathcal{E}} = [n] \setminus \mathcal{E}\).

Without loss of generality (by reordering the sets \(R_{i,1}, \ldots, R_{i,N}\)), we may assume that \(|\mathcal{E} \cap R_{i,1}| = \delta - 1\) and \(|(R_{i,j} \setminus T_i) \cap \mathcal{E} | = \delta - 1\), for all \(j \in [2,N]\) and all \(i \in [g]\). Therefore the code \(\mathcal{C}|_{\overline{\mathcal{E}}}\) is of the form \[\mathcal{C}|_{\overline{\mathcal{E}}} = \mathcal{C}_{out} {\rm diag}(D|_{\overline{\mathcal{E}} \cap R_1}, D|_{\overline{\mathcal{E}} \cap R_2}, \ldots, D|_{\overline{\mathcal{E}} \cap R_g}) \subseteq \mathbb{F}_{q^m}^{n_o},\] where we identify \(\overline{\mathcal{E}} \cap R_i\) with \([t + N(r-t)]\) in the obvious way (they are of the same size). By Lemma 1, we only need to show that \(D|_{\overline{\mathcal{E}} \cap R_i} \in \mathbb{F}_q^{(t + N(r-t)) \times (t + N(r-t))}\) is invertible, for all \(i \in [g]\).

For each \(i \in [g]\), we have that \[D|_{\overline{\mathcal{E}} \cap R_i} = \left( \begin{array}{c|cccc} \multirow{2}{*}{A|_{\overline{\mathcal{E}} \cap R_{i,1}}} & B|_{\overline{\mathcal{E}} \cap (R_{i,2}\setminus T_i)} & B|_{\overline{\mathcal{E}} \cap (R_{i,3}\setminus T_i)} & \ldots & B|_{\overline{\mathcal{E}} \cap (R_{i,N}\setminus T_i)} \\ & 0 & 0 & \ldots & 0 \\ \hline 0 & C|_{\overline{\mathcal{E}} \cap (R_{i,2}\setminus T_i)} & 0 & \ldots & 0 \\ 0 & 0 & C|_{\overline{\mathcal{E}} \cap (R_{i,3}\setminus T_i)} & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & C|_{\overline{\mathcal{E}} \cap (R_{i,N}\setminus T_i)} \end{array} \right).\] Now, since \(A \in \mathbb{F}_q^{r \times (r+\delta -1)}\) generates an \(r\)-dimensional MDS code and \(|\mathcal{E} \cap R_{i,1}| =\delta -1\), then \(A|_{\overline{\mathcal{E}} \cap R_{i,1}} \in \mathbb{F}_q^{r \times r}\) is invertible. For the same reason, the matrix \[A|_{[t] \cup (\overline{\mathcal{E}} \cap (R_{i,j}\setminus T_i))} = \left( \begin{array}{c|c} I_t & B|_{\overline{\mathcal{E}} \cap (R_{i,j}\setminus T_i)} \\ \hline 0_{(r-t) \times t} & C|_{\overline{\mathcal{E}} \cap (R_{i,j}\setminus T_i)} \end{array} \right) \in \mathbb{F}_q^{r \times r}\] is also invertible, which in turn implies that \(C|_{\overline{\mathcal{E}} \cap (R_{i,j}\setminus T_i)} \in \mathbb{F}_q^{(r-t) \times (r-t)}\) is invertible, for \(j \in [2,N]\). Therefore, due to its upper block-triangular shape, we conclude that the matrix \(D|_{\overline{\mathcal{E}} \cap R_i} \in \mathbb{F}_q^{(t + N(r-t)) \times (t + N(r-t))}\) is invertible, for all \(i \in [g]\), and we are done. ◻

Proof. We define the sets \(T_i\) and \(R_{i,j}\) as in (1 ). Due to the shape of \(H\) and \(P\) in Construction 2, we observe that a codeword \(\mathbf{c} \in \mathcal{C}_{glob}\) restricted to the coordinates in \(R_{i,j}\) satisfies the equations \[\mathbf{c}|_{R_{i,j}} \left( \begin{array}{cc} I_t & B \\ 0 & C \end{array} \right)^\intercal = \mathbf{0},\] i.e., \(\mathbf{c}|_{R_{i,j}} (A^\prime)^\intercal = \mathbf{0}\). This means that \(\mathbf{c}|_{R_{i,j}}\) belongs to the \((r+\delta-1,r)\) MDS code with parity-check matrix \(A^\prime\), for \(j \in [N]\) and \(i \in [g]\). This proves that \(\mathcal{C}_{glob}\) is an LRC of type \((r,\delta,N,t)\) with \(N\)-availability, and if \(k \leq gt\), it has information \(N\)-availability.

Now we prove that it can correct any simple erasure pattern \(\mathcal{E} \subseteq [n]\) as in Definition 7. That is, \(\mathcal{E} = \mathcal{E}_1 \cup \mathcal{E}_2\), where the union is disjoint, \(\mathcal{E}_1\) is locally correctable (Definition 4) and \(|\mathcal{E}_2| \leq h\). Without loss of generality, we may assume that \(\mathcal{E}\) is of maximum size and that \(\mathcal{E}_1\) can be locally repaired starting from the first recovery sets, i.e.,

1. \(| \mathcal{E}_1 \cap R_{i,1} | = \delta - 1\), for all \(i \in [g]\),

2. \(| \mathcal{E}_1 \cap (R_{i,j} \setminus T_i) | = \delta - 1\), for all \(j \in [2,N]\) and all \(i \in [g]\), and

3. \(| \mathcal{E}_2 | = h\).

In order to be able to correct such erasures, we need the matrix \(H|_\mathcal{E} \in \mathbb{F}_{q^m}^{(gN(\delta - 1) + h) \times |\mathcal{E}|}\) to be invertible (notice that it is square, i.e., \(|\mathcal{E}| = gN(\delta - 1) + h\)).

Consider sets \(\overline{\Delta}_{i,j} \subseteq \mathcal{E}_1\) and \(\Delta_{i,j} \subseteq \mathcal{E}_2\) (thus disjoint) such that \(|\overline{\Delta}_{i,j}| = \delta - 1\) and \[\Delta_{i,j} \cup \overline{\Delta}_{i,j} = \left\lbrace \begin{array}{ll} \mathcal{E} \cap R_{i,1} & \textrm{ if } j = 1, \\ \mathcal{E} \cap (R_{i,j} \setminus T_i) & \textrm{ otherwise,} \end{array} \right.\] for \(j \in [N]\) and \(i \in [g]\). We also set, for \(i \in [g]\), \[\Delta_i = \bigcup_{j=1}^N \Delta_{i,j} \quad \textrm{and} \quad \overline{\Delta}_i = \bigcup_{j=1}^N \overline{\Delta}_{i,j}.\] By the MDS property, the restricted matrices \[\left( \begin{array}{cc} I_t & B \\ 0 & C \end{array} \right)_{\overline{\Delta}_{i,1}}, \left( \begin{array}{c} B \\ C \end{array} \right)_{\overline{\Delta}_{i,j}} \in \mathbb{F}_q^{(\delta-1)\times(\delta-1)} \label{eq32local32matrices32for32parity32proof}\tag{2}\] are invertible, for \(j \in [2,N]\) and \(i \in [g]\). Therefore, \(P_{\overline{\Delta}_i} \in \mathbb{F}_q^{N(\delta-1) \times N(\delta-1)}\) is also invertible due to its triangular shape.

Using the same reasoning, we have that \[\left( \begin{array}{cc} I_t & B \\ 0 & C \\ 0 & D \end{array} \right)_{\overline{\Delta}_{i,1} \cup \Delta_{i,1}}, \left( \begin{array}{c} B \\ C \\ D \end{array} \right)_{\overline{\Delta}_{i,j} \cup \Delta_{i,j}} \in \mathbb{F}_q^{(h+\delta-1)\times|\overline{\Delta}_{i,j} \cup \Delta_{i,j}|} \textrm{ if } j \geq 2,\] have full column rank \(|\overline{\Delta}_{i,j} \cup \Delta_{i,j}| \leq h + \delta - 1\), for \(j \in [N]\) and \(i \in [g]\). Therefore, \[\left( \begin{array}{c} P_{\overline{\Delta}_i \cup \Delta_i} \\ Q_{\overline{\Delta}_i \cup \Delta_i} \end{array} \right) \in \mathbb{F}_q^{(N(h + \delta-1)) \times |\overline{\Delta}_i \cup \Delta_i |}\] is of full column rank \(|\overline{\Delta}_i \cup \Delta_i | \leq h + N(\delta-1)\), since reordering its rows we obtain the matrix \[\left( \begin{array}{cccc} \left( \begin{array}{cc} I_t & B \\ 0 & C \\ 0 & D \end{array} \right)_{\overline{\Delta}_{i,1} \cup \Delta_{i,1}} & 0 & \ldots & 0 \\ \left( \begin{array}{cc} I_t & 0 \\ 0 & 0 \\ 0 & 0 \end{array} \right)_{\overline{\Delta}_{i,1} \cup \Delta_{i,1}} & \left( \begin{array}{c} B \\ C \\ D \end{array} \right)_{\overline{\Delta}_{i,2} \cup \Delta_{i,2}} & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ \left( \begin{array}{cc} I_t & 0 \\ 0 & 0 \\ 0 & 0 \end{array} \right)_{\overline{\Delta}_{i,1} \cup \Delta_{i,1}} & 0 & \ldots & \left( \begin{array}{c} B \\ C \\ D \end{array} \right)_{\overline{\Delta}_{i,N} \cup \Delta_{i,N}} \end{array} \right),\] which is of full column rank \(|\overline{\Delta}_i \cup \Delta_i | \leq h + N(\delta-1)\) due to its triangular shape as before.

Now, since the matrices in (2 ) are invertible, then using elementary \(\mathbb{F}_q\)-linear column operations, we may construct invertible matrices \(E_{i,j} \in \mathbb{F}_q^{|\overline{\Delta}_{i,j} \cup \Delta_{i,j}| \times |\overline{\Delta}_{i,j} \cup \Delta_{i,j}|}\) such that \[\left( \begin{array}{cc} I_t & B \\ 0 & C \\ 0 & D \end{array} \right)_{\overline{\Delta}_{i,1} \cup \Delta_{i,1}} \cdot E_{i,1} = \left( \begin{array}{cc} \left( \begin{array}{cc} I_t & B \\ 0 & C \end{array} \right)_{\overline{\Delta}_{i,1}} & 0 \\ \left( \begin{array}{cc} 0 & D \end{array} \right) _{\overline{\Delta}_{i,1}} & W_{i,1} \end{array} \right) \textrm{ and}\] \[\left( \begin{array}{c} B \\ C \\ D \end{array} \right)_{\overline{\Delta}_{i,j} \cup \Delta_{i,j}} \cdot E_{i,j} = \left( \begin{array}{cc} \left( \begin{array}{c} B \\ C \end{array} \right)_{\overline{\Delta}_{i,j}} & 0 \\ D_{\overline{\Delta}_{i,j}} & W_{i,j} \end{array} \right), \textrm{ for } j \geq 2,\] for some \(W_{i,j} \in \mathbb{F}_q^{h \times |\Delta_{i,j}|}\) for \(j \in [N]\) and \(i \in [g]\). More concretely, using a suitable ordering of \(\overline{\Delta}_{i,j} \cup \Delta_{i,j}\), the matrices \(E_{i,j}\) are given by \[E_{i,1} = \left( \begin{array}{cc} I_{\delta-1} & - \left( \begin{array}{cc} I_t & B \\ 0 & C \end{array} \right)_{\overline{\Delta}_{i,1}}^{-1} \left( \begin{array}{cc} I_t & B \\ 0 & C \end{array} \right)_{\Delta_{i,1}} \\ 0 & I_{|\Delta_{i,1}|} \end{array} \right) ,\] and similarly for \(E_{i,j}\) (simply remove the columns corresponding to \(I_t\)), for \(j \in [N]\) and \(i \in [g]\).

Hence, using a suitable ordering of \(\overline{\Delta}_i \cup \Delta_i\), we have \[\left( \begin{array}{cc} P_{\overline{\Delta}_i \cup \Delta_i} \\ Q_{\overline{\Delta}_i \cup \Delta_i} \end{array} \right) \cdot \left( \begin{array}{cccc} E_{i,1} & 0 & \ldots & 0 \\ 0 & E_{i,2} & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & E_{i,N} \end{array} \right) =\] \[\left( \begin{array}{cc|cc|c|cc} \left( \begin{array}{cc} I_t & B \\ 0 & C \end{array} \right)_{\overline{\Delta}_{i,1}} & 0 & 0 & 0 & \ldots & 0 & 0 \\ \hline \left( \begin{array}{cc} I_t & 0 \\ 0 & 0 \end{array} \right)_{\overline{\Delta}_{i,1}} & F_i & \left( \begin{array}{c} B \\ C \end{array} \right)_{\overline{\Delta}_{i,2}} & 0 & \ldots & 0 & 0 \\ \hline \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \hline \left( \begin{array}{cc} I_t & 0 \\ 0 & 0 \end{array} \right)_{\overline{\Delta}_{i,1}} & F_i & 0 & 0 & \ldots & \left( \begin{array}{c} B \\ C \end{array} \right)_{\overline{\Delta}_{i,N}} & 0 \\ \hline \left( \begin{array}{cc} 0 & D \end{array} \right)_{\overline{\Delta}_{i,1}} & W_{i,1} & 0 & 0 & \ldots & 0 & 0 \\ 0 & 0 & D_{\overline{\Delta}_{i,2}} & W_{i,2} & \ldots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \ldots & D_{\overline{\Delta}_{i,N}} & W_{i,N} \end{array} \right), \label{eq32big32matrix}\tag{3}\] for certain (possibly nonzero) matrices \[F_i = \left( \begin{array}{cc} I_t & 0 \\ 0 & 0 \end{array} \right)_{\Delta_{i,1}} - \left( \begin{array}{cc} I_t & 0 \\ 0 & 0 \end{array} \right)_{\overline{\Delta}_{i,1}} \left( \begin{array}{cc} I_t & B \\ 0 & C \end{array} \right)_{\overline{\Delta}_{i,1}}^{-1} \left( \begin{array}{cc} I_t & B \\ 0 & C \end{array} \right)_{\Delta_{i,1}} \in \mathbb{F}_q^{(\delta - 1) \times |\Delta_{i,1}|} , \label{eq32def32F95123i44j125}\tag{4}\] for \(i \in [g]\). Since \(\left( \begin{array}{cc} P_{\overline{\Delta}_i \cup \Delta_i} \\ Q_{\overline{\Delta}_i \cup \Delta_i} \end{array} \right)\) has full column rank \(|\overline{\Delta}_i \cup \Delta_i |\) (which is its number of columns) and multiplying by \({\rm diag}(E_{i,1},E_{i,2},\) \(\ldots, E_{i,N})\) on the right is an invertible linear transformation of such columns, then the matrix in (3 ) is also of full column rank \(|\overline{\Delta}_i \cup \Delta_i |\).

Next, since the matrices \(\left( \begin{array}{c} B \\ C \end{array} \right)_{\overline{\Delta}_{i,j}}\) are invertible, for \(j \in [2,N]\), by further elementary \(\mathbb{F}_q\)-linear column operations, we may construct invertible matrices \(M_i \in \mathbb{F}_q^{|\overline{\Delta}_i \cup \Delta_i| \times |\overline{\Delta}_i \cup \Delta_i|}\) such that \[\left( \begin{array}{cc} P_{\overline{\Delta}_i \cup \Delta_i} \\ Q_{\overline{\Delta}_i \cup \Delta_i} \end{array} \right) \cdot \left( \begin{array}{cccc} E_{i,1} & 0 & \ldots & 0 \\ 0 & E_{i,2} & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & E_{i,N} \end{array} \right) \cdot M_i =\] \[\left( \begin{array}{cc|cc|c|cc} \left( \begin{array}{cc} I_t & B \\ 0 & C \end{array} \right)_{\overline{\Delta}_{i,1}} & 0 & 0 & 0 & \ldots & 0 & 0 \\ \hline \left( \begin{array}{cc} I_t & 0 \\ 0 & 0 \end{array} \right)_{\overline{\Delta}_{i,1}} & 0 & \left( \begin{array}{c} B \\ C \end{array} \right)_{\overline{\Delta}_{i,2}} & 0 & \ldots & 0 & 0 \\ \hline \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \hline \left( \begin{array}{cc} I_t & 0 \\ 0 & 0 \end{array} \right)_{\overline{\Delta}_{i,1}} & 0 & 0 & 0 & \ldots & \left( \begin{array}{c} B \\ C \end{array} \right)_{\overline{\Delta}_{i,N}} & 0 \\ \hline \left( \begin{array}{cc} 0 & D \end{array} \right)_{\overline{\Delta}_{i,1}} & W_{i,1} & 0 & 0 & \ldots & 0 & 0 \\ 0 & V_{i,2} & D_{\overline{\Delta}_{i,2}} & W_{i,2} & \ldots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & V_{i,N} & 0 & 0 & \ldots & D_{\overline{\Delta}_{i,N}} & W_{i,N} \end{array} \right), \label{eq32big32matrix322}\tag{5}\] for some matrices \(V_{i,2}, \ldots, V_{i,N} \in \mathbb{F}_q^{h \times |\Delta_{i,1}|}\), for \(i \in [g]\). Since the matrices in (2 ) are invertible and those in (5 ) have full column rank \(|\overline{\Delta}_i \cup \Delta_i|\), we conclude that \[W_i = \left( \begin{array}{ccccc} W_{i,1} & 0 & 0 & \ldots & 0 \\ V_{i,2} & W_{i,2} & 0 & \ldots & 0 \\ V_{i,3} & 0 & W_{i,3} & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ V_{i,N} & 0 & 0 & \ldots & W_{i,N} \end{array} \right) \in \mathbb{F}_q^{(hN) \times |\Delta_i|}\] is of full column rank \(|\Delta_i|\), for \(i \in [g]\).

Finally, using a suitable ordering of \(\overline{\Delta}_i \cup \Delta_i\) and defining the invertible matrices \(N_i = {\rm diag}(E_{i,1},E_{i,2}, \ldots, E_{i,N}) M_i \in \mathbb{F}_q^{|\overline{\Delta}_i \cup \Delta_i| \times |\overline{\Delta}_i \cup \Delta_i|}\), we have \[H|_\mathcal{E} \cdot {\rm diag}(N_1, N_2, \ldots, N_g) =\] \[\left( \begin{array}{ccccccc} P_{\overline{\Delta}_1} & 0 & 0 & 0 & \ldots & 0 & 0 \\ 0 & 0 & P_{\overline{\Delta}_2} & 0 & \ldots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 &\ldots & P_{\overline{\Delta}_g} & 0 \\ G_1 Q_{\overline{\Delta}_1} & G_1W_1 & G_2 Q_{\overline{\Delta}_2} & G_2W_2 & \ldots & G_g Q_{\overline{\Delta}_g} & G_gW_g \end{array} \right).\] Since the matrices \(P_{\overline{\Delta}_i}\) are invertible, we conclude that \(H|_\mathcal{E}\) is invertible if, and only if, \[(G_1W_1| G_2W_2| \ldots |G_gW_g) = (G_1|G_2|\ldots|G_g) {\rm diag}(W_1,W_2,\ldots,W_g) \in \mathbb{F}_{q^m}^{h \times h}\] is invertible, which holds by Lemma 1 since \(\mathcal{C}_{out}\) is MSRD for the length partition \((g,hN)\) and \(W_i \in \mathbb{F}_q^{(hN) \times |\Delta_i|}\) is of full column rank \(|\Delta_i|\), for \(i \in [g]\), and we are done. ◻

Proof. Let \(\mathcal{E} \subseteq [n]\) be such that \(|\mathcal{E}| \leq \ell\) and \(|\mathcal{E}| - {\rm Rk}(P|_\mathcal{E}) \leq h\). If we denote by \[\ker(P^+|_\mathcal{E}) = \left\lbrace \mathbf{c} \in \mathbb{F}_{q^m}^{|\mathcal{E}|} : (P^+|_\mathcal{E}) \mathbf{c}^\intercal = \mathbf{0} \right\rbrace \subseteq \mathbb{F}_{q^m}^{|\mathcal{E}|}\] the right kernel of \(P^+|_\mathcal{E} \in \mathbb{F}_{q^m}^{|\mathcal{E}|}\), then we need to prove that \(\dim(\ker(P^+|_\mathcal{E})) = 0\), or equivalently, \(P^+|_\mathcal{E}\) has maximum rank, \({\rm Rk}(P^+|_\mathcal{E}) = |\mathcal{E}|\). This is because, in that case, there would be a unique solution to a linear system of equations with coefficient matrix \(P^+|_\mathcal{E}\), i.e., a unique way to correct the erasures.

Fix \(i \in [g]\). Let \(\mathcal{E}_i = \mathcal{E} \cap R_i\) (with notation as in Definition 1), which may be considered as a subset of \([t+N(r+\delta -1-t)]\) by a translation since \(|R_i| = t+N(r+\delta -1-t)\). Let also \(e_i = {\rm Rk}(P_0|_{\mathcal{E}_i}) \leq |\mathcal{E}_i|\). After possibly reordering the rows of \(P_0|_{\mathcal{E}_i}\), we may assume that its first \(e_i\) rows are linearly independent (this does not change the proof but simplifies the notation). Then there exists an invertible matrix \(A_i \in \mathbb{F}_q^{|\mathcal{E}_i| \times |\mathcal{E}_i|}\) such that \[P_0|_{\mathcal{E}_i} \cdot A_i = \left( \begin{array}{c|c} P_i & 0_{e_i \times (|\mathcal{E}_i|-e_i)} \\ \hline P_i^\prime & P_i^{\prime \prime} \\ \end{array} \right) \in \mathbb{F}_q^{(N(\delta-1)) \times |\mathcal{E}_i|} ,\] for an invertible matrix \(P_i \in \mathbb{F}_q^{e_i \times e_i}\), and for other (possibly not of full rank) matrices \(P_i^\prime \in \mathbb{F}_q^{(N(\delta-1) - e_i) \times e_i}\) and \(P_i^{\prime \prime} \in \mathbb{F}_q^{(N(\delta-1) - e_i) \times (|\mathcal{E}_i|-e_i)}\).

Now if we set \(A = {\rm diag}(A_1, A_2, \ldots, A_g) \in \mathbb{F}_q^{|\mathcal{E}| \times |\mathcal{E}|}\), which is invertible, we have that \[P^+|_\mathcal{E} \cdot A = \left( \begin{array}{c} P|_\mathcal{E} \\ Q|_\mathcal{E} \end{array} \right) \cdot A = \left( \begin{array}{cc|cc|c|cc} P_1 & 0 & 0 & 0 & \ldots & 0 & 0 \\ P_1^\prime & P_1^{\prime \prime} & 0 & 0 & \ldots & 0 & 0 \\ \hline 0 & 0 & P_2 & 0 & \ldots & 0 & 0 \\ 0 & 0 & P_2^\prime & P_2^{\prime \prime} & \ldots & 0 & 0 \\ \hline \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \hline 0 & 0 & 0 & 0 & \ldots & P_g & 0 \\ 0 & 0 & 0 & 0 & \ldots & P_g^\prime & P_g^{\prime \prime} \\ \hline \multicolumn{2}{c|}{(Q_1|_{\mathcal{E}_1})A_1} & \multicolumn{2}{c|}{(Q_2|_{\mathcal{E}_2})A_2} & \ldots & \multicolumn{2}{c}{(Q_g|_{\mathcal{E}_g})A_g} \end{array} \right) \in \mathbb{F}_{q^m}^{(gN(\delta-1)+h) \times |\mathcal{E}|} .\] Now, since \(|\mathcal{E}_i| \leq |\mathcal{E}| \leq \ell\), for all \(i \in [g]\), and \(\mathcal{S} = \{ \beta_1, \beta_2, \ldots, \beta_{n/g} \} \subseteq \mathbb{F}_{q^m}\) is \(\ell\)-wise \(\mathbb{F}_q\)-linearly independent, then the matrix \[Q|_\mathcal{E} = ((Q_1|_{\mathcal{E}_1})|(Q_2|_{\mathcal{E}_2})|\ldots|(Q_g|_{\mathcal{E}_g})) \in \mathbb{F}_{q^m}^{h \times |\mathcal{E}|}\] generates a linearized Reed–Solomon code (Definition 13), which is MSRD (Definition 11) by Theorem 2. As a consequence, by Lemma 1, we deduce that the matrix \[Q|_\mathcal{E} \cdot A = ((Q_1|_{\mathcal{E}_1})A_1|(Q_2|_{\mathcal{E}_2})A_2|\ldots|(Q_g|_{\mathcal{E}_g})A_g) \in \mathbb{F}_{q^m}^{h \times |\mathcal{E}|}\] generates an MDS code of dimension \(\min\{h, |\mathcal{E}|\}\). Next, since \[\sum_{i=1}^g (|\mathcal{E}_i| - e_i) = |\mathcal{E}| - {\rm Rk}(P|_\mathcal{E}) \leq h\] by hypothesis, then any \(|\mathcal{E}| - {\rm Rk}(P|_\mathcal{E})\) columns of \(Q|_\mathcal{E} \cdot A\) are linearly independent. Therefore, the matrix \(P^+|_\mathcal{E} \cdot A\) contains the following submatrix of full column rank \(|\mathcal{E}|\), \[\left( \begin{array}{cc|cc|c|cc} P_1 & 0 & 0 & 0 & \ldots & 0 & 0 \\ 0 & 0 & P_2 & 0 & \ldots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \ldots & P_g & 0 \\ \hline \multicolumn{2}{c|}{(Q_1|_{\mathcal{E}_1})A_1} & \multicolumn{2}{c|}{(Q_2|_{\mathcal{E}_2})A_2} & \ldots & \multicolumn{2}{c}{(Q_g|_{\mathcal{E}_g})A_g} \end{array} \right) \in \mathbb{F}_{q^m}^{({\rm Rk}(P|_\mathcal{E}) + h) \times |\mathcal{E}|} .\] In particular, \({\rm Rk}(P^+|_\mathcal{E} \cdot A) = |\mathcal{E}|\). Since \(A\) is invertible and \(|\mathcal{E}|\) is the number of columns of \(P^+\), we conclude that \({\rm Rk}(P^+|_\mathcal{E}) = {\rm Rk}(P^+|_\mathcal{E} \cdot A) = |\mathcal{E}|\), as we wanted to prove. ◻

Proof. Let the notation, the code \(\mathcal{C}_{glob}\) and the parameters \(r\), \(\delta\), \(t\), \(g\), \(h\) and \(N\) be as in Construction 3. We need to specify the matrix \(A\) (in order to specify the matrix \(P\)) and the set \(\mathcal{S} = \{ \beta_1, \beta_2, \ldots, \beta_{n/g} \}\) (in order to specify the matrix \(Q\)). The elements \(a_1, a_2, \ldots, a_g \in \mathbb{F}_{q^m}^*\) can be chosen arbitrarily such that \(N_{\mathbb{F}_{q^m}/\mathbb{F}_q}(a_i) \neq N_{\mathbb{F}_{q^m}/\mathbb{F}_q}(a_j)\), if \(i \neq j\), which imposes the restriction \(q \geq g+1\).

First, choose \(A\) as the generator matrix of a doubly extended Reed–Solomon code [18], which imposes the restriction \(q \geq r+\delta-1\). If we choose \(q = \mathcal{O}(\max \{ g+1, r+\delta-1 \})\), then both restrictions on \(q\) are satisfied.

Now that \(P\) is specified, set \(\ell = gN(\delta-1) + h\) and let \(\widetilde{H} \in \mathbb{F}_{q^s}^{\ell \times (n/g)}\) be the parity-check matrix of another doubly extended Reed–Solomon code, which this time imposes the condition \(q^s \geq n/g - 1\), i.e., \(s \geq \log_q(n/g -1)\). Set \(m = s \ell\) and let \(\alpha_1, \alpha_2, \ldots, \alpha_m \in \mathbb{F}_{q^m}\) form a basis of \(\mathbb{F}_{q^m}\) over \(\mathbb{F}_q\). If \(H \in \mathbb{F}_q^{(s\ell) \times (n/g)}\) denotes the matrix obtained by expanding every entry of \(\widetilde{H}\) column-wise over \(\mathbb{F}_q\), then \(H\) is the parity-check matrix of an \(\mathbb{F}_q\)-linear code of minimum Hamming distance at least \(\ell + 1\) and length \(n/g\). Define now \[(\beta_1, \beta_2, \ldots, \beta_{n/g} ) = (\alpha_1, \alpha_2, \ldots, \alpha_m) \cdot H \in \mathbb{F}_{q^m}^{n/g}.\] Since any \(\ell\) columns of \(H\) are \(\mathbb{F}_q\)-linearly independent (it is the parity-check matrix of a code of minimum hamming distance at least \(\ell+1\)), then \(\mathcal{S} = \{ \beta_1, \beta_2, \ldots, \beta_{n/g} \}\), as defined above, is \(\ell\)-wise \(\mathbb{F}_q\)-linearly independent. Thus the set \(\mathcal{S}\) is also specified, and so is the matrix \(Q\). Thus \(\mathcal{C}_{glob}\) in Construction 3 is explicit with definitions as above.

Next we prove the erasure-correction capabilities of the code \(\mathcal{C}_{glob}\). Exactly in the same way as in Theorem 4, the code \(\mathcal{C}_{glob}\) is an LRC of type \((r,\delta,N,t)\) with \(N\)-availability, and if \(k \leq gt\), it has information \(N\)-availability.

Now we prove that it can correct any simple erasure pattern \(\mathcal{E} \subseteq [n]\) as in Definition 7. That is, \(\mathcal{E} = \mathcal{E}_1 \cup \mathcal{E}_2\), where the union is disjoint, \(\mathcal{E}_1\) is locally correctable (Definition 4) and \(|\mathcal{E}_2| \leq h\). We may assume without loss of generality that \(\mathcal{E}_1\) is of maximum size, i.e., \(|\mathcal{E}_1| = gN(\delta-1)\).

Similarly to the proof of Theorem 4, since \(\mathcal{E}_1\) is locally correctable and by the shape of matrix \(P\) and the fact that \(A\) generates an MDS matrix, we have that \[{\rm Rk}(P|_{\mathcal{E}_1}) = gN(\delta-1).\] Therefore we have \[|\mathcal{E}| - {\rm Rk}(P|_{\mathcal{E}}) \leq gN(\delta-1)+h - {\rm Rk}(P|_{\mathcal{E}_1}) \leq h.\] Moreover, since \(|\mathcal{E}_1| = gN(\delta-1)\), \(|\mathcal{E}_2| \leq h\) and \(\ell = gN(\delta-1) + h\), then \[|\mathcal{E}| = |\mathcal{E}_1| + |\mathcal{E}_2| \leq gN(\delta-1) + h = \ell.\] Hence, by Theorem 5, the erasure pattern \(\mathcal{E}\) is correctable, and we have proven that \(\mathcal{C}_{glob}\) can correct any simple erasure pattern as in Definition 7.

Finally, we upper bound the field size \(q^m\). If we choose \(q^s = \mathcal{O}( n/g - 1)\), then \[q^m = q^{s \ell} = \mathcal{O}\left( \frac{n}{g}-1 \right)^\ell = \mathcal{O}\left( \frac{n}{g}-1 \right)^{gN(\delta-1) + h}.\] ◻

Proof. By Definition 1, the code \(\mathcal{C}\) must have a parity-check matrix of the form \[H = \left( \begin{array}{cccc} P_1 & 0 & \ldots & 0 \\ 0 & P_2 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & P_g \\ Q_1 & Q_2 & \ldots & Q_g \end{array} \right) \in \mathbb{F}^{(gN(\delta-1)+h) \times n},\] where \(P_i \in \mathbb{F}^{(N(\delta-1)) \times (t + N(r+\delta-1-t))}\), \(Q_i \in \mathbb{F}^{h \times (t + N(r+\delta-1-t))}\), for \(i \in [g]\), the length of \(\mathcal{C}\) is \(n = g(t + N(r+\delta -1-t))\) and its dimension is \(k = n - gN(\delta-1) - h\).

Consider the family \(\mathcal{S}\) of subsets \(S \subseteq [t + N(r+\delta-1-t)]\) of size \(a+1\) such that, for all \(s \in S\), the erasure pattern \(S \setminus \{ s \}\) is locally correctable in each block \(R_i\), for \(i \in [g]\), which means that there exists \(j \in [N]\) such that

1. \(|(S\setminus \{s\}) \cap R_{1,j}| = \delta - 1\), and

2. \(|(R_{1,\ell} \setminus T_1) \cap (S\setminus \{s\})| = \delta - 1\), for all \(\ell \in [N] \setminus \{ j \}\).

(See (1 ) and Definition 4, and notice that \(S\) may be translated to the subset \(R_i\), for all \(i \in [g]\), and it satisfies the same properties as above for every \(R_i\).) In particular, since \(S\setminus \{s\}\) is locally correctable in the block \(R_i\), we have that \(P_i|_{S\setminus \{s\}} \in \mathbb{F}^{a \times a}\) is invertible, for all \(s \in S\). In other words, any \(a \times a\) submatrix of \(P_i|_S \in \mathbb{F}^{a \times (a+1)}\) is invertible, which means that the code it generates is MDS.

The remainder of the proof will follow the steps of [5] (the case \(N = 1\)). However, in that case, \(\mathcal{S}\) was formed by any subset of size \(a+1\), whereas this is far from the case in this proof. Later we will need to lower bound the size \(|\mathcal{S}|\), but we skip this step for now.

For each \(S \in \mathcal{S}\), let \(P_{i,S}^\perp \in \mathbb{F}^{(a+1) \times 1}\) be a nonzero column matrix such that \(P_i|_S \cdot P_{i,S}^\perp = 0\). Note that \(P_{i,S}^\perp\) is unique up to multiplication by a scalar in \(\mathbb{F}\), since \(P_i|_S \in \mathbb{F}^{a \times (a+1)}\) is of full rank \(a\). Furthermore, every entry of \(P_{i,S}^\perp\) is nonzero since its transpose generates a one-dimensional MDS code (the dual of an MDS code is again MDS [18]). Define also \[p_{i,S} = Q_i|_S \cdot P_{i,S}^\perp \in \mathbb{F}^{h \times 1},\] for \(i \in [g]\) and \(S \in \mathcal{S}\). We have the following:

In particular, \(p_{i,S}\) and \(p_{j,T}\) are not scalar multiples of each other for any subsets \(S,T \subseteq \mathcal{S}\) (even if \(S=T\)), for distinct \(i,j \in [g]\) (note that this requires \(h \geq 2\)). We next show that the same holds for \(p_{i,S}\) and \(p_{i,T}\) for distinct \(S,T \subseteq \mathcal{S}\).

In conclusion, by Claims 16 and 17 (which use the assumptions \(a+2 \leq h \leq g\)), no two vectors \(p_{i,S}\) and \(p_{j,T}\), for \(i,j \in [g]\) and \(S,T \subseteq \mathcal{S}\), are scalar multiples of each other, that is, they define different projective points in \(\mathbb{P}^{h-1}_\mathbb{F}\), unless \((i,S) = (j,T)\). Define now \(X_i = \{ p_{i,S} : S \subseteq \mathcal{S} \}\), for \(i \in [g]\). Then \(|X_i| = |\mathcal{S}|\), for \(i \in [g]\), and \(X_1, \ldots, X_g \subseteq \mathbb{P}^{h-1}_\mathbb{F}\) are pairwise disjoint. By Claim 16, there is no hyperplane in \(\mathbb{P}^{h-1}_\mathbb{F}\) that contains \(h\) points from distinct subsets among \(X_1, \ldots, X_g\). Therefore, by Lemma 2, \[|\mathbb{F}| \geq \left( \frac{g}{h-1} - 1 \right) \cdot |\mathcal{S}| - 4. \label{eq32lower32bound32field32size32proof321}\tag{8}\] The only step left is finding a lower bound on \(|\mathcal{S}|\). Consider \(\mathcal{T}\) as the collection of subsets \(S \subseteq [t+N(r+\delta-1-t)]\) formed by one element in \(T_1\) and any \(\delta-1\) elements in \(R_{1,j}\setminus T_1\), for every \(j \in [N]\) (recall the notation from (1 )). We now check that \(S \in \mathcal{S}\), for all \(S \in \mathcal{T}\). First we observe that \(|S| = N(\delta-1)+1 = a+1\). Next, let \(s \in S\). If \(s \in T_1\), then \(S\setminus \{ s \}\) is formed by a disjoint union of subsets of \(R_{1,j}\setminus T_1\), for \(j \in [N]\), each of size \(\delta-1\). Thus \(S \setminus \{s \}\) is clearly locally correctable (Definition 4). Now assume that \(s \in R_{1,j}\), for some \(j \in [N]\). Then \(|(S\setminus \{s\}) \cap R_{1,j}| = \delta - 1\) and, therefore, \(|(R_{1,\ell} \setminus T_1) \cap (S\setminus \{s\})| = \delta - 1\), for all \(\ell \in [N] \setminus \{ j\}\). Thus \(S \setminus \{s\}\) is also locally correctable. In conclusion, \(S \in \mathcal{S}\). That is, \(\mathcal{T} \subseteq \mathcal{S}\) and \[|\mathcal{S}| \geq |\mathcal{T}| \geq t \binom{r+\delta-1-t}{\delta - 1}^N.\] Combining this lower bound with (8 ), we obtain (?? ), and we are done. ◻

Proof. As done in [5], we only need to adjust the proof of Proposition 15, as follows. Let the notation be as in that proof, set \(\ell = \delta - 1 - \lfloor (h-2)/N \rfloor\), and consider subsets \(S_j \subseteq R_{1,j} \setminus T_1 \subseteq [t+N(r+\delta -1-t)]\) of size \(|S_j| = \ell\), for \(j \in [N]\) (this is possible since \(\ell \leq \delta - 1 \leq |R_{1,j}\setminus T_1|\) by Definition 1). Consider the subfamily \(\mathcal{S}^\prime \subseteq \mathcal{T}\) formed by the sets \(S \in \mathcal{T}\) such that \(S_j \subseteq S\), for all \(j \in [N]\).

In the proof of Proposition 15, the only step where we used \(a+2 \leq h\) was in the proof of Claim 17, to show that \(|S\cup T| \leq 2a+2 \leq a+h\), for any two distinct \(S,T \in \mathcal{S}\). Now we do not have that \(2a+2 \leq a+h\). However, since \[\begin{align} \bigcup_{j=1}^N S_j & \subseteq S \cap T, \textrm{ and} \\ \left| \bigcup_{j=1}^N S_j \right| & = \ell N \geq N(\delta - 1) - (h-2) = a-h+2 , \end{align}\] then we still have that \[|S \cup T| = |S|+|T|-|S\cap T| = 2a+2 - |S\cap T| \leq a+h,\] for any two distinct \(S,T \subseteq \mathcal{S}^\prime\). The remainder of the proof is exactly as that of Proposition 15. However, we need to replace the collection \(\mathcal{T}\) by \(\mathcal{S}^\prime\). Since \[|\mathcal{S}^\prime| = t \binom{r+\delta -1-t -\ell}{\delta -1 -\ell}^N = t \binom{r + \left\lfloor \frac{h-2}{N} \right\rfloor -t}{\left\lfloor \frac{h-2}{N} \right\rfloor}^N ,\] the bound (?? ) follows. ◻

Proof. Combine (?? ) and (?? ), together with the inequality \(\binom{u}{v} \geq (u/v)^v\), for integers \(0 \leq v \leq u\), and recall that \(h\), \(\delta\) and \(N\) are considered as constants. ◻