# Some Results On the Primary Order Preserving Properties of Stochastic Orders

(Date: February 23, 2020)

###### Abstract.

The usual order ($\leq$) on the real numbers is both additive and
multiplicative. These properties are preserved when comparing these constant
random variables in the usual stochastic order. However, the statements for
the non-constant real-valued random variables have still been missing in the
literature. To examine the existential conditions of order preserving of
additivity and multiplication of stochastic orders on the real-valued random
variables a set of six stochastic orders including the usual, hazard rate,
moment, Laplace transform, convolution and increasing convex order were
considered; and, under independence assumption their order preserving property
statuses were discussed. The results indicated that while the usual, the
moment and the Laplace transform order are both additive and multiplicative,
the hazard rate and the increasing convex order preserve these properties
partially and the convolution order is only additive. As a conclusion,
additivity and multiplication order preserving status of stochastic orders
over real-valued random variables vary by the type of the order.

Mohsen Soltanifar111Mohsen Soltanifar
Biostatistics Division, Dalla Lana School of Public Health, University of
Toronto, Canada
e-mail<EMAIL_ADDRESS>
Keywords Inequalities, Stochastic orders

Mathematics Subject Classification (2010). 60E15

##  1\. Introduction

In their 1934 book on inequalities, Hardy, Littlewood and Polya introduced the
concept of majorization as one of the fundamental building blocks of
stochastic orders. Later in 1955, Lehmann introduced the concept of stochastic
orders on real valued random variables, [1]. Since then, inspired by their
application in many fields there has been a growing literature on these orders
specially from 1994. They have been playing a key role in comparison of
different probability models in wide range of research areas such as survival
analysis, reliability, queuing theory, biology and actuarial science. They
serve as an informative comparison criteria between different distributions
much more effective than low informative distributional point comparisons of
means, medians, variance and IQRs. In almost all cases, they have the same
fundamental properties of usual order $\leq$ in real numbers including
reflexivity, anti-symmetry, transitivity.

This paper deals with exploring another aspect of stochastic orders including
order preserving additive and multiplicative properties. Our investigation
originates from natural existence of earlier fundamental properties in both
the set of real numbers equipped with usual order and the set of real-valued
random variables equipped with one of stochastic orders. Given existence of
the mentioned order preserving properties on the set of real numbers equipped
with the usual order, there was a missing investigation on their parallel
existential conditions for the case of the set of real-valued random variables
equipped with a stochastic order.

This paper is divided into three sections: preliminaries, order preserving
properties of usual stochastic order; and, order preserving properties of
other stochastic orders. In the first section, we provide the required
definitions and established results for the next two sections. Then in the
second section, we establish order preserving additive and multiplicative
properties for the usual stochastic order. Finally, in the last section we
discuss these properties for five other stochastic orders including the hazard
rate order, the moment order, the Laplace transformation order, the
convolution order and the increasing convex order.

##  2\. Preliminaries

The reader who has studied the concepts of order and stochastic order is well
acquainted with the following definitions and results. For an essential
account of the mentioned concepts, see [2, 3, 4]. We begin with some
definitions:

######  Definition 2.1.

Let $P$ be a set. An order on $P$ is a binary $\leq$ on $P$ such that for all
$x,y,z\in P:$
(i) $x\leq x$ (reflexivity),
(ii) $x\leq y$ and $y\leq x$ imply $x=y$ (anti-symmetry),
(iii) $x\leq y$ and $y\leq z$ imply $x\leq z$ (transitivity).

######  Definition 2.2.

Let $P$ and $Q$ be ordered sets. A map $\phi:P\rightarrow Q$ is said to be
order preserving whenever $x\leq y$ in $P$ implies $\phi(x)\leq\phi(y),$ in
$Q.$

When $P=Q$ and for fixed $z\in P$ the maps $\phi_{z}^{add}(x)=x+z$ and
$\phi_{z}^{mul}(x)=xz(0<z)$ are order preserving, it is said that the order
$\leq$ has additivity and multiplication properties.

It is trivial that for the case $P=\mathbb{R}$ equipped with its usual order
$\leq$, the order has all of reflexivity, anti-symmetry, transitivity,
additivity and multiplication properties. From now onward, throughout this
paper it is assumed that $P$ is the set of all real valued random variables.
For the orders related to this $P$ we begin with one of the most well-known
ones:

######  Definition 2.3.

Let $X$ and $Y$ be two real-valued random variables with finite means and
associated Cumulative Distribution Functions $F_{X}$, and $F_{Y}$,
respectively. $X$ is said to be less or equal than $Y$ in the usual stochastic
order denoted by $X\leq_{st}Y$, if:

$F_{X}(t)\geq F_{Y}(t)\ \ \ (-\infty<t<\infty).$

It has been mentioned in the literature that usual stochastic order is
reflexive, anti-symmetric and transitive [3]. Regarding order preserving maps
on $P$ we have [4]:

######  Theorem 2.4.

If $X\leq_{st}Y$ and $\phi:\mathbb{R}\rightarrow\mathbb{R}$ is any increasing
function, then $\phi(X)\leq_{st}\phi(Y)$.

In particular, for constant random variable $Z_{0}$, $\phi_{Z_{0}}^{add}$ and
$\phi_{Z_{0}}^{mul}$ are order preserving and hence the usual stochastic order
is additive and multiplicative in this special case. However, the case in
general is still unknown. The other orders of interest in this work are
introduced in the following definition:

######  Definition 2.5.

Let $X$ and $Y$ be two real-valued random variables with finite means and
associated Cumulative Distribution Functions $F_{X}$ and $F_{Y}$,
respectively. $X$ is said to be less or equal than $Y$ in the:

(i) hazard rate order denoted by $X\leq_{hr}Y,$ if for the hazard function
$r(t)=\frac{\frac{dF(t)}{dt}}{1-F(t)}$ we have:

$r_{X}(t)\geq r_{Y}(t)\ \ \text{for all}\ \ -\infty<t<\infty.$

(ii) moment order denoted by $X\leq_{m}Y$, if with assumption $0\leq X,Y$ we
have:

$E(X^{m})\leq E(Y^{m})\ \ \text{for all}\ \ (m\in\mathbb{N}).$

(iii) Laplace transformation order denoted by $X\leq_{Lt}Y$, if with
assumption $0\leq X,Y$ we have:

$L_{X}(s)\geq L_{Y}(s)\ \ \text{for all}\ \ 0<s<\infty.$

(iv) convolution order denoted by $X\leq_{conv}Y$,if for some non-negative
independent random variable $U$ of $X$:

$Y=_{st}X+U.$

(v) increasing convex order denoted by $X\leq_{icx}Y$,if :

$E(g(X))\leq E(g(Y)):\ \ \text{for all increasing convex functions g}.$

######  Remark 2.6.

This work does not cover the moment generating function order $\leq_{mgf}$ as
it is equivalently associated with the Laplace transformation order
$\leq_{Lt}$ (i.e. $X\leq_{mgf}Y$ if an only if $-X\geq_{Lt}-Y$). All results
valid for the later are valid for the former too.

An straightforward verification shows that considering the subset $P_{0}$ of
all constant real-valued random variables of $P$ equipped with one of above
six stochastic orders, the order has both of mentioned order preserving
properties. This is a parallel result to the case of real numbers $\mathbb{R}$
equipped with the usual order $\leq$. The following lemmas will be useful in
the proof of the next sections theorems, [3, 4].

######  Lemma 2.7.

Let $X,Y$ be two real valued random variables with associated Laplace
transforms $L_{X},L_{Y},$ respectively. Then, $X\leq_{conv}Y$ if and only if
for $\phi_{X,Y}=\frac{L_{Y}}{L_{X}}$ we have:

$(-1)^{n}.\phi_{X,Y}^{(n)}(s)\geq 0\ \ \ \text{for all}\ \ (0<s<\infty,\
n\in\mathbb{N})$

######  Lemma 2.8.

Let $X,Y$ be two real valued random variables with associative CDFs
$F_{X},F_{Y},$ respectively. Then, $X\leq_{icx}Y$ if and only if:

$\int_{x}^{\infty}(1-F_{X}(t))dt\leq\int_{x}^{\infty}(1-F_{Y}(t))dt,\ \
\text{for all}\ \ (-\infty<x<\infty).$

We conclude this section with a remark on the independency of involved random
variables:

######  Remark 2.9.

Considering any pair of real numbers $x_{0},y_{0}$ as fixed random variables
$X=x_{0}$ and $Y=y_{0}$, it is trivial that any fixed random variable
$Z=z_{0}$ is independent from each of them. Hence, in the next two sections we
may assume the given random variables $Z$ is independent from $X$ and $Y$.

##  3\. Order Preserving Properties of Usual Stochastic Order

This section deals with general properties of usual stochastic order. The
first three properties has been established as mentioned above. We discuss the
later two properties and present an evidence of the necessity of the
independence condition mentioned in Remark2.9.

######  Theorem 3.1.

The usual stochastic order is (i) additive; and, (ii) multiplicative .

