affil0affil0affiliationtext: Department of Mathematics and Computer Science
Eindhoven University of Technology, the Netherlands

# LRCs: Duality, LP Bounds, and Field Size

Anina Gruica  Benjamin Jany  Alberto Ravagnani

###### Abstract

We develop a duality theory of locally recoverable codes (LRCs) and apply it
to establish a series of new bounds on their parameters. We introduce and
study a refined notion of weight distribution that captures the code’s
locality. Using a duality result analogous to a MacWilliams identity, we then
derive an LP-type bound that improves on the best known bounds in several
instances. Using a dual distance bound and the theory of generalized weights,
we obtain non-existence results for optimal LRCs over small fields. In
particular, we show that an optimal LRC must have both minimum distance and
block length relatively small compared to the field size.

##  1 Introduction

In the last decade, locally recoverable codes have been a central topic in
communication and distributed storage [4, 6, 8, 13, 22]. A code has good
locality properties when each entry of each codeword can be recovered from a
small set of other entries of the same codeword. This property is captured by
a parameter of the underlying code called locality. Small locality allows, for
instance, a fast recovery process when the code is used for distributed
storage. Ideally, a code has both small locality and large minimum distance,
as the latter offers protection from errors and erasures.

Most of the research on locally recoverable codes focuses on bounds [1, 4, 8,
11, 13], constructions and decoding [2, 3, 17, 22]. This paper pertains to the
former line of research.

As one expects, a code cannot have all the desirable properties at the same
time. In particular, it cannot have arbitrarily small locality while having
large minimum distance for the given dimension and block length. The trade-
offs among all these parameters are captured by various bounds, the best known
of which is probably the Generalized Singleton Bound [8]. Codes attaining this
bound with equality are known to exist for some parameter sets over large
fields. Over small fields, it is still a wide open questions which parameters
locally recoverable codes can have.

In this paper, we investigate two aspects of the theory of locally recoverable
codes that have overall been neglected so far, namely their duality theory and
field size.

We first demonstrate that duality results, besides being mathematically
interesting, represent a very powerful tool for investigating the parameters
of locally recoverable codes and establishing new bounds. In the second part
of the paper we derive various results that link the size of the underlying
field to the other parameters of a locally recoverable code. In particular, we
prove that codes attaining the Generalized Singleton Bound of [8] cannot exist
for some parameter sets.

The rest of the introduction briefly illustrates the contributions made by
this paper, pointing the reader to the relevant sections.

After recalling the basics of locally recoverable codes in Section 2, we
introduce a refined notion of weight distribution of a code, which is able to
capture its locality as well as the weights of the codewords; see Section 3.
In the same section, we then establish a duality result for the refined weight
distribution, which is similar to, and yet different from, a MacWilliams
identity. The identity combined with linear programming produces a bound on
the parameters of a locally recoverable code that improves the best bounds
currently available for several parameter sets; see Section 4. We illustrate
this with comparison tables.

The last part of the paper, namely Section 5, is devoted to the role played by
the field size in the theory of locally recoverable codes. We propose various
arguments based on the notions of dual distance and generalized weights. This
leads us to establishing new bounds for the parameters of a locally
recoverable code, which in turn gives us non-existence results for codes
meeting the Generalized Singleton Bound over small fields.

### Acknowledgements.

We are grateful to Markus Grassl for discussing with us the connection between
the results of this paper and the split weight enumerator of a code. A. G. is
supported by the Dutch Research Council through grant OCENW.KLEIN.539. B. J.
is supported by the Dutch Research Council through grant VI.Vidi.203.045. A.
R. is supported by the Dutch Research Council through grants VI.Vidi.203.045,
OCENW.KLEIN.539, and by the Royal Academy of Arts and Sciences of the
Netherlands.

##  2 Locally Recoverable Codes

We start by recalling concepts of classical coding theory and locally
recoverable codes, and by establishing the notation. Throughout the paper,
$n\geq 2$ is an integer, $q$ denotes a prime power, and $\mathbb{F}_{q}$ is
the finite field of $q$ elements. We will denote the set $\\{1,\dots,n\\}$ by
$[n]$.

######  Definition 2.1.

A (linear) code is an $\mathbb{F}_{q}$-linear subspace
$\mathscr{C}\leq\mathbb{F}_{q}^{n}$ endowed with the Hamming metric. The dual
of $\mathscr{C}$ is $\mathscr{C}^{\perp}:=\\{x\in\mathbb{F}_{q}^{n}:x\cdot
y^{\top}=0\textnormal{ for all }y\in\mathscr{C}\\}.$ Moreover, we say that
$\mathscr{C}\leq\mathbb{F}_{q}^{n}$ is non-degenerate if there is no $i\in[n]$
for which each $x\in\mathscr{C}$ has $x_{i}=0$. The codes $\\{0\\}$ and
$\mathbb{F}_{q}^{n}$ are called trivial.

In this document, by “code” we always mean “non-trivial code”, unless
otherwise specified.

######  Definition 2.2.

The minimum distance of a code $\mathscr{C}$ is defined as

$\displaystyle
d(\mathscr{C}):=\min\\{\omega^{\textnormal{H}}(x):x\in\mathscr{C}\setminus\\{0\\}\\},$

where $\omega^{\textnormal{H}}(x):=|\\{i\,:\,x_{i}\neq 0\\}|$ is the (Hamming)
weight of $x$.

A large minimum distance guarantees the error detection and correction
capabilities of a code, so naturally one wants this parameter to be as large
as possible. However, as it is well known, there is a trade-off between the
minimum distance and the dimension of a code with given length. This trade-off
is expressed by the famous _Singleton Bound_ , which says that for a code
$\mathscr{C}\leq\mathbb{F}_{q}^{n}$ we always have $d(\mathscr{C})\leq
n-\dim_{\mathbb{F}_{q}}(\mathscr{C})+1$; see [21]. Codes that meet the bound
with equality are called MDS. It remains a wide open problem in coding theory
to determine when codes achieving this bound (or other bounds) exist.

Apart from the minimum distance and the dimension, in this paper we consider
an additional parameter for linear codes, called _locality_.

######  Definition 2.3.

A code $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ has locality $r$ if for every
$i\in\\{1,\ldots,n\\}$ there exists a set $S_{i}\subseteq[n]$, called a
recovery set for (the coordinate) $i$, with the following properties:

  * 1)

$i\notin S_{i}$,

  * 2)

$|S_{i}|\leq r$,

  * 3)

if $x,y\in\mathscr{C}$ and $x_{j}=y_{j}$ for all $j\in S_{i}$, then
$x_{i}=y_{i}$.

We call LRC (locally recoverable code) a code for which the locality parameter
is considered.

######  Example 2.4.

Let $\mathscr{C}\leq\mathbb{F}_{2}^{7}$ be the binary simplex code of
dimension 3, which consists of codewords of the form

$\displaystyle(u_{1},u_{2},u_{3})\begin{pmatrix}1&0&0&1&0&1&1\\\
0&1&0&1&1&0&1\\\
0&0&1&0&1&1&1\end{pmatrix}=(u_{1},u_{2},u_{3},u_{1}+u_{2},u_{2}+u_{3},u_{1}+u_{3},u_{1}+u_{2}+u_{3}),$

where $u_{1},u_{2},u_{3}\in\mathbb{F}_{2}$. Without loss of generality, we
focus on recovering coordinate $i=1$. It is not hard to check that recovery
sets for 1 are

$\displaystyle\\{2,4\\},\,\\{3,6\\},\,\\{5,7\\},\,\\{2,3,7\\},\,\\{4,6,7\\},\,\\{3,4,5\\},\,\\{2,5,6\\}$

as well as any subset of $\\{2,\dots,7\\}$ containing one of the above. By
symmetry of the coordinates, this code has (minimum) locality 2.

As the name suggests, a recovery set $S_{i}$ for $i$ allows to recover the
coordinate $x_{i}$ of any codeword $x\in\mathscr{C}$ using only the
coordinates of $x$ indexed by $S_{i}$. This is done via a recovery function
$f_{i}:\pi_{S_{i}}(\mathscr{C})\rightarrow\mathbb{F}_{q}$ that satisfies
$f_{i}(\pi_{S_{i}}(x))=x_{i}$ for all $x\in\mathscr{C}$, where $\pi_{S_{i}}$
denotes the projection map onto the coordinates indexed by the elements of
$S_{i}$. Interestingly, for linear codes the recovery functions must be
linear; see [1, Lemma 10].

######  Proposition 2.5.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a code and let $S_{i}$ be a
recovery set for the coordinate $i$ with recovery function $f_{i}$. Then
$f_{i}$ is an $\mathbb{F}_{q}$-linear map.

Similarly to classical codes, it is important to understand the trade-offs
between the locality parameter and other parameters of the code, such as its
minimum distance and dimension. In [8], the authors showed how locality
impacts the dimension of an LRC by establishing a generalization of the
Singleton Bound.

######  Theorem 2.6 (Generalized Singleton Bound).

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a code with locality $r$, dimension
$k$, and minimum distance $d$. Then

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

Note that the bound of Theorem 2.6 coincides with the classical Singleton
Bound if $k=r$. Codes whose parameters meet the bound (2.1) with equality are
called optimal LRC. Note that the simplex code in Example 5.3 is optimal.

In [22], a construction of optimal LRC was given for $q\geq n$, $r\mid k$, and
$r+1\mid n$. However, if these divisibility constraints are not satisfied or
if $q<n$, optimal LRC do not always exist or have not been found yet. In order
to establish or exclude the existence of optimal LRCs for small $q$, it is
natural to establish bounds linking the locality to the size of the underlying
field. The following is a shortening bound established in [4], that improves
the Singleton-type bound in Theorem 2.6. In the minimum we include the
(trivial) case $t=0$, even though the original statement does not. Note that
for some parameters the minimum is indeed attained by $t=0$.

######  Theorem 2.7 (Shortening Bound).

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a code with locality $r$, dimension
$k$ and minimum distance $d$. We have

$k\leq\min_{t\in\mathbb{Z}_{\geq
0}}\left\\{rt+k_{\textnormal{opt}}^{(q)}(n-t(r+1),d)\right\\},$ (2.2)

where $\smash{k_{\textnormal{opt}}^{(q)}(n,d)}$ is the largest possible
dimension of a code of length $n$ and minimum distance $d$ over
$\mathbb{F}_{q}$.

######  Remark 2.8.

  * (i)

It was observed in [13] that (2.2) yields a series of bounds on codes with
locality, by applying known bounds on
$k_{\textnormal{opt}}^{(q)}(n-t(r+1),d)$. For example, by letting
$t=\left\lceil k/r\right\rceil$ and using the classical Singleton Bound on
$k_{\textnormal{opt}}^{(q)}(n-t(r+1),d)$, we recover Theorem 2.6.

  * (ii)

Even though the bound of Theorem 2.7 is a refinement of Theorem 2.6, there is
a “computational” drawback in evaluating it. Indeed, determining the value of
$k_{\textnormal{opt}}^{(q)}(n,d)$ for given $d,n,q$ is a wide open problem in
classical coding theory, which means that no closed formula is known for the
RHS of (2.2). Establishing bounds whose evaluation is computationally feasible
has therefore become a crucial research problem in the study of LRCs. This is
one of the problems this paper addresses.

The concept of locally recoverable codes was further generalized in [18],
where the authors introduce the notion of $(r,\delta)$-LRC. The additional
parameter $\delta$ provides extra information regarding the number of recovery
sets for coordinate $i$ of size less than or equal to $r$. In the
applications, $(r,\delta)$-LRCs facilitate the local recovery of a failed node
in the event that other nodes of the network fail as well.

######  Definition 2.9.

A non-degenerate code $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ has locality
$(r,\delta)$ (or is $(r,\delta)$-LRC) if for all $i\in[n]$ there exists a set
$S_{i}\subseteq[n]$ such that:

  * 1)

$i\notin S_{i}$,

  * 2)

$|S_{i}|\leq r+\delta$,

  * 3)

$d(\pi_{S_{i}\cup\\{i\\}}(\mathscr{C}))\geq\delta$.

We then call $S_{i}$ an $(r,\delta)$-recovery set for $i$.

Note that for an $(r,\delta)$-LRC $\mathscr{C}\leq\mathbb{F}_{q}^{n}$, an
$(r,\delta)$-recovery set $S_{i}$ for $i\in[n]$, and $T\subseteq
S_{i}\cup\\{i\\}$ with $|T|=\delta-1$, the coordinates of any
$x\in\mathscr{C}$ indexed by $T$ can be recovered from the coordinates of $x$
indexed by $\left(S_{i}\cup\\{i\\}\right)\setminus T$. This follows from
Definition 2.9, part 3). Moreover, it can easily be seen that the notions of
$(r,\delta)$-LRC and LRC with locality $r$ coincide when $\delta=2$.

A refinement of Theorem 2.6 taking the parameter $\delta$ into account was
established in [18] and it reads as follows:

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

Furthermore, the following is a generalization of Theorem 2.7 which was
established in [9, 19]:

$k\leq\min_{t\in\mathbb{Z}_{\geq
0}}\\{tr+k_{\textnormal{opt}}^{(q)}(n-t(r+\delta-1),d)\\}.$ (2.4)

Similarly to Theorem 2.7, the bound of (2.4) has a computational drawback, as
already explained in Remark 2.8.

Note that both (2.1) and (2.2) can be recovered by the two previous bounds
when $\delta=2$.

In this paper, we focus mostly on classical LRCs (i.e. $\delta=2)$. However,
in some instances we consider the broader case of $(r,\delta)$-LRCs for any
$\delta$, when the techniques we develop are applicable.

##  3 A Finer Weight Distribution and Duality

In this section, we introduce and work with a refinement of the classical
weight distribution of a code. Recall that the weight distribution of
$\mathscr{C}\leq\mathbb{F}_{q}^{n}$ is the tuple
$(W_{0}(\mathscr{C}),\dots,W_{n}(\mathscr{C}))$, where

$\displaystyle
W_{i}(\mathscr{C}):=|\\{x\in\mathscr{C}:\omega^{\textnormal{H}}(x)=i\\}|.$

Before we introduce the aforementioned refinement of the weight distribution,
we show how the locality of a code $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ can be
captured by looking at the support of codewords in the dual code
$\mathscr{C}^{\perp}$. Recall that for a vector $x\in\mathbb{F}_{q}^{n}$, its
support is defined to be the set $\sigma(x):=\\{i\mid x_{i}\neq 0\\}$. We now
have the following equivalent characterization of the locality parameter,
which will be used extensively in this paper.

