# Locally repairable convertible codes with optimal access costs

Xiangliang Kong Xiangliang Kong is with the Department of Electrical
Engineering-Systems, Tel Aviv University, Tel Aviv-Yafo 6997801, Israel
(rongxlkong@gmail.com). This work was supported by the European Research
Council (ERC) under Grant 852953.

###### Abstract

Modern large-scale distributed storage systems use erasure codes to protect
against node failures with low storage overhead. In practice, the failure rate
and other factors of storage devices in the system may vary significantly over
time, and leads to changes of the ideal code parameters. To maintain the
storage efficiency, this requires the system to adjust parameters of the
currently used codes. The changing process of code parameters on encoded data
is called code conversion.

As an important class of storage codes, locally repairable codes (LRCs) can
repair any codeword symbol using a small number of other symbols. This feature
makes LRCs highly efficient for addressing single node failures in the storage
systems. In this paper, we investigate the code conversions for locally
repairable codes in the merge regime. We establish a lower bound on the access
cost of code conversion for general LRCs and propose a general construction of
LRCs that can perform code conversions with access cost matching this bound.
This construction provides a family of LRCs together with optimal conversion
process over the field of size linear in the code length.

##  I Introduction

Large-scale cluster storage systems employ erasure codes to protect against
node failures with low storage overhead [1, 2, 3]. In such scenarios, a set of
$k$ data symbols is encoded as a codeword of length $n$ using an $[n,k]$ code
and the $n$ codeword symbols are distributed across $n$ different storage
nodes. The ratio $\frac{k}{n}$, referred to as the code rate, is chosen
according to the failure rate of storage devices. In practice, the failure
rate of storage devices in large-scale storage systems vary significantly over
time. However, the rate of the erasure code employed in the system usually
remains fixed. Consequently, as time goes by, storage systems utilizing
erasure codes with static rates will either be overly resource-consuming,
overly risky, or a mix of the two. To address this problem, [4] shows that
changing the code rate over time in response to the variations of failure
rates of storage devices yields substantial savings in storage space and
operating costs. In this approach, one need to convert already-encoded data
from an $[n^{I},k^{I}]$ code to its encoding under another code with different
parameters $[n^{F},k^{F}]$. This process is known as _code conversion_ [5],
the code with parameters $[n^{I},k^{I}]$ is called the _initial code_ and the
code with parameters $[n^{F},k^{F}]$ is called the _final code_.

The default approach for code conversion is to re-encode the data from the
initial code according to the finial code. However, such an approach requires
accessing a large number of symbols, decoding the entire data, transferring
the data over the network and then re-encoding it. This causes substantial I/O
load and adversely affects the efficiency of the system [6]. In the pursuit of
designing codes that allow for efficient code conversions, Maturana and Rashmi
introduced _convertible codes_ [5]. Their work, along with subsequent
studies[7, 8, 9], focused on conversions of MDS codes and MDS array codes, and
obtained several fundamental results in the theoretical study of code
conversions for storage codes.

As another important storage codes, locally repairable codes (LRCs) can repair
any codeword symbol using only a small number of other symbols. More formally,
an $(n,k,r)$ LRC is a code that produces an $n$-symbol codeword from $k$
information symbols, such that for any symbol within the codeword, one can use
at most $r$ other symbols to recover it. This feature makes LRCs notably
efficient for large-scale storage systems, particularly in scenarios involving
single node failures. Due to their applications in distributed and cloud
storage systems, LRCs have become one of the rapidly developing topics in
coding theory over the past decade. The study of LRCs encompasses a broad
range of topics, including constructions (e.g., [10, 11, 12, 13, 14, 15]),
bounds (e.g., [16, 17, 18, 19, 20, 21]), and diverse variations (e.g., [22,
23, 24, 25, 26, 27, 28]).

In this paper, we focus on code conversion problem for LRCs in the merge
regime. The merge regime corresponds to conversions where multiple codewords
are merged into a single codeword. Specifically, we establish a lower bound on
the number of accessed symbols during the conversion process for general LRCs
in the merge regime, and we propose a general construction of LRCs that can
perform code conversions with access cost matching this bound. It’s noteworthy
that during the preparation of this paper, Maturana and Rashmi [9] studied
conversion problem for LRCs with information locality. Based on piggybacking
frameworks, they proposed a construction technique for designing LRCs that can
perform code conversion at a lower cost than the default approach. In contrast
to their work, we focus on LRCs with all-symbol locality. Moreover, our
construction is from the algebraic coding perspective, and it explicitly
provides a family of LRCs together with optimal conversion process over the
field of size linear in the code length.

###  I-A The Setup and Related Results

Before formally defining and discussing the code conversion problem for LRCs,
we begin with the basic definition and bounds for LRCs.

For positive integers $n$ and $1\leq a<b\leq n$, we denote $[n]$ as the set of
integers $\\{1,2,\ldots,n\\}$ and $[a,b]$ as $\\{a,a+1,\ldots,b\\}$. Let $q$
be a prime power, we denote $\mathbb{F}_{q}$ as the finite field of $q$
elements. We say that $\mathcal{C}$ is an $(n,k)_{q}$ code if
$\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ and $|\mathcal{C}|=q^{k}$. For a
vector $\mathbf{v}\in\mathbb{F}_{q}^{n}$ and a subset $S\subseteq[n]$, we
denote $\mathbf{v}|_{S}$ as the vector obtained by removing the coordinates
outside $S$. Let $\mathcal{C}$ be an $(n,k)_{q}$ code and $S$ be a subset of
$[n]$, the restriction of $\mathcal{C}$ to $S$ is defined as
$\mathcal{C}|_{S}=\\{\mathbf{c}|_{S}:\mathbf{c}\in\mathcal{C}\\}$.

######  Definition I.1.

(Locally repairable codes, [16, 29]) Let $r\leq k\leq n$ be positive integers.
We say that a code $\mathcal{C}$ with parameters $(n,k)$ over alphabet
$\Sigma$ has locality $r$ if for every codeword $\mathbf{c}\in\mathcal{C}$ and
every $i\in[n]$, there exists a subset of coordinates
$I_{i}\subset[n]\setminus\\{i\\}$ with $|I_{i}|\leq r$ such that
$\mathbf{c}(i)$ can be recovered by symbols from $\mathbf{c}|_{I_{i}}$. The
subset $I_{i}$ is called a recovering set for $i$ and the $\mathcal{C}$ is
called an _$(n,k,r)$ -LRC_.

As a natural generalization of the classical Singleton bound, [16] and [29]
proved a bound on the minimum distance of an $(n,k,r)$-LRC. Here, we refer to
the version from [11].

######  Theorem I.1.

[11] Let $\mathcal{C}$ be an $(n,k,r)$-LRC of cardinality $|\Sigma|^{k}$ over
alphabet $\Sigma$, then:

  * •

The rate of $\mathcal{C}$ satisfies $\frac{k}{n}\leq\frac{r}{r+1}$.

  * •

The minimum distance of $\mathcal{C}$ satisfies $d\leq
n-k-\lceil\frac{k}{r}\rceil+2$.

Moreover, an $(n,k,r)$-LRC that achieves the bound on the distance with
equality is called an optimal LRC.

Next, we present the formal framework introduced in [5] for studying code
conversions.

Let the _initial code_ $\mathcal{C}^{I}$ be an $(n^{I},k^{I})_{q}$ code and
the _final code_ $\mathcal{C}^{F}$ be an $(n^{F},k^{F})_{q}$ code. Consider a
message vector of length $M=lcm(k^{I},k^{F})$ over $\mathbb{F}_{q}$, denoted
by $\mathbf{m}\in\mathbb{F}_{q}^{M}$. Clearly, to encode $\mathbf{m}$, we need
$\lambda^{I}=M/k^{I}$ codewords in $\mathcal{C}^{I}$ and $\lambda^{F}=M/k^{F}$
codewords in $\mathcal{C}^{F}$. To specify the information encoded in the
codewords involved in conversion process, we define partitions
$\mathcal{P}^{I}$ and $\mathcal{P}^{F}$ of $[M]$ as:
$\mathcal{P}^{I}=\\{P_{1}^{I},\ldots,P_{\lambda_{I}}^{I}\\}$ consists of
$\lambda_{I}$ disjoint subsets, each of size $k^{I}$ and
$\mathcal{P}^{F}=\\{P_{1}^{F},\ldots,P_{\lambda_{F}}^{F}\\}$ consists of
$\lambda_{F}$ disjoint subsets, each of size $k^{F}$. Then, for every
$i\in[\lambda^{I}]$, denote
$\mathbf{c}_{i}=\mathcal{C}^{I}(\mathbf{m}|_{P_{i}^{I}})$ as the _initial
codeword_ in $\mathcal{C}^{I}$ that encodes the message in $\mathbf{m}$
indexed by $P_{i}^{I}$ and for every $j\in[\lambda^{F}]$, denote
$\mathbf{d}_{j}=\mathcal{C}^{F}(\mathbf{m}|_{P_{j}^{F}})$ as the _final
codeword_ in $\mathcal{C}^{F}$ that encodes the message in $\mathbf{m}$
indexed by $P_{j}^{F}$. Then, the conversion procedure from $\mathcal{C}^{I}$
to $\mathcal{C}^{F}$ is defined as follows.

######  Definition I.2.

(Code Conversion, [5]) A _conversion_ from the initial code $\mathcal{C}^{I}$
to the final code $\mathcal{C}^{F}$ with initial partition $\mathcal{P}^{I}$
and the final partition $\mathcal{P}^{F}$ is a procedure, denoted by
$T_{\mathcal{C}^{I}\rightarrow\mathcal{C}^{F}}$, that for any
$\mathbf{m}\in\mathbb{F}_{q}^{M}$, takes the set of initial codewords
$\\{\mathbf{c}_{i}:1\leq i\leq\lambda^{I}\\}$ that encodes $\mathbf{m}$ as
inputs, and output the set of final codewords $\\{\mathbf{d}_{i}:1\leq
i\leq\lambda^{F}\\}$ that encodes $\mathbf{m}$.

######  Definition I.3.

(Convertible Code, [5]) An $(n^{I},k^{I};n^{F},k^{F})$ convertible code over
$\mathbb{F}_{q}$ is defined by:

  * 1.

A pair of codes $(\mathcal{C}^{I},\mathcal{C}^{F})$ where $\mathcal{C}^{I}$ is
an $(n^{I},k^{I})_{q}$ code and $\mathcal{C}^{F}$ is an $(n^{F},k^{F})_{q}$
code.

  * 2.

A pair of partitions $\mathcal{P}^{I}$ and $\mathcal{P}^{F}$ of $[M]$
($M=lcm(k^{I},k^{F})$) such that each subset in $\mathcal{P}^{I}$ is of size
$k^{I}$ and each subset in $\mathcal{P}^{F}$ is of size $k^{F}$.

  * 3.

A conversion procedure $T_{\mathcal{C}^{I}\rightarrow\mathcal{C}^{F}}$ that on
input $\\{\mathbf{c}_{i}:1\leq i\leq\lambda^{I}\\}$ outputs
$\\{\mathbf{d}_{i}:1\leq i\leq\lambda^{F}\\}$.

When both $\mathcal{C}^{I}$ and $\mathcal{C}^{F}$ are MDS codes, the
corresponding convertible code $(\mathcal{C}^{I},\mathcal{C}^{F})$ is called
an MDS convertible code. When $\mathcal{C}^{I}$ is an LRC with parameters
$(n^{I},k^{I},r^{I})$ and $\mathcal{C}^{F}$ is an LRC with parameters
$(n^{F},k^{F},r^{F})$, the corresponding convertible code
$(\mathcal{C}^{I},\mathcal{C}^{F})$ is called an locally repairable
convertible code (LRCC) with parameters
$(n^{I},k^{I},r^{I};n^{F},k^{F},r^{F})$.

Next, we define the access cost of code conversion, which measures the number
of symbols that are affected by the conversion procedure.

######  Definition I.4.

(Access Cost, [5]) The _read access cost_ and _write access cost_ are defined
as the total number of symbols read and written during the conversion
procedure, respectively. The _access cost_ of a conversion procedure is the
sum of its read and write access costs. The access cost of a convertible code
is the access cost of its conversion procedure.

To specify the transfer of codeword symbols during the conversion, we classify
them into the following three categories:

  * (1)

_remaining symbols_ , which refers to symbols in the initial codewords that
remain as is in the final codewords;

  * (2)

_accessed symbols_ , which refers to symbols of the initial codewords that are
accessed (read);

  * (3)

_new symbols_ , which refers to symbols in the final codewords which are not
remaining from initial codewords.

As two fundamental cases of code conversions, _Merge regime_ and _split
regime_ were introduced in [5] and [30], separately. In the merge regime,
$k^{F}=\zeta k^{I}$ for some integer $\zeta\geq 2$. As consequence, the length
of the message vector $\mathbf{m}$ is $M=lcm(k^{I},k^{F})=k^{F}$. Thus, the
number of initial codewords is $\lambda^{I}=\zeta$ and the number of final
codewords is $\lambda^{F}=1$. In the split regime, $k^{I}=\zeta k^{F}$. Thus,
the number of initial codewords is $\lambda^{I}=1$ and the number of final
codewords is $\lambda^{F}=\zeta$. As shown in [5], in the merge regime, all
pairs of initial and final partitions $(\mathcal{P}^{I},\mathcal{P}^{F})$ are
equivalent. Therefore, in the following context, we always assume that
$\mathcal{P}^{I}=\\{[k^{I}],[k^{I}+1,2k^{I}],\ldots,[(\zeta-1)k^{I}+1,\zeta
k^{I}]\\}$ and $\mathcal{P}^{F}=\\{[\zeta k^{I}]\\}$ for all
$(n^{I},k^{I};n^{F},k^{F}=\zeta k^{I})$ convertible codes.

Maturana and Rashmi [5] proved the following lower bound on the access cost of
linear MDS convertible codes in the merge regime. They also provided two
constructions and showed that this lower bound is optimal. Their construction
for general parameters requires the field size $q$ to be at least
$\Omega(2^{\zeta\cdot(n^{I})^{3}})$. Conditioning on the existence of certain
superregular Hankel arraires, they further reduce this requirement to
$q\geq\max\\{n^{I},n^{F}\\}$ when
$n^{F}-k^{F}\leq\lfloor\frac{n^{I}-k^{I}}{\zeta}\rfloor$.

######  Theorem I.2.

For all linear $(n^{I},k;n^{F},\zeta k)$ MDS convertible codes, the read
access cost of conversion is at least $\zeta\cdot\min\\{k,n^{F}-\zeta k\\}$
and the write access cost is at least $n^{F}-\zeta k$. Further, if
$n^{I}-k<n^{F}-\zeta k$, the read access cost is at least $\zeta k$.

###  I-B Our Contribution

In this paper, we study the code conversion problem of locally repairable
codes in the merge regime. Due to their good error correcting capabilities and
strong connections with MDS codes, we limit our focus on optimal LRCs, that
is, LRCs achieving the bound on the distance in Theorem I.1. In the following
context, the term LRCs will always refer to optimal LRCs unless otherwise
specified.

Below, we summarize the main contributions of this paper.

  * •

First, by establishing proper maps from polynomials of degree at most $k-1$ to
polynomials of degree at most $\zeta k-1$, we proprose a construction of MDS
convertible codes with optimal access costs for general parameters using GRS
codes. As a consequence, we obtain a family of $(n^{I},k;n^{F},\zeta k)$ MDS
convertible codes with optimal access costs over finite field of size linear
in $n^{I}$.

  * •

Second, based on the construction of optimal LRCs through “good polynomials”
in [11], we extend the construction of MDS convertible codes and propose a
construction of LRCCs. Similarly, a family of $(n^{I},k,r;n^{F},\zeta k,r)$
LRCCs over finite field of size linear in $n^{I}$ is obtained.

  * •

Third, we prove a general lower bound on the access cost of an
$(n^{I},k;n^{F},\zeta k)$ convertible code with the condition that the finial
code is an LRC. As a consequence, this shows that the LRCCs obtained in
Section III admit optimal access costs.

###  I-C Notations

Throughout the paper, we use bold lowercase letters to represent vectors and
bold uppercase letters to represent matrices. We use $\mathbf{I}_{r}$ to
denote the identity matrix of order $r$ and the subscript “$r$” is usually
omitted if it’s clear from the context. We use $(a_{i,j})_{1\leq i\leq m\atop
1\leq j\leq n}$ to denote the $m\times n$ matrix with $a_{i,j}$ as its
$(i,j)$-th entry and we denote $\mathbf{0}_{m\times n}$ as the $m\times n$
matrix with all entries equal to $0$. Given a vector $\mathbf{v}$ of length
$n$ over $\mathbb{F}_{q}$, we use $\text{diag}(\mathbf{v})$ to denote the
diagonal matrix with $\mathbf{v}(i)$ as its $i$-th diagonal element. Let $s,t$
be positive integers and $A=\\{a_{1},\ldots,a_{s}\\}\subseteq\mathbb{F}_{q}$,
we denote

$\mathbf{A}^{(t)}=(a_{j}^{i-1})_{1\leq i\leq t\atop 1\leq j\leq s}$

as the $t\times s$ Vandermonde matrix with $(i,j)$-th entry $a_{j}^{i-1}$ and
call $\mathbf{A}^{(t)}$ the $t\times s$ Vandermonde matrix generated by $A$.
Moreover, for $\alpha\in\mathbb{F}_{q}$, we use $\alpha A$ to denote the
subset $\\{\alpha a_{1},\ldots,\alpha a_{s}\\}\subseteq\mathbb{F}_{q}$.

For integer $k\geq 1$, let $g_{1},\ldots,g_{k}$ be $\mathbb{F}_{q}$-linearly
independent polynomials in $\mathbb{F}_{q}[x]$ and denote
$\text{Span}_{\mathbb{F}_{q}}\\{g_{1},\ldots,g_{k}\\}$ as the $k$-dim subspace
of $\mathbb{F}_{q}[x]$ spanned by $g_{1},\ldots,g_{k}$. Specially, when
$g_{i}=x^{i-1}$, we denote $\mathbb{F}_{q}^{<k}[x]$ as
$\text{Span}_{\mathbb{F}_{q}}\\{g_{1},\ldots,g_{k}\\}$ for simplicity. Let
$f\in\text{Span}_{\mathbb{F}_{q}}\\{g_{1},\ldots,g_{k}\\}$ and assume that
$f=\sum_{i=1}^{k}f_{i}g_{i}$, where $f_{i}\in\mathbb{F}_{q}$. We denote
$\mathbf{v}_{f}=(f_{1},\ldots,f_{k})$ and call $\mathbf{v}_{f}$ the
coefficient vector of $f$ w.r.t. basis $\\{g_{i}\\}_{i=1}^{k}$. When the basis
$\\{g_{i}\\}_{i=1}^{k}=\\{x^{i-1}\\}_{i=1}^{k}$, $\mathbf{v}_{f}$ is called
the coefficient vector of $f$ for brevity. Moreover, for a subset
$A\subseteq\mathbb{F}_{q}$, we use $h_{A}(x)=\prod_{a\in A}(x-a)$ to denote
the annihilator polynomial of $A$.

###  I-D Origanization of the Paper

The rest of the paper is structured as follows. In Section II, we provide a
general construction of MDS convertible code with optimal access cost in the
merge regime. In Section III, we extended the construction of MDS convertible
codes and provide a construction of LRCCs with optimal access costs in the
merge regime. Then, in Section IV, we prove a general lower bound on the
access cost of the conversion process for LRCCs in the merge regime. Finally,
we conclude the paper by highlighting some open questions in Section V.

##  II Constructions of MDS convertible codes

In this section, we provide a general construction of MDS convertible codes
with optimal access costs in the merge regime. We first provide an example to
illustrate the underlying idea of our general construction. Then, in Section
II-B, we present our construction of MDS convertible codes. Though this
construction, in Section II-C, we obtain a family of $(n^{I},k;n^{F},\zeta k)$
MDS convertible codes with optimal access costs over finite field of size
linear in $n^{I}$.

Recall that in the merge regime, we have $k^{F}=\zeta k^{I}$ for some integer
$\zeta\geq 2$. Write $l^{I}=n^{I}-k^{I}$ and $l^{F}=n^{F}-\zeta k^{I}$. Note
that when $l^{I}<l^{F}$ or $k^{I}\leq l^{F}$, the lower bound in Theorem I.2
can be obtained by the default approach. Thus, throughout this section, we
assume that $l^{F}\leq\min\\{l^{I},k^{I}\\}$.

###  II-A An illustrative example

We start with the following example.

######  Example II.1.

In this example, let $\mathbb{F}_{q}=\mathbb{F}_{19}$, we construct a
$(6,4)_{q}$ MDS code $\mathcal{C}^{I}$, a $(10,8)_{q}$ MDS code
$\mathcal{C}^{F}$ and a conversion procedure $T$ from $\mathcal{C}^{I}$ to
$\mathcal{C}^{F}$ with write access cost $2$ and read access cost $4$.
Together, they form a $(6,4;10,8)$ MDS convertible codes with optimal access
cost. Note that $2$ is generator of $\mathbb{F}_{19}^{*}$. We list all the
values of $2^{x}$ in Table I, which might help with calculations in this
example.

Table I: Correspondence of $2^{x}$ in $\mathbb{F}_{19}^{*}$ $x$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---|---
$2^{x}$ | 1 | 2 | 4 | 8 | 16 | 13 | 7 | 14 | 9
$x$ | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17
$2^{x}$ | 18 | 17 | 15 | 11 | 3 | 6 | 12 | 5 | 10

Let $A=\\{a_{1},a_{2},a_{3},a_{4}\\}=\\{1,8,7,18\\}$,
$B=\\{b_{1},b_{2},b_{3},b_{4}\\}=\\{2,16,14,17\\}$ and
$C=\\{c_{1},c_{2}\\}=\\{4,9\\}$. Then, it holds that $a_{i}=2^{3(i-1)}$,
$b_{i}=2a_{i}$ and $c_{i}=4a_{i}$. We define the initial code
$\mathcal{C}^{I}$ as the $[6,4]$ RS code with evaluation points $A\cup C$,
i.e.,

$\mathcal{C}^{I}=\\{(f(\alpha),\alpha\in A\cup C):\leavevmode\nobreak\
f\in\mathbb{F}_{q}^{<4}[x]\\}.$

Next, to define the final code $\mathcal{C}^{F}$, we need some preliminaries.
Let $\bm{\theta}=(11,3,3,6)$ and

