# Three classes of new optimal cyclic $(r,\delta)$ locally recoverable codes

Yaozong Zhang, Dabin Zheng and Xiaoqiang Wang<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Hubei Key Laboratory of Applied
Mathematics, Faculty of Mathematics and Statistics, Hubei University,
Wuhan, 430062, China

###### Abstract

An $(r,\delta)$-locally repairable code ($(r,\delta)$-LRC for short) was
introduced by Prakash et al. for tolerating multiple failed nodes in
distributed storage systems, and has garnered significant interest among
researchers. An $(r,\delta)$-LRC is called an optimal code if its parameters
achieve the Singleton-like bound. In this paper, we construct three classes of
$q$-ary optimal cyclic $(r,\delta)$-LRCs with new parameters by investigating
the defining sets of cyclic codes. Our results generalize the related work of
[4, 27], and the obtained optimal cyclic $(r,\delta)$-LRCs have flexible
parameters. A lot of numerical examples of optimal cyclic $(r,\delta)$-LRCs
are given to show that our constructions are capable of generating new optimal
cyclic $(r,\delta)$-LRCs.

###### keywords:

Cyclotomic cosets; Cyclic codes; $(r,\delta)$-LRCs; Optimal LRCs

††journal: Finite Fields and Their Applicationslabel1label1footnotetext: The
corresponding author is Dabin Zheng. The research was supported in part by
NSFC under Grant Numbers 62272148, 11971156, 12001175.

##  1 Introduction

A locally repairable code (LRC) is nothing but a block code with an additional
parameter called locality. LRCs were introduced by Gopalan et al. [8] for
applications to distributed storage systems. Such repair-efficient codes have
been used in the Hadoop Distributed File System RAID by Facebook and Windows
Azure Storage. Let ${\mathcal{C}}$ be an $[n,k,d]$ linear code over
${\mathbb{F}}_{q}$. The $i$-th code symbol of ${\mathcal{C}}$ is said to have
$r$-locality $(1\leq r\leq k)$ if it can be recovered by accessing at most $r$
other code symbols in ${\mathcal{C}}$, i.e., the $i$-th code symbol can be
expressed as a function of $r$ other code symbols. If all the code symbols of
${\mathcal{C}}$ have locality $r$, then ${\mathcal{C}}$ is called an $r$
locally repairable code ($r$-LRC for short). It was proved in [8, 30] that the
minimum distance of an $r$-LRC ${\mathcal{C}}$ is upper bounded by

$d({\mathcal{C}})\leq n-k-\left\lceil\frac{k}{r}\right\rceil+2.$ (1)

This bound is called the Singleton-like bound for LRCs. The linear codes
meeting the above bound (1) are called optimal $r$-LRCs. Abundant optimal
$r$-LRCs with flexible parameters have been constructed in [5, 7, 9, 10, 12,
13, 14, 16, 18, 19, 20, 23, 24, 30, 33], and the relevant references therein.

In order to deal with the situation that multiple node failures occur in a
distributed storage system, Prakash et al. [26] introduced the concept of
$(r,\delta)$-locality of linear codes, where $\delta\geq 2$, which generalized
the notion of $r$-locality. The $i$-th code symbol of ${\mathcal{C}}$ is said
to have $(r,\delta)$-locality ($\delta\geq 2$) if there exists a subset
$S_{i}\subset\\{1,2,\ldots,n\\}$ such that $i\in S_{i}$, $|S_{i}|\leq
r+\delta-1$ and the punctured code ${\mathcal{C}}|_{S_{i}}$ has the minimum
distance $d({\mathcal{C}}|_{S_{i}})\geq\delta$. The code ${\mathcal{C}}$ is
said to have $(r,\delta)$-locality or be an $(r,\delta)$-LRC if all the code
symbols have $(r,\delta)$-localities. The Singleton-like bound for the minimum
distance of an $(r,\delta)$-LRC is given as follows [26]:

$d({\mathcal{C}})\leq
n-k-\left(\left\lceil\frac{k}{r}\right\rceil-1\right)(\delta-1)+1.$ (2)

Linear codes meeting the bound (2) are called optimal $(r,\delta)$-LRCs. Note
that the notion of $r$-locality is a special case of the notion of
$(r,\delta)$-locality for $\delta=2$.

Table 1: The known optimal cyclic $(r,\delta)$-LRCs with length $\lambda(q+1)$ or $\lambda(q-1)$. $[n,k,d]_{q}$ | $r+\delta-1$ | Constraints | Refs.
---|---|---|---
$[2(q+1),2(q+2-4\delta)+4,\delta+2]_{q}$ | $\frac{q+1}{4}$ |  $q\equiv 7({\rm mod}~{}8),2\leq\delta\leq\frac{q-7}{4}$ is even. | [21]
$[2(q+1),2(q+2-2\delta)-2,\delta+2]_{q}$ | $\frac{q+1}{2}$ |  $q\equiv 3({\rm mod}~{}4),2\leq\delta\leq\frac{q-3}{2}$ is even. | [27]
$[2(q+1),2(q+2-\delta)-2,\delta+2]_{q}$ | $q+1$ |  $q\equiv 1({\rm mod}~{}4),2\leq\delta\leq q-1$ is even. | [27]
$[3(q+1),3(q+2-\delta)-2,\delta+2]_{q}$ | $q+1$ |  $q\equiv 1({\rm mod}~{}6),2\leq\delta\leq q-1$ is even. | [4]
$[3(q-1),3(q-\delta)-1,\delta+1]_{q}$ | $q-1$ |  $q\equiv 7({\rm mod}~{}9),2\leq\delta\leq\frac{2(q-1)}{3}$ is even, $6\nmid\delta$. | [4]
$[\lambda(q+1),\lambda(q+2-\delta)-2,\delta+2]_{q}$ | $q+1$ |  |  $q\equiv 1({\rm mod}~{}2\lambda)$, $\lambda\geq 2$,
---
$\delta=2(b+1),0\leq b\leq\frac{q-3}{2}$,
${\rm gcd}((q+1)(\lambda-(b)_{\lambda}-1)+1,n)=1$.
Th.3.3
$[\lambda(q+1),\lambda(q+3-2\delta)-2,\delta+2]_{q}$ | $\frac{q+1}{2}$ |  |  $q\equiv 1({\rm mod}~{}2\lambda),q\equiv 3({\rm mod}~{}4)$, $\lambda\geq 3$,
---
$\delta=2(b+1)-\frac{q+1}{2},\frac{q+1}{4}\leq b\leq\frac{q-3}{2}$,
$\gcd((q+1)(\lambda-(b)_{\lambda}-\frac{1}{2})+1,n)=1$.
Th.3.8
$[\lambda(q-1),\lambda(q-\delta)-2,\delta+2]_{q}$ | $q-1$ |  |  $q\equiv-1({\rm mod}~{}2\lambda)$, $\lambda\geq 2,\delta=2(c+1),0\leq c\leq\lambda-1$,
---
${\rm gcd}((q-1)(\lambda-c-1)+1,n)=1$ for $0\leq c\leq\lambda-2,$
or $\gcd((q-1)(\lambda-2)+1,n)=1$ for $c=\lambda-1$.
Th.4.3

Recently, the constructions of optimal cyclic $(r,\delta)$-LRCs have received
widespread attention from coding scholars because cyclic codes have a rich
algebraic structure that makes them efficient to encode and decode. Chen et
al. [2, 3] generalized the constructions of optimal cyclic $r$-LRCs proposed
by Tamo et al. [31, 32] and constructed several classes of optimal
$(r,\delta)$-LRCs of length $n$ for $n\,|\,(q-1)$ or $n\,|\,(q+1)$,
respectively in terms of a union of the set of zeros controlling the minimum
distance and the set of zeros ensuring the locality. Following the work of [2,
3], Qiu et al. [28] characterized $(r,\delta)$-locality of a cyclic code by
decomposing its zero set into the product of two subsets, and constructed
several classes of optimal cyclic $(r,\delta)$-LRCs of length $n$ for
$n|(q-1)$ or $n|(q+1)$, and many of them satisfied $(r+\delta-1)\,\nmid\,n$.
For a fixed alphabet size $q$, many authors focused on constructions of
$q$-ary optimal $(r,\delta)$-LRCs with unbounded length, and a large number of
$q$-ary optimal $(r,\delta)$-LRCs with code lengths independent of $q$ have
been obtained, for example see [1, 6, 17, 22, 29, 34, 35], and reference
therein. On the other hand, some optimal cyclic $(r,\delta)$-LRCs of length
$\mathcal{O}(q)$ with flexible parameters have been obtained. Qian and Zhang
[27] constructed two classes of optimal cyclic $(r,\delta)$-LRCs of length
$n=2(q+1)$, where $r+\delta-1=q+1$ or $r+\delta-1=\frac{q+1}{2}$. Following
this work, Liu et al. [21] constructed a class of optimal cyclic
$(r,\delta)$-LRCs of length $n=2(q+1)$, where $r+\delta-1=\frac{q+1}{4}$, and
Chen and Kai [4] constructed two classes of optimal cyclic $(r,\delta)$-LRCs
of length $n=3(q+1)$ satisfying $r+\delta-1=q+1$, and $n=3(q-1)$ satisfying
$r+\delta-1=q-1$, respectively.

