# The minimum linear locality of linear codes

Pan Tan, Cuiling Fan, Cunsheng Ding and Zhengchun Zhou P. Tan, C. Fan, and Z.
Zhou are with the School of Mathematics, Southwest Jiaotong University,
Chengdu, 611756, China. E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Ding is with the Department of Computer
Science and Engineering, The Hong Kong University of Science and Technology,
Clear Water Bay, Kowloon, Hong Kong, China (email<EMAIL_ADDRESS>
###### Abstract

Locally recoverable codes (LRCs) were proposed for the recovery of data in
distributed and cloud storage systems about nine years ago. A lot of progress
on the study of LRCs has been made by now. However, there is a lack of general
theory on the minimum linear locality of linear codes. In addition, the
minimum linear locality of many known families of linear codes is not studied
in the literature. Motivated by these two facts, this paper develops some
general theory about the minimum linear locality of linear codes, and
investigates the minimum linear locality of a number of families of linear
codes, such as $q$-ary Hamming codes, $q$-ary Simplex codes, generalized Reed-
Muller codes, ovoid codes, maximum arc codes, the extended hyperoval codes,
and near MDS codes. Many classes of both distance-optimal and dimension-
optimal LRCs are presented in this paper. The minimum linear locality of many
families of linear codes are settled with the general theory developed in this
paper.

###### Index Terms:

Cyclic code, linear code, locally recoverable code, near MDS code, punctured
code, shortened code.

##  I Introduction of motivations, objectives and methodology

Throughout this paper, let $n$ be a positive integer and let $q$ be a prime
power. An $[n,k,d]$ code ${\mathcal{C}}$ over ${\mathrm{GF}}(q)$ is a
$k$-dimensional subspace of ${\mathrm{GF}}(q)^{n}$ with Hamming distance $d$.
We use $A_{i}({\mathcal{C}})$ or $A_{i}$, $\dim({\mathcal{C}})$,
$d({\mathcal{C}})$ and ${\mathcal{C}}^{\perp}$ to denote the number of
codewords of Hamming weight $i$ in ${\mathcal{C}}$, the dimension of
${\mathcal{C}}$, the minimum Hamming distance of ${\mathcal{C}}$, and the dual
of ${\mathcal{C}}$. The weight distribution and weight enumerator of
${\mathcal{C}}$ are defined by the sequence $(A_{0},\ldots,A_{n})$ and the
polynomial $\sum_{i=0}^{n}A_{i}z^{i}$, respectively. ${\mathcal{C}}$ is said
to be a $t$-weight code if the sequence $(A_{1},\ldots,A_{n})$ has Hamming
weight $t$.

Denote $[n]=\\{0,1,\ldots,n-1\\}$ for each positive integer $n$. We usually
index the coordinates of the codewords in ${\mathcal{C}}$ with the elements in
$[n]$. An $[n,k,d]$ code ${\mathcal{C}}$ over ${\mathrm{GF}}(q)$ is called an
$(n,k,d,q;r)$-LRC (locally recoverable code) if for each $i\in[n]$ there is a
subset $R_{i}\subseteq[n]\setminus\\{i\\}$ of size $r$ and a function
$f_{i}(x_{1},\ldots,x_{r})$ on ${\mathrm{GF}}(q)^{r}$ such that
$c_{i}=f_{i}({\mathbf{c}}_{R_{i}})$ for each codeword
${\mathbf{c}}=(c_{0},\ldots,c_{n-1})$ in ${\mathcal{C}}$, where
${\mathbf{c}}_{R_{i}}$ is the projection of ${\mathbf{c}}$ at $R_{i}$. The
symbol $c_{i}$ is called the $i$-th _code symbol_ and the set $R_{i}$ is
called the _repair set_ or _recovering set_ of the code symbol $c_{i}$. In
this definition of LRCs, the degrees of the functions $f_{i}$ are not
restricted. If we require that each $f_{i}$ be a homogeneous function of
degree $1$ in the definition above, then we say that ${\mathcal{C}}$ is
$(n,k,d,q;r)$-LLRC (linearly local recoverable code) and has linear locality
$r$. By definition, a code ${\mathcal{C}}$ has locality $r$ if it has linear
locality $r$. But the converse may not be true. If a linear code has locality,
it must have the minimum locality. The same is true for linear locality.
Regarding linear locality, we have the following questions.

######  Question 1.

What linear codes have linear locality?

######  Question 2.

If a linear code has linear locality, what is the minimum linear locality and
how does one compute the minimum linear locality?

The first objective of this paper is to answer the two questions above. We
will develop some general theory answering these two questions.

For any $(n,k,d,q;r)$-LLRC, Gopalan et al. proved the following upper bound on
the minimum distance $d$ [20]:

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

The bound in (1) is similar to the Singleton bound, so we call it the
Singleton-like bound. If an $(n,k,d,q;r)$-LLRC meets the Singleton-like bound
with equality, then we say that the $(n,k,d,q;r)$-LLRC is distance-optimal
($d$-optimal for short). If an $(n,k,d,q;r)$-LLRC meets the Singleton-like
bound minus one with equality, then we say that the $(n,k,d,q;r)$-LLRC is
almost distance-optimal (almost $d$-optimal for short). Note that the
Singleton-like bound is not tight for codes over small finite fields, as it is
independent of the alphabet size $q$.

For any $(n,k,d,q;r)$-LLRC, Cadambe and Mazumdar developed the following bound
on the dimension $k$ [5], [6]:

$k\leq\min_{t\in\mathbb{{Z}}_{+}}[tr+k_{opt}^{(q)}(n-t(r+1),d)],$ (2)

where $\mathbb{{Z}}_{+}$ denotes the set of all positive integers, and
$k_{opt}^{(q)}(n,d)$ is the largest possible dimension of a linear code with
length $n$, minimum distance $d$, and alphabet size $q$. In this paper, we
call the bound in (2) the CM bound. An $(n,k,d,q;r)$-LLRC that attains the CM
bound with equality is said to be dimension-optimal ($k$-optimal for short).

While constructing new optimal LLRCs is an important task, searching for
optimal LLRCs in the known families of linear codes is also important. The
second objective of this paper is to study the minimum linear locality of
certain known families of linear codes and try to find out $d$-optimal or
$k$-optimal LLRCs. We focus on non-binary linear codes, as the linear locality
of some families of binary codes were studied in [22]. Our methodology is
combinatorial and group-theoretical.

Locally recoverable codes were proposed for the recovery of data in
distributed and cloud storage systems by Gopalan, Huang, Simitci and Yikhanin
[20]. In the past nine years, a lot of progress on the study of locally
recoverable codes has been made. The reader is referred to [7, 8, 9, 5, 6, 20,
22, 25, 27, 28, 31, 32, 33, 39, 40] and the references therein for
information. Despite of the good progress made by now, the two questions
raised above look still open, and there is a lack of general theory on the
minimum linear locality of linear codes. In addition, the minimum linear
locality of many known families of linear codes are not studied in the
literature. Motivated by these two facts, this paper develops some general
theory about the minimum linear locality of linear codes, and investigates the
minimum linear locality of a number of families of linear codes, such as
$q$-ary Hamming codes, $q$-ary Simplex codes, generalized Reed-Muller codes,
ovoid codes, maximum arc codes, the extended hyperoval codes, and near MDS
codes. Many classes of both distance-optimal and dimension-optimal LRCs are
presented in this paper. The minimum linear locality of many families of
linear codes are settled with the general theory developed in this paper.

The rest of this paper is organized as follows. Section II introduces some
basics of cyclic and linear codes and the support designs of linear codes.
Section III develops some general theory about the minimum linear locality of
nontrivial linear codes. Section IV investigates the minimum linear locality
of several families of famous linear codes, including the $q$-ary Hamming
codes, the $q$-ary Simplex codes, the generalized Reed-Muller codes, the ovoid
codes, and the maximum arc codes. Section V studies the minimum linear
locality of near MDS codes. Section VI summarizes the contributions of this
paper and makes some concluding remarks.

##  II Preliminaries

To study the minimum linear locality of linear codes, we need to introduce
some basics of linear codes and cyclic codes. Since our methodology is
combinatorial and group-theoretic, we have to introduce the automorphism
groups of linear codes and combinatorial $t$-designs. The purpose of this
section is to introduce these stuffs very briefly.

###  II-A BCH and cyclic codes

An $[n,k,d]$ code ${\mathcal{C}}$ over ${\mathrm{GF}}(q)$ is said to be cyclic
if for each $(c_{0},c_{1},c_{2},\cdots,c_{n-1})\in{\mathcal{C}}$ we have
$(c_{n-1},c_{0},c_{1},c_{2},\cdots,c_{n-2})\in{\mathcal{C}}$. We identify a
vector $(c_{0},c_{1},c_{2},\cdots,c_{n-1})\in{\mathrm{GF}}(q)^{n}$ with the
polynomial $c(x)=\sum_{i=0}^{n-1}c_{i}x^{i}\in{\mathrm{GF}}(q)[x]/(x^{n}-1).$
Then a code ${\mathcal{C}}$ of length $n$ over ${\mathrm{GF}}(q)$ corresponds
to a subset ${\mathcal{C}}(x)$ of the quotient ring
${\mathrm{GF}}(q)[x]/(x^{n}-1)$, where

${\mathcal{C}}(x):=\left\\{\sum_{i=0}^{n-1}c_{i}x^{i}:c=(c_{0},c_{1},\cdots,c_{n-1})\in{\mathcal{C}}\right\\}.$

It is easy to see that ${\mathcal{C}}$ is cyclic if and only if the set
${\mathcal{C}}(x)$ is an ideal of the ring ${\mathrm{GF}}(q)[x]/(x^{n}-1)$.

It is well-known that each ideal of ${\mathrm{GF}}(q)[x]/(x^{n}-1)$ is
principal. Let ${\mathcal{C}}=\langle g(x)\rangle$ be a cyclic code, where
$g(x)$ is monic and has the smallest degree among all the generators of
${\mathcal{C}}$. Then $g(x)$ is unique and called the generator polynomial,
and $h(x)=(x^{n}-1)/g(x)$ is referred to as the check polynomial of
${\mathcal{C}}$.

Let $n$ be a positive integer with $\gcd(n,q)=1$, and let
$m={\mathrm{ord}}_{n}(q)$ be the order of $q$ modulo $n$. Let $\alpha$ be a
generator of the multiplicative group ${\mathrm{GF}}(q^{m})^{*}$. Put
$\beta=\alpha^{(q^{m}-1)/n}$. Then $\beta$ is a primitive $n$-th root of unity
in ${\mathrm{GF}}(q^{m})$. The minimal polynomial
${\mathsf{M}}_{\beta^{s}}(x)$ of $\beta^{s}$ over ${\mathrm{GF}}(q)$ is
defined to be the monic polynomial of the smallest degree over
${\mathrm{GF}}(q)$ with $\beta^{s}$ as a root and is given by

$\displaystyle{\mathsf{M}}_{\beta^{s}}(x)=\prod_{i\in
C_{s}}(x-\beta^{i})\in{\mathrm{GF}}(q)[x],$ (3)

where $C_{s}=\\{sq^{i}\bmod n:0\leq i\leq m-1\\}$ and is called the
$q$-cyclotomic class containing $s$.

Let $\delta$ be an integer with $2\leq\delta\leq n$ and let $h$ be an integer.
A _BCH code_ over ${\mathrm{GF}}(q)$ with length $n$ and _designed distance_
$\delta$, denoted by ${\mathcal{C}}_{(q,n,\delta,h)}$, is a cyclic code with
generator polynomial

$\displaystyle
g_{(q,n,\delta,h)}={\mathrm{lcm}}({\mathsf{M}}_{\beta^{h}}(x),{\mathsf{M}}_{\beta^{h+1}}(x),\cdots,{\mathsf{M}}_{\beta^{h+\delta-2}}(x)).$
(4)

If $h=1$, the code ${\mathcal{C}}_{(q,n,\delta,h)}$ with the generator
polynomial in (4) is referred to as a _narrow-sense_ BCH code. If $n=q^{m}-1$,
then ${\mathcal{C}}_{(q,n,\delta,h)}$ is called a _primitive_ BCH code.

BCH codes form a subfamily of cyclic codes with very attractive properties and
applications. In many cases BCH codes are the best linear codes. For instance,
among all binary cyclic codes of odd lengths $n$ with $n\leq 125$ the best
cyclic code is always a BCH code except for two special cases [11]. Reed-
Solomon codes are also BCH codes and have been widely used in data storage
systems, communication devices and consumer electronics.

###  II-B Several basic operations on linear codes

Let ${\mathcal{C}}$ be a linear code with length $n$. Below we introduce
several basic operations on ${\mathcal{C}}$ for obtaining new codes. Let $T$
be a set of coordinate positions in ${\mathcal{C}}$ and let
${\mathcal{C}}^{T}$ denote the code obtained by puncturing ${\mathcal{C}}$ in
all the coordinate positions in $T$, which has length $n-|T|$. Let
${\mathcal{C}}(T)$ denote the set of codewords whose coordinates are
${\mathbf{0}}$ on $T$, which is a subcode of ${\mathcal{C}}$. After puncturing
${\mathcal{C}}(T)$ on $T$, we get a linear code over ${\mathrm{GF}}(q)$ with
length $n-|T|$, which is called a _shortened code_ of ${\mathcal{C}}$, and is
denoted by ${\mathcal{C}}_{T}$. It is known that
$({\mathcal{C}}^{\perp}))_{T}=({\mathcal{C}}^{T})^{\perp}$ and
$({\mathcal{C}}^{\perp})^{T}=({\mathcal{C}}_{T})^{\perp}$. The _extended code_
$\overline{{\mathcal{C}}}$ of ${\mathcal{C}}$ is defined by

$\overline{{\mathcal{C}}}=\left\\{(c_{0},c_{1},\ldots,c_{n-1},c_{n})\in{\mathrm{GF}}(q)^{n+1}:(c_{0},c_{1},\ldots,c_{n-1})\in{\mathcal{C}}\mbox{
with }\sum_{i=0}^{n}c_{i}=0\right\\}.$

Let $G$ be a generator matrix of ${\mathcal{C}}$. Suppose that the all-$1$
vector is not a codeword of ${\mathcal{C}}$. Then the _augmented code_ ,
denoted by $\widetilde{{\mathcal{C}}}$, of ${\mathcal{C}}$ is the linear code
over ${\mathrm{GF}}(q)$ with generator matrix

$\displaystyle\left[\begin{array}[]{c}G\\\ {\mathbf{1}}\end{array}\right],$

where ${\mathbf{1}}$ denotes the all-$1$ vector. The augmented code has length
$n$ and dimension $k+1$.

###  II-C Automorphism groups of linear codes

The _permutation automorphism group_ of ${\mathcal{C}}$, denoted by
${\mathrm{PAut}}({\mathcal{C}})$, is the set of coordinate permutations that
map a code ${\mathcal{C}}$ to itself. A square matrix having exactly one
nonzero element of ${\mathrm{GF}}(q)$ in each row and column is called a
_monomial matrix_ over ${\mathrm{GF}}(q)$. A monomial matrix $M$ can be
written in the form $DP$ or the form $PD_{1}$, where $P$ is a permutation
matrix and $D$ and $D_{1}$ are diagonal matrices. The _monomial automorphism
group_ of ${\mathcal{C}}$ refers to the set of monomial matrices that map
${\mathcal{C}}$ to itself. Obviously,
${\mathrm{PAut}}({\mathcal{C}})\subseteq{\mathrm{MAut}}({\mathcal{C}})$. The
automorphism group of ${\mathcal{C}}$, denoted by
${\mathrm{Aut}}({\mathcal{C}})$, is the set of maps of the form $M\gamma$ that
map ${\mathcal{C}}$ to itself, where $M$ is a monomial matrix and $\gamma$ is
a field automorphism. If $q=2$, ${\mathrm{PAut}}({\mathcal{C}})$,
${\mathrm{MAut}}({\mathcal{C}})$ and ${\mathrm{Aut}}({\mathcal{C}})$ are the
same. If $q$ is a prime, ${\mathrm{MAut}}({\mathcal{C}})$ and
${\mathrm{Aut}}({\mathcal{C}})$ are identical. In general, we have

${\mathrm{PAut}}({\mathcal{C}})\subseteq{\mathrm{MAut}}({\mathcal{C}})\subseteq{\mathrm{Aut}}({\mathcal{C}}).$

By the definitions above, each element in ${\mathrm{Aut}}({\mathcal{C}})$ is
of the form $DP\gamma$, where $D$ is a diagonal matrix, $P$ is a permutation
matrix, and $\gamma$ is an automorphism of ${\mathrm{GF}}(q)$. The
automorphism group ${\mathrm{Aut}}({\mathcal{C}})$ is said to be _$t$
-transitive_ if for every pair of $t$-element ordered sets of coordinates,
there is an element $DP\gamma$ of the automorphism group
${\mathrm{Aut}}({\mathcal{C}})$ such that its permutation part $P$ sends the
first set to the second set. The automorphism group
${\mathrm{Aut}}({\mathcal{C}})$ is said to be _$t$ -homogeneous_ if for every
pair of $t$-element sets of coordinates, there is an element $DP\gamma$ of the
automorphism group ${\mathrm{Aut}}({\mathcal{C}})$ such that its permutation
part $P$ sends the first set to the second set. If the automorphism group
${\mathrm{Aut}}({\mathcal{C}})$ is $t$-transitive, then it must be
$t$-homogeneous. But the converse may not be true. For simplicity, we say that
${\mathrm{Aut}}({\mathcal{C}})$ is transitive (respectively, homogeneous) if
${\mathrm{Aut}}({\mathcal{C}})$ is $1$-transitive (respectively,
$1$-homogeneous).