$\mathbf{M}=\mathbf{A}^{(4)}\cdot\text{diag}(\bm{\theta})\cdot(\mathbf{B}^{(4)})^{-1}=\left(\begin{array}[]{cccc}0&16&14&7\\\
1&17&17&17\\\ 16&16&10&7\\\ 1&6&17&15\end{array}\right).$

Then, one can verify that the following holds:

  * 1.

For every $i\in[4]$,
$\mathbf{M}\cdot(1,b_{i},b_{i}^{2},b_{i}^{3})^{T}=\bm{\theta}(i)(1,a_{i},a_{i}^{2},a_{i}^{3})^{T}$.

  * 2.

$\mathbf{M}\cdot(1,c_{1},c_{1}^{2},c_{1}^{3})^{T}=(14,4,4,3)^{T}=13(1,c_{1},c_{1}^{2},c_{1}^{3})^{T}+(1,c_{2},c_{2}^{2},c_{2}^{3})^{T}$.

  * 3.

$\mathbf{M}\cdot(1,c_{2},c_{2}^{2},c_{2}^{3})^{T}=(16,16,12,17)^{T}=18(1,c_{1},c_{1}^{2},c_{1}^{3})^{T}-2(1,c_{2},c_{2}^{2},c_{2}^{3})^{T}$.

For each $f\in\mathbb{F}_{q}^{<4}[x]$, we denote $M(f)$ as the polynomial in
$\mathbb{F}_{q}^{<4}[x]$ with coefficient vector
$\mathbf{v}_{f}\cdot\mathbf{M}$. Then, we have

$\begin{cases}M(f)(b_{i})=\mathbf{v}_{f}\cdot\mathbf{M}\cdot(1,b_{i},b_{i}^{2},b_{i}^{3})^{T}=\bm{\theta}(i)f(a_{i}),\leavevmode\nobreak\
1\leq i\leq 4;\\\
M(f)(c_{1})=\mathbf{v}_{f}\cdot\mathbf{M}\cdot(1,c_{1},c_{1}^{2},c_{1}^{3})^{T}=13f(c_{1})+f(c_{2});\\\
M(f)(c_{2})=\mathbf{v}_{f}\cdot\mathbf{M}\cdot(1,c_{2},c_{2}^{2},c_{2}^{3})^{T}=18f(c_{1})-2f(c_{2}).\end{cases}$

Recall that $h_{A}$ and $h_{B}$ are the annihilator polynomials of $A$ and
$B$, respectively. Let $T$ be the map from
$\mathbb{F}_{q}^{<4}[x]\times\mathbb{F}_{q}^{<4}[x]$ to
$\mathbb{F}_{q}^{<8}[x]$ such that

$T:\leavevmode\nobreak\ (f_{1},f_{2})\longmapsto h_{B}\cdot f_{1}+h_{A}\cdot
M(f_{2})$

and let $\mathbf{u}=(u_{\alpha},\alpha\in A\cup B\cup C)$ be a vector in
$\mathbb{F}_{q}^{10}$ with coordinates indexed by elements in $A\cup B\cup C$
and

$\begin{cases}u_{a_{i}}=h_{B}(a_{i})^{-1},\leavevmode\nobreak\ 1\leq i\leq
4;\\\ u_{b_{i}}=\bm{\theta}(i)^{-1}h_{A}(b_{i})^{-1},\leavevmode\nobreak\
1\leq i\leq 4;\\\ u_{c_{i}}=1,\leavevmode\nobreak\ 1\leq i\leq 2.\\\
\end{cases}$

Now, we define the final code $\mathcal{C}^{F}$ as

$\mathcal{C}^{F}=\\{(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in A\cup B\cup
C):\leavevmode\nobreak\ f_{1},f_{2}\in\mathbb{F}_{q}^{<4}[x]\\}.$

Since $T(f_{1},f_{2})\in\mathbb{F}_{q}^{<8}[x]$, $\mathcal{C}^{F}$ is a
subcode of the $[10,8]$ GRS code defined by $A\cup B\cup C$ and vector
$\mathbf{u}$. Note that

$u_{\alpha}T(f_{1},f_{2})(\alpha)=\begin{cases}f_{1}(\alpha),\leavevmode\nobreak\
\text{when}\leavevmode\nobreak\ \alpha\in A;\\\
f_{2}(\alpha),\leavevmode\nobreak\ \text{when}\leavevmode\nobreak\ \alpha\in
B.\end{cases}$

Thus, we can use $(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in A)$ and
$(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in B)$ to reconstruct $f_{1}$ and
$f_{2}$, respectively. This implies that $\dim(\mathcal{C}^{F})=8$ and
$\mathcal{C}^{F}$ is a $[10,8]$ GRS code. Moreover, note that

$\begin{cases}u_{c_{1}}T(f_{1},f_{2})(c_{1})=h_{B}(c_{1})f_{1}(c_{1})+h_{A}(c_{1})(13f_{2}(c_{1})+f_{2}(c_{2})),\\\
u_{c_{2}}T(f_{1},f_{2})(c_{2})=h_{B}(c_{2})f_{1}(c_{2})-h_{A}(c_{2})(f_{2}(c_{1})+2f_{2}(c_{2})).\end{cases}$

Therefore, for any two codewords $\mathbf{c}_{1}=(f_{1}(\alpha),\alpha\in
A\cup C)$ and $\mathbf{c}_{2}=(f_{2}(\alpha),\alpha\in A\cup C)$ in
$\mathcal{C}^{I}$, the map $T$ induces a conversion procedure from
$(\mathbf{c}_{1},\mathbf{c}_{2})$ to
$\mathbf{d}=(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in A\cup B\cup
C)\in\mathcal{C}^{F}$ such that

  * 1)

the $4$ symbols in $\mathbf{c}_{1}|_{A}$ remain in $\mathbf{d}$ as
$\mathbf{d}|_{A}$, and the $4$ symbols in $\mathbf{c}_{2}|_{A}$ remain in
$\mathbf{d}$ as $\mathbf{d}|_{B}$111Let $\mathcal{C}$ be an $[n,k]$ RS code
with evaluation points $A$. For any $\mathbf{c}=(f(\alpha),\alpha\in
A)\in\mathcal{C}$ and $A^{\prime}\subseteq A$, we denote
$\mathbf{c}|_{A^{\prime}}$ as the restriction of $\mathbf{c}$ to coordinates
corresponding to $A^{\prime}$, i.e.,
$\mathbf{c}|_{A^{\prime}}=(f(\alpha),\alpha\in A^{\prime})$.;

  * 2)

the $2$ symbols in $\mathbf{d}|_{C}$ are linear combinations of symbols in
$\mathbf{c}_{1}|_{C}$ and $\mathbf{c}_{2}|_{C}$.

Therefore, the conversion procedure $T$ has write access cost $2$ and read
access cost $4$.

######  Remark II.1.

Example II.1 provides an overview of the underlying idea behind our general
construction. That is, by selecting proper evaluation points
$A=\\{a_{1},\ldots,a_{k}\\}$, $B=\\{b_{1},\ldots,b_{k}\\}$ and
$C=\\{c_{1},\ldots,c_{l}\\}$, we can obtain a surjective map
$T:\mathbb{F}_{q}^{<k}[x]\times\mathbb{F}_{q}^{<k}[x]\rightarrow\mathbb{F}_{q}^{<2k}[x]$
such that for every
$(f_{1},f_{2})\in\mathbb{F}_{q}^{<k}[x]\times\mathbb{F}_{q}^{<k}[x]$ the
following holds:

  * 1.

$T(f_{1},f_{2})(a_{i})=\alpha_{i}f_{1}(a_{i})$ and
$T(f_{1},f_{2})(b_{i})=\beta_{i}f_{2}(a_{i})$, where for each $1\leq i\leq k$,
$\alpha_{i}$ and $\beta_{i}$ are non-zero constants determined by $A$, $B$ and
$C$;

  * 2.

$T(f_{1},f_{2})(c_{i})=\sum_{j=1}^{l}(\gamma_{i,j}^{(1)}f_{1}(c_{j})+\gamma_{i,j}^{(2)}f_{2}(c_{j}))$,
where for each $(i,j)\in[l]\times[l]$, $\gamma_{i,j}^{(1)}$ and
$\gamma_{i,j}^{(2)}$ are constants determined by $A$, $B$ and $C$.

Then, based on this, we can define $\mathcal{C}^{I}$ as the $[k+l,k]$ RS code
with evaluation points $A\cup C$ and $\mathcal{C}^{F}$ as

$\mathcal{C}^{F}=\\{(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in A\cup B\cup
C):\leavevmode\nobreak\ f_{1},f_{2}\in\mathbb{F}_{q}^{<k}[x]\\},$

where $u_{a_{i}}=\alpha_{i}^{-1}$, $u_{b_{i}}=\beta_{i}^{-1}$ and
$u_{c_{i}}=1$. Since $T$ is surjective, $\mathcal{C}^{F}$ is actually the
$[2k+l,k]$ GRS code defined by $A\cup B\cup C$ and vector
$(u_{\alpha},\alpha\in A\cup B\cup C)$.

By the one-to-one correspondence between polynomials and codewords in GRS
codes, $T$ induces a conversion procedure from $\mathcal{C}^{I}$ to
$\mathcal{C}^{F}$, i.e., codewords $\mathbf{c}_{1}=(f_{1}(\alpha),\alpha\in
A\cup C)$ and $\mathbf{c}_{2}=(f_{2}(\alpha),\alpha\in A\cup C)$ are mapped to
$\mathbf{d}=(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in A\cup B\cup C)$.
Similar to Example II.1, one can easily verify that
$\mathbf{d}|_{A}=\mathbf{c}_{1}|_{A}$, $\mathbf{d}|_{B}=\mathbf{c}_{2}|_{A}$
and symbols in $\mathbf{d}|_{C}$ are linear combinations of symbols in
$\mathbf{c}_{1}|_{C}$ and $\mathbf{c}_{2}|_{C}$. This will imply that
$(\mathcal{C}^{I},\mathcal{C}^{F})$ is an MDS convertible codes with optimal
access cost.

######  Remark II.2.

In Example II.1, the map $T$ is defined as

$T:\leavevmode\nobreak\ (f_{1},f_{2})\longmapsto h_{B}\cdot f_{1}+h_{A}\cdot
M(f_{2}),$

where $M(f_{2})$ is the polynomial with coefficient vector
$\mathbf{v}_{f_{2}}\cdot\mathbf{M}$. Note that $\mathbf{M}$ is a $k\times k$
matrix satisfying

  * 1.

$\mathbf{M}\cdot(1,b_{i},\ldots,b_{i}^{k-1})^{T}=\theta_{i}(1,a_{i},\ldots,a_{i}^{k-1})^{T}$,
where for each $1\leq i\leq k$, $\theta_{i}$ is non-zero constant determined
by $A$, $B$ and $C$;

  * 2.

$\mathbf{M}\cdot(1,c_{i},\ldots,c_{i}^{k-1})^{T}\in\text{Span}_{\mathbb{F}_{q}}\\{(1,c_{i},\ldots,c_{i}^{k-1})^{T}:\leavevmode\nobreak\
1\leq i\leq l\\}.$

One can easily check that these properties of $\mathbf{M}$ ensure the map $T$
defined above satisfies the requirements in Remark II.1. Thus, the crucial
part of the construction is to find proper subsets $A$, $B$ and $C$ such that
there exists a $k\times k$ matrix $\mathbf{M}$ satisfying the above
requirements.

###  II-B Constructions of MDS convertible codes with optimal access costs

First, we assume that $l^{F}=l^{I}=l<k^{I}$ and present a construction of MDS
convertible codes for this case. Then, we will modify it for the case when
$l^{F}<l^{I}$.

Construction I: Let $A_{i}=\\{a_{i,1},\ldots,a_{i,k}\\}$, $1\leq i\leq\zeta$
and $C=\\{c_{1},\ldots,c_{l}\\}$ be mutually disjoint subsets of
$\mathbb{F}_{q}$ such that for every $2\leq i\leq\zeta$, there is a $k\times
k$ matrix $\mathbf{M}_{i}$ satisfying:

Condition 1

For every $1\leq j\leq k$,

$\mathbf{M}_{i}\cdot\mathbf{a}_{i,j}=\theta_{i,j}\mathbf{a}_{1,j},$

where $\mathbf{a}_{i,j}=(1,a_{i,j},\ldots,a_{i,j}^{k-1})^{T}$ and
$\theta_{i,j}=\frac{h_{A_{i}\cup
C\setminus\\{a_{i,j}\\}}(a_{i,j})}{h_{A_{1}\cup
C\setminus\\{a_{1,j}\\}}(a_{1,j})}$.

Condition 2

For every $1\leq j\leq l$,
$\mathbf{M}_{i}\cdot(1,c_{j},\ldots,c_{j}^{k-1})^{T}\in\text{Span}_{\mathbb{F}_{q}}\\{(1,c_{j},\ldots,c_{j}^{k-1})^{T}:\leavevmode\nobreak\
1\leq j\leq l\\}$.

Let $\mathcal{C}^{I}$ be the $[k+l,k]$ RS code with evaluation points
$A_{1}\cup C$, i.e.,

$\mathcal{C}^{I}=\\{(f(\alpha),\leavevmode\nobreak\ \alpha\in A_{1}\cup
C):f\in\mathbb{F}_{q}^{<k}[x]\\}.$

Denote $A=\bigcup_{i=1}^{k}A_{i}$. Let $\mathbf{M}_{1}=\mathbf{I}$ and define
map $T:(\mathbb{F}_{q}^{<k}[x])^{\zeta}\rightarrow\mathbb{F}_{q}^{<\zeta
k}[x]$ as

$\displaystyle T:(f_{1},\ldots,f_{\zeta})$
$\displaystyle\longmapsto\sum_{i=1}^{\zeta}h_{A\setminus A_{i}}\cdot
M_{i}(f_{i}),$ (1)

where $M_{i}(f_{i})\in\mathbb{F}_{q}^{<k}[x]$ is the polynomial with
coefficient $\mathbf{v}_{f_{i}}\cdot\mathbf{M}_{i}$. Then, we define
$\mathcal{C}^{F}$ as

$\displaystyle\mathcal{C}^{F}=\\{(u_{\alpha}T(f_{1},\ldots,f_{\zeta})(\alpha),\leavevmode\nobreak\
\alpha\in A\cup C):f_{i}\in\mathbb{F}_{q}^{<k}[x],\leavevmode\nobreak\ 1\leq
i\leq\zeta\\},$ (2)

where $u_{\alpha}=\theta_{i,j}^{-1}h_{A\setminus A_{i}}^{-1}(a_{i,j})$ when
$\alpha=a_{i,j}\in A_{i}$ and $u_{\alpha}=1$ when $\alpha\in C$.

######  Theorem II.1.

For positive integers $\zeta\geq 2$, $k$ and $l<k$, the
$(\mathcal{C}^{I},\mathcal{C}^{F})$ given by Construction I is a $(k+l,k;\zeta
k+l,\zeta k)$ MDS convertible code with optimal access cost.

###### Proof.

Let $\mathbf{c}_{1},\ldots,\mathbf{c}_{\zeta}\in\mathcal{C}^{I}$ be the
$\zeta$ initial codewords and denote $f_{i}(x)$ as the encoding polynomial of
$\mathbf{c}_{i}$. Since for every $1\leq i\leq\zeta$, $\deg(M_{i}(f_{i}))\leq
k-1$ and $\deg(h_{A\setminus A_{i}})=(\zeta-1)k$, it holds that
$T(f_{1},\ldots,f_{\zeta})\in\mathbb{F}_{q}^{<\zeta k}$. Thus,
$\mathcal{C}^{F}$ is a subcode of the $[\zeta k+l,\zeta k]$ GRS code defined
by evaluation points $A\cup C$ and vector $(u_{\alpha},\alpha\in A\cup C)$.
Moreover, the map $T$ induces a conversion procedure from $\mathcal{C}^{I}$ to
$\mathcal{C}^{F}$, that is, $\mathbf{c}_{1},\ldots,\mathbf{c}_{\zeta}$ are
converted to the codeword

$\mathbf{d}=(u_{\alpha}T(f_{1},\ldots,f_{\zeta})(\alpha),\leavevmode\nobreak\
\alpha\in A\cup C)\in\mathcal{C}^{F}.$

Next, we show that the read and write access costs of the conversion procedure
induced by $T$ are $\zeta l$ and $l$, respectively. By Theorem I.2, this
implies that $(\mathcal{C}^{I},\mathcal{C}^{F})$ has optimal access cost. As a
byproduct, we shall see that $\mathcal{C}^{F}$ has dimension $\zeta k$, i.e.,
the map $T$ is surjective. This yields the result.

For each $(i,j)\in[\zeta]\times[k]$ and $\alpha=a_{i,j}$, since $h_{A\setminus
A_{i}}$ is the annihilator polynomial of $A\setminus A_{i}$, we have

$\displaystyle u_{\alpha}T(f_{1},\ldots,f_{\zeta})(\alpha)$
$\displaystyle=\theta_{i,j}^{-1}h_{A\setminus
A_{i}}^{-1}(a_{i,j})\sum_{s=1}^{\zeta}h_{A\setminus
A_{s}}(a_{i,j})(M_{s}(f_{s}))(a_{i,j})$
$\displaystyle=\theta_{i,j}^{-1}(M_{i}(f_{i}))(a_{i,j})$
$\displaystyle=f_{i}(a_{1,j}),$

where the last equality follows from
$(M_{i}(f_{i}))(a_{i,j})=\mathbf{v}_{f_{i}}\cdot\mathbf{M}_{i}\cdot\mathbf{a}_{i,j}=\theta_{i,j}f_{i}(a_{1,j})$.
Therefore, we have $\mathbf{d}|_{A_{i}}=\mathbf{c}_{i}|_{A_{1}}$. In other
words, there are at least $k$ symbols from each $\mathbf{c}_{i}$ remaining in
$\mathbf{d}$. Thus, the write access cost is at most $l$. Moreover, note that
$\mathcal{C}^{I}|_{A_{1}}=\mathbb{F}_{q}^{k}$. Thus, we have
$\mathcal{C}^{F}|_{A}=\mathbb{F}_{q}^{\zeta k}$, which leads to
$\dim(\mathcal{C}^{F})=\zeta k$.

On the other hand, for $1\leq j\leq l$, denote
$\mathbf{c}_{j}=(1,c_{j},\ldots,c_{j}^{k-1})^{T}$. By
$\mathbf{M}_{i}\cdot\mathbf{c}_{j}\in\text{Span}_{\mathbb{F}_{q}}\\{\mathbf{c}_{1},\ldots,\mathbf{c}_{l}\\}$,
we can assume that
$\mathbf{M}_{i}\cdot\mathbf{c}_{j}=\sum_{s=1}^{l}\eta_{s}^{(i,j)}\mathbf{c}_{s}$.
Then, for $\alpha=c_{j}\in C$, we have

$\displaystyle u_{\alpha}T(f_{1},\ldots,f_{\zeta})(\alpha)$
$\displaystyle=\sum_{i=1}^{\zeta}h_{A\setminus
A_{i}}(c_{j})(M_{i}(f_{i}))(c_{j})$
$\displaystyle=\sum_{i=1}^{\zeta}h_{A\setminus
A_{i}}(c_{j})\left(\mathbf{v}_{f_{i}}\cdot\sum_{s=1}^{l}\eta_{s}^{(i,j)}\mathbf{c}_{s}\right)$
$\displaystyle=\sum_{i=1}^{\zeta}\sum_{s=1}^{l}h_{A\setminus
A_{i}}(c_{j})\eta_{s}(i,j)f_{i}(c_{s}).$ (3)

This implies that the $l$ symbols in $\mathbf{d}|_{C}$ are linear combinations
of the $\zeta l$ symbols in
$\mathbf{c}_{1}|_{C},\ldots,\mathbf{c}_{\zeta}|_{C}$. Therefore, the read
access cost is at most $\zeta l$. ∎

Now, we present the construction for the general case when $l^{F}\leq l^{I}$.
The idea is simple. Note that if $\mathcal{C}^{I}$ is a linear $[k+l^{I},k]$
MDS code, then, $\mathcal{C}^{I}|_{[k+l^{F}]}$ is a $[k+l^{F},k]$ MDS code.
Therefore, we can use the same $\mathcal{C}^{F}$ obtained in Construction I as
the final code and maintain the access cost.

Construction II: Let $A_{1},\ldots,A_{\zeta}$, $C$ and
$(u_{\alpha},\alpha\in\bigcup_{i\in[\zeta]}{A_{i}}\cup C)$ be identical to
those defined in Construction I. Let $B=\\{b_{1},\ldots,b_{l^{I}-l^{F}}\\}$ be
a subset of $\mathbb{F}_{q}$ of size $(l^{I}-l^{F})$ such that
$B\cap(A_{1}\cup C)=\emptyset$222When $l^{I}=l^{F}$, $B=\emptyset$. Let
$\mathcal{C}^{I}$ be the $[k+l^{I},k]$ RS code with evaluation points
$A_{1}\cup C\cup B$, i.e.,

$\mathcal{C}^{I}=\\{(f(\alpha),\leavevmode\nobreak\ \alpha\in A_{1}\cup C\cup
B):f(x)\in\mathbb{F}_{q}^{<k}[x]\\}.$

Let the conversion procedure $T$ and the final code $\mathcal{C}^{F}$ be the
same as those defined in (1) and (2).

By Theorem I.2 and Theorem II.1, we have the following immediate result.

######  Theorem II.2.

For positive integers $\zeta\geq 2$, $k$, $l^{I}$ and
$l^{F}\leq\min\\{k,l^{I}\\}$, the $(\mathcal{C}^{I},\mathcal{C}^{F})$ given by
Construction II is a $(k+l^{I},k;\zeta k+l^{F},\zeta k)$ MDS convertible code
with optimal access cost.

###  II-C A family of MDS convertible codes with optimal access costs

From Section II-B, the key to implementing Construction I and II lies in
finding pairwise disjoint subsets $A_{i}$’s and $C$ from $\mathbb{F}_{q}$,
such that there exist matrices $\mathbf{M}_{i}$’s satisfying conditions 1 and
2 in Construction I. In the following, we first give a sufficient condition
for when $A_{i}$’s can ensure the existence of such $\mathbf{M}_{i}$’s. Then,
we give an explicit construction of $A_{1}$, $\ldots$, $A_{\zeta}$ satisfying
this sufficient condition. Together with proper subsets $B$ and $C$, we
provide an implementation of Construction II, and obtain a family of MDS
convertible codes with optimal access costs.