Following the work of [4, 21, 27], this paper constructs more optimal cyclic
$(r,\delta)$-LRCs with new parameters by investigating the zeros of cyclic
codes. First, two classes of new optimal cyclic $(r,\delta)$-LRCs of length
$n=\lambda(q+1)$ with $r+\delta-1=q+1$ or $r+\delta-1=\frac{q+1}{2}$ are
constructed, where $q$ is an odd prime power with $q\equiv 1~{}({\rm
mod}~{}2\lambda)$ and $\lambda\,(\geq 2)$ is a positive integer (see Theorems
3.3 and 3.8). Then, we construct a class of new optimal cyclic
$(r,\delta)$-LRCs of length $n=\lambda(q-1)$ with $r+\delta-1=q-1$, where $q$
is an odd prime power with $q\equiv-1~{}({\rm mod}~{}2\lambda)$ and
$\lambda\,(\geq 2)$ is a positive integer (see Theorem 4.3). Our theorems
generalize the results in [27] and [4], and our method seems more convenient
for obtaining optimal cyclic $(r,\delta)$-LRCs with flexible parameters.
Comparisons between our optimal $(r,\delta)$-LRCs and previous constructions
are shown in Table 1. Finally, a lot of numerical examples of optimal cyclic
$(r,\delta)$-LRCs are given to show that our constructions are capable of
generating new optimal cyclic $(r,\delta)$-LRCs.

The rest of this paper is organized as follows. In Section 2, we introduce
some basic concepts and results on cyclic codes over the finite field
$\mathbb{F}_{q}$, and provide some lemmas for constructing optimal cyclic
$(r,\delta)$-LRCs. In Section 3, we construct two classes of optimal cyclic
$(r,\delta)$-LRCs of length $n=\lambda(q+1)$ with $r+\delta-1=q+1$ or
$r+\delta-1=\frac{q+1}{2}$, respectively. In Section 4, a class of optimal
cyclic $(r,\delta)$-LRCs of length $n=\lambda(q-1)$ with $r+\delta-1=q-1$ are
obtained. Section 5 concludes this paper.

##  2 Preliminaries

In this section, we introduce cyclic codes and some preliminaries, which will
be used later in this paper. Starting from now on, we adopt the following
notation unless we specify them separately.

  * •

$q$ is an odd prime power and $\mathbb{F}_{q}$ is a finite field with $q$
elements.

  * •

$n$ is a positive integer satisfying ${\rm gcd}(n,q)=1$.

  * •

$|S|$ denotes the size of $S$, where $S$ is a finite set.

  * •

$\lceil x\rceil$ denotes the smallest integer greater than or equal to $x$,
where $x$ is a real number.

  * •

$(a)_{n}$ denotes the remainder of $a$ modulo $n$, where $a$ and $n(\geq 2)$
are two integers and $0\leq(a)_{n}\leq n-1$.

  * •

$d({\mathcal{C}})$ denotes the minimum distance of a linear code
${\mathcal{C}}$.

  * •

$(r,\delta)$-$[n,k,d]_{q}$ denotes the parameters of an $(r,\delta)$-LRC over
${\mathbb{F}}_{q}$ with parameters $[n,k,d]$.

An $[n,k,d]$ linear code over $\mathbb{F}_{q}$ is a subspace of
$\mathbb{F}_{q}^{n}$ with dimension $k$ and minimum Hamming distance $d$, and
denote it by $[n,k,d]_{q}$ for short. An $[n,k,d]_{q}$ linear code
${\mathcal{C}}$ is called cyclic if
$\mathbf{c}=(c_{1},c_{2},\ldots,c_{n})\in{\mathcal{C}}$ implies
$(c_{n},c_{0},\ldots,c_{n-1})\in{\mathcal{C}}$. It is known that any cyclic
code ${\mathcal{C}}$ of length $n$ over $\mathbb{F}_{q}$ corresponds to an
ideal of the quotient ring $\mathbb{F}_{q}[x]/\langle x^{n}-1\rangle$. Since
every ideal of $\mathbb{F}_{q}[x]/\langle x^{n}-1\rangle$ is principal,
${\mathcal{C}}$ can be expressed as ${\mathcal{C}}=\langle g(x)\rangle$, where
$g(x)$ is a monic polynomial with the smallest degree and is called the
generator polynomial of ${\mathcal{C}}$ [25]. It is clear that the dimension
of ${\mathcal{C}}$ equals $n-\deg(g(x))$. Since $n$ and $q$ are co-prime,
$g(x)$ is uniquely determined by the set of its roots. The zeros of $g(x)$ are
also called the zeros of ${\mathcal{C}}$, and the set ${\mathcal{D}}=\\{0\leq
i\leq n-1|g(\alpha^{i})=0\\}$ is called the defining set of ${\mathcal{C}}$,
where $\alpha$ is a primitive $n$-th root of unity in some extension of
${\mathbb{F}}_{q}$.

The operation of multiplying by $q$ divides the integers modulo $n$ into sets
called $q$-cyclotomic cosets modulo $n$. For an integer $s$ with $0\leq s\leq
n-1$, the $q$-cyclotomic coset of $s$ modulo $n$ is defined by

$C_{s,n}=\left\\{s,\,\,sq,\,\,sq^{2},\,\,\ldots,\,\,sq^{\ell_{s}-1}\right\\},$

where $\ell_{s}$ is the smallest positive integer such that
$sq^{\ell_{s}}\equiv s\,\,\,({\rm mod}\,\,n)$. Let
${\mathcal{C}}_{{\mathcal{D}}}$ be a cyclic code over ${\mathbb{F}}_{q}$ of
length $n$ with the defining set ${\mathcal{D}}\subset\\{0,1,\ldots,n-1\\}$.
Then, ${\mathcal{D}}$ is a union of some $q$-cyclotomic cosets modulo $n$
since the generator polynomial $\prod_{i\in{\mathcal{D}}}(x-\alpha^{i})$ of
${\mathcal{C}}_{{\mathcal{D}}}$ is a monic divisor of $x^{n}-1$ over
${\mathbb{F}}_{q}$. Moreover, ${\rm
dim}_{\mathbb{F}_{q}}({\mathcal{C}})=n-|{\mathcal{D}}|$.

The following propositions characterize lower bounds of the minimal distance
of cyclic codes by using their defining sets, which can be found in [11, 25].

######  Proposition 2.1.

[25, BCH bound] Let $d$ be an integer with $2\leq d\leq n$, and
${\mathcal{C}}$ be a cyclic code of length $n$ over $\mathbb{F}_{q}$ with
defining set ${\mathcal{D}}$. If ${\mathcal{D}}$ contains $d-1$ consecutive
integers, then the minimal distance of ${\mathcal{C}}$ is at least $d$.

######  Proposition 2.2.

[11, Hartmann-Tzeng bound] Let ${\mathcal{C}}$ be a cyclic code of length $n$
over $\mathbb{F}_{q}$ with defining set ${\mathcal{D}}$. Let $a$, $b$, $c$,
$d$ and $d^{\prime}$ be integers. If $\\{a+i_{1}b+i_{2}c\,|\,0\leq i_{1}\leq
d-2,\,0\leq i_{2}\leq d^{\prime}\\}\subseteq{\mathcal{D}}$ and
$\gcd(n,b)=\gcd(n,c)=1$, then the minimal distance of ${\mathcal{C}}$ is at
least $d+d^{\prime}$.

The following lemma characterizes the $(r,\delta)$-locality of cyclic codes by
their defining sets, which will be used in the following sections.

######  Lemma 2.3.

[15] Let $m,n$ and $t$ be positive integers satisfying $m\,|\,n$ and ${\rm
gcd}(m,t)=1$. Let $X=\\{i_{1},i_{2},\ldots,i_{\delta-1}\\}$, where $0\leq
i_{1}\leq i_{2}\leq\ldots\leq i_{\delta-1}\leq m-1,i_{\ell}=i_{1}+t(\ell-1)$
and $1\leq\ell\leq\delta-1$. Let ${\mathcal{C}}$ be a cyclic code of length
$n$ with defining set ${\mathcal{D}}$. If

$\cup_{j\in X}\\{j,j+m,j+2m,\ldots,j+n-m\\}\subseteq{\mathcal{D}},$

then ${\mathcal{C}}$ has $(r,\delta)$-locality for all code symbols, where
$r=m-\delta+1$.

##  3 Optimal cyclic $(r,\delta)$-LRCs of length $\lambda(q+1)$

In this section, we construct two classes of optimal cyclic $(r,\delta)$-LRCs
of length $\lambda(q+1)$.

###  3.1 Optimal cyclic $(r,\delta)$-LRCs with $r+\delta-1=q+1$

In this subsection, we assume that $q$ is an odd prime power and $\lambda(\geq
2)$ is a positive integer satisfying $q\equiv 1~{}({\rm mod}~{}2\lambda)$. To
construct optimal cyclic $(r,\delta)$-LRCs of length $\lambda(q+1)$ with
$r+\delta-1=q+1$, we first give some lemmas on $q$-cyclotomic cosets modulo
$n$.