###  II-D The support designs of linear codes

Let ${\mathcal{P}}$ be a set of $n$ elements, and let ${\mathcal{B}}$ be a set
of $k$-subsets of ${\mathcal{P}}$, where $1\leq k\leq n$. Let $t$ be an
integer with $1\leq t\leq k$. The pair
${\mathbb{D}}:=({\mathcal{P}},{\mathcal{B}})$ is an incidence structure, where
the incidence relation is the set membership. The incidence structure
${\mathbb{D}}=({\mathcal{P}},{\mathcal{B}})$ is called a $t$-$(n,k,\lambda)$
design, or simply $t$-design, if each $t$-subset of ${\mathcal{P}}$ is
contained in $\lambda$ elements of ${\mathcal{B}}$. The elements of
${\mathcal{P}}$ are referred to as points, and those of ${\mathcal{B}}$ are
called blocks. If ${\mathcal{B}}$ does not contain any repeated blocks, then
the $t$-design is called simple. This paper considers only simple $t$-designs.
A $t$-$(n,k,\lambda)$ design is referred to as a Steiner system if $t\geq 2$
and $\lambda=1$, and is denoted by $S(t,k,n)$.

There are different ways to construct $t$-designs. A coding-theoretic
construction of $t$-designs is briefly described below. Let ${\mathcal{C}}$ be
a linear code over ${\mathrm{GF}}(q)$ with length $n$. For each $k$ with
$A_{k}\neq 0$, let ${\mathcal{B}}_{k}({\mathcal{C}})$ denote the set of the
supports of all codewords with Hamming weight $k$ in ${\mathcal{C}}$, where
the coordinates of a codeword are indexed by $(0,1,\ldots,n-1)$. Let
${\mathcal{P}}({\mathcal{C}})=[n]$. The incidence structure
$({\mathcal{P}}({\mathcal{C}}),{\mathcal{B}}_{k}({\mathcal{C}}))$ may be a
$t$-$(n,k,\lambda)$ design for some positive integer $\lambda$, which is
called a _support design_ of the code ${\mathcal{C}}$, and is denoted by
${\mathbb{D}}_{k}({\mathcal{C}})$. In such a case, we say that the codewords
of weight $k$ in ${\mathcal{C}}$ support or hold a $t$-$(n,k,\lambda)$ design,
and for simplicity, we say that ${\mathcal{C}}$ supports or holds a
$t$-$(n,k,\lambda)$ design.

The following theorem, called the Assmus-Mattson Theorem, demonstrates that
the pair $({\mathcal{P}}({\mathcal{C}}),{\mathcal{B}}_{k}({\mathcal{C}}))$
defined by a linear code ${\mathcal{C}}$ is a $t$-design under certain
conditions [4].

######  Theorem 3.

Let ${\mathcal{C}}$ be an $[n,k,d]$ code over ${\mathrm{GF}}(q)$. Let
$d^{\perp}$ denote the minimum distance of ${\mathcal{C}}^{\perp}$. Let $w$ be
the largest integer satisfying $w\leq n$ and

$w-\left\lfloor\frac{w+q-2}{q-1}\right\rfloor<d.$

Define $w^{\perp}$ analogously using $d^{\perp}$. Let $(A_{i})_{i=0}^{n}$ and
$(A_{i}^{\perp})_{i=0}^{n}$ denote the weight distribution of ${\mathcal{C}}$
and ${\mathcal{C}}^{\perp}$, respectively. Fix a positive integer $t$ with
$t<d$, and let $s$ be the number of $i$ with $A_{i}^{\perp}\neq 0$ for $1\leq
i\leq n-t$. Suppose $s\leq d-t$. Then

  * •

all the codewords of weight $i$ in ${\mathcal{C}}$ support a $t$-design
provided $A_{i}\neq 0$ and $d\leq i\leq w$, and

  * •

all the codewords of weight $i$ in ${\mathcal{C}}^{\perp}$ support a
$t$-design provided $A_{i}^{\perp}\neq 0$ and $d^{\perp}\leq
i\leq\min\\{n-t,w^{\perp}\\}$.

The Assmus-Mattson Theorem above is a useful tool in constructing $t$-designs
from linear codes (see, for example, [12]), but does not characterize all
linear codes supporting $t$-designs. The reader is referred to [35] for a
generalized Assmus-Mattson theorem.

Using the automorphism group of a linear code ${\mathcal{C}}$, the following
theorem gives another sufficient condition for the code ${\mathcal{C}}$ to
hold $t$-designs [23, p. 308].

######  Theorem 4.

Let ${\mathcal{C}}$ be a linear code of length $n$ over ${\mathrm{GF}}(q)$
such that ${\mathrm{Aut}}({\mathcal{C}})$ is $t$-transitive or
$t$-homogeneous. Then the codewords of any weight $i\geq t$ of ${\mathcal{C}}$
hold a $t$-design.

##  III General theory about the minimum linear locality of linear codes

The objective of this section is to develop some general theory about the
linear locality of linear codes over finite fields. In particular, we will
answer Questions 1 and 2 raised in Section I. The zero code
$\\{{\mathbf{0}}\\}$ and the code ${\mathrm{GF}}(q)^{n}$ are not interesting
in both theory and practice, and are called _trivial codes_. If the dual
distance $d({\mathcal{C}}^{\perp})$ of ${\mathcal{C}}$ is $1$, then
${\mathcal{C}}$ has a zero coordinate, which can be punctured away without
affecting the error-correcting capability. Hence, in theory and practice codes
with $d({\mathcal{C}})\leq 1$ or $d({\mathcal{C}}^{\perp})\leq 1$ are not
interesting, and are called trivial codes. In this paper, we consider the
minimum linear locality only for nontrivial linear codes, i.e., linear codes
with $d({\mathcal{C}})\geq 2$ and $d({\mathcal{C}}^{\perp})\geq 2$. Recall
that we use the elements in $[n]$ to index the coordinate positions in a
linear code of length $n$.

###  III-A Some general theory the linear locality of nontrivial linear codes

The following lemma directly follows from the definition of linear locality of
linear codes, and is well known in the literature. We will need it later.

######  Lemma 5.

Let ${\mathcal{C}}$ be a nontrivial linear code of length $n$. Then
${\mathcal{C}}$ has linear locality $r$ if and only if for each $i\in[n]$ the
dual code ${\mathcal{C}}^{\perp}$ has a codeword ${\mathbf{c}}$ of Hamming
weight at most $r+1$ such that $i\in{\mathrm{suppt}}({\mathbf{c}})$.

######  Theorem 6.

Let ${\mathcal{C}}$ be a nontrivial linear code of lenth $n$. Then there
exists a positive integer $w$ with $2\leq w\leq n$ such that
$A_{w}({\mathcal{C}}^{\perp})>0$ and

$\displaystyle\bigcup_{j=1}^{w}\bigcup_{S\in{\mathcal{B}}_{j}({\mathcal{C}}^{\perp})}S\supseteq[n].$
(6)

Let $w$ be the smallest integer such that $A_{w}({\mathcal{C}}^{\perp})>0$ and
(6) holds. Then ${\mathcal{C}}$ has minimum linear locality $w-1$.

###### Proof.

Suppose that there is an integer $i$ in $[n]$ such that

$\displaystyle
i\not\in\bigcup_{j=1}^{n}\bigcup_{S\in{\mathcal{B}}_{j}({\mathcal{C}}^{\perp})}S.$

Then $c_{i}^{\perp}=0$ for all codewords
${\mathbf{c}}^{\perp}=(c_{0}^{\perp},\cdots,c_{n-1}^{\perp})$ in
${\mathcal{C}}^{\perp}$. Consequently, the vector
${\mathbf{c}}=(0,\cdots,0,1,0,\cdots,0)$ of length $n$, which has only one
nonzero coordinate $1$ in coordinate position $i$, is a codeword in
${\mathcal{C}}$. This is contrary to the assumption that $d\geq 2$.

Let $w$ be the smallest integer such that $A_{w}({\mathcal{C}}^{\perp})>0$ and
(6) holds. Then every integer $i\in[n]$ is contained in
${\mathrm{suppt}}({\mathbf{c}}^{\perp})$, where ${\mathbf{c}}^{\perp}$ is some
codeword with weight at most $w$ in ${\mathcal{C}}^{\perp}$. Then the code
symbol $c_{i}$ in ${\mathcal{C}}$ can be recovered by a linear combination of
the coordinates in the positions in
${\mathrm{suppt}}({\mathbf{c}}^{\perp})\setminus\\{i\\}$. Then ${\mathcal{C}}$
has linear locality $w-1$.

If the code symbol $c_{i}$ in every codeword ${\mathbf{c}}$ in ${\mathcal{C}}$
can be recovered linearly by

$c_{i}=u_{1}c_{i_{1}}+\cdots+u_{h}c_{i_{h}}$

where $u_{i}\neq 0$ and $R_{i}=\\{i_{1},\ldots,i_{h}\\}$ is the corresponding
recovering set of the code symbol $c_{i}$. Then ${\mathcal{C}}^{\perp}$ has a
codeword with weight $h+1$. Hence, $w-1$ is the minimum linear locality. ∎

Theorem 6 means that every nontrivial linear code has a minimum linear
locality, and tells us how to calculate the minimum linear locality. In
practice, it is also necessary and important to find a recovering set $R_{i}$
for each code symbol $c_{i}$. But we will not deal with this problem in this
paper.

###  III-B Linear codes ${\mathcal{C}}$ with minimum linear locality
$d({\mathcal{C}}^{\perp})-1$

It follows from Lemma 5 that the minimum linear locality of a nontrivial
linear code ${\mathcal{C}}$ is at least $d({\mathcal{C}}^{\perp})-1$. Hence,
nontrivial linear codes ${\mathcal{C}}$ with minimum linear locality
$d({\mathcal{C}}^{\perp})-1$ would be very interesting in both theory and
practice. In this subsection, we develop some general results for such special
codes. It will be seen later that there are indeed nontrivial linear codes
${\mathcal{C}}$ with minimum linear locality more than
$d({\mathcal{C}}^{\perp})-1$.

######  Corollary 7.

Let ${\mathcal{C}}$ be a nontrivial linear code of length $n$ and put
$d^{\perp}=d({\mathcal{C}}^{\perp})$. Then ${\mathcal{C}}$ has minimum linear
locality $d^{\perp}-1$ if and only if

$\displaystyle\bigcup_{S\in{\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp})}S=[n].$
(7)

###### Proof.

The desired conclusion directly follows from Theorem 6 and Lemma 5. ∎

The following result is well known in the literature. We show that it is a
corollary of Theorem 6.

######  Corollary 8.

Let ${\mathcal{C}}$ be a nontrivial cyclic code of length $n$. Then
${\mathcal{C}}$ has minimum linear locality $d({\mathcal{C}}^{\perp})-1$.

###### Proof.

Put $d^{\perp}=d({\mathcal{C}}^{\perp})$. Let $i\in[n]$. Let
${\mathbf{c}}^{\perp}$ be a minimum weight codeword in
${\mathcal{C}}^{\perp}$. By definition, the Hamming weight
${\mathtt{wt}}({\mathbf{c}}^{\perp})\geq 2$. Consequently,
${\mathbf{c}}^{\perp}$ has a nonzero coordinate. Since ${\mathcal{C}}^{\perp}$
is also cyclic, we can assume ${\mathbf{c}}^{\perp}_{i}\neq 0$. We then deduce
that

$\bigcup_{S\in{\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp})}S\supseteq\\{i\\}.$

The desired conclusion then follows from Theorem 6. ∎

######  Corollary 9.

Let ${\mathcal{C}}$ be a nontrivial linear code of length $n$ and put
$d^{\perp}=d({\mathcal{C}}^{\perp})$. If
$({\mathcal{P}}({\mathcal{C}}^{\perp}),{\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp}))$
is a $1$-$(n,d^{\perp},\lambda_{1}^{\perp})$ design with
$\lambda_{1}^{\perp}\geq 1$, then ${\mathcal{C}}$ has minimum linear locality
$d^{\perp}-1$.

###### Proof.

By the definition of $1$-designs, every
$i\in{\mathcal{P}}({\mathcal{C}}^{\perp})$ is covered in $\lambda_{1}^{\perp}$
blocks in the block set ${\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp})$.
Hence,

$\displaystyle\bigcup_{j=1}^{d^{\perp}}\bigcup_{S\in{\mathcal{B}}_{j}({\mathcal{C}}^{\perp})}S=\bigcup_{S\in{\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp})}S=[n].$

The desired conclusion then follows from Theorem 6. ∎

It should be noted that there are many nontrivial linear codes with minimum
linear locality $d({\mathcal{C}}^{\perp})-1$, but
$({\mathcal{P}}({\mathcal{C}}^{\perp}),{\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp}))$
is not a $1$-design. Hence, the converse of Corollary 9 is not true. Corollary
9 will be one of the tools for studying the minimum linear locality of some
families of linear codes in this paper. Another tool is documented in the
following corollary.

######  Corollary 10.

Let ${\mathcal{C}}$ be a nontrivial linear code. If
${\mathrm{Aut}}({\mathcal{C}})$ or ${\mathrm{Aut}}({\mathcal{C}}^{\perp})$ is
transitive, then ${\mathcal{C}}$ has minimum linear locality
$d({\mathcal{C}}^{\perp})-1$ and ${\mathcal{C}}^{\perp}$ has minimum linear
locality $d({\mathcal{C}})-1$.

###### Proof.

Put $d^{\perp}=d({\mathcal{C}}^{\perp})$. Let ${\mathcal{C}}$ be over
${\mathrm{GF}}(q)$ and have length $n$. Suppose that
${\mathrm{Aut}}({\mathcal{C}}^{\perp})$ is transitive. Let
${\mathbf{c}}^{\perp}$ be a minimum weight codeword in
${\mathcal{C}}^{\perp}$. Then ${\mathtt{wt}}({\mathbf{c}}^{\perp})\geq 2$. Let
$i\in{\mathrm{suppt}}({\mathbf{c}}^{\perp})$. For each
$j\in[n]\setminus\\{i\\}$, there is an automorphism $DP\gamma$ in
${\mathrm{Aut}}({\mathcal{C}}^{\perp})$ such that the permutation part $P$
sends $i$ to $j$, as ${\mathrm{Aut}}({\mathcal{C}}^{\perp})$ is transitive.
This means there is another minimum weight codeword
$({\mathbf{c}}^{\prime})^{\perp}$ in ${\mathcal{C}}^{\perp}$ such that
$j\in{\mathrm{suppt}}(({\mathbf{c}}^{\prime})^{\perp})$. Consequently,

$\bigcup_{j=1}^{d^{\perp}}\bigcup_{S\in{\mathcal{B}}_{j}({\mathcal{C}}^{\perp})}S=\bigcup_{S\in{\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp})}S=[n].$

It then follows from Theorem 6 that ${\mathcal{C}}$ has minimum linear
locality $d({\mathcal{C}}^{\perp})-1$.

In general, ${\mathrm{Aut}}({\mathcal{C}})$ and
${\mathrm{Aut}}({\mathcal{C}}^{\perp})$ are different. However, it is
straightforward to prove that ${\mathrm{Aut}}({\mathcal{C}})$ is transitive if
and only if ${\mathrm{Aut}}({\mathcal{C}}^{\perp})$ is so. Then the remaining
desired conclusion follows from the first conclusion proved above. ∎

Note that combining Theorem 4 and Corollary 9 gives another proof of Corollary
10. Sometimes we may need to use Corollary 9, as the automorphism group of a
code may be unknown. Sometimes it is more convenient to use Corollary 10.
Sometimes both corollaries can be used to study the linear locality of some
linear codes. In many cases, both corollaries cannot be used to do so. It
looks impossible to find out all nontrivial linear codes with minimum linear
locality $d({\mathcal{C}}^{\perp})-1$. But Corollaries 9 and 10 can be
employed to find many families of such codes. Most of the families of linear
codes documented in the monograph [12] are such codes, as they support
$t$-designs with $t\geq 2$ or their automorphism groups are doubly
homogeneous. Other families of such linear codes are not documented in [12],
as the monograph [12] does not include linear codes supporting $1$-designs but
not $2$-designs.

The following result would also be useful in some cases.

######  Theorem 11.

Let ${\mathcal{C}}$ be a nontrivial linear code. If ${\mathcal{C}}^{\perp}$ is
spanned by its minimum weight codewords, then ${\mathcal{C}}$ has minimum
linear locality $d({\mathcal{C}}^{\perp})-1$.

###### Proof.

Let ${\mathcal{C}}$ have length $n$. Let $i\in[n]$. If

$i\not\in\bigcup_{S\in{\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp})}S,$

then $(0,\ldots,0,1,0,\ldots,0)$ would be a codeword in ${\mathcal{C}}$, where
the nonzero coordinate $1$ is in coordinate position $i$, as all the minimum
weight codewords in ${\mathcal{C}}^{\perp}$ span ${\mathcal{C}}^{\perp}$. This
is contrary to the fact that ${\mathcal{C}}$ is nontrivial. The desired
conclusion then follows from Corollary 7. ∎