######  Lemma II.3.

For positive integers $k\geq 2$ and $l<k$, let $A=\\{a_{1},\ldots,a_{k}\\}$
and $B=\\{b_{1},\ldots,b_{k}\\}$ be disjoint subsets of $\mathbb{F}_{q}$.
Suppose that there is an invertible matrix $\mathbf{T}$ over $\mathbb{F}_{q}$
of order $l$ satisfying

$\mathbf{B}^{(l)}=\mathbf{T}\mathbf{A}^{(l)}.$ (4)

Then, for any $C=\\{c_{1},\ldots,c_{l}\\}\subseteq\mathbb{F}_{q}$, there is a
$k\times k$ matrix $\mathbf{M}$ such that:

  * 1.

For every $1\leq i\leq k$,
$\mathbf{M}\cdot(1,b_{i},\ldots,b_{i}^{k-1})^{T}=\theta_{i}(1,a_{i},\ldots,a_{i}^{k-1})^{T}$,
where $\theta_{i}=\frac{h_{B\cup C\setminus\\{b_{i}\\}}(b_{i})}{h_{A\cup
C\setminus\\{a_{i}\\}}(a_{i})}$.

  * 2.

For every $1\leq i\leq l$,
$\mathbf{M}\cdot(1,c_{i},\ldots,c_{i}^{k-1})^{T}\in\text{Span}_{\mathbb{F}_{q}}\\{(1,c_{i},\ldots,c_{i}^{k-1})^{T}:\leavevmode\nobreak\
1\leq i\leq l\\}$.

By Lemma II.3, we have the following immediate corollary, which provides a
sufficient condition for the existence of $\mathbf{M}_{i}$’s satisfying
conditions 1 and 2 in Construction I.

######  Corollary II.1.

Let $\zeta\geq 2$, $k$ and $l<k$ be positive integers. Let
$A_{i}=\\{a_{i,1},\ldots,a_{i,k}\\}$, $1\leq i\leq\zeta$, and
$C=\\{c_{1},\ldots,c_{l}\\}$ be mutually disjoint subsets of $\mathbb{F}_{q}$.
If for every $2\leq i\leq\zeta$, there is an invertible matrix
$\mathbf{T}_{i}$ over $\mathbb{F}_{q}$ of order $l$ satisfying

$\mathbf{A}_{i}^{(l)}=\mathbf{T}_{i}\mathbf{A}_{1}^{(l)}.$

Then, for every $2\leq i\leq\zeta$, there is a $k\times k$ matrix
$\mathbf{M}_{i}$ satisfies condition 1 and 2 in Construction I.

Now, we present the proof of Lemma II.3.

###### Proof of Lemma II.3.

Define
$\mathbf{M}=\mathbf{A}^{(k)}\cdot\text{diag}(\theta_{1},\ldots,\theta_{k})\cdot(\mathbf{B}^{(k)})^{-1}$.
Let $\mathbf{a}_{i}=(1,a_{i},\ldots,a_{i}^{k-1})^{T}$,
$\mathbf{b}_{i}=(1,b_{i},\ldots,b_{i}^{k-1})^{T}$, $1\leq i\leq k$ and
$\mathbf{c}_{i}=(1,c_{i},\ldots,c_{i}^{k-1})^{T}$, $1\leq i\leq l$. Then, for
every $1\leq i\leq k$,
$\mathbf{M}\cdot\mathbf{b}_{i}=\theta_{i}\mathbf{a}_{i}$. Thus, we only need
to verify that $\mathbf{M}$ satisfies the second condition.

For every $1\leq j\leq l$, it holds that

$\mathbf{c}_{j}=\sum_{i=1}^{k}\frac{h_{B\setminus\\{b_{i}\\}}(c_{j})}{h_{B\setminus\\{b_{i}\\}}(b_{i})}\mathbf{b}_{i}.$

Denote
$\eta_{i,j}=\frac{h_{B\setminus\\{b_{i}\\}}(c_{j})}{h_{B\setminus\\{b_{i}\\}}(b_{i})}$.
This leads to
$\mathbf{M}\cdot\mathbf{c}_{j}=\sum_{i=1}^{k}\eta_{i,j}\theta_{i}\mathbf{a}_{i}.$

For each $f(x)\in\mathbb{F}_{q}^{<k-l}[x]$, we denote $\mathbf{v}_{h_{C}\cdot
f}$ as the coefficient vector of polynomial $h_{C}(x)f(x)$. Then,

$\displaystyle\mathbf{v}_{h_{C}\cdot f}\cdot\mathbf{M}\cdot\mathbf{c}_{j}$
$\displaystyle=\sum_{i=1}^{k}\eta_{i,j}\theta_{i}(\mathbf{v}_{h_{C}\cdot
f}\cdot\mathbf{a}_{i})=\sum_{i=1}^{k}\eta_{i,j}\theta_{i}h_{C}(a_{i})f(a_{i})$
$\displaystyle=\sum_{i=1}^{k}\frac{h_{B\setminus\\{b_{i}\\}}(c_{j})}{h_{B\setminus\\{b_{i}\\}}(b_{i})}\frac{h_{B\cup
C\setminus\\{b_{i}\\}}(b_{i})}{h_{A\cup
C\setminus\\{a_{i}\\}}(a_{i})}h_{C}(a_{i})f(a_{i})$
$\displaystyle=\sum_{i=1}^{k}\frac{h_{C}(b_{i})}{h_{A\setminus\\{a_{i}\\}}(a_{i})}h_{B\setminus\\{b_{i}\\}}(c_{j})f(a_{i}).$
(5)

Note that $h_{C}(b_{i})h_{B\setminus\\{b_{i}\\}}(c_{j})=\prod_{c\in
C}(b_{i}-c)\prod_{b\in
B\setminus\\{b_{i}\\}}(c_{j}-b)=-h_{C\setminus\\{c_{j}\\}}(b_{i})h_{B}(c_{j})$.
Thus, (5) is equivalent to

$\displaystyle\mathbf{v}_{h_{C}\cdot f}\cdot\mathbf{M}\cdot\mathbf{c}_{j}$
$\displaystyle=-h_{B}(c_{j})\left(\sum_{i=1}^{k}\frac{h_{C\setminus\\{c_{j}\\}}(b_{i})f(a_{i})}{h_{A\setminus\\{a_{i}\\}}(a_{i})}\right).$
(6)

Denote $\mathbf{h}_{C\setminus\\{c_{j}\\}}$ as the coefficient vector of
polynomial $h_{C\setminus\\{c_{j}\\}}(x)$. By (4), we have

$\mathbf{h}_{C\setminus\\{c_{j}\\}}\cdot\mathbf{B}^{(l)}=\mathbf{h}_{C\setminus\\{c_{j}\\}}\cdot\mathbf{T}\mathbf{A}^{(l)}.$

Denote $H(x)\in\mathbb{F}_{q}^{<l}[x]$ as the polynomial with coefficient
vector $\mathbf{h}_{C\setminus\\{c_{j}\\}}\cdot\mathbf{T}$. Then, the above
identity implies that $h_{C\setminus\\{c_{j}\\}}(b_{i})=H(a_{i})$ for every
$1\leq i\leq k$. Thus, (6) can be further simplified as

$\displaystyle\mathbf{v}_{h_{C}\cdot f}\cdot\mathbf{M}\cdot\mathbf{c}_{j}$
$\displaystyle=-h_{B}(c_{j})\left(\sum_{i=1}^{k}\frac{(H\cdot
f)(a_{i})}{h_{A\setminus\\{a_{i}\\}}(a_{i})}\right).$ (7)

Meanwhile, by $\deg(f)\leq k-l-1$, we have $\deg(H\cdot f)\leq k-2$. Denote
$\tilde{\mathbf{v}}$ as the coefficient vector of $H(x)f(x)$. Then, we have

$\tilde{\mathbf{v}}\cdot\mathbf{A}^{(k-1)}=((H\cdot f)(a_{1}),\ldots,(H\cdot
f)(a_{k})).$

On the other hand, by Cramer’s rule, we know that

$\mathbf{A}^{(k-1)}\cdot(h_{A\setminus\\{a_{1}\\}}(a_{1})^{-1},\ldots,h_{A\setminus\\{a_{k}\\}}(a_{k})^{-1})^{T}=\mathbf{0}.$

Thus, by (7) and

$\sum_{i=1}^{k}\frac{(H\cdot
f)(a_{i})}{h_{A\setminus\\{a_{i}\\}}(a_{i})}=\tilde{\mathbf{v}}\cdot\mathbf{A}^{(k-1)}\cdot(h_{A\setminus\\{a_{1}\\}}(a_{1})^{-1},\ldots,h_{A\setminus\\{a_{k}\\}}(a_{k})^{-1})^{T},$

we have $\mathbf{v}_{h_{C}\cdot f}\cdot\mathbf{M}\cdot\mathbf{c}_{j}=0$ for
every $f(x)\in\mathbb{F}_{q}^{<k-l}[x]$ and $1\leq j\leq l$. Note that
$\\{\mathbf{v}_{h_{C}\cdot f}:f(x)\in\mathbb{F}_{q}^{<k-l}[x]\\}$ is a
$(k-l)$-dim subspace of $\mathbb{F}_{q}^{k}$ and $\mathbf{v}_{h_{C}\cdot
f}\cdot\mathbf{c}_{j}=0$ for every $f(x)\in\mathbb{F}_{q}^{<k-l}[x]$ and
$1\leq j\leq l$. Therefore, by
$dim(\text{Span}\\{\mathbf{c}_{1},\ldots,\mathbf{c}_{l}\\})=l$, we have
$\mathbf{M}\cdot\mathbf{c}_{j}\in\text{Span}\\{\mathbf{c}_{1},\ldots,\mathbf{c}_{l}\\}$.

This completes the proof. ∎

Next, using the multiplicative subgroups of $\mathbb{F}_{q}^{*}$, we give an
explicit construction of $A_{i}$’s and $C$ that satisfy the requirements in
Corollary II.1.

Let $q\geq(\zeta+1)\cdot\max\\{k,l^{I}\\}+1$ be a prime power. Assume that
$\max\\{k,l^{I}\\}|(q-1)$ and let $G$ be a multiplicative subgroup of
$\mathbb{F}_{q}^{*}$ of order $\max\\{k,l^{I}\\}$333When
$\max\\{k,l^{I}\\}\nmid(q-1)$, one can let $G$ be the smallest multiplicative
subgroup of $\mathbb{F}_{q}^{*}$ of order at least $\max\\{k,l^{I}\\}$ and the
condition that $q\geq(\zeta+1)\cdot\max\\{k,l^{I}\\}+1$ becomes
$q\geq(\zeta+1)\cdot|G|+1$.. Then, $|\mathbb{F}_{q}^{*}/G|\geq\zeta+1$. Denote
$\alpha\in\mathbb{F}_{q}^{*}$ as the generator of the quotient group
$\mathbb{F}_{q}^{*}/G$. Let $A_{1}=\\{a_{1},\ldots,a_{k}\\}\subseteq G$. Then,
we define

  * •

$A_{i}=\alpha^{i-1}A_{1}=\\{\alpha^{i-1}a_{1},\ldots,\alpha^{i-1}a_{k}\\}$,
$2\leq i\leq\zeta+1$;

  * •

$C=\\{\alpha^{\zeta}a_{1},\ldots,\alpha^{\zeta}a_{k}\\}\subseteq A_{\zeta+1}$
and $B=\\{b_{1},\ldots,b_{l^{I}-l^{F}}\\}$ be any subset of
$\alpha^{\zeta}G\setminus C$ of size $l^{I}-l^{F}$.

Note that $B,C\subseteq\alpha^{\zeta}G$ and $A_{i}\subseteq\alpha^{i-1}G$,
$1\leq i\leq\zeta$. Thus, they are pairwise disjoint in $\mathbb{F}_{q}^{*}$.
Meanwhile, for $2\leq i\leq\zeta$,

$\displaystyle\mathbf{A}_{i}^{(l^{F})}$
$\displaystyle=\left(\begin{array}[]{cccc}1&1&\cdots&1\\\
\alpha^{i-1}a_{1}&\alpha^{i-1}a_{2}&\cdots&\alpha^{i-1}a_{k}\\\
\vdots&\vdots&&\vdots\\\
(\alpha^{i-1}a_{1})^{l^{F}-1}&(\alpha^{i-1}a_{2})^{l^{F}-1}&\cdots&(\alpha^{i-1}a_{k})^{l^{F}-1}\end{array}\right)$
(12)
$\displaystyle=\text{diag}(1,\alpha^{i-1},\ldots,\alpha^{(i-1)(l^{F}-1)})\mathbf{A}_{1}^{(l^{F})}.$
(13)

Since $\alpha\neq 0$, the diagonal matrix
$\text{diag}(1,\alpha^{i-1},\ldots,\alpha^{(i-1)(l^{F}-1)})$ is invertible.
Thus, for $2\leq i\leq\zeta$, set
$\mathbf{T}_{i}=\text{diag}(1,\alpha^{i-1},\ldots,\alpha^{(i-1)(l^{F}-1)})$
and we have $\mathbf{A}_{i}^{(l^{F})}=\mathbf{T}_{i}\mathbf{A}_{1}^{(l^{F})}$.

######  Remark II.3.

The sets $A$, $B$ and $C$ in Example II.1 can be viewed as an example of the
above construction for $q=19$, $k=4$, $l^{I}=l^{F}=2$ and $\zeta=2$.

Clearly, the sets $A_{i}$’s and $C$ constructed above satisfy the requirements
in Corollary II.1. Then, $A_{i}$’s, $B$ and $C$ satisfy the requirements in
Construction II. This leads to the following immediate corollary.

######  Corollary II.2.

For positive integers $\zeta\geq 2$, $k$, $l^{I}$ and
$l^{F}\leq\min\\{k,l^{I}\\}$, let $q$ be a prime power such that
$\max\\{k,l^{I}\\}\mid(q-1)$ and $q\geq(\zeta+1)\cdot\max\\{k,l^{I}\\}+1$.
Then, there is an explicit construction of $(k+l^{I},k;\zeta k+l^{F},\zeta k)$
MDS convertible code with optimal access cost.

######  Remark II.4.

The requirement of the field size in Corollary II.2 is
$q\geq(\zeta+1)\cdot\max\\{k,n^{I}-k\\}+1$, which is less strict than those in
[5].

##  III Constructions of Locally repairable convertible codes

In this section, we focus on constructions of locally repairable convertible
codes (LRCCs) in merge regime. First, we recall the construction of LRCs
introduced in [11] using “good” polynomials. Then, we give a example to
illustrate the underlying idea of the construction. In Section III-C, based on
the construction of LRCs using “good” polynomials, we present our construction
of LRCCs. Though this construction, for $n^{I}=(k+l^{I})(r+1)$ and
$n^{F}=(k+l^{F})(r+1)$, we obtain a family of $(n^{I},kr,r;n^{F},\zeta kr,r)$
LRCCs with write access cost $l^{F}(r+1)$ and read access cost $\zeta l^{F}r$
over finite field of size linear in $n^{I}$. The access costs of the
constructed LRCCs are then shown to be optimal in Section IV by Corollary
IV.1.

###  III-A Optimal LRCs through “good” polynomials

To start with, we first recall the general construction of optimal LRCs in
[11].

Let $n,k,r$ be positive integers such that $(r+1)|n$ and let
$\mathcal{A}=\\{A_{1},\ldots,A_{\frac{n}{r+1}}\\}$ be a family of $n/(r+1)$
mutually disjoint $r+1$-subsets of $\mathbb{F}_{q}$. A polynomial
$g(x)\in\mathbb{F}_{q}[x]$ of degree $r+1$ is called a _good_ polynomial
(w.r.t. $\mathcal{A}$) if for each $1\leq i\leq n/(r+1)$, $g$ is constant on
$A_{i}$ and we use $g(A_{i})$ to denote this constant.

Let $\mathbf{m}=(m_{1},\ldots,m_{k})\in\mathbb{F}_{q}^{kr}$ be a message
vector. Given a good polynomial $g$, define the encoding polynomial

$f_{\mathbf{m}}(x)=\sum_{i=1}^{r}\sum_{j=0}^{k-1}m_{jr+i}g(x)^{j}x^{i-1}.$
(14)

Then, as shown in [11], $\mathcal{C}_{0}=\\{(f_{\mathbf{m}}(a),a\in
A):\mathbf{m}\in\mathbb{F}_{q}^{kr}\\}$ is an optimal $(n,kr,r)$-LRC w.r.t.
the Singleton-type bound in Theorem I.1. Let
$\mathbf{v}=(v_{1},\ldots,v_{n})\in(\mathbb{F}_{q}^{*})^{n}$. Like GRS codes
to RS codes, one can easily obtain that the following code

$\mathcal{C}=\\{(v_{i}f_{\mathbf{m}}(a_{i}),i\in[n]):\mathbf{m}\in\mathbb{F}_{q}^{kr}\\}$

is also an $(n,kr,r)$-optimal LRC. For simplicity, we call $\mathcal{C}$ the
LRC defined by $\mathcal{A}$, $g(x)$ and $\mathbf{v}$. Specially, when
$\mathbf{v}$ is the all one vector, we call $\mathcal{C}$ the LRC defined by
$\mathcal{A}$ and $g(x)$.

Let $\tilde{\mathcal{C}}$ be the $[n,kr]$ GRS code defined by evaluation
points $\bigcup_{i=1}^{n/(r+1)}A_{i}$ and vector $\mathbf{v}$. There is a one-
to-one correspondence between codewords of $\tilde{\mathcal{C}}$ and
polynomials of degree less than $kr$. Similarly, there is also a one-to-one
correspondence between codewords of $\mathcal{C}$ and polynomials in
$\mathbb{F}_{q}[x]$ of form (14). From this perspective, $\mathcal{C}$ can be
viewed as the image of $\tilde{\mathcal{C}}$ under the base transformation
that maps $\\{x^{i}\\}_{0\leq i\leq kr-1}$ to $\\{x^{i}g^{j}\\}_{0\leq i\leq
r-1\atop 0\leq j\leq k-1}$. Based on this connection between the LRCs obtained
from good polynomials and the GRS codes, in the following, we generalize our
constructions of MDS convertible codes in Section II and obtain constructions
of optimal LRCCs.

###  III-B An illustrative example

Similar to Section II-A, we begin with the following example.

######  Example III.1.

In this example, we construct a $(9,4,2)$-LRC $\mathcal{C}^{I}$ and a
$(15,8,2)$-LRC $\mathcal{C}^{F}$ over $\mathbb{F}_{q}=\mathbb{F}_{19}$, and a
conversion procedure $T$ from $\mathcal{C}^{I}$ to $\mathcal{C}^{F}$ with
write access cost $3$ and read access cost $4$. Together, they form an
$(9,4,2;15,8,2)$ optimal LRCC with optimal access cost.

Let $A_{1}=\\{a_{11},a_{12},a_{13}\\}=\\{1,7,11\\}$,
$A_{2}=\\{a_{21},a_{22},a_{23}\\}=\\{8,18,12\\}$,
$B_{1}=\\{b_{11},b_{12},b_{13}\\}=\\{2,14,3\\}$,
$B_{2}=\\{b_{21},b_{22},b_{23}\\}=\\{16,17,5\\}$ and
$C=\\{c_{1},c_{2},c_{3}\\}=\\{4,9,6\\}$. Let $A=A_{1}\cup A_{2}$ and
$B=B_{1}\cup B_{2}$. By Table I, it holds that $a_{1j}=2^{6(j-1)}$ ($1\leq
j\leq 3$), $A_{2}=2^{3}A_{1}$, $B_{1}=2A_{1}$, $B_{2}=2^{4}A_{1}$ and
$C=2^{2}A_{1}$.

Let $g(x)=x^{3}$. Then, $g$ is constant on each $A_{i}$, $B_{i}$ and $C$.
Specifically, we have $g(A_{1})=1$, $g(A_{2})=18$, $g(B_{1})=8$, $g(B_{2})=11$
and $g(C)=7$. Denote $G_{1}=\\{g(A_{1}),g(A_{2})\\}=\\{1,18\\}$ and
$G_{2}=\\{g(B_{1}),g(B_{2})\\}=\\{8,11\\}$.

For $f\in\text{Span}_{\mathbb{F}_{q}}\\{1,x,g(x),xg(x)\\}$, denote
$\mathbf{v}_{f}$ as its coefficient vector w.r.t. basis
$\\{1,x,g(x),xg(x)\\}$. Define the initial code $\mathcal{C}^{I}$ as the
$(9,4,2)$-LRC defined by $\\{A_{1},A_{2},C\\}$ and $g$, i.e.,

$\mathcal{C}^{I}=\\{(f(\alpha),\alpha\in A\cup C):\leavevmode\nobreak\
f\in\text{Span}_{\mathbb{F}_{q}}\\{1,x,g(x),xg(x)\\}\\}.$

Next, to define the final code $\mathcal{C}^{F}$, we need some preliminaries.
Let $\theta_{1}=5$, $\theta_{2}=15$ and $\bm{\theta}=(5,5,15,15)$. Define

$\displaystyle\mathbf{M}$ $\displaystyle=\left(\begin{array}[]{cccc}1&1&1&1\\\
a_{11}&a_{12}&a_{21}&a_{22}\\\ a_{11}^{3}&a_{12}^{3}&a_{21}^{3}&a_{22}^{3}\\\
a_{11}^{4}&a_{12}^{4}&a_{21}^{4}&a_{22}^{4}\end{array}\right)\cdot\text{diag}(\bm{\theta})\cdot\left(\begin{array}[]{cccc}1&1&1&1\\\
b_{11}&b_{12}&b_{21}&b_{22}\\\ b_{11}^{3}&b_{12}^{3}&b_{21}^{3}&b_{22}^{3}\\\
b_{11}^{4}&b_{12}^{4}&b_{21}^{4}&b_{22}^{4}\end{array}\right)^{-1}$
$\displaystyle=\left(\begin{array}[]{cccc}10&0&16&0\\\ 0&5&0&8\\\ 14&0&6&0\\\
0&7&0&3\end{array}\right).$

Then, one can verify that

  * 1.

$\mathbf{M}\cdot(1,b_{ij},b_{ij}^{3},b_{ij}^{4})^{T}=\theta_{i}(1,a_{ij},a_{ij}^{3},a_{ij}^{4})^{T}$,
$(i,j)\in[2]\times[3]$;

  * 2.