######  Lemma 3.1.

Let $q$ be an odd prime power and $\lambda(\geq 2)$ be a positive integer
satisfying $q\equiv 1~{}({\rm mod}~{}2\lambda)$. Let $n=\lambda(q+1)$,
$h=\frac{q-1}{2\lambda}$ and $a=\frac{q+1}{2}$. Then,

  1. (1)

$C_{ai,n}=\left\\{ai\right\\}$ and $C_{\lambda j,n}=\left\\{\lambda
j,n-\lambda j\right\\}$, where $0\leq i\leq 2\lambda-1$ and $1\leq j\leq h$;

  2. (2)

$C_{ia+\lambda\ell+j,n}=\left\\{ia+\lambda\ell+j,a(i+2j)-(\lambda\ell+j)\right\\}$,
where $0\leq\ell\leq h-1$, $1\leq j\leq\lambda-1$ and $0\leq i\leq
2\lambda-2j$.

Moreover, the above $q$-cyclotomic cosets do not intersect each other, and
their union is $\mathbb{Z}_{n}$.

  * Proof.

Since $q\equiv 1\,({\rm mod}~{}2\lambda)$ and $n=\lambda(q+1)$, we know that
the order of $q$ modulo $n$ is $2$, i.e., ${\rm{ord}}_{n}(q)=2$. So, for any
$i$ with $0\leq i\leq n-1$, $|C_{i,n}|$ is equal to either $1$ or $2$. The
proof of the first case is trivial, thus it is omitted. We prove the second
case below.

For $0\leq\ell\leq h-1$, $1\leq j\leq\lambda-1$ and $0\leq i\leq 2\lambda-2j$,
we have

$q(ia+\lambda\ell+j)\equiv ia-\lambda\ell+qj\,\,({\rm mod}~{}n).$

Since $q=2a-1$, we obtain $ia-\lambda\ell+qj=a(i+2j)-(\lambda\ell+j)$, where
$0<a(i+2j)-(\lambda\ell+j)<n$. On the other hand,

$q\left(a(i+2j)-(\lambda\ell+j)\right)=q(ia-\lambda\ell+qj)\equiv
ia+\lambda\ell+(q^{2}-1)j+j\equiv ia+\lambda\ell+j\,\,({\rm mod}~{}n).$

Moreover, if $ia+\lambda\ell+j=a(i+2j)-(\lambda\ell+j)$ then $\ell=hj$. This
contradicts that $0\leq\ell\leq h-1$. So, $|C_{ia+\lambda\ell+j,n}|=2$ and
$C_{ia+\lambda\ell+j,n}=\\{ia+\lambda\ell+j,a(i+2j)-(\lambda\ell+j)\\}$, where
$0\leq\ell\leq h-1$, $1\leq j\leq\lambda-1$ and $0\leq i\leq 2\lambda-2j$.

It is easy to show that $C_{ai,n}\cap C_{\lambda j,n}=\emptyset,C_{ai,n}\cap
C_{ai+\lambda\ell+j,n}=\emptyset$ and $C_{\lambda j,n}\cap
C_{ai+\lambda\ell+j,n}=\emptyset$. Moreover,

$N_{1}=\sum_{i=0}^{2\lambda-1}|C_{ai,n}|=2\lambda,\,\,N_{2}=\sum_{j=1}^{h}|C_{\lambda
j,n}|=2h,$

and

$N_{3}=\sum_{\ell=0}^{h-1}\sum_{j=1}^{\lambda-1}\sum_{i=0}^{2\lambda-2j}\,|\,C_{ai+\lambda\ell+j,n}|=2h[(2\lambda-1)+(2\lambda-3)+\cdots+3]=2h(\lambda^{2}-1).$

Then $N_{1}+N_{2}+N_{3}=\lambda(q+1)$. This completes the proof.  $\square$

The following lemma is very helpful for constructing optimal cyclic
$(r,\delta)$-LRCs.

######  Lemma 3.2.

Let $q$ be an odd prime power and $\lambda(\geq 2)$ be a positive integer
satisfying $q\equiv 1~{}({\rm mod}~{}2\lambda)$, and $b$ be an integer with
$0\leq b\leq\frac{q-3}{2}$. Let $n=\lambda(q+1)$ and $a=\frac{q+1}{2}$. Set

$S=\cup_{j\in X}\left\\{j,j+2a,j+4a,\ldots,j+2a(\lambda-1)\right\\},$

where $X=\\{a-b,a-b+1,\ldots,a+b\\}$. Then

$S=\cup_{j=0}^{b}\cup_{i=1}^{\lambda}C_{(2i-1)a-j,n}.$

  * Proof.

We arrange all the elements of $S$ into a $\lambda\times(2b+1)$ matrix as
follows:

$\displaystyle
M=\left(\begin{array}[]{ccccccc}a-b&\cdots&a-1&a&a+1&\cdots&a+b\\\
3a-b&\cdots&3a-1&3a&3a+1&\cdots&3a+b\\\
\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
(2\lambda-1)a-b&\cdots&(2\lambda-1)a-1&(2\lambda-1)a&(2\lambda-1)a+1&\cdots&(2\lambda-1)a+b\\\
\end{array}\right).$ (3)

Let $M_{1}$ and $M_{2}$ be the sets of all elements in the first $b$ and last
$b$ columns of $M$, respectively and denote them by

$M_{1}=\left\\{a(2i-1)-j\,\,|\,\,1\leq i\leq\lambda,1\leq j\leq
b\right\\},\,\,\,M_{2}=\left\\{a(2i-1)+j\,\,|\,\,1\leq i\leq\lambda,1\leq
j\leq b\right\\}.$

Next, we show that for any $\theta\in M_{1}$, its coset conjugate belongs to
$M_{2}$, i.e., $(q\theta)_{n}\in M_{2}$, and vice versa. For $a(2i-1)-j\in
M_{1}$, we have

$\displaystyle q(a(2i-1)-j)$ $\displaystyle=aq(2i-1)-a(2i-1)+a(2i-1)-(2a-1)j$
$\displaystyle\equiv a(2i-2j-1)+j~{}({\rm mod}~{}n).$

Now we prove that $(a(2i-2j-1)+j)_{n}=a(2i-2j-1)_{2\lambda}+j\in M_{2}$. Since
$1\leq i\leq\lambda$ and $1\leq j\leq b$, we have

$(2i-2j-1)a+j\leq(2\lambda-3)a+b<2a(\lambda-1)<n.$

If $0\leq(2i-2j-1)a+j<n$ for some $i$ and $j$, then $(2i-2j-1)a<n$ and
$2i-2j-1<2\lambda$. So,

$((2i-2j-1)a+j)_{n}=(2i-2j-1)a+j=a(2i-2j-1)_{2\lambda}+j.$ (4)

If $(2i-2j-1)a+j<0$ for some $i$ and $1\leq j\leq b$, then $2i-2j-1<0$. There
exists a negative integer $u$ such that $2i-2j-1=2\lambda
u+(2i-2j-1)_{2\lambda}$ and $0\leq(2i-2j-1)_{2\lambda}\leq 2\lambda-1$. Then
$(2i-2j-1)a=nu+a(2i-2j-1)_{2\lambda}$. Since $0\leq a(2i-2j-1)_{2\lambda}\leq
n-a$, we have $((2i-2j-1)a)_{n}=a(2i-2j-1)_{2\lambda}$. It is easy to check
that $1\leq a(2i-2j-1)_{2\lambda}+j<n$ for $1\leq j\leq b$. So, from
$(2i-2j-1)a+j=nu+a(2i-2j-1)_{2\lambda}+j$, we have

$((2i-2j-1)a+j)_{n}=a(2i-2j-1)_{2\lambda}+j.$ (5)

It is easy to see that $(2i-2j-1)_{2\lambda}$ is an odd number and
$0\leq(2i-2j-1)_{2\lambda}\leq 2\lambda-1$. For a fixed $j$ with $1\leq j\leq
b$, one can show that $(2i_{1}-2j-1)_{2\lambda}\neq(2i_{2}-2j-1)_{2\lambda}$
for any $1\leq i_{1}\neq i_{2}\leq\lambda$. So,
$\\{(2i-2j-1)_{2\lambda}\,|\,1\leq i\leq\lambda\\}=\\{2i-1\,|\,1\leq
i\leq\lambda\\}$ for $1\leq j\leq b$. Combining (4) and (5) we show that for
any $a(2i-1)-j\in M_{1}$, $(q(a(2i-1)-j))_{n}\in M_{2}$. Similarly, for any
$a(2i-1)+j\in M_{2}$, we can also prove that $(q(a(2i-1)+j))_{n}\in M_{1}$.
So,

$C_{(2i-1)a-j,n}=\left\\{(2i-1)a-j,a(2i-2j-1)_{2\lambda}+j\right\\}\,\,{\rm
and}\,\,M_{1}\cup M_{2}=\cup_{j=1}^{b}\cup_{i=1}^{\lambda}C_{(2i-1)a-j,n}.$
(6)