Proof. To prove (i), first let $X\leq_{st}Y,$ and $Z$ be a independent random
variable from $X,Y$. Consequently:

$\displaystyle
F_{Y+Z}(t)=\int_{z=-\infty}^{\infty}F_{Y}(t-z)dF_{Z}(z)\leq\int_{z=-\infty}^{\infty}F_{X}(t-z)dF_{Z}(z)$
$\displaystyle=$ $\displaystyle F_{X+Z}(t)$ $\displaystyle(-\infty<t<\infty)$

Hence, $X+Z\leq_{st}Y+Z.$

To prove (ii), we assume $X\leq_{st}Y,$ and $0\leq_{st}Z.$ Then, by
definition, $F_{X}(t)\geq F_{Y}(t)\ (-\infty<t<\infty)$ and $P(Z<0)=0.$
Consequently,

$\displaystyle F_{XZ}(t)$ $\displaystyle=$ $\displaystyle P(XZ\leq t)$
$\displaystyle=$ $\displaystyle P(XZ\leq t,Z\geq 0)+P(XZ\leq t,Z<0)$
$\displaystyle=$ $\displaystyle P(X\leq\frac{t}{Z},Z\geq 0)$ $\displaystyle=$
$\displaystyle\int_{z=0}^{+\infty}F_{X}(\frac{t}{z})dF_{Z}(z)$
$\displaystyle\geq$
$\displaystyle\int_{z=0}^{+\infty}F_{Y}(\frac{t}{z})dF_{Z}(z)$
$\displaystyle=$ $\displaystyle F_{YZ}(t),\ \ (-\infty<t<\infty).$

Thus, $XZ\leq_{st}YZ.$
$\Box$

######  Remark 3.2.

The assumption of independence is necessary for the usual stochastic order
additivity. As the counterexample, let $X\sim N(0,\frac{1}{2}),Y\sim
N(1,\frac{1}{2})$ be two independent normal random variables. Then, for the
CDF of the standard normal distribution $\Phi$, we have:

$F_{X}(t)=\Phi(\frac{t}{\sqrt{\frac{1}{2}}}))\geq\Phi(\frac{t-1}{\sqrt{\frac{1}{2}}}))=F_{Y}(t),\
\ (-\infty<t<\infty),$

implying: $X\leq_{st}Y.$ On the other hand, take $Z=-X$, consider $Y-X\sim
N(1,1),$ and consequently:

$\displaystyle F_{0}(t)=1_{(-\infty,0)}(t)=0<\Phi(t-1)=F_{Y-X}(t),\ \
(-\infty<t<0),$ $\displaystyle
F_{0}(t)=1_{[0,\infty)}(t)=1>\Phi(t-1)=F_{Y-X}(t),\ \ (0\leq t<\infty).$

yielding: $0\nleq_{st}Y-X.$ Figure 1. presents the CDFs of the involved random
variables.

Figure 1.  Cumulative Function Distributions of random variables in : (a)
Original random variables; (b) added random variables.

##  4\. Order Preserving Properties of Other Stochastic Orders

As we mentioned, there other types of stochastic orders in the literature of
particular interest. In this section we deal with the similar problem of
determining their main five general properties as the case of usual stochastic
order for the hazard rate order ($\leq_{hr}$), the moment order ($\leq_{m}$),
the Laplace transformation order ($\leq_{Lt}$), the convolution order
($\leq_{conv}$) and the increasing convex order ($\leq_{icx}$). First of all,
for the case of reflexivity, anti-symmetry and transitivity we have:

######  Theorem 4.1.

The hazard rate order, moment order, Laplace transformation order, convolution
order and increasing convex order are all reflexive, anti-symmetric and
transitive.

Proof. The proof of reflexivity and anti-symmetry properties are trivial. The
proof of transitivity is straightforward for all the mentioned types of
stochastic orders except the convolution order. For the case of convolution
order, let $X\leq_{conv}Y$ and $Y\leq_{conv}Z.$ Then, by two applications of
Lemma2.7 and an application of Leibniz derivative rule for multiplication we
have:

$\displaystyle(-1)^{n}.\phi_{X,Z}^{(n)}(s)$ $\displaystyle=$
$\displaystyle(-1)^{n}.(\phi_{X,Y}*\phi_{Y,Z})^{(n)}(s)$ $\displaystyle=$
$\displaystyle(-1)^{n}.\sum_{k=0}^{n}(\binom{n}{k}(\phi_{X,Y})^{(k)}*(\phi_{Y,Z})^{(n-k)})(s))$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{n}(\binom{n}{k}(-1)^{k}.(\phi_{X,Y})^{(k)}*(-1)^{(n-k)}.(\phi_{Y,Z})^{(n-k)}(s))$
$\displaystyle\geq$ $\displaystyle 0,\ \ (0<s<\infty,\ n\in\mathbb{N}).$

Hence, by another applications of Lemma2.7, it follows that $X\leq_{conv}Z.$
$\Box$

Next, we deal with the additivity. For the hazard rate order $\leq_{hr}$, an
special case of additive property has been proved whenever $Z$ is IFR (i.e.
$r_{Z}$ is increasing), [4] (Lemma 1.B.3). But the general case is still
unsolved. For the other four orders we have:

######  Theorem 4.2.

The moment order, Laplace transformation order, convolution order and the
increasing convex order are all additive.

Proof. First, for the moment order, the proof is straightforward application
of binomial identity, and the independence condition. Indeed, let $X\leq_{m}Y$
and $X,Y>0$. Then, for any independent $0\leq_{m}Z$ we have:

$\displaystyle E((X+Z)^{m})$ $\displaystyle=$ $\displaystyle
E(\sum_{k=0}^{m}C_{k}^{m}X^{k}Z^{m-k})=\sum_{k=0}^{m}C_{k}^{m}E(X^{k})E(Z^{m-k})$
$\displaystyle\leq$
$\displaystyle\sum_{k=0}^{m}C_{k}^{m}E(Y^{k})E(Z^{m-k})=E(\sum_{k=0}^{m}C_{k}^{m}Y^{k}Z^{m-k})$
$\displaystyle=$ $\displaystyle E((Y+Z)^{m})\ \ \forall m\in\mathbb{N}.$

Thus, $X+Z\leq_{m}Y+Z.$

Second, for the Laplace transformation, the proof is straightforward from of
the Laplace transformation multiplication of sum of independent random
variables. Indeed, let $X\leq_{Lt}Y$ and $0<_{Lt}Z$ be independent. Then we
have:

$\displaystyle L_{X+Z}(t)$ $\displaystyle=$ $\displaystyle
E(e^{-t(X+Z)})=E(e^{-tX}e^{-tZ})=E(e^{-tX})E(e^{-tZ})$ $\displaystyle\leq$
$\displaystyle E(e^{-tY})E(e^{-tZ})=E(e^{-tY}e^{-tZ})=E(e^{-t(Y+Z)})$
$\displaystyle=$ $\displaystyle L_{Y+Z}(t),\forall t\in\mathbb{R},$

implying $X+Z\leq_{Lt}Y+Z.$

Third, we consider the convolution order. Let $X\leq_{conv}Y$ and $Z$ be
independent from $X,Y.$ Then, by the later condition it follows:

$\phi_{X+Z,Y+Z}(s)=\frac{L_{Y+Z}(s)}{L_{X+Z}(s)}=\frac{L_{Y}(s)L_{Z}(s)}{L_{X}(s)L_{Z}(s)}=\phi_{X,Y}(s),\
\ (0<s<\infty).$

Now, two applications of Lemma2.7 and former condition implies
$X+Z\leq_{conv}Y+Z.$

Finally, we consider the increasing convex order. Let $X\leq_{icx}Y$ and $Z$
be independent from $X,Y.$ Then by Lemma2.8 and two times application of
Fubini’s theorem it follows that:

$\displaystyle\int_{x}^{\infty}(1-F_{X+Z}(t))dt$ $\displaystyle=$
$\displaystyle\int_{x}^{\infty}(1-\int_{z=-\infty}^{\infty}F_{X}(t-z)dF_{Z}(z))dt$
$\displaystyle=$
$\displaystyle\int_{x}^{\infty}\int_{z=-\infty}^{\infty}(1-F_{X}(t-z))dF_{Z}(z)dt$
$\displaystyle=$
$\displaystyle\int_{z=-\infty}^{\infty}\int_{x}^{\infty}(1-F_{X}(t-z))dtdF_{Z}(z)$
$\displaystyle\leq$
$\displaystyle\int_{z=-\infty}^{\infty}\int_{x}^{\infty}(1-F_{Y}(t-z))dtdF_{Z}(z)$
$\displaystyle=$ $\displaystyle...$ $\displaystyle=$
$\displaystyle\int_{x}^{\infty}(1-F_{Y+Z}(t))dt\ \ \text{for all}\ \
(-\infty<x<\infty).$

Now, by another application of Lemma2.8 it follows that $X+Z\leq_{icx}Y+Z.$

$\Box$