$\mathbf{M}\cdot(1,c_{1},c_{1}^{3},c_{1}^{4})^{T}=(8,16,18,17)^{T}=15(1,c_{1},c_{1}^{3},c_{1}^{4})^{T}-7(1,c_{2},c_{2}^{3},c_{2}^{4})^{T}$;

  * 2.

$\mathbf{M}\cdot(1,c_{2},c_{2}^{3},c_{2}^{4})^{T}=(8,17,18,5)^{T}=11(1,c_{1},c_{1}^{3},c_{1}^{4})^{T}-3(1,c_{2},c_{2}^{3},c_{2}^{4})^{T}$.

For $f\in\text{Span}_{\mathbb{F}_{q}}\\{1,x,g(x),xg(x)\\}$, denote $M(f)$ as
the polynomial in $\text{Span}_{\mathbb{F}_{q}}\\{1,x,g(x),xg(x)\\}$ with
coefficient vector $\mathbf{v}_{f}\cdot\mathbf{M}$ w.r.t. basis
$\\{1,x,g(x),xg(x)\\}$. Then,

$\begin{cases}M(f)(b_{i,j})=\mathbf{v}_{f}\cdot\mathbf{M}\cdot(1,b_{ij},b_{ij}^{3},b_{ij}^{4})^{T}=\theta_{i}f(a_{ij}),\leavevmode\nobreak\
(i,j)\in[2]\times[3];\\\
M(f)(c_{1})=\mathbf{v}_{f}\cdot\mathbf{M}\cdot(1,c_{1},c_{1}^{3},c_{1}^{4})^{T}=15f(c_{1})-7f(c_{2});\\\
M(f)(c_{2})=\mathbf{v}_{f}\cdot\mathbf{M}\cdot(1,c_{2},c_{2}^{3},c_{2}^{4})^{T}=11f(c_{1})-3f(c_{2}).\end{cases}$

For $f_{1},f_{2}\in\text{Span}_{\mathbb{F}_{q}}\\{1,x,g(x),xg(x)\\}$, define
$T$ as the following map over $\mathbb{F}_{q}[x]$

$T:\leavevmode\nobreak\ (f_{1},f_{2})\longmapsto(h_{G_{2}}\circ g)\cdot
f_{1}+(h_{G_{1}}\circ g)\cdot M(f_{2}).$

Note that $h_{G_{1}}\circ g=(g(x)-g(A_{1}))(g(x)-g(A_{2}))$ and
$h_{G_{2}}\circ g=(g(x)-g(B_{1}))(g(x)-g(B_{2}))$. Thus, we have

$T(f_{1},f_{2})\in\text{Span}_{\mathbb{F}_{q}}\\{x^{i}g^{j}\\}_{0\leq i\leq
1\atop 0\leq j\leq 3}.$ (15)

Let $\mathbf{u}=(u_{\alpha},\alpha\in A\cup B\cup C)$ be a vector in
$\mathbb{F}_{q}^{15}$ with coordinates indexed by elements in $A\cup B\cup C$
and

$\begin{cases}u_{a_{ij}}=(h_{G_{2}}\circ g)(a_{ij})^{-1},\leavevmode\nobreak\
(i,j)\in[2]\times[3];\\\ u_{b_{ij}}=\theta_{i}^{-1}(h_{G_{1}}\circ
g)(b_{ij})^{-1},\leavevmode\nobreak\ (i,j)\in[2]\times[3];\\\
u_{c_{i}}=1,\leavevmode\nobreak\ 1\leq i\leq 3.\\\ \end{cases}$

Now, we define the final code $\mathcal{C}^{F}$ as

$\mathcal{C}^{F}=\\{(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in A\cup B\cup
C):\leavevmode\nobreak\
f_{1},f_{2}\in\text{Span}_{\mathbb{F}_{q}}\\{1,x,g(x),xg(x)\\}\\}.$

By (15), $\mathcal{C}^{F}$ is a subcode of the optimal $(15,8,2)$-LRC defined
by $\\{A_{1},A_{2},B_{1},B_{2},C\\}$ and $\mathbf{u}$. Note that

$u_{\alpha}T(f_{1},f_{2})(\alpha)=\begin{cases}f_{1}(a_{i,j}),\leavevmode\nobreak\
\text{when}\leavevmode\nobreak\ \alpha=a_{i,j};\\\
f_{2}(a_{i,j}),\leavevmode\nobreak\ \text{when}\leavevmode\nobreak\
\alpha=b_{i,j}.\end{cases}$

Thus, we have $(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in
A)=(f_{1}(\alpha),\alpha\in A)$ and
$(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in B)=(f_{2}(\alpha),\alpha\in A)$.
This means that we can use $(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in A)$
and $(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in B)$ to reconstruct $f_{1}$
and $f_{2}$, respectively. Thus, $\dim(\mathcal{C}^{F})=8$. Moreover, we have

$\begin{cases}u_{c_{1}}T(f_{1},f_{2})(c_{1})=4f_{1}(c_{1})+10\cdot(15f_{2}(c_{1})-7f_{2}(c_{2})),\\\
u_{c_{2}}T(f_{1},f_{2})(c_{2})=4f_{1}(c_{2})+10\cdot(11f_{2}(c_{1})-3f_{2}(c_{2}))\end{cases}$

and by locality, $u_{c_{3}}T(f_{1},f_{2})(c_{3})$ is a linear combination of
$u_{c_{1}}T(f_{1},f_{2})(c_{1})$ and $u_{c_{2}}T(f_{1},f_{2})(c_{2})$.
Therefore, for any two codewords $\mathbf{c}_{1}=(f_{1}(\alpha),\alpha\in
A\cup C)$ and $\mathbf{c}_{2}=(f_{2}(\alpha),\alpha\in A\cup C)$ in
$\mathcal{C}^{I}$, the map $T$ induces a conversion procedure from
$(\mathbf{c}_{1},\mathbf{c}_{2})$ to
$\mathbf{d}=(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in A\cup B\cup
C)\in\mathcal{C}^{F}$ such that

  * 1)

the $6$ symbols in $\mathbf{c}_{1}|_{A}$ remain in $\mathbf{d}$ as
$\mathbf{d}|_{A}$, and the $6$ symbols in $\mathbf{c}_{2}|_{A}$ remain in
$\mathbf{d}$ as $\mathbf{d}|_{B}$;

  * 2)

the $3$ symbols in $\mathbf{d}|_{C}$ are linear combinations of symbols in
$\mathbf{c}_{1}|_{\\{c_{1},c_{2}\\}}$ and
$\mathbf{c}_{2}|_{\\{c_{1},c_{2}\\}}$.

Therefore, the conversion procedure $T$ has write access cost $3$ and read
access cost $4$.

######  Remark III.1.

Example III.1 provides an overview of the underlying idea of our general
construction. That is, by selecting proper evaluation points
$A_{i}=\\{a_{i,1},\ldots,a_{i,r+1}\\}$,
$B_{i}=\\{b_{i,1},\ldots,b_{i,r+1}\\}$, $1\leq i\leq k$ and
$C_{i}=\\{c_{i,1},\ldots,c_{i,r+1}\\}$, $1\leq i\leq l$, we can obtain a
polynomial $g$ and a surjective map
$T:\text{Span}_{\mathbb{F}_{q}}\\{x^{s}g^{t}\\}_{0\leq s\leq r-1\atop 0\leq
t\leq k-1}\times\text{Span}_{\mathbb{F}_{q}}\\{x^{s}g^{t}\\}_{0\leq s\leq
r-1\atop 0\leq t\leq
k-1}\rightarrow\text{Span}_{\mathbb{F}_{q}}\\{x^{s}g^{t}\\}_{0\leq s\leq
r-1\atop 0\leq t\leq 2k-1}$ such that the following holds:

  * 1.

$g$ is a good polynomial, i.e., $\deg(g)=r+1$ and $g$ is constant on each
$A_{i}$, $B_{i}$ and $C_{i}$.

  * 2.

For any $f_{1},f_{2}\in\text{Span}_{\mathbb{F}_{q}}\\{x^{s}g^{t}\\}_{0\leq
s\leq r-1\atop 0\leq t\leq k-1}$,
$T(f_{1},f_{2})(a_{i,j})=\alpha_{i,j}f_{1}(a_{i,j})$ and
$T(f_{1},f_{2})(b_{i,j})=\beta_{i,j}f_{2}(a_{i,j})$, where for each
$(i,j)\in[k]\times[r+1]$, $\alpha_{i,j}$ and $\beta_{i,j}$ are non-zero
constants determined by $A=\bigcup_{i\in[k]}A_{i}$, $B=\bigcup_{i\in[k]}B_{i}$
and $C=\bigcup_{i\in[l]}C_{i}$;

  * 3.

For any $f_{1},f_{2}\in\text{Span}_{\mathbb{F}_{q}}\\{x^{s}g^{t}\\}_{0\leq
s\leq r-1\atop 0\leq t\leq k-1}$,
$T(f_{1},f_{2})(c_{i,j})=\sum_{(i^{\prime},j^{\prime})\in[l]\times[r]}(\gamma_{i,j,i^{\prime},j^{\prime}}^{(1)}f_{1}(c_{i^{\prime},j^{\prime}})+\gamma_{i,j,i^{\prime},j^{\prime}}^{(2)}f_{2}(c_{i^{\prime},j^{\prime}}))$,
where for each $(i,i^{\prime},j,j^{\prime})\in[l]\times[l]\times[r]\times[r]$,
$\gamma_{i,j,i^{\prime},j^{\prime}}^{(1)}$ and
$\gamma_{i,j,i^{\prime},j^{\prime}}^{(2)}$ are constants determined by $A$,
$B$ and $C$.

Then, let $\mathcal{C}^{I}$ be the $((k+l)(r+1),kr,r)$-optimal LRC defined by
$\\{A_{1},\ldots,A_{k},C_{1},\ldots,C_{l}\\}$ and $g$, and define
$\mathcal{C}^{F}$ as

$\mathcal{C}^{F}=\\{(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in A\cup B\cup
C):\leavevmode\nobreak\
f_{1},f_{2}\in\text{Span}_{\mathbb{F}_{q}}\\{x^{s}g^{t}\\}_{0\leq s\leq
r-1\atop 0\leq t\leq k-1}\\},$

where $u_{a_{i,j}}=\alpha_{i,j}^{-1}$, $u_{b_{i,j}}=\beta_{i,j}^{-1}$ and
$u_{c_{i,j}}=1$. Since $T$ is surjective, $\mathcal{C}^{F}$ is actually the
$((2k+l)(r+1),kr,r)$-optimal LRC defined by
$\\{A_{1},\ldots,A_{k},B_{1},\ldots,B_{k},C_{1},\ldots,C_{l}\\}$, $g$ and
vector $(u_{\alpha},\alpha\in A\cup B\cup C)$.

The map $T$ induces a conversion procedure from $\mathcal{C}^{I}$ to
$\mathcal{C}^{F}$, that is, codewords $\mathbf{c}_{1}=(f_{1}(\alpha),\alpha\in
A\cup C)$ and $\mathbf{c}_{2}=(f_{2}(\alpha),\alpha\in A\cup C)$ are mapped to
$\mathbf{d}=(u_{\alpha}T(f_{1},f_{2})(\alpha),\alpha\in A\cup B\cup C)$, where
$f_{1},f_{2}\in\text{Span}_{\mathbb{F}_{q}}\\{x^{s}g^{t}\\}_{0\leq s\leq
r-1\atop 0\leq t\leq k-1}$. Similar to Example III.1, one can easily verify
that $\mathbf{d}|_{A}=\mathbf{c}_{1}|_{A}$,
$\mathbf{d}|_{B}=\mathbf{c}_{2}|_{A}$ and symbols in $\mathbf{d}|_{C}$ are
linear combinations of symbols in $\mathbf{c}_{1}|_{\tilde{C}}$ and
$\mathbf{c}_{2}|_{\tilde{C}}$, where
$\tilde{C}=\bigcup_{i\in[l]}C_{i}\setminus\\{c_{i,r+1}\\}$. This will imply
that $(\mathcal{C}^{I},\mathcal{C}^{F})$ is an optimal LRCC with write access
cost $l(r+1)$ and read access cost $2lr$.

######  Remark III.2.

In Example III.1, the map $T$ is defined as

$T:\leavevmode\nobreak\ (f_{1},f_{2})\longmapsto(h_{G_{2}}\circ g)\cdot
f_{1}+(h_{G_{1}}\circ g)\cdot M(f_{2}),$

where $G_{1}=\\{g(A_{1}),\ldots,g(A_{k})\\}$,
$G_{2}=\\{g(B_{1}),\ldots,g(B_{k})\\}$ and
$M(f_{2})\in\text{Span}_{\mathbb{F}_{q}}\\{x^{s}g^{t}\\}_{0\leq s\leq r-1\atop
0\leq t\leq k-1}$ is the polynomial with coefficient vector
$\mathbf{v}_{f_{2}}\cdot\mathbf{M}$ w.r.t. basis $\\{x^{s}g^{t}\\}_{0\leq
s\leq r-1\atop 0\leq t\leq k-1}$. Note that $\mathbf{M}$ is a $kr\times kr$
matrix satisfying:

  * 1.

For every $(i,j)\in[k]\times[r+1]$,
$\mathbf{M}\cdot\mathbf{b}_{i,j}=\theta_{i}\mathbf{a}_{i,j}$, where
$\mathbf{a}_{i,j}=(a_{i,j}^{s}g^{t}(a_{i,j}),\leavevmode\nobreak\
(s,t)\in[0,r-1]\times[0,k-1])^{T}$,
$\mathbf{b}_{i,j}=(b_{i,j}^{s}g^{t}(b_{i,j}),\leavevmode\nobreak\
(s,t)\in[0,r-1]\times[0,k-1])^{T}$ and for each $1\leq i\leq k$, $\theta_{i}$
is a non-zero constant determined by $A$, $B$ and $C$;

  * 2.

For every $(i,j)\in[l]\times[r]$,
$\mathbf{M}\cdot\mathbf{c}_{i,j}\in\text{Span}_{\mathbb{F}_{q}}\\{\mathbf{c}_{i^{\prime},j^{\prime}}:\leavevmode\nobreak\
(i^{\prime},j^{\prime})\in[l]\times[r]\\}$, where
$\mathbf{c}_{i,j}=(c_{i,j}^{s}g^{t}(c_{i,j}),\leavevmode\nobreak\
(s,t)\in[0,r-1]\times[0,l-1])^{T}$.

As we shall prove Section III-C, these properties of $\mathbf{M}$ ensure the
map $T$ defined above satisfying the requirements in Remark III.1. Thus, the
crucial part of the construction is to find proper subsets $A$, $B$ and $C$
such that there exists a $kr\times kr$ matrix $\mathbf{M}$ satisfying the
above requirements.

###  III-C Constructions of LRCCs with optimal access costs

Throughout the section, we assume that $n^{I}=(k+l^{I})(r+1)$,
$n^{F}=(k+l^{F})(r+1)$ and $l^{F}\leq\min\\{k,l^{I}\\}$. Similar to Section
II-B, we first assume that $l^{F}=l^{I}=l\leq k$ and present a construction of
optimal LRCCs for this case. Then, we modify it for the general case when
$l^{F}\leq l^{I}\leq k$.

Construction III: Let $A_{s,i}=\\{a_{s,i,1},\ldots,a_{s,i,r+1}\\}$,
$(s,i)\in[\zeta]\times[k]$ and $C_{i}=\\{c_{i,1},\ldots,c_{i,r+1}\\}$, $1\leq
i\leq l$, be mutually disjoint $(r+1)$-subsets of $\mathbb{F}_{q}$ such that
the following holds:

Condition 1

There is a polynomial $g(x)\in\mathbb{F}_{q}[x]$ of degree $r+1$ such that $g$
is constant on each $(s,i)\in[\zeta]\times[k]$ and $C_{i}$, $1\leq i\leq l$.
Denote $G_{0}=\\{g({C_{1}}),\ldots,g({C_{l}})\\}$ and
$G_{s}=\\{g({A_{s,1}}),\ldots,g({A_{s,k}})\\}$.

Condition 2

For every $2\leq s\leq\zeta$, there is a $kr\times kr$ matrix $\mathbf{M}_{s}$
satisfying:

$\begin{cases}\mathbf{M}_{s}\cdot\mathbf{a}_{s,i,j}=\theta_{s,i}\mathbf{a}_{1,i,j},\leavevmode\nobreak\
(i,j)\in[k]\times[r+1];\\\
\mathbf{M}_{s}\cdot\mathbf{c}_{i,j}\in\text{Span}_{\mathbb{F}_{q}}\\{\mathbf{c}_{i^{\prime},j^{\prime}}:\leavevmode\nobreak\
(i^{\prime},j^{\prime})\in[l]\times[r]\\},\leavevmode\nobreak\
(i,j)\in[l]\times[r],\end{cases}$ (16)

where
$\mathbf{a}_{s,i,j}=(a_{s,i,j}^{t_{1}}g^{t_{2}}(a_{s,i,j}),\leavevmode\nobreak\
(t_{1},t_{2})\in[0,r-1]\times[0,k-1])^{T}$,
$\mathbf{c}_{i,j}=(c_{i,j}^{t_{1}}g^{t_{2}}(c_{i,j}),\leavevmode\nobreak\
(t_{1},t_{2})\in[0,r-1]\times[0,l-1])^{T}$ and

$\theta_{s,i}=\frac{h_{G_{s}\cup
G_{0}\setminus\\{g(A_{s,i})\\}}(g(A_{s,i}))}{h_{G_{1}\cup
G_{0}\setminus\\{g(A_{1,i})\\}}(g(A_{1,i}))}.$

Denote $A_{s}=\bigcup_{i=1}^{k}A_{s,i}$, $C=\bigcup_{i=1}^{l}C_{i}$,
$G=\bigcup_{s=1}^{\zeta}G_{s}$ and
$V_{k,r}=\text{Span}_{\mathbb{F}_{q}}\\{x^{t_{1}}g^{t_{2}}\\}_{0\leq t_{1}\leq
r-1\atop 0\leq t_{2}\leq k-1}$. Then, define $\mathcal{C}^{I}$ as

$\mathcal{C}^{I}=\\{(f(\alpha),\leavevmode\nobreak\ \alpha\in A_{1}\cup
C):\leavevmode\nobreak\ f\in V_{k,r}\\}.$

Let $\mathbf{M}_{1}=\mathbf{I}$ and define the map $T$ as

$\displaystyle T:\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \left(V_{k,r}\right)^{\zeta}$
$\displaystyle\longrightarrow V_{\zeta k,r}$
$\displaystyle(f_{1},\ldots,f_{\zeta})$
$\displaystyle\longmapsto\sum_{s=1}^{\zeta}(h_{G\setminus G_{s}}\circ g)\cdot
M_{s}(f_{s}),$ (17)

where $M_{s}(f_{s})\in V_{k,r}$ is the polynomial with coefficient vector
$\mathbf{v}_{f_{s}}\cdot\mathbf{M}_{s}$ w.r.t. basis
$\\{x^{t_{1}}g^{t_{2}}\\}_{0\leq t_{1}\leq r-1\atop 0\leq t_{2}\leq k-1}$.
Then, we define the final code $\mathcal{C}^{F}$ as

$\displaystyle\mathcal{C}^{F}=\\{(u_{\alpha}T(f_{1},\ldots,f_{\zeta})(\alpha),\leavevmode\nobreak\
\alpha\in(\bigcup_{s=1}^{\zeta}A_{s})\cup C):f_{s}\in
V_{k,r},\leavevmode\nobreak\ 1\leq s\leq\zeta\\},$ (18)

where $u_{\alpha}=\theta_{s,i}^{-1}h_{G\setminus G_{s}}^{-1}(g(A_{s,i}))$,
when $\alpha=a_{s,i,j}$ and $u_{\alpha}=1$, when $\alpha=c_{i,j}$.

######  Theorem III.1.

For positive integers $\zeta\geq 2$, $r$, $k$ and $l^{F}=l^{I}=l\leq k$, the
$(\mathcal{C}^{I},\mathcal{C}^{F})$ given by Construction III is an
$(n^{I},kr,r;n^{F},\zeta kr,r)$ optimal LRCC with write access cost $l(r+1)$
and read access cost $\zeta lr$.

###### Proof.

Clearly, $\mathcal{C}^{I}$ is the $(n^{I},kr,r)$-optimal LRC defined by
$\\{A_{1,i}\\}_{i=1}^{k}\cup\\{C_{i}\\}_{i=1}^{l}$ and $g$. Let
$\mathbf{c}_{1},\ldots,\mathbf{c}_{\zeta}\in\mathcal{C}^{I}$ be the $\zeta$
initial codewords and denote $f_{i}(x)\in V_{k,r}$ as the encoding polynomial
of $\mathbf{c}_{i}$. Since for every $1\leq s\leq\zeta$, $M_{s}(f_{s})\in
V_{k,r}$ and

$(h_{G\setminus G_{s}}\circ g)(x)=\prod_{\alpha\in G\setminus
G_{s}}(g(x)-\alpha)\in\text{Span}_{\mathbb{F}_{q}}\\{g^{i}\\}_{0\leq
i\leq(\zeta-1)k},$

we have $T(f_{1},\ldots,f_{\zeta})\in V_{\zeta k,r}$. Thus, $\mathcal{C}^{F}$
is a subcode of the following $(n^{F},\zeta kr,r)$-optimal LRC:

$\mathcal{C}_{0}=\\{(u_{\alpha}f(\alpha),\leavevmode\nobreak\
\alpha\in(\bigcup_{s=1}^{\zeta}A_{s})\cup C):\leavevmode\nobreak\ f\in
V_{\zeta k,r}\\}.$

Moreover, the map $T$ induces a conversion procedure from $\mathcal{C}^{I}$ to
$\mathcal{C}^{F}$, that is, $\mathbf{c}_{1},\ldots,\mathbf{c}_{\zeta}$ are
converted to the following codeword

$\mathbf{d}=(u_{\alpha}T(f_{1},\ldots,f_{\zeta})(\alpha),\leavevmode\nobreak\
\alpha\in(\bigcup_{s=1}^{\zeta}A_{s})\cup C).$

Next, we show that the read and write access costs of the conversion procedure
induced by $T$ are $\zeta lr$ and $l(r+1)$, respectively. As a byproduct, we
shall see that $\mathcal{C}^{F}=\mathcal{C}_{0}$, which yields the result.

For each $(s,i,j)\in[\zeta]\times[k]\times[r+1]$ and $\alpha=a_{s,i,j}$, by
$g(a_{s,i,j})=g(A_{s,i})$ and $h_{G\setminus G_{s}}(x)=\prod_{w\in G\setminus
G_{s}}(x-w)$, we have