Let $M_{3}$ be the set of all elements of the $(b+1)$-th column of $M$, and
$M_{3}=\\{a,3a,\ldots,(2\lambda-1)a\\}$. By Lemma 3.1 (1), we have
$M_{3}=\cup_{i=1}^{\lambda}C_{(2i-1)a,n}$. Therefore,

$\displaystyle S$ $\displaystyle=\cup_{j\in
X}\\{j,j+2a,j+4a,\ldots,j+2a(\lambda-1)\\}$ $\displaystyle=M_{1}\cup M_{2}\cup
M_{3}$
$\displaystyle=\cup_{j=1}^{b}\cup_{i=1}^{\lambda}C_{(2i-1)a-j,n}\cup_{i=1}^{\lambda}C_{(2i-1)a,n}$
$\displaystyle=\cup_{j=0}^{b}\cup_{i=1}^{\lambda}C_{(2i-1)a-j,n}.$

This completes the proof.  $\square$

By Lemmas 2.3 and 3.2, we can construct a class of optimal cyclic
$(r,\delta)$-LRCs of length $\lambda(q+1)$ with $r+\delta-1=q+1$ as follows.

######  Theorem 3.3.

Follow the notation and conditions of Lemma 3.2. Let ${\mathcal{C}}$ be a
cyclic code of length $n$ over ${\mathbb{F}}_{q}$ with defining set
${\mathcal{D}}=C_{a-(b+1),n}\cup S$. If
$\gcd(2a(\lambda-(b)_{\lambda}-1)+1,n)=1$, then ${\mathcal{C}}$ is an optimal
cyclic $(r,\delta)$-LRC with parameters
$[\lambda(q+1),\lambda(q+2-\delta)-2,\delta+2]$, where $\delta=2(b+1)$ and
$r+\delta-1=q+1$.

  * Proof.

Let ${\mathcal{C}}$ be a $q$-ary cyclic code of length $n=\lambda(q+1)$ with
defining set ${\mathcal{D}}$, where $S$ is given in Lemma 3.2. Then,
$|X|=2b+1$ and $|S|=(2b+1)\lambda$. So,

${\rm
dim}_{\mathbb{F}_{q}}({\mathcal{C}})=n-|{\mathcal{D}}|=n-(|S|+2)=\lambda(q-\delta+2)-2.$

Since $S\subseteq{\mathcal{D}}$, by Lemma 2.3 we know that ${\mathcal{C}}$ has
$(r,\delta)$-locality, and $r=q-\delta+2$.

Set $i=1$ and $j=b+1$ in (6). Then
$C_{a-(b+1),n}=\\{a-(b+1),a(-2b-1)_{2\lambda}+b+1\\}$. It is known that $0\leq
b\leq\frac{q-3}{2}$. Let $b=\lambda v+(b)_{\lambda}$, where
$0\leq(b)_{\lambda}\leq\lambda-1$. Then $2b+1=2\lambda v+2(b)_{\lambda}+1$.
This implies that $-2b-1=-2\lambda(v+1)+(2\lambda-2(b)_{\lambda}-1)$ and
$1\leq 2\lambda-2(b)_{\lambda}-1\leq 2\lambda-1$. This shows that
$(-2b-1)_{2\lambda}=2\lambda-2(b)_{\lambda}-1$. So,

$C_{a-(b+1),n}=\\{a-(b+1),(2\lambda-2(b)_{\lambda}-1)a+b+1\\}.$ (7)

Let $M$ be a matrix given by (3). Next, we discuss the minimal distance of
cyclic code ${\mathcal{C}}$ in two cases: $(b)_{\lambda}=\lambda-1$ and
$0\leq(b)_{\lambda}\leq\lambda-2$.

Case I: $(b)_{\lambda}=\lambda-1$. Since ${\mathcal{D}}=C_{a-(b+1),n}\cup S$,
from (7) and the first row of the matrix $M$, we have

$\\{a-(b+1),a-b,\ldots,a,\ldots,a+b,a+b+1\\}\subseteq{\mathcal{D}}.$

By Proposition 2.1, $d({\mathcal{C}})\geq 2b+4=\delta+2.$ On the other hand,
by the Singleton-like bound (2),

$d({\mathcal{C}})\leq\lambda(\delta-1)+3-\left(\left\lceil\frac{\lambda(q-\delta+2)-2}{q-\delta+2}\right\rceil-1\right)(\delta-1)=\delta+2.$

So, $d({\mathcal{C}})=\delta+2$.

Case II: $0\leq(b)_{\lambda}\leq\lambda-2$. From (7) we add $a-(b+1)$ into the
first row of $M$ and $(2\lambda-2(b)_{\lambda}-1)a+b+1$ into the
$(\lambda-(b)_{\lambda})$-th row of $M$, and the set of all elements of these
two new rows can be rewritten as follows:

$\displaystyle\\{a-i|-b\leq i\leq
b+1\\}\cup\\{(2\lambda-2(b)_{\lambda}-1)a-j|-(b+1)\leq j\leq b\\}$
$\displaystyle=$
$\displaystyle\\{a-(b+1)+i_{1}+i_{2}(2(\lambda-(b)_{\lambda}-1)a+1)|0\leq
i_{1}\leq 2b+1,0\leq i_{2}\leq 1\\}\subseteq{\mathcal{D}}.$

Since ${\rm gcd}(2a(\lambda-(b)_{\lambda}-1)+1,n)=1$, $d({\mathcal{C}})\geq
2b+4=\delta+2$ by Proposition 2.2. On the other hand, by the Singleton-like
bound (2), $d({\mathcal{C}})\leq\delta+2$. So, $d({\mathcal{C}})=\delta+2$.

Combining above two cases, we prove that ${\mathcal{C}}$ is an optimal cyclic
$(r,\delta)$-LRC with parameters
$[\lambda(q+1),\lambda(q+2-\delta)-2,\delta+2]$, where $r+\delta-1=q+1$.
$\square$

######  Remark 3.4.

(1) In [27, Theorem 3.1], the authors constructed a class of optimal cyclic
$(r,\delta)$-LRCs with parameters $[2(q+1),2(q+2-\delta)-2,\delta+2]_{q}$,
where $q\equiv 1~{}({\rm mod}~{}4)$ is an odd prime power and
$r+\delta-1=q+1$. Such optimal cyclic $(r,\delta)$-LRCs can be obtained from
Theorem 3.3 by setting $\lambda=2$.

(2) In [4, Theorem 1], the authors constructed a class of optimal cyclic
$(r,\delta)$-LRCs with parameters $[3(q+1),3(q+2-\delta)-2,\delta+2]_{q}$,
where $q\equiv 1~{}({\rm mod}~{}6)$ is an odd prime power and
$r+\delta-1=q+1$. Such optimal cyclic $(r,\delta)$-LRCs can be obtained from
Theorem 3.3 by setting $\lambda=3$.

By Theorem 3.3, some examples of new optimal cyclic $(r,\delta)$-LRCs are
provided as follows.

######  Example 3.5.

Let $q=9$ and $\lambda=4$. Then $n=\lambda(q+1)=40,a=\frac{q+1}{2}=5$ and
$0\leq b\leq 3$. Suppose that $b=0$, then $\delta=2(b+1)=2$ and $X=\\{5\\}$.
By Lemma 3.2,

$S=\cup_{j\in X}\\{j,j+2a,j+4a,j+6a\\}=C_{5,40}\cup C_{15,40}\cup
C_{25,40}\cup C_{35,40}.$

Let ${\mathcal{C}}$ be a cyclic code of length $40$ over $\mathbb{F}_{9}$ with
defining set ${\mathcal{D}}=C_{4,40}\cup S$. Magma verifies that
${\mathcal{C}}$ is a $[40,34,4]_{9}$ code. By Lemma 2.3, ${\mathcal{C}}$ has
$(9,2)$-locality. So, ${\mathcal{C}}$ is an optimal cyclic $(9,2)$-LRC with
parameters $[40,34,4]_{9}$ from Singleton-like bound. This result is
consistent with Theorem 3.3. Moreover, this code can not be obtained from [4,
21, 27]. By setting $b=1,2$ and $3$, we can also obtain optimal cyclic LRCs
with new parameters $(7,4)$-$[40,26,6]_{9}$, $(5,6)$-$[40,18,8]_{9}$ and
$(3,8)$-$[40,10,10]_{9}$, respectively and these optimal cyclic
$(r,\delta)$-LRCs can not be obtained from [4, 21, 27].

######  Example 3.6.

Let $q=11$ and $\lambda=5$. Then $n=\lambda(q+1)=60,a=\frac{q+1}{2}=6,0\leq
b\leq 4$ and $b\neq 2$. Suppose that $b=4$, then $\delta=2(b+1)=10$ and
$X=\\{2,3,4,5,6,7,8,9,10\\}$. By Lemma 3.2,

$S=\cup_{j\in
X}\\{j,j+2a,j+4a,j+6a,j+8a\\}=\cup_{j=0}^{4}\cup_{i=1}^{5}C_{6(2i-1)-j,60}.$