###  III-C The minimum linear locality of extended cyclic code

While any nontrivial cyclic code ${\mathcal{C}}$ has minimum linear locality
$d({\mathcal{C}}^{\perp})-1$, extended cyclic codes may not have such
property. Note that even if ${\mathcal{C}}$ is nontrivial, the extended code
$\overline{{\mathcal{C}}}$ may be trivial, as $d(\overline{{\mathcal{C}}})$
could be $1$. The automorphism group of any cyclic code is transitive and each
cyclic code supports $1$-designs. But these may not be true for extended
cyclic codes. In this section, we consider the linear locality of the extended
cyclic codes and their duals.

Let $H$ and $\overline{H}$ denote the parity-check matrix of ${\mathcal{C}}$
and $\overline{{\mathcal{C}}}$, respectively. Then we have the following well
known lemma [23].

######  Lemma 12.

Let ${\mathcal{C}}$ be an $[n,\kappa,d]$ code over ${\mathrm{GF}}(q)$. Then
$\overline{{\mathcal{C}}}$ is an $[n+1,\kappa,\overline{d}]$ linear code,
where $\overline{d}=d$ or $d+1$. In the binary case, $\overline{d}=d$ if $d$
is even, and $\overline{d}=d+1$ otherwise.

In addition, the parity-check matrix $\overline{H}$ of
$\overline{{\mathcal{C}}}$ can be deduced from that of ${\mathcal{C}}$ by

$\displaystyle\overline{H}=\left[\begin{array}[]{ll}{\mathbf{1}}&1\\\
H&{\mathbf{0}}\end{array}\right],$ (10)

where ${\mathbf{1}}=(1,1,\ldots,1)$ and ${\mathbf{0}}=(0,0,\ldots,0)^{T}$.

We now prove the following result, which will be needed later.

######  Theorem 13.

Let ${\mathcal{C}}$ be a nontrivial cyclic code. If
$d(\overline{{\mathcal{C}}})=d({\mathcal{C}})+1$, then
$(\overline{{\mathcal{C}}})^{\perp}$ has minimum linear locality
$d({\mathcal{C}})$.

###### Proof.

Let ${\mathcal{C}}$ have length $n$. By definition, $d({\mathcal{C}})\geq 2$
and $d({\mathcal{C}}^{\perp})\geq 2$. Since
$d(\overline{{\mathcal{C}}})=d({\mathcal{C}})+1$, we know that
$d((\overline{{\mathcal{C}}})^{\perp})\geq 2$. Therefore,
$\overline{{\mathcal{C}}}$ is nontrivial. Let
${\mathbf{c}}_{1},\ldots,{\mathbf{c}}_{h}$ be all the minimum weight codewords
in ${\mathcal{C}}$, and let $\overline{{\mathbf{c}}_{i}}$ be the extended
codeword of ${\mathbf{c}}_{i}$ in $\overline{{\mathcal{C}}}$. Since
$d({\mathcal{C}})\geq 2$ and ${\mathcal{C}}$ is cyclic, we have

$\bigcup_{i=1}^{h}{\mathrm{suppt}}({\mathbf{c}}_{i})=[n].$

Since $d(\overline{{\mathcal{C}}})=d({\mathcal{C}})+1$, the extended
coordinate in each $\overline{{\mathbf{c}}_{i}}$ is nonzero. As a result, we
get

$\bigcup_{i=1}^{h}{\mathrm{suppt}}(\overline{{\mathbf{c}}_{i}})=[n+1].$

The desired conclusion then follows from Corollary 7. ∎

######  Corollary 14.

Let ${\mathcal{C}}$ be a nontrivial binary cyclic code. If $d({\mathcal{C}})$
is odd, then $(\overline{{\mathcal{C}}})^{\perp}$ has minimum linear locality
$d({\mathcal{C}})$.

###### Proof.

The desired conclusion follows from Lemma 12 and Theorem 13. ∎

Corollary 14 has determined the minimum linear locality of
$(\overline{{\mathcal{C}}})^{\perp}$ for all binary cyclic codes.
Specifically, either $(\overline{{\mathcal{C}}})^{\perp}$ is a trivial code or
nontrivial binary linear code with minimum linear locality $d({\mathcal{C}})$
for each nontrivial cyclic code ${\mathcal{C}}$.

##  IV The minimum linear locality of some known families of linear codes

The objective of this section is to study the minimum linear locality of
several families of linear codes which are geometric codes and their punctured
and shortened codes. We wish to find out some families of optimal LLRCs.

###  IV-A The minimum linear locality of the $q$-ary Hamming codes and Simplex
codes

A parity check matrix $H_{(q,m)}$ of the Hamming code ${\mathcal{H}}_{(q,m)}$
over ${\mathrm{GF}}(q)$ is defined by choosing for its columns a nonzero
vector from each one-dimensional subspace of ${\mathrm{GF}}(q)^{m}$. In terms
of finite geometry, the columns of $H_{(q,m)}$ are the points of the
projective geometry ${\mathrm{PG}}(m-1,{\mathrm{GF}}(q))$. Hence
${\mathcal{H}}_{(q,m)}$ has length $n=(q^{m}-1)/(q-1)$ and dimension $n-m$. It
is well known that ${\mathcal{H}}_{(q,m)}$ has minimum weight 3 and any
$[(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m,3]$ code over ${\mathrm{GF}}(q)$ is
monomially equivalent to the Hamming code ${\mathcal{H}}_{(q,m)}$ [23]. Note
that the Hamming code ${\mathcal{H}}_{(q,m)}$ is permutation-equivalent to a
cyclic code when $\gcd(m,q-1)=1$. By Corollary 8, its minimum linear locality
is known in this case. However, its minimum locality may not be known for the
case that $\gcd(m,q-1)\neq 1$. The linear locality of the binary Hamming and
Simplex codes was settled in [22]. Note that binary Hamming and Simplex codes
are permutation-equivalent to cyclic codes. In this subsection, we investigate
the minimum linear locality of the $q$-ary Hamming and Simplex codes.

The weight distribution of ${\mathcal{H}}_{(q,m)}$ is given in the following
lemma [26].

######  Lemma 15.

The weight distribution of ${\mathcal{H}}_{(q,m)}$ is given by

$\displaystyle q^{m}A_{k}({\mathcal{H}}_{(q,m)})$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}0\leq i\leq\frac{q^{m-1}-1}{q-1}\\\
0\leq j\leq q^{m-1}\\\ i+j=k\end{subarray}}\left[{\frac{q^{m-1}-1}{q-1}\choose
i}{q^{m-1}\choose
j}\bigg{(}(q-1)^{k}+(-1)^{j}(q-1)^{i}(q^{m}-1)\bigg{)}\right]$

for $0\leq k\leq(q^{m}-1)/(q-1)$.

The duals of the Hamming codes ${\mathcal{H}}_{(q,m)}$ are called Simplex
codes, denoted by ${\mathcal{S}}_{(q,m)}$, which have parameters
$[(q^{m}-1)/(q-1),m,q^{m-1}]$. The nonzero codewords of the
$[(q^{m}-1)/(q-1),m,q^{m-1}]$ Simplex codes all have weight $q^{m-1}$.

######  Theorem 16.

The Hamming code ${\mathcal{H}}_{(q,m)}$ is an $(n,n-m,3,q;q^{m-1}-1)$-LLRC
and the Simplex code ${\mathcal{S}}_{(q,m)}$ is an $(n,m,q^{m-1},q;2)$-LLRC.
Furthermore, the Hamming code ${\mathcal{H}}_{(q,m)}$ and
${\mathcal{S}}_{(q,m)}$ are $k$-optimal.

###### Proof.

The Hamming code ${\mathcal{H}}_{(q,m)}$ has parameters $[n,n-m,3]$ and its
dual code is a one-weight code. Then by the Assmus-Mattson Theorem, the
codewords of minimum weight in the Hamming code and Simplex code both hold a
2-design. So
$({\mathcal{P}}({\mathcal{H}}_{(q,m)}),{\mathcal{B}}_{3}({\mathcal{H}}_{(q,m)}))$
and
$({\mathcal{P}}({\mathcal{H}}_{(q,m)}^{\perp}),{\mathcal{B}}_{q^{m-1}}({\mathcal{H}}_{(q,m)}^{\perp}))$
are $1$-designs. Hence, the conclusions on the minimum linear locality of the
two codes follow from Corollary 9.

We now prove the dimension optimality of ${\mathcal{H}}_{(q,m)}$. Putting
$t=1$ and the parameters of the $(n,n-m,3,q;q^{m-1}-1)$-LLRC into the right-
hand side of the CM bound in (2), we have

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

where the last inequality holds due to the fact that
$k_{opt}^{(q)}(n-q^{m-1},3)\leq n-q^{m-1}-m+1$, which follows from the sphere
packing bound. Therefore, the Hamming code ${\mathcal{H}}_{(q,m)}$ is
$k$-optimal.

Putting $t=1$ and the parameters of $(n,m,q^{m-1},q;2)$-LLRC into the right-
hand side of the CM bound in (2), we have

$\displaystyle k$ $\displaystyle\leq r+k_{opt}^{(q)}(n-(r+1),d)$
$\displaystyle=2+k_{opt}^{(q)}(n-3,q^{m-1})$ $\displaystyle\leq m,$

where the last inequality holds due to the fact that
$k_{opt}^{(q)}(n-3,q^{m-1})\leq m-2$, which follows from the Plotkin bound.
Therefore, the Simplex code ${\mathcal{S}}_{(q,m)}$ is $k$-optimal. This
completes the proof. ∎

According to the Singleton-like bound in (1), we can obtain the following
family of $d$-optimal LLRCs.

######  Corollary 17.

When $m=3$, the Hamming code ${\mathcal{H}}_{(q,3)}$ is a
$(q^{2}+q+1,q^{2}+q-2,3,q;q^{2}-1)$-LLRC and is both $d$-optimal and
$k$-optimal.

###### Proof.

The parameters and dimension optimality of ${\mathcal{H}}_{(q,3)}$ directly
follow from Theorem 16. Hence, we only need to prove the distance optimality.
It is easy to verify that the parameters of ${\mathcal{H}}_{(q,3)}$ satisfy
the equality in (1). Hence, it is a $d$-optimal
$(q^{2}+q+1,q^{2}+q-2,3,q;q^{2}-1)$-LLRC. This completes the proof. ∎

If a linear code ${\mathcal{C}}$ supports 2-designs, then the punctured code
${\mathcal{C}}^{\\{t_{1}\\}}$ or shortened code ${\mathcal{C}}_{\\{t_{1}\\}}$
may support 1-designs. Then we can settle the minimum linear locality of
${\mathcal{C}}^{\\{t_{1}\\}}$ or ${\mathcal{C}}_{\\{t_{1}\\}}$. The parameters
of some punctured codes and shortened codes of the Hamming code are given in
the following lemma [26].

######  Lemma 18.

Let $n=(q^{m}-1)/(q-1)\geq 4$, and let $t_{1}$ be any coordinate position of
codewords in ${\mathcal{H}}_{(q,m)}$. Then the following hold:

  * •

$({\mathcal{H}}_{(q,m)})_{\\{t_{1}\\}}$ is an $[n-1,n-m-1,3]$ code over
${\mathrm{GF}}(q)$ with

$\displaystyle A_{k}(({\mathcal{H}}_{(q,m)})_{\\{t_{1}\\}})$ $\displaystyle=$
$\displaystyle\frac{n-k}{n}A_{k}({\mathcal{H}}_{(q,m)})$

for $0\leq k\leq n-1$, where $A_{k}({\mathcal{H}}_{(q,m)})$ was given in Lemma
15.

  * •

$(({\mathcal{H}}_{(q,m)})_{\\{t_{1}\\}})^{\perp}$ is an $[n-1,m,q^{m-1}-1]$
code over ${\mathrm{GF}}(q)$ with weight enumerator

$1+(q-1)q^{m-1}z^{q^{m-1}-1}+(q^{m-1}-1)z^{q^{m-1}}.$

  * •

$({\mathcal{S}}_{(q,m)})_{\\{t_{1}\\}}$ is an $[n-1,m-1,q^{m-1}]$ code over
${\mathrm{GF}}(q)$ with weight enumerator $1+(q^{m-1}-1)z^{q^{m-1}}.$

  * •

$(({\mathcal{S}}_{(q,m)})_{\\{t_{1}\\}})^{\perp}$ is an $[n-1,n-m,2]$ code
over ${\mathrm{GF}}(q)$ with weight enumerator

$\frac{1}{q^{m-1}}[(1+(q-1)z)^{n-1}+(q^{m-1}-1)(1-z)^{q^{m-1}}(1+(q-1)z)^{n-1-q^{m-1}}].$

With the Assmus-Mattson Theorem, we can deduce that the codewords of minimum
weight in these codes in Lemma 18 hold a 1-design. Then by Corollary 9, we can
settle the minimum linear locality of these codes in Lemma 18.

######  Theorem 19.

Let $n=(q^{m}-1)/(q-1)\geq 4$, and let $t_{1}$ be any coordinate position of
codewords in ${\mathcal{H}}_{(q,m)}$. Then we have the following.

  * •

$({\mathcal{H}}_{(q,m)})_{\\{t_{1}\\}}$ is a $k$-optimal
$(n-1,n-m-1,3,q;q^{m-1}-2)$-LLRC.

  * •

$(({\mathcal{H}}_{(q,m)})_{\\{t_{1}\\}})^{\perp}$ is a $k$-optimal
$(n-1,m,q^{m-1}-1,q;2)$-LLRC.

  * •

$({\mathcal{S}}_{(q,m)})_{\\{t_{1}\\}}$ is a $k$-optimal
$(n-1,m-1,q^{m-1},q;1)$-LLRC.

  * •

$({\mathcal{S}}_{(q,m)})_{\\{t_{1}\\}})^{\perp}$ is a $k$-optimal
$(n-1,n-m,2,q;q^{m-1}-1)$-LLRC.

###### Proof.

The conclusions on the parameters of the codes follow from Lemma 18, the
Assmus-Mattson Theorem and Corollary 9. The proofs of the dimension optimality
of $({\mathcal{H}}_{(q,m)})_{\\{t_{1}\\}}$ and
$({\mathcal{S}}_{(q,m)})_{\\{t_{1}\\}})^{\perp}$ are similar to that in
Theorem 16, and are omitted. ∎

Furthermore, we can obtain the following $d$-optimal LLRCs.

######  Corollary 20.

The code $({\mathcal{H}}_{(q,3)})_{\\{t_{1}\\}}$ is a
$(q^{2}+q,q^{2}+q-3,3,q;q^{2}-2)$-LLRC and the code
$(({\mathcal{S}}_{(q,3)})_{\\{t_{1}\\}})^{\perp}$ is a
$(q^{2}+q,q^{2}+q-2,2,q;q^{2}-1)$-LLRC. Furthermore, they are both $d$-optimal
and $k$-optimal.

###### Proof.

The parameters of the codes follow from Theorem 19. The $d$-optimality and
$k$-opmality of the codes are with respect to the Singleton-like bound and CM
bound and can be easily verified. ∎

###  IV-B The minimum linear locality of the generalised Reed-Muller codes
over ${\mathrm{GF}}(q)$

The general affine group ${\mathrm{GA}}_{1}({\mathrm{GF}}(q^{m}))$ is defined
by

${\mathrm{GA}}_{1}({\mathrm{GF}}(q^{m}))=\\{ax+b:a\in{\mathrm{GF}}(q^{m})^{*},\
b\in{\mathrm{GF}}(q^{m})\\},$

which acts on ${\mathrm{GF}}(q^{m})$ doubly transitively [12, Section 1.7].

We can index the coordinates of a linear code of length $q^{m}$ with the
elements of ${\mathrm{GF}}(q^{m})$. When each permutation in
${\mathrm{GA}}_{1}({\mathrm{GF}}(q^{m}))$ is applied to a codeword, it is
applied to the indices of the coordinates. A linear code ${\mathcal{C}}$ of
length $q^{m}$ is said to be affine-invariant if
${\mathrm{GA}}_{1}({\mathrm{GF}}(q))$ fixes ${\mathcal{C}}$. It follows from
Theorem 4 that affine-invariant codes supports $2$-designs. By Corollary 10,
all affine-invariant codes ${\mathcal{C}}$ have minimum locality
$d({\mathcal{C}}^{\perp})-1$. There are many infinite families of affine-
invariant codes [12, Chapter 6]. Our objective in this section is to study the
minimum linear locality of the generalised Reed-Muller codes and obtain a
class of either $k$-optimal or almost $k$-optimal LLRCs.

For any integer $j=\sum_{i=0}^{m-1}j_{i}q^{i}$, where $0\leq j_{i}\leq q-1$
for all $0\leq i\leq m-1$ and $m$ is a positive integer, we define

$\displaystyle{\mathtt{wt}}_{q}(j)=\sum_{i=0}^{m-1}j_{i},$ (11)

where the sum is taken over the ring of integers, and is called the $q$-weight
of $j$. Let $\ell$ be a positive integer with $1\leq\ell<(q-1)m$. The
$\ell$-th order _punctured generalized Reed-Muller code_
${\mathcal{R}}_{q}(\ell,m)^{*}$ over ${\mathrm{GF}}(q)$ is the cyclic code of
length $n=q^{m}-1$ with generator polynomial