######  Lemma 3.1.

Let $r\geq 1$ be an integer. A linear code $\mathscr{C}\leq\mathbb{F}_{q}^{n}$
has locality $r$ if and only if for any $i\in[n]$ there exists
$x\in\mathscr{C}^{\perp}$ with $i\in\sigma(x)$ and
$\omega^{\textnormal{H}}(x)\leq r+1$.

Lemma 3.1 was first established in [11, Lemma 5] and heavily relies on the
fact that recovery functions for linear codes are always linear; see
Proposition 2.5. The characterization of Lemma 3.1 inspires the following
definition, where instead of caring only about how many codewords of a certain
weight there are (which is captured in the classical weight distribution), we
want to know the number of codewords of a certain weight having a certain
subset of $[n]$ in their support.

######  Definition 3.2.

For a code $\mathscr{C}\leq\mathbb{F}_{q}^{n}$, a set $S\subseteq[n]$, and
$0\leq i\leq n$, we let

$\displaystyle
W_{i}^{S}(\mathscr{C}):=|\\{x\in\mathscr{C}:\omega^{\textnormal{H}}(x)=i,\,S\subseteq\sigma(x)\\}|.$

Note that if we set $S=\emptyset$, then the refined weight distribution
introduced in Definition 3.2 recovers the classical weight distribution. The
main result of this section is a MacWilliams-type identity for the refined
weight distribution. In more detail, we will show that the refined weight
distribution of the dual code fully determines the refined weight distribution
of the original code.

We start with the following result, which relates values of the refined weight
distributions to one another.

######  Lemma 3.3.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ and $A\subseteq[n]$. Then for all
$1\leq i\leq n$ and $|A|\leq t\leq i$ we have

$W_{i}^{A}(\mathscr{C})=\frac{1}{{\binom{i-|A|}{t-|A|}}}\sum_{\begin{subarray}{c}A\subseteq
S\subseteq[n]\\\ |S|=t\end{subarray}^{\,}}W_{i}^{S}(\mathscr{C}).$

###### Proof.

Let $\mathscr{V}=\\{(x,S)\mid
x\in\mathscr{C},\,\omega^{\textnormal{H}}(x)=i,\,A\subseteq
S\subseteq\sigma(x),\,|S|=t\\}$. We count the elements of $\mathscr{V}$ in two
ways. On one hand, we have

$\displaystyle|\mathscr{V}|=\sum_{\begin{subarray}{c}A\subseteq
S\subseteq[n]\\\ |S|=t\end{subarray}^{\,}}W_{i}^{S}(\mathscr{C}).$ (3.1)

On the other hand,

$\displaystyle|\mathscr{V}|=\sum_{\begin{subarray}{c}x\in\mathscr{C}\\\
\omega^{\textnormal{H}}(x)=i\\\
A\subseteq\sigma(x)\end{subarray}}|\\{S\,:\,A\subseteq
S\subseteq\sigma(x)\textup{ and }|S|=t\\}|={i-|A|\choose
t-|A|}W_{i}^{A}(\mathscr{C}).$ (3.2)

Combining (3.1) and (3.2) concludes the proof. ∎

In order to obtain the MacWilliams-type identity for the refined weight
distribution from Definition 3.2, we need to introduce auxiliary definitions
and results.

######  Definition 3.4.

For a code $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ and subsets $S\subseteq
T\subseteq[n]$, let

$\displaystyle\mathscr{C}(S,T):=\\{x\in\mathscr{C}:S\subseteq\sigma(x),\,x\in\mathscr{C}(T)\\},$

where $\mathscr{C}(T)$ denotes the shortening of $\mathscr{C}$ by the set $T$,
i.e., $\mathscr{C}(T)=\\{x\in\mathscr{C}:\sigma(x)\subseteq T\\}$.

We can now express the cardinality of a subcode introduced in Definition 3.4
in terms of the cardinality of subcodes of the dual code.

######  Proposition 3.5.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$. For all $S\subseteq T\subseteq[n]$ we
have

$\displaystyle|\mathscr{C}(S,T)|=|\mathscr{C}|\sum_{A\subseteq
S}(-1)^{|A|}\displaystyle\frac{|\mathscr{C}^{\perp}(T^{c}\cup
A)|}{q^{n-|T|+|A|}}.$

###### Proof.

We have

$\displaystyle|\mathscr{C}(S,T)|$
$\displaystyle=|\mathscr{C}(T)|-|\\{x\in\mathscr{C}:\sigma(x)\subseteq
T,\,\sigma(x)\subseteq[n]\setminus A\textnormal{ for some $\emptyset\neq
A\subseteq S$}\\}|$
$\displaystyle=|\mathscr{C}(T)|-|\\{x\in\mathscr{C}:\sigma(x)\subseteq
T\cap([n]\setminus A)\textnormal{ for some $\emptyset\neq A\subseteq S$}\\}|.$
(3.3)

Since $A\subseteq S\subseteq T$, we can rewrite (3) as

$\displaystyle|\mathscr{C}(T)|-|\\{x\in\mathscr{C}:\sigma(x)\subseteq
T\setminus A\textnormal{ for some $\emptyset\neq A\subseteq S$}\\}|$
$\displaystyle=|\mathscr{C}(T)|-\left|\bigcup_{\emptyset\neq A\subseteq
S}\mathscr{C}(T\setminus A)\right|$ $\displaystyle=\sum_{A\subseteq
S}(-1)^{|A|}\left|\mathscr{C}(T\setminus A)\right|,$

where the latter equality follows from the Inclusion-Exclusion principle.
Finally, we have

$\displaystyle|\mathscr{C}(T\setminus
A)|=\frac{|\mathscr{C}|}{q^{n-|T|+|A|}}|\mathscr{C}^{\perp}(T^{c}\cup A)|,$

from which the statement of the lemma follows. ∎

With the aid of Proposition 3.5 we can prove the following result, which can
be seen as an analogue of a MacWilliams binomial moment identity.

######  Proposition 3.6.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$, $S\subseteq[n]$ and $|S|\leq t\leq
n$. We have

$\sum_{i=0}^{n}\binom{n-i}{t-i}W_{i}^{S}(\mathscr{C})=\\\
q^{k-n+t-|S|}(q-1)^{|S|}\sum_{i=0}^{n}\sum_{D\subseteq S}\sum_{B\subseteq
D}(-1)^{|D|-|B|}(1-q)^{-|B|}\binom{n-|S|-i+|B|}{t-|S|}W_{i}^{D}(\mathscr{C}^{\perp}).$

###### Proof.

We prove the statement by first fixing a subset $S\subseteq[n]$ and summing
both sides of the expression in Proposition 3.5 over all $T\subseteq[n]$ with
$S\subseteq T$ and $|T|=t$. The LHS of the equality in Proposition 3.5 gives

$\displaystyle\sum_{\begin{subarray}{c}S\subseteq T\subseteq[n]\\\
|T|=t\end{subarray}}|\mathscr{C}(S,T)|$
$\displaystyle=\sum_{\begin{subarray}{c}x\in\mathscr{C},\\\ \sigma(x)\supseteq
S\end{subarray}}|\\{T\subseteq[n]:|T|=t,\,\sigma(x)\subseteq T,\,S\subseteq
T\\}|$
$\displaystyle=\sum_{i=0}^{n}\sum_{\begin{subarray}{c}x\in\mathscr{C}\\\
\sigma(x)\supseteq S\\\
\omega^{\textnormal{H}}(x)=i\end{subarray}}|\\{T\subseteq[n]:|T|=t,\,S\subseteq\sigma(x)\subseteq
T\\}|$
$\displaystyle=\sum_{i=0}^{n}\sum_{\begin{subarray}{c}x\in\mathscr{C}\\\
\sigma(x)\supseteq S\\\
\omega^{\textnormal{H}}(x)=i\end{subarray}}\binom{n-i}{t-i}=\sum_{i=0}^{n}\binom{n-i}{t-i}W_{i}^{S}(\mathscr{C}),$

which is the LHS of the corollary. For the RHS we compute

$\displaystyle\sum_{\begin{subarray}{c}S\subseteq T\subseteq[n]\\\
|T|=t\end{subarray}}|\mathscr{C}|\sum_{A\subseteq
S}(-1)^{|A|}\displaystyle\frac{|\mathscr{C}^{\perp}(T^{c}\cup
A)|}{q^{n-t+|A|}}=|\mathscr{C}|\sum_{A\subseteq
S}\displaystyle\frac{(-1)^{|A|}}{q^{n-t+|A|}}\sum_{\begin{subarray}{c}S\subseteq
T\subseteq[n]\\\ |T|=t\end{subarray}}|\mathscr{C}^{\perp}(T^{c}\cup A)|.$
(3.4)

We now write the last sum in (3.4) differently. For a fixed $A\subseteq S$ we
have

$\displaystyle\sum_{\begin{subarray}{c}S\subseteq T\subseteq[n]\\\
|T|=t\end{subarray}}|\mathscr{C}^{\perp}(T^{c}\cup A)|$
$\displaystyle=\sum_{i=0}^{n}\sum_{\begin{subarray}{c}x\in\mathscr{C}^{\perp}\\\
\omega^{\textnormal{H}}(x)=i\end{subarray}}|\\{T\subseteq[n]:|T|=t,\sigma(x)\subseteq
T^{c}\cup A,S\subseteq T\\}|$
$\displaystyle=\sum_{i=0}^{n}\sum_{\begin{subarray}{c}x\in\mathscr{C}^{\perp}\\\
\omega^{\textnormal{H}}(x)=i\end{subarray}}|\\{T\subseteq[n]:|T|=n-t,\sigma(x)\subseteq
T\cup A,T\subseteq S^{c}\\}|$
$\displaystyle=\sum_{i=0}^{n}\sum_{\begin{subarray}{c}x\in\mathscr{C}^{\perp}\\\
\omega^{\textnormal{H}}(x)=i\\\ \sigma(x)\subseteq S^{c}\cup
A\end{subarray}}|\\{T\subseteq S^{c}:|T|=n-t,\sigma(x)\subseteq T\cup A\\}|$
$\displaystyle=\sum_{i=0}^{n}\sum_{j=0}^{|A|}\sum_{\begin{subarray}{c}x\in\mathscr{C}^{\perp},\\\
\omega^{\textnormal{H}}(x)=i\\\ |\sigma(x)\cap A|=j\\\ |\sigma(x)\cap
S^{c}|=i-j\end{subarray}}\binom{n-|S|-i+j}{n-t-i+j}$
$\displaystyle=\sum_{i=0}^{n}\sum_{j=0}^{|A|}\sum_{\begin{subarray}{c}B\subseteq
A\\\ |B|=j\end{subarray}}\,\sum_{\begin{subarray}{c}D\subseteq S^{c},\\\
|D|=i-j\end{subarray}}\,\sum_{\begin{subarray}{c}x\in\mathscr{C}^{\perp}\\\
\sigma(x)=D\cup B\end{subarray}}\binom{n-|S|-i+j}{n-t-i+j}$
$\displaystyle=\sum_{i=0}^{n}\sum_{B\subseteq
A}\sum_{\begin{subarray}{c}D\subseteq S^{c},\\\
|D|=i-|B|\end{subarray}}\binom{n-|S|-|D|}{n-t-|D|}W_{i}^{D\cup
B}(\mathscr{C}^{\perp}),$

where the last step follows from the fact that
$|\\{x\in\mathscr{C}^{\perp}:\sigma(x)=B\cup D\\}|=W_{i}^{D\cup
B}(\mathscr{C}^{\perp})$ for $B\subseteq A$ with $|B|=j$ and $D\subseteq
S^{c}$ with $|D|=i-j$. After substituting this expression into (3.4), we
simplify further by reordering the summands and applying the Binomial Theorem
as follows:

$\displaystyle|\mathscr{C}|\sum_{A\subseteq
S}\displaystyle\frac{(-1)^{|A|}}{q^{n-t+|A|}}\sum_{i=0}^{n}\sum_{B\subseteq
A}\sum_{\begin{subarray}{c}D\subseteq S^{c}\\\
|D|=i-|B|\end{subarray}}\binom{n-|S|-|D|}{n-t-|D|}W_{i}^{D\cup
B}(\mathscr{C}^{\perp})$
$\displaystyle=q^{k-n+t}\sum_{i=0}^{n}\sum_{B\subseteq
S}\sum_{\begin{subarray}{c}D\subseteq S^{c}\\\
|D|=i-|B|\end{subarray}}\binom{n-|S|-|D|}{n-t-|D|}W_{i}^{D\cup
B}(\mathscr{C}^{\perp})\sum_{B\subseteq A\subseteq
S}\displaystyle\frac{(-1)^{|A|}}{q^{|A|}}$
$\displaystyle=q^{k-n+t}\sum_{i=0}^{n}\sum_{B\subseteq
S}\sum_{\begin{subarray}{c}D\subseteq S^{c}\\\
|D|=i-|B|\end{subarray}}\binom{n-|S|-|D|}{n-t-|D|}W_{i}^{D\cup
B}(\mathscr{C}^{\perp})\sum_{j=|B|}^{|S|}(-1)^{j}\binom{|S|-|B|}{j-|B|}q^{-j}$
$\displaystyle=q^{k-n+t}\sum_{i=0}^{n}\sum_{B\subseteq
S}\sum_{\begin{subarray}{c}D\subseteq S^{c}\\\
|D|=i-|B|\end{subarray}}\binom{n-|S|-|D|}{n-t-|D|}W_{i}^{D\cup
B}(\mathscr{C}^{\perp})(-1)^{|S|}q^{-|B|}$ $\displaystyle\hskip
227.62204pt\cdot\sum_{j=0}^{|S|-|B|}(-1)^{|S|-|B|-j}\binom{|S|-|B|}{j}(q^{-1})^{j}$
$\displaystyle=q^{k-n+t}\sum_{i=0}^{n}\sum_{B\subseteq
S}\sum_{\begin{subarray}{c}D\subseteq S^{c}\\\
|D|=i-|B|\end{subarray}}\binom{n-|S|-|D|}{n-t-|D|}W_{i}^{D\cup
B}(\mathscr{C}^{\perp})(-1)^{|S|}q^{-|B|}(q^{-1}-1)^{|S|-|B|}$
$\displaystyle=q^{k-n+t-|S|}(q-1)^{|S|}\sum_{i=0}^{n}\sum_{B\subseteq
S}(1-q)^{-|B|}\sum_{\begin{subarray}{c}D\subseteq S^{c}\\\
|D|=i-|B|\end{subarray}}\binom{n-|S|-i+|B|}{t-|S|}W_{i}^{D\cup
B}(\mathscr{C}^{\perp}).$