Let ${\mathcal{C}}$ be a cyclic code of length $60$ over $\mathbb{F}_{11}$
with defining set ${\mathcal{D}}=C_{1,60}\cup S$. Magma verifies that
${\mathcal{C}}$ is a $[60,13,12]_{11}$ code. By Lemma 2.3, ${\mathcal{C}}$ has
$(3,10)$-locality. So, ${\mathcal{C}}$ is an optimal cyclic $(3,10)$-LRC with
parameters $[60,13,12]_{11}$ from Singleton-like bound. This result is
consistent with Theorem 3.3. Moreover, this code can not be obtained from [4,
21, 27]. By setting $b=0,1$ and $3$, we can also obtain optimal LRCs with new
parameters $(11,2)$-$[60,53,4]_{11}$,$(9,4)$-$[60,43,6]_{11}$ and
$(5,8)$-$[60,23,10]_{11}$, respectively and these optimal $(r,\delta)$-LRCs
can not be obtained from [4, 21, 27].

###  3.2 Optimal cyclic $(r,\delta)$-LRCs with $r+\delta-1=\frac{q+1}{2}$

Let $q$ be an odd prime power and $\lambda(\geq 3)$ be a positive integer
satisfying $q\equiv 1~{}({\rm mod}~{}2\lambda)$ and $q\equiv 3~{}({\rm
mod}~{}4)$. In this subsection, we construct a class of optimal cyclic
$(r,\delta)$-LRCs of length $\lambda(q+1)$ with $r+\delta-1=\frac{q+1}{2}$. To
this end, we first give a preliminary lemma.

######  Lemma 3.7.

Let $n=\lambda(q+1)$ and $a=\frac{q+1}{2}$. Assume that $b$ is an integer with
$\frac{a}{2}\leq b\leq\frac{q-3}{2}$. Set

$S=\cup_{j\in U}\\{j,j+a,j+2a,\ldots,j+(2\lambda-1)a\\},$

where $U=\\{a-b,a-b+1,\ldots,b\\}$. Then

$\displaystyle S=\cup_{j=a-b}^{b}\cup_{i=1}^{\lambda}C_{(2i-1)a-j,n}.$

  * Proof.

Set

$\displaystyle V=\\{b+1,b+2,\ldots,2a-(b+1)\\}=\\{a-v,a-v+1,\ldots,a+v\\},$

where $v=a-(b+1)$. By Lemma 3.2, we have

$\cup_{j\in
V}\\{j,j+2a,\ldots,j+2(\lambda-1)a\\}=\cup_{j=0}^{v}\cup_{i=1}^{\lambda}C_{(2i-1)a-j,n}.$

It is easy to check that

$\displaystyle S$ $\displaystyle=\cup_{j\in
U}\\{j,j+a,j+2a,\ldots,j+(2\lambda-1)a\\}$ $\displaystyle=\cup_{j\in
X}\\{j,j+2a,\ldots,j+2(\lambda-1)a\\}\backslash\left(\cup_{j\in
V}\\{j,j+2a,\ldots,j+2(\lambda-1)a\\}\right)$
$\displaystyle=\cup_{j=0}^{b}\cup_{i=1}^{\lambda}C_{(2i-1)a-j,n}\backslash\left(\cup_{j=0}^{v}\cup_{i=1}^{\lambda}C_{(2i-1)a-j,n}\right)$
$\displaystyle=\cup_{j=v+1}^{b}\cup_{i=1}^{\lambda}C_{(2i-1)a-j,n},$

where $X=\\{a-b,a-b+1,\ldots,a+b\\}$, which is given in Lemma 3.2. This
completes the proof.  $\square$

By Lemma 3.7, we can construct a class of optimal cyclic $(r,\delta)$-LRCs of
length $\lambda(q+1)$ with $r+\delta-1=\frac{q+1}{2}$ as follows.

######  Theorem 3.8.

Follow the notation and conditions of Lemma 3.7. Let ${\mathcal{C}}$ be a
cyclic code of length $n$ over ${\mathbb{F}}_{q}$ with defining set
${\mathcal{D}}=C_{a-(b+1),n}\cup S$. If ${\rm
gcd}((2\lambda-2(b)_{\lambda}-1)a+1,n)=1$, then ${\mathcal{C}}$ is an optimal
cyclic $(r,\delta)$-LRC with parameters
$[\lambda(q+1),\lambda(q+3-2\delta)-2,\delta+2]_{q}$, where $\delta=2(b+1)-a$
and $r+\delta-1=\frac{q+1}{2}$.

  * Proof.

Let ${\mathcal{C}}$ be a $q$-ary cyclic code of length $n=\lambda(q+1)$ with
defining set ${\mathcal{D}}$, where $S$ is given in Lemma 3.7. Then,
$|U|=2b+1-a$ and $|S|=2\lambda(2b+1-a)$. So,

${\rm
dim}_{\mathbb{F}_{q}}({\mathcal{C}})=n-|{\mathcal{D}}|=n-(|S|+2)=\lambda(q+3-2\delta)-2.$

Since $S\subseteq{\mathcal{D}}$, by Lemma 2.3 we know that ${\mathcal{C}}$ has
$(r,\delta)$-locality, where $r=\frac{q+3}{2}-\delta$.

Let $M$ be a matrix given by (3). Since ${\mathcal{D}}=C_{a-(b+1),n}\cup S$,
from (7) we add $a-(b+1)$ into the first row of $M$ and
$(2\lambda-2(b)_{\lambda}-1)a+b+1$ into the $(\lambda-(b)_{\lambda})$-th row
of $M$, and the set of first $(2b-a+2)$ elements in new first row and the last
$(2b-a+2)$ elements in new $(\lambda-(b)_{\lambda})$-th row can be rewritten
as follows:

$\displaystyle\\{a-i|v+1\leq i\leq
b+1\\}\cup\\{(2\lambda-2(b)_{\lambda}-1)a+i\,|\,v+1\leq i\leq b+1\\}$
$\displaystyle=$
$\displaystyle\left\\{a-(b+1)+i_{1}+i_{2}((2\lambda-2(b)_{\lambda}-1)a+1)\,|\,0\leq
i_{1}\leq 2b+1-a,0\leq i_{2}\leq 1\right\\}\subseteq{\mathcal{D}}.$

Since ${\rm gcd}((2\lambda-2(b)_{\lambda}-1)a+1,n)=1$, $d({\mathcal{C}})\geq
2(b+1)-a+2=\delta+2$ by Proposition 2.2. On the other hand, by the Singleton-
like bound (2),

$\displaystyle d({\mathcal{C}})\leq
2\lambda(\delta-1)+3-\left(\left\lceil\frac{2\lambda(q+3-2\delta)-2}{q+3-2\delta}\right\rceil-1\right)(\delta-1)=\delta+2.$

So, $d({\mathcal{C}})=\delta+2$.

Hence, we prove that ${\mathcal{C}}$ is an optimal cyclic $(r,\delta)$-LRC
with parameters $[\lambda(q+1),\lambda(q+3-2\delta)-2,\delta+2]_{q}$, where
$r+\delta-1=\frac{q+1}{2}$. This completes the proof.  $\square$

######  Remark 3.9.

In [27, Theorem 3.4], the authors constructed a class of optimal cyclic
$(r,\delta)$-LRCs with parameters $[2(q+1),2(q+2-2\delta)-2,\delta+2]_{q}$,
where $q\geq 7$ is an odd prime power with $q\equiv 3~{}({\rm mod}~{}4)$ and
$r+\delta-1=\frac{q+1}{2}$. For the case $\lambda\geq 3$, $q\equiv 3~{}({\rm
mod}~{}4)$ and $q\equiv 1~{}({\rm mod}~{}2\lambda)$, it is easy to check that

$\frac{\lambda(q+3-2\delta)-2}{\lambda(q+1)}>\frac{q-2\delta+2}{q+1}>\frac{2(q+2-2\delta)-2}{2(q+1)}.$

This shows that optimal cyclic $(r,\delta)$-LRCs in Theorem 3.8 have new
parameters and a higher code rate by comparing with the known optimal cyclic
$(r,\delta)$-LRCs proposed in [27].

By Theorem 3.8, some examples of new optimal cyclic $(r,\delta)$-LRCs are
given as follows.

######  Example 3.10.

Let $q=7$ and $\lambda=3$. Then $n=3(q+1)=24,a=\frac{q+1}{2}=4,b=2,\delta=2$
and $U=\\{2\\}$. By Lemma 3.7,

$S=\cup_{j\in U}\\{j,j+4,j+8,j+12,j+16,j+20\\}=C_{2,24}\cup C_{10,24}\cup
C_{18,24}.$

Let ${\mathcal{C}}$ be a cyclic code of length $24$ over $\mathbb{F}_{7}$ with
defining set ${\mathcal{D}}=C_{1,24}\cup S$. Magma verifies that
${\mathcal{C}}$ is a $[24,16,4]_{7}$ code. By Lemma 2.3, ${\mathcal{C}}$ has
$(3,2)$-locality. So, ${\mathcal{C}}$ is an optimal cyclic $(3,2)$-LRC with
parameters $[24,16,4]_{7}$ from Singleton-like bound. This result is
consistent with Theorem 3.8. Moreover, this code can not be obtained from [4,
21, 27].