$\displaystyle g(x)=\prod_{\genfrac{}{}{0.0pt}{}{1\leq j\leq
n-1}{{\mathtt{wt}}_{q}(j)<(q-1)m-\ell}}(x-\alpha^{j}),$ (12)

where $\alpha$ is a generator of ${\mathrm{GF}}(q^{m})^{*}$. Since
${\mathtt{wt}}_{q}(j)$ is a constant function on each $q$-cyclotomic coset
modulo $n=q^{m}-1$, $g(x)$ is a polynomial over ${\mathrm{GF}}(q)$.

The generalized Reed-Muller code ${\mathcal{R}}_{q}(\ell,m)$ is defined to be
the extended code of ${\mathcal{R}}_{q}(\ell,m)^{*}$, and its parameters are
given below [3].

######  Theorem 21.

Let $0\leq\ell<q(m-1)$. Then the generalized Reed-Muller code
${\mathcal{R}}_{q}(\ell,m)$ has length $n=q^{m}$, dimension

$\displaystyle\kappa=\sum_{i=0}^{\ell}\sum_{j=0}^{m}(-1)^{j}\binom{m}{j}\binom{i-jq+m-1}{i-jq},$
(13)

and minimum weight

$\displaystyle d=(q-\ell_{0})q^{m-\ell_{1}-1},$ (14)

where $\ell=\ell_{1}(q-1)+\ell_{0}$ and $0\leq\ell_{0}<q-1$.

The minimum linear locality of the generalized Reed-Muller code
${\mathcal{R}}_{q}(\ell,m)$ is given in the following theorem.

######  Theorem 22.

Let $0\leq\ell<q(m-1)$ and
$m(q-1)-1-\ell=\ell^{\prime}_{1}(q-1)+\ell^{\prime}_{0}$ with
$0\leq\ell^{\prime}_{0}<q-1$. The generalized Reed-Muller code
${\mathcal{R}}_{q}(\ell,m)$ is a
$[q^{m},\kappa,d,q;(q-\ell^{\prime}_{0})q^{m-\ell^{\prime}_{1}-1}-1]$ LLRC,
where $\kappa$ and $d$ were given in (13) and (14), respectively.

###### Proof.

The dimension and minimum weight of the code were given in Theorem 21. We only
prove its minimum linear locality. It is well known that the generalised Reed-
Muller code ${\mathcal{R}}_{q}(\ell,m)$ is affine-invariant [12, Chapter 6].
By Corollary 10, the code has minimum duality
$d({\mathcal{R}}_{q}(\ell,m)^{\perp})-1$. It was proved in [3] that

$\displaystyle{\mathcal{R}}_{q}(\ell,m)^{\perp}={\mathcal{R}}_{q}(m(q-1)-1-\ell,m).$
(15)

It then follows from Theorem 21 that the minimum linear locality is

$r=d({\mathcal{R}}_{q}(\ell,m)^{\perp})-1=d({\mathcal{R}}_{q}(m(q-1)-1-\ell,m))-1=(q-\ell^{\prime}_{0})q^{m-\ell^{\prime}_{1}-1}-1.$

This completes the proof. ∎

######  Corollary 23.

Let $q>2$. Then ${\mathcal{R}}_{q}(1,m)$ is a
$(q^{m},1+m,(q-1)q^{m-1},q;2)$-LLRC and its dual
${\mathcal{R}}_{q}(1,m)^{\perp}$ is a
$(q^{m},q^{m}-1-m,3,q;(q-1)q^{m-1}-1)$-LLRC. Both codes are $k$-optimal.

###### Proof.

The parameters of the two codes were given in Theorem 22. Putting the
parameters of ${\mathcal{R}}_{q}(1,m)^{\perp}$ into the right-hand side of the
CM bound in (2), we have

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

where the last inequality holds due to the fact that
$k_{opt}^{(q)}(q^{m-1},3)\leq q^{m-1}-m+1$, which follows from the Sphere
packing bound. Therefore, the ${\mathcal{R}}_{q}(1,m)^{\perp}$ is $k$-optimal.

Taking the parameters of ${\mathcal{R}}_{q}(1,m)$ on the right-hand side of
the CM bound in (2), we have

$\displaystyle k$
$\displaystyle\leq\min_{s\in\mathbb{{Z}}_{+}}\\{rs+k_{opt}^{(q)}(n-(r+1)s,d)\\}$
$\displaystyle\leq r+k_{opt}^{(q)}(n-(r+1),d)$
$\displaystyle=2+k_{opt}^{(q)}(q^{m}-3,(q-1)q^{m-1})$ $\displaystyle\leq m+1,$

where the last inequality holds due to the fact that
$k_{opt}^{(q)}(q^{m}-3,(q-1)q^{m-1})\leq m-1$, which follows from the Plotkin
bound. Therefore, ${\mathcal{R}}_{q}(1,m)$ is $k$-optimal. This completes the
proof. ∎

In this section, we found two classes of affine-invariant codes
${\mathcal{R}}_{1}(1,m)$ and ${\mathcal{R}}_{q}(1,m)^{\perp}$, which are
$k$-optimal. It would be nice if other classes of $d$-optimal or $k$-optimal
affine-invariant codes could be found. Notice that many classes of affine-
invariant codes are known in the literature.

###  IV-C The minimum linear locality of ovoid codes

In the projective space PG$(3,{\mathrm{GF}}(q))$ with $q>2$, an ovoid
${\mathcal{V}}$ is a set of $q^{2}+1$ points such that no three of them are
collinear (i.e., on the same line). In other words, an ovoid is a
$(q^{2}+1)$-cap (a cap with $q^{2}+1$ points) in PG$(3,{\mathrm{GF}}(q))$, and
thus a maximal cap. Two ovoids are said to be equivalent if there is a
collineation (i.e., automorphism) of PG$(3,{\mathrm{GF}}(q))$ that sends one
to the other.

A classical ovoid ${\mathcal{V}}$ can be defined as the set of all points
given by

${\mathcal{V}}=\\{(0,0,1,0)\\}\cup\\{(x,y,x^{2}+xy+ay^{2},1):x,y\in{\mathrm{GF}}(q)\\}$

where $a\in{\mathrm{GF}}(q)$ is such that the polynomial $x^{2}+x+a$ has no
root in ${\mathrm{GF}}(q)$. Such ovoid is called an elliptic quadric, as the
points come from a non-degenerate elliptic quadratic form.

For $q=2^{2e+1}$ with $e\geq 1$, there is an ovoid which is not an elliptic
quadric, and is called the Tits ovoid. It is defined by

${\mathcal{T}}=\\{(0,0,1,0)\\}\cup\\{(x,y,x^{\sigma}+xy+y^{\sigma+2},1):x,y\in{\mathrm{GF}}(q)\\},$

where $\sigma=2^{e+1}$.

Let ${\mathcal{V}}$ be an ovoid in PG$(3,{\mathrm{GF}}(q))$ with $q>2$. Denote
${\mathcal{V}}=\\{{\mathbf{v}}_{1},{\mathbf{v}}_{2},\ldots,{\mathbf{v}}_{q^{2}+1}\\},$
where each ${\mathbf{v}}_{i}$ is a column vector in ${\mathrm{GF}}(q)^{4}$.
Let ${\mathcal{C}}_{\mathcal{V}}$ be the linear code over ${\mathrm{GF}}(q)$
with generator matrix
$G_{\mathcal{V}}=[{\mathbf{v}}_{1}{\mathbf{v}}_{2}\cdots{\mathbf{v}}_{q^{2}+1}].$
It is known that ${\mathcal{C}}_{\mathcal{V}}$ is a $[q^{2}+1,4,q^{2}-q]$ code
over ${\mathrm{GF}}(q)$ with weight enumerator

$1+(q^{2}-q)(q^{2}+1)z^{q^{2}-q}+(q-1)(q^{2}+1)z^{q^{2}}$

and its dual ${\mathcal{C}}_{\mathcal{V}}^{\perp}$ is a $[q^{2}+1,q^{2}-3,4]$
almost MDS code over ${\mathrm{GF}}(q)$ [12, Chapter 13]. Conversely, the set
of column vectors of a generator matrix of any $[q^{2}+1,4,q^{2}-q]$ code over
${\mathrm{GF}}(q)$ is an ovoid in PG$(3,{\mathrm{GF}}(q))$. Hence, ovoids in
PG$(3,{\mathrm{GF}}(q))$ and $[q^{2}+1,4,q^{2}-q]$ codes over
${\mathrm{GF}}(q)$ are equivalent in the sense that one can be used to
construct the other, and a $[q^{2}+1,4,q^{2}-q]$ code over ${\mathrm{GF}}(q)$
is called an ovoid code over ${\mathrm{GF}}(q)$.

Ovoid codes are very interesting in combinatorics, as they support
$3$-designs, which are documented below [12, Chapter 13].

######  Lemma 24.

The supports of all minimum weight codewords in an ovoid code form a
3-$(q^{2}+1,q^{2}-q,(q-2)(q^{2}-q-1))$ design and the supports of all
codewords of weight 4 in the dual of the ovoid code form a 3-$(q^{2}+1,4,q-2)$
design.

The linear locality of an ovoid code and its dual is described in the next
theorem.

######  Theorem 25.

An ovoid code ${\mathcal{C}}_{o}$ is a $(q^{2}+1,4,q;q^{2}-q,3)$-LLRC and its
dual ${\mathcal{C}}_{o}^{\perp}$ is a $(q^{2}+1,q^{2}-3,4,q;q^{2}-q-1)$-LLRC.
Moreover, ${\mathcal{C}}_{o}$ is $k$-optimal and ${\mathcal{C}}_{o}^{\perp}$
is $d$-optimal and $k$-optimal.

###### Proof.

The parameters follow from Lemma 24 and Corollary 9. It is easy to check the
distance optimality of ${\mathcal{C}}_{o}^{\perp}$. Then we check the
dimension optimality of ${\mathcal{C}}_{o}^{\perp}$. Putting $t=1$ into the
right-hand side of the CM bound in (2), one has

$\displaystyle k$ $\displaystyle\leq r+k_{opt}^{(q)}(n-(r+1),d)$
$\displaystyle=(q-1)q-1+k_{opt}^{(q)}(q+1,4)$ $\displaystyle\leq q^{2}-3,$

where the last inequality holds due to the fact that $k_{opt}^{(q)}(q+1,4)\leq
q-2$, which follows from the classical Singleton bound. Therefore, the code
${\mathcal{C}}_{o}^{\perp}$ is $k$-optimal.

Taking the parameters of ${\mathcal{C}}_{o}$ on the right-hand side of the CM
bound in (2), one has

$\displaystyle k$
$\displaystyle\leq\min_{t\in\mathbb{{Z}}_{+}}\\{rt+k_{opt}^{(q)}(n-(r+1)t,d)\\}$
$\displaystyle\leq r+k_{opt}^{(q)}(n-(r+1),d)$
$\displaystyle=3+k_{opt}^{(q)}(q^{2}-3,q^{2}-q)$ $\displaystyle\leq 4,$

where the last inequality holds due to the fact that
$k_{opt}^{(q)}(q^{2}-3,q^{2}-q)\leq 1$, which follows from the Plotkin bound.
Therefore, ${\mathcal{C}}_{o}$ is $k$-optimal. This completes the proof. ∎

In [26], Liu et al. studied some shortened and punctured codes of an ovoid
code, and obtained the following results.

######  Lemma 26.

Let $q\geq 4$, and let ${\mathcal{C}}_{o}$ be a $[q^{2}+1,4,q^{2}-q]$ code
over ${\mathrm{GF}}(q)$. For any coordinate position $\\{t_{1}\\}$, the
following hold.

  * •

$({\mathcal{C}}_{o})_{\\{t_{1}\\}}$ is a $[q^{2},3,q^{2}-q]$ code over
${\mathrm{GF}}(q)$ with weight enumerator

$1+q(q^{2}-1)z^{q^{2}-q}+(q-1)z^{q^{2}}.$

  * •

$(({\mathcal{C}}_{o})_{\\{t_{1}\\}})^{\perp}$ is a $[q^{2},q^{2}-3,3]$ almost
MDS code over ${\mathrm{GF}}(q)$.

  * •

$(({\mathcal{C}}_{o}^{\perp})_{\\{t_{1}\\}})^{\perp}$ is a
$[q^{2},4,q^{2}-q-1]$ code over ${\mathrm{GF}}(q)$ with weight enumerator

$1+q^{2}(q-1)z^{q^{2}-q-1}+q(q^{2}-1)z^{q^{2}-q}+q^{2}(q-1)z^{q^{2}-1}+(q-1)z^{q^{2}}.$

  * •

$({\mathcal{C}}_{o}^{\perp})_{\\{t_{1}\\}}$ is a $[q^{2},q^{2}-4,4]$ almost
MDS code over ${\mathrm{GF}}(q)$.

Furthermore, these codes hold 2-design.

The minimum linear locality of these punctured and shortened codes of ovoid
codes and their duals are documented in the following theorem.

######  Theorem 27.

Let $q\geq 4$. Then the code $({\mathcal{C}}_{o})_{\\{t_{1}\\}}$ is a
$k$-optimal $(q^{2},3,q^{2}-q,q;2)$-LLRC and the code
$(({\mathcal{C}}_{o}^{\perp})_{\\{t_{1}\\}})^{\perp}$ is a $k$-optimal
$(q^{2},4,q^{2}-q-1,q;3)$-LLRC. The code
$({\mathcal{C}}_{o}^{\perp})_{\\{t_{1}\\}}$ is a
$(q^{2},q^{2}-4,4,q;q^{2}-q-2)$-LLRC and the code
$(({\mathcal{C}}_{o})_{\\{t_{1}\\}})^{\perp}$ is a
$(q^{2},q^{2}-3,3,q;q^{2}-q-1)$-LLRC. Furthermore,
$({\mathcal{C}}_{o}^{\perp})_{\\{t_{1}\\}}$ and
$(({\mathcal{C}}_{o})_{\\{t_{1}\\}})^{\perp}$ are both $d$-optimal and
$k$-optimal.

###### Proof.

The parameters of these codes follow from Lemma 26 and Corollary 9. It is easy
to verify the distance optimality of
$({\mathcal{C}}_{o}^{\perp})_{\\{t_{1}\\}}$ and
$(({\mathcal{C}}_{o})_{\\{t_{1}\\}})^{\perp}$ with respect to the Singleton-
like bound. The proofs of dimension optimality of
$({\mathcal{C}}_{o}^{\perp})_{\\{t_{1}\\}}$ and
$(({\mathcal{C}}_{o})_{\\{t_{1}\\}})^{\perp}$ are similar, so we just prove
the dimension optimality of $({\mathcal{C}}_{o}^{\perp})_{\\{t_{1}\\}}$.
Taking $t=1$ into the right-hand side of the CM bound in (2), one arrives at

$\displaystyle k$ $\displaystyle\leq r+k_{opt}^{(q)}(n-(r+1),d)$
$\displaystyle=(q-1)q-2+k_{opt}^{(q)}(q+1,4)$ $\displaystyle\leq q^{2}-4,$

where the last inequality holds due to the fact that $k_{opt}^{(q)}(q+1,3)\leq
q-2$, which follows from the classical Singleton bound. Therefore, the code
$({\mathcal{C}}_{o}^{\perp})_{\\{t_{1}\\}}$ is $k$-optimal. The completes the
proof. ∎

Ovoid codes are very attractive in the sense that ${\mathcal{C}}_{o}^{\perp}$,
$({\mathcal{C}}_{o}^{\perp})_{\\{t_{1}\\}}$ and
$(({\mathcal{C}}_{o})_{\\{t_{1}\\}})^{\perp}$ are both $d$-optimal and
$k$-optimal. Recall that ovoid codes are the same as ovoids in projective
geometry. In addition, ovoid codes support $3$-designs, which are related to
inversive planes (also called Möbius planes) [12, Chapter 13]. Furthermore,
the trace codes of some ovoid codes are also optimal [13]. These facts show
that ovoid codes are really diamonds.

###  IV-D The minimum linear locality of maximal arc codes

Throughout this section, let $q=2^{m}$ for some positive integer $m\geq 2$. A
_maximal $(n,h)$-arc ${\mathcal{A}}$_ in the projective plane
${\mathrm{PG}}(2,{\mathrm{GF}}(q))$ is a subset of $n=hq+h-q$ points such that
every line meets ${\mathcal{A}}$ in $0$ or $h$ points. A maximal $(n,h)$-arc
${\mathcal{A}}$ in ${\mathrm{PG}}(2,{\mathrm{GF}}(q))$ exists if and only if
$h$ divides $q$, where $2\leq h<q$. Hence, in this section, we let $h=2^{i}$
for some $i$ with $1\leq i<m$. There are several known families of maximal
arcs and the reader is referred to [12, Section 12.7] for further information.

Let ${\mathcal{A}}$ be a maximal $(n,h)$-arc in PG$(2,{\mathrm{GF}}(q))$.
Denote
${\mathcal{A}}=\\{{\mathbf{a}}_{1},{\mathbf{a}}_{2},\ldots,{\mathbf{a}}_{n}\\},$
where each ${\mathbf{a}}_{i}$ is a column vector in ${\mathrm{GF}}(q)^{3}$.
Let ${\mathcal{C}}({\mathcal{A}})$ denote the linear code over
${\mathrm{GF}}(q)$ with generator matrix
$G_{\mathcal{A}}=[{\mathbf{a}}_{1}{\mathbf{a}}_{2}\cdots{\mathbf{a}}_{n}].$ We
call ${\mathcal{C}}({\mathcal{A}})$ a _maximum arc code_. The following
theorem was proved in [12, Section 12.7].