$\displaystyle u_{\alpha}T(f_{1},\ldots,f_{\zeta})(\alpha)$
$\displaystyle=\theta_{s,i}^{-1}h_{G\setminus
G_{s}}^{-1}(g(A_{s,i}))\sum_{s^{\prime}=1}^{\zeta}h_{G\setminus
G_{s^{\prime}}}(g(A_{s,i}))(M_{s^{\prime}}(f_{s^{\prime}}))(a_{s,i,j})$
$\displaystyle=\theta_{s,i}^{-1}(M_{s}(f_{s}))(a_{s,i,j})$
$\displaystyle=f_{s}(a_{1,i,j}),$

where the last equality follows from
$(M_{s}(f_{s}))(a_{s,i,j})=\mathbf{v}_{f_{s}}\cdot\mathbf{M}_{s}\cdot\mathbf{a}_{s,i,j}=\theta_{s,i}f_{s}(a_{1,i,j})$.
This leads to

$\mathbf{d}|_{A_{s}}=\mathbf{c}_{s}|_{A_{1}}=(f_{s}(\alpha),\leavevmode\nobreak\
\alpha\in A_{1}).$

Thus, for each $1\leq s\leq\zeta$, there are at least $k(r+1)$ symbols in
$\mathbf{c}_{i}$ that remains in $\mathbf{d}$. This implies that the write
access cost is at most $l(r+1)$. Moreover, by
$\mathcal{C}^{I}|_{A_{1}}=\mathbb{F}_{q}^{kr}$,
$\mathbf{d}|_{A_{s}}=\mathbf{c}_{s}|_{A_{1}}$ also implies that
$\mathcal{C}^{F}|_{\bigcup_{s=1}^{\zeta}A_{s}}=\mathbb{F}_{q}^{\zeta kr}$. In
other words, $\dim(\mathcal{C}^{F})\geq\zeta kr$. By
$\mathcal{C}^{F}\subseteq\mathcal{C}_{0}$, this leads to
$\mathcal{C}^{F}=\mathcal{C}_{0}$.

On the other hand, for each $(i,j)\in[l]\times[r]$ and $\alpha=c_{i,j}$, we
have

$\displaystyle u_{\alpha}T(f_{1},\ldots,f_{\zeta})(\alpha)$
$\displaystyle=\sum_{s=1}^{\zeta}h_{G\setminus
G_{s}}(g(C_{i}))(M_{s}(f_{s}))(c_{i,j}).$ (19)

Since
$\mathbf{M}_{s}\cdot\mathbf{c}_{i,j}\in\text{Span}_{\mathbb{F}_{q}}\\{\mathbf{c}_{i^{\prime},j^{\prime}}:\leavevmode\nobreak\
(i^{\prime},j^{\prime})\in[l]\times[r]\\}$, we can assume that
$\mathbf{M}_{s}\cdot\mathbf{c}_{i,j}=\sum_{(i^{\prime},j^{\prime})\in[l]\times[r]}\eta_{s,i^{\prime},j^{\prime}}\mathbf{c}_{i^{\prime},j^{\prime}}$.
Therefore,

$\displaystyle(M_{s}(f_{s}))(c_{i,j})$
$\displaystyle=\mathbf{v}_{f_{s}}\cdot\left(\sum_{(i^{\prime},j^{\prime})\in[l]\times[r]}\eta_{s,i^{\prime},j^{\prime}}\mathbf{c}_{i^{\prime},j^{\prime}}\right)$
$\displaystyle=\sum_{(i^{\prime},j^{\prime})\in[l]\times[r]}\eta_{s,i^{\prime},j^{\prime}}f_{s}(c_{i^{\prime},j^{\prime}}).$
(20)

Denote $\tilde{C}=\bigcup_{i\in[l]}C_{i}\setminus\\{c_{i,r+1}\\}$. Note that
$f_{s}(c_{i,j})=\mathbf{c}_{s}|_{\\{c_{i,j}\\}}$. Thus, (19) and (20) implies
that for every $1\leq j\leq l$, symbols in
$\mathbf{d}|_{C_{j}\setminus\\{c_{j,r+1}\\}}$ are linear combinations of the
$\zeta lr$ symbols in
$\mathbf{c}_{1}|_{\tilde{C}},\ldots,\mathbf{c}_{\zeta}|_{\tilde{C}}$.
Moreover, by locality, $\mathbf{d}|_{\\{c_{j,r+1}\\}}$ can be recovered by the
$r$ symbols in $\mathbf{d}|_{C_{j}\setminus\\{c_{j,r+1}\\}}$. Therefore, all
the $l(r+1)$ symbols of $\mathbf{d}|_{C}$ can be constructed by the $\zeta lr$
symbols in
$\mathbf{c}_{1}|_{\tilde{C}},\ldots,\mathbf{c}_{\zeta}|_{\tilde{C}}$. Thus,
the read access cost is at most $\zeta lr$. ∎

Now, we present the construction for the case when $l^{F}\leq l^{I}$, which
follows the same idea as Construction II.

Construction IV: Let $A_{s,i}$, $A_{s}$, $C_{i}$ and $g(x)$ be identical to
those defined in Construction III. For $1\leq i\leq l^{I}-l^{F}$, let
$B_{i}=\\{b_{i,1},\ldots,b_{i,r+1}\\}$ be mutually disjoint subsets of size
$r+1$ in $\mathbb{F}_{q}\setminus A_{1}\cup C$ such that $g$ is constant on
each $B_{i}$. Denote $B=\bigcup_{i=1}^{l^{I}-l^{F}}B_{i}$.444When
$l^{I}=l^{F}$, $B=\emptyset$ Define $\mathcal{C}^{I}$ as the following optimal
$(n^{I},kr,r)$-LRC:

$\mathcal{C}^{I}=\\{(f(\alpha),\leavevmode\nobreak\ \alpha\in A_{1}\cup C\cup
B):f\in V_{k,r}\\}.$

Let $T$ and the final code $\mathcal{C}^{F}$ be the same as those defined in
(III-C) and (18).

Under this construction, symbols indexed by evaluation points $B$ of codewords
in $\mathcal{C}^{I}$ don’t participant the conversion procedure induced by
$T$. Thus, by Theorem III.1, we have the following immediate result.

######  Theorem III.2.

For positive integers $\zeta\geq 2$, $r$, $k$, $l^{I}$ and
$l^{F}\leq\min\\{k,l^{I}\\}$, the $(\mathcal{C}^{I},\mathcal{C}^{F})$ given by
Construction IV is an $(n^{I},kr,r;n^{F},\zeta kr,r)$ optimal LRCC with write
access cost $l^{F}(r+1)$ and read access cost $\zeta l^{F}r$.

###  III-D A family of LRCCs with optimal access costs

From Section III-C, the key to implementing Construction III and IV lies in
finding proper subsets $A_{s}$’s and $C$ from $\mathbb{F}_{q}$, such that
there exist matrices $\mathbf{M}_{s}$’s satisfying conditions 1 and 2 in
Construction III. Like Section II-C, in the following, we first give a
sufficient condition for when $A_{s}$’s and $C$ can ensure the existence of
such $\mathbf{M}_{s}$’s. Then, we give an explicit construction of $A_{s,i}$
and $C_{i}$ satisfying this sufficient condition. Together with proper subset
$B$, we provide an implementation of Construction IV, and obtain a family of
LRCCs with optimal access costs.

######  Lemma III.3.

For positive integers $\zeta\geq 2$, $r$, $k$ and $l\leq k$, let
$A_{i}=\\{a_{i,1},\ldots,a_{i,r+1}\\}$,
$B_{i}=\\{b_{i,1},\ldots,b_{i,r+1}\\}$, $1\leq i\leq k$, and
$C_{i}=\\{c_{i,1},\ldots,c_{i,r+1}\\}$, $1\leq i\leq l$, be mutually disjoint
$(r+1)$-subsets of $\mathbb{F}_{q}$. Let $g$ be a polynomial of degree $r+1$
such that $g$ is constant on each $A_{i}$, $B_{i}$ and $C_{i}$. Denote
$G_{0}=\\{g(C_{1}),\ldots,g(C_{l})\\}$, $G_{1}=\\{g(A_{1}),\ldots,g(A_{k})\\}$
and $G_{2}=\\{g(B_{1}),\ldots,g(B_{k})\\}$. Suppose that

  * i)

there is an invertible matrix $\mathbf{T}$ of order $r$ such that
$\mathbf{B}_{i}^{(r)}=\mathbf{T}\mathbf{A}_{i}^{(r)}$ for every $1\leq i\leq
k$;

  * ii)

there is an invertibel matrix $\mathbf{T}^{\prime}$ of order $l$ such that
$\mathbf{G}_{2}^{(l)}=\mathbf{T}^{\prime}\mathbf{G}_{1}^{(l)}$.

Then, there is a $kr\times kr$ matrix $\mathbf{M}$ satisfying:

$\begin{cases}\mathbf{M}\cdot\mathbf{b}_{i,j}=\theta_{i}\mathbf{a}_{i,j},\leavevmode\nobreak\
(i,j)\in[k]\times[r+1];\\\
\mathbf{M}\cdot\mathbf{c}_{i,j}\in\text{Span}_{\mathbb{F}_{q}}\\{\mathbf{c}_{i^{\prime},j^{\prime}}:\leavevmode\nobreak\
(i^{\prime},j^{\prime})\in[l]\times[r]\\},\leavevmode\nobreak\
(i,j)\in[l]\times[r],\end{cases}$

where $\mathbf{a}_{i,j}=(a_{i,j}^{s}g^{t}(a_{i,j}),\leavevmode\nobreak\
(s,t)\in[0,r-1]\times[0,k-1])^{T}$,
$\mathbf{b}_{i,j}=(b_{i,j}^{s}g^{t}(b_{i,j}),\leavevmode\nobreak\
(s,t)\in[0,r-1]\times[0,k-1])^{T}$,
$\mathbf{c}_{i,j}=(c_{i,j}^{s}g^{t}(c_{i,j}),\leavevmode\nobreak\
(s,t)\in[0,r-1]\times[0,l-1])^{T}$ and

$\theta_{i}=\frac{h_{G_{2}\cup
G_{0}\setminus\\{g(B_{i})\\}}(g(B_{i}))}{h_{G_{1}\cup
G_{0}\setminus\\{g(A_{i})\\}}(g(A_{i}))}.$

By Lemma III.3, we have the following immediate corollary, which provides a
sufficient condition for the existence of $\mathbf{M}_{s}$’s satisfying
condition 2 in Construction III.

######  Corollary III.1.

Let $\zeta\geq 2$, $r$, $k$ and $l<k$ be positive integers. Let
$A_{s,i}=\\{a_{s,i,1},\ldots,a_{s,i,r+1}\\}$, $(s,i)\in[\zeta]\times[k]$ and
$C_{i}=\\{c_{i,1},\ldots,c_{i,r+1}\\}$, $1\leq i\leq l$, be mutually disjoint
$(r+1)$-subsets of $\mathbb{F}_{q}$. Let $g$ be a polynomial of degree $r+1$
such that $g$ is constant on each $A_{s,i}$ and $C_{i}$. Denote
$G_{0}=\\{g({C_{1}}),\ldots,g({C_{l}})\\}$ and
$G_{s}=\\{g(A_{s,1}),\ldots,g(A_{s,k})\\}$, $1\leq s\leq\zeta$. If for every
$2\leq s\leq\zeta$,

  * i)

there is an invertible matrix $\mathbf{T}_{s}$ of order $r$ such that
$\mathbf{A}_{s,i}^{(r)}=\mathbf{T}_{s}\mathbf{A}_{1,i}^{(r)}$ for every $1\leq
i\leq k$;

  * ii)

there is an invertible matrix $\mathbf{T}_{s}^{\prime}$ of order $l$ such that
$\mathbf{G}_{s}^{(l)}=\mathbf{T}_{s}^{\prime}\mathbf{G}_{1}^{(l)}$.

Then, for every $2\leq s\leq\zeta$, there is a $kr\times kr$ matrix
$\mathbf{M}_{s}$ satisfying condition 2 in Construction III.

Now, we present the proof of Lemma III.3.

###### Proof of Lemma III.3.

Denote $V_{k,r}=\text{Span}_{\mathbb{F}_{q}}\\{x^{s}g^{t}\\}_{0\leq s\leq
r-1\atop 0\leq t\leq k-1}$. Denote $g_{1,i}=g(A_{i})$, $g_{2,i}=g(B_{i})$ and
$g_{0,i}=g(C_{i})$. Let $\tilde{A}_{i}=A_{i}\setminus\\{a_{i,r+1}\\}$ and
$\tilde{B}_{i}=B_{i}\setminus\\{b_{i,r+1}\\}$. By $1)$ in Lemma A.1,
$\\{\mathbf{a}_{i,j}\\}_{1\leq i\leq k\atop 1\leq j\leq r}$ and
$\\{\mathbf{b}_{i,j}\\}_{1\leq i\leq k\atop 1\leq j\leq r}$ form two bases of
$\mathbb{F}_{q}^{kr}$ and
$\text{Span}_{\mathbb{F}_{q}}\\{\mathbf{c}_{i,j}:\leavevmode\nobreak\
(i,j)\in[l]\times[r]\\}$ has dimension $lr$. Moreover, by $2)$ in Lemma A.1,
we also have

$\displaystyle\mathbf{a}_{i,r+1}$
$\displaystyle=\sum_{j=1}^{r}\frac{h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(a_{i,r+1})}{h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(a_{i,j})}\mathbf{a}_{i,j},$
(21) $\displaystyle\mathbf{b}_{i,r+1}$
$\displaystyle=\sum_{j=1}^{r}\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(b_{i,r+1})}{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(b_{i,j})}\mathbf{b}_{i,j}$
(22)

for every $1\leq i\leq k$ and

$\mathbf{c}_{s,t}=\sum_{(i,j)\in[k]\times[r]}\frac{h_{G_{2}\setminus\\{g_{2,i}\\}}(g_{0,s})}{h_{G_{2}\setminus\\{g_{2,i}\\}}(g_{2,i})}\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(c_{s,t})}{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(b_{i,j})}\mathbf{b}_{i,j}$
(23)

for every $(s,t)\in[l]\times[r]$.

Denote
$\mathbf{A}=(\mathbf{a}_{1,1},\ldots,\mathbf{a}_{1,r},\ldots,\mathbf{a}_{k,1},\ldots,\mathbf{a}_{k,r})$
and
$\mathbf{B}=(\mathbf{b}_{1,1},\ldots,\mathbf{b}_{1,r},\ldots,\mathbf{b}_{k,1},\ldots,\mathbf{b}_{k,r})$
as the $kr\times kr$ matrices with $(i-1)r+j$-th column $\mathbf{a}_{i,j}$ and
$\mathbf{b}_{i,j}$, respectively. Define vector

$\bm{\theta}=(\underbrace{\theta_{1},\ldots,\theta_{1}}_{r},\underbrace{\theta_{2},\ldots,\theta_{2}}_{r},\ldots,\underbrace{\theta_{k},\ldots,\theta_{k}}_{r}).$

Then, we define matrix $\mathbf{M}$ as

$\displaystyle\mathbf{M}=\mathbf{A}\cdot\text{diag}(\bm{\theta})\cdot\mathbf{B}^{-1}.$
(24)

Next, we show that $\mathbf{M}$ satisfies the two properties claimed in the
statement of Lemma III.3.

Clearly, for every $(i,j)\in[k]\times[r]$,
$\mathbf{M}\cdot\mathbf{b}_{i,j}=\theta_{i}\mathbf{a}_{i,j}$. To confirm the
first property, we only need to show that
$\mathbf{M}\cdot\mathbf{b}_{i,r+1}=\theta_{i}\mathbf{a}_{i,r+1}$ holds for
every $1\leq i\leq k$. By
$\mathbf{B}_{i}^{(r)}=\mathbf{T}\mathbf{A}_{i}^{(r)}$, we have
$(1,\ldots,b_{i,r+1}^{r-1})^{T}=\mathbf{T}\cdot(1,\ldots,a_{i,r+1}^{r-1})^{T}$
and $\mathbf{T}=\tilde{\mathbf{B}}_{i}\tilde{\mathbf{A}}_{i}^{-1}$, where
$\tilde{\mathbf{A}}_{i}$ and $\tilde{\mathbf{B}}_{i}$ are the $r\times r$
Vandermonde matrix generated by $\tilde{A}_{i}$ and $\tilde{B}_{i}$,
respectively. Thus,
$\tilde{\mathbf{B}}_{i}^{-1}\cdot(1,\ldots,b_{i,r+1}^{r-1})^{T}=\tilde{\mathbf{A}}_{i}^{-1}\cdot(1,\ldots,a_{i,r+1}^{r-1})^{T}$.
Note that for every $1\leq i\leq k$ and $x\in\mathbb{F}_{q}$,

$\displaystyle\tilde{\mathbf{A}}_{i}^{-1}\cdot(1,\ldots,x^{r-1})^{T}$
$\displaystyle=(\frac{h_{\tilde{A}_{i}\setminus\\{a_{i,1}\\}}(x)}{h_{\tilde{A}_{i}\setminus\\{a_{i,1}\\}}(a_{i,1})},\ldots,\frac{h_{\tilde{A}_{i}\setminus\\{a_{i,r}\\}}(x)}{h_{\tilde{A}_{i}\setminus\\{a_{i,r}\\}}(a_{i,r})})^{T},$
$\displaystyle\tilde{\mathbf{B}}_{i}^{-1}\cdot(1,\ldots,x^{r-1})^{T}$
$\displaystyle=(\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,1}\\}}(x)}{h_{\tilde{B}_{i}\setminus\\{b_{i,1}\\}}(b_{i,1})},\ldots,\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,r}\\}}(x)}{h_{\tilde{B}_{i}\setminus\\{b_{i,r}\\}}(b_{i,r})})^{T}.$
(25)

Thus,
$\frac{h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(a_{i,r+1})}{h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(a_{i,j})}=\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(b_{i,r+1})}{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(b_{i,j})}$
for every $1\leq j\leq r$. By (22) and (24), this implies that

$\displaystyle\mathbf{M}\cdot\mathbf{b}_{i,r+1}$
$\displaystyle=\theta_{i}\sum_{j=1}^{r}\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(b_{i,r+1})}{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(b_{i,j})}\mathbf{a}_{i,j}$
$\displaystyle=\theta_{i}\sum_{j=1}^{r}\frac{h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(a_{i,r+1})}{h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(a_{i,j})}\mathbf{a}_{i,j}.$

Thus, $\mathbf{M}\cdot\mathbf{b}_{i,r+1}=\theta_{i}\mathbf{a}_{i,r+1}$ follows
from (21). This confirms the first property.

Next, we show that for each $(i,j)\in[l]\times[r]$,
$\mathbf{M}\cdot\mathbf{c}_{i,j}\in\text{Span}_{\mathbb{F}_{q}}\\{\mathbf{c}_{i^{\prime},j^{\prime}}:\leavevmode\nobreak\
(i^{\prime},j^{\prime})\in[l]\times[r]\\}$.

Define $H_{C}(x)=(h_{G_{0}}\circ
g)(x)=\prod_{i=1}^{l}\left(g(x)-g_{0,i}\right)$. Then, for every $f\in
V_{k-l,r}$, $H_{C}\cdot f\in V_{k,r}$. Denote $\mathbf{v}_{H_{C}\cdot
f}\in\mathbb{F}_{q}^{kr}$ as the coefficient vector of $H_{C}\cdot f$ w.r.t.
basis $\\{x^{s}g^{t}\\}_{0\leq s\leq r-1\atop 0\leq t\leq k-1}$. Then, for
every $(s,t)\in[l]\times[r]$, by (23), we have

$\displaystyle\mathbf{v}_{H_{C}\cdot f}\cdot\mathbf{M}\cdot\mathbf{c}_{s,t}$
$\displaystyle=\sum_{(i,j)\in[k]\times[r]}\frac{h_{G_{2}\setminus\\{g_{2,i}\\}}(g_{0,s})}{h_{G_{2}\setminus\\{g_{2,i}\\}}(g_{2,i})}\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(c_{s,t})}{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(b_{i,j})}\theta_{i}(\mathbf{v}_{H_{C}\cdot
f}\cdot\mathbf{a}_{i,j})$
$\displaystyle=\sum_{(i,j)\in[k]\times[r]}\frac{h_{G_{2}\setminus\\{g_{2,i}\\}}(g_{0,s})}{h_{G_{2}\setminus\\{g_{2,i}\\}}(g_{2,i})}\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(c_{s,t})}{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(b_{i,j})}\theta_{i}(H_{C}\cdot
f)({a}_{i,j}).$ (26)

Since $\theta_{i}=\frac{h_{G_{2}\cup
G_{0}\setminus\\{g_{2,i}\\}}(g_{2,i})}{h_{G_{1}\cup
G_{0}\setminus\\{g_{1,i}\\}}(g_{1,i})}$ and
$H_{C}(a_{i,j})=h_{G_{0}}(g_{1,i})$, (26) leads to

$\displaystyle\mathbf{v}_{H_{C}\cdot f}\cdot\mathbf{M}\cdot\mathbf{c}_{s,t}$
$\displaystyle=\sum_{(i,j)\in[k]\times[r]}\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(c_{s,t})}{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(b_{i,j})}\frac{h_{G_{0}}(g_{2,i})}{h_{G_{1}\setminus\\{g_{1,i}\\}}(g_{1,i})}h_{G_{2}\setminus\\{g_{2,i}\\}}(g_{0,s})f({a}_{i,j})$
$\displaystyle=-h_{G_{2}}(g_{0,s})\left(\sum_{(i,j)\in[k]\times[r]}\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(c_{s,t})}{h_{\tilde{B}_{i}\setminus\\{b_{i,j}\\}}(b_{i,j})}\frac{h_{G_{0}\setminus\\{g_{0,s}\\}}(g_{2,i})}{h_{G_{1}\setminus\\{g_{1,i}\\}}(g_{1,i})}f({a}_{i,j})\right),$
(27)

where the 2nd equality follows from

$h_{G_{0}}(g_{2,i})h_{G_{2}\setminus\\{g_{2,i}\\}}(g_{0,s})=-h_{G_{2}}(g_{0,s})h_{G_{0}\setminus\\{g_{0,s}\\}}(g_{2,i}).$