To conclude the proof we will need the following claim.

######  Claim A.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$, $S\subseteq[n]$ with $|S|=t$,
$B\subseteq S$, and $1\leq j\leq n$. Then

$\sum_{\begin{subarray}{c}D\subseteq S^{c}\\\
|D|=j-|B|\end{subarray}}W_{j}^{D\cup B}(\mathscr{C}^{\perp})=\sum_{B\subseteq
D\subseteq S}(-1)^{|D|-|B|}W_{j}^{D}(\mathscr{C}^{\perp}).$

###### Proof of the claim.

For all $D\subseteq S^{c}$ with $|D|=j-|B|$ we have

$W_{j}^{D\cup
B}(\mathscr{C}^{\perp})=\left|\\{v\in\mathscr{C}^{\perp}\,:\,\sigma(v)=D\cup
B\\}\right|.$

Hence

$\displaystyle\sum_{\begin{subarray}{c}D\subseteq S^{c}\\\
|D|=j-|B|\end{subarray}}W_{j}^{D\cup B}(\mathscr{C}^{\perp})$
$\displaystyle=\left|\\{v\in\mathscr{C}^{\perp}\,:\,D\subseteq
S^{c},\,|D|=j-|B|,\,\sigma(v)=D\cup B\\}\right|$
$\displaystyle=\left|\\{v\in\mathscr{C}^{\perp}\,:\,B\subseteq
D\subseteq[n]\setminus(S\setminus B),\,|D|=j,\,\sigma(v)=D\\}\right|$
$\displaystyle=\left|\\{v\in\mathscr{C}^{\perp}\,:\,B\subseteq
D\subseteq[n],\,|D|=j,\,\sigma(v)=D\\}\right|-$
$\displaystyle\left|\bigcup_{\emptyset\subsetneq A\subseteq(S\setminus
B)}\\{v\in\mathscr{C}^{\perp}\,:\,B\cup A\subseteq
D\subseteq[n],\,|D|=j,\,\sigma(v)=D\\}\right|.$

Using the Inclusion-Exclusion principle followed by Lemma 3.3, we get

$\displaystyle\sum_{\begin{subarray}{c}D\subseteq S^{c}\\\
|D|=j-|B|\end{subarray}}W_{j}^{D\cup B}(\mathscr{C}^{\perp})$
$\displaystyle=\sum_{\emptyset\subseteq A\subseteq S\setminus
B}(-1)^{|A|}\sum_{\begin{subarray}{c}A\cup B\subseteq D\subseteq[n]\\\
|D|=j\end{subarray}}W_{j}^{D}(\mathscr{C}^{\perp})$
$\displaystyle=\sum_{\emptyset\subseteq A\subseteq S\setminus
B}(-1)^{|A|}W_{j}^{A\cup B}(\mathscr{C}^{\perp})$
$\displaystyle=\sum_{B\subseteq D\subseteq
S}(-1)^{|D|-|B|}W_{j}^{D}(\mathscr{C}^{\perp}),$

proving the desired claim. ∎

Finally, from Claim A it follows that

$q^{k-n+t-|S|}(q-1)^{|S|}\sum_{i=0}^{n}\sum_{B\subseteq
S}(1-q)^{-|B|}\sum_{\begin{subarray}{c}D\subseteq S^{c}\\\
|D|=i-|B|\end{subarray}}\binom{n-|S|-i+|B|}{t-|S|}W_{i}^{D\cup
B}(\mathscr{C}^{\perp})=\\\
q^{k-n+t-|S|}(q-1)^{|S|}\sum_{i=0}^{n}\sum_{D\subseteq S}\sum_{B\subseteq
D}(-1)^{|D|-|B|}(1-q)^{-|B|}\binom{n-|S|-i+|B|}{t-|S|}W_{i}^{D}(\mathscr{C}^{\perp}),$

concluding the proof. ∎

In order to “isolate” the refined weight distribution of a code
$\mathscr{C}\leq\mathbb{F}_{q}^{n}$ in the sum of Proposition 3.6, we will use
the following lemma.

######  Lemma 3.7.

Let

$\alpha_{t}:=\sum_{i=0}^{n}\binom{n-i}{t-i}\beta_{i}\quad\textnormal{for
$0\leq t\leq n.$}$

Then

$\beta_{i}=\displaystyle\sum_{t=0}^{n}(-1)^{(i-t)}\binom{n-t}{i-t}\alpha_{t}\quad\textnormal{for
all $0\leq i\leq n.$}$

###### Proof.

Let $0\leq i\leq n$ be fixed. We have

$\displaystyle\sum_{t=0}^{n}(-1)^{(i-t)}\binom{n-t}{i-t}\alpha_{t}$
$\displaystyle=\sum_{t=0}^{n}(-1)^{(i-t)}\binom{n-t}{i-t}\sum_{j=0}^{n}\binom{n-j}{t-j}\beta_{j}$
$\displaystyle=\sum_{t=0}^{n}(-1)^{(i-t)}\sum_{j=0}^{n}\binom{n-t}{n-i}\binom{n-j}{n-t}\beta_{j}$
$\displaystyle=\sum_{t=0}^{n}(-1)^{(i-t)}\sum_{j=0}^{n}\binom{i-j}{i-t}\binom{n-j}{n-i}\beta_{j}$
$\displaystyle=\sum_{j=0}^{n}\binom{n-j}{n-i}\beta_{j}\sum_{t=0}^{i}(-1)^{(i-t)}\binom{i-j}{i-t}$
$\displaystyle=\sum_{j=0}^{n}\binom{n-j}{n-i}\beta_{j}\sum_{s=0}^{i-j}(-1)^{s}\binom{i-j}{s}$
$\displaystyle=\beta_{i},$

because

$\displaystyle\sum_{s=0}^{i-j}(-1)^{s}\binom{i-j}{s}=0$

unless $i=j$, by the Binomial Theorem. ∎

We can finally established the MacWilliams-type identity for the refined
weight distribution of a code.

######  Theorem 3.8.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ and fix $S\subseteq[n]$. For all
$0\leq i\leq n$ we have

$W_{i}^{S}(\mathscr{C})=q^{k-n-|S|}(q-1)^{|S|}\sum_{t=|S|}^{n}\sum_{j=0}^{n}\sum_{D\subseteq
S}\sum_{B\subseteq D}(-1)^{i-t+|D|}q^{t}\\\
(q-1)^{-|B|}\binom{n-t}{i-t}\binom{n-|S|-j+|B|}{t-|S|}W_{j}^{D}(\mathscr{C}^{\perp}).$
(3.5)

###### Proof.

The statement follows directly from Proposition 3.6 and Lemma 3.7, by setting
$\beta_{i}=W_{i}^{S}(\mathscr{C})$ and

$\alpha_{t}=q^{k-n+t-|S|}(q-1)^{|S|}\sum_{j=0}^{n}\sum_{D\subseteq
S}\sum_{B\subseteq
D}(-1)^{|D|-|B|}(1-q)^{-|B|}\binom{n-|S|-j+|B|}{t-|S|}W_{j}^{D}(\mathscr{C}^{\perp}).\qed$

######  Remark 3.9.

Although we call the above a MacWilliams-type identity, enumerators we
consider do not naturally fit in the framework of the MacWilliams identities,
as they do not represent the cardinalities of the blocks of a partition of the
underlying code; see [7]. However, one can see the above as a generalization
of the classical MacWilliams identity. In fact, with tedious but
straightfowrad computations one can show that (3.5) reduces to the famous
MacWilliams identity [16] when $S=\emptyset$.

When applying MacWilliams-type identities, it is crucial to understand the
dependencies between variables and which groups of these determine each other,
possibly under extra assumptions. The next result shows that
$W_{i}^{S}(\mathscr{C})$ can be rewritten in terms of
$W_{j}^{T}(\mathscr{C}^{\perp})$ for $1\leq j\leq n$ and all $T\subseteq[n]$
with $|T|=|S|$, provided that the cardinality of $S$ does not exceed the
minimum distance of $\mathscr{C}^{\perp}$. This result will become especially
useful for the linear programming bounds presented in Section 4.

######  Corollary 3.10.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a code, $d^{\perp}$ the minimum
distance of $\mathscr{C}^{\perp}$, and $S\subseteq[n]$. If $|S|\leq
d^{\perp}$, then

$W_{i}^{S}(\mathscr{C})=\binom{n-|S|}{i-|S|}q^{k-n}(q-1)^{i}+q^{k-n-|S|}(q-1)^{|S|}\sum_{t=|S|}^{n}\sum_{j=d^{\perp}}^{n}\sum_{\begin{subarray}{c}T\subseteq[n]\\\
|T|=|S|\end{subarray}}\sum_{D\subseteq S\cap T}\sum_{B\subseteq
D}(-1)^{i-t+|D|}\\\
q^{t}(q-1)^{-|B|}\binom{n-t}{i-t}\binom{n-|S|-j+|B|}{t-|S|}\binom{j-|D|}{|S|-|D|}^{-1}W_{j}^{T}(\mathscr{C}^{\perp}).$

###### Proof.

Let $s:=|S|$ and consider the identity from Theorem 3.8. We first isolate the
case $j=0$. Note that $W_{0}^{D}(\mathscr{C}^{\perp})=1$ if $D=\emptyset$ and
$W_{0}^{D}(\mathscr{C}^{\perp})=0$ otherwise. Hence the summand of Theorem 3.8
corresponding to $j=0$ is:

$\displaystyle\sum_{t=s}^{n}(-1)^{i-t}q^{t}\binom{n-t}{i-t}\binom{n-s}{n-t}=$
$\displaystyle\sum_{t=s}^{n}(-1)^{i-t}q^{t}\binom{n-s}{n-i}\binom{i-s}{i-t}$
$\displaystyle=$
$\displaystyle\binom{n-s}{n-i}\sum_{t=s}^{i}(-1)^{i-t}q^{t}\binom{i-s}{i-t}$
$\displaystyle=$
$\displaystyle\binom{n-s}{n-i}q^{s}\sum_{t=0}^{i-s}(-1)^{i-s-t}q^{t}\binom{i-s}{t}$
$\displaystyle=$ $\displaystyle\binom{n-s}{n-i}q^{s}(q-1)^{i-s},$

where the former equality follows from the identity

$\binom{a}{b+c}\binom{b+c}{b}=\binom{a}{c}\binom{a-c}{b},$

and the latter one follows from the Binomial Theorem.

Now assume $j\geq 1$. If $j\leq d^{\perp}$ then
$W_{j}^{D}(\mathscr{C}^{\perp})=0$. Thus it suffices to consider the summands
for $d^{\perp}\leq j\leq n$. By assumption $s\leq d^{\perp}$. Hence for all
$D\subseteq S$ we can apply Lemma 3.3 and get

$W_{j}^{D}(\mathscr{C}^{\perp})=\binom{j-|D|}{s-|D|}^{-1}\sum_{\begin{subarray}{c}D\subseteq
T\subseteq[n]\\\ |T|=s\end{subarray}}W_{j}^{T}(\mathscr{C}^{\perp}).$

Therefore for $j\geq d^{\perp}$, (3.5) can be rewritten as

$\displaystyle\sum_{j=d^{\perp}}^{n}\sum_{t=s}^{n}\sum_{D\subseteq
S}\sum_{B\subseteq
D}(-1)^{i-t+|D|}q^{t}(q-1)^{-|B|}\binom{n-t}{i-t}\binom{n-s-j+|B|}{t-s}\binom{j-|D|}{s-|D|}^{-1}\sum_{\begin{subarray}{c}D\subseteq
T\subseteq[n]\\\ |T|=s\end{subarray}}W_{j}^{T}(\mathscr{C}^{\perp})$
$\displaystyle=$
$\displaystyle\sum_{j=d^{\perp}}^{n}\sum_{t=s}^{n}\sum_{\begin{subarray}{c}T\subseteq[n]\\\
|T|=s\end{subarray}}\sum_{D\subseteq S\cap T}\sum_{B\subseteq
D}(-1)^{i-t+|D|}q^{t}(q-1)^{-|B|}\binom{n-t}{i-t}\binom{n-s-j+|B|}{t-s}\binom{j-|D|}{s-|D|}^{-1}W_{j}^{T}(\mathscr{C}^{\perp}).$

Putting everything together proves the desired statement. ∎

Note that in the above proof the assumption $|S|\leq d^{\perp}$ was needed to
apply Lemma 3.3. A natural question is whether $W_{i}^{S}(\mathscr{C})$ or not
can be fully expressed in terms of $W_{j}^{T}(\mathscr{C}^{\perp})$, for
$0\leq j\leq n$ and $|T|=|S|$ when $|S|>d^{\perp}$. At the time of writing
this paper we are unable to answer this question.

##  4 Applications and Bounds

Delsarte’s linear programming (LP) bound [5] is a powerful tool to estimate
the size of a code with a certain length and minimum distance. It combines the
classical Macwilliams identities with, as the name suggests, linear
programming. In this section we study a new LP bound for codes with locality.
We use our main duality result, Theorem 3.8, to build a linear program that
gives a bound on the size of $(r,\delta)$-LRCs.

######  Notation 4.1.

In the sequel, for a code $\mathscr{C}\leq\mathbb{F}_{q}^{n}$, $0\leq i\leq n$
and $1\leq j\leq n$, we will write $\smash{W_{i}^{j}(\mathscr{C})}$ instead of
$\smash{W_{i}^{\\{j\\}}(\mathscr{C})}$.

The next result shows that it is possible to bound from below, in any
$(r,\delta)$-LRC, the number of codewords with coordinate $i$ in their support
and weight at most $r+\delta-1$.

######  Proposition 4.2.

Let $\delta\geq 2$ and let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be an
$(r,\delta)$-LRC, with dimension $k$. Then for all $j\in[n]$ we have

$\sum_{i=0}^{r+\delta-1}W^{j}_{i}(\mathscr{C}^{\perp})\geq
q^{\delta-1}-q^{\delta-2}.$