######  Theorem 28.

Let $q=2^{m}$ for any $m\geq 3$ and $h=2^{i}$ with $2\leq i<m$. Let
${\mathcal{A}}$ be a maximal $(n,h)$-arc in
${\mathrm{PG}}(2,{\mathrm{GF}}(q))$. Then the maximum arc code
${\mathcal{C}}({\mathcal{A}})$ has parameters $[n,\,3,\,n-h]$ and weight
enumerator

$\displaystyle
1+\frac{(q^{2}-1)n}{h}z^{n-h}+\frac{(q^{3}-1)h-(q^{2}-1)n}{h}z^{n},$ (16)

where $n=hq+h-q$. The dual code ${\mathcal{C}}({\mathcal{A}})^{\perp}$ has
parameters $[n,n-3,3]$. Furthermore, the minimum weight codewords in both
${\mathcal{C}}({\mathcal{A}})$ and ${\mathcal{C}}({\mathcal{A}})^{\perp}$
support a $2$-design.

######  Theorem 29.

Let $q=2^{m}$ for any $m\geq 3$ and $h=2^{i}$ with $2\leq i<m$. Let
${\mathcal{A}}$ be a maximal $(n,h)$-arc in
${\mathrm{PG}}(2,{\mathrm{GF}}(q))$. Then ${\mathcal{C}}({\mathcal{A}})$ is a
$k$-optimal $(n,3,n-h,q;2)$-LLRC and ${\mathcal{C}}({\mathcal{A}})^{\perp}$ is
a $d$-optimal and $k$-optimal $(n,n-3,3,q;n-h-1)$-LLRC.

###### Proof.

It follows from Corollary 9 and Theorem 28 that
${\mathcal{C}}({\mathcal{A}})^{\perp}$ has minimum linear locality
$d({\mathcal{C}}({\mathcal{A}}))-1$ and ${\mathcal{C}}({\mathcal{A}})$ has
minimum linear locality $d({\mathcal{C}}({\mathcal{A}})^{\perp})-1$. The
parameters of the two codes then follow from Theorem 28. It is straightforward
to verify that the parameters of ${\mathcal{C}}({\mathcal{A}})^{\perp}$ meet
the Singleton-like bound. We now prove the dimension optimality of
${\mathcal{C}}({\mathcal{A}})^{\perp}$. Putting $t=1$ into the right-hand side
of the CM bound in (2), we have

$\displaystyle k$ $\displaystyle\leq r+k_{opt}^{(q)}(n-(r+1),d)$
$\displaystyle=n-h-1+k_{opt}^{(q)}(h,3)$ $\displaystyle\leq n-3,$

where the last inequality holds due to the fact that $k_{opt}^{(q)}(h,3)\leq
h-2$, which follows from the classical Singleton bound. Therefore, the
${\mathcal{C}}({\mathcal{A}})^{\perp}$ is $k$-optimal.

Taking the parameters of ${\mathcal{C}}({\mathcal{A}})$ on the right-hand side
of the CM bound in (2), one has

$\displaystyle k$
$\displaystyle\leq\min_{t\in\mathbb{{Z}}_{+}}\\{rt+k_{opt}^{(q)}(n-(r+1)t,d)\\}$
$\displaystyle\leq r+k_{opt}^{(q)}(n-(r+1),d)$
$\displaystyle=2+k_{opt}^{(q)}(n-3,n-h)$ $\displaystyle\leq 3,$

where the last inequality holds due to the fact that
$k_{opt}^{(q)}(n-3,n-h)\leq 1$, which follows from the Plotkin bound.
Therefore, ${\mathcal{C}}({\mathcal{A}})$ is $k$-optimal. This completes the
proof. ∎

A family of extended cyclic codes with the parameters of the code in Theorem
28 were documented in [12, Section 12.8]. We are interested in maximal arc
codes, as they are $k$-optimal LLRCs and their duals are $d$-optimal and
$k$-optimal LLRCs.

##  V The minimum linear locality of near MDS codes

###  V-A Some general theory on the minimum linear locality of near MDS codes

The Singleton defect of an $[n,k,d]$ code ${\mathcal{C}}$ is defined by
def$({\mathcal{C}})=n-k+1-d$. Thus, MDS codes are codes with defect 0. A code
${\mathcal{C}}$ is said to be almost MDS (AMDS for short) if it has defect 1.
Hence, AMDS codes have parameters $[n,k,n-k]$. A code is said to be near MDS
(NMDS for short) if the code and its dual code both are AMDS. By definition,
${\mathcal{C}}$ is near MDS if and only if ${\mathcal{C}}^{\perp}$ is so. Then
an $[n,k]$ code ${\mathcal{C}}$ over ${\mathrm{GF}}(q)$ is NMDS if and only if
$d({\mathcal{C}})+d({\mathcal{C}}^{\perp})=n$ [15]. The following lemma will
be needed later ([16], [18]).

######  Lemma 30.

Let ${\mathcal{C}}$ be an $[n,k,n-k]$ AMDS code over ${\mathrm{GF}}(q)$.

  * •

If $k\geq 2$, then ${\mathcal{C}}$ is generated by its codewords of weight
$n-k$ and $n-k+1$.

  * •

If $k\geq 2$ and $n-k>q$, then ${\mathcal{C}}$ is generated by its minimum
weight codewords.

######  Theorem 31.

Let ${\mathcal{C}}$ be a nontrivial NMDS code. Then the minimum linear
locality of ${\mathcal{C}}$ is either $d({\mathcal{C}}^{\perp})-1$ or
$d({\mathcal{C}}^{\perp})$. In particular, the minimum linear locality of
${\mathcal{C}}$ is $d({\mathcal{C}}^{\perp})-1$ if the minimum weight
codewords in ${\mathcal{C}}^{\perp}$ generate ${\mathcal{C}}^{\perp}$.

###### Proof.

Let $n$ denote the length of ${\mathcal{C}}$. If ${\mathcal{C}}^{\perp}$ is
generated by its minimum weight codewords, it then follows from Theorem 11
that ${\mathcal{C}}$ has minimum linear locality $d({\mathcal{C}}^{\perp})-1$.
Assume now that all the minimum weight codewords in ${\mathcal{C}}^{\perp}$ do
not generate ${\mathcal{C}}^{\perp}$. Since ${\mathcal{C}}^{\perp}$ is
nontrivial, $\dim({\mathcal{C}}^{\perp})\geq 2$. It then follows from Lemma 30
that ${\mathcal{C}}^{\perp}$ is generated by all the codewords of weights
$d({\mathcal{C}}^{\perp})$ and $d({\mathcal{C}}^{\perp})+1$. If the union of
the supports of all the codes of weights $d({\mathcal{C}}^{\perp})$ and
$d({\mathcal{C}}^{\perp})+1$ does not contain $i\in[n]$, then ${\mathcal{C}}$
must be have a zero coordinate in position $i$. This means that
$d({\mathcal{C}})=1$, which contradicts to our assumption that ${\mathcal{C}}$
is nontrivial. It then follows from Theorem 6 that the minimum linear locality
of ${\mathcal{C}}$ is either $d({\mathcal{C}}^{\perp})-1$ or
$d({\mathcal{C}}^{\perp})$. ∎

MDS codes are very interesting due to the following theorem whose proof is
straightforward by following the assumptions and the parameters of NMDS codes.

######  Theorem 32.

If a nontrivial NMDS code ${\mathcal{C}}$ over ${\mathrm{GF}}(q)$ with
parameters $[n,k,n-k]$ has minimum linear locality
$d({\mathcal{C}}^{\perp})-1$, then ${\mathcal{C}}$ is a $d$-optimal and
$k$-optimal $(n,k,n-k,q;k-1)$-LLRC with respect to the Singleton-like bound
and the CM bound, respectively.

If a nontrivial NMDS code ${\mathcal{C}}$ over ${\mathrm{GF}}(q)$ with
parameters $[n,k,n-k]$ has minimum linear locality $d({\mathcal{C}}^{\perp})$,
then ${\mathcal{C}}$ is an almost $d$-optimal and $k$-optimal
$(n,k,n-k,q;k)$-LLRC with respect to the Singleton-like bound and the CM
bound, respectively.

We will demonstrate later that some nontrivial NMDS codes ${\mathcal{C}}$ have
minimum linear locality $d({\mathcal{C}}^{\perp})-1$ and some nontrivial NMDS
codes ${\mathcal{C}}$ indeed have minimum linear locality
$d({\mathcal{C}}^{\perp})$. Of course, nontrivial NMDS codes ${\mathcal{C}}$
with minimum linear locality $d({\mathcal{C}}^{\perp})-1$ are better.
Therefore, we are more interested in nontrivial MDS code ${\mathcal{C}}$ with
minimum linear locality $d({\mathcal{C}}^{\perp})-1$.

######  Corollary 33.

Let ${\mathcal{C}}$ be a nontrivial NMDS code over ${\mathrm{GF}}(q)$ with
parameters $[n,k,n-k]$. If ${\mathcal{C}}^{\perp}$ does not have a codeword of
weight $d({\mathcal{C}}^{\perp})+1$, Then ${\mathcal{C}}$ is a $d$-optimal and
$k$-optimal $(n,k,n-k,q;k-1)$-LLRC.

###### Proof.

By definition, ${\mathcal{C}}^{\perp}$ has parameters $[n,n-k,k]$. Since
${\mathcal{C}}$ is nontrivial, $d({\mathcal{C}}^{\perp})=k\geq 2$. By Lemma
30, ${\mathcal{C}}^{\perp}$ is generated by its codewords of weights
$d({\mathcal{C}}^{\perp})$ and $d({\mathcal{C}}^{\perp})+1$. Since
${\mathcal{C}}^{\perp}$ does not have a codeword of weight
$d({\mathcal{C}}^{\perp})+1$, ${\mathcal{C}}^{\perp}$ is generated by its
codewords of weight $d({\mathcal{C}}^{\perp})$. By Theorem 11, ${\mathcal{C}}$
has minimum linear locality $d({\mathcal{C}}^{\perp})-1$. The desired
conclusion then follows from Theorem 32. ∎

We remark that under the condition of Corollary 33, it can be proved that the
minimum weight codewords in ${\mathcal{C}}^{\perp}$ support a $1$-design [14].
To prove another result about the minimum linear locality, we need the
following lemma [18].

######  Lemma 34.

Let ${\mathcal{C}}$ be an NMDS code. Then for every minimum weight codeword
${\mathbf{c}}$ in ${\mathcal{C}}$, there exists, up to a multiple, a unique
minimum weight codeword ${\mathbf{c}}^{\perp}$ in ${\mathcal{C}}^{\perp}$ such
that
${\mathrm{suppt}}({\mathbf{c}})\cap{\mathrm{suppt}}({\mathbf{c}}^{\perp})=\emptyset$.
In particular, ${\mathcal{C}}$ and ${\mathcal{C}}^{\perp}$ have the same
number of minimum weight codewords.

We now provide the following result, which is useful in certain cases.

######  Theorem 35.

Let ${\mathcal{C}}$ be an NMDS code and let
$d^{\perp}=d({\mathcal{C}}^{\perp})$. If

$\bigcap_{S\in{\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp})}S=\emptyset,$

then ${\mathcal{C}}^{\perp}$ has minimum linear locality $d({\mathcal{C}})-1$.

###### Proof.

Let ${\mathcal{C}}$ have parameters $[n,k,d]$ with $d=n-k$. It follows from
Lemma 34 that each set in ${\mathcal{B}}_{d}({\mathcal{C}})$ is the complement
of a set in ${\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp})$ and vice versa.
If an integer $i\in[n]$ is not in
$\cup_{S\in{\mathcal{B}}_{d}({\mathcal{C}})}$, we then deduce that it must be
in $\cap_{S\in{\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp})}$. This is
contrary to the assumption that
$\cap_{S\in{\mathcal{B}}_{d^{\perp}}({\mathcal{C}}^{\perp})}S=\emptyset$.
Consequently,

$\bigcup_{S\in{\mathcal{B}}_{d}({\mathcal{C}})}=[n].$

The desired conclusion then follows from Corollary 7. ∎

###  V-B The minimum linear locality of NMDS cyclic codes

According to Corollary 8 and Theorem 32, every nontrivial NMDS cyclic code
${\mathcal{C}}$ and its dual are both $d$-optimal and $k$-optimal LLRCs. In
this subsection, we document such NMDS cyclic codes. We begin with the
following example.

######  Example 36.

The ternary Golay code ${\mathcal{C}}_{\mathrm{Golay}}$ has parameters
$[11,6,5]$ and weight enumerator

$1+132z^{5}+132z^{6}+330z^{8}+110z^{9}+24z^{11}.$

The dual code ${\mathcal{C}}_{\mathrm{Golay}}^{\perp}$ has parameters
$[11,5,6]$ and weight enumerator

$1+132z^{6}+110z^{9}.$

Hence, the ternary Golay code is an nontrivial NMDS. It is well known that
${\mathcal{C}}_{\mathrm{Golay}}$ is a BCH code, an irreducible cyclic code,
and also a quadratic residue code. By Corollary 8 and Theorem 32, both codes
are $d$-optimal and $k$-optimal LLRCs.

The following two theorems document two classes of nontrivial NMDS cyclic
codes [14].

######  Theorem 37.

Let $q=2^{s}$ with $s\geq 4$ being even. Then the narrow-sense BCH code
${\mathcal{C}}_{(q,q+1,3,1)}$ over ${\mathrm{GF}}(q)$ has parameters
$[q+1,q-3,4]$, and its dual code ${\mathcal{C}}_{(q,q+1,3,1)}^{\perp}$ has
parameters $[q+1,4,q-3]$ and weight enumerator

$\displaystyle
1+\frac{(q-4)(q-1)q(q+1)}{24}z^{q-3}+\frac{(q-1)q(q+1)}{2}z^{q-2}+$
$\displaystyle\frac{(q+1)q^{2}(q-1)}{4}z^{q-1}+\frac{(q-1)(q+1)(2q^{2}+q+6)}{6}z^{q}+$
$\displaystyle\frac{3q^{4}-4q^{3}-3q^{2}+4q}{8}z^{q+1}.$

Further, the codewords of weight $4$ in ${\mathcal{C}}_{(q,q+1,3,1)}$ support
a $2$-$(q+1,4,(q-4)/2)$ design, and the codewords of weight $q-3$ in the dual
code ${\mathcal{C}}_{(q,q+1,3,1)}^{\perp}$ support a
$2$-$(q+1,q-3,\lambda^{\perp})$ design with

$\lambda^{\perp}=\frac{(q-4)^{2}(q-3)}{24}.$

######  Theorem 38.

Let $q=3^{s}$ with $s\geq 2$. Then the narrow-sense BCH code
${\mathcal{C}}_{(q,q+1,3,1)}$ over ${\mathrm{GF}}(q)$ has parameters
$[q+1,q-3,4]$, and its dual code ${\mathcal{C}}_{(q,q+1,3,1)}^{\perp}$ has
parameters $[q+1,4,q-3]$ and weight enumerator

$\displaystyle
1+\frac{(q-1)^{2}q(q+1)}{24}z^{q-3}+\frac{(q-1)q(q+1)(q+3)}{4}z^{q-1}+$
$\displaystyle\frac{(q^{2}-1)(q^{2}-q+3)}{3}z^{q}+\frac{3(q-1)^{2}q(q+1)}{8}z^{q+1}.$

Further, the minimum weight codewords in ${\mathcal{C}}_{(q,q+1,3,1)}^{\perp}$
support a $3$-$(q+1,q-3,\lambda)$ design with

$\lambda=\frac{(q-3)(q-4)(q-5)}{24},$

and the minimum weight codewords in ${\mathcal{C}}_{(q,q+1,3,1)}$ support a
$3$-$(q+1,4,1)$ design, i.e., a Steiner quadruple system $S(3,4,3^{s}+1)$.
Furthermore, the codewords of weight 5 in ${\mathcal{C}}_{(q,q+1,3,1)}$
support a $3$-$(q+1,5,(q-3)(q-7)/2)$ design.

Notice that the minimum weight codewords in the code
${\mathcal{C}}_{(q,q+1,3,1)}^{\perp}$ in Theorem 38 generate the code, as it
does not have a codeword of weight $q-2$. The next theorem gives the third
class of NMDS cyclic codes [34].

######  Theorem 39.

Let $m\geq 5$ be odd and $q=2^{m}$. Then the narrow-sense BCH code
${\mathcal{C}}_{(q,q+1,4,1)}$ over ${\mathrm{GF}}(q)$ is a $[q+1,q-5,6]$ NMDS
code and ${\mathcal{C}}_{(q,q+1,4,1)}^{\perp}$ has parameters $[q+1,6,q-5]$.
Furthermore, the minimum weight codewords in ${\mathcal{C}}_{(q,q+1,4,1)}$
support a $4$-$(q+1,6,(q-8)/2)$ design and the minimum weight codewords in
${\mathcal{C}}_{(q,q+1,4,1)}^{\perp}$ support a $4$-$(q+1,q-5,\lambda)$ design
with