######  Example 3.11.

Let $q=11$ and $\lambda=5$. Then $n=5(q+1)=60,a=\frac{q+1}{2}=6$ and $3\leq
b\leq 4$. Suppose that $b=4$, then $\delta=4$ and $U=\\{2,3,4\\}$. By Lemma
3.7,

$S=\cup_{j\in
U}\\{j,j+6,j+12,\ldots,j+54\\}=\cup_{j=2}^{4}\cup_{i=1}^{5}C_{6(2i-1)-j,60}.$

Let ${\mathcal{C}}$ be a cyclic code of length $60$ with defining set
${\mathcal{D}}=C_{1,60}\cup S$. Magma verifies that ${\mathcal{C}}$ is a
$[60,28,6]_{11}$ code. By Lemma 2.3, ${\mathcal{C}}$ has $(3,4)$-locality. So,
${\mathcal{C}}$ is an optimal cyclic $(3,4)$-LRC with new parameters
$[60,28,6]_{11}$. This result is consistent with Theorem 3.8. Moreover, this
code can not be obtained from [4, 21, 27]. By setting $b=3$, we can also
obtain optimal cyclic $(5,2)$-LRC with new parameters $[60,48,4]_{11}$ and it
can not be obtained from [4, 21, 27].

##  4 Optimal cyclic $(r,\delta)$-LRCs of length $\lambda(q-1)$

Let $q$ be an odd prime power and $\lambda(\geq 2)$ be a positive integer
satisfying $q\equiv-1~{}({\rm mod}~{}2\lambda)$. In this section, we construct
a class of optimal cyclic $(r,\delta)$-LRCs of length $\lambda(q-1)$ with
$r+\delta-1=q-1$. To this end, we first give some preliminary results. The
proof of the following lemma is similar to that in Lemma 3.1, and is omitted
here.

######  Lemma 4.1.

Let $n=\lambda(q-1)$. Then, the following statements hold.

  * (1)

$C_{\lambda\ell,n}=\\{\lambda\ell\\}$, where $1\leq\ell\leq q-1$;

  * (2)

$C_{i\lambda+j,n}=\\{i\lambda+j,\,i\lambda+jq\\}$, where $1\leq
j\leq\lambda-1$ and $0\leq i\leq\frac{\lambda-j}{\lambda}(q+1)-2$.

Moreover, the above $q$-cyclotomic cosets do not intersect each other, and
their union is $\mathbb{Z}_{n}$.

The following lemma is very helpful for constructing optimal cyclic
$(r,\delta)$-LRCs of length $\lambda(q-1)$ with $r+\delta-1=q-1$.

######  Lemma 4.2.

Let $c$ be an integer with $0\leq c\leq\lambda-1$. Let $n=\lambda(q-1)$ and
$s=\frac{q-1}{2}$. Set

$S=\cup_{j\in Y}\\{j,j+2s,j+4s,\ldots,j+2s(\lambda-1)\\},$

where $Y=\\{\lambda-c,\lambda-c+1,\ldots,\lambda+c\\}$. Then

$S=\cup_{j=\lambda-c}^{\lambda+c}\cup_{i\in\Gamma(j)}C_{2s(i-1)+j,n},$ (8)

where $\Gamma(j)$ denotes the set of coset leaders of the $q$-cyclotomic
cosets containing $2s(i-1)+j$ for all $i$ with $1\leq i\leq\lambda$.

  * Proof.

We arrange all the elements of $S$ into a $\lambda\times(2c+1)$ matrix as
follows:

$\displaystyle\mathcal{M}=\left(\begin{array}[]{ccccc}\lambda-c&\cdots&\lambda&\cdots&\lambda+c\\\
2s+\lambda-c&\cdots&2s+\lambda&\cdots&2s+\lambda+c\\\
4s+\lambda-c&\cdots&4s+\lambda&\cdots&4s+\lambda+c\\\
\vdots&\ddots&\vdots&\ddots&\vdots\\\
2(\lambda-1)s+\lambda-c&\cdots&2(\lambda-1)s+\lambda&\cdots&2(\lambda-1)s+\lambda+c\\\
\end{array}\right).$ (9)

Let $M_{j}$ be a set of all elements in a column of $\mathcal{M}$, and denote
it by

$\mathrm{M}_{j}=\left\\{j,\ldots,2s(i_{1}-1)+j,\ldots,2s(\lambda-1)+j\right\\},$

where $1\leq i_{1}\leq\lambda$ and $\lambda-c\leq j\leq\lambda+c$. Next, we
show that $\mathrm{M}_{j}$ can be represented as a union of some
$q$-cyclotomic cosets modulo $n$. For any element
$2s(i_{1}-1)+j\in\mathrm{M}_{j}$, it is easy to check that

$2s(i_{1}-1)+j=\frac{q+1}{\lambda}(i_{1}-1)\lambda+j-2i_{1}+2,$

where $1\leq i_{1}\leq\lambda$ and $1\leq\lambda-c\leq j\leq\lambda+c\leq
2\lambda-1$.

Let $j-2i_{1}+2=\nu\lambda+\gamma$, that is, $\gamma=(j-2i_{1}+2)_{n}$ and
$0\leq\gamma\leq\lambda-1$. If $\gamma=0$, then
$2s(i_{1}-1)+j=(\frac{q+1}{\lambda}(i_{1}-1)+\nu)\lambda.$ By Lemma 4.1 (1),
we have $C_{2s(i_{1}-1)+j,n}=\left\\{2s(i_{1}-1)+j\right\\}$. If
$1\leq\gamma\leq\lambda-1$, i.e., $(j-2i_{1}+2)_{\lambda}\neq 0$, then
$2s(i_{1}-1)+j=(\frac{q+1}{\lambda}(i_{1}-1)+\nu)\lambda+\gamma.$ By Lemma 4.1
(2), we have
$q(2s(i_{1}-1)+j)\equiv(\frac{q+1}{\lambda}(i_{1}-1)+\nu)\lambda+\gamma+(q-1)\gamma~{}({\rm
mod}~{}n).$ Since $q=2s+1$, we obtain that

$q(2s(i_{1}-1)+j)\equiv 2s(i_{1}+\gamma-1)+j~{}({\rm mod}~{}n).$

Conversely,
$2s(i_{1}+\gamma-1)+j=\frac{q+1}{\lambda}(i_{1}-1+\gamma)\lambda+(\nu-1)\lambda+\lambda-\gamma.$
By Lemma 4.1 (2), we have
$q(2s(i_{1}+\gamma-1)+j)\equiv(\frac{q+1}{\lambda}(i_{1}+\gamma-1)+(\nu-1))\lambda+q(\lambda-\gamma)~{}({\rm
mod}~{}n)$. So,

$q(2s(i_{1}+\gamma-1)+j)\equiv 2s(i_{1}+\gamma-1)+j+2s(\lambda-\gamma)\equiv
2s(i_{1}-1)+j~{}({\rm mod}~{}n),$

and $C_{2s(i_{1}-1)+j,n}=\\{2s(i_{1}-1)+j,(2s(i_{1}+\gamma-1)+j)_{n}\\}$,
where $\gamma=(j-2i_{1}+2)_{\lambda}$.

Next, we show that
$(2s(i_{1}+\gamma-1)+j)_{n}=2s(i_{1}+\gamma-1)_{\lambda}+j$. Since $1\leq
i_{1}\leq\lambda$ and $0\leq\gamma\leq\lambda-1$, we have $0\leq
2s(i_{1}+\lambda-1)\leq 2s(2\lambda-1)$. If $0\leq 2s(i_{1}+\gamma-1)<n$ for
some $i_{1}$, then $i_{1}+\gamma-1<\lambda$ and $0\leq 2s(i_{1}+\gamma-1)\leq
n-2s$. This implies that $2s(i_{1}+\gamma-1)+j<n$ for $1\leq j\leq
2\lambda-1$. So,

$(2s(i_{1}+\gamma-1)+j)_{n}=2s(i_{1}+\gamma-1)+j=2s(i_{1}+\gamma-1)_{\lambda}+j.$

If $2s(i_{1}+\gamma-1)\geq n$ for some $i_{1}$, then there exists a positive
integer $\beta$ such that
$i_{1}+\gamma-1=\lambda\beta+(i_{1}+\gamma-1)_{\lambda}$. Then
$2s(i_{1}+\gamma-1)=n\beta+2s(i_{1}+\gamma-1)_{\lambda}$. Since $0\leq
2s(i_{1}+\gamma-1)_{\lambda}\leq n-2s$, we have
$(2s(i_{1}+\gamma-1))_{n}=2s(i_{1}+\gamma-1)_{\lambda}$. It is easy to check
that $0\leq 2s(i_{1}+\gamma-1)_{\lambda}+j<n$ for $1\leq j\leq 2\lambda-1$.
So, from $2s(i_{1}+\gamma-1)+j=n\beta+2s(i_{1}+\gamma-1)_{\lambda}+j,$ we have