For $1\leq s\leq l$, denote $\mathbf{h}_{G_{0}\setminus\\{g_{0,s}\\}}$ as the
coefficient vector of $h_{G_{0}\setminus\\{g_{0,s}\\}}(x)$ w.r.t. basis
$\\{x^{i}\\}_{i=0}^{l-1}$ and define
$H_{s}(x)=\mathbf{h}_{G_{0}\setminus\\{g_{0,s}\\}}\cdot\mathbf{T}^{\prime}\cdot(1,x,\ldots,x^{l-1})^{T}$.
By $\mathbf{G}_{2}^{(l)}=\mathbf{T}^{\prime}\mathbf{G}_{1}^{(l)}$, we have

$\mathbf{h}_{G_{0}\setminus\\{g_{0,s}\\}}\cdot\mathbf{G}_{2}^{(l)}=\mathbf{h}_{G_{0}\setminus\\{g_{0,s}\\}}\cdot\mathbf{T^{\prime}}\mathbf{G}_{1}^{(l)}.$

Thus, $h_{G_{0}\setminus\\{g_{0,s}\\}}(g_{2,i})=H_{s}(g_{1,i})$ for every
$1\leq i\leq k$. For $1\leq i\leq k$, let

$\mathbf{u}_{i}=\mathbf{T}^{-1}\tilde{\mathbf{A}}_{i}\cdot(\frac{h_{\tilde{A}_{i}\setminus\\{a_{i,1}\\}}(c_{s,t})}{h_{\tilde{A}_{i}\setminus\\{a_{i,1}\\}}(a_{i,1})},\ldots,\frac{h_{\tilde{A}_{i}\setminus\\{a_{i,r}\\}}(c_{s,t})}{h_{\tilde{A}_{i}\setminus\\{a_{i,r}\\}}(a_{i,r})})^{T}.$

By (III-D), we have
$\mathbf{u}_{i}=\mathbf{T}^{-1}\cdot(1,\ldots,c_{s,t}^{r-1})^{T}$. Note that,
$\mathbf{T}=\tilde{\mathbf{B}}_{i}\tilde{\mathbf{A}}_{i}^{-1}$, this leads to

$\displaystyle\tilde{\mathbf{A}}_{i}^{-1}\cdot\mathbf{u}_{i}$
$\displaystyle=\tilde{\mathbf{A}}_{i}^{-1}\mathbf{T}^{-1}\tilde{\mathbf{A}}_{i}\cdot(\frac{h_{\tilde{A}_{i}\setminus\\{a_{i,1}\\}}(c_{s,t})}{h_{\tilde{A}_{i}\setminus\\{a_{i,1}\\}}(a_{i,1})},\ldots,\frac{h_{\tilde{A}_{i}\setminus\\{a_{i,r}\\}}(c_{s,t})}{h_{\tilde{A}_{i}\setminus\\{a_{i,r}\\}}(a_{i,r})})^{T}$
$\displaystyle=\tilde{\mathbf{B}}_{i}^{-1}\cdot(1,\ldots,c_{s,t}^{r-1})^{T}$
$\displaystyle=(\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,1}\\}}(c_{s,t})}{h_{\tilde{B}_{i}\setminus\\{b_{i,1}\\}}(b_{i,1})},\ldots,\frac{h_{\tilde{B}_{i}\setminus\\{b_{i,r}\\}}(c_{s,t})}{h_{\tilde{B}_{i}\setminus\\{b_{i,r}\\}}(b_{i,r})})^{T}.$

Denote $\tilde{H}_{s}(x)=(H_{s}\circ g)(x)$. Then, $(\tilde{H}_{s}\cdot
f)(a_{i,j})=H_{s}(g_{1,i})f(a_{i,j})=h_{G_{0}\setminus\\{g_{0,s}\\}}(g_{2,i})f(a_{i,j})$.
Thus, the RHS of (27) can be simplified as

$\displaystyle-h_{G_{2}}(g_{0,s})\sum_{i\in[k]}((\tilde{H}_{s}\cdot
f)(a_{i,1}),\ldots,(\tilde{H}_{s}\cdot
f)(a_{i,r}))\cdot\frac{\tilde{\mathbf{A}}_{i}^{-1}\cdot\mathbf{u}_{i}}{h_{G_{1}\setminus\\{g_{1,i}\\}}(g_{1,i})}.$
(28)

Note that $\deg(H_{s})\leq l-1$ and $f\in V_{k-l,r}$. Thus,
$\tilde{H}_{s}\cdot f\in\mathbf{V}_{k-1,r}$. Denote
$\tilde{\mathbf{v}}\in\mathbb{F}_{q}^{(k-1)r}$ as the coefficient vector of
$\tilde{H}_{s}\cdot f$ w.r.t. basis $\\{x^{s}g^{t}\\}_{0\leq s\leq k-2\atop
0\leq t\leq r-1}$. Then, for $1\leq i\leq k$, we have

$\tilde{\mathbf{v}}\cdot\left(\begin{array}[]{c}\tilde{\mathbf{A}}_{i}\\\
g_{1,i}\tilde{\mathbf{A}}_{i}\\\ \vdots\\\
g_{1,i}^{k-2}\tilde{\mathbf{A}}_{i}\end{array}\right)=((\tilde{H}_{s}\cdot
f)(a_{i,1}),\ldots,(\tilde{H}_{s}\cdot f)(a_{i,r})).$

On the other hand, by $3)$ in Lemma A.1, we know that

$\left(\begin{array}[]{cccc}\tilde{\mathbf{A}}_{1}&\tilde{\mathbf{A}}_{2}&\cdots&\tilde{\mathbf{A}}_{k}\\\
g_{1,1}\tilde{\mathbf{A}}_{1}&g_{1,2}\tilde{\mathbf{A}}_{2}&\cdots&g_{1,k}\tilde{\mathbf{A}}_{k}\\\
\vdots&\vdots&&\vdots\\\
g_{1,1}^{k-2}\tilde{\mathbf{A}}_{1}&g_{1,2}^{k-2}\tilde{\mathbf{A}}_{2}&\cdots&g_{1,k}^{k-2}\tilde{\mathbf{A}}_{k}\end{array}\right)\cdot\left(\begin{array}[]{c}\frac{\tilde{\mathbf{A}}_{1}^{-1}}{h_{G_{1}\setminus\\{g_{1,1}\\}}(g_{1,1})}\\\
\frac{\tilde{\mathbf{A}}_{2}^{-1}}{h_{G_{1}\setminus\\{g_{1,2}\\}}(g_{1,2})}\\\
\vdots\\\
\frac{\tilde{\mathbf{A}}_{k}^{-1}}{h_{G_{1}\setminus\\{g_{1,k}\\}}(g_{1,k})}\end{array}\right)$
(29)

is an all-$0$ matrix of size $kr\times r$. Then, by (29),
$\sum_{i\in[k]}((\tilde{H}_{s}\cdot f)(a_{i,1}),\ldots,(\tilde{H}_{s}\cdot
f)(a_{i,r}))\cdot\frac{\tilde{\mathbf{A}}_{i}^{-1}\cdot\mathbf{u}_{i}}{h_{G_{1}\setminus\\{g_{1,i}\\}}(g_{1,i})}$
equals to

$\tilde{\mathbf{v}}\cdot\left(\begin{array}[]{ccc}\tilde{\mathbf{A}}_{1}&\cdots&\tilde{\mathbf{A}}_{k}\\\
g_{1,1}\tilde{\mathbf{A}}_{1}&\cdots&g_{1,k}\tilde{\mathbf{A}}_{k}\\\
\vdots&&\vdots\\\
g_{1,1}^{k-2}\tilde{\mathbf{A}}_{1}&\cdots&g_{1,k}^{k-2}\tilde{\mathbf{A}}_{k}\end{array}\right)\cdot\left(\begin{array}[]{c}\frac{\tilde{\mathbf{A}}_{1}^{-1}}{h_{G_{1}\setminus\\{g_{1,1}\\}}(g_{1,1})}\\\
\vdots\\\
\frac{\tilde{\mathbf{A}}_{k}^{-1}}{h_{G_{1}\setminus\\{g_{1,k}\\}}(g_{1,k})}\end{array}\right)\cdot\left(\begin{array}[]{ccc}\mathbf{u}_{1}&&\\\
&\ddots&\\\ &&\mathbf{u}_{k}\end{array}\right)=0.$

By (27) and (28), this implies $\mathbf{v}_{H_{C}\cdot
f}\cdot\mathbf{M}\cdot\mathbf{c}_{s,t}=0$ for every $f\in V_{k-l,r}$ and
$(s,t)\in[l]\times[r]$. Note that $V_{0}=\\{\mathbf{v}_{H_{C}\cdot f}:f\in
V_{k-l,r}\\}$ is a $(k-l)r$-dim subspace of $\mathbb{F}_{q}^{kr}$ and for
every $(s,t)\in[l]\times[r]$

$\mathbf{v}_{H_{C}\cdot f}\cdot\mathbf{c}_{s,t}=(H_{C}\cdot f)(c_{s,t})=0.$

Thus, $\text{Span}_{\mathbb{F}_{q}}\\{\mathbf{c}_{i,j}:\leavevmode\nobreak\
(i,j)\in[l]\times[r]\\}$ is the dual space of $V_{0}$ in
$\mathbb{F}_{q}^{kr}$. Then, $\mathbf{v}_{H_{C}\cdot
f}\cdot\mathbf{M}\cdot\mathbf{c}_{s,t}=0$ implies that
$\mathbf{M}\cdot\mathbf{c}_{s,t}\in\text{Span}_{\mathbb{F}_{q}}\\{\mathbf{c}_{i,j}:\leavevmode\nobreak\
(i,j)\in[l]\times[r]\\}$. This confirms the second property. ∎

In the following, using the multiplicative group of $\mathbb{F}_{q}$, we give
an explicit construction of $A_{s,i}$, $C_{i}$ and $g(x)$ that satisfy the
requirements in Corollary III.1.

Let $\zeta\geq 2$, $r$, $k$, $l^{I}$ and $l^{F}\leq\min\\{k,l^{I}\\}$ be
positive integers. Let $q$ be a prime power such that $k(r+1)|(q-1)$ and

$q\geq k(r+1)\cdot\max\\{\zeta+1,\lceil\frac{l^{I}}{k}\rceil+2\\}+1.$

Let $\beta$ be the generator of the multiplicative group $\mathbb{F}_{q}^{*}$.
Denote $\alpha=\beta^{\frac{q-1}{k(r+1)}}$ and let $G$ be the subgroup of
$\mathbb{F}_{q}^{*}$ generated by $\alpha$. Denote
$\zeta_{0}=\max\\{\zeta,\lceil\frac{l^{I}}{k}\rceil+1\\}$. Clearly,
$|G|=k(r+1)$ and $|\mathbb{F}_{q}^{*}/G|\geq\zeta_{0}+1$. For every
$(s,i,j)\in[0,\zeta_{0}]\times[k]\times[r+1]$, let
$a_{s,i,j}=\beta^{s}\alpha^{i-1+jk}$. Now, we define $g(x)=x^{r+1}$ and

  * •

$A_{s,i}=\\{a_{s-1,i,1},\ldots,a_{s-1,i,r+1}\\}$,
$(s,i)\in[\zeta_{0}]\times[k]$ and $A_{s}=\bigcup_{i=1}^{k}A_{s,i}$;

  * •

$C_{i}=\\{a_{\zeta_{0},i,1},\ldots,a_{\zeta_{0},i,r+1}\\}$, $1\leq i\leq
l^{F}$ and $C=\bigcup_{i=1}^{l^{F}}C_{i}$.

Since $C_{i}\subseteq\beta^{\zeta_{0}}G$ and $A_{s,i}\subseteq\beta^{s-1}G$,
$A_{s,i}$’s and $C_{i}$’s are mutually disjoint. Notice that
$\zeta_{0}-1\geq\lceil\frac{l^{I}}{k}\rceil\geq\lceil\frac{l^{I}-l^{F}}{k}\rceil$.
Thus, $(\zeta_{0}-1)k\geq l^{I}-l^{F}$ and we can pick $l^{I}-l^{F}$ different
$(r+1)$-subsets from $\\{A_{s,i}\\}_{2\leq s\leq\zeta_{0}\atop 1\leq i\leq k}$
as $B_{1},\ldots,B_{l^{I}-l^{F}}$. Denote
$B=\bigcup_{i=1}^{l^{I}-l^{F}}B_{i}$. Clearly, $B_{1},\ldots,B_{l^{I}-l^{F}}$
are mutually disjoint and $B\cap(A_{1}\cup C)=\emptyset$.

Next, we show that the $A_{s,i}$, $C_{i}$ and $g$ defined above satisfy the
requirements in Corollary III.1:

  * •

For each $(s,i,j)\in[0,\zeta_{0}]\times[k]\times[r+1]$, by
$\alpha^{k(r+1)}=1$, we have

$\displaystyle g(\beta^{s}\alpha^{i-1+jk})$
$\displaystyle=\left(\beta^{s}\alpha^{i-1+jk}\right)^{r+1}$
$\displaystyle=\left(\beta^{s}\alpha^{i-1}\right)^{r+1}.$

Thus, $g$ is constant on each $A_{s,i}$ and $C_{i}$.

  * •

Since
$A_{s+1,i}=\\{\beta^{s}\alpha^{i-1+k},\ldots,\beta^{s}\alpha^{i-1+(r+1)k}\\}$,
we have

$\displaystyle\mathbf{A}_{s+1,i}^{(r)}$
$\displaystyle=\left(\begin{array}[]{cccc}1&1&\cdots&1\\\
\beta^{s}\alpha^{i-1+k}&\beta^{s}\alpha^{i-1+2k}&\cdots&\beta^{s}\alpha^{i-1+(r+1)k}\\\
\vdots&\vdots&&\vdots\\\
(\beta^{s}\alpha^{i-1+k})^{r-1}&(\beta^{s}\alpha^{i-1+2k})^{r-1}&\cdots&(\beta^{s}\alpha^{i-1+(r+1)k})^{r-1}\end{array}\right)$
$\displaystyle=\text{diag}(1,\beta^{s-1},\ldots,\beta^{(s-1)(r-1)})\mathbf{A}_{1,i}^{(r)}.$

Take $\mathbf{T}_{s}=\text{diag}(1,\beta^{s-1},\ldots,\beta^{(s-1)(r-1)})$,
clearly, $\mathbf{T}_{s}$ is invertible. This verifies the condition i).

  * •

Let $g_{s,i}$ be the constant $g(A_{s,i})$. Note that for every $1\leq
s\leq\zeta$,

$\displaystyle
G_{s}=\\{g_{s,1},\ldots,g_{s,k}\\}=\\{\beta^{(s-1)(r+1)},\ldots,(\beta^{(s-1)}\alpha^{k-1})^{r+1}\\}.$

Thus, we have

$\displaystyle\mathbf{G}_{s}^{(l^{F})}$
$\displaystyle=\left(\begin{array}[]{cccc}1&1&\cdots&1\\\
\beta^{(s-1)(r+1)}&(\beta^{(s-1)}\alpha)^{r+1}&\cdots&(\beta^{(s-1)}\alpha^{k-1})^{r+1}\\\
\vdots&\vdots&&\vdots\\\
\beta^{(s-1)(r+1)(l^{F}-1)}&(\beta^{(s-1)}\alpha)^{(r+1)(l^{F}-1)}&\cdots&(\beta^{(s-1)}\alpha^{k-1})^{(r+1)(l^{F}-1)}\end{array}\right)$
$\displaystyle=\text{diag}(1,\beta^{(s-1)(r+1)},\ldots,\beta^{(s-1)(r+1)(l^{F}-1)})\mathbf{G}_{1}^{(l^{F})}.$

Take
$\mathbf{T}_{s}^{\prime}=\text{diag}(1,\beta^{(s-1)(r+1)},\ldots,\beta^{(s-1)(r+1)(l^{F}-1)})$,
clearly, $\mathbf{T}_{s}^{\prime}$ is invertible. This verifies the condition
ii).

######  Remark III.3.

The sets $A_{1}$, $A_{2}$, $B_{1}$, $B_{2}$, and $C$ in Example III.1 can be
viewed as an example of the above construction for $q=19$, $k=r=2$,
$l^{I}=l^{F}=1$ and $\zeta=2$.

Clearly, the sets $A_{s,i}$’s and $C_{i}$ constructed above satisfy the
requirements in Corollary III.1. Then, $A_{s,i}$, $B_{i}$ and $C_{i}$
constructed above satisfy the requirements in Construction IV. Thus, we have
the following immediate corollary.

######  Corollary III.2.

For positive integers $\zeta\geq 2$, $r$, $k$, $l^{I}$ and
$l^{F}\leq\min\\{k,l^{I}\\}$, let $q$ be a prime power such that
$k(r+1)\mid(q-1)$ and $q\geq
k(r+1)\cdot\max\\{\zeta+1,\lceil\frac{l^{I}}{k}\rceil+2\\}+1$. Then, there is
an explicit construction of $(n^{I},kr,r;n^{F},\zeta kr,r)$ optimal LRCCs with
write access cost $l(r+1)$ and read access cost $\zeta lr$, where
$n^{I}=(k+l^{I})(r+1)$ and $n^{F}=(k+l^{F})(r+1)$.

##  IV Lower bounds on the access cost

In this section, we prove a general lower bound on the access cost of an
$(n^{I},k;n^{F},\zeta k)$ convertible code with the condition that
$\mathcal{C}^{F}$ is an $r$-LRC. As a consequence, the LRCCs obtained by
Constructions III and IV admit optimal access costs.

Throughout the section, we need the following additional notations. Let
$\mathcal{C}$ be an $(n,k)$ code over $\mathbb{F}_{q}$ and
$\mathbf{m}\in\mathbb{F}_{q}^{k}$ be a message vector, denote
$\mathcal{C}(\mathbf{m})$ as the codeword in $\mathcal{C}$ that encodes
$\mathbf{m}$. Let $(\mathcal{C}^{I},\mathcal{C}^{F})$ be an
$(n^{I},k;n^{F},\zeta k)$ convertible code over $\mathbb{F}_{q}$ with
conversion procedure $T$. For a message vector
$\mathbf{m}\in\mathbb{F}_{q}^{\zeta k}$ and $1\leq i\leq\zeta$, we denote
$\mathbf{c}_{i}=\mathcal{C}^{I}(\mathbf{m}|_{[(i-1)k+1,ik]})$ as the $i$-th
initial codeword and denote $\mathbf{d}=\mathcal{C}^{F}(\mathbf{m})$ as the
final codeword. For $i\in[\zeta]$, we denote $U_{i}\subseteq[n^{I}]$ as the
set of coordinates corresponding to the remaining symbols in $\mathbf{c}_{i}$
and $A_{i}\subseteq[n^{I}]$ as the set of coordinates corresponding to the
accessed symbols in $\mathbf{c}_{i}$. We denote $T(U_{i})\subseteq[n^{F}]$ as
the set of coordinates of the symbols in $\mathbf{d}$ that remains from
$\mathbf{c}_{i}$. Moreover, for $j\in T(U_{i})$, we say the symbol
$\mathbf{d}(j)$ is inherited from $\mathbf{c}_{i}|_{U_{i}}$. Clearly, there is
a one-to-one map between $U_{i}$ and $T(U_{i})$ and for convenience we also
use $T$ to denote this map. In the following, by a slight abuse of notation,
we also use the coordinate $j$ to referred to the corresponding codeword
symbol.

The proof of the general lower bound consists of two parts. First, we prove a
lower bound on the write access cost. To do this, we bound from above the
number of remaining symbols in each initial codewords. Then, we prove a lower
bound on the read access cost based on the locality of $\mathcal{C}^{F}$.

To start with, we prove the following upper bound on $|U_{i}|$.

######  Lemma IV.1.

Let $(\mathcal{C}^{I},\mathcal{C}^{F})$ be an $(n^{I},k;n^{F},\zeta k)$
convertible code over $\mathbb{F}_{q}$ with conversion procedure $T$. Assume
that $\mathcal{C}^{F}$ has locality $r$ and minimum distance $d$. Then, for
every $1\leq i\leq\zeta$, we have

$|U_{i}|=|T(U_{i})|\leq
n^{F}-d-((\zeta-1)k+\lceil\frac{(\zeta-1)k}{r}\rceil)+2.$ (30)

###### Proof.

We only show that (30) holds for $i=1$ and the proofs for cases $2\leq
i\leq\zeta$ are similar.

Let $\tilde{\mathcal{C}}$ be the subcode of $\mathcal{C}^{F}$ that encodes
message vectors in $\\{\mathbf{m}\in\mathbb{F}_{q}^{\zeta
k}:\mathbf{m}|_{[k]}=\mathbf{0}\\}$, i.e.,

$\tilde{\mathcal{C}}=\\{\mathbf{d}\in\mathcal{C}^{F}:\mathbf{d}=\mathcal{C}^{F}((\mathbf{0},\tilde{\mathbf{m}}))\text{\leavevmode\nobreak\
for some\leavevmode\nobreak\
}\tilde{\mathbf{m}}\in\mathbb{F}_{q}^{(\zeta-1)k}\\}.$

Denote $d(\tilde{\mathcal{C}})$ as the minimal distance of
$\tilde{\mathcal{C}}$. Clearly, we have $d(\tilde{\mathcal{C}})\geq d$ and
$|\tilde{\mathcal{C}}|=q^{(\zeta-1)k}$.

Define

$N=\\{i\in[n^{F}]:\leavevmode\nobreak\ i\in T(U_{1}),\leavevmode\nobreak\
\text{or}\leavevmode\nobreak\ i\leavevmode\nobreak\ \text{can be recovered by
symbols in}\leavevmode\nobreak\ T(U_{1})\\}.$

Denote $N^{C}=[n^{F}]\setminus N$. Then, for every $i\in N^{C}$ and every
recovering set $I_{i}$ of $i$, we have $I_{i}\cap N^{C}\neq\emptyset$.
Otherwise, assume that there is an $i_{0}\in N^{C}$ with a recovering set
$I_{0}\subseteq N$. Then, by the definition of $N$, every symbol of $I_{0}$
can be recovered by symbols in $T(U_{1})$. Thus, $i_{0}$ can also be recovered
by symbols in $T(U_{1})$. This leads to $i_{0}\in N$, a contradiction.