$\lambda=\frac{q-8}{30}\binom{q-5}{4}.$

Many NMDS codes have been constructed (see, for example, [1, 2, 10, 15, 16,
17, 18, 19, 24, 29, 37, 38, 36]). It is worthwhile to check if some of them
are cyclic.

###  V-C The minimum linear locality of the extended codes of some NMDS cyclic
codes

In this section, we investigate the minimum linear locality of the extended
codes of some NMDS cyclic codes, and will make use of Theorem 13.

######  Theorem 40.

Let $q=3^{s}$ with $s\geq 2$. Then the extended code
$\overline{{\mathcal{C}}_{(q,q+1,3,1)}}$ over ${\mathrm{GF}}(q)$ has
parameters $[q+2,q-3,5]$, and its dual code
$(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp}$ has parameters
$[q+2,5,q-3]$. Furthermore, $(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp}$
is a $d$-optimal and $k$-optimal $(q+2,5,q-3,q;4)$-LLRC.

###### Proof.

Put $n=q+1$. Let $\alpha$ be a generator of ${\mathrm{GF}}(q^{2})^{*}$ and
$\beta=\alpha^{q-1}$. Then $\beta$ is an $n$-th root of unity in
${\mathrm{GF}}(q^{2})$. Let $\mathbb{M}_{\beta}(x)$ and
$\mathbb{M}_{\beta^{2}}(x)$ denote the minimal polynomial of $\beta$ and
$\beta^{2}$ over ${\mathrm{GF}}(q)$, respectively. Note that
$\mathbb{M}_{\beta}(x)$ has only roots $\beta$ and $\beta^{q}$ and
$\mathbb{M}_{\beta^{2}}(x)$ has roots $\beta^{2}$ and $\beta^{q-1}$. We deduce
that $\mathbb{M}_{\beta}(x)$ and $\mathbb{M}_{\beta^{2}}(x)$ are distinct
irreducible polynomials of degree $2$. By definition,
$g(x):=\mathbb{M}_{\beta}(x)\mathbb{M}_{\beta^{2}}(x)$ is the generator
polynomial of ${\mathcal{C}}_{(q,q+1,3,1)}$. Put $\gamma=\beta^{-1}$. Then
$\gamma^{q+1}=\beta^{-(q+1)}=1$. It then follows from Delsarte’s theorem that
the trace expression of ${\mathcal{C}}_{(q,q+1,3,1)}^{\perp}$ is given by

$\displaystyle{\mathcal{C}}_{(q,q+1,3,1)}^{\perp}=\\{{\mathbf{c}}_{(a,b)}:a,b\in{\mathrm{GF}}(q^{2})\\},$

where
${\mathbf{c}}_{(a,b)}=({\mathrm{Tr}}_{q^{2}/q}(a\gamma^{i}+b\gamma^{2i}))_{i=0}^{q}$.
Define

$\displaystyle
H=\left[\begin{array}[]{rrrrr}1&\gamma^{1}&\gamma^{2}&\cdots&\gamma^{q}\\\
1&\gamma^{2}&\gamma^{4}&\cdots&\gamma^{2q}\end{array}\right].$

It is easily seen that $H$ is a parity-check matrix of
${\mathcal{C}}_{(q,q+1,3,1)}$, i.e.,

${\mathcal{C}}_{(q,q+1,3,1)}=\\{{\mathbf{c}}\in{\mathrm{GF}}(q)^{q+1}:{\mathbf{c}}H^{T}={\mathbf{0}}\\}.$

Note that $\\{1,\gamma\\}$ is a basis of ${\mathrm{GF}}(q^{2})$ over
${\mathrm{GF}}(q)$. Every $\gamma^{j}$ can be expressed as
$\gamma^{j}=a_{j,0}+a_{j,1}\gamma$, where $a_{j,0}\in{\mathrm{GF}}(q)$ and
$a_{j,1}\in{\mathrm{GF}}(q)$. Later, $H$ refers to the $4\times n$ matrix over
${\mathrm{GF}}(q)$ defined by these $a_{j,i}$.

From Lemma 12, $\overline{{\mathcal{C}}_{(q,q+1,3,1)}}$ has parameters
$[q+2,q-3,d(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})]$ and the parity-check
matrix $\overline{H}$ of $\overline{{\mathcal{C}}_{(q,q+1,3,1)}}$ is

$\displaystyle\overline{H}=\left[\begin{array}[]{ll}{\mathbf{1}}&1\\\
H&{\mathbf{0}}\end{array}\right],$

where ${\mathbf{1}}=(1,1,\ldots,1)$ and ${\mathbf{0}}=(0,0,\ldots,0)^{T}$.

Note that
$d(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})=d({\mathcal{C}}_{(q,q+1,3,1)})+1$
or $d(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})=d({\mathcal{C}}_{(q,q+1,3,1)})$.
Now we prove that
$d(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})=d({\mathcal{C}}_{(q,q+1,3,1)})+1=5$.
Let $U_{q+1}$ denote the set of all $(q+1)$-th roots of unity in
${\mathrm{GF}}(q^{2})$. Suppose
$d(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})=d({\mathcal{C}}_{(q,q+1,3,1)})=4$.
Then there are four pairwise distinct elements $x,y,z,w$ in $U_{q+1}$ such
that

$\displaystyle a\left[\begin{array}[]{c}1\\\ x\\\
x^{2}\end{array}\right]+b\left[\begin{array}[]{c}1\\\ y\\\
y^{2}\end{array}\right]+c\left[\begin{array}[]{c}1\\\ z\\\
z^{2}\end{array}\right]+d\left[\begin{array}[]{c}1\\\ w\\\
w^{2}\end{array}\right]=0,$ (31)

where $a,b,c,d\in{\mathrm{GF}}(q)^{*}$. Raising to the $q$-th power both sides
of the equation $ax+by+cz+dw=0$ yields

$\displaystyle ax^{-1}+by^{-1}+cz^{-1}+dw^{-1}=0.$ (32)

Combining (31) and (32) gives

$\displaystyle a\left[\begin{array}[]{c}x^{-1}\\\ 1\\\ x\\\
x^{2}\end{array}\right]+b\left[\begin{array}[]{c}y^{-1}\\\ 1\\\ y\\\
y^{2}\end{array}\right]+c\left[\begin{array}[]{c}z^{-1}\\\ 1\\\ z\\\
z^{2}\end{array}\right]+d\left[\begin{array}[]{c}w^{-1}\\\ 1\\\ w\\\
w^{2}\end{array}\right]=0.$

It then follows that

$\displaystyle\left|\begin{array}[]{llll}x^{-1}&y^{-1}&z^{-1}&w^{-1}\\\
1&1&1&1\\\ x&y&z&w\\\
x^{2}&y^{2}&z^{2}&w^{2}\end{array}\right|=\frac{(x-y)(x-z)(x-w)(y-z)(y-w)(z-w)}{xyzw}=0.$

This is contrary to our assumption that $x,y,z,w$ are pairwise distinct.
Hence,

$\displaystyle
d(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})=d({\mathcal{C}}_{(q,q+1,3,1)})+1=5.$
(35)

We now prove the following equalities:

$\displaystyle(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp}=\widetilde{\overline{{\mathcal{C}}_{(q,q+1,3,1)}^{\perp}}},$
(36)

where $\widetilde{D}$ denotes the augmented code of a code $D$. It is easily
verified that the sum of all coordinates in each codeword

${\mathbf{c}}_{(a,b)}=({\mathrm{Tr}}_{q^{2}/q}(a\gamma^{i}+b\gamma^{2i}))_{i=0}^{q}$

is zero, as both $\gamma$ and $\gamma^{2}$ are $n$-th roots of unity.
Consequently, $\overline{{\mathcal{C}}^{\perp}}$ is generated by the matrix
$[H{\mathbf{0}}]$, where $H$ is the $4\times n$ matrix over ${\mathrm{GF}}(q)$
defined above. Then the equality in (36) follows from Lemma 12. By (35), we
conclude that the all-one vector is not a codeword in
${\mathcal{C}}_{(q,q+1,3,1)}^{\perp}$. It then follows from (36) that

$\dim((\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp})=1+\dim({\mathcal{C}}_{(q,q+1,3,1)}^{\perp})=5.$

Now we prove $d((\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp})=q-3$. Note
that $(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp}$ has generator matrix
$\overline{H}$ and

$\displaystyle{\mathcal{C}}_{(q,q+1,3,1)}^{\perp}=\\{{\mathbf{c}}_{(a,b)}:a,b\in{\mathrm{GF}}(q^{2})\\},$

where
${\mathbf{c}}_{(a,b)}=({\mathrm{Tr}}_{q^{2}/q}(a\gamma^{i}+b\gamma^{2i}))_{i=0}^{q}$.
It follows from (36) that the codewords in
$(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp}$ have the form
$({\mathbf{c}}_{(a,b)}+c{\mathbf{1}},c)$, where $c\in{\mathrm{GF}}(q)$. Let
$u\in U_{q+1}$. Then

$\displaystyle{\mathrm{Tr}}_{q^{2}/q}(au+bu^{2})+c$ $\displaystyle=$
$\displaystyle au+bu^{2}+a^{q}u^{-1}+b^{q}u^{-2}+c$ $\displaystyle=$
$\displaystyle u^{-2}(bu^{4}+au^{3}+a^{q}u+b^{q}+cu^{2}).$

Hence, there are at most four $u\in U_{q+1}$ such that
${\mathrm{Tr}}_{q^{2}/q}(au+bu^{2})+c=0$ if $(a,b,c)\neq(0,0,0)$. As a result,
for $(a,b,c)\neq(0,0,0)$, we have

${\mathtt{wt}}(({\mathbf{c}}_{(a,b)}+c{\mathbf{1}},c))={\mathtt{wt}}({\mathbf{c}}_{(a,b)}+c{\mathbf{1}})+1\geq
q+1-4+1=q-2,$

and for $(a,b)\neq(0,0),c=0$, we have

${\mathtt{wt}}(({\mathbf{c}}_{(a,b)},0))={\mathtt{wt}}({\mathbf{c}}_{(a,b)})\geq
q+1-4=q-3.$

This means that $d((\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp})\geq q-3$.
If $d((\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp})=q-2$, then
$(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp}$ would be an MDS code and
$\overline{{\mathcal{C}}_{(q,q+1,3,1)}}$ would also be an MDS code, which
leads to a contradiction. We then conclude that
$d((\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp})=q-3$. Now both
$\overline{{\mathcal{C}}_{(q,q+1,3,1)}}$ and its dual are AMDS. Since
$d(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})=5=d({\mathcal{C}}_{(q,q+1,3,1)})+1$,
by Theorem 13 we deduce that
$(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp}$ has locality
$d({\mathcal{C}}_{(q,q+1,3,1)})=4$. The optimality of
$(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp}$ then follows from Theorem
32. ∎

######  Theorem 41.

Let $q=2^{s}$ with $s\geq 4$ being even. Then the extended code
$\overline{{\mathcal{C}}_{(q,q+1,3,1)}}$ over ${\mathrm{GF}}(q)$ has
parameters $[q+2,q-3,5]$, and its dual code
$(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp}$ has parameters
$[q+2,5,q-3]$. Furthermore, $(\overline{{\mathcal{C}}_{(q,q+1,3,1)}})^{\perp}$
is a $d$-optimal and $k$-optimal $(q+2,5,q-3,q;4)$-LLRC.

###### Proof.

The proof of this theorem is similar to that of Theorem 40 and is omitted. ∎

Notice that the two theorems above provide not only two families of
$d$-optimal and $k$-optimal LLRCs, but also two families of NMDS codes with
new parameters.

###  V-D The linear locality of some NMDS codes from oval polynomials

Oval polynomials were used to construct NMDS codes in [38]. These NMDS codes
are not cyclic. In this subsection, we study the minimum linear locality of
some of them. To introduce these codes, we need oval polynomials. Throughout
this subsection, let $q=2^{m}$, where $m\geq 3$.

An oval polynomial $f(x)$ on ${\mathrm{GF}}(q)$ is a polynomial such that

  * •

$f$ is a permutation polynomial of ${\mathrm{GF}}(q)$ with $\deg(f)<q$ and
$f(0)=0$, $f(1)=1$; and

  * •

for each $a\in{\mathrm{GF}}(q)$, $g_{a}(x):=(f(x+a)+f(a))x^{q-2}$ is also a
permutation polynomial of ${\mathrm{GF}}(q)$.

Every oval polynomial $f$ can be used to construct a hyperoval in
${\mathrm{PG}}(2,{\mathrm{GF}}(q))$ [12, Chapter 12]. The following is a list
of known infinite families of oval polynomials in the literature.

######  Theorem 42.

Let $m\geq 4$ be an integer. The following are oval polynomials of
${\mathrm{GF}}(q)$, where $q=2^{m}$.

  * •

The translation polynomial $f(x)=x^{2^{h}}$, where $\gcd(h,m)=1$.

  * •

The Segre polynomial $f(x)=x^{6}$, where $m$ is odd.

  * •

The Glynn oval polynomial $f(x)=x^{3\times 2^{(m+1)/2}+4}$, where $m$ is odd.

  * •

The Glynn oval polynomial $f(x)=x^{2^{(m+1)/2}+2^{(m+1)/4}}$ for $m\equiv
3\pmod{4}$.

  * •

The Glynn oval polynomial $f(x)=x^{2^{(m+1)/2}+2^{(3m+1)/4}}$ for $m\equiv
1\pmod{4}$.

  * •

The Cherowitzo oval polynomial $f(x)=x^{2^{e}}+x^{2^{e}+2}+x^{3\times
2^{e}+4},$ where $e=(m+1)/2$ and $m$ is odd.

  * •

The Payne oval polynomial
$f(x)=x^{\frac{2^{m-1}+2}{3}}+x^{2^{m-1}}+x^{\frac{3\times 2^{m-1}-2}{3}}$,
where $m$ is odd.

  * •

The Subiaco polynomial