###### Proof.

Let $j\in[n]$ and $S_{j}\subseteq[n]$ be minimal with respect to inclusion
such that $|S_{j}|\leq r+\delta-1$, $j\in S_{j}$, and
$d(\pi_{S_{j}}(\mathscr{C}))\geq\delta$. Let
$k_{j}:=\dim(\pi_{S_{j}}(\mathscr{C}))$, $d_{j}:=d(\pi_{S_{j}}(\mathscr{C}))$,
and $k_{j}^{\perp}=|S_{j}|-k_{j}$. From the Singleton Bound we have
$|S_{j}|-k_{j}+1\geq\delta$, which means $k_{j}^{\perp}\geq\delta-1$.
Furthermore there exist $v\in\mathscr{C}^{\perp}(S_{j})$ such that
$j\in\sigma(v)$, since otherwise we arrive to the contradiction that
$\mathscr{C}^{\perp}(S_{j})$ would be degenerate and
$d(\pi_{S_{j}}(\mathscr{C}))=1<\delta$. These two facts together imply that
there are at least $q^{\delta-1}-q^{\delta-2}$ codewords in
$\mathscr{C}^{\perp}(S_{j})$ containing $j$ in their support and of weight at
most $|S_{j}|\leq r+\delta-1$. Therefore
$\sum_{i=0}^{r+\delta-1}W^{j}_{i}(\mathscr{C}^{\perp})\geq
q^{\delta-1}-q^{\delta-2}$. ∎

Unfortunately, the converse of this statement is not true, unless $\delta=2$
(leading to the statement of Lemma 4.4 below). Consider the following example.

######  Example 4.3.

Let $G$ and $H$ be matrices over $\mathbb{F}_{2}$ defined as follows:

$G:=\begin{pmatrix}1&1&0&1&0\\\ 0&1&1&0&0\\\ 0&0&0&1&1\end{pmatrix},\quad
H:=\begin{pmatrix}1&1&1&0&0\\\ 1&0&0&1&1\end{pmatrix}.$

Let $\mathscr{C}=\\{xG:x\in\mathbb{F}_{2}^{3}\\}$ which then implies
$\mathscr{C}^{\perp}=\\{xH:x\in\mathbb{F}_{2}^{2}\\}$. If we fix $r:=2$ and
$\delta:=3$, then $r+\delta-1=4$ and $q^{\delta-1}-q^{\delta-2}=2$. One can
easily check that for all $j\in[5]$ we have

$\sum_{i=0}^{r+\delta-1}W_{i}^{j}(\mathscr{C}^{\perp})=\sum_{i=0}^{4}W_{i}^{j}(\mathscr{C}^{\perp})=2.$

However, for the coordinate $\\{1\\}$ there exists no set $S_{1}\subseteq[5]$
such that $1\in S_{1}$, $|S_{1}|\leq 4$, and $d(\pi_{S_{1}}(\mathscr{C}))\geq
3$. In fact any projection of $\mathscr{C}$ onto a set of coordinate of size
less or equal to $4$ will have minimum distance $1$ or $2$. Hence the code
$\mathscr{C}$ is not an $(2,3)$-LRC.

As already mentioned, for $\delta=2$ the converse of Proposition 4.2 is also
true. As a byproduct, the result also gives a characterization of codes with
locality.

######  Lemma 4.4.

A non-degenerate code $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ has locality $r$ if
and only if $\sum_{i=2}^{r+1}W_{i}^{j}(\mathscr{C}^{\perp})\geq q-1$ for all
$1\leq j\leq n$.

Proposition 4.2 and Lemma 4.4 indicate that the MacWilliams-type identity of
Corollary 3.10 becomes especially useful in the context of LRCs when
considering the weight distribution $W_{i}^{j}(\mathscr{C}^{\perp})$, where
$1\leq j\leq n$ and $0\leq i\leq n$. By applying Corollary 3.10, we get the
following corollary.

######  Corollary 4.5.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a code and $l\in[n]$. Then

$W_{i}^{l}(\mathscr{C})=\binom{n-1}{i-1}q^{k-n}(q-1)^{i}+q^{k-n-1}(q-1)\sum_{j=d^{\perp}}^{n}\sum_{s=1}^{n}\sum_{t=1}^{i}(-1)^{i-t}q^{t}\binom{n-t}{i-t}\\\
\left(\frac{1}{j}\binom{n-1-j}{t-1}\right)^{1-\delta(l,s)}\left(\frac{1-j}{j}\binom{n-1-j}{t-1}-(q-1)^{-1}\binom{n-j}{t-1}\right)^{\delta(l,s)}W_{j}^{s}(\mathscr{C}^{\perp}),$

where $\delta(l,s)=1$ if $l=s$ and $0$ otherwise.

###### Proof.

Using Corollary 3.10 for $S=\\{l\\}$ we immediately get

$W_{i}^{l}(\mathscr{C})=\binom{n-1}{i-1}q^{k-n}(q-1)^{i}+q^{k-n-1}(q-1)\sum_{t=1}^{n}\sum_{j=d^{\perp}}^{n}\sum_{\begin{subarray}{c}T\subseteq[n]\\\
|T|=1\end{subarray}}\sum_{D\subseteq\\{l\\}\cap T}\sum_{B\subseteq
D}(-1)^{i-t+|D|}q^{t}\\\
(q-1)^{-|B|}\binom{n-t}{i-t}\binom{n-1-j+|B|}{t-1}\binom{j-|D|}{1-|D|}^{-1}W_{j}^{T}(\mathscr{C}^{\perp}).$

We now compute

$\sum_{D\subseteq\\{l\\}\cap T}\sum_{B\subseteq
D}(-1)^{|D|}(q-1)^{-|B|}\binom{n-1-j+|B|}{t-1}\binom{j-|D|}{1-|D|}^{-1},$
(4.1)

for both $T=\\{l\\}$ and $T=\\{s\\}$ where $s\neq l$. In the former case,
(4.1) is equal to

$\displaystyle\frac{1}{j}\binom{n-1-j}{t-1}-\left[(q-1)^{-1}\binom{n-j}{t-1}+\binom{n-1-j}{t-1}\right].$

In the case $T=\\{s\\}$ where $s\neq l$, (4.1) is equal to
$\frac{1}{j}\binom{n-1-j}{t-1}$. The results then follows. ∎

######  Remark 4.6.

There exist other methods to derive the MacWilliams-type identity of Corollary
4.5. A first approach was established in [10], where the parameter
$W_{i}^{l}(\mathscr{C})$ is rewritten in terms of the $W_{j}(\mathscr{C})$’s
and $W_{j}(\mathscr{C}([n]\setminus\\{l\\}))$’s for $1\leq j,\,l\leq n$. The
classical MacWilliams identity is then applied to the latter terms. In
addition, it was brought to our attention by M. Grassl that our refined weight
distribution seems related to the notion of split weight enumerator; see [20]
for more details. We were able to show that this is in fact the case and are
able to derive Corollary 4.5 also as a corollary of [20, Proposition 1].

The last result we need to apply a linear program is the following, which is a
specific case of Lemma 3.3 for $A=\emptyset$ and $|S|=1$.

######  Lemma 4.7.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be non-degenerate. For all $1\leq
i\leq n$ and $1\leq j\leq n$ we have

$W_{i}(\mathscr{C})={\displaystyle\sum_{j=1}^{n}W_{i}^{j}(\mathscr{C})}/{i}.$

For ease of exposition, we introduce the following notation.

######  Notation 4.8.

Let $A=\\{a_{il}\mid 1\leq i\leq n+1,\,1\leq l\leq
n\\}\subseteq\mathbb{R}_{\geq 0}$. For $1\leq i,l\leq n$ we denote by
$a_{il}^{\perp}$ the following linear combination of elements of $A$:

$a_{il}^{\perp}=\binom{n-1}{i-1}(q-1)^{i}+q^{-1}(q-1)\sum_{j=d^{\perp}}^{n}\sum_{s=1}^{n}\sum_{t=1}^{i}(-1)^{i-t}q^{t}\binom{n-t}{i-t}\cdot\\\
\left(\frac{1}{j}\binom{n-1-j}{t-1}\right)^{1-\delta(l,s)}\left(\frac{1-j}{j}\binom{n-1-j}{t-1}-(q-1)^{-1}\binom{n-j}{t-1}\right)^{\delta(l,s)}a_{js}.$

The following result gives a linear program that establishes bounds for codes
with $(r,\delta)$-locality.

######  Theorem 4.9 (LP bound for $(r,\delta)$-LRCs).

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a non-degenerate code of minimum
distance at least $d$, dimension $k$, and $(r,\delta)$-locality. Let $\mu^{*}$
denote the minimum value of

$\sum_{i=1}^{n}\left({\displaystyle\sum_{j=1}^{n}a_{ij}}/{i}\right),$

where $a_{ij}\in\mathbb{R}$, for $1\leq i\leq n+1$ and $1\leq j\leq n$,
satisfy the following constraints:

  * (i)

$a_{ij}\geq 0$ for $1\leq i,j\leq n$,

  * (ii)

$a_{ij}^{\perp}\geq 0$ for $1\leq i,j\leq n$,

  * (iii)

$a_{ij}^{\perp}=0$ for $1\leq i\leq d-1$ and $1\leq j\leq n$,

  * (iv)

$\smash{\textstyle\sum_{i=1}^{r+\delta-1}a_{ij}\geq
q^{\delta-1}-q^{\delta-2}}$ for $1\leq j\leq n$,

  * (v)

$a_{1j}=0$ for $1\leq j\leq n$.

Then

$k\leq n-\lceil\log_{q}(1+\mu^{*})\rceil.$

###### Proof.

We claim that for any non-degenerate linear code
$\mathscr{C}\leq\mathbb{F}_{q}^{n}$ of minimum distance $d$ and
$(r,\delta)$-locality, the assignment
$\smash{a_{ij}=W_{i}^{j}(\mathscr{C}^{\perp})}$ is a feasible solution of the
linear program. Indeed, (i) and (ii) are satisfied trivially. Constraint (iii)
guarantees that the minimum distance of the code is at least $d$ and
constraint (iv) needs to be fulfilled in order for the code to be an
$(r,\delta)$-LRC. Finally constraint (v) makes sure that $\mathscr{C}$ is non-
degenerate. Therefore the optimum of the linear program gives a lower bound on
the size of $\mathscr{C}^{\perp}$ by Proposition 4.2. ∎

We conclude this section with some results obtained with the LP bound of
Theorem 4.9 in Tables 1-5. For fixed parameters $(q,n,d,r,\delta)$, we give an
upper bound on the dimension $k$ of an $(r,\delta)$-LRC in
$\mathbb{F}_{q}^{n}$ and minimum distance at least $d$. The computations were
performed using SageMath. In the case where $\delta=2$ (i.e. Tables 1-4) we
compare our results to (2.1) (gen. Singl) and (2.2) (SH). The latter is
computed in two different ways: first, the value
$\smash{k_{\textrm{opt}}^{(q)}}$ is estimated using a classical LP bound (SH
with LP); second, the exact value of $\smash{k_{\textrm{opt}}^{(q)}}$ is
computed (SH exact), since it can be determined for the parameters considered
in the tables by looking at databases of codes. The most fair comparison
between our result and (2.2) is given by SH with LP, since the value of SH
exact is only known for very small parameters. Our results show that Theorem
4.9 is often tighter than (2.2) (this is indicated in red on the tables). A
similar comparison is done in Table 5, but using (2.3) and (2.4) instead.

Table 1: $q=2$, $\delta=2$ $n$ | $d$ | $r$ | LP | SH with LP | SH exact | gen. Singl.
---|---|---|---|---|---|---
10 | 4 | 2 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}}}$ | $k\leq 5$ | $k\leq 5$ | $k\leq 5$
11 | 3 | 3 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}}}$ | $k\leq 7$ | $k\leq 7$ | $k\leq 7$
12 | 3 | 3 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}6}}}$ | $k\leq 7$ | $k\leq 7$ | $k\leq 7$
14 | 4 | 6 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}8}}}$ | $k\leq 9$ | $k\leq 9$ | $k\leq 10$
17 | 7 | 2 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}}}$ | $k\leq 6$ | $k\leq 6$ | $k\leq 8$
18 | 8 | 2 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}}}$ | $k\leq 6$ | $k\leq 6$ | $k\leq 8$
20 | 9 | 5 | $k\leq 5$ | $k\leq 6$ | $k\leq 5$ | $k\leq 11$
20 | 11 | 2 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}}}$ | $k\leq 3$ | $k\leq 3$ | $k\leq 7$
Table 2: $q=3$, $\delta=2$ $n$ | $d$ | $r$ | LP | SH with LP | SH exact | gen. Singl.
---|---|---|---|---|---|---
10 | 2 | 4 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}7}}}$ | $k\leq 8$ | $k\leq 8$ | $k\leq 8$
11 | 6 | 4 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}}}$ | $k\leq 5$ | $k\leq 5$ | $k\leq 5$
11 | 5 | 5 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}}}$ | $k\leq 6$ | $k\leq 6$ | $k\leq 6$
13 | 9 | 2 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}}}$ | $k\leq 3$ | $k\leq 3$ | $k\leq 4$
14 | 2 | 6 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}11}}}$ | $k\leq 12$ | $k\leq 12$ | $k\leq 12$
14 | 9 | 3 | $k\leq 3$ | $k\leq 4$ | $k\leq 3$ | $k\leq 5$
18 | 6 | 5 | $k\leq 10$ | $k\leq 11$ | $k\leq 10$ | $k\leq 11$
25 | 5 | 5 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}15}}}$ | $k\leq 17$ | $k\leq 17$ | $k\leq 18$
Table 3: $q=4$, $\delta=2$ $n$ | $d$ | $r$ | LP | SH with LP | SH exact | gen. Singl.
---|---|---|---|---|---|---
9 | 3 | 3 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}}}$ | $k\leq 6$ | $k\leq 6$ | $k\leq 6$
10 | 2 | 4 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}7}}}$ | $k\leq 8$ | $k\leq 8$ | $k\leq 8$
11 | 8 | 2 | $k\leq 2$ | $k\leq 3$ | $k\leq 2$ | $k\leq 3$
12 | 2 | 5 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}9}}}$ | $k\leq 10$ | $k\leq 10$ | $k\leq 10$
14 | 2 | 6 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}11}}}$ | $k\leq 12$ | $k\leq 12$ | $k\leq 12$
15 | 10 | 4 | $k\leq 4$ | $k\leq 5$ | $k\leq 4$ | $k\leq 5$
15 | 8 | 6 | $k\leq 6$ | $k\leq 7$ | $k\leq 6$ | $k\leq 7$
20 | 2 | 9 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}17}}}$ | $k\leq 18$ | $k\leq 18$ | $k\leq 18$
Table 4: $q=5$, $\delta=2$ $n$ | $d$ | $r$ | LP | SH with LP | SH exact | gen. Singl.
---|---|---|---|---|---|---
9 | 3 | 3 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}}}$ | $k\leq 6$ | $k\leq 6$ | $k\leq 6$
11 | 3 | 4 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}7}}}$ | $k\leq 8$ | $k\leq 8$ | $k\leq 8$
14 | 2 | 6 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}11}}}$ | $k\leq 12$ | $k\leq 12$ | $k\leq 12$
16 | 2 | 7 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}13}}}$ | $k\leq 14$ | $k\leq 14$ | $k\leq 14$
16 | 2 | 7 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}13}}}$ | $k\leq 14$ | $k\leq 14$ | $k\leq 14$
18 | 2 | 8 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}15}}}$ | $k\leq 16$ | $k\leq 16$ | $k\leq 16$
22 | 2 | 10 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}19}}}$ | $k\leq 20$ | $k\leq 20$ | $k\leq 20$
24 | 2 | 11 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}21}}}$ | $k\leq 22$ | $k\leq 22$ | $k\leq 22$
Table 5: $q=2$, $\delta=3$ $n$ | $d$ | $r$ | LP | SH with LP | SH exact | gen. Singl
---|---|---|---|---|---|---
15 | 7 | 5 | $k\leq 5$ | $k\leq 5$ | $k\leq 5$ | $k\leq 7$
16 | 5 | 5 | $k\leq 8$ | $k\leq 7$ | $k\leq 7$ | $k\leq 10$
16 | 8 | 5 | $k\leq{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}}}$ | $k\leq 5$ | $k\leq 5$ | $k\leq 7$
17 | 9 | 5 | $k\leq 3$ | $k\leq 3$ | $k\leq 3$ | $k\leq 7$
17 | 10 | 5 | $k\leq 2$ | $k\leq 2$ | $k\leq 2$ | $k\leq 6$
18 | 7 | 5 | $k\leq 7$ | $k\leq 7$ | $k\leq 7$ | $k\leq 10$
19 | 8 | 5 | $k\leq 7$ | $k\leq 7$ | $k\leq 7$ | $k\leq 10$
20 | 5 | 7 | $k\leq 13$ | $k\leq 11$ | $k\leq 11$ | $k\leq 14$