Let $\mathbf{v}_{0}=\mathcal{C}^{I}(\mathbf{0})$ and
$\mathbf{d}=\mathcal{C}^{F}((\mathbf{0},\tilde{\mathbf{m}}))\in\tilde{\mathcal{C}}\text{\leavevmode\nobreak\
for some\leavevmode\nobreak\
}\tilde{\mathbf{m}}\in\mathbb{F}_{q}^{(\zeta-1)k}$. Then, $\mathbf{d}$ is
converted from $\mathbf{c}_{1}=\mathbf{v}_{0}$ and
$\mathbf{c}_{i+1}=\mathcal{C}^{I}(\tilde{\mathbf{m}}|_{[(i-1)k+1,ik]})$,
$1\leq i\leq\zeta-1$. Note that each symbol of $\mathbf{d}|_{T(U_{1})}$ is
from $\mathbf{v}_{0}|_{U_{1}}$ and symbols in $\mathbf{d}|_{N}$ can be
recovered by symbols in $\mathbf{d}|_{T(U_{1})}$. Thus, $\mathbf{d}|_{N}$ is
fully determined by $\mathbf{v}_{0}|_{U_{1}}$ regardless of
$\tilde{\mathbf{m}}$. This implies that $\tilde{\mathcal{C}}|_{N}$ is a
constant vector determined by $\mathbf{v}_{0}|_{U_{1}}$. Therefore,
$|\tilde{\mathcal{C}}|=|\tilde{\mathcal{C}}|_{N^{C}}|=q^{(\zeta-1)k^{I}}$.

On the other hand, note that each $i\in N^{C}$ has a recovering set $I_{i}$
such that $I_{i}\cap N^{C}\neq\emptyset$. Since $\tilde{\mathcal{C}}|_{N}$ is
a constant vector, we have
$d(\tilde{\mathcal{C}})=d(\tilde{\mathcal{C}}|_{N^{C}})$. Moreover,
$\tilde{\mathcal{C}}|_{N^{C}}$ can be viewed as an
$(n^{F}-|N|,(\zeta-1)k,r)$-LRC by taking $I_{i}\cap N^{C}$ as the recovering
set for every $i\in N^{C}$. Thus, by Theorem I.1, we have

$d(\tilde{\mathcal{C}})=d(\tilde{\mathcal{C}}|_{N^{C}})\leq(n^{F}-|N|)-((\zeta-1)k+\lceil\frac{(\zeta-1)k}{r}\rceil)+2.$
(31)

Then, the result follows directly from $d(\tilde{\mathcal{C}})\geq d$,
$|U_{1}|\leq|N|$ and (31). ∎

Now, we focus on bounding the read access cost $|A_{i}|$, i.e., the number of
symbols that are read from the $i$-th initial codeword during the conversion.

######  Lemma IV.2.

Let $(\mathcal{C}^{I},\mathcal{C}^{F})$ be the convertible code defined in
Lemma IV.1. For each $1\leq i\leq\zeta$, denote $\Delta_{i}=|U_{i}\setminus
A_{i}|-d+1$. Let $B$ be the largest subset of $T(U_{i}\setminus A_{i})$ with
$|B|\leq\lfloor\frac{\Delta_{i}}{r+1}\rfloor$ such that every $b\in B$ has a
recovering set $I_{b}$ satisfying $I_{b}\cap B=\emptyset$. Then, for each
$1\leq i\leq\zeta$, we have

$|A_{i}|\geq\begin{cases}k,\leavevmode\nobreak\ \text{if $\Delta_{i}\leq
0$};\\\ k-\Delta_{i}+|B|,\leavevmode\nobreak\ \text{otherwise}.\end{cases}$
(32)

Moreover, if $d>n^{I}-k+1$, then $\Delta_{i}\leq 0$ for every $1\leq
i\leq\zeta$ and therefore, $|A_{i}|\geq k$.

###### Proof.

Similar to the proof of Lemma IV.1, we only show that (32) holds for $i=1$.

Let $\tilde{\mathcal{C}}$ be the subcode of $\mathcal{C}^{F}$ that encodes
message vectors in $\\{\mathbf{m}\in\mathbb{F}_{q}^{\zeta
k}:\mathbf{m}|_{[k+1,\zeta k]}=\mathbf{0}\\}$, i.e.,

$\tilde{\mathcal{C}}=\\{\mathbf{d}\in\mathcal{C}^{F}:\mathbf{d}=\mathcal{C}^{F}((\tilde{\mathbf{m}},\mathbf{0}))\text{\leavevmode\nobreak\
for some\leavevmode\nobreak\ }\tilde{\mathbf{m}}\in\mathbb{F}_{q}^{k}\\}.$

Denote $d(\tilde{\mathcal{C}})$ as the minimal distance of
$\tilde{\mathcal{C}}$. Clearly, $d(\tilde{\mathcal{C}})\geq d$ and
$|\tilde{\mathcal{C}}|=q^{k}$.

Now, fix a vector $\tilde{\mathbf{m}}\in\mathbb{F}_{q}^{k}$, let
$\mathbf{d}=\mathcal{C}^{F}((\tilde{\mathbf{m}},\mathbf{0}))\in\tilde{\mathcal{C}}$.
Each codeword symbol of $\mathbf{d}$ is either inherited from
$\mathbf{c}_{1}|_{U_{1}},\ldots,\mathbf{c}_{\zeta}|_{U_{\zeta}}$, or is
determined by symbols from
$\mathbf{c}_{1}|_{A_{1}},\ldots,\mathbf{c}_{\zeta}|_{A_{\zeta}}$. Note that
for $2\leq i\leq\zeta$,

$\mathbf{c}_{i}=\mathcal{C}^{I}((\tilde{\mathbf{m}},\mathbf{0})|_{[(i-1)k+1,ik]})=\mathcal{C}^{I}(\mathbf{0})$

is a constant vector. Therefore, the non-constant symbols of $\mathbf{d}$ are
either inherited from $\mathbf{c}_{1}|_{U_{1}\setminus A_{1}}$, or are
functions of symbols in $\mathbf{c}_{1}|_{A_{1}}$.

For any $(n,k)$ code $\mathcal{C}$ with distance $d$, we know that
$|\mathcal{C}|_{S}|=q^{k}$ for any subset $S\subseteq[n]$ of size at least
$n-d+1$. Based on this observation, we will pick a subset $S\subseteq[n^{F}]$
of size at least $n^{F}-d+1$ and prove the lower bound by analyzing the
relationships among codeword symbols in $\mathbf{c}_{1}|_{U_{1}\setminus
A_{1}}$, $\mathbf{c}_{1}|_{A_{1}}$ and $\mathbf{d}|_{S}$.

  * •

Case 1: $\Delta_{1}\leq 0$

Recall that there is a one-to-one map between $U_{1}$ and $T(U_{1})$, thus,
$\Delta_{1}=|T(U_{1}\setminus A_{1})|-d+1\leq 0$. In other words,
$[n^{F}]\setminus T(U_{1}\setminus A_{1})$ has size at least $n^{F}-d+1\geq
n^{F}-d(\tilde{\mathcal{C}})+1$. Take $S=[n^{F}]\setminus T(U_{1}\setminus
A_{1})$, we have $|\tilde{\mathcal{C}}|_{S}|=q^{k}$. Note that symbols in
$\mathbf{c}_{1}|_{U_{1}\setminus A_{1}}$ are remaining as
$\mathbf{d}|_{T(U_{1}\setminus A_{1})}$ in $\mathbf{d}$. Thus, by $S\cap
T(U_{1}\setminus A_{1})=\emptyset$, non-constant symbols in $\mathbf{d}|_{S}$
are functions of symbols in $\mathbf{c}_{1}|_{A_{1}}$. Therefore,
$|\tilde{\mathcal{C}}|_{S}|$ is upper bounded by $q^{|A_{1}|}$, which implies
that $|A_{1}|\geq k$.

  * •

Case 2: $\Delta_{1}>0$

Let $N=\bigcup_{b\in B}I_{b}$. Since $\mathcal{C}^{F}$ has locality $r$, we
have $|B\cup N|\leq|B|(r+1)\leq\Delta_{1}$. Note that

$\displaystyle|T(U_{1}\setminus A_{1})\setminus(B\cup N)|$
$\displaystyle\geq|T(U_{1}\setminus A_{1})|-|B\cup N|$
$\displaystyle\geq|T(U_{1}\setminus A_{1})|-\Delta_{1}=d-1.$

Therefore, we can obtain an $(n^{F}-d+1)$-subset $S\subseteq[n^{F}]$ by
removing any $d-1$ elements in $T(U_{1}\setminus A_{1})\setminus(B\cup N)$
from $[n^{F}]$. Clearly, both $B\cup N$ and $[n^{F}]\setminus T(U_{1}\setminus
A_{1})$ are subsets of $S$. By $n^{F}-d+1\geq n^{F}-d(\tilde{\mathcal{C}})+1$,
we have $|\tilde{\mathcal{C}}|_{S}|=q^{k}$.

Let $S_{1}=S\cap T(U_{1}\setminus A_{1})$. Then,

$|S_{1}|=|T(U_{1}\setminus A_{1})|-d+1=\Delta_{1}.$

Since $B\subseteq T(U_{1}\setminus A_{1})$ and $B\cup N\subseteq S$, we have
$B\subseteq S_{1}$. Moreover, by $N\cap B=\emptyset$, we have $N\subseteq
S\setminus B$. Thus, symbols in $\mathbf{d}|_{B}$ can be recovered by symbols
in $\mathbf{d}|_{S\setminus B}$. On the other hand, note that symbols in
$\mathbf{c}_{1}|_{U_{1}\setminus A_{1}}$ are remaining as
$\mathbf{d}|_{T(U_{1}\setminus A_{1})}$. Thus, by $T(U_{1}\setminus A_{1})\cap
S=S_{1}$, symbols in $\mathbf{d}|_{S}$ that are inherited from
$\mathbf{c}_{1}|_{U_{1}\setminus A_{1}}$ are from
$\mathbf{c}_{1}|_{T^{-1}(S_{1})}$. This implies that non-constant symbols in
$\mathbf{d}|_{S\setminus B}$ is determined by symbols in
$\mathbf{c}_{1}|_{A_{1}}$ and $\mathbf{c}_{1}|_{T^{-1}(S_{1}\setminus B)}$.
Thus, $\mathbf{d}|_{S}$ is determined by $\mathbf{c}_{1}|_{A_{1}}$ and
$\mathbf{c}_{1}|_{T^{-1}(S_{1}\setminus B)}$. Therefore,
$|\tilde{\mathcal{C}}|_{S}|$ is upper bounded by

$q^{|A_{1}\cup T^{-1}(S_{1}\setminus B)|}=q^{|A_{1}|+|S_{1}|-|B|},$

where the equality follows from $T^{-1}(S_{1}\setminus B)\subseteq
U_{1}\setminus A_{1}$ and $(U_{1}\setminus A_{1})\cap A_{1}=\emptyset$. This
leads to $|A_{1}|+|S_{1}|-|B|\geq k$, which further implies that $|A_{1}|\geq
k-\Delta_{1}+|B|$.

  * •

Case 3: $d>n^{I}-k+1$

In this case, we claim that one must have $\Delta_{1}\leq 0$. Otherwise,
assume that $\Delta_{1}>0$ and let $C\subseteq U_{1}\setminus A_{1}$ such that
$|C|=d-1$. Let $S=[n^{F}]\setminus T(C)$. By $|S|=n^{F}-d+1\geq
n^{F}-d(\tilde{\mathcal{C}})+1$, we have $|\tilde{\mathcal{C}}|_{S}|=q^{k}$.
Note that for each $\mathbf{d}\in\tilde{\mathcal{C}}$, the non-constant
symbols of $\mathbf{d}|_{S}$ are either inherited from
$\mathbf{c}_{1}|_{U_{1}\setminus C}$ or determined by
$\mathbf{c}_{1}|_{A_{1}}$. Therefore, we have
$|\tilde{\mathcal{C}}|_{S}|=q^{k}\leq q^{|(U_{1}\setminus C)\cup A_{1}|}$.
Since $C\subseteq U_{1}\setminus A_{1}$, we have $(U_{1}\setminus C)\cup
A_{1}=(U_{1}\cup A_{1})\setminus C$ and $|(U_{1}\cup A_{1})\setminus
C|=|U_{1}\cup A_{1}|-|C|$. This leads to

$|(U_{1}\setminus C)\cup A_{1}|=|U_{1}\cup A_{1}|-|C|\geq k.$

On the other hand, since $U_{1}\cup A_{1}\subseteq[n^{I}]$, we have

$|U_{1}\cup A_{1}|-|C|\leq n^{I}-d+1.$

This implies that $d\leq n^{I}-k+1$, a contradiction. Thus, when
$d>n^{I}-k+1$, we always have $\Delta_{1}\leq 0$ and therefore, $|A_{1}|\geq
k$.

Combining the above cases together, we can conclude the result. ∎

In Lemma IV.2, the size of the special subset $B$ affects the lower bound on
the read access cost $|A_{i}|$. To get an exact lower bound on $|A_{i}|$, in
the following, we show that one can always find such $B$ with
$|B|=\lfloor\frac{\Delta_{i}}{r+1}\rfloor$ when $\mathcal{C}^{F}$ is linear.

Let $\mathcal{C}$ be an $(n,k,r)$-LRC. We call a subset $R_{i}\subseteq[n]$ an
_extended recovering set_ of $i$, if $i\in R_{i}$ and $R_{i}\setminus\\{i\\}$
is a recovering set of $i$.

######  Lemma IV.3.

Assume that $\mathcal{C}^{F}$ is a linear $(n^{F},\zeta k,r)$-LRC. For any
$A\subseteq[n^{F}]$, there is a subset $A^{\prime}\subseteq A$ of size
$\lceil\frac{|A|}{r+1}\rceil$ such that every $i\in A^{\prime}$ has a
recovering set $I_{i}$ satisfying $I_{i}\cap A^{\prime}=\emptyset$.

###### Proof.

Let $\Gamma\subseteq 2^{[n^{F}]}$ be the family of all possible extended
recovering sets of $\mathcal{C}^{F}$. First, we show that there is a sub-
family $\mathcal{R}\subseteq\Gamma$ such that
$\bigcup_{R\in\mathcal{R}}R=[n^{F}]$ and for any $R^{\prime}\in\mathcal{R}$,
$\bigcup_{R\in\mathcal{R}\setminus\\{R^{\prime}\\}}R\neq[n^{F}]$. Clearly,
$\bigcup_{R\in\Gamma}R=[n^{F}]$. Assume that there is an $R_{0}\in\Gamma$ such
that $\bigcup_{R\in\Gamma\setminus\\{R_{0}\\}}R=[n^{F}]$. Then, we can remove
this $R_{0}$ from $\Gamma$ and obtain a new family $\Gamma_{1}$ such that
$\bigcup_{R\in\Gamma_{1}}R=[n^{F}]$. Since $\Gamma$ is finite, by repeating
this procedure, we can obtain a sub-family $\mathcal{R}\subseteq\Gamma$
satisfy the required property at a certain step.

Denote

$\mathcal{S}=\\{R\cap A:R\in\mathcal{R}\\}.$

Clearly, $\bigcup_{S\in\mathcal{S}}S=A$. W.l.o.g., we assume that for every
$S^{\prime}\in\mathcal{S}$,
$\bigcup_{S\in\mathcal{S}\setminus\\{S^{\prime}\\}}S\neq A$. Otherwise, by
apply the elimination procedure above, we can get a sub-family
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ satisfying this property and
$\bigcup_{S\in\mathcal{S}^{\prime}}S=A$.

Under this assumption, each $S\in\mathcal{S}$ contains a unique element
$i_{S}\in A$ which doesn’t belong to
$\bigcup_{S^{\prime}\in\mathcal{S}\setminus\\{S\\}}S^{\prime}$. By the
linearity of $\mathcal{C}$, for every $R\in\mathcal{R}$ and $i\in R$,
$R\setminus\\{i\\}$ is a recovering set of $i$. Therefore, for
$S\in\mathcal{S}$, we can take some $R(S)\in\mathcal{R}$ satisfying $R(S)\cap
A=S$ as the extended recovering set of $i_{S}$. Clearly, for any
$S^{\prime}\in\mathcal{S}\setminus\\{S\\}$, $i_{S^{\prime}}\notin R(S)$. Let
$A^{\prime}=\\{i_{S}:S\in\mathcal{S}\\}$. Then, we have
$|A^{\prime}|=|\mathcal{S}|$ and every $i_{S}\in A^{\prime}$ has a recovering
set $R(S)\setminus\\{i_{S}\\}$ such that $R(S)\cap A^{\prime}=\\{i_{S}\\}$.
Since $|R|\leq r+1$ for each $R\in\mathcal{R}$, $|S|\leq r+1$ for each
$S\in\mathcal{S}$. Therefore,
$|A^{\prime}|=|\mathcal{S}|\geq\lceil\frac{|A|}{r+1}\rceil$. ∎

Now, armed with the results above, we can obtain the following general lower
bound on the access cost of the convertible code
$(\mathcal{C}^{I},\mathcal{C}^{F})$.

######  Theorem IV.4.

Let $(\mathcal{C}^{I},\mathcal{C}^{F})$ be an $(n^{I},k;n^{F},\zeta k)$
convertible code over $\mathbb{F}_{q}$ with conversion procedure $T$. Assume
that $\mathcal{C}^{F}$ is a linear code with locality $r$ and minimum distance
$d$. Then, the write access cost of $T$ is at least

$\zeta\left(d+(\zeta-1)k+\lceil\frac{(\zeta-1)k}{r}\rceil-2\right)-(\zeta-1)n^{F}.$
(33)

Write $\Delta=n^{F}-2d-((\zeta-1)k+\lceil\frac{(\zeta-1)k}{r}\rceil)+3$. Then,
the read access cost of $T$ is at least

$\begin{cases}\zeta k,\text{ if $\Delta\leq 0$};\\\
\zeta(k-\lceil\frac{r\Delta}{r+1}\rceil),\text{ otherwise.}\end{cases}$ (34)

Moreover, when $d>n^{I}-k+1$, the read access cost is at least $\zeta k$.

###### Proof.

Note that the write access cost is the number of new symbols written during
the conversion procedure and there are $n^{F}$ symbols in total. Therefore,
(33) follows directly from Lemma IV.1.

As in Lemma IV.2, for every $i\in[\zeta]$, assume that $|U_{i}\setminus
A_{i}|-d+1=\Delta_{i}$. By Lemma IV.1, we have

$|U_{i}\setminus A_{i}|\leq|U_{i}|\leq
n^{F}-d-((\zeta-1)k+\lceil\frac{(\zeta-1)k}{r}\rceil)+2.$

This leads to,

$\displaystyle|U_{i}\setminus A_{i}|-d+1$ $\displaystyle\leq
n^{F}-2d-((\zeta-1)k+\lceil\frac{(\zeta-1)k}{r}\rceil)+3=\Delta.$

Thus, we have $\Delta_{i}\leq\Delta$ for every $1\leq i\leq\zeta$. On the
other hand, by Lemma IV.3, we have

$\displaystyle\Delta_{i}-|B|$
$\displaystyle=\Delta_{i}-\lfloor\frac{\Delta_{i}}{r+1}\rfloor$
$\displaystyle=\lceil\Delta_{i}\cdot\frac{r}{r+1}\rceil\leq\lceil\frac{r\Delta}{r+1}\rceil.$

Therefore, by Lemma IV.2, we have

$|A_{i}|\geq\begin{cases}k,\leavevmode\nobreak\ \text{if $\Delta\leq 0$};\\\
k-\lceil\frac{r\Delta}{r+1}\rceil,\leavevmode\nobreak\
\text{otherwise}.\end{cases}$

for every $i\in[\zeta]$. This leads to (34).

When $d>n^{I}-k+1$, the results follow directly from Lemma IV.2. ∎

######  Corollary IV.1.

Let $(\mathcal{C}^{I},\mathcal{C}^{F})$ be an $(n^{I},kr,r;n^{F},\zeta kr,r)$
optimal LRCCs over $\mathbb{F}_{q}$ with conversion procedure $T$. Assume that
$(r+1)|n^{I}$ and $(r+1)|n^{F}$. Then, the write access cost of $T$ is at
least $n^{F}-\zeta k(r+1)$ and the read access cost of $T$ is at least

$\begin{cases}\zeta kr,\text{ if $(\zeta+1)k\leq\frac{n^{F}}{r+1}$};\\\
\zeta(\frac{rn^{F}}{r+1}-\zeta kr),\text{ otherwise.}\end{cases}$ (35)

Moreover, when $n^{F}-n^{I}\geq(\zeta-1)kr+\zeta k$, the read access cost is
at least $\zeta kr$.

######  Remark IV.1.

The LRCC obtained in Corollary III.2 attains the lower bound in (35).

###### Proof.

The proof is straight forward. Since $\mathcal{C}^{F}$ is an optimal $r$-LRC,
we have $d=d(\mathcal{C}^{F})=n^{F}-\zeta k(r+1)+2$. Thus, by (33), the write
access cost is at least $n^{F}-\zeta k(r+1)$. Meanwhile, by the formula of
$\Delta$, we have

$\displaystyle\Delta$
$\displaystyle=n^{F}-2d-((\zeta-1)kr+\lceil\frac{(\zeta-1)kr}{r}\rceil)+3$
$\displaystyle=2\zeta k(r+1)-4-n^{F}-(\zeta-1)k(r+1)+3$
$\displaystyle=(\zeta+1)k(r+1)-n^{F}-1.$

Thus, $\lfloor\frac{\Delta}{r+1}\rfloor=(\zeta+1)k-\frac{n^{F}}{r+1}-1$ and
$\Delta-\lfloor\frac{\Delta}{r+1}\rfloor=(\zeta+1)kr-\frac{rn^{F}}{r+1}$. This
leads to

$\displaystyle kr-\lceil\frac{r\Delta}{r+1}\rceil$
$\displaystyle=kr-\left(\Delta-\lfloor\frac{\Delta}{r+1}\rfloor\right)$
$\displaystyle=\frac{rn^{F}}{r+1}-\zeta kr$

and (35) follows directly from (34).

When $n^{F}-n^{I}\geq(\zeta-1)kr+\zeta k$, by $d=n^{F}-\zeta k(r+1)+2$, we
have $d\geq n^{I}-kr+2$. Then, the result follows directly from Theorem IV.4.
∎

Note that $(n,k)$ MDS codes are $(n,k,k)$-optimal LRCs. Thus, by Lemma IV.1
and Lemma IV.2, we can also obtain a proof of Theorem I.2 without assuming the
linearity of $\mathcal{C}^{I}$ and $\mathcal{C}^{F}$.

######  Theorem IV.5.

For all $(n^{I},k;n^{F},\zeta k)$ MDS convertible codes, the read access cost
of conversion is at least $\zeta\cdot\min\\{k,n^{F}-\zeta k\\}$ and the write
access cost is at least $n^{F}-\zeta k$. Furthermore, if $n^{I}-k<n^{F}-\zeta
k$, then, the read access cost is at least $\zeta k$.