$f_{a}(x)=((a^{2}(x^{4}+x)+a^{2}(1+a+a^{2})(x^{3}+x^{2}))(x^{4}+a^{2}x^{2}+1)^{2^{m}-2}+x^{2^{m-1}},$

where ${\mathrm{Tr}}_{q/2}(1/a)=1$ and $a\not\in{\mathrm{GF}}(4)$ if $m\equiv
2\bmod{4}$.

  * •

The Adelaide oval polynomial

$f(x)=\frac{T(\beta^{m})(x+1)}{T(\beta)}+\frac{T((\beta
x+\beta^{q})^{m})}{T(\beta)(x+T(\beta)x^{2^{m-1}}+1)^{m-1}}+x^{2^{m-1}},$

where $m\geq 4$ is even, $\beta\in{\mathrm{GF}}(q^{2})\setminus\\{1\\}$ with
$\beta^{q+1}=1$, $m\equiv\pm(q-1)/3\pmod{q+1}$, and $T(x)=x+x^{q}$.

The following lemma will be needed later [30].

######  Lemma 43.

A polynomial $f$ over ${\mathrm{GF}}(q)$ with $f(0)=0$ is an oval polynomial
if and only if $f_{u}:=f(x)+ux$ is $2$-to-$1$ for every
$u\in{\mathrm{GF}}(q)^{*}$.

####  V-D1 NMDS codes with parameters $[q+3,3,q]$ from oval polynomials

Let $f$ be a polynomial over ${\mathrm{GF}}(q)$ with $f(0)=0$ and $f(1)=1$.
Let $\alpha$ be a generator of ${\mathrm{GF}}(q)^{*}$. Define

$\displaystyle\bar{B}_{f}=\left[\begin{array}[]{llllllll}f(0)&f(\alpha^{0})&f(\alpha^{1})&\cdots&f(\alpha^{q-2})&1&0&1\\\
0&\alpha^{0}&\alpha^{1}&\cdots&\alpha^{q-2}&0&1&1\\\
1&1&1&\cdots&1&0&0&0\end{array}\right].$

Let $\bar{{\mathcal{C}}}_{f}$ denote the linear code over ${\mathrm{GF}}(q)$
with generator matrix $\bar{B}_{f}$. The following theorem was proved in [38].

######  Theorem 44.

Let $m\geq 3$, and let $f$ be an oval polynomial over ${\mathrm{GF}}(q)$. Then
the code $\bar{{\mathcal{C}}}_{f}$ is an NMDS code over ${\mathrm{GF}}(q)$
with parameters $[q+3,3,q]$ and weight enumerator

$\displaystyle
1+\frac{(q-1)(q+2)}{2}z^{q}+\frac{(q-1)q(q+2)}{2}z^{q+1}+\frac{(q-1)q}{2}z^{q+2}+\frac{(q-2)(q-1)q}{2}z^{q+3}.$

######  Theorem 45.

The dual code $(\bar{{\mathcal{C}}}_{f})^{\perp}$ is a $d$-optimal and
$k$-optimal $(q+3,q,3,q;q-1)$-LLRC.

###### Proof.

Let ${\mathbf{c}}_{1}$, ${\mathbf{c}}_{2}$ and ${\mathbf{c}}_{3}$ denote the
first, second and third rows of the generator matrix $\bar{B}_{f}$,
respectively. By the definition of the polynomial $f$, it is easily seen that
${\mathbf{c}}_{1}+{\mathbf{c}}_{3}$ and ${\mathbf{c}}_{2}+{\mathbf{c}}_{3}$
are two minimum weight codewords in $\bar{{\mathcal{C}}}_{f}$. In addition,
the supports of these two codewords are $[q+3]\setminus\\{q+1\\}$ and
$[q+3]\setminus\\{q\\}$, respectively. Clearly,

$([q+3]\setminus\\{q+1\\})\cup([q+3]\setminus\\{q\\})=[q+3].$

By Corollary 7, $(\bar{{\mathcal{C}}}_{f})^{\perp}$ has minimum linear
locality $d(\bar{{\mathcal{C}}}_{f})-1=q-1$. The desired conclusion then
follows from Theorem 32. ∎

The minimum linear locality of $\bar{{\mathcal{C}}}_{f}$ is given below.

######  Theorem 46.

The NMDS code $\bar{{\mathcal{C}}}_{f}$ is a $d$-optimal and $k$-optimal
$(q+3,3,q,q;2)$-LLRC.

###### Proof.

Recall we use the elements in the set $[q+3]=\\{0,1,\ldots,q+2\\}$ to index
the coordinate positions of the code $\bar{{\mathcal{C}}}_{f}$ and its dual.
Since all the codewords of weight 3 in $(\bar{{\mathcal{C}}}_{f})^{\perp}$
were characterised in [38], we outline a proof here only. Notice that the
union of the supports of all the codewords of weight 3 in
$(\bar{{\mathcal{C}}}_{f})^{\perp}$ specified in Case 1 of the proof of
Theorem 8 in [38] is $\\{0,1,\ldots,q-1,q+2\\}$, and the union of the supports
of all the codewords of weight 3 in $(\bar{{\mathcal{C}}}_{f})^{\perp}$
specified in Case 4 of the proof of Theorem 8 in [38] is $\\{q,q+1,q+2\\}$. It
then follows that

$\bigcup_{S\in{\mathcal{B}}_{3}((\bar{{\mathcal{C}}}_{f})^{\perp})}S=[q+3].$

By Corollary 7, $(\bar{{\mathcal{C}}}_{f})$ has minimum linear locality
$d((\bar{{\mathcal{C}}}_{f})^{\perp})-1=2$. The desired conclusion then
follows from Theorem 32. ∎

We remark that the NMDS code $(\bar{{\mathcal{C}}}_{f})$ is an extended
hyperoval code (see for example [12, Section 12.2]). The reader is referred to
[38] for detail.

####  V-D2 NMDS codes with parameters $[q+1,3,q-2]$ from oval polynomials

Let $f$ be a polynomial over ${\mathrm{GF}}(q)$ with $f(0)=0$ and $f(1)=1$.
Let $\alpha$ be a generator of ${\mathrm{GF}}(q)^{*}$. Define

$\displaystyle
G_{f}=\left[\begin{array}[]{llllll}f(\alpha^{0})&f(\alpha^{1})&\cdots&f(\alpha^{q-2})&0&1\\\
\alpha^{0}&\alpha^{1}&\cdots&\alpha^{q-2}&1&0\\\
1&1&\cdots&1&1&1\end{array}\right].$ (41)

Let ${\mathcal{C}}_{f}$ denote the linear code over ${\mathrm{GF}}(q)$ with
generator matrix $G_{f}$. The following result was proved in [38].

######  Theorem 47.

Let $m\geq 3$ be odd and let $f(x)$ be an oval polynomial over
${\mathrm{GF}}(q)$ with coefficients in ${\mathrm{GF}}(2)$. Then
${\mathcal{C}}_{f}$ is a $[q+1,3,q-2]$ NMDS code over ${\mathrm{GF}}(q)$ with
weight enumerator

$\displaystyle A(z)=1+(q-1)(q-2)z^{q-2}+\frac{(q-1)(q^{2}-5q+12)}{2}z^{q-1}+$
$\displaystyle(q-1)(4q-5)z^{q}+\frac{(q-1)(q^{2}-3q+4)}{2}z^{q+1}.$

This class of NMDS codes are very important to us, as they demonstrate that
some nontrivial NMDS codes ${\mathcal{C}}$ indeed have minimum linear locality
$d({\mathcal{C}}^{\perp})$ rather than $d({\mathcal{C}}^{\perp})-1$. We will
need the following lemma later.

######  Lemma 48.

Let $m\geq 3$ be odd and let $f(x)$ be an oval polynomial over
${\mathrm{GF}}(q)$ with coefficients in ${\mathrm{GF}}(2)$. Then $f(x)+x+1=0$
does not have a solution $x\in{\mathrm{GF}}(q)$.

###### Proof.

By the definition of oval polynomials, $0$ and $1$ are not not solutions of
the equation $f(x)+x+1=0$. Suppose that $f(a)+a+1=0$ for some
$a\in{\mathrm{GF}}(q)\setminus\\{0,1\\}$. Since $f(x)$ has coefficients in
${\mathrm{GF}}(2)$, we have $f(a^{2})+a^{2}+1=0$ and $f(a^{4})+a^{4}+1=0$. It
then follows from Lemma 43 that the set $\\{a,a^{2},a^{4}\\}$ has cardinality
at most $2$. If $a=a^{2}$, then $a\in\\{0,1\\}$, which contradicts to the
assumption that $a\in{\mathrm{GF}}(q)\setminus\\{0,1\\}$. If $a=a^{4}$, then
$a=0$ or $a^{3}=1$. If $a^{3}=1$, we have $a=1$ as $\gcd(3,q-1)=1$. Hence,
$a=a^{4}$ implies that $a\in\\{0,1\\}$, which contradicts to the assumption
that $a\in{\mathrm{GF}}(q)\setminus\\{0,1\\}$. If $a^{2}=a^{4}$, then
$a\in\\{0,1\\}$, which contradicts to the assumption that
$a\in{\mathrm{GF}}(q)\setminus\\{0,1\\}$. This completes the proof. ∎

######  Theorem 49.

Let $m\geq 3$ be odd and let $f(x)$ be an oval polynomial over
${\mathrm{GF}}(q)$ with coefficients in ${\mathrm{GF}}(2)$, and let
${\mathcal{C}}_{f}$ be the code in Theorem 47. Then
${\mathcal{C}}_{f}^{\perp}$ has minimum linear locality $d({\mathcal{C}})-1$
and is a $d$-optimal and $k$-optimal $(q+1,q-2,3,q;q-3)$-LLRC, and
${\mathcal{C}}_{f}$ has minimum linear locality $d({\mathcal{C}}_{f}^{\perp})$
and is an almost $d$-optimal and $k$-optimal $(q+1,3,q-2,q;3)$-LLRC.

###### Proof.

Since all the minimum weight codewords in ${\mathcal{C}}_{f}$ were not
characterized in [38], we have to do this job here. Let ${\mathbf{v}}_{1}$,
${\mathbf{v}}_{2}$ and ${\mathbf{v}}_{3}$ denote the first, second and third
rows in the generator matrix $G_{f}$ above.

We first first consider all the codewords
${\mathbf{v}}_{3}+{\mathbf{v}}_{2}+b{\mathbf{v}}_{1}$, where
$b\in{\mathrm{GF}}(q)^{*}\setminus\\{1\\}$. By definition,

${\mathbf{v}}_{3}+{\mathbf{v}}_{2}+b{\mathbf{v}}_{1}=(b,1+\alpha^{1}+bf(\alpha^{1}),\ldots,1+\alpha^{q-2}+bf(\alpha^{q-2}),0,1+b).$

For any $i$ with $1\leq i\leq q-2$, put $b=(1+\alpha^{i})/f(\alpha^{i})$. It
then follows from Lemma 48 that $b\neq 1$. Clearly, $b\neq 0$, as $\alpha$ is
a generator of ${\mathrm{GF}}(q)$. It then follows from Lemma 43 that there is
a unique $j\in\\{1,2,\ldots,q-2\\}\setminus\\{i\\}$ such that
$b=(1+\alpha^{j})/f(\alpha^{j})$. Consequently,

${\mathtt{wt}}({\mathbf{v}}_{3}+{\mathbf{v}}_{2}+b{\mathbf{v}}_{1})=q+1-3=q-2.$

The support of this codeword is

${\mathrm{suppt}}({\mathbf{v}}_{3}+{\mathbf{v}}_{2}+b{\mathbf{v}}_{1})=[q+1]\setminus\\{i,j,q-1\\}.$

The total number of such choices of $b$ is $(q-2)/2$. Since ${\mathbf{v}}_{3}$
is the all-one codeword, we have already characterized $(q-1)(q-2)/2$ minimum
weight codewords of this form in ${\mathcal{C}}_{f}$.

We then consider all the codewords
${\mathbf{v}}_{3}+a{\mathbf{v}}_{2}+{\mathbf{v}}_{1}$, where
$a\in{\mathrm{GF}}(q)^{*}\setminus\\{1\\}$. By definition,

${\mathbf{v}}_{3}+a{\mathbf{v}}_{2}+{\mathbf{v}}_{1}=(a,1+a\alpha^{1}+f(\alpha^{1}),\ldots,1+a\alpha^{q-2}+f(\alpha^{q-2}),1+a,0).$

For any $i$ with $1\leq i\leq q-2$, put $a=(1+f(\alpha^{i}))/\alpha^{i}$. It
then follows from Lemma 48 that $a\neq 1$. Clearly, $a\neq 0$, as $\alpha$ is
a generator of ${\mathrm{GF}}(q)$ and $f(1)=1$. It then follows from Lemma 43
that there is a unique $j\in\\{1,2,\ldots,q-2\\}\setminus\\{i\\}$ such that
$b=(1+f(\alpha^{j}))/\alpha^{j}$. Consequently,

${\mathtt{wt}}({\mathbf{v}}_{3}+a{\mathbf{v}}_{2}+{\mathbf{v}}_{1})=q+1-3=q-2.$

The support of this codeword is

${\mathrm{suppt}}({\mathbf{v}}_{3}+a{\mathbf{v}}_{2}+{\mathbf{v}}_{1})=[q+1]\setminus\\{i,j,q\\}.$

The total number of such choices of $a$ is $(q-2)/2$. Since ${\mathbf{v}}_{3}$
is the all-one codeword, we have already characterized $(q-1)(q-2)/2$ minimum
weight codewords of this form in ${\mathcal{C}}_{f}$.

In the first case above, the coordinate in position $q-1$ in the codewords
${\mathbf{v}}_{3}+{\mathbf{v}}_{2}+b{\mathbf{v}}_{1}$ is zero and the
coordinate in position $q$ in these codewords is nozero. In the second case
above, the coordinate in position $q-1$ in the codewords
${\mathbf{v}}_{3}+a{\mathbf{v}}_{2}+{\mathbf{v}}_{1}$ is nonzero and the
coordinate in position $q$ in these codewords is zero. Therefore, the minimum
weight codewords in the two forms do not overlap. By Theorem 47, we have
characterized all the minimum weight codewords in ${\mathcal{C}}_{f}$. From
the discussions above, we have

$\bigcup_{S\in{\mathcal{B}}_{q-2}({\mathcal{C}}_{f})}S=[q+1].$

It then follows from Corollary 7 that ${\mathcal{C}}_{f}^{\perp}$ has minimum
locality $d({\mathcal{C}}_{f})-1$.

The discussions above showed that the coordinate in position $0$ in all the
minimum weight codewords in ${\mathcal{C}}_{f}$ is nonzero. It then follows
from Lemma 34 that the coordinate in position $0$ in all the minimum weight
codewords in ${\mathcal{C}}_{f}^{\perp}$ is zero. This means that

$0\not\in\bigcup_{S\in{\mathcal{B}}_{3}({\mathcal{C}}_{f}^{\perp})}S.$

Hence, ${\mathcal{C}}_{f}$ does not have minimum linear locality
$d({\mathcal{C}}_{f}^{\perp})-1$. It then follows from Theorem 31 that
${\mathcal{C}}_{f}$ has minimum linear locality
$d({\mathcal{C}}_{f}^{\perp})$. The remaining desired conclusions then follow
from Theorems 47 and 32. ∎

The proof of Theorem 49 shows that it could be hard to determine the minimum
linear locality of an NMDS code.

####  V-D3 NMDS codes with parameters $[q+2,3,q-1]$ from oval polynomials

Let $f$ be a polynomial over ${\mathrm{GF}}(q)$ with $f(0)=0$ and $f(1)=1$.
Let $\alpha$ be a generator of ${\mathrm{GF}}(q)^{*}$. Define

$\displaystyle\bar{G}_{f}=\left[\begin{array}[]{lllllll}f(0)&f(\alpha^{0})&f(\alpha^{1})&\cdots&f(\alpha^{q-2})&0&1\\\
0&\alpha^{0}&\alpha^{1}&\cdots&\alpha^{q-2}&1&0\\\
1&1&1&\cdots&1&1&1\end{array}\right].$ (45)

By definition, $\bar{G}_{f}$ is a $3$ by $q+2$ matrix over ${\mathrm{GF}}(q)$.
Let $\bar{{\mathcal{C}}}_{f}$ denote the linear code over ${\mathrm{GF}}(q)$
with generator matrix $\bar{G}_{f}$.

The following theorem was presented in [38], but its proof was omitted in
[38].

######  Theorem 50.

Let $m\geq 3$ be odd and let $f(x)$ be an oval polynomial over
${\mathrm{GF}}(q)$ with coefficients in ${\mathrm{GF}}(2)$. Then
$\bar{{\mathcal{C}}}_{f}$ is a $[q+2,3,q-1]$ NMDS code over ${\mathrm{GF}}(q)$
with weight enumerator

$\displaystyle\bar{A}(z)=1+(q-1)(q-2)z^{q-1}+\frac{(q-1)(q^{2}-3q+14)}{2}z^{q}+$
$\displaystyle 3(q-1)(q-2)z^{q+1}+\frac{(q-1)(q^{2}-3q+4)}{2}z^{q+2}.$

######  Theorem 51.

Let $m\geq 3$ be odd and let $f(x)$ be an oval polynomial over
${\mathrm{GF}}(q)$ with coefficients in ${\mathrm{GF}}(2)$, and let
$\bar{{\mathcal{C}}}_{f}$ be the code in Theorem 50. Then
$\bar{{\mathcal{C}}}_{f}^{\perp}$ has minimum linear locality
$d({\mathcal{C}}_{f})-1$ and is a $d$-optimal and $k$-optimal
$(q+2,q-1,3,q;q-2)$-LLRC, and $\bar{{\mathcal{C}}}_{f}$ has minimum linear
locality $d(\bar{{\mathcal{C}}}_{f}^{\perp})$ and is an almost $d$-optimal and
$k$-optimal $(q+2,3,q-1,q;3)$-LLRC.

###### Proof.

The proof is similar to that of Theorem 49 and is omitted here. However, we
inform the reader that the coordinates in positions $0$ and $1$ in all the
minimum weight codewords in $\bar{{\mathcal{C}}}_{f}$ are always nonzero. This
means that

$\\{0,1\\}\bigcap\bigcup_{S\in{\mathcal{B}}_{3}(\bar{{\mathcal{C}}}_{f}^{\perp})}S=\emptyset.$

To prove this theorem, one has to characterize all the minimum weight
codewords in $\bar{{\mathcal{C}}}_{f}$. ∎

Notice that Theorem 49 documents the second class of nontrivial linear codes
${\mathcal{C}}$ with minimum linear locality more than
$d({\mathcal{C}}^{\perp})-1$.

###  V-E The minimum linear locality of other NMDS codes

The following result says that other infinite families of NMDS codes do exist.

######  Theorem 52 ([36]).

Algebraic geometric $[n,k,n-k]$ NMDS codes over ${\mathrm{GF}}(q)$, $q=p^{m}$,
do exist for every $n$ with

$\displaystyle n\leq\left\\{\begin{array}[]{ll}q+\lceil 2\sqrt{q}\rceil&\mbox{
if $p$ divides $\lceil 2\sqrt{q}\rceil$ and $m$ is odd,}\\\ q+\lceil
2\sqrt{q}\rceil+1&\mbox{ otherwise,}\end{array}\right.$

and arbitrary $k\in\\{2,3,\ldots,n-2\\}$.

Many NMDS codes have been constructed (see, for example, [1, 2, 10, 15, 16,
17, 18, 19, 24, 29, 37, 38, 36]). It is valuable to check which of the NMDS
codes ${\mathcal{C}}$ have minimum linear locality
$d({\mathcal{C}}^{\perp})-1$, as they are $d$-optimal and $k$-optimal LLRCs.
It has been observed that the analysis of the minimum linear locality of a
linear code is harder than the determination of the minimum distance of the
dual code.

##  VI Summary and concluding remarks

The objectives of this paper are to develop some general theory for the
minimum linear locality of linear codes and search for $d$-optimal or
$k$-optimal LLRCs in known families of linear codes. Below is a summary of the
major general results on the minimum linear locality of nontrivial linear
codes developed in this paper.

  1. 1.

We proved that every nontrivial linear code has a minimum linear locality and
showed how to find it (see Theorem 6).

  2. 2.

We gave a necessary and sufficient condition for a nontrivial linear code
${\mathcal{C}}$ to have the minimum linear locality
$d({\mathcal{C}}^{\perp})-1$ (see Corollary 7).

  3. 3.

We determined the minimum linear locality for nontrivial linear codes
${\mathcal{C}}$ such that the minimum weight codewords in
${\mathcal{C}}^{\perp}$ support a $1$-design (see Corollary 9). This general
result has settled the minimum linear locality of many families of linear
codes, as many families of linear codes support $1$-designs.

  4. 4.

We determined the minimum linear locality for nontrivial linear codes
${\mathcal{C}}$ whose automorphism group is transitive (see Corollary 10).
This general result has settled the minimum linear locality of many families
of linear codes, including the affine-invariant linear codes.

  5. 5.

We determined the minimum linear locality of
$(\overline{{\mathcal{C}}})^{\perp}$ under the condition that
$d(\overline{{\mathcal{C}}})=d({\mathcal{C}})+1$ for each nontrivial linear
code ${\mathcal{C}}$ (see Theorem 13), and settled the minimum linear locality
of $(\overline{{\mathcal{C}}})^{\perp}$ for each nontrivial binary linear code
${\mathcal{C}}$ (see Corollary 14).

  6. 6.

We proved that the minimum linear locality of an NMDS code ${\mathcal{C}}$ is
either $d({\mathcal{C}}^{\perp})-1$ or $d({\mathcal{C}}^{\perp})$ (see Theorem
31), and further proved that ${\mathcal{C}}$ is either a $d$-optimal and
$k$-optimal or an almost $d$-optimal and $k$-optimal LLRC (see Theorem 32).

These general results have settled the minimum linear locality of many
families of nontrivial linear codes. Furthermore, the minimum linear locality
of these codes was not studied in the literature. Hence, we have reached our
first objective.

After studying a number of families of known linear codes with the general
theory developed, we have found many classes of optimal LLRCs. These optimal
LLRCs were not reported in the literature. Table I lists fourteen classes of
$k$-optimal LLRCs. Table II lists nineteen classes of LLRCs which are both
$d$-optimal and $k$-optimal and have different parameters. In both tables,

  * •

$n_{h}=(q^{m}-1)/(q-1)$,

  * •

$\surd$ means that the code is optimal with the Singleton-like or CM bound,

  * •

$A$ means that the code is almost optimal with respect to the Singleton-like
bound, and

  * •

$?$ means that the optimality is open.

These classes of optimal LLRCs demonstrate that we have reached our second
objective.

We remark that the locality of locally recoverable codes in the literature
actually is the linear locality, but may not be the minimum linear locality.
This paper has treated the minimum linear locality of nontrivial linear codes.
Availability is another interesting parameter of LLRCs. All the LLRCs
presented in this paper naturally have availability $1$, and some of them may
have availability $2$ or more. It is extremely hard to develop general theory
for LLRCs with availability more than $1$, although such LLRCs are available
in the literature. To study the maximum availability of an LLRC code
${\mathcal{C}}$ with respect to the minimum linear locality
$d({\mathcal{C}}^{\perp})-1$, one has to characterize the minimum weight
codewords in ${\mathcal{C}}^{\perp}$. This is a very hard problem in general.
The reader is cordially invited to investigate the maximum availability of
these optimal LLRCs documented in this paper. Finally, we point out that all
the LLRCs presented in this paper are from known linear codes in the
literature and our objective is to study their minimum linear locality and
optimality with respect to the Singleton-like and CM bounds.

TABLE I: Some $k$-optimal LLRCs from known codes ${\mathcal{C}}$ | $n$ | $k$ | $d$ | $r$ | $d_{opt}$ | $k_{opt}$
---|---|---|---|---|---|---
${\mathcal{H}}_{(q,m)}$ | $n_{h}$ | $n_{h}-m$ | $3$ | $q^{m-1}-1$ | $?$ | $\surd$
${\mathcal{S}}_{(q,m)}$ | $n_{h}$ | $m$ | $q^{m-1}$ | $2$ | $?$ | $\surd$
$({\mathcal{H}}_{(q,m)})_{\\{t_{1}\\}}$ | $n_{h}-1$ | $n_{h}-m-1$ | $3$ | $q^{m-1}-2$ | $?$ | $\surd$
$(({\mathcal{H}}_{(q,m)})_{\\{t_{1}\\}})^{\perp}$ | $n_{h}-1$ | $m$ | $q^{m-1}-1$ | $2$ | $?$ | $\surd$
$({\mathcal{S}}_{(q,m)})_{\\{t_{1}\\}}$ | $n_{h}-1$ | $m-1$ | $q^{m-1}$ | $1$ | $?$ | $\surd$
$(({\mathcal{S}}_{(q,m)})_{\\{t_{1}\\}})^{\perp}$ | $n_{h}-1$ | $n_{h}-m$ | $2$ | $q^{m-1}-1$ | $?$ | $\surd$
${\mathcal{R}}_{q}(1,m)$ | $q^{m}$ | $m+1$ | $(q-1)q^{m-1}$ | $2$ | $?$ | $\surd$
${\mathcal{R}}_{q}(1,m)^{\perp}$ | $q^{m}$ | $q^{m}-m-1$ | $3$ | $q^{m}-q^{m-1}-1$ | $?$ | $\surd$
${\mathcal{C}}_{f}$ (Thm. 49) | $2^{m}+1$ | $3$ | $2^{m}-2$ | $3$ | $A$ | $\surd$
$\bar{{\mathcal{C}}}_{f}$ (Thm. 51) | $2^{m}+2$ | $3$ | $2^{m}-1$ | $3$ | $A$ | $\surd$
${\mathcal{C}}_{o}$ | $q^{2}+1$ | $4$ | $q^{2}-q$ | $3$ | $?$ | $\surd$
$({\mathcal{C}}_{o})_{\\{t_{1}\\}}$ | $q^{2}$ | $3$ | $q^{2}-q$ | $2$ | $?$ | $\surd$
$({\mathcal{C}}_{o})^{\\{t_{1}\\}}$ | $q^{2}$ | $4$ | $q^{2}-q-1$ | $3$ | $?$ | $\surd$
${\mathcal{C}}({\mathcal{A}})$ (Thm. 29) | $n$ | $3$ | $n-h$ | $2$ | $?$ | $\surd$
TABLE II: Both $d$-optimal and $k$-optimal LLRCs from known codes ${\mathcal{C}}$ | $n$ | $k$ | $d$ | $r$ | $d_{opt}$ | $k_{opt}$
---|---|---|---|---|---|---
${\mathcal{H}}_{(q,3)}$ | $q^{2}+q+1$ | $q^{2}+q-2$ | $3$ | $q^{2}-1$ | $\surd$ | $\surd$
$({\mathcal{H}}_{(q,3)})_{\\{t_{1}\\}}$ | $q^{2}+q$ | $q^{2}+q-3$ | $3$ | $q^{2}-2$ | $\surd$ | $\surd$
$(({\mathcal{S}}_{(q,3)})_{\\{t_{1}\\}})^{\perp}$ | $q^{2}+q$ | $q^{2}+q-2$ | $2$ | $q^{2}-1$ | $\surd$ | $\surd$
${\mathcal{C}}_{o}^{\perp}$ | $q^{2}+1$ | $q^{2}-3$ | $4$ | $q^{2}-q-1$ | $\surd$ | $\surd$
$({\mathcal{C}}_{o}^{\perp})_{\\{t_{1}\\}}$ | $q^{2}$ | $q^{2}-4$ | $4$ | $q^{2}-q-2$ | $\surd$ | $\surd$
$({\mathcal{C}}_{o}^{\perp})^{\\{t_{1}\\}}$ | $q^{2}$ | $q^{2}-3$ | $3$ | $q^{2}-q-1$ | $\surd$ | $\surd$
${\mathcal{C}}({\mathcal{A}})^{\perp}$ (Thm. 29) | $n$ | $n-3$ | $3$ | $n-h-1$ | $\surd$ | $\surd$
${\mathcal{C}}_{(3^{s},3^{s}+1,3,1)}$ | $3^{s}+1$ | $3^{s}-3$ | $4$ | $3^{s}-4$ | $\surd$ | $\surd$
${\mathcal{C}}_{(3^{s},3^{s}+1,3,1)}^{\perp}$ | $3^{s}+1$ | $4$ | $3^{s}-3$ | $3$ | $\surd$ | $\surd$
${\mathcal{C}}_{(2^{s},2^{s}+1,3,1)}$ | $2^{s}+1$ | $2^{s}-3$ | $4$ | $2^{s}-4$ | $\surd$ | $\surd$
${\mathcal{C}}_{(2^{s},2^{s}+1,3,1)}^{\perp}$ | $2^{s}+1$ | $4$ | $2^{s}-3$ | $3$ | $\surd$ | $\surd$
${\mathcal{C}}_{(2^{s},2^{s}+1,4,1)}$ | $2^{s}+1$ | $2^{s}-5$ | $6$ | $2^{s}-6$ | $\surd$ | $\surd$
${\mathcal{C}}_{(2^{s},2^{s}+1,4,1)}^{\perp}$ | $2^{s}+1$ | $6$ | $2^{s}-5$ | $5$ | $\surd$ | $\surd$
${\mathcal{C}}_{f}^{\perp}$ (Thm. 49) | $2^{m}+1$ | $2^{m}-2$ | $3$ | $2^{m}-3$ | $\surd$ | $\surd$
$\bar{{\mathcal{C}}}_{f}^{\perp}$ (Thm. 51) | $2^{m}+2$ | $2^{m}-1$ | $3$ | $2^{m}-2$ | $\surd$ | $\surd$
$\bar{{\mathcal{C}}}_{f}^{\perp}$ (Thm. 45) | $2^{m}+3$ | $2^{m}$ | $3$ | $2^{m}-1$ | $\surd$ | $\surd$
$\bar{{\mathcal{C}}}_{f}$ (Thm. 46) | $2^{m}+3$ | $3$ | $2^{m}$ | $2$ | $\surd$ | $\surd$
$(\overline{{\mathcal{C}}_{(2^{s},2^{s}+1,3,1)}})^{\perp}$ (Thm 41) | $2^{s}+2$ | $5$ | $2^{s}-3$ | $4$ | $\surd$ | $\surd$
$(\overline{{\mathcal{C}}_{(3^{s},3^{s}+1,3,1)}})^{\perp}$ (Thm 40) | $3^{s}+2$ | $5$ | $3^{s}-3$ | $4$ | $\surd$ | $\surd$

## References

  * [1] V. Abatangelo, B. Larato, “Near-MDS codes arising from algebraic curves,” _Discr. Math._ , vol. 301, pp. 5–19, 2005.
  * [2] V. Abatangelo, B. Larato, “Elliptic near-MDS codes over $\mathbf{F}_{5}$,” _Des. Codes Cryptgr._ , vol. 46, pp. 167–174, 2008.
  * [3] E. F. Assmus Jr., J. D. Key, “Polynomial codes and finite geometries,” In: Pless V.S., Huffman W.C. (eds.) Handbook of Coding Theory, vol. II, pp. 1269–1343. Elsevier, Amsterdam, 1998.
  * [4] E. F. Assmus Jr., H. F. Mattson Jr., “New 5-designs,” _J. Comb. Theory_ , vol. 6, no. 2, pp. 122–151, March 1969.
  * [5] V. R. Cadambe, A. Mazumdar, “An upper bound on the size of locally recoverable codes,” In International Symposium on Network Coding, NetCod 2013, Calgary, AB, Canada, June 7-9, 2013, pp. 1–5, 2013.
  * [6] V. R. Cadambe, A. Mazumdar, “Bounds on the size of locally recoverable codes,” IEEE Trans. Information Theory, vol. 61, no. 11, pp. 5787–5794, 2015.
  * [7] H. Cai, M. Cheng, C. Fan, X. Tang, “Optimal locally repairable systematic codes based on packings,” _IEEE Trans. Inf. Theory_ , vol. 67, no. 1, pp. 39–49, Jan. 2019.
  * [8] H. Cai, C. Fan, Y. Miao, M. Schwartz, X. Tang, “Optimal locally repairable codes: an improved bound and constructions,” arXiv:2011.04966v1 [cs.IT].
  * [9] B. Chen, J. Chen, “A construction of optimal $(r,\delta)$-locally recoverable codes,” _IEEE Access_ , vol. 7, pp. 180349–180353, Dec. 2019.
  * [10] M. A. de Boer, “Almost MDS codes,” _Des. Codes Cryptogr.,_ vol. 9, 143–155, 1996.
  * [11] C. Ding, _Codes from Difference Sets_ , World Scientific, Singapore, 2015.
  * [12] C. Ding, _Designs from Linear Codes_ , World Scientific, Singapore, 2018.
  * [13] C. Ding, Z. Heng, “The subfield codes of ovoid codes,” IEEE Trans. Inf. Theory, vol. 65, no. 8, pp. 4715–4729, August 2019.
  * [14] C. Ding, C. Tang, “Infinite families of near MDS codes holding $t$-designs,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 9, pp. 5419–5428, Sep. 2020.
  * [15] S. Dodunekov and I. Landgev, “On near-MDS codes,” J. Geometry, vol. 54, nos. 1–2, pp. 30–43, Nov. 1995.
  * [16] S. Dodunekov, I. Landgev, “On near-MDS codes,” _J. Geometry_ , vol. 54, pp. 30–43, 1995.
  * [17] S. M. Dodunekov, I. N. Landjev, “Near-MDS codes over some small fields,” _Discrete Math._ , vol. 213, nos. 1-3, pp. 55–65, February 2000.
  * [18] A. Faldum, W. Willems, “Codes of small defect,” _Des. Codes Cryptogr._ , vol. 10, pp. 341–350, March 1997.
  * [19] M. Giulietti, “On the extendibility of near-MDS elliptic codes,” _AAECC_ , vol. 15, pp. 1–11, 2004.
  * [20] P. Gopalan, C. Huang, H. Simitci, S. Yekhanin, “On the locality of codeword symbols,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 11, pp. 6925–6934, 2012.
  * [21] M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes,” Online available at http://www.codetables.de, 2007, accessed on 2021-01-07.
  * [22] P. Huang, E. Yaakobi, H. Uchikawa, P. H. Siegel, “Binary linear locally repairable codes,” _IEEE Trans. Inf. Theory,_ vol. 62, no. 11, pp. 6268–6283, Nov. 2016.
  * [23] W. C. Huffman, V. Pless, _Fundamentals of Error-Correcting Codes_ , Cambridge University Press, Cambridge, 2003.
  * [24] L. Jin, H. Kan, “Self-dual near MDS codes from elliptic curves,” _IEEE Trans. Inf. Theory,_ vol. 65, no. 4, pp. 2166–2170, 2019.
  * [25] L. Jin, H. Kan, Y. Zhang, “Constructions of locally repairable codes with multiple recovering sets via rational function fields,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 1, pp. 202–209, Jan. 2020.
  * [26] Y. Liu, C. Ding, C. Tang, “Shortened linear codes over finite fields,” arXiv:2007.05901v1 [cs.IT], 2020.
  * [27] J. Liu, S. Mesnager, D. Tang, “Constructions of optimal locally recoverable codes via Dickson polynomials,” _Des. Codes Cryptogr._ , vol. 88, no. 2, pp. 1759–1780, 2020.
  * [28] Y. Luo, C. Xing, C. Yuan, “Optimal locally repairable codes of distance 3 and 4 via cyclic codes,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 2, pp. 1048–1053, Feb. 2019.
  * [29] S. Marcugini, A. Milani, F. Pambianco, “NMDS codes of maximum length over $\mathbf{F}_{q}$, $8\leq q\leq 11,$”, _IEEE Trans. Inf. Theory,_ vol. 48, no. 4, pp. 963–966, 2002.
  * [30] A. Maschietti, “Difference set and hyperovals,” _Des. Codes Cryptogr._ , vol. 14, pp. 89–98, 1998.
  * [31] G. Micheli, “Constructions of locally recoverable codes which are optimal,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 1, pp. 167–175, Jan. 2020
  * [32] I. Tamo, A. Barg, “A family of optimal locally recoverable codes,” _IEEE Trans. Inf. Theory,_ vol. 60, no. 8, pp. 4661–4676, Aug. 2014.
  * [33] P. Tan, Z. Zhou, V. Sidorenko, U. Parampalli, “Two classes of optimal LRCs with information $(r,t)$-locality,” _Des. Codes Cryptogr._ , vol. 88, pp. 1741–1757, 2020.
  * [34] C. Tang, C. Ding, “An infinite family of linear codes supporting $4$-designs,” IEEE Trans. Inf. Theory, vol. 67, no. 1, pp. 244–254, Jan. 2021.
  * [35] C. Tang, C. Ding, M. Xiong, “Codes, differentially $\delta$-uniform functions and $t$-designs,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 6, pp. 3691–3703, June 2020.
  * [36] M. A. Tsfasmann, S. G. Vladut, _Algebraic-Geometry Codes_ , Kluwer, Dordrecht, 1991.
  * [37] H. Tong, Y. Ding, “Quasi-cyclic NMDS codes,” _Finite Fields and Their Applications_ , vol. 24, pp. 45–54, 2013.
  * [38] Q. Wang, Z. Heng, “Near MDS codes from overal polynomials,” _Disc. Math._ , vol. 344, no. 4, April 2021.
  * [39] A. Wang, Z. Zhang, M. Liu, “Achieving arbitrary locality and availability in binary codes,” in: _Proceedings of ISIT 2016_ , pp. 1866–1870, IEEE, 2015.
  * [40] C. Xing, C. Yuan, “Construction of optimal locally recoverable codes and connection with hypergraph,” In: _Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)_ , pp. 98:1–98:13, 2019.