######  Remark 4.10.

As Table 5 illustrates, when $\delta>2$ our LP bound does not seem to beat the
shortening bound (both the exact and the LP one) as frequently as for
$\delta=2$. A possible explanation for why this happens is that, for
$\delta>2$, the $(r,\delta)$-LRCs are not fully characterized by the
constraint (iv) in Theorem 4.9. Hence a code that achieves the minimum of the
objective function may not be the dual code of an $(r,\delta)$-LRC.

##  5 The Role of the Field Size

In this section we establish various bounds for LRCs that involve the
underlying field size $q$. The goal is to understand the role played by this
parameter for the code’s locality.

We first use the refined weight distribution introduced in Section 3 to derive
bounds connecting the dual distance with the locality and the field size. We
then apply the theory of generalized weights to derive bounds involving the
length, dimension, minimum distance, locality, and field size.

To derive our first bound for LRCs, recall from Definition 3.4 that

$\smash{\mathscr{C}(S,[n])=\\{x\in\mathscr{C}:S\subseteq\sigma(x)\\}}.$

The following result holds for any linear code and does not depend on the
locality parameter.

######  Proposition 5.1.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be an code of dimension $k$ and
minimum distance $d$. Let $S\subseteq[n]$ with $|S|\leq k-1$. If
$|\mathscr{C}(S,[n])|>0$, then there exist $x\in\mathscr{C}(S,[n])$ such that

$\omega^{\mathrm{H}}(x)\leq n-k+|S|-(d-q)/q.$ (5.1)

###### Proof.

Let $s=|S|$ and $x\in\mathscr{C}(S,[n])$ of minimum weight with $x\neq 0$. Let
$t=\omega^{\textnormal{H}}(x)$. Without loss of generality, we may assume
$S=\\{1,\ldots,s\\}$, $T=\\{1,\ldots,t\\}$, and $x=\sum_{i=1}^{t}e_{i}$, where
$e_{i}$ is the $i$-th standard basis elements. Since $s\leq k-1$ we have
$t\leq n-k+s$. Furthermore, since $\dim(\mathscr{C})=k$ then there must be an
element $y\in\mathscr{C}$ such that $y_{i}=0$ for all $i\in
S\cup\\{n-k+s+2,\ldots,n\\}$. Then $\omega^{\textnormal{H}}(\pi_{T}(y))\geq
d-(n-t)+k-s-1$. Moreover, there exist $\alpha\in\mathbb{F}_{q}^{*}$ such that

$\\{j\,:\,\pi_{T}(y)=\alpha\\}\geq(d-n+t+k-s-1)/(q-1).$

Let $x^{\prime}=\alpha x-y$. Then $\alpha_{i}\neq 0$ for all $i\in S$ and

$\displaystyle\omega^{\textnormal{H}}(x^{\prime})$ $\displaystyle\leq
t-\frac{d-n+t+k-s-1}{q-1}+(n-t)-(k-s-1)$
$\displaystyle=n-k+s+1-\frac{d-n+t+k-s-1}{q-1}.$

By choice of $t$ we therefore have

$t\leq n-k+s+1-\frac{d-n+t+k-s-1}{q-1},$

which is equivalent to $t\leq n-k+s-(d-q)/q$. ∎

By applying the previous proposition to a set $S$ of cardinality 1, we obtain
the following corollary, which was presented also in [10].

######  Corollary 5.2.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ of dimension $k$ and minimum distance
$d$. Then

$d\leq n-k+1-(d-q)/q.$

Note the above result improves on the Singleton bound for $d\geq q$.
Furthermore, it shows that for linear MDS codes one must have $d\leq q$. In
the context of Corollary 5.2, one may wonder if the bound of Proposition 5.1,
when applied to a set $S$ with $2\leq|S|\leq k-1$, can lead to an upper bound
for the $|S|$-generalized weight (see Definition 5.5). In other words: Is it
true that $d_{|S|}\leq n-k+|S|-(d-q)/q$? Although there exist examples of
codes for which the inequality holds, this is in general not the case, as
illustrated by the following example.

######  Example 5.3.

Let $\mathscr{C}\leq\mathbb{F}_{2}^{7}$ be the simplex code of dimension $3$,
i.e., the code generated by

$G=\begin{pmatrix}1&0&0&1&0&1&1\\\ 0&1&0&1&1&0&1\\\
0&0&1&0&1&1&1\end{pmatrix}.$

It is well known that $\omega^{\textnormal{H}}(x)=4$ for all non-zero
$x\in\mathscr{C}$. Therefore for all $S\subseteq[7]$ such that $|S|=2$, the
smallest weight of a codeword $x\in\mathscr{C}(S,[n])$ is $4$. One can easily
show that $d_{2}(\mathscr{C})=6$, which is greater than the right hand side of
(5.1) when the parameters are those of the simplex code.

By applying Proposition 5.1 to the dual code $\mathscr{C}^{\perp}$ of an LRC
$\mathscr{C}$, one can easily derive the following bound.

######  Corollary 5.4.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a code with dimension $k\geq 2$,
minimum distance $d$, and locality $r$. Let
$d^{\perp}=d(\mathscr{C}^{\perp})$. We have

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

###### Proof.

Note that if a code $\mathscr{C}$ has locality $r$, then by Lemma 4.7 there
exists a codeword $x\in\mathscr{C}^{\perp}$ with
$\omega^{\textnormal{H}}(x)\leq r+1$. In particular, $d^{\perp}\leq r+1$.
Applying Corollary 5.2 we obtain

$\displaystyle d^{\perp}\leq k+1-(d^{\perp}-q)/q$

which, combined with Theorem 2.6, yields

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

This concludes the proof. ∎

We now use the generalized weights of a code to derive new bounds which we
later apply to LRCs. We start by recalling the needed definitions.

######  Definition 5.5.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a code. The $i$-th generalized
weight of $\mathscr{C}$ is

$d_{i}(\mathscr{C}):=\min\\{|\sigma(\mathscr{D})|\,:\mathscr{D}\leq\mathscr{C}\textup{
and }\dim(\mathscr{D})=i\\}$

for $1\leq i\leq k$, and where
$\sigma(\mathscr{D}):=\bigcup_{x\in\mathscr{D}}\sigma(x)$.

It is easy to see that $d_{1}=d$. Moreover, the generalized weights of a code
are strictly increasing, i.e.,
$d_{1}(\mathscr{C})<d_{2}(\mathscr{C})<\ldots<d_{k}(\mathscr{C})$; see e.g.
[24]. The following are well-known bounds involving the generalized weights of
codes established respectively in [24] and [14, Theorem 1].

######  Theorem 5.6.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a code of dimension $k$ and let
$d_{1},\ldots,d_{k}$ be its generalized weights. Then:

  * (i)

$d_{i}\leq n-k+i$,

  * (ii)

$(q^{i}-1)d_{i-1}\leq(q^{i}-q)d_{i}$.

Part (i) of Theorem 5.6 is often referred to as the generalized Singleton-type
bounds.

The first two generalized weights of a code provide extremely useful
information when trying to determine the smallest underlying field size over
which some classes of codes exist. This is shown in the next result. It is, to
the best of our knowledge, the first time such a bound is derived.

######  Theorem 5.7.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a code of minimum distance $d$. If
$d_{2}=d+s$, then

$d\leq sq.$ (5.2)

###### Proof.

By Theorem 5.6 (ii) we know that
$(q^{2}-1)d\leq(q^{2}-q)d_{2}=(q^{2}-q)(d+s)$. Rewriting this equality gives
us $d\leq sq$, as desired. ∎

As a simple consequence of the previous theorem, we get the following bound.

######  Corollary 5.8.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ have dimension $k$ and minimum
distance $d$. Then

$d\leq\frac{q}{q+1}(n-k+2).$ (5.3)

###### Proof.

Let $d_{2}$ be the second generalized weight of $\mathscr{C}$. Then by Theorem
5.6 (i) we have $d_{2}-d\leq n-k+2-d$. Moreover, by applying Theorem 5.7 we
get

$d\leq q(n-k+2-d).$

The inequality above can then be rewritten a $d\leq\frac{q}{q+1}(n-k+2)$,
which proves the wanted result. ∎

In the remaining part of this section, we study the generalized weights of an
LRC. While these parameters were already considered in [12], we propose a new
approach based on a new class of code parameters. The latter turn out to be
closely related to the locality, and allow to provide concise proofs for known
results and extend them as well.

######  Notation 5.9.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be of dimension $k$,
$\mathscr{C}^{\perp}$ its dual code of dimension $k^{\perp}=n-k$ with $i$-th
generalized weight $d_{i}^{\perp}$. Define

$\mu_{i}(\mathscr{C}):=\min\\{t\,:\,d^{\perp}_{t}\geq n-k^{\perp}-(i-1)+t\\}.$

The parameter $\mu_{i}(\mathscr{C})$ captures the smallest dimension $t$ such
that all subcodes of $\mathscr{C}^{\perp}$ of dimension $t$ have support of
size at least $n-k^{\perp}-(i-1)+t$. In other words, $\mu_{i}(\mathscr{C})$ is
the smallest dimension of subscodes needed such that the generalized weight of
the dual code of said dimension has defect at least $(i-1)$ from the
generalized Singleton bound.

######  Remark 5.10.

The parameters $\mu_{i}$ can be seen as a generalization of the parameter
$\mu$ introduced in [23]. In the latter the parameter $\mu$ is defined in
terms of matroid theory terminology but gives 5.9 when translated into coding
theory language. Furthermore, the parameters $\mu_{i}$ can also be defined for
matroids, however for readability purposes we restrict to defining those
parameters in terms of coding theory terminology.

Before presenting the next result, we recall the following well-known facts;
see e.g. [15].

######  Lemma 5.11.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ have dimension $k$ and let
$S\subseteq[n]$. Then

  * (1)

$\dim(\mathscr{C}(S))+\dim(\pi_{S^{c}}(\mathscr{C}))=k$.

  * (2)

$\pi_{S}(\mathscr{C})^{\perp}=\pi_{S}(\mathscr{C}^{\perp}(S))$

As the next result shows, the parameters $\mu_{i}$ are closely related to the
generalized weights of the code $\mathscr{C}$. The following proof is inspired
by the work of [23], in which similar methods were used to prove the same
result for $i=1$.

######  Theorem 5.12.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a code of dimension $k$ and let
$d_{i}(\mathscr{C})$, for $1\leq i\leq k$, be its generalized weights. Then

$d_{i}(\mathscr{C})=n-k-\mu_{i}(\mathscr{C})+i+1.$

###### Proof.

For notation purposes, throughout the proof we let
$\mu_{i}=\mu_{i}(\mathscr{C})$, $d_{i}=d_{i}(\mathscr{C})$, and
$d_{i}^{\perp}=d_{i}(\mathscr{C}^{\perp})$. For ease of exposition, we divide
the proof into two claims.

######  Claim B.

We have $\mu_{i}\geq n-k-d_{i}+i+1$.

###### Proof of the claim.

We show that $d^{\perp}_{k^{\perp}-d_{i}+i}<n-d_{i}+1$ by constructing a
subspace of $\mathscr{C}^{\perp}$ that has the desired dimension and support.
Let $\mathscr{D}\leq\mathscr{C}$ and $S:=\sigma(\mathscr{D})$ with the
property that $\dim(\mathscr{D})=i$ and $|S|=d_{i}$. Since $\mathscr{D}$
achieves the generalized weight, it must be that $\mathscr{D}=\mathscr{C}(S)$
and by Lemma 5.11(1) we know that $\dim(\pi_{S^{c}}(\mathscr{C}))=k-i$.
Furthermore, using Lemma 5.11(2) we obtain
$\dim(\mathscr{C}^{\perp}(S^{c}))=\dim(\pi_{S^{c}}(\mathscr{C})^{\perp})=n-d_{i}-k+i$.
Define $\mathscr{D}^{\prime}=\mathscr{C}^{\perp}(S^{c})$ and note that
$\sigma(\mathscr{D}^{\prime})\leq n-d_{i}<n-d_{i}+1$. Therefore we have
$d^{\perp}_{k^{\perp}-d_{i}+1}<n-d_{i}+1$, which establishes the statement. ∎