$(2s(i_{1}+\gamma-1)+j)_{n}=2s(i_{1}+\gamma-1)_{\lambda}+j.$

Let $i_{2}=(i_{1}+\gamma-1)_{\lambda}+1$, then $1\leq i_{2}\leq\lambda$.
Hence, for any $2s(i_{1}-1)+j\in\mathrm{M}_{j}$, we have

$C_{2s(i_{1}-1)+j,n}=\left\\{2s(i_{1}-1)+j,2s(i_{2}-1)+j\right\\}.$

This shows that the set $\mathrm{M}_{j}$ can be represented as an union of
some $q$-cyclotomic cosets, and moreover, the set of all elements in
$\mathcal{M}$, that is, $S$ can be represented an union of some $q$-cyclotomic
cosets as in (8).  $\square$

By Lemma 4.2, we construct a class of optimal cyclic $(r,\delta)$-LRCs of
length $\lambda(q-1)$ with $r+\delta-1=q-1$ as follows.

######  Theorem 4.3.

Follow the notation and conditions of Lemma 4.2. Let ${\mathcal{C}}$ be a
cyclic code of length $n$ over ${\mathbb{F}}_{q}$ with defining set
${\mathcal{D}}$. If

  * (1)

${\mathcal{D}}=S\cup\\{\lambda-c-1,2s(\lambda-c-1)+\lambda+c+1\\}$ and
$\gcd(2s(\lambda-c-1)+1,n)=1$ for $0\leq c\leq\lambda-2$, or

  * (2)

${\mathcal{D}}=S\cup\\{2s,2s(\lambda-1)+2\lambda\\}$ and
$\gcd(2s(\lambda-2)+1,n)=1$ for $c=\lambda-1$,

then ${\mathcal{C}}$ is an optimal cyclic $(r,\delta)$-LRC with parameters
$[\lambda(q-1),\lambda(q-\delta)-2,\delta+2]_{q}$, where $\delta=2(c+1)$ and
$r+\delta-1=q-1$.

  * Proof.

Let ${\mathcal{C}}$ be a cyclic code of length $n=\lambda(q-1)$ over
$\mathbb{F}_{q}$ with defining set ${\mathcal{D}}$. Let $\mathcal{M}$ be a
matrix given by (9). In the following, we discuss the minimal distance of
cyclic code ${\mathcal{C}}$ in two cases: $0\leq c\leq\lambda-2$ and
$c=\lambda-1$.

Case I: $0\leq c\leq\lambda-2$. Let
${\mathcal{D}}=S\cup\\{\lambda-c-1,2s(\lambda-c-1)+\lambda+c+1\\},$ where $S$
is given in Lemma 4.2. Then, $|Y|=2c+1$ and $|S|=\lambda(2c+1)$. So,

$\dim_{\mathbb{F}_{q}}({\mathcal{C}})=n-|{\mathcal{D}}|=n-(|S|+2)=\lambda(q-\delta)-2.$

Since $S\subseteq{\mathcal{D}}$, by Lemma 2.3 we know that ${\mathcal{C}}$ has
$(r,\delta)$-locality, and $r=q-\delta$. We add $\lambda-c-1$ into the first
row of $\mathcal{M}$ and $2s(\lambda-c-1)+\lambda+c+1$ into the
$(\lambda-c)$-th row of $\mathcal{M}$, and all elements of these two new rows
can be rewritten as follows:

$\displaystyle\left\\{\lambda-i\,|\,-c\leq i\leq
c+1\right\\}\cup\left\\{2s(\lambda-c-1)+\lambda+i\,|\,-c\leq i\leq
c+1\right\\}$ $\displaystyle=$
$\displaystyle\left\\{\lambda-c-1+i_{1}+i_{2}\left(2s(\lambda-c-1)+1\right)\,|\,0\leq
i_{1}\leq 2c+1,0\leq i_{2}\leq 1\right\\}\subseteq{\mathcal{D}}.$

Since ${\rm gcd}(2s(\lambda-c-1)+1,n)=1$, by Proposition 2.2 we know that
$d({\mathcal{C}})\geq 2c+3+1=\delta+2$. On the other hand, by the Singleton-
like bound (2),

$\displaystyle
d({\mathcal{C}})\leq\lambda(\delta-1)+3-\left(\left\lceil\frac{\lambda(q-\delta)-2}{q-\delta}\right\rceil-1\right)(\delta-1)=\delta+2.$

So, $d({\mathcal{C}})=\delta+2$.

Case II: $c=\lambda-1$. Let
${\mathcal{D}}=S\cup\\{2s,2s(\lambda-1)+2\lambda\\},$ where $S$ is given in
Lemma 4.2. Then, $|Y|=2\lambda-1$ and $|S|=\lambda(2\lambda-1)$. So,

$\dim_{\mathbb{F}_{q}}({\mathcal{C}})=n-|{\mathcal{D}}|=n-(|S|+2)=\lambda(q-\delta)-2.$

Since $S\subseteq{\mathcal{D}}$, by Lemma 2.3 we know that ${\mathcal{C}}$ has
$(q-2\lambda,2\lambda)$-locality. We add $2s$ into the second row of
$\mathcal{M}$ and $2s(\lambda-1)+2\lambda$ into the last row of $\mathcal{M}$,
and all elements of these two new rows can be rewritten as follows:

$\displaystyle\left\\{2s+i\,|\,0\leq i\leq
2\lambda-1\right\\}\cup\left\\{2s(\lambda-1)+j\,|\,1\leq j\leq
2\lambda\right\\}$ $\displaystyle=$
$\displaystyle\left\\{2s+i_{1}+i_{2}\left(2s(\lambda-2)+1\right)\,|\,0\leq
i_{1}\leq 2\lambda-1,0\leq i_{2}\leq 1\right\\}\subseteq{\mathcal{D}}.$

Since ${\rm gcd}(2s(\lambda-2)+1,n)=1$, by Proposition 2.2,
$d({\mathcal{C}})\geq 2\lambda+2.$ On the other hand, by the Singleton-like
bound (2), $d({\mathcal{C}})\leq 2\lambda+2$. So,
$d({\mathcal{C}})=2\lambda+2=\delta+2$.

Combining above two cases, we show that ${\mathcal{C}}$ is an optimal cyclic
$(r,\delta)$-LRC with parameters
$[\lambda(q-1),\lambda(q-\delta)-2,\delta+2]$, where $r+\delta-1=q-1$. This
completes the proof.  $\square$

######  Remark 4.4.

In [4, Theorem 3], the authors constructed a class of optimal cyclic
$(r,\delta)$-LRCs with parameters $[3(q-1),3(q-\delta)-1,\delta+1]_{q}$, where
$q\equiv 7~{}({\rm mod}~{}9)$, $r+\delta-1=q-1$,
$2\leq\delta\leq\frac{2(q-1)}{3}$ is even and $\delta\not\equiv 0~{}({\rm
mod}~{}6)$. By setting $\lambda=3$, Theorem 4.3 can derive a class of new
optimal cyclic $(r,\delta)$-LRCs with parameters
$[3(q-1),3(q-\delta)-2,\delta+2]_{q}$, where $q\equiv 5~{}({\rm
mod}~{}6),2\leq\delta\leq 6$ and $r+\delta-1=q-1$. Moreover, our result in
Theorem 4.3 can construct optimal cyclic $(r,\delta)$-LRCs with more flexible
parameters, and these optimal cyclic $(r,\delta)$-LRCs can not be obtained
from [4].

In the following, some examples of new optimal cyclic $(r,\delta)$-LRCs are
derived from Theorem 4.3.

######  Example 4.5.

Let $q=11$ and $\lambda=3$. Then, $n=3(q-1)=30,s=\frac{q-1}{2}=5$ and $1\leq
c\leq 2$. Suppose that $c=1$, then $Y=\\{2,3,4\\}$ and $\delta=4$. For $2\leq
j\leq 4$ and $1\leq i_{1},i_{2}\leq 3$, then
$\Gamma(2)=\\{1,2\\},\Gamma(3)=\\{1,2\\},\Gamma(4)=\\{1,3\\}.$ By Lemma 4.2,

$S=\cup_{j\in Y}\\{j,j+2s,j+4s\\}=C_{2,30}\cup C_{3,30}\cup C_{4,30}\cup
C_{12,30}\cup C_{13,30}\cup C_{24,30}.$

Let ${\mathcal{C}}$ be a cyclic code of length $30$ over $\mathbb{F}_{11}$
with defining set ${\mathcal{D}}=S\cup\\{1,15\\}$. Magma verifies that
${\mathcal{C}}$ is a $[30,19,6]_{11}$ code. By Lemma 2.3, ${\mathcal{C}}$ has
$(7,4)$-locality. So, ${\mathcal{C}}$ is an optimal cyclic $(7,4)$-LRC with
parameters $[30,19,6]_{11}$. This result is consistent with Theorem 4.3.
Moreover, this code can not be obtained from [4]. By setting $c=2$, we can
also obtain an optimal cyclic $(5,6)$-LRC with parameters $[30,13,8]_{11}$ and
this code can not be obtained from [4].