Finally, we discuss multiplication. For the case of hazard rate order
$\leq_{hr},$ the special case for the IFR random variable $Z$ can be proved
similarly to the case of additivity. We have the following key theorem:

######  Theorem 4.3.

The moment order, the Laplace transformation order, and the increasing convex
order(for special case) are all multiplicative.

Proof. First of all, for the moment order the proof is trivial from
independence condition.

Second, for the Laplace transformation order, let $X\leq_{Lt}Y$ and $0<_{Lt}Z$
be independent from $X,Y.$ Then, we have:

$\displaystyle
L_{XZ}(s)=\int_{z=0}^{\infty}L_{X}(sz)dF_{Z}(z)\geq\int_{z=0}^{\infty}L_{Y}(sz)dF_{Z}(z)$
$\displaystyle=$ $\displaystyle L_{YZ}(s)$ $\displaystyle(0<s<\infty).$

Hence, $XZ\leq_{Lt}YZ$.

Finally, for the case of increasing convex order, let $X\leq_{icx}Y$ and
$0\leq_{st}Z$(and so $0\leq_{icx}Z$) be independent from $X,Y.$ Then, using
Fubini’s theorem we have:

$\displaystyle\int_{x}^{\infty}(1-F_{XZ}(t))dt$ $\displaystyle=$
$\displaystyle\int_{x}^{\infty}(1-\int_{0}^{\infty}F_{X}(\frac{t}{z})dF_{Z}(z))dt$
$\displaystyle=$
$\displaystyle\int_{x}^{\infty}\int_{0}^{\infty}(1-F_{X}(\frac{t}{z})dF_{Z}(z)dt$
$\displaystyle=$
$\displaystyle\int_{0}^{\infty}\int_{x}^{\infty}(1-F_{X}(\frac{t}{z})dtdF_{Z}(z)$
$\displaystyle\leq$
$\displaystyle\int_{0}^{\infty}\int_{x}^{\infty}(1-F_{Y}(\frac{t}{z})dtdF_{Z}(z)$
$\displaystyle=$ $\displaystyle...$ $\displaystyle=$
$\displaystyle\int_{x}^{\infty}(1-F_{XZ}(t))dt,\ \ (-\infty<x<\infty).$

Consequently, by another application of Lemma2.8, it follows that
$XZ\leq_{icx}YZ.$ $\Box$

######  Remark 4.4.

In the above theorem, the proof or counterexample for multiplicity of the
increasing convex order remains an open question.

However, for the case of multiplicativity for the convolution order the
situation is different.

######  Remark 4.5.

The convolution order is not multiplicative. As the counterexample, let $X\sim
exp(1),Y\sim exp(\frac{1}{2}),$ and $Z\sim Bernoulli(\frac{1}{2}),$ be
independent from $X,Y.$ Since $\phi_{X,Y}(s)=\frac{s+1}{2s+1},$ for all
$0<s<\infty$ and
$(-1)^{n}\phi_{X,Y}^{(n)}(s)=\frac{n!.2^{n-1}}{(2s+1)^{n+1}}>0,$ for all
$0<s<\infty;$ by an application of Lemma2.7, $X\leq_{conv}Y.$ However, a
simple conditioning on $Z$ yields
$\phi_{XZ,YZ}(s)=\frac{s^{2}+2s+1}{s^{2}+2.5s+1},$ for all $0<s<\infty.$ But,
$\phi_{XZ,YZ}^{{}^{\prime}}(s)=\frac{0.5(s^{2}-1)}{(s^{2}+2.5s+1)^{2}},$
changes signs from $0<s<1$ to $1\leq s.$ Consequently, by another application
of Lemma2.7, it follows that $XZ\nleq_{conv}YZ.$

Table.1 summarizes the main results in both sections:

Table 1. A Summary of order preserving properties of six stochastic orders

[b]  Order Preserving Property Order Type Addition Multiplication Usual
$\leq_{st}$ Yes Yes Hazard Rate $\leq_{hr}$ * * Moment $\leq_{m}$ Yes Yes
Laplace transformation $\leq_{Lt}$$\dagger$ Yes Yes Convolution $\leq_{conv}$
Yes No Increasing Convex $\leq_{icx}$ Yes *

  * ∗

Special cases were proved to be “Yes”.

  * †

The results hold for the moment generating function order $\leq_{mgf}$ as
well.

Future Work. There are other types of stochastic orders that this study did
not cover their general properties.Some of them included mean residual life
order $\leq_{mrl}$, harmonic mean residual life order $\leq_{hmrl},$ Lorenz
order $\leq_{Lorenz},$ dilation order $\leq_{dil},$ dispersive order
$\leq_{disp},$ execessive wealth order $\leq_{ew},$ peakedness order
$\leq_{peak},$ starshaped order $\leq_{ss},$ pth order $\leq_{p},$ star order
$\leq_{*},$ superadditive order $\leq_{su},$ factorial moment order
$\leq_{fm},$ and total time on test order $\leq_{ttt},$ [3, 4]. It may be of
particular interest for the researchers to investigate their existential
conditions for non-trivial order preserving additive and multiplicative
properties.

## References

  * [1] Mosler, K.; Scarsini,M. Stochastic Orders and Applications: A Classified Bibliography. Springer-Verlage. Berlin. (1993).
  * [2] Davey, B.A.; Priestly, H.A. Introduction to Lattices and Orders(2ed). Camridge University Press, pp.2,23.(2002).
  * [3] Belzunce,F.; Martinez-Riquelme, C.; Mulero, J. An Introduction to Stochastic Orders. Elsevier Ltd, pp.29-30,58,63 .(2016).
  * [4] Shaked, M.; Shantikumar, J. G. Stochastic Orders. Springer, pp.5-6,18, 71.(2010).


# Optimal $(2,\delta)$ Locally Repairable Codes via Punctured Simplex Codes

Dong Wang12, Weijun Fang124, and Sihuang Hu124  1Key Laboratory of Cryptologic
Technology and Information Security, Ministry of Education,
Shandong University, Qingdao, 266237, China<EMAIL_ADDRESS>2School
of Cyber Science and Technology, Shandong University, Qingdao, 266237, China,
{fwj<EMAIL_ADDRESS>4Quancheng Laboratory, Jinan 250103, China

###### Abstract

Locally repairable codes (LRCs) have attracted a lot of attention due to their
applications in distributed storage systems. In this paper, we provide new
constructions of optimal $(2,\delta)$-LRCs. Firstly, by the techniques of
finite geometry, we present a sufficient condition to guarantee a punctured
simplex code to be a $(2,\delta)$-LRC. Secondly, by using characteristic sums
over finite fields and Krawtchouk polynomials, we construct several families
of LRCs with new parameters. All of our new LRCs are optimal with respect to
the generalized Cadambe-Mazumdar bound.

††footnotetext:  This research is supported in part by National Key Research
and Development Program of China under Grant Nos. 2021YFA1001000 and
2022YFA1004900, the National Natural Science Foundation of China under Grant
No. 62201322, the Natural Science Foundation of Shandong under Grant No.
ZR2022QA031. (Corresponding Author: Weijun Fang)

##  I Introduction

In order to ensure the reliability of nodes in large-scale distributed storage
systems, the concept of locally repairable codes was first proposed in [1].
Let $[n]=\\{1,2,...,n\\}$, for a linear code $C$ of length $n$ over the finite
field $\mathbb{F}_{q}$, a code symbol $c_{i}$ of $C$ has locality $r$ if there
exists a subset $R_{i}\subseteq[n]$ such that $i\in R_{i},|R_{i}|\leq r+1$ and
$c_{i}$ is a linear combination of $\\{c_{j}\\}_{j\in R_{i}\backslash\\{i\\}}$
over $\mathbb{F}_{q}$. If each symbol of a codeword in $C$ has locality $r$,
then $C$ is called a locally repairable code with locality $r$ or an $r$-LRC.
However, when multiple node failures happens in a distributed storage system,
the $r$-LRCs can not recover failed nodes successfully. To address this
problem, Prakash et al. [2] extended the concept of $r$-LRCs to
$(r,\delta)$-LRCs which can tolerate any $\delta-1$ erasures. A code symbol
$c_{i}$ of $C$ has locality $(r,\delta)$ if there exists a subset
$R_{i}\subseteq[n]$ such that $i\in R_{i},|R_{i}|\leq r+\delta-1$ and
$d(C|_{R_{i}})\geq\delta$ where $C|_{R_{i}}$ is the punctured code on the set
$[n]\backslash R_{i}$. The code $C$ is called an $(r,\delta)$-LRC if all code
symbols have locality $(r,\delta)$. Obviously when $\delta=2,(r,\delta)$-LRCs
reduce to $r$-LRCs.

###  I-A Known Results about $(r,\delta)$-LRCs

In [2], analogous to the classical Singleton bound for general codes, the
following Singleton-type bound for an $(r,\delta)$-LRC with parameters
$[n,k,d]$ is given as

$d\leq n-k+1-(\lceil k/r\rceil-1)(\delta-1).$ (1)

If an $(r,\delta)$-LRC achieves the Singleton-type bound
$(\ref{singletonBound})$ with equality, then the code is called a Singleton-
optimal $(r,\delta)$-LRC. Due to its interesting algebraic structures and
practical applications in distributed storage systems, several constructions
of Singleton-optimal $(r,\delta)$-LRCs have been proposed in [3, 4, 5, 6, 7,
8]. Note that the Singleton-type bound is independent of the field size. In
[9], Cadambe and Mazumdar derived the first field-dependent bound for $q$-ary
$r$-LRCs with parameters $[n,k,d]$,

$k\leq\min_{s\in\mathbb{Z}_{+}}\\{sr+k_{opt}^{(q)}(n-s(r+1),d)\\},$

where $k_{opt}^{(q)}(n,d)$ is the maximum dimension of a $q$-ary linear code
of length $n$ and minimum distance $d$. The generalized Cadambe-Mazumdar bound
was considered in [10], which stated that for a $q$-ary $(r,\delta)$-LRC with
parameters $[n,k,d]$,

$k\leq\min_{s\in\mathbb{Z}_{+}}\\{sr+k_{opt}^{(q)}(n-s(r+\delta-1),d)\\}.$ (2)

We call a code achieving the generalized C-M bound $(\ref{CMbound_rdeltaLRC})$
with equality as a $k$-optimal $(r,\delta)$-LRC. In [9], the authors proved
that the simplex code is a $k$-optimal 2-LRC. By deleting some columns from
the generator matrix of the simplex code, several new families of $k$-optimal
LRCs with localities 2 or 3 were proposed in [11] and [12]. In [13], Luo et
al. presented several binary $k$-optimal 2-LRCs by deleting or adding some
columns from a binary simplex code and used character sums to determine their
parameters. Motivated by works of [14], Luo et al. constructed a family of
$p$-ary linear codes and demonstrated that they are $k$-optimal 2-LRCs in some
cases. Tan et al.[15] determined the locality of some known linear codes and
showed that many of these codes are $k$-optimal.

###  I-B Our Contributions and Techniques

In this paper, we focus on new constructions of $(2,\delta)$-LRCs. We follow
the construction of linear codes presented in [16]. This construction has been
applied to secret sharing schemes or LRCs by many researchers [13, 17]. It is
more intuitive to describe the properties of $(2,\delta)$-LRCs in the language
of finite geometry, this converts the analysis of locality into how many lines
pass through a point in projective geometry.

From the finite geometry point of view, we give a simple but useful sufficient
condition to guarantee a linear code to be a $(2,\delta)$-LRC (see Theorem 5).
We generalize some results proposed by Luo et al.[18] (see Theorems 6, 7 and
8) and Silberstein et al.[11] (see Theorem 10). In particular, we extend the
$p$-ary linear codes presented in [18] to the $q$-ary linear codes, where $p$
is a prime and $q$ is the power of $p$, and determine their locality in some
cases. Motivated by Silberstein’s work on $r$-LRCs, we utilize Krawtchouk
polynomials to determine the parameters of some punctured simplex codes.
Specifically speaking, if the punctured columns from the generator matrix of a
simplex code have certain weight, then determining the minimum distance of the
punctured simplex code is equivalent to determining the minimum value of
Krawtchouk polynomials. Then we construct two infinite families of $k$-optimal
$(2,q)$-LRCs. Our constructions are generalizations of the results of [11].
Moreover, all our new LRCs are $k$-optimal with respect to the generalized C-M
bound.

The rest of this paper is organized as follows. In Section II, we recall a
general construction of linear codes given by Ding et al.[16], and some basic
notation and results on finite geometry and Krawtchouk polynomials. In Section
III, we consider $(2,\delta)$-LRCs and present three infinite families of
$k$-optimal ($2,\delta$)-LRCs. Section IV concludes the paper.

##  II Preliminaries

###  II-A A General Construction of Linear Codes

In this subsection, we describe a general construction of linear code which
was given by Ding et al.[16]. Let $m$ be a positive integer, $q$ a power of
some prime $p$, $\mathbb{F}_{q}$ the finite field containing $q$ elements and
$\mathbb{F}_{q}^{m}$ the vector space over $\mathbb{F}_{q}$ of dimension $m$.
For any vector $\bm{x}$= $(x_{1},x_{2},\cdots,x_{m})\in\mathbb{F}_{q}^{m}$,
the Hamming weight of $\bm{x}$ is given as wt$(\bm{x})=|\\{1\leq i\leq
m:x_{i}\neq 0\\}|$. We let tr${}_{q^{m}/q}(\cdot)$ be the trace function from
$\mathbb{F}_{q^{m}}$ to $\mathbb{F}_{q}$ and tr$(\cdot)$ the absolute trace
function from $\mathbb{F}_{q}$ to $\mathbb{F}_{p}$.

Ding et al.[16] established a general construction of linear codes, which says
that if $D=\\{d_{1},...,d_{n}\\}$ is a nonempty subset of
$\mathbb{F}_{q^{m}}$, a $q$-ary linear code of length $n$ is constructed by

$C_{D}=\\{\bm{c}_{x}=(\text{tr}_{q^{m}/q}(xd_{1}),\cdots,\text{tr}_{q^{m}/q}(xd_{n})):x\in\mathbb{F}_{q^{m}}\\}.$
(3)

If $D=\\{\bm{d}_{1},\bm{d}_{2},\cdots,\bm{d}_{n}\\}$ is a nonempty subset of
$\mathbb{F}^{m}_{q}$, then the above construction (3) can be modified to

$C_{D}=\\{\bm{c_{x}}=(\bm{x\cdot d}_{1},...,\bm{x\cdot
d}_{n}):\bm{x}\in\mathbb{F}_{q}^{m}\\},$ (4)

where $\bm{x\cdot d}_{i}$ is the Euclidean inner product of $\bm{x}$ and
$\bm{d}_{i}$.

Using character sums over finite fields, we can compute the parameters of
those constructed codes. Assume that $\omega_{p}$ is the primitive
$p^{\text{th}}$ root of unity in the complex number field $\mathbb{C}$, then
for $a\in\mathbb{F}_{q}$, the additive character $\chi_{a}$ from
$\mathbb{F}_{q}$ to $\mathbb{F}_{p}$ is defined as
$\chi_{a}(c)=\omega_{p}^{\text{tr}(ac)},\text{for all }c\in\mathbb{F}_{q}.$ If
$a=0$, then $\sum_{c\in\mathbb{F}_{q}}\chi_{a}(c)=q$; otherwise
$\sum_{c\in\mathbb{F}_{q}}\chi_{a}(c)=0$ ([19]).

The following two bounds are useful in subsequent sections.

######  Lemma 1 ([20], Griesmer Bound).

Let $C$ be a $q$-ary $[n,k,d]$ linear code, then

$n\geq\sum_{i=0}^{k-1}\lceil\frac{d}{q^{i}}\rceil.$

A linear code achieving the Griesmer bound with equality is called a Griesmer
code.

######  Lemma 2 ([20], Plotkin Bound).

Let $C$ be a $q$-ary code with $M$ codewords, length $n$ and minimum distance
$d$. If $qd>(q-1)n$, then

$M\leq\frac{qd}{qd-(q-1)n}.$

###  II-B Finite Geometry

The projective space $PG(m-1,q)$ over $\mathbb{F}_{q}$ is the geometry whose
points, lines, planes, $\cdots$ , hyperplanes are the subspaces of
$\mathbb{F}^{m}_{q}$ of dimension $1,2,3,\cdots,m-1$. So, we also use a
nonzero vector $\bm{g}\in\mathbb{F}^{m}_{q}$ to denote the point in
$PG(m-1,q)$. Two nonzero vectors $\bm{g}_{1}$ and $\bm{g}_{2}$ are the same
point in $PG(m-1,q)$ if and only if $\bm{g}_{1}=\lambda\bm{g}_{2}$ for some
$\lambda\in\mathbb{F}^{*}_{q}$. Note that when we replace $\bm{g}_{i}$ by
$\lambda\bm{g}_{i}$ for some $\lambda\in\mathbb{F}^{*}_{q}$, the parameters of
the code given by Eq. (4) do not change. So we rewrite the code construction
given in Eq. (4) via the language of projective geometry as follows. Suppose
$D=\\{\bm{d}_{1},\bm{d}_{2},\cdots,\bm{d}_{n}\\}$ is a nonempty subset of
$PG(m-1,q)$, then a $q$-ary linear code of length $n$ is constructed by

$C_{D}=\\{\bm{c_{x}}=(\bm{x\cdot d}_{1},...,\bm{x\cdot
d}_{n}):\bm{x}\in\mathbb{F}_{q}^{m}\\}.$ (5)

In this paper, we will use Eq. (5) to construct optimal LRCs. Note that when
$D=PG(m-1,q)$, $C_{D}$ is the famous simplex code. Thus in this sense, for
general nonempty subset $D$, the code $C_{D}$ is the punctured code of the
simplex code.

We let the points in $PG(m-1,q)$ be the vectors in $\mathbb{F}_{q}^{m}$ that
the first nonzero coordinate is 1 for simplicity. If $A$ is a nonempty subset
of $[m]$, we let $P_{[m]}=PG(m-1,q)$ and $P_{A}$ be the subset of $PG(m-1,q)$
that the coordinates outside of $A$ are 0. It is easy to see that
$|P_{A}|=\frac{q^{|A|}-1}{q-1},\bigcup_{\alpha\in\mathbb{F}_{q}^{*}}\alpha
P_{A}=L_{A}^{*}$ where $\alpha P_{A}=\\{\alpha\bm{a}:\bm{a}\in P_{A}\\}$ and

$L_{A}=\\{(a_{1},...,a_{m})\in\mathbb{F}_{q}^{m}:a_{i}=0\text{ if }i\notin
A\\}.$ (6)

For any two subsets $A_{1},A_{2}$ of $[m]$, the intersection of $P_{A_{1}}$
and $P_{A_{2}}$ is equal to $P_{A_{1}\cap A_{2}}$, where
$P_{\varnothing}=\varnothing.$

###  II-C Krawtchouk Polynomials

In this subsection, we briefly review some basic results of Krawtchouk
polynomials.

Given positive integers $n,q$, and suppose $0\leq k\leq n$, the Krawtchouk
polynomial of degree $k$ is defined as[20]

$K_{k}(x;n,q)=K_{k}(x)=\sum_{j=0}^{k}(-1)^{j}\binom{x}{j}\binom{n-x}{k-j}(q-1)^{k-j}.$

The following lemma is a slight modification of [20, Lemma(5.3.1)].

######  Lemma 3 ([20], Lemma(5.3.1)).

Let a and s be positive integers and $\bm{x}$ be a vector of length $m$ over
$\mathbb{F}_{q}$ with wt$(\bm{x})=a$. Then we have

$\sum_{\bm{y}\in\mathbb{F}_{q}^{m},\text{wt}(\bm{y})=s}\omega_{p}^{\text{tr}(\bm{x}\cdot\bm{y})}=K_{s}(a;m,q).$

##  III $(2,\delta)$-LRCs from Punctured Simplex Codes

In this section, we will provide several constructions of LRCs via punctured
simplex codes. Firstly, we give a simple lemma which will be used to determine
the locality of linear codes.

######  Lemma 4.

Let $\delta\geq 2$ be an integer, $\bm{g}_{1},\cdots,\bm{g}_{\delta+1}$ be
$\delta+1$ distinct collinear points in $PG(m-1,q)$. Let $C$ be the linear
code with the generator matrix $G=[\bm{g}_{1}\ ...\ \bm{g}_{\delta+1}]$, then
$C$ is a $q$-ary $[\delta+1,2,\delta]$-MDS code.

###### Proof.

Since any two of $\bm{g}_{1},\cdots,\bm{g}_{\delta+1}$ are linearly
independent and any three of $\bm{g}_{1},\cdots,\bm{g}_{\delta+1}$ are
linearly dependent, we have $rank(G)=2$. Thus $\dim(C)=2$ and
$\dim(C^{\perp})=\delta-1$. On the other hand, $G$ is the parity-check matrix
of $C^{\perp}$, thus $d(C^{\perp})\geq 3$. By the Singleton bound,
$d(C^{\perp})\leq\delta+1-(\delta-1)+1=3$, hence $C^{\perp}$ is a
$[\delta+1,\delta-1,3]$-MDS code. So $C$ is a $[\delta+1,2,\delta]$-MDS code.
∎

In the following, we give a sufficient condition which guarantees that a
punctured simplex code is a $(2,\delta)$-LRC.

######  Theorem 5.

Suppose $2\leq\delta\leq q$ and $D$ is a subset of $PG(m-1,q)$. If
$|D|\leq\frac{q^{m-1}-1}{q-1}(q+1-\delta)-1$, then the code $C_{D^{c}}$ given
in Eq. (5) is a $q$-ary $(2,\delta)$-LRC, where $D^{c}=PG(m-1,q)\setminus D$.

###### Proof.

For any point $\bm{g}\in D^{c}$, there are $\frac{q^{m-1}-1}{q-1}$ lines in
$PG(m-1,q)$ containing $\bm{g}$, and each line has $q+1$ points. Since
$|D|\leq\frac{q^{m-1}-1}{q-1}(q+1-\delta)-1$, by the Pigeonhole Principle,
there exists at least one line $L$ containing $\bm{g}$, such that there are
$\delta+1$ points $\bm{g}_{1}=\bm{g},\bm{g}_{2},\cdots,\bm{g}_{\delta+1}$ of
$L$ belonging to the subset $D^{c}$. By Lemma 4, $d((C_{D^{c}})_{|E})=\delta$,
where $E=\\{\bm{g}_{1},\bm{g}_{2},\cdots,\bm{g}_{\delta+1}\\}$. Hence the code
$C_{D^{c}}$ has $(2,\delta)$-locality. ∎

######  Remark.

When $D=\varnothing$, then $C_{D^{c}}$ is the $q$-ary simplex code. From
Theorem 5, we know that the $q$-ary simplex codes have locality $(2,q)$. In
particular, to ensure the code $C_{D^{c}}$ to be a $2$-LRC, it only needs to
satisfy that $|D|\leq q^{m-1}-2$. Thus our method is simpler than that in
[18].

Hyun et al.[14] constructed infinite families of binary Griesmer codes
punctured by unions of projective spaces, and Luo et al.[18] obtained similar
results of linear codes over $\mathbb{F}_{p}$. In the following, we extend
their results to general $q$-ary codes.

######  Theorem 6.

Let $m,t>1$ be positive integers. Assume that $A_{1},...,A_{t}$ are nonempty
subsets of $[m]$ satisfying $A_{i}\cap A_{j}=\varnothing$ for any $i\neq
j\in[t].$ Let $D=\cup_{i=1}^{t}P_{A_{i}}$ and $D^{c}=P_{[m]}\backslash D$,
then the code $C_{D^{c}}$ defined by Eq. (5) is a $q$-ary linear code with
parameters
$[\frac{q^{m}-1}{q-1}-\frac{\sum_{i=1}^{t}q^{|A_{i}|}-t}{q-1},m,q^{m-1}-\sum_{i=1}^{t}q^{|A_{i}|-1}]$.
Furthermore, assume that
$|A_{1}|=...=|A_{i_{1}}|=s_{1},|A_{i_{1}+1}|=...=|A_{i_{2}}|=s_{2},...,|A_{i_{u-1}+1}|=...=|A_{i_{u}}|=s_{u}$
where $s_{1}<s_{2}<...<s_{u}$. If
$\max\\{i_{1},i_{2}-i_{1},...,i_{u}-i_{u-1}\\}\leq q-1$, then $C_{D^{c}}$ is a
Griesmer code.

###### Proof.

Note that $P_{A_{i}}\cap P_{A_{j}}=P_{A_{i}\cap A_{j}}=\varnothing$ for any
$i\neq j\in[t]$, so we have
$|D|=\sum_{i=1}^{t}|P_{A_{i}}|=\frac{\sum_{i=1}^{t}q^{|A_{i}|}-t}{q-1}$, thus
the length of $C_{D^{c}}$ is
$\frac{q^{m}-1}{q-1}-\frac{\sum_{i=1}^{t}q^{|A_{i}|}-t}{q-1}$.

Let $\bm{x}=(x_{1},...,x_{m})$ be any nonzero vector of $\mathbb{F}_{q}^{m}$,
then

$\displaystyle\text{wt}(\bm{c_{x}})$ $\displaystyle=|D^{c}|-|\\{\bm{d}\in
D^{c}|\bm{x\cdot d=0}\\}|$ $\displaystyle=|D^{c}|-\sum_{\bm{d}\in
D^{c}}\frac{1}{q}\sum_{y\in\mathbb{F}_{q}}\omega_{p}^{\text{tr}(y\bm{x\cdot
d})}$ $\displaystyle=\frac{q-1}{q}|D^{c}|-\frac{1}{q}\sum_{\bm{d}\in
D^{c}}\sum_{y\in\mathbb{F}_{q}^{*}}\omega_{p}^{\text{tr}(y\bm{x\cdot d})}$
$\displaystyle=\frac{q-1}{q}|D^{c}|-\frac{1}{q}\sum_{\bm{d}\in{\mathbb{F}_{q}^{m}}^{*}}\omega_{p}^{\text{tr}(\bm{x\cdot
d})}+\frac{1}{q}\sum_{\bm{d}\in
D}\sum_{y\in\mathbb{F}_{q}^{*}}\omega_{p}^{\text{tr}(y\bm{x\cdot d})}.$ (7)

Note that

$\displaystyle\sum_{\bm{d}\in{\mathbb{F}_{q}^{m}}^{*}}\omega_{p}^{\text{tr}(\bm{x\cdot
d})}$
$\displaystyle=\sum_{d_{1}\in\mathbb{F}_{q}}\cdots\sum_{d_{m}\in\mathbb{F}_{q}}\omega_{p}^{\text{tr}(x_{1}d_{1})}\cdots\omega_{p}^{\text{tr}(x_{m}d_{m})}-1$
$\displaystyle=\prod_{i=1}^{m}\left(\sum_{d_{i}\in\mathbb{F}_{q}}\omega_{p}^{\text{tr}(x_{i}d_{i})}\right)-1=-1,$

where $\bm{d}=(d_{1},...,d_{m})$ and

$\displaystyle\sum_{\bm{d}\in
D}\sum_{y\in\mathbb{F}_{q}^{*}}\omega_{p}^{\text{tr}(y\bm{x\cdot d})}$
$\displaystyle=\sum_{i=1}^{t}\sum_{\bm{d}\in
P_{A_{i}}}\sum_{y\in\mathbb{F}_{q}^{*}}\omega_{p}^{\text{tr}(\bm{x\cdot}(y\bm{d}))}$
$\displaystyle=\sum_{i=1}^{t}\sum_{\bm{d}\in{\mathbb{F}_{q}^{|A_{i}|}}^{*}}\omega_{p}^{\text{tr}(\bm{x}_{A_{i}}\cdot\bm{d})}.$

As

$\displaystyle\sum_{\bm{d}\in{\mathbb{F}_{q}^{|A_{i}|}}^{*}}\omega_{p}^{\text{tr}(\bm{x}_{A_{i}}\cdot\bm{d})}=\begin{cases}q^{|A_{i}|}-1,\bm{x}_{A_{i}}=\bm{0}\\\
-1,\bm{x}_{A_{i}}\neq\bm{0}\end{cases}$

for $1\leq i\leq t$, then the minimum weight is
$\min\limits_{\bm{x}\in{\mathbb{F}_{q}^{m}}^{*}}\text{wt}(\bm{c_{x}})=\frac{q-1}{q}|D^{c}|+\frac{1}{q}-\frac{t}{q}=q^{m-1}-\sum\limits_{i=1}^{t}q^{|A_{i}|-1}$.
It is easy to prove that $q^{m}-\sum_{i=1}^{t}q^{|A_{i}|}>0$ since
$\sum_{i=1}^{t}|A_{i}|\leq m$. Thus wt$(\bm{c_{x}})=0$ if and only if
$\bm{x}=\bm{0}$, hence the dimension is $m$.

Suppose $\sum_{i=1}^{t}q^{|A_{i}|-1}=\sum_{i=g}^{h}b_{i}q^{i}$, where $0\leq
b_{i}\leq q-1,i=g,...,h$. Then

$\displaystyle\sum_{i=0}^{m-1}\left\lceil\frac{q^{m-1}-\sum_{j=1}^{t}q^{|A_{j}|-1}}{q^{i}}\right\rceil=\sum_{i=0}^{m-1}\left\lceil\frac{q^{m-1}-\sum_{j=g}^{h}b_{j}q^{j}}{q^{i}}\right\rceil$
$\displaystyle=\sum_{i=0}^{m-1}q^{m-1-i}-\sum_{i=0}^{g}\sum_{j=g}^{h}b_{j}q^{j-i}-\sum_{i=g+1}^{h}\sum_{j=i}^{h}b_{i}q^{j-i}$
$\displaystyle=\frac{q^{m}-1}{q-1}-\frac{\sum_{i=1}^{t}q^{|A_{i}|}-\sum_{i=g}^{h}b_{i}}{q-1}.$

As $\max\\{i_{1},i_{2}-i_{1},...,i_{u}-i_{u-1}\\}\leq
q-1,\sum_{i=g}^{h}b_{i}=i_{1}+i_{2}-i_{1}+...+i_{u}-i_{u-1}=i_{u}=t.$ The
length of $C_{D^{c}}$ is
$\frac{q^{m}-1}{q-1}-|D|=\frac{q^{m}-1}{q-1}-\frac{\sum_{i=1}^{t}q^{|A_{i}|}-\sum_{i=g}^{h}b_{i}}{q-1},$
hence the code $C_{D^{c}}$ is a Griesmer code. ∎

We now investigate the locality of the codes given in Theorem 6.

######  Theorem 7.

Keep the notation as in Theorem 6. If $t=2$ and $|A_{i}|\leq m-2$ for all
$i\in[t]$, then the code $C_{D^{c}}$ has locality $(2,q)$; if $t\geq 3$ and
$m\geq 4$, then the code $C_{D^{c}}$ has locality $(2,q)$; if $m>t=2,q>2$ and
$|A_{1}|=m-1$, then the code $C_{D^{c}}$ has locality $(2,q-1)$.

###### Proof.

Case 1: $t=2,|A_{i}|\leq m-2,i=1,2.$ If $m\geq 4$, then
$|D|=\frac{q^{|A_{1}|}+q^{|A_{2}|}-2}{q-1}\leq\frac{q^{2}+q^{m-2}-2}{q-1}\leq\frac{q^{m-1}-q}{q-1}$;
if $m=3$, then
$|D|=\frac{q^{|A_{1}|}+q^{|A_{2}|}-2}{q-1}=2\leq\frac{q^{2}-q}{q-1}$. By
Theorem 5, we can deduce that the code $C_{D^{c}}$ has locality $(2,q)$.

Case 2: $m>3$ and $t>2$. Note that
$|D|=\frac{\sum_{i=1}^{t}q^{|A_{i}|}-t}{q-1}\leq\frac{q^{m-t+1}+(t-1)q-t}{q-1}=\frac{q^{m-t+1}+t(q-1)-q}{q-1}\leq\frac{q^{m-t+1}+m(q-1)-q}{q-1}\leq\frac{q^{m-2}+q^{m-2}(q-1)-q}{q-1}=\frac{q^{m-1}-q}{q-1}$.
By Theorem 5, we can deduce that the code $C_{D^{c}}$ has locality $(2,q)$.

Case 3: $m>t=2,|A_{1}|=m-1,|A_{2}|=1,q>2$. Note that
$|D|=\frac{q^{m-1}+q-2}{q-1}\leq\frac{2q^{m-1}-2}{q-1}-1$. By Theorem 5, we
can deduce that the code $C_{D^{c}}$ has locality $(2,q-1)$. ∎

######  Theorem 8.

Keep the notation as in Theorems 6 and 7, the code $C_{D^{c}}$ is $k$-optimal
LRC with respect to the bound (2).

###### Proof.

Case 1: $t=2,|A_{i}|\leq m-2,i=1,2$. We let
$n^{\prime}=\frac{q^{m}-1}{q-1}-\frac{q^{|A_{1}|}+q^{|A_{2}|}-2}{q-1}-q-1,d=q^{m-1}-q^{|A_{1}|-1}-q^{|A_{2}|-1}$,
according to the Plotkin bound, we have

$\displaystyle k_{opt}^{(q)}(n^{\prime},d)$
$\displaystyle\leq\left\lfloor\log_{q}\frac{q(q^{m-1}-q^{|A_{1}|-1}-q^{|A_{2}|-1})}{q^{2}-2}\right\rfloor$
$\displaystyle\leq\left\lfloor\log_{q}(q^{m-1}-q^{|A_{1}|-1}-q^{|A_{2}|-1})\right\rfloor$
$\displaystyle\leq m-2.$

Utilizing the bound (2) with $s=1$, we obtain that $k\leq
2+k_{opt}^{(q)}(n^{\prime},d)\leq m$. Therefore, the code $C_{D^{c}}$ is
$k$-optimal.

Case 2: $m>3$ and $t>2$. The Griesmer code $C_{D^{c}}$ has parameters
$[n=\frac{q^{m}-\sum_{i=1}^{t}q^{|A_{i}|}+t-1}{q-1},k=m,d=q^{m-1}-\sum_{i=1}^{t}q^{|A_{i}|-1}]$.
When $q>2$, we have
$\left\lceil\frac{q^{m-1}-\sum_{i=1}^{t}q^{|A_{i}|-1}}{q^{m-2}}\right\rceil\geq\left\lceil
q-\frac{t-1+q^{m-t}}{q^{m-2}}\right\rceil\geq\left\lceil
q-\frac{m-1+q^{m-3}}{q^{m-2}}\right\rceil=q$ and
$\left\lceil\frac{q^{m-1}-\sum_{i=1}^{t}q^{|A_{i}|-1}}{q^{m-1}}\right\rceil=1$.
So we have

$n-1=\sum_{i=0}^{m-2}\left\lceil\frac{d}{q^{i}}\right\rceil,n-q-1\geq\sum_{i=0}^{m-3}\left\lceil\frac{d}{q^{i}}\right\rceil.$

Using the Griesmer bound, we obtain that $k_{opt}^{(q)}(n-1-q,d)\leq m-2$,
thus $k\leq 2+k_{opt}^{(q)}(n-1-q,d)\leq m$ and the code $C_{D^{c}}$ is
$k$-optimal. When $q=2$, since $A_{1},...,A_{t}$ are mutually disjoint and
$\max\\{i_{1},i_{2}-i_{1},...,i_{u}-i_{u-1}\\}\leq 1,$ we obtain that
$\left\lceil\frac{2^{m-1}-\sum_{i=1}^{t}2^{|A_{i}|-1}}{2^{m-2}}\right\rceil\geq
2$. According to the similar arguments, $k\leq 2+k_{opt}^{(q)}(n-1-q,d)\leq m$
and the code $C_{D^{c}}$ is $k$-optimal.

Case 3: $m>t=2,|A_{1}|=m-1,|A_{2}|=1,q>2$. We let
$n^{\prime}=\frac{q^{m}-1}{q-1}-\frac{q^{m-1}+q-2}{q-1}-q,d=q^{m-1}-q^{m-2}-1$,
according to the Plotkin bound, we have

$\displaystyle k_{opt}^{(q)}(n^{\prime},d)$
$\displaystyle\leq\left\lfloor\log_{q}\frac{q(q^{m-1}-q^{m-2}-1)}{q^{2}-q-1}\right\rfloor$
$\displaystyle\leq\left\lfloor\log_{q}(q^{m-1}-q^{m-2}-1)\right\rfloor$
$\displaystyle\leq m-2.$

Utilizing the bound (2) with $s=1$, we obtain that $k\leq
2+k_{opt}^{(q)}(n^{\prime},d)\leq m$. Therefore, the code $C_{D^{c}}$ is
$k$-optimal. ∎

######  Example.

Let $q=4,m=3$ and $A_{1}=\\{1\\},A_{2}=\\{2,3\\}$, then $C_{D^{c}}$ defined in
Theorem 6 is a 4-ary Griesmer code $[15,3,11]$ with a generator matrix
$G=(G_{1}\ G_{2})$, where $G_{1}=\begin{pmatrix}1&1&1&1&1&1&1\\\
1&\alpha&\alpha+1&0&1&\alpha&\alpha+1\\\
0&0&0&1&1&1&1\end{pmatrix},G_{2}=\begin{pmatrix}1&1&1&1&1&1&1&1\\\
0&1&\alpha&\alpha+1&0&1&\alpha&\alpha+1\\\
\alpha&\alpha&\alpha&\alpha&\alpha+1&\alpha+1&\alpha+1&\alpha+1\end{pmatrix}$
and $\alpha$ is a primitive element in $\mathbb{F}_{4}$. Then $C_{D^{c}}$ is a
$(2,3)$-LRC. For instance, one can see that the columns
$(1,1,0)^{T},(1,0,1)^{T},(1,\alpha,\alpha+1)^{T},(1,\alpha+1,\alpha)^{T}$ of
$G$ generate a $[4,2,3]$-code. Hence the first symbol of $C_{D^{c}}$ has
locality $(2,3)$.

Note that $k^{(4)}_{opt}(11,11)=1$, thus $C_{D^{c}}$ attains the generalized
C-M bound (2).

In the following, we consider another family of punctured simplex codes, which
is motivated by[11, Theorem 10].

######  Theorem 9.

Let $A\subseteq[m],|A|=s\geq 3,D=\\{\bm{d}\in
P_{A}:\text{wt}(\bm{d})=2\\},D^{c}=P_{[m]}\backslash D$, then the code
$C_{D^{c}}$ defined in Eq. (5) is a $q$-ary $k$-optimal $(2,q)$-LRC with
parameters
$[n,k,d]=\left[\frac{q^{m}-1}{q-1}-(q-1)\binom{s}{2},m,q^{m-1}-\left\lfloor\frac{(2(s-1)(q-1)+q)^{2}}{8q}\right\rfloor\right]$
providing that $\binom{s}{2}(q-1)\leq\frac{q^{m-1}-q}{q-1}$ and
$0<\frac{qd}{qd-(q-1)(n-q-1)}<q^{m-1}$.

###### Proof.

There are $(q-1)^{2}\binom{s}{2}$ vectors in $L_{A}$ with Hamming weight 2, so
$|D|=(q-1)\binom{s}{2}$ since $\text{wt}(\bm{a})=\text{wt}(\lambda\bm{a})$ if
and only if $\lambda\in\mathbb{F}_{q}^{*}$.

$\displaystyle\sum_{\bm{d}\in
D}\sum_{y\in\mathbb{F}_{q}^{*}}\omega_{p}^{\text{tr}(y\bm{x\cdot d})}$
$\displaystyle=\sum_{\bm{d}\in\mathbb{F}_{q}^{s},\text{wt}(\bm{d})=2}\omega_{p}^{\text{tr}(\bm{x}_{A}\cdot\bm{d})}$
$\displaystyle=K_{2}(a;s,q)$
$\displaystyle=\frac{q^{2}}{2}a^{2}-\left(\frac{2(q-1)qs+q(2-q)}{2}\right)a$
$\displaystyle\ \ \ \ \ \ \ \ +\binom{s}{2}(q-1)^{2}.$

Thus the minimum weight of $C_{D^{c}}$ corresponding to $\bm{x}$ is

$\displaystyle\min_{\bm{x}\in{\mathbb{F}_{q}^{m}}^{*}}\text{wt}(\bm{c_{x}})=\left\lceil
q^{m-1}-\frac{(q-1)^{2}}{q}\binom{s}{2}-\frac{4s(q-1)+(q-2)^{2}}{8q}\right\rceil$
$\displaystyle=q^{m-1}-\left\lfloor\frac{(q-1)^{2}}{q}\binom{s}{2}+\frac{4s(q-1)+(q-2)^{2}}{8q}\right\rfloor$
$\displaystyle=q^{m-1}-\left\lfloor\frac{(2(s-1)(q-1)+q)^{2}}{8q}\right\rfloor$

according to the Eq. $(\ref{calcu_min_weight}).$

According to Theorem 5, the code has locality $(2,q)$. Using the Plotkin
bound, we obtain that

$\displaystyle k_{opt}^{(q)}(n-q-1,d)$
$\displaystyle\leq\left\lfloor\log_{q}\frac{qd}{qd-(q-1)(n-q-1)}\right\rfloor$
$\displaystyle\leq m-2.$ (8)

Thus the code $C_{D^{c}}$ is a $k$-optimal $(2,q)$-LRC according to the
generalized C-M bound (2). ∎

######  Remark.

By the techniques of graph theory, the authors in [11, Theorem 10] have
obtained these codes as 2-LRCs. And they only proved that these codes are
$k$-optimal 2-LRCs for $s=3,m\geq 3,2\leq q\leq 14$. However, in Theorem 9, we
prove that all the codes in [11, Theorem 10] are actually $k$-optimal
$(2,q)$-LRCs.

######  Theorem 10.

Let $A_{1},A_{2},...,A_{t}\subseteq[m],|A_{i}|=s_{i}\geq 3$ for
$i\in[t],D_{i}=\\{\bm{d}\in
P_{A_{i}}|\text{wt}(\bm{x})=2\\},D=\bigcup_{i\in[t]}D_{i},D^{c}=P_{[m]}\backslash
D$. If $|A_{i}\cap A_{j}|\leq 1$ for all $i\neq j\in[t]$, and
$(q-1)\sum_{i=1}^{t}\binom{s_{i}}{2}\leq\frac{q^{m-1}-q}{q-1}$, then the code
$C_{D^{c}}$ defined in (4) is a $q$-ary $k$-optimal $(2,q)$-LRC with
parameters

$[n,k,d]=\left[\frac{q^{m}-1}{q-1}-(q-1)\sum_{i=1}^{t}\binom{s_{i}}{2},m,q^{m-1}-\Delta\right]$

providing that $0<\frac{qd}{qd-(q-1)(n-q-1)}<q^{m-1}$ where
$\Delta=\left\lfloor\sum_{i=1}^{t}\frac{(2(s_{i}-1)(q-1)+q)^{2}}{8q}\right\rfloor$.

###### Proof.

For all $i\neq j\in[t]$, $D_{i}\cap D_{j}=\\{\bm{d}\in P_{A_{i}\cap
A_{j}}|\text{wt}(\bm{d})=2\\}=\varnothing$ since $|A_{i}\cap A_{j}|\leq 1$.
$|D|=\sum_{i=1}^{t}|D_{i}|=(q-1)\sum_{i=1}^{t}\binom{s_{i}}{2}$.

$\displaystyle\sum_{\bm{d}\in
D}\sum_{y\in\mathbb{F}_{q}^{*}}\omega_{p}^{\text{tr}(y\bm{d\cdot x})}$
$\displaystyle=\sum_{i=1}^{t}\sum_{\bm{d}\in
D_{i}}\sum_{y\in\mathbb{F}_{q}^{*}}\omega_{p}^{\text{tr}(y\bm{d\cdot x})}$
$\displaystyle=\sum_{i=1}^{t}\sum_{\bm{d}\in\mathbb{F}_{q}^{s_{i}},\text{wt}(\bm{d})=2}\omega_{p}^{\text{tr}(\bm{x}_{A_{i}}\cdot\bm{d})}$
$\displaystyle=K_{2}(w_{1};s_{1},q)+...+K_{2}(w_{t};s_{t},q)$

where $w_{i}=\text{wt}(\bm{x}_{A_{i}})$. Thus the weight of a codeword
corresponding to some nonzero $\bm{x}$ is

$\displaystyle\text{wt}(\bm{c_{x}})$
$\displaystyle=\left(\frac{q^{m}-1}{q-1}-(q-1)\sum_{i=1}^{t}\binom{s_{i}}{2}\right)\frac{q-1}{q}$
$\displaystyle+\frac{1}{q}+\frac{1}{q}\sum_{i=1}^{t}K_{2}(w_{i};s_{i},q)$
$\displaystyle=q^{m-1}-\frac{(q-1)^{2}}{q}\sum_{i=1}^{t}\binom{s_{i}}{2}+\frac{1}{q}\sum_{i=1}^{t}K_{2}(w_{i};s_{i},q).$

Note that the axis of symmetry of $K_{2}(w_{i};s_{i},q)$ is
$\frac{2(q-1)s_{i}+2-q}{2q}=\frac{1}{q}(1-s_{i})+s_{i}-\frac{1}{2}\geq\frac{s_{i}}{2}>1$
for all prime power $q$, thus $w_{i}\geq 1$ when $K_{2}(w_{i};s_{i},q)$ get
the minimum value. Meanwhile, $|A_{i}\cap A_{j}|\leq 1$ for all $i\neq
j\in[t]$, so $K_{2}(w_{i};s_{i},q)$ get the minimum value simultaneously for
all $i\in[t]$. The minimum weight of $\bm{c_{x}}$ is

$\displaystyle\min_{\bm{x}\in{\mathbb{F}_{q}^{m}}^{*}}\text{wt}(\bm{c_{x}})$
$\displaystyle=\left\lceil
q^{m-1}-\frac{(q-1)^{2}}{q}\sum_{i=1}^{t}\binom{s_{i}}{2}\right.$
$\displaystyle\left.\ \ \ \ \ \ \ \
-\sum_{i=1}^{t}\frac{4s_{i}(q-1)+(q-2)^{2}}{8q}\right\rceil$
$\displaystyle=q^{m-1}-\left\lfloor\sum_{i=1}^{t}\frac{(2(s_{i}-1)(q-1)+q)^{2}}{8q}\right\rfloor.$

According to Theorem 5, the code has locality $(2,q)$. Using the Plotkin
bound, we obtain that

$\displaystyle k_{opt}^{(q)}(n-q-1,d)$
$\displaystyle\leq\left\lfloor\log_{q}\frac{qd}{qd-(q-1)(n-q-1)}\right\rfloor$
$\displaystyle\leq m-2.$

The code $C_{D^{c}}$ is a $k$-optimal $(2,q)$-LRC according to (2). ∎

######  Example.

Let $q=2,m=5,A_{1}=\\{1,2,3\\}$ and $A_{2}=\\{3,4,5\\}$. By the SageMath
software, the binary code $C_{D^{c}}$ defined in Theorem 10 has parameters
$[25,5,12]$ and the generator matrix is $G=(G_{1}\ G_{2})$ where
$G_{1}=\setcounter{MaxMatrixCols}{12}\begin{pmatrix}1&0&0&1&0&1&0&1&1&0&1&0\\\
0&1&0&1&0&0&1&1&0&1&1&0\\\ 0&0&1&1&0&0&0&0&1&1&1&0\\\
0&0&0&0&1&1&1&1&1&1&1&0\\\
0&0&0&0&0&0&0&0&0&0&0&1\end{pmatrix},G_{2}=\setcounter{MaxMatrixCols}{13}\begin{pmatrix}1&0&1&1&0&1&0&0&1&0&1&0&1\\\
0&1&1&0&1&1&0&1&1&0&0&1&1\\\ 0&0&0&1&1&1&0&0&0&1&1&1&1\\\
0&0&0&0&0&0&1&1&1&1&1&1&1\\\ 1&1&1&1&1&1&1&1&1&1&1&1&1\end{pmatrix}.$ By the
Plotkin bound, $k^{(2)}_{opt}(22,12)\leq\lfloor\log_{2}12\rfloor=3$. Hence
$C_{D^{c}}$ is a $k$-optimal 2-LRC achieving the C-M bound.

##  IV Concluding Remarks

In this paper, we have investigated new constructions of optimal
$(2,\delta)$-LRCs via punctured simplex codes. By using the language of finite
geometry, we propose a simple but useful condition to ensure that a linear
code has $(2,\delta)$-locality. According to some characteristic sums and
Krawtchouk polynomials, we obtain several infinite families of $q$-ary
$(2,\delta)$-LRCs. All these codes are optimal with respect to the generalized
C-M bound. We not only generalize some previous results of 2-LRCs to the
$(2,\delta)$-LRCs, but also construct some new optimal $(2,\delta)$-LRCs which
are not optimal in the sense of 2-LRCs.

It is interesting to find more new optimal $(2,\delta)$-LRCs and generalize
these results to the $(r,\delta)$-LRCs with $r\geq 3$ in the future.

## References

  * [1] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the locality of codeword symbols,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 11, pp. 6925–6934, 2012.
  * [2] N. Prakash, G. M. Kamath, V. Lalitha, and P. V. Kumar, “Optimal linear codes with a local-error-correction property,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , 2012, pp. 2776–2780.
  * [3] L. Jin, “Explicit construction of optimal locally recoverable codes of distance 5 and 6 via binary constant weight codes,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 8, pp. 4658–4663, 2019.
  * [4] I. Tamo and A. Barg, “A family of optimal locally recoverable codes,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 8, pp. 4661–4676, 2014.
  * [5] G. Luo, M. F. Ezerman, and S. Ling, “Three new constructions of optimal locally repairable codes from matrix-product codes,” _IEEE Trans. Inf. Theory_ , vol. 69, no. 1, pp. 75–85, 2023.
  * [6] B. Chen, W. Fang, S.-T. Xia, J. Hao, and F.-W. Fu, “Improved bounds and singleton-optimal constructions of locally repairable codes with minimum distance 5 and 6,” _IEEE Trans. Inf. Theory_ , vol. 67, no. 1, pp. 217–231, 2021.
  * [7] W. Fang, B. Chen, S.-T. Xia, and F.-W. Fu, “Singleton-optimal lrcs and perfect lrcs via cyclic codes,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , 2021, pp. 3261–3266.
  * [8] ——, “Bounds and constructions of singleton-optimal locally repairable codes with small localities,” _arXiv preprint arXiv:2207.05479_ , 2022.
  * [9] V. R. Cadambe and A. Mazumdar, “Bounds on the size of locally recoverable codes,” _IEEE Trans. Inf. Theory_ , vol. 61, no. 11, pp. 5787–5794, 2015\.
  * [10] A. S. Rawat, A. Mazumdar, and S. Vishwanath, “Cooperative local repair in distributed storage,” _EURASIP Journal on Advances in Signal Processing_ , vol. 2015, no. 1, pp. 1–17, 2015.
  * [11] N. Silberstein and A. Zeh, “Anticode-based locally repairable codes with high availability,” _Des. Codes Cryptogr._ , vol. 86, no. 2, pp. 419–445, 2018\.
  * [12] ——, “Optimal binary locally repairable codes via anticodes,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , 2015, pp. 1247–1251.
  * [13] G. Luo and X. Cao, “Constructions of optimal binary locally recoverable codes via a general construction of linear codes,” _IEEE Trans. Commun._ , vol. 69, no. 8, pp. 4987–4997, 2021.
  * [14] J. Y. Hyun, J. Lee, and Y. Lee, “Infinite families of optimal linear codes constructed from simplicial complexes,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 11, pp. 6762–6773, 2020.
  * [15] P. Tan, C. Fan, C. Ding, C. Tang, and Z. Zhou, “The minimum locality of linear codes,” _Des. Codes Cryptogr._ , pp. 1–32, 2022.
  * [16] C. Ding and H. Niederreiter, “Cyclotomic linear codes of order $3$,” _IEEE Trans. Inf. Theory_ , vol. 53, no. 6, pp. 2274–2277, 2007.
  * [17] K. Ding and C. Ding, “A class of two-weight and three-weight codes and their applications in secret sharing,” _IEEE Trans. Inf. Theory_ , vol. 61, no. 11, pp. 5835–5842, 2015.
  * [18] G. Luo and S. Ling, “Application of optimal $p$-ary linear codes to alphabet-optimal locally repairable codes,” _Des. Codes Cryptogr._ , vol. 90, no. 5, pp. 1271–1287, 2022.
  * [19] R. Lidl and H. Niederreiter, _Introduction to Finite Fields and Their Applications_. Cambridge university press, 1994.
  * [20] J. H. Van Lint, _Introduction to Coding Theory_. Springer Science & Business Media, 1998.