######  Claim C.

We have $\mu_{i}\leq n-k-d_{i}+i+1$.

###### Proof of the claim.

First assume $\mu_{i}=1$. From Theorem 5.6(1), we have $d_{i}\leq n-k+i$ and
therefore $\mu_{i}=1\leq n-k-d_{i}+i+1$, as desired.

Now assume $\mu_{i}\geq 2$. Let $\mathscr{D}\leq\mathscr{C}^{\perp}$ such that
$\dim(\mathscr{D})=\mu_{i}-1$ and $\sigma(\mathscr{D})=:S$ satisfies
$|S|=d^{\perp}_{\mu_{i}-1}\leq k-i+\mu_{i}-1$. Such a subspace exists by
definition of the parameter $\mu_{i}$. Furthermore, since
$\dim(\mathscr{D})=\mu_{i}-1$, $\sigma(\mathscr{D})=S$ and
$d_{\mu_{i}-1}^{\perp}=|S|$, we must have
$\mathscr{D}=\mathscr{C}^{\perp}(S)$. Therefore using Lemma 5.11(2) we obtain:

$\displaystyle\dim(\pi_{S}(\mathscr{C}))$
$\displaystyle=\dim(\pi_{S}(\mathscr{C}^{\perp}(S))^{\perp})$
$\displaystyle=|S|-\dim(\mathscr{C}^{\perp}(S))$ $\displaystyle\leq
k-i+\mu_{i}-1-(\mu_{i}-1)$ $\displaystyle=k-i.$

The above also gives that
$|S|=\dim(\pi_{S}(\mathscr{C}))+\dim(\mathscr{D})=\dim(\pi_{S}(\mathscr{C}))+\mu_{i}-1$,
which will be used later on.

Using Lemma 5.11(1), we moreover get
$s:=\dim(\mathscr{C}(S^{c}))=k-\dim(\pi_{S}(\mathscr{C}))\geq i$. Let
$G\in\mathbb{F}_{q}^{s\times n}$ be a generator matrix of $\mathscr{C}(S^{c})$
in reduced row-echelon form (RREF). Let $\mathscr{W}=\langle g_{1},\ldots
g_{i}\rangle$, where $g_{i}$ is the $i$-th row of $G$. Clearly,
$\dim(\mathscr{W})=i$, $D:=\sigma(\mathscr{W})\subseteq S^{c}$, and since $G$
is in RREF, $\mathscr{C}(D)=\mathscr{W}$. This shows that $d_{i}\leq|D|$. Now
consider $A\subseteq S^{c}$ such that $A\cup D=S^{c}$ and $A\cap D=\emptyset$.
Note that $D^{c}=S\cup A$. By Lemma 5.11(1), we have $\dim(\pi_{A\cup
S}(\mathscr{C}))=k-\dim(\mathscr{C}(D))=k-i$. This leads to the following
chain of inequalities:

$\displaystyle k-i$ $\displaystyle=\dim(\pi_{A\cup S}(\mathscr{C}))$
$\displaystyle\leq\dim(\pi_{S}(\mathscr{C}))+\dim(\pi_{A}(\mathscr{C}))$
$\displaystyle\leq\dim(\pi_{S}(\mathscr{C}))+|A|.$

Finally, we use the facts that $d_{i}\leq|D|$ and
$|S|=\dim(\pi_{S}(\mathscr{C}))+\mu_{i}-1$ to get the following:

$\displaystyle n-d_{i}$ $\displaystyle\geq n-|D|$ $\displaystyle=|S\cup A|$
$\displaystyle=|S|+|A|$
$\displaystyle\geq\dim(\pi_{S}(\mathscr{C}))+\mu_{i}-1+k-i-\dim(\pi_{S}(\mathscr{C}))$
$\displaystyle=\mu_{i}+k-i-1.$

This shows that $\mu_{i}\leq n-d_{i}-k+i+1$, as desired. ∎

Combining Claim B with Claim C concludes the proof. ∎

Our next move is to show how the dimension and locality of a code directly
impact the parameter $\mu_{i}$. The special case of $\mu_{1}$ was already
shown in [23].

######  Lemma 5.13.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be an LRC of dimension $k$, locality
$r$, generalized weights $d_{i}$, and $\mu_{i}$ as in Notation 5.9. Then for
all $1\leq i\leq k$ we have

$\mu_{i}\geq\left\lceil\frac{k-(i-1)}{r}\right\rceil.$

###### Proof.

Since $\mathscr{C}$ has locality $r$, there exist at least $\left\lceil
k/r\right\rceil-1$ linearly independent codewords
$x_{i}\in\mathscr{C}^{\perp}$, for $1\leq i\leq\left\lceil k/r\right\rceil-1$,
of weight at most $r+1$. Let
$s:=\left\lceil(k-(i-1))/r\right\rceil-1\leq\left\lceil k/r\right\rceil-1$.
Consider $\mathscr{D}=\langle x_{1},\ldots x_{s}\rangle$. Then

$\displaystyle\sigma(\mathscr{D})$
$\displaystyle\leq(r+1)\left(\left\lceil\frac{k-i+1}{r}\right\rceil-1\right)$
$\displaystyle\leq k-i+1+r-r+\left\lceil\frac{k-i+1}{r}\right\rceil-1$
$\displaystyle<k-(i-1)+\left\lceil\frac{k-i+1}{r}\right\rceil.$

Hence $\mu_{i}>\left\lceil(k-(i-1))/r\right\rceil-1$, proving the lemma. ∎

As a simple consequence we get the following characterization of optimal LRCs
and a bound on the generalized weights of an LRC.

######  Corollary 5.14.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be a code with dimension $k$, minimum
distance $d$ and locality $r$. Furthermore, let $\mathscr{C}^{\perp}$ be its
dual code with generalized weight
$\\{d^{\perp}_{1},\ldots,d^{\perp}_{n-k}\\}$. The code $\mathscr{C}$ is an
optimal LRC if and only if $d^{\perp}_{\lceil k/r\rceil}=n-k^{\perp}+\lceil
k/r\rceil$.

###### Proof.

By Theorem 5.12, a code $\mathscr{C}$ is an optimal LRC if and only if
$\mu_{1}=\lceil k/r\rceil$. By definition, the latter is true if and only if
$d_{\lceil k/r\rceil}\geq n-k^{\perp}+\lceil k/r\rceil$. However, by Theorem
5.6(i) we also know that $d_{\lceil k/r\rceil}\leq n-k^{\perp}+\lceil
k/r\rceil$. Hence equality must hold. ∎

######  Corollary 5.15.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be an LRC of dimension $k$, locality
$r$, and let $d_{i}$ denote its generalized weights where $1\leq i\leq k$.
Then

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

###### Proof.

Combining Theorem 5.12 and Lemma 5.13 we obtain

$\displaystyle d_{i}$ $\displaystyle=n-k-\mu_{i}+i+1$ $\displaystyle\leq
n-k-\left\lceil\frac{k-(i-1)}{r}\right\rceil+i+1.\qed$

######  Remark 5.16.

Corollary 5.15 is a special case of the bound established in [12, Theorem 1]
for $(r,\delta)$-LRCs. However, the result therein is proved using the gap
numbers of a code, which differs from our approach.

Using the generalized Singleton-type bounds (see Theorem 5.6 (i)), it is
possible to determine or obtain a bound on the second generalized weight of
optimal LRC. Note that in [12, Theorem 5], the authors establish the full
generalized weight hierarchy of optimal LRCs under the assumption that $r|k$.
The proof of [12, Theorem 5] is based on the following result, which we can
prove for completeness using the theory developed in this paper.

######  Proposition 5.17.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be an optimal LRC of dimension $k$,
locality $r$, and let $d_{i}$ denote its $i$-th generalized weight, $1\leq
i\leq k$.

  * •

If $k\not\equiv 1\pmod{r}$, then $d_{2}=d_{1}+1$.

  * •

If $k\equiv 1\pmod{r}$, then $d_{2}\leq d_{1}+2$.

###### Proof.

Assume $k\not\equiv 1\pmod{r}$. First note that $\left\lceil
k/r\right\rceil=\left\lceil(k-1)/r\right\rceil$. Since $\mathscr{C}$ is
optimal, we have $d=n-k-\left\lceil k/r\right\rceil+2$. Using Theorem 5.15 we
get the following bound on $d_{2}$:

$\displaystyle d_{2}$ $\displaystyle\leq
n-k+2-(\left\lceil(k-1)/r\right\rceil)+1$ $\displaystyle\leq n-k-\left\lceil
k/r\right\rceil+3$ $\displaystyle=d_{1}+1.$

However since $d_{1}<d_{2}$ it must be that $d_{2}=d_{1}+1$. Now assume
$k\equiv 1\pmod{r}$. Then $d_{2}\leq d_{1}+2$. Therefore $\left\lceil
k/r\right\rceil=\left\lceil(k-1)/r\right\rceil-1$. Using Theorem 5.15 in a
similar way as above, we get $d_{2}\leq d_{1}+2.$ ∎

Combining Proposition 5.17 with Theorem 5.7 we get as an immediate corollary
an upper bound on the minimum distance of optimal LRCs. A similar result was
shown in [13, Theorem 2] by considering a suitable construction. We, on the
other hand, show that the following bound can be seen as a direct consequence
of the change in generalized weights of an optimal LRC.

######  Corollary 5.18.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be an optimal LRC of dimension $k$,
minimum distance $d$, and locality $r$.

  * •

If $k\not\equiv 1\pmod{r}$, then $d\leq q$.

  * •

If $k\equiv 1\pmod{r}$, then $d\leq 2q$.

######  Remark 5.19.

For $q=2$ there exist codes for which the bound in Corollary 5.18 for $k\equiv
1\pmod{r}$ is attained. For example, the simplex code of Example 5.3 is an
optimal LRC where $d=4=2q$.

We can now derive a Singleton-type bound for LRCs that depends on the field
size.

######  Proposition 5.20.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be an LRC of dimension $k$ and
locality $r$. Then

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

###### Proof.

By Theorem 5.6 we have $d_{2}\leq n-k-\lceil\frac{k-1}{r}\rceil+3$. Hence
$\smash{d_{2}-d\leq n-k-\left\lceil\frac{k-1}{r}\right\rceil+3-d}$ and
applying Theorem 5.7 we get that

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

By rewriting the inequality above we get the desired result. ∎

The previous theorem leads to interesting restrictions on the parameters of
optimal LRC, including the field size $q$.

######  Corollary 5.21.

Let $\mathscr{C}\leq\mathbb{F}_{q}^{n}$ be an optimal LRC with dimension $k$
and locality $r$.

  * •

If $k\leq q$ and $k\not\equiv 1\pmod{r}$, then $n\leq 3q$,

  * •

If $k\leq q$ and $k\equiv 1\pmod{r}$, then $n\leq 4q+1$.

###### Proof.

By rewriting Proposition 5.20 we have

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

First we assume $k\not\equiv 1\pmod{r}$. By applying the assumptions on $k$ we
then obtain:

$\displaystyle d$ $\displaystyle\leq
n-k-\left\lceil\frac{k}{r}\right\rceil+3-\frac{n-q-\lceil(q-1)/r\rceil+3}{q+1}$
$\displaystyle=n-k-\left\lceil\frac{k}{r}\right\rceil+3-\frac{n+3}{q+1}+\frac{q+\lceil(q-1)/r\rceil}{q+1}$
$\displaystyle=n-k-\left\lceil\frac{k}{r}\right\rceil+2-\frac{n+3}{q+1}+3$

Note that if $3-({n+3})/({q+1})<0$ then we get a sharper bound than (2.1).
Hence if $\mathscr{C}$ is an optimal LRC we must have $3-({n+3})/({q+1})\geq
0$, which is true if and only if $n\leq 3q$.

If $k\equiv 1\pmod{r}$ we apply a similar argument with the only difference
that $\lceil(k-1)/r\rceil=\lceil k/r\rceil-1$. We then get that $n\leq 4q+1$.
∎

######  Remark 5.22.

The previous result shows that an optimal LRC
$\mathscr{C}\in\mathbb{F}_{q}^{n}$ cannot exist when $k\leq q<(n-1)/4$.