######  Example 4.6.

Let $q=23$ and $\lambda=4$. Then, $n=4(q-1)=88,s=\frac{q-1}{2}=11$ and $0\leq
c\leq 3$. Suppose that $c=0$, then $Y=\\{4\\}$ and $\delta=2$. For $j=4$ and
$1\leq i_{1},i_{2}\leq 4$, then $\Gamma(4)=\\{1,2,3\\}$. By Lemma 4.2,

$S=\cup_{j\in Y}\\{j,j+2s,j+4s,j+6s\\}=C_{4,88}\cup C_{26,88}\cup C_{48,88}.$

Let ${\mathcal{C}}$ be a cyclic code of length $88$ over $\mathbb{F}_{23}$
with defining set ${\mathcal{D}}=S\cup\\{3,71\\}$. Magma verifies that
${\mathcal{C}}$ is a $[88,82,4]_{23}$ code. By Lemma 2.3, ${\mathcal{C}}$ has
$(21,2)$-locality. So, ${\mathcal{C}}$ is an optimal cyclic $(21,2)$-LRC with
parameters $[88,82,4]_{23}$. This result is consistent with Theorem 4.3.
Moreover, this code can not be obtained from [4]. By setting $c=1,2$ and $3$,
we can also obtain optimal cyclic LRCs with parameters
$(19,4)$-$[88,74,6]_{23}$, $(17,6)$-$[88,66,8]_{23}$ and
$(15,8)$-$[88,58,10]_{23}$, respectively and these codes can not be obtained
from [4].

##  5 Conclusion

In this paper, we constructed three classes of new optimal cyclic
$(r,\delta)$-LRCs of length $n=\lambda(q+1)$ or $n=\lambda(q-1)$ over
${\mathbb{F}}_{q}$ by investigating the defining sets of cyclic codes. Our
results generalized the related work of [4, 27] and the obtained optimal
cyclic $(r,\delta)$-LRCs have flexible parameters. Lots of numerical examples
were given to show that our constructions are capable to generate optimal
cyclic $(r,\delta)$-LRCs with new parameters.

## References

## References

  * [1] H. Cai, Y. Miao, M. Schwartz, X. Tang, On optimal locally repairable codes with super-linear length, IEEE Trans. Inf. Theory 66(8) (2020) 4853-4868.
  * [2] B. Chen, S. Xia, J. Hao, F.-W. Fu, Constructions of optimal cyclic $(r,\delta)$ locally repairable codes, IEEE Trans. Inf. Theory 64 (4) (2018) 2499-2511.
  * [3] B. Chen, W. Fang, S. Xia, F.-W. Fu, Constructions of optimal $(r,\delta)$ locally repairable codes via constacyclic codes, IEEE Trans. Commun. 67 (8) (2019) 5253-5263.
  * [4] M. Chen, X. Kai, Constructions of two classes of optimal cyclic locally repairable codes, J. Sys. Sci. Math. Scis. 42 (2) (2022) 487-494.
  * [5] W. Fang, F.-W. Fu, B. Chen, S. Xia, Singleton-optimal LRCs and perfect LRCs via cyclic and constacyclic codes, Finite Fields Appl. 91 (2023) 102273.
  * [6] W. Fang, F.-W. Fu, Optimal cyclic $(r,\delta)$ locally repairable codes with unbounded length, Finite Fields Appl. 63 (2020) 101650.
  * [7] Q. Fu, R. Li, L. Guo, L. Lv, Locality of optimal binary codes, Finite Fields Appl. 48 (2017) 371-394.
  * [8] P. Gopalan, C. Huang, H. Simitci, S. Yekhanin, On the locality of codeword symbols, IEEE Trans. Inf. Theory 58 (11) (2012) 6925-6934.
  * [9] V. Guruswami, C. Xing, C. Yuan, How long can optimal locally repairable codes be? IEEE Trans. Inf. Theory 65 (6) (2019) 3662-3670.
  * [10] J. Hao, S. Xia, B. Chen, Some results on optimal locally repairable codes, IEEE Int. Symp. Inf. Theory (ISIT) (2016) 440-444.
  * [11] C. R. P. Hartmann, K. K. Tzeng, Generalizations of the BCH bound, Inf. Control 20 (5) (1972) 489-498.
  * [12] Z. Heng, X. Wang, X. Li, Constructions of cyclic codes and extended primitive cyclic codes with their applications, Finite Fields Appl. 89 (2023) 102208.
  * [13] L. Jin, Explicit construction of optimal locally recoverable codes of distance $5$ and $6$ via binary constant weight codes, IEEE Trans. Inf. Theory 65 (8) (2019) 4658-4663.
  * [14] L. Jin, L, Ma, C. Xing, Construction of optimal locally repairable codes via automorphism groups of rational function fields, IEEE Trans. Inf. Theory 66 (1) (2020) 210-221.
  * [15] M.N. Krishnan, B. Puranik, P.V. Kumar, I. Tamo, A. Barg, Exploiting locality for improved decoding of binary cyclic codes, IEEE Trans. Commun. 66 (6) (2018) 2346-2358.
  * [16] O. Kolosov, A. Barg, I. Tamo, G. Yadgar, Optimal LRC codes for all lenghts $n\leq q$, arXiv:1802.00157 [cs.IT], 2018.
  * [17] X. Kong, X. Wang, G. Ge, New constructions of optimal locally repairable codes with super-linear length, IEEE Trans. Inf. Theory 67 (10) (2021) 6491-6506.
  * [18] X. Li, L. Ma, C. Xing, Optimal locally repairable codes via elliptic curves, IEEE Trans. Inf. Theory 65 (1) (2019) 108-117.
  * [19] X. Li, Z. Heng, Constructions of near MDS codes which are optimal locally recoverable codes, Finite Fields Appl. 88 (2023) 102184.
  * [20] F. Li, H. Chen, S. Lyu, A characterization of optimal locally repairable codes, Discrete Math. 346 (2023) 113465.
  * [21] X. Liu, Q. Zeng, Y. Hao, Y. Zhao, J. Zhong, L. Zhou, Optimal cyclic $(r,\delta)$ locally repairable codes with $r+\delta-1=\frac{q+1}{4}$, in: 2021 6th International Conference on Communication, Image and Signal Processing, CCISP, 2021, pp. 11-15.
  * [22] Y. Luo, C. Xing, C. Yuan, Optimal locally repairable codes of distance $3$ and $4$ via cyclic codes, IEEE Trans. Inf. Theory 65 (2) 2019 1048-1053.
  * [23] G. Luo, X. Cao, Constructions of optimal binary locally recoverable codes via a general construction of linear codes, IEEE Trans. Commun. 69 (8) (2019) 4987-4997.
  * [24] G. Luo, S, Ling, Application of optimal $p$-ary linear codes to alphabet-optimal locally repairable codes, Des. Codes Crypt. 90 (2022) 1271-1287.
  * [25] F. J. MacWilliams, N. J. A. Sloane, The theory of error correcting codes. Amsterdam, The Netherlands: North Holland, 1977.
  * [26] N. Prakash, G.M. Kamath, V. Lalitha, P.V. Kumar, Optimal linear codes with a local-error-correction property, IEEE Int. Symp. Inf. Theory (ISIT) (2012) 2779-2780.
  * [27] J. Qian, L. Zhang, New optimal cyclic locally recoverable codes of length $n=2(q+1)$, IEEE Trans. Inf. Theory 66 (1) (2020) 233-239.
  * [28] J. Qiu, D. Zheng, F.-W. Fu, New constructions of optimal cyclic $(r,\delta)$ locally repairable codes from their zeros, IEEE Trans. Inf. Theory 67 (3) (2021) 1596-1608.
  * [29] Z. Sun, S. Zhu, L. Wang, Optimal constacyclic locally repairable codes, IEEE Commun. Lett. 23 (2) (2019) 206-209.
  * [30] I. Tamo, A. Barg, A family of optimal locally recoverable codes, IEEE Trans. Inf. Theory 60 (8) (2014) 4661-4676.
  * [31] I. Tamo, A. Barg, S. Goparaju, R. Calderbank, Cyclic LRC codes and their subfield subcodes, IEEE Int. Symp. Inf. Theory (ISIT) (2015) 1262-1266.
  * [32] I. Tamo, A. Barg, S. Goparaju, R. Calderbank, Cyclic LRC codes, binary LRC codes, and upper bounds on the distance of cyclic codes, Int. J. Inf. Coding Theory 3 (4) (2016) 345-364.
  * [33] P. Tan, Z. Zhou, H. Yan, U. Parampalli, Optimal cyclic locally repairable codes via cyclotomic polynomials, IEEE Commun. Lett. 23 (2) (2019) 202-205.
  * [34] F. Tian, S. Zhu, Optimal cyclic locally repairable codes with unbounded length from their zeros, Discrete Math. 345 (2022) 112978.
  * [35] W. Zhao, W. Li, S. Yang, K.W. Shum, Several classes of optimal cyclic locally repairable codes of unbounded code lengths, arXiv:2304.00762 [cs.IT], 2023.