###### Proof.

The proof is straight forward. Since $\mathcal{C}^{F}$ has locality $r=\zeta
k$, we have $\lceil\frac{(\zeta-1)k}{r}\rceil=1$ and the minimum distance of
$\mathcal{C}^{F}$ satisfies $d=n^{F}-\zeta k+1$. By substituting these two
parameters into (30), we have $|U_{i}|\leq k$ for every $1\leq i\leq\zeta$.
Thus, the write access cost is at least $n^{F}-\zeta k$. Meanwhile, by the
definition of $\Delta_{i}$ in Lemma IV.2, we have

$\Delta_{i}\leq|U_{i}|-d+1\leq(\zeta+1)k-n^{F}.$

When $n^{F}-\zeta k\geq k$, we have $(\zeta+1)k-n^{F}\leq 0$. Thus,
$\Delta_{i}\leq 0$ and by (32), $|A_{i}|\geq k$. When $n^{F}-\zeta k<k$, we
have $0<(\zeta+1)k-n^{F}\leq k$. Thus, if $\Delta_{i}>0$, the requirement of
$|B|$ in Lemma IV.2 becomes $|B|\leq\lfloor\frac{\Delta_{i}}{r+1}\rfloor=0$.
Then, we can take $B=\emptyset$ in Lemma IV.2 and by (32), we have
$|A_{i}|\geq k-\Delta_{i}\geq n^{F}-\zeta k$. Therefore, the read access cost
is at least $\zeta\cdot\min\\{k,n^{F}-\zeta k\\}$.

Moreover, if $n^{I}-k<n^{F}-\zeta k$, we have $d>n^{I}-k+1$ and the result
also follows directly from Lemma IV.2. ∎

##  V Conclusion and further research

In this paper, we study the code conversion problem of locally repairable
codes in the merge regime. First, by establishing proper maps among
polynomials of different degrees, we provide a general construction of MDS
convertible codes with optimal access costs using GRS codes. As a consequence,
we obtain a family of $(n^{I},k;n^{F},\zeta k)$ MDS convertible codes with
optimal access costs over finite field of size linear in $n^{I}$. Then, based
on the construction of optimal LRCs in [11], we extend the construction of MDS
convertible codes and provide a general construction of LRCCs. Similarly, a
family of $(n^{I},k,r;n^{F},\zeta k,r)$ LRCCs over finite field of size linear
in $n^{I}$ is obtained. Finally, we prove a lower bound on the access cost of
convertible codes with the condition that the final code is an LRC. This
confirms that the LRCCs obtained through our construction admit optimal access
costs.

The study presented in this paper is inspired by interesting open questions
raised in [30] regarding constructions of low-field-size convertibles codes
optimizing the conversion costs. Hence, our primary focus is on constructing
low-field-size convertibles codes. As phrased in [30], convertible codes have
significant potentials for real-world impact by enabling resource-efficient
redundancy tuning. Although many works have been done recently in this topic,
there are still a lot of questions left. In the following, we mention several
open questions that, in our opinion, could improve the study of locally
repairable convertible codes.

  1. 1.

In this paper, we only focus on LRCCs in the merge regime. However, as another
fundamental case, convertible codes in split regime also have strong practical
backgrounds. So, for LRCCs in split regime, what is the lower bound on the
access cost and are there any corresponding optimal constructions? Very
rescently, Maturana and Rashmi [9] presented a construction of convertible
codes with information locality in the split regime, which is a good start for
the study of this question.

  2. 2.

For general LRCCs, the initial code and the final code may have different
localities. However, our construction in Section III requires the initial code
and the final code have the same locality. Note that our lower bound in
Theorem IV.4 is for the general case. Is it possible to generalize our
construction and obtain convertible codes with optimal access costs when the
initial code and the final code have different localities?

  3. 3.

Unlike MDS codes, for optimal locally repairable codes, it is known that the
size of the field can be sub-linear in the code length (e.g., see [24, 25, 27,
28]). Note that long codes over small fields are preferred in practice. It’s
also interesting to ask how small the field size can be to ensure the
existence of LRCCs with optimal access costs.

  4. 4.

As two variations of LRCs, codes with $(r,\delta)$-locality and LRCs with
disjoint recovering sets (availability) are also important storage codes,
which have attracted lots of attentions these years. Therefore, the study of
code conversion problems for these codes are also interesting both
theoretically and practically.

## Acknowledgement

We thank Prof. Itzhak Tamo for his many illuminating discussions and
especially, his helpful suggestions regarding the presentation of this paper.
We also thank Prof. Xin Wang for reading and commenting the earlier version of
the manuscript.

## References

  * [1] C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin, “Erasure coding in windows azure storage,” in _2012 USENIX Annual Technical Conference (USENIX ATC 12)_. Boston, MA: USENIX Association, Jun. 2012, pp. 15–26. [Online]. Available: https://www.usenix.org/conference/atc12/technical-sessions/presentation/huang
  * [2] M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, A. G. Dimakis, R. Vadali, S. Chen, and D. Borthakur, “Xoring elephants: Novel erasure codes for big data,” _Proc. VLDB Endow._ , vol. 6, no. 5, pp. 325–336, mar 2013. [Online]. Available: https://doi.org/10.14778/2535573.2488339
  * [3] A. S. Foundation., “Apache hadoop documentation: HDFS Erasure Coding.” Accessed: Jul. 25, 2023. Available: https://hadoop.apache.org/docs/r3.0.0/hadoop-project-dist/hadoop-hdfs/HDFSErasureCoding.html: [Online].
  * [4] S. Kadekodi, K. V. Rashmi, and G. R. Ganger, “Cluster storage systems gotta have heart: Improving storage efficiency by exploiting disk-reliability heterogeneity,” in _Proceedings of the 17th USENIX Conference on File and Storage Technologies_ , ser. FAST’19. USA: USENIX Association, 2019, pp. 345–358.
  * [5] F. Maturana and K. V. Rashmi, “Convertible codes: Enabling efficient conversion of coded data in distributed storage,” _IEEE Transactions on Information Theory_ , vol. 68, no. 7, pp. 4392–4407, 2022.
  * [6] S. Kadekodi, F. Maturana, S. J. Subramanya, J. Yang, K. V. Rashmi, and G. R. Ganger, “Pacemaker: Avoiding heart attacks in storage clusters with disk-adaptive redundancy,” ser. OSDI’20. USA: USENIX Association, 2020.
  * [7] F. Maturana, V. S. C. Mukka, and K. V. Rashmi, “Access-optimal linear mds convertible codes for all parameters,” in _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 577–582.
  * [8] F. Maturana and K. V. Rashmi, “Bandwidth cost of code conversions in distributed storage: Fundamental limits and optimal constructions,” _IEEE Trans. Inf. Theory_ , vol. 69, no. 8, pp. 4993–5008, 2023. [Online]. Available: https://doi.org/10.1109/TIT.2023.3265512
  * [9] ——, “Locally reapirable convertible codes,” in _IEEE International Symposium on Information Theory, ISIT 2023, Taipei, Taiwan, China, June 25 \- June 30, 2023_ , p. to appear.
  * [10] C. Huang, M. Chen, and J. Li, “Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems,” in _Sixth IEEE International Symposium on Network Computing and Applications (NCA 2007)_ , 2007, pp. 79–86.
  * [11] I. Tamo and A. Barg, “A family of optimal locally recoverable codes,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 8, pp. 4661–4676, 2014. [Online]. Available: https://doi.org/10.1109/TIT.2014.2321280
  * [12] A. Barg, I. Tamo, and S. Vlădaţ, “Locally recoverable codes on algebraic curves,” _IEEE Trans. Inform. Theory_ , vol. 63, no. 8, pp. 4928–4939, 2017. [Online]. Available: https://doi.org/10.1109/TIT.2017.2700859
  * [13] X. Li, L. Ma, and C. Xing, “Optimal locally repairable codes via elliptic curves,” _IEEE Transactions on Information Theory_ , vol. 65, no. 1, pp. 108–117, 2019.
  * [14] L. Jin, L. Ma, and C. Xing, “Construction of optimal locally repairable codes via automorphism groups of rational function fields,” _IEEE Transactions on Information Theory_ , vol. 66, no. 1, pp. 210–221, 2020.
  * [15] H. Cai, C. Fan, Y. Miao, M. Schwartz, and X. Tang, “Optimal locally repairable codes: An improved bound and constructions,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 8, pp. 5060–5074, 2022. [Online]. Available: https://doi.org/10.1109/TIT.2022.3161613
  * [16] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the locality of codeword symbols,” _IEEE Transactions on Information Theory_ , vol. 58, no. 11, pp. 6925–6934, 2012.
  * [17] I. Tamo, A. Barg, and A. Frolov, “Bounds on the parameters of locally recoverable codes,” _IEEE Transactions on Information Theory_ , vol. 62, no. 6, pp. 3070–3083, 2016.
  * [18] A. Agarwal, A. Barg, S. Hu, A. Mazumdar, and I. Tamo, “Combinatorial alphabet-dependent bounds for locally recoverable codes,” _IEEE Transactions on Information Theory_ , vol. 64, no. 5, pp. 3481–3492, 2018.
  * [19] J. Ma and G. Ge, “Optimal binary linear locally repairable codes with disjoint repair groups,” _SIAM J. Discret. Math._ , vol. 33, no. 4, pp. 2509–2529, 2019. [Online]. Available: https://doi.org/10.1137/19M1248443
  * [20] A. Wang, Z. Zhang, and D. Lin, “Bounds for binary linear locally repairable codes via a sphere-packing approach,” _IEEE Transactions on Information Theory_ , vol. 65, no. 7, pp. 4167–4179, 2019.
  * [21] R. M. Roth, “Asymptotic bounds on the rate of locally repairable codes,” _IEEE Transactions on Information Theory_ , vol. 68, no. 3, pp. 1581–1598, 2022.
  * [22] N. Prakash, G. M. Kamath, V. Lalitha, and P. V. Kumar, “Optimal linear codes with a local-error-correction property,” in _2012 IEEE International Symposium on Information Theory Proceedings_ , 2012, pp. 2776–2780.
  * [23] A. Wang and Z. Zhang, “Repair locality with multiple erasure tolerance,” _IEEE Transactions on Information Theory_ , vol. 60, no. 11, pp. 6979–6987, 2014.
  * [24] V. Guruswami, C. Xing, and C. Yuan, “How long can optimal locally repairable codes be?” _IEEE Transactions on Information Theory_ , vol. 65, no. 6, pp. 3662–3670, 2019.
  * [25] H. Cai, Y. Miao, M. Schwartz, and X. Tang, “On optimal locally repairable codes with super-linear length,” _IEEE Transactions on Information Theory_ , vol. 66, no. 8, pp. 4853–4868, 2020.
  * [26] ——, “On optimal locally repairable codes with multiple disjoint repair sets,” _IEEE Transactions on Information Theory_ , vol. 66, no. 4, pp. 2402–2416, 2020.
  * [27] X. Kong, X. Wang, and G. Ge, “New constructions of optimal locally repairable codes with super-linear length,” _IEEE Transactions on Information Theory_ , vol. 67, no. 10, pp. 6491–6506, 2021.
  * [28] C. Xing and C. Yuan, “Construction of optimal (r, Î´)-locally recoverable codes and connection with graph theory,” _IEEE Transactions on Information Theory_ , vol. 68, no. 7, pp. 4320–4328, 2022.
  * [29] D. S. Papailiopoulos and A. G. Dimakis, “Locally repairable codes,” _IEEE Transactions on Information Theory_ , vol. 60, no. 10, pp. 5843–5855, 2014.
  * [30] F. Maturana and K. V. Rashmi, “Bandwidth cost of code conversions in the split regime,” _CoRR_ , vol. abs/2205.06793, 2022. [Online]. Available: https://arxiv.org/abs/2205.06793

##  Appendix A Properties of $\\{x^{s}g^{t}(x)\\}_{0\leq s\leq r-1\atop 0\leq
t\leq k-1}$

Let $k$ and $r$ be positive integers. For $1\leq i\leq k$, let
$A_{i}=\\{a_{i,1},\ldots,a_{i,r+1}\\}\subset\mathbb{F}_{q}$ such that
$A_{i}\cap A_{i}^{\prime}=\emptyset$ for $i\neq i^{\prime}$. Denote
$A=\bigcup_{i=1}^{k}A_{i}$ and $\tilde{A}_{i}=A_{i}\setminus\\{a_{i,r+1}\\}$.
Let $g(x)\in\mathbb{F}_{q}[x]$ be a polynomial of degree $r+1$ such that $g$
is constant on each $A_{i}$. Denote $g_{i}$ as the constant $g(A_{i})$ and
denote $G=\\{g_{1},\ldots,g_{k}\\}$. For every $(i,j)\in[k]\times[r+1]$,
define $\mathbf{a}_{i,j}\in\mathbb{F}_{q}^{kr}$ as

$\mathbf{a}_{i,j}=(a_{i,j}^{s}g^{t}(a_{i,j}),\leavevmode\nobreak\
(s,t)\in[0,r-1]\times[0,k-1])^{T}.$

######  Lemma A.1.

  * 1)

$\\{\mathbf{a}_{i,j}\\}_{1\leq i\leq k\atop 1\leq j\leq r}$ are linearly
independent over $\mathbb{F}_{q}^{kr}$.

  * 2)

For $c\in\mathbb{F}_{q}$, denote $\mathbf{c}\in\mathbb{F}_{q}^{kr}$ as the
vector $\mathbf{c}=(c^{s}g^{t}(c),\leavevmode\nobreak\
(s,t)\in[0,r-1]\times[0,k-1])^{T}.$ Then, we have

$\mathbf{c}=\sum_{(i,j)\in[k]\times[r]}\frac{h_{G\setminus\\{g_{i}\\}}(g(c))}{h_{G\setminus\\{g_{i}\\}}(g_{i})}\frac{h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(c)}{h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(a_{i,j})}\mathbf{a}_{i,j}.$
(36)

  * 3)

For every $1\leq i\leq k$, denote $\tilde{\mathbf{A}}_{i}$ as the $r\times r$
Vandermonde matrix generated by $\tilde{A}_{i}$. Then, we have

$\left(\begin{array}[]{cccc}\tilde{\mathbf{A}}_{1}&\tilde{\mathbf{A}}_{2}&\cdots&\tilde{\mathbf{A}}_{k}\\\
g_{1}\tilde{\mathbf{A}}_{1}&g_{2}\tilde{\mathbf{A}}_{2}&\cdots&g_{k}\tilde{\mathbf{A}}_{k}\\\
\vdots&\vdots&&\vdots\\\
g_{1}^{k-2}\tilde{\mathbf{A}}_{1}&g_{2}^{k-2}\tilde{\mathbf{A}}_{2}&\cdots&g_{k}^{k-2}\tilde{\mathbf{A}}_{k}\end{array}\right)\cdot\left(\begin{array}[]{c}\frac{\tilde{\mathbf{A}}_{1}^{-1}}{h_{G\setminus\\{g_{1}\\}}(g_{1})}\\\
\frac{\tilde{\mathbf{A}}_{2}^{-1}}{h_{G\setminus\\{g_{2}\\}}(g_{2})}\\\
\vdots\\\
\frac{\tilde{\mathbf{A}}_{k}^{-1}}{h_{G\setminus\\{g_{k}\\}}(g_{k})}\end{array}\right)=\mathbf{0}_{kr\times
r}.$ (37)

###### Proof.

There is a one-to-one correspondence between a polynomial $f$ in
$\text{Span}_{\mathbb{F}_{q}}\\{x^{s}g^{t}(x)\\}_{0\leq s\leq r-1\atop 0\leq
t\leq k-1}$ and its coefficient vector $\mathbf{v}_{f}\in\mathbb{F}_{q}^{kr}$
w.r.t. basis $\\{x^{s}g^{t}(x)\\}_{0\leq s\leq r-1\atop 0\leq t\leq k-1}$.
Clearly, for every $c\in\mathbb{F}_{q}$, $f(c)=\mathbf{v}_{f}\cdot\mathbf{c}$.
Next, we proceed to prove the three results separately.

  * 1.

Let $\mathbf{A}$ be the $kr\times kr$ matrix with $\mathbf{a}_{i,j}$ as its
$((i-1)r+j)$-th column. Next, we prove the first result by showing that
$rank(\mathbf{A})=kr$.

Assume that there is a vector $\mathbf{v}_{f}\in\mathbb{F}_{q}^{kr}$ such that
$\mathbf{v}_{f}\cdot\mathbf{A}=\mathbf{0}$. Thus, $f(a_{i,j})=0$ for every
$(i,j)\in[k]\times[r]$. For each $1\leq i\leq k$, denote

$f_{i}(x)=\sum_{j=1}^{r}\left(\sum_{s=1}^{k}f_{s,j}g_{i}^{s-1}\right)x^{j-1}.$

Then, we have $f_{i}(a_{i,j})=0$ for every $(i,j)\in[k]\times[r]$. Note that
$f_{i}(x)$ is a polynomial of degree at most $r-1$. Thus, by
$f_{i}(a_{i,j})=0$ for every $1\leq j\leq r$, $f_{i}$ is the zero polynomial.
This implies that $\sum_{s=1}^{k}f_{s,j}g_{i}^{s-1}=0$ for every
$(i,j)\in[k]\times[r]$. Denote
$\tilde{f}_{j}(x)=\sum_{s=1}^{k}f_{s,j}x^{s-1}$. Since $g_{i}$’s are pairwise
distinct and $\deg(\tilde{f}_{j})\leq k-1$, we can obtain $f_{s,j}=0$ for
every $(s,j)\in[k]\times[r]$. Therefore, we can conclude that
$\mathbf{v}_{f}=\mathbf{0}$ and $rank(\mathbf{A})=kr$.

  * 2.

Since $\\{\mathbf{a}_{i,j}\\}_{1\leq i\leq k\atop 1\leq j\leq r}$ are linearly
independent over $\mathbb{F}_{q}$, $\mathbf{c}$ can be uniquely expressed as a
linear combination of $\\{\mathbf{a}_{i,j}\\}_{1\leq i\leq k\atop 1\leq j\leq
r}$. Assume that
$\mathbf{c}=\sum_{(i,j)\in[k]\times[r]}\eta_{i,j}\mathbf{a}_{i,j}$. Next, we
show that

$\eta_{i,j}=\frac{h_{G\setminus\\{g_{i}\\}}(g(c))}{h_{G\setminus\\{g_{i}\\}}(g_{i})}\frac{h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(c)}{h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(a_{i,j})}.$
(38)

For any $f\in\text{Span}_{\mathbb{F}_{q}}\\{x^{s}g^{t}(x)\\}_{0\leq s\leq
r-1\atop 0\leq t\leq k-1}$, $f(c)=\mathbf{v}_{f}\cdot\mathbf{c}^{T}$. Thus,
$f(c)=\sum_{(i,j)\in[k]\times[r]}\eta_{i,j}f({a}_{i,j})$. For
$(i,j)\in[k]\times[r]$, define

$f_{i,j}(x)=h_{G\setminus\\{g_{i}\\}}(g(x))h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(x).$

Then,
$f_{i,j}(c)=h_{G\setminus\\{g_{i}\\}}(g(c))h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(c)$
and for $(s,t)\in[k]\times[r]$,

$f_{i,j}(a_{s,t})=\left\\{\begin{array}[]{cc}h_{G\setminus\\{g_{i}\\}}(g_{i})h_{\tilde{A}_{i}\setminus\\{a_{i,j}\\}}(a_{i,j})&\text{if}\leavevmode\nobreak\
(s,t)=(i,j);\\\ 0&\text{otherwise}.\end{array}\right.$

Thus, (38) follows directly from
$f_{i,j}(c)=\sum_{(s,t)\in[k]\times[r]}\eta_{s,t}f_{i,j}({a}_{s,t})$.

  * 3.

To start with, we consider the toy case when $r=1$. When $r=1$, we have
$\tilde{\mathbf{A}}_{i}=(1)$ and

$\left(\begin{array}[]{ccc}\tilde{\mathbf{A}}_{1}&\cdots&\tilde{\mathbf{A}}_{k}\\\
g_{1}\tilde{\mathbf{A}}_{1}&\cdots&g_{k}\tilde{\mathbf{A}}_{k}\\\
\vdots&&\vdots\\\
g_{1}^{k-2}\tilde{\mathbf{A}}_{1}&\cdots&g_{k}^{k-2}\tilde{\mathbf{A}}_{k}\end{array}\right)=\left(\begin{array}[]{ccc}1&\cdots&1\\\
g_{1}&\cdots&g_{k}\\\ \vdots&&\vdots\\\
g_{1}^{k-2}&\cdots&g_{k}^{k-2}\end{array}\right).$

Note that the RHS of the above equality is the $(k-1)\times k$ Vandermonde
matrix generated by $G$. Therefore, by Cramer’s rule, we have

$\left(\begin{array}[]{ccc}1&\cdots&1\\\ g_{1}&\cdots&g_{k}\\\
\vdots&&\vdots\\\
g_{1}^{k-2}&\cdots&g_{k}^{k-2}\end{array}\right)\cdot\left(\begin{array}[]{c}\frac{1}{h_{G\setminus\\{g_{1}\\}}(g_{1})}\\\
\vdots\\\
\frac{1}{h_{G\setminus\\{g_{k}\\}}(g_{k})}\end{array}\right)=\mathbf{0}.$

This confirms (37) when $r=1$.

For $r\geq 1$, the LHS of (37) equals to

$\left(\begin{array}[]{cccc}\mathbf{I}&\mathbf{I}&\cdots&\mathbf{I}\\\
g_{1}\mathbf{I}&g_{2}\mathbf{I}&\cdots&g_{k}\mathbf{I}\\\
\vdots&\vdots&&\vdots\\\
g_{1}^{k-2}\mathbf{I}&g_{2}^{k-2}\mathbf{I}&\cdots&g_{k}^{k-2}\mathbf{I}\end{array}\right)\cdot\left(\begin{array}[]{c}\frac{\mathbf{I}}{h_{G\setminus\\{g_{1}\\}}(g_{1})}\\\
\frac{\mathbf{I}}{h_{G\setminus\\{g_{2}\\}}(g_{2})}\\\ \vdots\\\
\frac{\mathbf{I}}{h_{G\setminus\\{g_{k}\\}}(g_{k})}\end{array}\right).$

Then, (37) follows from the case when $r=1$.

∎