## References

  * [1] A. Agarwal, A. Barg, S. Hu, A. Mazumdar, and I. Tamo, _Combinatorial alphabet-dependent bounds for locally recoverable codes_ , IEEE Transactions on Information Theory 64 (2018), no. 5, 3481–3492.
  * [2] A. Barg, K. Haymaker, E. Howe, G. Matthews, and A. Várilly-Alvarado, _Locally recoverable codes from algebraic curves and surfaces_ , Algebraic Geometry for Coding Theory and Cryptography: IPAM, Los Angeles, CA, February 2016, Springer, 2017, pp. 95–127.
  * [3] A. Barg, I. Tamo, and S. Vlăduţ, _Locally recoverable codes on algebraic curves_ , IEEE Transactions on Information Theory 63 (2017), no. 8, 4928–4939.
  * [4] V. Cadambe and A. Mazumdar, _Bounds on the size of locally recoverable codes_ , IEEE transactions on information theory 61 (2015), no. 11, 5787–5794.
  * [5] P. Delsarte, _An algebraic approach to the association schemes of coding theory_ , Philips Res. Rep. Suppl. 10 (1973), vi+–97.
  * [6] R. Freij-Hollanti, C. Hollanti, and T. Westerbäck, _Matroid theory and storage codes: bounds and constructions_ , Network Coding and Subspace Designs, Springer, 2018, pp. 385–425.
  * [7] H. Gluesing-Luerssen, _Fourier-reflexive partitions and Macwilliams identities for additive codes_ , Designs, Codes and Cryptography 75 (2015), 543–563.
  * [8] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, _On the locality of codeword symbols_ , IEEE Transactions on Information Theory 58 (2012), no. 11, 6925–6934.
  * [9] M. Grezet, R. Freij-Hollanti, T. Westerbäck, and C. Hollanti, _Alphabet-dependent bounds for linear locally repairable codes based on residual codes_ , IEEE Transactions on Information Theory 65 (2019), no. 10, 6089–6100.
  * [10] A. Gruica, B. Jany, and A. Ravagnani, _Duality and LP bounds for codes with locality_ , Proc. IEEE Information Theory Workshop (2023).
  * [11] V. Guruswami, C. Xing, and C. Yuan, _How long can optimal locally repairable codes be?_ , IEEE Transactions on Information Theory 65 (2019), no. 6, 3662–3670.
  * [12] J. Hao and B. Chen, _On the generalized Hamming weights of $(r,\delta)$-locally repairable codes_, IEEE Access 8 (2020), 149706–149713.
  * [13] J. Hao, S. Xia, K. Shum, B. Chen, F. Fu, and Y. Yang, _Bounds and constructions of locally repairable codes: parity-check matrix approach_ , IEEE Transactions on Information Theory 66 (2020), no. 12, 7465–7474.
  * [14] T. Helleseth, T. Klove, V. Levenshtein, and Ø. Ytrehus, _Bounds on the minimum support weights_ , IEEE transactions on information theory 41 (1995), no. 2, 432–440.
  * [15] C.W. Huffman and V. Pless, _Fundamentals of error-correcting codes_ , Cambridge University Press, 2003.
  * [16] J. MacWilliams, _A theorem on the distribution of weights in a systematic code_ , Bell System Technical Journal 42 (1963), no. 1, 79–94.
  * [17] G. Micheli, _Constructions of locally recoverable codes which are optimal_ , IEEE Transactions on Information Theory 66 (2020), no. 1, 167–175.
  * [18] N. Prakash, G. Kamath, V. Lalitha, and P. Kumar, _Optimal linear codes with a local-error-correction property_ , 2012 IEEE International Symposium on Information Theory Proceedings, IEEE, 2012, pp. 2776–2780.
  * [19] A.S. Rawat, A. Mazumdar, and S. Vishwanath, _Cooperative local repair in distributed storage_ , EURASIP Journal on Advances in Signal Processing 2015 (2015), 1–17.
  * [20] J. Simonis, _Macwilliams identities and coordinate partitions_ , Linear Algebra and its Applications 216 (1995), 81–91.
  * [21] R. Singleton, _Maximum distance $q$-nary codes_, IEEE Transactions on Information Theory 10 (1964), no. 2, 116–118.
  * [22] I. Tamo and A. Barg, _A family of optimal locally recoverable codes_ , IEEE Transactions on Information Theory 60 (2014), no. 8, 4661–4676.
  * [23] I. Tamo, D. Papailiopoulos, and A. Dimakis, _Optimal locally repairable codes and connections to matroid theory_ , IEEE Transactions on Information Theory 62 (2016), no. 12, 6661–6671.
  * [24] V. Wei, _Generalized hamming weights for linear codes_ , IEEE Transactions on information theory 37 (1991), no. 5, 1412–1418.


This paper is published on behalf of the Euclid consortium.
Further author information: (Send correspondence to J.S.)
J. S.: E-mail<EMAIL_ADDRESS>Telephone: +44 (0)1908 652698

# Tracking radiation damage of Euclid VIS detectors after 1 year in space

Jesper Skottfelt  Centre for Electronic Imaging, The Open University, Walton
Hall, Milton Keynes, MK7 6AA, United Kingdom  Matt Wander  Centre for
Electronic Imaging, The Open University, Walton Hall, Milton Keynes, MK7 6AA,
United Kingdom  Mark Cropper  Mullard Space Science Laboratory, University
College London, Holmbury St Mary, Dorking Surrey RH5 6NT, United Kingdom  Ben
Dryer  Centre for Electronic Imaging, The Open University, Walton Hall, Milton
Keynes, MK7 6AA, United Kingdom  David J. Hall  Centre for Electronic Imaging,
The Open University, Walton Hall, Milton Keynes, MK7 6AA, United Kingdom
Richard Hayes  Department of Physics, Durham University, South Road, Durham
DH1 3LE, United Kingdom  Bradley Kelman  Centre for Electronic Imaging, The
Open University, Walton Hall, Milton Keynes, MK7 6AA, United Kingdom  Tom
Kitching  Mullard Space Science Laboratory, University College London,
Holmbury St Mary, Dorking Surrey RH5 6NT, United Kingdom  Ralf Kohley
European Space Agency / ESAC, Villanueva de la Cañada, E-28692 Madrid, Spain
David Lagattuta  Department of Physics, Durham University, South Road, Durham
DH1 3LE, United Kingdom  Zoe Lee-Payne  Centre for Electronic Imaging, The
Open University, Walton Hall, Milton Keynes, MK7 6AA, United Kingdom  Patricia
Liebing  Mullard Space Science Laboratory, University College London, Holmbury
St Mary, Dorking Surrey RH5 6NT, United Kingdom  Richard Massey  Department of
Physics, Durham University, South Road, Durham DH1 3LE, United Kingdom  Henry
Joy McCracken  Institut d’Astrophysique de Paris, 98 bis Boulevard Arago,
75014 Paris, France  Reiko Nakajima  Argelander-Institut für Astronomie, Auf
dem Hügel 71, D-53121 Bonn, Germany  James Nightingale  School of Mathematics,
Statistics and Physics, Newcastle University, Herschel Building, Newcastle-
upon-Tyne, NE1 7RU, UK  Department of Physics, Durham University, South Road,
Durham DH1 3LE, United Kingdom

###### Abstract

Due to the space radiation environment at $L_{2}$, ESA’s Euclid mission will
be subject to a large amount of highly energetic particles over its lifetime.
These particles can cause damage to the detectors by creating defects in the
silicon lattice. These defects degrade the returned image in several ways, one
example being a degradation of the Charge Transfer Efficiency, which appears
as readout trails in the image data. This can be problematic for the Euclid
VIS instrument, which aims to measure the shapes of galaxies to a very high
degree of accuracy. Using a special clocking technique called trap pumping,
the single defects in the CCDs can be detected and characterised. Being the
first instrument in space with this capability, it will provide novel insights
into the creation and evolution of radiation-induced defects and give input to
the radiation damage correction of the scientific data. We present the status
of the radiation damage of the Euclid VIS CCDs and how it has evolved over the
first year in space.

###### keywords:

Euclid mission, CCD, radiation damage, trap pumping

##  1 INTRODUCTION

The main purpose of the VIS instrument[1] on board the European Space Agency’s
Euclid mission[2] is to measure the shape of galaxies to very high precision
and from that infer the distribution of dark matter in the Universe. For this
to be possible, all systematic effects need to be well-understood and
controlled to a very high degree of accuracy.

One such systematic effect stems from the radiation damage the spacecraft and
imaging sensors will receive at $L_{2}$, the 2nd Sun-Earth Lagrangian point
1.5 million km from Earth. The VIS instrument uses silicon-based charge-
coupled devices (CCDs), which can be damaged by highly energetic particles,
mainly protons from the Sun or the Galactic plane. When these particles hit
the device, they are able to release silicon atoms from the silicon lattice,
thus creating defects. During integration and readout of the CCDs, these
defects can act as traps that can capture photo-electrons and release them at
a later point in time, depending on the trap “species” and device temperature.
Because of how a CCD is operated, where charge is transferred across the image
array through many pixels to be read out, these traps can create trails in the
scientific data. This effect is known as charge transfer inefficiency (CTI),
i.e. the fraction of charge left behind when it is transferred from one pixel
to the next. After time in space, this shape change will dominate over the
shape distortions due to weak lensing that Euclid is measuring, and it is
crucial that the effect of CTI is well understood and can be corrected to very
high accuracy.

For Euclid VIS the Algorithm for CTI Correction (ArCTIC)[3, 4] is used to
correct CTI in science data. ArCTIC assumes that traps delay electrons
stochastically, but with a characteristic time that (in aggregate) leads to
trails behind bright objects that are roughly a decaying exponential. The free
parameters in this model include the density of traps in a CCD and their
distribution of release times. They can be calibrated by fitting the observed
trails behind an injected block of charge. However, sums of (nearly)
exponential functions are inherently degenerate and the results can be
distorted by stray light, bias, other electronic effects[5]. There is,
therefore, a risk that a non-optimal set of parameters are found.

To provide additional, independent information about some traps, we also use
Trap Pumping (TP; also known as pocket pumping). This was described by Ref. 6
as a method to identify pixels with one or more traps in the silicon lattice.
This has been further developed by Refs. 7, 8, 9, 10 to give more information
about the trap species, such as emission time constant and energy level of the
trap.

TP was adapted for the VIS CCDs and has been thoroughly tested as part of the
on-ground irradiation campaign[11, 12, 13]. Here it was shown that getting
this extra information about the trap parameters can inform and improve the
radiation damage correction. TP was therefore implemented as part of the daily
calibration routines that the VIS instrument performs in orbit.

With the launch of the Euclid telescope on 1 July 2023, the spacecraft has now
spent almost a year in space. Here we give a short introduction to the TP
method, followed by initial in-orbit trap pumping results and how the trap
landscape has evolved over the first year in space.

##  2 TRAP PUMPING TECHNIQUE

TP is a technique that can localise and characterise traps in the silicon
lattice down to the electrode, and even sub-electrode level of the single
pixels.[14]. It works by creating a uniform charge across the entire device,
either by illumination with a flat field, or by charge injection. The charge
is then shifted a number of clock phases forward and then back to its origin,
using the same phase time ($t_{\rm ph}$) for each step. If a trap that has
captured an electron, releases it when the charge cloud from the adjacent
pixel is closer by, the electron will be ejected and therefore shifted to that
pixel. Repeating this shuffle many times will generate a dipole, i.e. a pixel
depleted of charge and an adjacent pixel with excess charge compared to the
uniform level. From Shockley-Read-Hall theory[15, 16] it can be found that the
intensity (defined as half of the contrast) of this dipole can be determined
by the emission time constant ($\tau_{\rm e}$) of the trap and the $t_{\rm
ph}$ used in the shuffling, using the following equation[7]:

$I=N\cdot P\cdot\left[\exp\left(\frac{-t_{\rm ph}}{\tau_{\rm
e}}\right)-\exp\left(\frac{-2t_{\rm ph}}{\tau_{\rm e}}\right)\right]\,,$ (1)

where $N$ is the number of pumps and $P$ is the pumping efficiency, which is
related to the capture probability of the trap[9].

By repeating this process using different $t_{\rm ph}$values, a dipole
intensity curve as a function of $t_{\rm ph}$ can be measured, and by fitting
this curve with Equation 1, the best values for $\tau_{\rm e}$ and $P$ will be
found. Doing this process at different temperatures allows a fit to the energy
level of the trap species, which can be used to get a deeper understanding of
the origin of the trap. However, as the VIS focal plane is kept at a constant
temperature, this last step cannot be performed in space but single
temperature results can be related to full on-ground testing.

As an example, the standard clocking scheme for a three-phase device is to
clock the charge through phases 1-2-3-1′-3-2-1, where 1′ denotes the first
phase in the next pixel. This will create an “up-down” dipole for traps under
phase 2 and a “down-up” dipole for traps under phase 3, which means that
electrode position can be obtained, resulting in sub-pixel trap position. To
get the traps under phase 1, the clocking scheme can be started at either
phase 2 or 3.

##  3 TRAP PUMPING FOR Euclid VIS

The VIS instrument focal plane comprises of a 6$\times$6 mosaic of CCD273s,
which are manufactured by Teledyne-e2v in Chelmsford, UK. Each CCD273 has
$\sim$4k $\times$ 4k 12µm square pixels and four outputs, one in each corner,
giving 2048(H) $\times$ 2066(V) pixels for each quadrant. They are
manufactured on high-resistivity epitaxial silicon and back-thinned to 40 µm
thickness[17].

The devices have a charge injection structure in the middle of the device,
from which charge can be injected into all 4 quadrants. This is used to inject
a uniform signal to be used for the TP technique. The amount of charge that is
injected depends on the exact geometry of the charge injection electrodes in
each column, causing a large column-to-column variation, but the noise on the
charge injected within a column is very low. Because of the CCD273 pixel
design, more charge is injected in the upper half of the device (quadrants
G-H) than the lower half (quadrants E-F).

The pixels have four phases in the image region, or parallel register,
designed with alternating widths of 4-2-4-2 µm. The readout, or serial,
register pixels have three equal-sized phases with a width of 4 µm.

As TP was originally developed for 3-phase devices, the technique had to be
further updated to be used for a 4-phase device, like the parallel direction
for the CCD273. The resulting clocking scheme is presented in Ref. 14 and is
named the sub-pixel clocking scheme, as the charge will only see a part of the
pixel. The scheme works by clocking the charge through phases 1-2-3-2-1, which
will only probe the traps in the outer parts of phases 1 and 3, providing not
only sub-pixel, but sub-phase positional information about the trap. Using
four versions of this clocking scheme, each starting in a different phase, the
traps in both sides of all four phases can be detected.

TP is part of the in-orbit calibration routines for Euclid VIS, which has six
daily slots dedicated to TP, however, only one frame can be read out in each
slot. During the on-ground calibration campaign, 50 or 100 $t_{\rm ph}$ value
measurements were used to build the dipole curves for parallel, or vertical,
trap pumping (VTP) but running that many $t_{\rm ph}$ values in orbit would
take 8 to 16 days. Taking data for a single dipole curve over such a long
period would risk invalidating the data as the trap landscape would change
over that time. By running an analysis on many subsets of the on-ground data,
it was found that taking 11 $t_{\rm ph}$ values between 10 µs and 16 ms gave
the optimal balance between coverage of the dipole curve to avoid fitting
errors, keeping within the time allocated to each TP measurement, and taking
the data within a reasonable time frame.

It therefore takes less than two days to get a dipole curve for a single set
of VTP parameters. With four start phases for the clocking scheme and two
different charge injection levels, a full parameter set can be measured in
about 15 days.

As the serial register consists of a single row of pixels, serial trap pumping
(STP) is done slightly differently. After the charge has been injected into
the device, a single line of charge is clocked into the serial register. STP
is performed on this line of charge, which is then read out and the next line
clocked into the serial register, and so on. With the Euclid VIS electronics,
it is possible to define eight different parameter sets to be read out in a
single frame. The serial $t_{\rm ph}$ values can therefore be covered with
just three TP calibration slots. With two start phases for the serial clocking
scheme and two signal levels, only 12 slots are needed to cover all the STP
parameters. However, due to the need for optimising the serial readout, the
VIS electronics is not able to perform STP in the normal way. The output and
analysis are therefore slightly different and will not be detailed in this
paper.

##  4 IN-ORBIT TRAP PUMPING MEASUREMENTS

Euclid was launched on 1 July 2023 on a Space-X Falcon 9 rocket. It had a
6-week spacecraft commissioning phase, including the two-week transit to
$L_{2}$, and was then ready to start the Performance Verification (PV) phase.
A full set of VTP and STP data was acquired over 12 hours on 15 August as part
of PV (in the following referred to as PV1).

A small section of a PV1 VTP raw data frame, and the same section after
subtracting the charge injection level for each line, are shown in Fig. 1.

Figure 1: (left) Small section of a raw VTP frame, showing the large column-
to-column non-uniformity of the charge injection, and (right) the same
section, where the median of each column has been subtracted revealing the
dipoles.

The VTP data was analysed using an implementation of the algorithm described
in Sec. 2 and a histogram of the detected traps are shown in Fig. 2. This
shows all the traps found in one quadrant of the device, by the combined
result for all four starting phases for the clocking scheme.

Figure 2: Histograms of $\tau_{\rm e}$values for the G quadrant of all the
devices from the PV1 VTP data. The histograms are displayed in the same way as
the devices are positioned in the focal plane.

After only 1.5 months in space, it is not expected that the devices have
incurred any significant damage and the trap landscape should therefore be
very similar to the pre-launch trap landscape. All of the devices show three
distinct peaks at the same location. These peaks are consistent with the pre-
irradiation peaks found in on-ground data[18]. The majority of these are
intrinsic, or manufacturing, traps, which are created by the intrinsic Carbon
and Oxygen impurities in the silicon wafers, which form stable defects with
Phosphorus and Boron atoms used in the doping process of the devices[14]. This
can be further evidenced by looking at the number of traps in each device and
comparing these to the batch numbers of the devices (see Fig. 3), which show a
clear relationship between the silicon wafers used for the device and the
number of intrinsic traps there are.

Figure 3: Number of intrinsic traps as a function of signal level, for each of
the four quadrants E-H, showing the difference in injection level between the
lower half (quadrants E-F) and the upper half (quadrants G-H). The colours
represent the silicon wafer batches from which the devices are manufactured.
Several CCDs belong to the same batch, which are made from the same bulk
silicon. The number of traps detected further depends on the signal level as
this changes the size of the charge cloud.

On-ground testing has shown that the number of intrinsic traps will be
constant across the device and Fig. 3 therefore also shows that there is a
clear correlation between the signal level and the number of traps found in
the device. As the E-F quadrants have a lower amount of charge injected than
the G-H quadrants, the charge cloud will be smaller in the E-F quadrants and
will “see” fewer traps than in the G-H quadrants for the same device.

A second full TP parameter data set (PV2) was acquired as part of the PV phase
on 31 October, 2.5 months after the first data was obtained. Fig. 4 shows a
histogram of the differences between PV1 and PV2. Here traps in the same pixel
and phase in the two datasets with $\log(\tau_{\rm e}{})$ values within 7% of
each other are taken to be the same trap, to account for inherent noise in the
$\tau_{\rm e}$ measurement (and any temperature difference of the devices
between PV1 and PV2). This should remove all the intrinsic traps and only
display the traps created in the 2.5 months after the PV1 data was obtained.

Figure 4: Histograms of difference in traps detected between PV1 (15 August
2023) and PV2 (31 October 2023).

From Fig. 4 it can be seen that many traps are being created with a continuum
of $\tau_{\rm e}$ values rather than in the well-defined divacancy trap
peak[19] with a $\tau_{\rm e}$ value of about 220 µs, at the VIS focal plane
operating temperature of about 153 K. This is consistent with the results
obtained during the CCD273 irradiation campaign, where the devices were
irradiated cold and kept cold for subsequent testing. Here it was found that
most traps were created as continuum traps, which over time re-orient in the
silicon lattice to a more optimal energy level closer to the divacancy peak.
Some of the histograms have negative values, which could be attributed to
traps created in the short period before PV1 and going through the same
process of annealing towards the divacancy peak.

Since mid-March full TP parameter sets have been obtained through the regular
six daily TP measurements and fortnightly updates of the trap densities of the
focal plane are therefore available. Fig. 5 shows the new traps created in the
period between PV2 and the end of March 2024.

Figure 5: Histograms of difference in traps detected between PV2 (31 October
2023) and end-March 2024.

This figure looks very similar to the Fig. 4, with a distinct divacancy peak
at 220 µs, a broad hump around 20 ms, and a significant number of traps with a
continuum of $\tau_{\rm e}$values, which is all consistent with the on-ground
radiation damage testing. The traps seem to be generated fairly uniformly
across the focal plane, maybe with slightly more generated in the upper half,
especially the right-hand side, and slightly fewer in the lower part of the
focal plane. This difference does not seem to be correlated with either the
mean injection level of the quadrant or the intrinsic trap density of the
device. It could be related to the general shielding of the focal plane or
another effect, but the cause for this non-uniformity in trap distribution
will become clearer as the total damage increases.

The number of new traps generated since the initial PV1 data was obtained, is
shown in Fig. 6. While this is early in the mission and only a few data points
are available, it shows a clear linear trend of trap generation. However, some
of the devices, especially in the upper right-hand side of the focal plane,
might be showing indications of jumps. This could be caused by large Coronal
Mass Ejections (CMEs), similar to what was found in the Gaia CTI data[20], and
it will be interesting to track if this behaviour continues.

Figure 6: Number of traps found in one quadrant of each device since the
launch of Euclid. Note, that the vertical axes of all the sub-plots are scaled
equally, making the number of radiation-induced traps in each device directly
comparable.

##  5 CONCLUSION

Radiation damage will have a major impact on the Euclid VIS detectors and it
is therefore of great importance that the effect of this damage is corrected
for in the VIS data. The TP method can detect single defects in the silicon
lattice of CCDs, allowing for the detection and tracking of radiation-induced
defects in the VIS detectors.

The initial TP data obtained at the very beginning of the mission shows three
distinct species of intrinsic defects. These can be attributed to the
intrinsic Carbon and Oxygen impurities in the silicon, which mixed with the
Phosphorus and Boron dopants, create stable defects in the manufacturing
process.

Subsequent TP data show that traps are created in a continuum and then re-
orienting themselves in the silicon lattice to obtain a more optimal energy
level closer to the divacancy peak, which matches what was found during the
on-ground radiation damage campaign of the CCD273 devices. They also show a
small variation in trap generation across the focal plane, and that the traps
are generated linearly over time, however, with some indication of jumps that
could be caused by CMEs.

The TP method will be performed throughout the Euclid mission and this will
provide further measurements of the evolution of damage in the VIS CCDs. The
results shown thus far indicate that performing trap pumping in orbit allows
the evolution of the trap landscape and therefore CTI of the device to be
measured and understood with much more precision than previously possible.
This will allow models to correct CTI (e.g. ArCTIC) to be more accurate and
therefore meet the science requirements of Euclid for a longer time in the
harsh radiation environment in space. Using this technique allows Euclid to
perform its science goals at higher irradiation levels, hopefully resulting in
a longer useful operating lifetime.

###### Acknowledgements.

The authors acknowledge the Euclid Consortium, the European Space Agency, and
a number of agencies and institutes that have supported the development of
Euclid, in particular the Agenzia Spaziale Italiana, the Austrian
Forschungsförderungsgesellschaft funded through BMK, the Belgian Science
Policy, the Canadian Euclid Consortium, the Deutsches Zentrum für Luft- und
Raumfahrt, the DTU Space and the Niels Bohr Institute in Denmark, the French
Centre National d’Etudes Spatiales, the Fundação para a Ciência e a
Tecnologia, the Hungarian Academy of Sciences, the Ministerio de Ciencia,
Innovación y Universidades, the National Aeronautics and Space Administration,
the National Astronomical Observatory of Japan, the Netherlandse
Onderzoekschool Voor Astronomie, the Norwegian Space Agency, the Research
Council of Finland, the Romanian Space Agency, the State Secretariat for
Education, Research, and Innovation (SERI) at the Swiss Space Office (SSO),
and the United Kingdom Space Agency. A complete and detailed list is available
on the Euclid web site (http://www.euclid-ec.org).

## References

  * [1] Euclid Collaboration: Cropper, M., Al Bahlawan, A., Amiaux, J., et al., “Euclid. II. The VIS Instrument,” A&A, submitted , arXiv:2405.13492 (May 2024).
  * [2] Euclid Collaboration: Mellier, Y., Abdurro’uf, Acevedo Barroso, J., Achúcarro, A., et al., “Euclid. I. Overview of the Euclid mission,” A&A, submitted , arXiv:2405.13491 (May 2024).
  * [3] Massey, R., Stoughton, C., Leauthaud, A., Rhodes, J., Koekemoer, A., Ellis, R., and Shaghoulian, E., “Pixel-based correction for Charge Transfer Inefficiency in the Hubble Space Telescope Advanced Camera for Surveys,” MNRAS 401, 371–384 (Jan. 2010).
  * [4] Massey, R., Schrabback, T., Cordes, O., Marggraf, O., Israel, H., Miller, L., Hall, D., Cropper, M., Prod’homme, T., and Niemi, S.-M., “An improved model of charge transfer inefficiency and correction algorithm for the Hubble Space Telescope,” MNRAS 439, 887–907 (Mar. 2014).
  * [5] Israel, H., Massey, R., Prod’homme, T., Cropper, M., Cordes, O., Gow, J., Kohley, R., Marggraf, O., Niemi, S., Rhodes, J., Short, A., and Verhoeve, P., “How well can charge transfer inefficiency be corrected? A parameter sensitivity study for iterative correction,” MNRAS 453, 561–580 (Oct. 2015).
  * [6] Janesick, J. R., [Scientific charge-coupled devices ], SPIE-Intl Soc Optical Eng (2001).
  * [7] Hall, D. J., Murray, N. J., Holland, A. D., Gow, J., Clarke, A., and Burt, D., “Determination of In Situ Trap Properties in CCDs Using a “Single-Trap Pumping” Technique,” IEEE Transactions on Nuclear Science 61, 1826–1833 (Aug. 2014).
  * [8] Hall, D. J., Wood, D., Murray, N. J., Gow, J. P. D., Chroneos, A., and Holland, A., “In situ trap properties in CCDs: the donor level of the silicon divacancy,” Journal of Instrumentation 12, P01025 (Jan. 2017).
  * [9] Skottfelt, J., Hall, D. J., Dryer, B., Bush, N., Gow, J. P. D., and Holland, A. D., “Importance of charge capture in interphase regions during readout of charge-coupled devices,” Journal of Astronomical Telescopes, Instruments, and Systems 4, 018005 (Jan. 2018).
  * [10] Bush, N., Hall, D., and Holland, A., “Proton-induced traps in electron multiplying charge-coupled devices,” Journal of Astronomical Telescopes, Instruments, and Systems 7, 016003 (Jan. 2021).
  * [11] Lee-Payne, Z., Skottfelt, J., and Dryer, B., “Euclid ccd273-84 em3 pre-irradiation test report,” Tech. Rep. Open-Euclid-TR-40, Open University (Mar 2022).
  * [12] Skottfelt, J., Hall, D. J., Gow, J. P. D., Murray, N. J., Holland, A. D., and Prod’homme, T., “Comparing simulations and test data of a radiation damaged charge-coupled device for the euclid mission,” Journal of Astronomical Telescopes, Instruments, and Systems 3(2), 028001 (2017).
  * [13] Skottfelt, J., Hall, D. J., Dryer, B., Burgon, R., and Holland, A. D., “C3tm: Cei ccd charge transfer model for radiation damage analysis and testing,” in [High Energy, Optical, and Infrared Detectors for Astronomy VIII ], Proceedings 10709, Society of Photo-Optical Instrumentation Engineers (July 2018).
  * [14] Skottfelt, J., Hall, D. J., Dryer, B., Bush, N., Campa, J., Gow, J. P. D., Holland, A. D., Jordan, D., and Burt, D., “Trap pumping schemes for the Euclid CCD273 detector: characterisation of electrodes and defects,” Journal of Instrumentation 12, C12033 (Dec. 2017).
  * [15] Shockley, W. and Read, W. T., “Statistics of the Recombinations of Holes and Electrons,” Physical Review 87, 835–842 (Sept. 1952).
  * [16] Hall, R. N., “Electron-Hole Recombination in Germanium,” Physical Review 87, 387–387 (July 1952).
  * [17] Short, A. D., Barry, D., Berthe, M., Boudin, N., Boulade, O., Cole, R., Cropper, M., Duvet, L., Endicott, J., Gaspar Venancio, L., Gow, J., Guttridge, P., Hall, D., Holland, A., Israel, H., Kohley, R., Laureijs, R., Lorenzo Alvarez, J., Martignac, J., Maskell, J., Massey, R., Murray, N., Niemi, S.-M., Pool, P., Pottinger, S., Prod’homme, T., Racca, G., Salvignol, J.-C., Suske, W., Szafraniec, M., Verhoeve, P., Walton, D., and Wheeler, R., “The euclid vis ccd detector design, development, and programme status,” Proc. SPIE 9154, 91540R–91540R–13 (2014).
  * [18] Skottfelt, J., “Vis ground calibration campaign trap pumping analysis,” Tech. Rep. Open-Euclid-TR-37, Open University (Jan 2021).
  * [19] Wood, D., Hall, D., Gow, J. P. D., and Holland, A., “A study of the double-acceptor level of the silicon divacancy in a proton irradiated n-channel ccd,” SPIE Proceedings: High Energy, Optical, and Infrared Detectors for Astronomy VII 9915 (August 2016).
  * [20] Crowley, C., Kohley, R., Hambly, N. C., Davidson, M., Abreu, A., van Leeuwen, F., Fabricius, C., Seabroke, G., de Bruijne, J. H. J., Short, A., Lindegren, L., Brown, A. G. A., Sarri, G., Gare, P., Prusti, T., Prod’homme, T., Mora, A., Martín-Fleitas, J., Raison, F., Lammers, U., O’Mullane, W., and Jansen, F., “Gaia data release 1 - on-orbit performance of the gaia ccds at l2,” A&A 595, A6 (2016).