# Erasure codes with symbol locality and group decodability for distributed
storage

Wentu Song  Singapore University of Technology
and Design, Singapore
Email<EMAIL_ADDRESS>Son Hoang Dau  Singapore University of
Technology
and Design,Singapore
Email<EMAIL_ADDRESS>Chau Yuen  Singapore University of Technology
and Design, Singapore
Email<EMAIL_ADDRESS>
###### Abstract

We introduce a new family of erasure codes, called _group decodable code
(GDC)_ , for distributed storage system. Given a set of design parameters
$\\{\alpha,\beta,k,t\\}$, where $k$ is the number of information symbols, each
codeword of an $(\alpha,\beta,k,t)$-group decodable code is a $t$-tuple of
strings, called _buckets_ , such that each bucket is a string of $\beta$
symbols that is a codeword of a $[\beta,\alpha]$ MDS code (which is encoded
from $\alpha$ information symbols). Such codes have the following two
properties:

  * (P1)

_Locally Repairable_ : Each code symbol has locality
$(\alpha,\beta-\alpha+1)$.

  * (P2)

_Group decodable_ : From each bucket we can decode $\alpha$ information
symbols.

We establish an upper bound of the minimum distance of
$(\alpha,\beta,k,t)$-group decodable code for any given set of
$\\{\alpha,\beta,k,t\\}$; We also prove that the bound is achievable when the
coding field $\mathbb{F}$ has size $|\mathbb{F}|>{n-1\choose k-1}$.

##  I Introduction

Distributed storage systems (DSS) are becoming increasingly important due to
the explosively grown demand for large-scale data storage, including large
files and video sharing, social networks, and back-up systems. Distributed
storage systems store a tremendous amount of data using a massive collection
of distributed storage nodes and, to ensure reliability against node failures,
introduce a certain of redundancy.

The simplest form of redundancy is replication. DSS with replication are very
easy to implement, but extremely inefficient in storage efficiency, incurring
tremendous waste in devices and equipment. In recent years, some efficient
schemes for distributed storage systems, such as erasure codes [1] and
regenerating codes [2], are proposed. We focus on erasure codes in this paper.

MDS codes are the most efficient erasure codes in term of storage efficiency.
When use an $[n,k]$ MDS code, the data file that need to be stored is divided
into $k$ information packets, where each packet is a symbol of the coding
field. These $k$ information packets are encoded into $n$ packets and stored
in $n$ storage nodes such that each node stores one packet. Then the original
file can be recovered from any $k$ out of the $n$ coded packets. Although MDS
code is storage optimal, it is not efficient for node repair. That is, when
one storage node fails, we must download the whole file from some other $k$
nodes to reconstruct the coded packet stored in it.

To construct erasure codes with more repair efficiency than MDS codes, the
concepts of locality and locally repairable code (LRC) were introduced [3, 4,
5]. Let $1\leq\alpha\leq k$ and $\delta\geq 2$. The $i$th code symbol
$c_{i}~{}(1\leq i\leq n)$ in an $[n,k]$ linear code $\mathcal{C}$ is said to
have locality $(\alpha,\delta)$ if there exists a subset
$S_{i}\subseteq[n]=\\{1,2,\cdots,n\\}$ containing $i$ and of size
$|S_{i}|\leq\alpha+\delta-1$ such that the punctured subcode of $\mathcal{C}$
to $S_{i}$ has minimum distance at least $\delta$. We will call each subset
$\\{c_{j};j\in S_{i}\\}$ a _repair group_. Thus, if $c_{i}$ has locality
$(\alpha,\delta)$, then $c_{i}$ can be computed from any $|S_{i}|-\delta+1$
other symbols in the repair group $\\{c_{j};j\in S_{i}\\}$. A code is said to
have all-symbol locality $(\alpha,\delta)$ (or is called an
$(\alpha,\delta)_{a}$ code) if all of its code symbols have locality
$(\alpha,\delta)$. Note that $|S_{i}|-\delta+1\leq\alpha$. The code has a
higher repair efficiency than MDS code if $\alpha<k$. The minimum distance of
an $(\alpha,\delta)_{a}$ linear code is bounded by (See [4]) :

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

However, for the case that $(\alpha+\delta-1)\nmid n$ and $\alpha|k$, there
exists no $(\alpha,\delta)_{a}$ linear code achieving the above bound [6].

The most common case of $(\alpha,\delta)_{a}$ linear code is that $n$ is
divisible by $\alpha+\delta-1$. For this case, in the constructions presented
in the literature, all code symbols of an $(\alpha,\delta)_{a}$ linear code
are usually divided into $t=\frac{n}{\alpha+\delta-1}$ mutually disjoint
repair groups such that each repair group is a codeword of an
$[\alpha+\delta-1,\alpha]$ MDS code. Fig. 1 illustrates a $(4,3)_{a}$
systematic linear code with $n=18$ and $k=6$, where $x_{1},\cdots,x_{6}$ are
the information symbols and $y_{1},\cdots,y_{12}$ are the parities. All code
symbols are divided into three groups and each group is a codeword of a
$[6,4]$ MDS code. By constructing the parities elaborately, the code can be
distance optimal according to (1).

Fig 1: Illustration of a systematic locally repairable code: The information
symbols $x_{1},\cdots,x_{6}$ are encoded into
$x_{1},\cdots,x_{6},y_{1},\cdots,y_{12}$ that are divided into three groups.
Each group is a codeword of a $[6,4]$ MDS code.

As pointed out in [10], in distributed storage applications there are subsets
of the data that are accessed more often than the remaining contents (they are
termed “hot data”). Thus, a desired property of a distributed storage system
is that the subsets of hot data can be retrieved easily and by multiple ways.
For example, for the storage system illustrated by Fig. 1, suppose $x_{1}$ is
hot data. There are two “easy ways” to retrieve it from the system: Downloaded
$x_{1}$ directly from the node where it is stored, or decode it from any four
coded symbols in the first group. Another way is to decode it from some six
coded symbols, but this is not an easy way because to decode $x_{1}$, one has
to decode the whole data file.

Fig 2: Illustration of a $(4,6,6,3)$-group decodable code:
$x_{1},\cdots,x_{6}$ are information symbols and $z_{1},\cdots,z_{6}$ are
parities. Each codeword has $3$ buckets and each bucket is a codeword of a
$[6,4]$ MDS code that is encoded from $4$ information symbols. Clearly, each
bucket is a repair group.

In this work, we introduce a new family of erasure codes, called _group
decodable code (GDC)_ , for distributed storage system, which can provide more
options of easy ways to retrieve each information symbol than systematic
codes. Given a set of design parameters $\\{\alpha,\beta,k,t\\}$, where $k$ is
the number of information symbols, each codeword of an
$(\alpha,\beta,k,t)$-group decodable code is a $t$-tuple of strings, called
_buckets_ , such that each bucket is a string of $\beta$ symbols that is a
codeword of a $[\beta,\alpha]$ MDS code (which is encoded from $\alpha$
information symbols). So such codes have the following two properties:

  * (P1)

_Locally Repairable_ : Each code symbol has locality
$(\alpha,\beta-\alpha+1)$.

  * (P2)

_Group decodable_ : From each bucket we can decode $\alpha$ information
symbols.

Fig. 2 illustrates a $(4,6,6,3)$-group decodable code. There are six
information symbols $x_{1},\cdots,x_{6}$. Each codeword has $3$ buckets and
each bucket is a codeword of a $[6,4]$ MDS code that is encoded from $4$
information symbols. Clearly, each bucket is a repair group. So each code
symbol of this code has locality $(4,3)$. Moreover, this code provides more
options of easy ways to retrieve each information symbol than the code in Fig.
1. For example, $x_{1}$ can be downloaded directly from two nodes or can be
decoded from any four symbols in bucket 1 or any four symbols in bucket 2. In
the case that $x_{1}$ is requested simultaneously by many users of the system,
the can ensure that multiple read requests can be satisfied concurrently and
with no delays.

###  I-A Our contribution

We establish an upper bound of the minimum distance of group decodable code
for any given set of parameters $\\{\alpha,\beta,k,t\\}$ (Theorem 4). We also
prove that there exist linear codes of which the minimum distances achieve the
bound, which proves the tightness of the bound (Theorem 5). Our proof gives a
method to construct $(\alpha,\beta,k,t)$-group decodable code on a field of
size $q>{n-1\choose k-1}$, where $n=t\beta$ is the length of the code.

###  I-B Related Work

Some existing works consider erasure codes for distributed storage that can
provide multiple alternatives for repairing information symbols or all code
symbols with locality.

In [7], the authors introduced the metric “local repair tolerance” to measure
the maximum number of erasures that do not compromise local repair. They also
presented a class of locally repairable codes, named pg-BLRC codes, with high
local repair tolerance and low repair locality. However, they did not present
any bound on the minimum distance of such codes.

In [8], the concept of $(\alpha,\delta)_{c}$-locality was defined, which
captures the property that there exist $\delta-1$ pairwise disjoint local
repair sets for a code symbol. An upper bound on the minimum distance for
$[n,k]$ linear codes with information $(\alpha,\delta)_{c}$-locality was
derived, and codes that attain this bound was constructed for the length
$n\geq k(\alpha(\delta-1)+1)$. However, for $n<k(\alpha(\delta-1)+1)$, it is
not known whether there exist codes attaining this bound. Upper bounds on the
rate and minimum distance of codes with all-symbol
$(\alpha,\delta)_{c}$-locality was proved in [9]. However, no explicit
construction of codes that achieve this bound was presented. It is still an
open question whether the distance bound in [9] is achievable.

Another subclass of LRC is codes with $(r,t)$-locality: any set of $t$ code
symbols are functions of at most $r$ other code symbols [11]. Hence, for such
codes, any $t$ failed code symbols can be repaired by contacting at most $r$
other code symbols. An upper bound of the minimum distance of such codes
similar to (1) is derived in [11].

###  I-C Organization

The paper is organized as follows. In Section II, we present the related
concepts and the main results of this paper. We prove the main results in
section III and Section IV.

##  II Model and Main Result

Denote $[n]:=\\{1,\cdots,n\\}$ for any given positive integer $n$. Let
$\mathbb{F}$ be a finite field and $k$ be a positive integer. For any
$S=\\{i_{1},\cdots,i_{\alpha}\\}\subseteq[k]$, the _projection_ of
$\mathbb{F}^{k}$ about $S$ is a function
$\psi_{S}:\mathbb{F}^{k}\rightarrow\mathbb{F}^{\alpha}$ such that for any
$(x_{1},\cdots,x_{k})\in\mathbb{F}^{k}$,

$\displaystyle\psi_{S}(x_{1},\cdots,x_{k})=(x_{i_{1}},\cdots,x_{i_{\alpha}}).$
(2)

We can define group decodable codes (GDC) as follows.

###### Definition 1

Suppose $\mathcal{S}=\\{S_{1},\cdots,S_{t}\\}$ is a collection of subsets of
$[k]$ and $\mathcal{N}=\\{n_{1},\cdots,n_{t}\\}$ is a collection of positive
integers such that $\textstyle\bigcup_{i=1}^{t}S_{i}=[k]$ and
$n_{i}>k_{i}=|S_{i}|,\forall i\in[t]$. A linear code $\mathcal{C}$ is said to
be an $(\mathcal{N},\mathcal{S})$-_group decodable code (GDC)_ if
$\mathcal{C}$ has an encoding function $f$ of the following form:

$\displaystyle f:\mathbb{F}^{k}$ $\displaystyle\rightarrow$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\mathbb{F}^{n_{1}}\times\cdots\times\mathbb{F}^{n_{t}}$
$\displaystyle x~{}~{}$ $\displaystyle\mapsto$
$\displaystyle(f_{1}(\psi_{S_{1}}(x)),\cdots,f_{t}(\psi_{S_{t}}(x))).$ (3)

where each $f_{i}:\mathbb{F}^{k_{i}}\rightarrow\mathbb{F}^{n_{i}}$ is an
encoding function of an $[n_{i},k_{i}]$ MDS code and the output of it is
called a _bucket_.

By Definition 1, if $\mathcal{C}$ is an $(\mathcal{N},\mathcal{S})$-group
decodable code, then $\mathcal{C}$ has length $n=\sum_{i=1}^{t}n_{i}$. For any
message vector $x=(x_{1},\cdots,x_{k})$ and $i\in[t]$, the subset of $k_{i}$
messages $\\{x_{j};j\in S_{i}\\}$ are encoded into a bucket of $n_{i}$ symbols
by the function $f_{i}$. A codeword of $\mathcal{C}$ is the concatenation of
these $t$ buckets. Since $f_{i}$ is an encoding function of an $[n_{i},k_{i}]$
MDS code, each bucket is a repair group and we can decode the subset
$\\{x_{j};j\in S_{i}\\}$ from any $k_{i}$ symbols of the $i$th bucket.—The
term “group decodable code” comes from this observation.

For the special case that $S_{1},\cdots,S_{t}$ are pairwise disjoint, an
$(\mathcal{N},\mathcal{S})$-group decodable code $\mathcal{C}$ is just the
direct sum of the $t$ buckets and the minimum distance of $\mathcal{C}$ is
$\min\\{n_{i}-k_{i}+1;i\in[t]\\}$. In this work, we consider the most general
case that $S_{1},\cdots,S_{t}$ can have arbitrary intersection.

Definition 1 depends on the explicit collections $\mathcal{S}$ and
$\mathcal{N}$. We can also define GDC based on design parameters.

###### Definition 2

Let $\alpha,\beta,k,t$ be positive integers such that
$\alpha<\text{min}\\{k,\beta\\}$. A linear code $\mathcal{C}$ is said to be an
$(\alpha,\beta,k,t)$-_group decodable code_ if $\mathcal{C}$ is an
$(\mathcal{N},\mathcal{S})$-group decodable code for some
$\mathcal{S}=\\{S_{1},\cdots,S_{t}\\}$ and
$\mathcal{N}=\\{n_{1},\cdots,n_{t}\\}$ such that $S_{i}\subseteq[k]$,
$|S_{i}|=\alpha$ and $n_{i}=\beta$ for all $i\in[t]$.

If $\mathcal{C}$ is an $(\alpha,\beta,k,t)$-group decodable code, then by
Definition 2, the length of $\mathcal{C}$ is $n=t\beta$. Moreover, since
$\textstyle\bigcup_{i=1}^{t}S_{i}=[k]$ and $|S_{i}|=\alpha$, then
$t\alpha=\sum_{i=1}^{t}|S_{i}|\geq k$, which implies that
$\left\lfloor\frac{t\alpha}{k}\right\rfloor\geq 1$. So we have the following
remark.

###### Remark 3

If $\mathcal{C}$ is an $(\alpha,\beta,k,t)$-group decodable code, then
$n=t\beta$ and $\left\lfloor\frac{t\alpha}{k}\right\rfloor\geq 1$.

We will give a tight upper bound on the minimum distance $d$ of an
$(\alpha,\beta,k,t)$-group decodable code $\mathcal{C}$. Our main results are
the following two theorems.

###### Theorem 4

Let $t\alpha=sk+r$ such that $s\geq 1$ and $0\leq r\leq k-1$. If $\mathcal{C}$
is an $(\alpha,\beta,k,t)$-group decodable code, then

$\displaystyle d\leq s\beta-\left\lceil\frac{k-r}{{t\choose
s}}\right\rceil+1.$ (4)

Note that an $(\alpha,\beta,k,t)$-group decodable code is an $(r,\delta)_{a}$
with the additional property (P2). So the bound (4) is looser than the bound
(1). The sacrifice in minimum distance is resulted from the property (P2).

###### Theorem 5

If $|\mathbb{F}|>{n-1\choose k-1}$, then there exists an
$(\alpha,\beta,k,t)$-group decodable code over $\mathbb{F}$ with $d$ achieves
the bound (4).

By Remark 3, $t\alpha\geq k$. So we always have $t\alpha=sk+r$ for some $s\geq
1$ and $0\leq r\leq k-1$. So Theorem 4 and 5 covers all possible sets of
parameters $\\{\alpha,\beta,k,t\\}$.

##  III Proof of Theorem 4

In this section, we prove Theorem 4. We will use some similar discussions as
in [16, 17, 18].

In the rest of this paper, we always assume that
$\mathcal{S}=\\{S_{1},\cdots,S_{t}\\}$ is a collection of subsets of $[k]$ and
$\mathcal{N}=\\{n_{1},\cdots,n_{t}\\}$ such that
$\textstyle\bigcup_{i=1}^{t}S_{i}=[k]$ and $n_{i}=\beta>|S_{i}|=\alpha$ for
all $i\in[t]$. Moreover, let $n=t\beta$ and

$\displaystyle J_{i}=\\{(i-1)\beta+1,(i-1)\beta+2,\cdots,i\beta\\}.$ (5)

Clearly, $J_{1},\cdots,J_{t}$ are pairwise disjoint and
$\bigcup_{i=1}^{t}J_{i}=[n]$.

Let $\ell$ be any positive integers and $A$ be any $k\times\ell$ matrix. If
$J\subseteq[\ell]$, we use $A_{J}$ to denote the sub-matrix of $A$ formed by
the columns of $A$ that are indexed by $J$. Moreover, we will use the
following notations:

  * 1)

For $i\in[k]$ and $j\in[\ell]$, $R_{A}(i)$ and $C_{A}(j)$ are the support of
the $i$th row and the $j$th column of $A$ respectively. Meanwhile,
$|R_{A}(i)|$ and $|C_{A}(j)|$ are called the weight of the $i$th row and the
$j$th column of $A$ respectively.

  * 2)

The minimum row weight of $A$ is

$\displaystyle w_{\min}(A)=\min\limits_{i\in[k]}|R_{A}(i)|.$ (6)

The $i$th row is said to be minimal if $|R_{A}(i)|=w_{\min}(A)$.

  * 3)

The repetition number of the $i$th row, denoted by $\Gamma_{A}(i)$, is the
number of $i^{\prime}\in[k]$ such that $R_{A}(i^{\prime})=R_{A}(i)$. Let
$\Phi_{A}$ be the set of indices of all minimal rows of $A$. We denote

$\displaystyle\Gamma(A)=\max\limits_{i\in\Phi_{A}}\Gamma_{A}(i).$ (7)

Clearly, we always have $\Gamma(M)\geq 1$. The following example gives some
explanation of the above notations.

###### Example 6

Consider the following $7\times 8$ binary matrix

$\displaystyle~{}~{}~{}A=\left[\begin{array}[]{cccccccc}1&0&1&0&0&0&1&0\\\
0&1&0&1&0&1&0&0\\\ 0&0&1&0&1&0&1&1\\\ 1&0&0&0&1&1&0&1\\\ 0&1&0&1&0&1&0&0\\\
1&0&1&0&0&0&1&0\\\ 0&1&0&1&1&0&0&1\\\ \end{array}\right].$

We have $R_{A}(1)=R_{A}(6)$. So $\Gamma_{A}(1)=\Gamma_{A}(6)=2$. Similarly,
$\Gamma_{A}(2)=\Gamma_{A}(5)=2$ and the repetition number of all other rows
are $1$. Note that $w_{\text{min}}(A)=3$ and the minimal rows of $A$ are
indexed by $\\{1,2,5,6\\}$. Then $\Gamma(A)=2$.

To prove Theorem 4, we first give a description of
$(\mathcal{N},\mathcal{S})$-group decodable codes using their generator
matrix. To do this, we need the following two definitions.

###### Definition 7

Let $M=(m_{i,j})_{k\times n}$ be a binary matrix and $G=(a_{i,j})_{k\times n}$
be a matrix over $\mathbb{F}$. We say that $G$ is supported by $M$ if for all
$i\in[k]$ and $j\in[n]$, $m_{i,j}=0$ implies $a_{i,j}=0$. If $\mathcal{C}$ is
a linear code over $\mathbb{F}$ and has a generator matrix $G$ supported by
$M$, we call $M$ a _support generator matrix_ of $\mathcal{C}$.

###### Definition 8

Let $M_{0}$ be a $k\times t$ binary matrix and $M$ be a $k\times n$ binary
matrix such that $C_{M_{0}}(j)=S_{j}$ for all $j\in[t]$ and $C_{M}(j)=S_{i}$
for all $i\in[t]$ and $j\in J_{i}$. We call $M_{0}$ the _incidence matrix_ of
$\mathcal{S}$ and $M$ the _indicator matrix_ of $(\mathcal{N},\mathcal{S})$.

###### Remark 9

Since $\textstyle\bigcup_{i=1}^{t}S_{i}=[k]$ and $C_{M_{0}}(i)=S_{i}$ for all
$i\in[t]$, then by Definition 8, each row of $M_{0}$ has at least one $1$ and
each column of $M_{0}$ has exactly $\alpha~{}1$s. Moreover, by (5) and
Definition 8, $M$ is extended from $M_{0}$ by replicating each column of
$M_{0}$ by $\beta$ times. Hence, each row of $M$ has at least $\beta$ $1$s and
each column of $M_{0}$ has exactly $\alpha~{}1$s.

Now, we can describe $(\mathcal{N},\mathcal{S})$-group decodable codes using
their generator matrix.

###### Lemma 10

Let $M$ be the indicator matrix of $(\mathcal{N},\mathcal{S})$. Then
$\mathcal{C}$ is an $(\mathcal{N},\mathcal{S})$-group decodable code if and
only if $\mathcal{C}$ has a generator matrix $G$ satisfying the following two
conditions:

  * (1)

$G$ is supported by $M$;

  * (2)

$\text{rank}(G_{J})=\alpha$ for each $i\in[t]$ and $J\subseteq J_{i}$ with
$|J|=\alpha$.

###### proof 11

This lemma can be directly derived from Definition 1 and 8.

For any $[n,k]$ linear code $\mathcal{C}$, the well-known Singleton bound
([15, Ch1]) states that $d\leq n-k+1$. On the other hand, we always have
$d\geq 1$. So it must be that $d=n-k+1-\delta$ for some
$\delta\in\\{0,1,\cdots,n-k\\}$. The following lemma describes a useful fact
about $d$ for any linear code [20].

###### Lemma 12

Let $\mathcal{C}$ be an $[n,k,d]$ linear code and $G$ be a generator matrix of
$\mathcal{C}$. Let $0\leq\delta\leq n-k$. Then $d\geq n-k+1-\delta$ if and
only if any $k+\delta$ columns of $G$ has rank $k$.

Using this lemma, we can give a bound on the minimum distance of any linear
code by its support generator matrix.

###### Lemma 13

Let $M=(m_{i,j})$ be a $k\times n$ binary matrix and $0\leq\delta\leq n-k$.
The following three conditions are equivalent:

  * (1)

There is an $[n,k]$ linear code $\mathcal{C}$ over some field $\mathbb{F}$
such that $M$ is a support generator matrix of $\mathcal{C}$ and $d\geq
n-k+1-\delta$.

  * (2)

$|\mathop{\textstyle\bigcup}_{j\in J}C_{M}(j)|\geq\ell$ for any $\ell\in[k]$
and any $J\subseteq[n]$ of size $|J|=\ell+\delta$.

  * (3)

$|\mathop{\textstyle\bigcup}_{i\in I}R_{M}(i)|\geq n-k+|I|-\delta$ for all
$\emptyset\neq I\subseteq[k]$.

Moreover, if condition (2) or (3) holds, there exists an $[n,k]$ linear code
over the field of size $q>{n-1\choose k-1}$ with a support generator matrix
$M$ and minimum distance $d\geq n-k+1-\delta$.

###### proof 14

The proof is given in Appendix A.

For $(\mathcal{N},\mathcal{S})$-group decodable code, we have the following
two lemmas.

###### Lemma 15

Suppose $M$ is the indicator matrix of $(\mathcal{N},\mathcal{S})$. If $M$
satisfies condition (2) of Lemma 13, there exists an an
$(\mathcal{N},\mathcal{S})$-group decodable code over the field of size
$q>{n-1\choose k-1}$ with minimum distance $d\geq n-k+1-\delta$.

###### proof 16

The proof is given in Appendix B.

###### Lemma 17

Let $M_{0}=(m_{i,j})$ be the incidence matrix of $\mathcal{S}$. For any
$(\mathcal{N},\mathcal{S})$-group decodable code $\mathcal{C}$, we have

$\displaystyle d\leq w_{\min}(M_{0})\beta-\Gamma(M_{0})+1.$ (9)

Moreover, there exist an $(\mathcal{N},\mathcal{S})$-group decodable code over
the field of size $q>{n-1\choose k-1}$ with
$d=w_{\min}(M_{0})\beta-\Gamma(M_{0})+1$.

###### proof 18

The proof is given in Appendix C.

Now, we can prove Theorem 4.

######  proof 19 (Proof of Theorem 4)

Suppose $\mathcal{C}$ is an $(\alpha,\beta,k,t)$-group decodable code. By
Definition 2, $\mathcal{C}$ is an $(\mathcal{N},\mathcal{S})$-group decodable
code for some $\mathcal{S}=\\{S_{1},\cdots,S_{t}\\}$ and
$\mathcal{N}=\\{n_{1},\cdots,n_{t}\\}$ such that $S_{i}\subseteq[k]$,
$|S_{i}|=\alpha$ and $n_{i}=\beta$ for all $i\in[t]$. Let $M_{0}$ be the
incidence matrix of $\mathcal{S}$. By Lemma 17, it is sufficient to prove
$w_{\min}(M_{0})\beta-\Gamma(M_{0})+1\leq
s\beta-\left\lceil\frac{k-r}{{t\choose s}}\right\rceil+1$.

By Remark 9, each column of $M_{0}$ has exactly $\alpha$ ones. Then the total
number of ones in $M_{0}$ is $N_{\text{one}}=t\alpha$. On the other hand, each
row of $M_{0}$ has at least $w_{\min}(M_{0})$ ones. So
$N_{\text{one}}=t\alpha\geq kw_{\min}(M_{0})$, which implies
$w_{\min}(M_{0})\leq\frac{t\alpha}{k}$. Since $w_{\min}(M_{0})$ is an integer,
then we have

$\displaystyle
w_{\min}(M_{0})\leq\left\lfloor\frac{t\alpha}{k}\right\rfloor=s.$ (10)

Note that $\Gamma(M_{0})\geq 1$. If $k-r\leq{t\choose s}$, then we have
$\left\lceil\frac{k-r}{{t\choose s}}\right\rceil=1$, and (10) implies
$w_{\min}(M_{0})\beta-\Gamma(M_{0})+1\leq
s\beta=s\beta-\left\lceil\frac{k-r}{{t\choose s}}\right\rceil+1$. Thus, we
only need to consider $k-r>{t\choose s}$. Again by (10), we have the following
two cases:

Case 1: $w_{\min}(M_{0})=s$. Let $N_{s}$ be the number of rows of $M_{0}$ with
weight $s$. Then $M_{0}$ has $k-N_{s}$ rows with weight at least $s+1$. So the
total number of ones in $M_{0}$ is $N_{\text{one}}=t\alpha=sk+r\geq
sN_{s}+(s+1)(k-N_{s})=ks+(k-N_{s})$. Thus,

$\displaystyle N_{s}\geq k-r.$ (11)

If $\Gamma(M_{0})<\left\lceil\frac{k-r}{{t\choose s}}\right\rceil$, then the
repetition number of each row of weight $w_{\min}(M_{0})=s$ is at most
$\left\lceil\frac{k-r}{{t\choose s}}\right\rceil-1$. Note that there are at
most ${t\choose s}$ binary vector of length $t$ and weight $s$. Then we have
$N_{s}\leq{t\choose s}\left(\left\lceil\frac{k-r}{{t\choose
s}}\right\rceil-1\right)<k-r$, which contradicts to (11). So we have
$\Gamma(M_{0})\geq\left\lceil\frac{k-r}{{t\choose s}}\right\rceil$. Thus,
$w_{\min}(M_{0})\beta-\Gamma(M_{0})+1\leq
s\beta-\left\lceil\frac{k-r}{{t\choose s}}\right\rceil+1$.

Case 2: $w_{\min}(M_{0})\leq s-1$. Note that $t\alpha=sk+r\geq sk$ and
$\alpha\leq k$. Then we have $t\geq s$ and ${t-1\choose s-1}\geq 1$. Thus,

$\displaystyle k-r$ $\displaystyle\leq k\leq{t-1\choose
s-1}k+\frac{r}{s}{t-1\choose s-1}$ $\displaystyle=\frac{sk+r}{s}{t-1\choose
s-1}=\frac{t\alpha}{s}{t-1\choose s-1}=\alpha{t\choose s}.$

So we have $\frac{k-r}{{t\choose s}}\leq\alpha$, which implies that

$\displaystyle\left\lceil\frac{k-r}{{t\choose
s}}\right\rceil-1<\frac{k-r}{{t\choose s}}\leq\alpha\leq\beta.$

Note that $\Gamma(M_{0})\geq 1$. Then
$w_{\min}(M_{0})\beta-\Gamma(M_{0})+1\leq
w_{\min}(M_{0})\beta\leq(s-1)\beta=s\beta-\beta\leq
s\beta-\left\lceil\frac{k-r}{{t\choose s}}\right\rceil+1$.

By above discussion, we proved $w_{\min}(M_{0})\beta-\Gamma(M_{0})+1\leq
s\beta-\left\lceil\frac{k-r}{{t\choose s}}\right\rceil+1$. By Lemma 17, $d\leq
s\beta-\left\lceil\frac{k-r}{{t\choose s}}\right\rceil+1$.

##  IV Proof of Theorem 5

In this section, we prove Theorem 5. We first give a lemma that will be used
in our following discussion.

###### Lemma 20

Suppose $t\alpha=sk+r$, where $s\geq 1$ and $0\leq r\leq k-1$. If
$k-r\leq{t\choose s}$, then there exists a $k\times t$ binary matrix
$M_{0}=(m_{i,j})$ such that: (i) Each column of $M_{0}$ has exactly
$\alpha~{}1$s; (ii) $w_{min}(M_{0})=s$ and $\Gamma(M_{0})=1$.

###### proof 21

The proof is given in Appendix D.

Now we can prove Theorem 5

######  proof 22 (Proof of Theorem 5)

By Lemma 17, it is sufficient to construct a $k\times t$ binary matrix $M_{0}$
such that each column has exactly $\alpha~{}1$s, $w_{\min}(M_{0})=s$ and
$\Gamma(M_{0})=\left\lceil\frac{k-r}{{t\choose s}}\right\rceil$. We have the
following two cases:

Case 1: $k-r\leq{t\choose s}$. Then $\left\lceil\frac{k-r}{{t\choose
s}}\right\rceil=1$ and $M_{0}$ can be constructed by Lemma 20.

Case 2: $k-r>{t\choose s}$. In this case, we can assume

$\displaystyle k-r=u{t\choose s}+v$ (12)

where $u\geq 1$ and $0\leq v\leq{t\choose s}-1$. Since $t\alpha=sk+r$, then

$\displaystyle t\left[\alpha-u{t-1\choose s-1}\right]$ $\displaystyle=t\alpha-
tu{t-1\choose s-1}$ $\displaystyle=t\alpha-su{t\choose s}$
$\displaystyle=t\alpha-s(k-r-v)$ $\displaystyle=(t\alpha-sk)+s(r+v)$
$\displaystyle=r+s(r+v).$ (13)

Let $M_{1}$ be a $u{t\choose s}\times t$ binary matrix such that each binary
vector of length $t$ and weight $s$ appears in $M_{1}$ exactly $u$ times. Then
each column of $M_{1}$ has exactly $u{t-1\choose s-1}~{}1$s. We can further
construct a $(r+v)\times t$ matrix $M_{2}$ and let
$M_{0}=\left[{}^{M_{1}}_{M_{2}}\right]$. To do so, we need to consider the
following two sub-cases:

Case 2.1: $v=0$. By (22), $t\left[\alpha-u{t-1\choose s-1}\right]=(s+1)r$. It
is easy to construct an $r\times t$ binary matrix $M_{2}$ such that each
column has exactly $\alpha-u{t-1\choose s-1}~{}1$s and each row has exactly
$s+1~{}1$s. Let $M_{0}=\left[{}^{M_{1}}_{M_{2}}\right]$. Then $M_{0}$ is a
$k\times t$ binary matrix and each column has exactly $\alpha~{}1$s. Moreover,
by the construction, we have $w_{min}(M_{0})=s$ and
$\Gamma(M)=u=\left\lceil\frac{k-r}{{t\choose s}}\right\rceil$.

Case 2.2: $v\neq 0$. Then $0\leq r\leq v+r-1$. Note that $0\leq v\leq{t\choose
s}-1$ and by (22), $t\left[\alpha-u{t-1\choose s-1}\right]=s(r+v)+r$. By the
same discussion as in Lemma 20, we can construct a $(r+v)\times t$ binary
matrix $M_{2}$ such that: (i) Each column of $M_{2}$ has exactly
$\alpha-u{t-1\choose s-1}~{}1$s; (ii) $w_{min}(M_{2})=s$ and
$\Gamma(M_{2})=1$. Let $M_{0}=\left[{}^{M_{1}}_{M_{2}}\right]$. Then $M_{0}$
is a $k\times t$ binary matrix and each column has exactly $\alpha~{}1$s.
Moreover, by the construction, we have $w_{min}(M_{0})=s$ and
$\Gamma(M)=u+1=\left\lceil\frac{k-r}{{t\choose s}}\right\rceil$.

Thus, we can always construct a $k\times t$ binary matrix $M_{0}$ such that
each column has exactly $\alpha~{}1$s, $w_{\min}(M_{0})=s$ and
$\Gamma(M_{0})=\left\lceil\frac{k-r}{{t\choose s}}\right\rceil$. By Lemma 17,
there exist $(\mathcal{N},\mathcal{S})$-group decodable code over the field of
size $q>{n-1\choose k-1}$ with
$d=w_{\min}(M_{0})\beta-\Gamma(M_{0})+1=s\beta-\left\lceil\frac{k-r}{{t\choose
s}}\right\rceil+1$.

##  V Conclusions

We introduce a new family of erasure codes, called group decodable codes
(GDC), for distributed storage systems that allows both locally repairable and
group decodable. Thus, such codes can be viewed as a subclass of locally
repairable codes (LRC). We derive an upper bound on the minimum distance of
such codes and prove that the bound is achievable for all possible code
parameters. However, since GDC is a subclass of LRC, the minimum distance
bound of GDC is smaller than the minimum distance bound of LRC in general.

## References

  * [1] H. Weatherspoon and J. Kubiatowicz, “Erasure coding vs. replication: A quantitative comparison,” in _Proc. Workshop on Peer-to-Peer Systems (IPTPS)_ , 2002.
  * [2] A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 9, pp. 4539-4551, Sep. 2010.
  * [3] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the locality of codeword symbols,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 11, pp. 6925-6934, Nov. 2012.
  * [4] N. Prakash, G. M. Kamath, V. Lalitha, and P. V. Kumar, “Optimal linear codes with a local-error-correction property,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , Cambridge, MA, USA, Jul. 2012, pp. 2776-2780.
  * [5] D. S. Papailiopoulos and A. G. Dimakis, “Locally repairable codes,” in _Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on_ , pp. 2771-2775, IEEE, 2012.
  * [6] W. Song, S. H. Dau, C. Yuen, and T. J. Li, “Optimal locally repairable linear codes,” _IEEE J. Sel. Areas Commun._ , vol. 32, no. 5, pp. 1019-1036, May 2014.
  * [7] L. Pamies-Juarez, H. D. L. Hollmann, and F. Oggier, “Locally repairable codes with multiple repair alternatives,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , Istanbul, Turkey, Jul. 2013, pp. 892-896.
  * [8] A. Wang and Z. Zhang, “Repair locality with multiple erasure tolerance,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 11, pp. 6979-6987, Nov. 2014.
  * [9] I. Tamo, A. Barg, “Bounds on locally recoverable codes with multiple recovering sets,” in _Proc. IEEE Int. Symp. Inform. Theory (ISIT)_ , Honolulu, HI, USA, June. 2014, pp. 691-695.
  * [10] I. Tamo, A. Barg, “A family of optimal locally recoverable codes,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 80, pp. 4661-4676, Aug. 2014.
  * [11] A. S. Rawat, A. Mazumdar, and S. Vishwanath, “Cooperative Local Repair in Distributed Storage,” http://arxiv.org/abs/1409.3900, 2015
  * [12] H. S. Dau, W. Song and C. Yuen, “On Block Security of Regenerating Codes at the MBR Point for Distributed Storage Systems,” in _Proc. IEEE Int. Symp. Inform. Theory (ISIT)_ , Honolulu, HI, USA, June. 2014, pp. 1967-1971.
  * [13] J. Pernas, B. Gaston, C. Yuen and J. Pujol, “Non-homogeneous two-rack model for distributed storage systems,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , Istanbul, Turkey, Jul. 2013, pp. 1237-1241.
  * [14] V. T. Van, C. Yuen and J. Li, “Non-homogeneous distributed storage systems,” Allerton 2012, pp. 1133-1140.
  * [15] D. S. Hoang, H. M. Kiah, W. Song and C. Yuen, “Locally Encodable and Decodable Codes for Distributed Storage Systems,” Globecom 2015, also available at http://arxiv.org/abs/1504.04926, 2015.
  * [16] W. Song, X. Wang, C. Yuen, T. J. Li, and R. Feng, “Error Correction for Cooperative Data Exchange,” _IEEE Communications Letters_ , vol. 16, no. 11, pp. 1856-1859, Nov. 2012\.
  * [17] S. H. Dau, W. Song, Z. Dong, and C. Yuen, “Balanced sparsest generator matrices for MDS codes,” in _Proc. IEEE Int. Symp. Inform. Theory (ISIT)_ , Istanbul, Turkey, Jul. 2013, pp. 1889-1893.
  * [18] S. H. Dau, W. Song, C. Yuen, “On the Existence of MDS Codes Over Small Fields With Constrained Generator Matrices,” in _Proc. IEEE Int. Symp. Inform. Theory (ISIT)_ , Honolulu, HI, USA, June. 2014, pp. 1787-1791.
  * [19] T. Ho, M. Medard, R. Kotter, D. R. Karger, M. Effros, J. Shi, and B. Leong, “A Random Linear Network Coding Approach to Multicast,” _IEEE Trans. Inf. Theory_ , vol. 52, no. 10, pp. 4413-4430, Oct 2006.
  * [20] F. J. MacWilliams and N. J. A. Sloane, _The Theory of Error-Correcting Codes_. Amsterdam, The Netherlands: North-Holland, 1977.
  * [21] J.A. Bondy and U.S.R. Murty, _Graph Theory_. Springer, 2007.
  * [22] R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, 1995.

##  Appendix A Proof of Lemma 13

The proof consists of three steps: In the first step, we prove condition (1)
implies condition (2); In the second step, we prove condition (2) implies
condition (3); In the third step, we prove that if condition (3) holds, then
there exists an $[n,k]$ linear code over the field of size $q>{n-1\choose
k-1}$ with a support generator matrix $M$ and minimum distance $d\geq
n-k+1-\delta$.

######  proof 23 (Proof of Lemma 13)

(1) $\Rightarrow$ (2). Suppose condition (1) holds. Let $G=(a_{i,j})$ be a
generator matrix of $\mathcal{C}$ supported by $M$. Then for any $i\in[k]$ and
$j\in[n]$, $m_{i,j}=0$ implies $a_{i,j}=0$. Given any $\ell\in[k]$, since any
$k+\delta$ columns of $G$ has rank $k~{}($Lemma 12$)$, then any $\ell+\delta$
columns of $G$ has rank at least $\ell$, i.e., $\text{rank}(G_{J})\geq\ell$
for any $J\subseteq[n]$ of size $|J|=\ell+\delta$. So $G_{J}$ has at most
$k-\ell$ rows that are all zeros, which implies $|\textstyle\bigcup_{j\in
J}C_{M}(j)|\geq\ell$.

(2) $\Rightarrow$ (3). We can prove this by contradiction. Suppose
$\emptyset\neq I\subseteq[k]$ and $|\mathop{\textstyle\bigcup}_{i\in
I}R_{M}(i)|<n-k+|I|-\delta$. Let
$J^{\prime}=[n]\backslash\mathop{\textstyle\bigcup}_{i\in I}R_{M}(i)$. Then
$|J^{\prime}|>k-|I|+\delta$ and $m_{i,j}=0$ for all $i\in I$ and $j\in
J^{\prime}$. Let $\ell=k-|I|+1$ and $J\subseteq J^{\prime}$ such that
$|J|=\ell$. Then $\mathop{\textstyle\bigcup}_{j\in
J}C_{M}(j)\subseteq[k]\backslash I$. So $|\mathop{\textstyle\bigcup}_{j\in
J}C_{M}(j)|\leq k-|I|=\ell-1$, which contradicts to condition (2). Thus, it
must be that $|\mathop{\textstyle\bigcup}_{i\in I}R_{M}(i)|\geq
n-k+|I|-\delta$.

(3) $\Rightarrow$ (1). The key is to construct a $k\times n$ matrix $G$ over a
field $\mathbb{F}$ of size $q>{n-1\choose k-1}$ such that $G$ is supported by
$M$ and any $k+\delta$ columns of $G$ has rank $k$.

Let $X=(x_{i,j})_{k\times n}$ such that $x_{i,j}$ is an indeterminant if
$m_{i,j}=1$ and $x_{i,j}=0$ if $m_{i,j}=0$. Let
$f(\cdots,x_{i,j},\cdots)=\Pi_{P}\text{det}(P)$, where the product is taken
over all $k$ by $k$ submatrix $P$ of $X$ with
$\text{det}(P)\not\equiv\boldsymbol{O}$. Note that each $x_{i,j}$ belongs to
at most ${n-1\choose k-1}$ submatrix $P$ and has degree at most $1$ in each
$\text{det}(P)$. Then $x_{i,j}$ has degree at most ${n-1\choose k-1}$ in
$f(\cdots,x_{i,j},\cdots)$. Note that
$f(\cdots,x_{i,j},\cdots)=\prod_{P}\text{det}(P)\not\equiv\boldsymbol{O}$. By
[14, Lemma 4], if $|\mathbb{F}|>{n-1\choose k-1}$, then there exist
$a_{i,j}\in\mathbb{F}$ $($for $i,j$ where $m_{i,j}=1)$ such that
$f(\cdots,a_{i,j},\cdots)\neq 0$. Let $G=(a_{i,j})$ $($for $i,j$ where
$m_{i,j}=0$, we set $a_{i,j}=0)$. Then $G$ is supported by $M$. We will prove
$\text{rank}(G_{J})=k$ for any $J\subseteq[n]$ with $|J|=k+\delta$. By
construction of $G$, it is sufficient to prove
$\text{det}(X_{J_{0}})\not\equiv\boldsymbol{O}$ for some $J_{0}\subseteq J$
with $|J_{0}|=k$.

Let $\mathcal{G}_{J}$ be the bipartite graph with vertex set $U\cup V$, where
$U=\\{u_{i};i\in[k]\\}$, $V=\\{v_{j};j\in J\\}$ and $U\cap V=\emptyset$ such
that $(u_{i},v_{j})$ is an edge of $\mathcal{G}_{I}$ if and only if
$m_{i,j}=1$. Then for each $u_{i}\in U$, the set of all neighbors of $u_{i}$
is $N(u_{i})=\\{v_{j};j\in R_{M}(i)\cap J\\}$. So for all $I\subseteq[k]$, the
set of all neighbors of the vertices in $S=\\{u_{i};i\in I\\}$ is
$N(S)=\\{v_{j};j\in(\textstyle\bigcup_{i\in I}R_{M}(i))\cap J\\}$. By
assumption, $\left|\textstyle\bigcup_{i\in I}R_{M}(i)\right|\geq
n-k+|I|-\delta$ and $|J|=k+\delta$. So we have
$|N(S)|=\left|\textstyle\bigcup_{i\in I}R_{M}(i)\cap
J\right|\geq\left|\textstyle\bigcup_{i\in
I}R_{M}(i)\right|-\left|[n]\backslash J\right|=|I|=|S|$. By Hall’s Theorem
$($[16, p. 419]$)$, $\mathcal{G}_{J}$ has a matching which covers every vertex
in $U$. Let
$\mathcal{M}=\\{(u_{1},v_{\ell_{1}}),\cdots,(u_{k},v_{\ell_{k}})\\}$ be such a
matching and $J_{0}=\\{\ell_{1},\cdots,\ell_{k}\\}$. Let $\mathcal{G}_{J_{0}}$
be the subgraph of $\mathcal{G}_{J}$ generated by $U\cup\\{v_{j};j\in
J_{0}\\}$. Then $\mathcal{M}$ is a perfect matching of $\mathcal{G}_{J_{0}}$
and $X_{J_{0}}$ is the Edmonds matrix of $\mathcal{G}_{J_{0}}$. It is well
known $($[17, p. 167]$)$ that a bipartite graph has a perfect matching if and
only if the determinant of its Edmonds matrix is not identically zero. Hence
$\text{det}(X_{J_{0}})\not\equiv\boldsymbol{O}$.

By the construction of $G$, we have $\text{det}(G_{J_{0}})\neq 0$ and
$\text{rank}(G_{J})=k$, where $J$ is any subset of $[n]$ and $|J|=k+\delta$.
Let $\mathcal{C}$ be the $[n,k]$ linear code generated by $G$. By Lemma 12,
$d\geq n-k+1-\delta$. Note that we have proved that $G$ is supported by $M$.
So $M$ is a support generator matrix of $\mathcal{C}$.

##  Appendix B Proof of Lemma 15

######  proof 24 (Proof of Lemma 15)

Let $G$ and $\mathcal{C}$ be constructed as in the proof of Lemma 13. We will
prove that $\mathcal{C}$ is an $(\mathcal{N},\mathcal{S})$-group decodable
code.

By Lemma 10, we need to prove $\text{rank}(G_{J})=\alpha$ for each $i\in[t]$
and each $J\subseteq J_{i}$ of size $|J|=\alpha$. To prove this, it is
sufficient to construct a subset $J_{0}\subseteq[n]$ such that $J\subseteq
J_{0}$ and $\text{rank}(G_{J_{0}})=k$. To simplify notations, without loss of
generality, we can assume $J\subseteq J_{1}$, where $J_{1}$ is defined by (5).
Since $\bigcup_{i=1}^{t}S_{i}=[k]$, we can always find a collection
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ (By proper naming, we can assume
$\mathcal{S}^{\prime}=\\{S_{1},S_{2},\cdots,S_{r}\\}.)$ such that
$\bigcup_{i=1}^{r}S_{i}=[k]$ and
$I_{\ell}=S_{\ell}\backslash\bigcup_{i=1}^{\ell-1}S_{i}\neq\emptyset,\ell=2,\cdots,r$.
Then $\\{I_{1},I_{2},\cdots,I_{r}\\}$ is a partition of $[k]$, where
$I_{1}=S_{1}$. Let $J^{\prime}_{1}=J$ and for each $\ell\in\\{2,\cdots,r\\}$,
pick an $J^{\prime}_{\ell}\subseteq J_{\ell}$ with
$|J^{\prime}_{\ell}|=|I_{\ell}|$. Let $J_{0}=J^{\prime}_{1}\cup
J^{\prime}_{2}\cup\cdots\cup J^{\prime}_{r}$. Then $|J_{0}|=k$. Let
$\mathcal{G}_{J_{0}}$ be the bipartite graph with vertex set $U\cup V$, where
$U=\\{u_{i};i\in[k]\\}$, $V=\\{v_{j};j\in J_{0}\\}$ and $U\cap V=\emptyset$
such that $(u_{i},v_{j})$ is an edge of $\mathcal{G}_{J_{0}}$ if and only if
$m_{i,j}=1$. By Definition 8, $m_{i,j}=1$ for each $i\in I_{\ell}$, $j\in
J^{\prime}_{\ell}$ and $\ell\in[r]$. So each subgraph
$\mathcal{G}_{I_{\ell},J^{\prime}_{\ell}}$ is a complete bipartite graph and
has a perfect matching, where $\mathcal{G}_{I_{\ell},J^{\prime}_{\ell}}$ is
generated by $\\{u_{i};i\in I_{\ell}\\}\cup\\{v_{j};j\in
J^{\prime}_{\ell}\\}$. So the bipartite graph $\mathcal{G}_{J_{0}}$ has a
perfect matching. By a similar discussion as in the proof of Lemma 13,
$\text{rank}(G_{J_{0}})=k$. So $\text{rank}(G_{J})=\alpha$.

Moreover, by the proof of Lemma 13, $G$ is supported by $M$ and is a generator
matrix of $\mathcal{C}$. So by Lemma 10, $\mathcal{C}$ is an
$(\mathcal{N},\mathcal{S})$-group decodable code. By Lemma 13, $d\geq
n-k+1-\delta$. So $\mathcal{C}$ is a code that satisfies our requirements.

As an example, let $M_{0}$ be the matrix $A$ in Example 6. Then $\alpha=3,k=7$
and $t=8$. Let $\beta=5$. Then $M$ is obtained from $M_{0}$ by replicating
each column of $M_{0}$ by $5$ times. By (5),
$J_{1}=\\{1,\cdots,5\\},\cdots,J_{8}=\\{36,\cdots,40\\}$. Let
$J=\\{1,3,5\\}\subseteq J_{1}$. We have $I_{1}=S_{1}=\\{1,4,6\\}$,
$I_{2}=S_{2}\backslash S_{1}=\\{2,5,7\\}$ and $I_{3}=S_{3}\backslash(S_{1}\cup
S_{2})=\\{3\\}$. Moreover, we can pick
$J_{1}^{\prime}=J,J_{2}^{\prime}=\\{6,7,8\\}$ and $J_{3}^{\prime}=\\{11\\}$.
Then $G_{J_{0}}$ is of the following form:

$\displaystyle~{}~{}~{}\left[\begin{array}[]{ccccccc}*&*&*&0&0&0&*\\\
0&0&0&*&*&*&0\\\ 0&0&0&0&0&0&*\\\ &*&*&0&0&0&0\\\ 0&0&0&*&*&*&0\\\
&*&*&0&0&0&*\\\ 0&0&0&*&*&*&0\\\ \end{array}\right]$

where stars denote the nonzero entries of $G_{J_{0}}$. Clearly,
$\\{(1,1),(2,4),(3,6),(4,2),(5,5),(6,7),(7,3)\\}$ is a perfect matching of the
corresponding bipartite graph $\mathcal{G}_{J_{0}}$. By construction of $G$,
we have $\text{det}(G_{J_{0}})\neq 0$ and $\text{rank}(G_{J_{0}})=k=7$.

##  Appendix C Proof of Lemma 17

######  proof 25 (Proof of Lemma 17)

Let $M$ be the indicator matrix of $(\mathcal{N},\mathcal{S})$. By Lemma 10,
$M$ is a support generator matrix of $\mathcal{C}$. Let $\delta_{0}$ be the
smallest number such that $|\mathop{\textstyle\bigcup}_{j\in
J}C_{M}(j)|\geq\ell$ for all $\ell\in[k]$ and all $J\subseteq[n]$ of size
$|J|=\ell+\delta_{0}$. Then by Lemma 13, $d\leq n-k+1-\delta_{0}$. By Lemma 13
and 15, there exists an $(\mathcal{N},\mathcal{S})$-group decodable code over
the field $\mathbb{F}$ of size $q>{n-1\choose k-1}$ with $d=n-k+1-\delta_{0}$.
Thus, to prove this lemma, the key is to prove that
$\delta_{0}=n-w_{\min}(M_{0})\beta-k+\Gamma(M_{0})$.

By Definition 8, $M_{0}$ is a $k\times t$ binary matrix and $M$ is a $k\times
n$ binary matrix such that $C_{M_{0}}(i)=S_{i}$ for all $i\in[t]$ and
$C_{M}(j)=S_{i}$ for all $i\in[t]$ and $j\in J_{i}$. For each $\ell\in[n]$,
let

$\displaystyle\xi_{M}(\ell)=\min\limits_{J\subseteq[n],|J|=\ell}\left|\textstyle\bigcup\limits_{j\in
J}C_{M}(j)\right|.$ (15)

Then by definition of $\delta_{0}$, we have

$\displaystyle\delta_{0}=\min\\{\delta;0\leq\delta\leq
n-k,\xi_{M}(\ell+\delta)\geq\ell,\forall\ell\in[k]\\}.$ (16)

For each $i\in[t]$, let

$\displaystyle\xi_{M_{0}}(i)=\min\limits_{J\subseteq[n],|J|=i}\left|\textstyle\bigcup\limits_{j\in
J}C_{M_{0}}(j)\right|.$ (17)

Then we have the following four claims:
Claim 1:
$\xi_{M_{0}}(i_{0})=k-\Gamma(M_{0})<k=\xi_{M_{0}}(i_{0}+1)=\cdots=\xi_{M_{0}}(t)$,
where $i_{0}=t-w_{\min}(M_{0})$.
Claim 2: For all $i\in[t]$ and $\ell\in J_{i}$,
$\xi_{M}(\ell)=\xi_{M_{0}}(i)$.
Claim 3: $\ell^{\prime}-\xi_{M}(\ell^{\prime})\leq
i_{0}\beta-\xi_{M}(i_{0}\beta),~{}\forall\ell^{\prime}\in[i_{0}\beta]\\}.$
Claim 4: $\delta_{0}=i_{0}\beta-\xi_{M_{0}}(i_{0})$.
Note that $n=t\beta$. Then Claims 1 and 4 imply that
$\delta_{0}=n-w_{\min}(M_{0})\beta-k+\Gamma(M_{0})$, which completes the
proof.

######  proof 26 (Proof of Claim 1)

Suppose $J\subseteq[t]$ and $i_{0}+1\leq|J|\leq t$. Then
$\textstyle\bigcup_{j\in J}C_{M_{0}}(j)=[k]$. Otherwise, there is an
$\ell\in[k]$ such that $\ell\notin C_{M_{0}}(j)$ for all $j\in J$, which
implies that $m_{\ell,j}=0$ for all $j\in J$. So
$R_{M_{0}}(\ell)\subseteq[t]\backslash J$ and
$|R_{M_{0}}(\ell)|\leq|[t]\backslash J|=t-|J|\leq
t-(i_{0}+1)=w_{\min}(M_{0})-1$, which contradicts to (6). Thus, we proved that
$\textstyle\bigcup_{j\in J}C_{M_{0}}(j)=[k]$. By (17), we have
$\xi_{M_{0}}(i)=k$ for $i_{0}+1\leq i\leq t$.

Now, suppose $J\subseteq[t]$ and $|J|=i_{0}=t-w_{\min}(M_{0})$. We have the
following two cases:

Case 1: $J=[t]\backslash R_{M_{0}}(\ell)$ for some $\ell\in[k]$ such that
$|R_{M_{0}}(\ell)|=w_{\text{min}}(M_{0})$. Then $|\bigcup_{j\in
J}R_{M_{0}}(j)|=k-\Gamma_{M_{0}}(\ell)$. This can be proved as follows:

For each $\ell^{\prime}\in[k]$ such that
$R_{M_{0}}(\ell^{\prime})=R_{M_{0}}(\ell)$, we have
$m_{\ell^{\prime},j}=m_{\ell,j}=0$ for all $j\in J$. Thus,
$\ell^{\prime}\notin\bigcup_{j\in J}C_{M_{0}}(j)$.

For each $\ell^{\prime}\in[k]$ such that $R_{M_{0}}(\ell^{\prime})\neq
R_{M_{0}}(\ell)$, since $|R_{M_{0}}(\ell)|=w_{\text{min}}(M_{0})$, then
$R_{M_{0}}(\ell^{\prime})\nsubseteq R_{M_{0}}(\ell)$. Note that
$J=[t]\backslash R_{M_{0}}(\ell)$. Then $R_{M_{0}}(\ell^{\prime})\cap
J\neq\emptyset$ and $m_{\ell^{\prime},j}\neq 0$ for some $j\in J$. So
$\ell^{\prime}\in C_{M_{0}}(j)$ and $\ell^{\prime}\in\bigcup_{j\in
J}C_{M_{0}}(j)$.

Thus, for each $\ell^{\prime}\in[k]$, $\ell^{\prime}\notin\bigcup_{j\in
J}C_{M_{0}}(j)$ if and only if $R_{M_{0}}(\ell)=R_{M_{0}}(\ell)$. So
$|\bigcup_{j\in J}C_{M_{0}}(j)|=k-\Gamma_{M}(\ell)$.

Case 2: $J\neq[t]\backslash R_{M_{0}}(\ell)$ for all $\ell\in[k]$ such that
$|R_{M_{0}}(\ell)|=w_{\min}(M_{0})$. Then $|\bigcup_{j\in J}C_{M_{0}}(j)|=k$.
Otherwise, there is an $\ell^{\prime}\in[k]$ such that $\ell^{\prime}\notin
C_{M_{0}}(j)$ for all $j\in J$, which implies that $m_{\ell^{\prime},j}=0$ for
all $j\in J$, and hence $R_{M_{0}}(\ell^{\prime})\subseteq[t]\backslash J$.
Note that $|J|=t-w_{\text{min}}(M_{0})$. Then
$|R_{M_{0}}(\ell^{\prime})|\leq|[t]\backslash J|=t-|J|=w_{\text{min}}(M_{0})$.
Thus, $|R_{M_{0}}(\ell^{\prime})|=w_{\text{min}}(M)=t-|J|$ and
$J=[t]\backslash R_{M_{0}}(\ell^{\prime})$, which contradicts to assumption on
$J$.

By the above discussion, we proved that for each $J\subseteq[n]$ of size
$|J|=i_{0}$, either $|\bigcup_{j\in J}C_{M_{0}}(j)|=k-\Gamma_{M_{0}}(\ell)$
for some $\ell\in[k]$ with $|R_{M_{0}}(\ell)|=w_{\min}(M_{0})$ or
$|\bigcup_{j\in J}C_{M_{0}}(j)|=k$. Thus, by (17) and (7),
$\xi_{M_{0}}(i_{0})=k-\Gamma(M_{0})$.

######  proof 27 (Proof of Claim 2)

From Definition 8, we have

$\displaystyle\textstyle\bigcup\limits_{j\in
J}C_{M}(j)=\textstyle\bigcup\limits_{i^{\prime}\in[t]:J\cap
J_{i^{\prime}}\neq\emptyset}S_{i^{\prime}},~{}\forall J\subseteq[n].$ (18)

Firstly, we prove $\left|\textstyle\bigcup_{j\in
J}C_{M}(j)\right|\geq\xi_{M_{0}}(i)$ for each $J\subseteq[n]$ of size
$|J|=\ell$.

By (5), we have

$(i-1)\beta+1\leq|J|\leq i\beta.$

Note that by (5), $|J_{i}|=\beta$. Then the number of $i^{\prime}$ such that
$J\cap J_{i^{\prime}}\neq\emptyset$ is at least $i$. By (18) and (17), we have

$\displaystyle\left|\textstyle\bigcup\limits_{j\in J}C_{M}(j)\right|$
$\displaystyle=\left|\textstyle\bigcup\limits_{i^{\prime}\in[t]:J\cap
J_{i^{\prime}}\neq\emptyset}S_{i^{\prime}}\right|$
$\displaystyle=\left|\textstyle\bigcup\limits_{i^{\prime}\in[t]:J\cap
J_{i^{\prime}}\neq\emptyset}C_{M_{0}}(i^{\prime})\right|$
$\displaystyle\geq\xi_{M_{0}}(i).$

The second equation holds because by Definition 8, for each
$i^{\prime}\in[t]$, $C_{M_{0}}(i^{\prime})=S_{i^{\prime}}$. So by (15), we
have $\xi_{M}(\gamma)\geq\xi_{M_{0}}(i)$.

Secondly, we prove there exists a $J\subseteq[n]$ of size $|J|=\ell$ such that
$\left|\textstyle\bigcup_{j\in J}C_{M}(j)\right|=\xi_{M_{0}}(i)$.

By (17), there is a $\\{j_{1},\cdots,j_{i}\\}\subseteq[t]$ such that

$\displaystyle\xi_{M_{0}}(i)=\left|\textstyle\bigcup_{\lambda=1}^{i}C_{M_{0}}(j_{\lambda})\right|=\left|\textstyle\bigcup_{\lambda=1}^{i}S_{j_{\lambda}}\right|.$
(19)

Since $\ell\in J_{i}$, then by (5),
$\left|\textstyle\bigcup_{\lambda=1}^{i-1}J_{j_{\lambda}}\right|=(i-1)\beta<\ell\leq\left|\textstyle\bigcup_{\lambda=1}^{i}J_{j_{\lambda}}\right|=i\beta$.
So we can always find a subset $J\subseteq[n]$ such that
$\textstyle\bigcup_{\lambda=1}^{i-1}J_{j_{\lambda}}\subsetneq
J\subseteq\textstyle\bigcup_{\lambda=1}^{i}J_{j_{\lambda}}$ and $|J|=\ell$.
Then by (18) and (19), we have

$\displaystyle\left|\textstyle\bigcup\limits_{j\in J}C_{M}(j)\right|$
$\displaystyle=\left|\textstyle\bigcup\limits_{i^{\prime}\in[t]:J\cap
J_{i^{\prime}}\neq\emptyset}S_{i^{\prime}}\right|$
$\displaystyle=\left|\textstyle\bigcup_{\lambda=1}^{i}S_{j_{\lambda}}\right|$
$\displaystyle=\xi_{M_{0}}(i).$

Above discussion implies that
$\xi_{M_{0}}(i)=\min\limits_{J\subseteq[n],|J|=\ell}\left|\textstyle\bigcup\limits_{j\in
J}C_{M}(j)\right|$. By (15), we have $\xi_{M}(\ell)=\xi_{M_{0}}(i)$.

######  proof 28 (Proof of Claim 3)

We first prove

$\displaystyle i\beta-\xi_{M}(i\beta)\leq
i_{0}\beta-\xi_{M}(i_{0}\beta),~{}\forall i\in[i_{0}].$ (20)

For each $i\in\\{1,2,\cdots,t-1\\}$, by (17), there exists a
$J^{\prime}\subseteq[t]$ of size $|J^{\prime}|=i$ such that

$\xi_{M_{0}}(i)=\left|\textstyle\bigcup_{j\in J^{\prime}}C_{M_{0}}(j)\right|.$

Pick a $j_{0}\in[t]\backslash J^{\prime}$ and let
$J=J^{\prime}\cup\\{j_{0}\\}$. Then by (17),

$\xi_{M_{0}}(i+1)\leq\left|\textstyle\bigcup_{j\in J}C_{M_{0}}(j)\right|.$

Above two equations imply that

$\displaystyle\xi_{M_{0}}(i+1)-\xi_{M_{0}}(i)$
$\displaystyle\leq\left|\textstyle\bigcup_{j\in
J}C_{M_{0}}(j)\right|-\left|\textstyle\bigcup_{j\in
J^{\prime}}C_{M_{0}}(j)\right|$
$\displaystyle\leq|C_{M_{0}}(j_{0})|=|S_{j_{0}}|=\alpha$
$\displaystyle\leq\beta.$

Combining this with Claim 2, we have

$\displaystyle i\beta-\xi_{M}(i\beta)$ $\displaystyle=i\beta-\xi_{M_{0}}(i)$
$\displaystyle\leq(i+1)\beta-\xi_{M_{0}}((i+1)\beta)$
$\displaystyle=(i+1)\beta-\xi_{M}((i+1)\beta).$

By induction, we have

$\beta-\xi_{M}(\beta)\leq 2\beta-\xi_{M}(2\beta)\leq\cdots\leq
i_{0}\beta-\xi_{M}(i_{0}\beta),$

which proves (20).

Now, we can prove Claim 3. Given $i\in[i_{0}]$ and $\ell^{\prime}\in J_{i}$.
Since by (5), $(i-1)\beta+1\leq\ell^{\prime}\leq i\beta$, and by Claim 2,
$\xi_{M}(\ell^{\prime})=\xi_{M_{0}}(i)=\xi_{M}(i\beta)$, then

$\ell^{\prime}-\xi_{M}(\ell^{\prime})\leq i\beta-\xi_{M}(i\beta).$

Combining this with (20), we have

$\ell^{\prime}-\xi_{M}(\ell^{\prime})\leq i_{0}\beta-\xi_{M}(i_{0}\beta).$

Note that by (5), $[i_{0}\beta]=\\{1,2,\cdots,i_{0}\beta\\}=J_{1}\cup
J_{2}\cup\cdots\cup J_{i_{0}}$. Thus,
$\ell^{\prime}-\xi_{M}(\ell^{\prime})\leq
i_{0}\beta-\xi_{M}(i_{0}\beta),~{}\forall\ell^{\prime}\in[i_{0}\beta]\\}.$

######  proof 29 (Proof of Claim 4)

Denote $\delta^{\prime}_{0}=i_{0}\beta-\xi_{M_{0}}(i_{0})$. We need to prove
$\delta_{0}=\delta_{0}^{\prime}$. Since by Claim 2,
$\xi_{M}(i_{0}\beta)=\xi_{M_{0}}(i_{0})$, then we have
$\delta^{\prime}_{0}=i_{0}\beta-\xi_{M}(i_{0}\beta)$.

Firstly, we prove $\xi_{M}(\ell+\delta_{0}^{\prime})\geq\ell$ for all
$\ell\in[k].$

Suppose $\ell\in[k]$. If $\ell+\delta_{0}^{\prime}\geq i_{0}\beta+1$, then by
(5), $\ell+\delta_{0}^{\prime}\in J_{i}$ for some
$i\in\\{i_{0}+1,\cdots,t\\}$. By Claim 1 and 2,
$\xi_{M}(\ell+\delta_{0}^{\prime})=\xi_{M_{0}}(i)=k\geq\ell,\forall\ell\in[k]$.
If $\ell+\delta_{0}^{\prime}\leq i_{0}\beta$, by Claim 3,
$(\ell+\delta_{0}^{\prime})-\xi_{M}(\ell+\delta_{0}^{\prime})\leq
i_{0}\beta-\xi_{M}(i_{0}\beta)=\delta_{0}^{\prime}$. So
$\xi_{M}(\ell+\delta_{0}^{\prime})\geq\ell$. Thus,
$\xi_{M}(\ell+\delta_{0}^{\prime})\geq\ell$ for all $\ell\in[k].$

Secondly, we prove that if $\delta^{\prime}<\delta_{0}^{\prime}$, then
$\xi_{M}(\ell+\delta_{0}^{\prime})<\ell$ for some $\ell\in[k]$. We can prove
this by contradiction.

Suppose $\xi_{M}(\ell+\delta_{0}^{\prime})\geq\ell$ for all $\ell\in[k]$. We
have the following two cases:

Case 1: $i_{0}\beta-\delta^{\prime}\in[k]$. Note that
$i_{0}\beta-\xi_{M}(i_{0}\beta)=\delta^{\prime}_{0}>\delta^{\prime}$. Then
$\xi_{M}(i_{0}\beta)<i_{0}\beta-\delta^{\prime}$. Let
$\ell=i_{0}\beta-\delta^{\prime}$. Then $\ell\in[k]$ and
$\xi_{M}(\ell+\delta^{\prime})<\ell$, which contradicts to assumption.

Case 2: $i_{0}\beta-\delta^{\prime}\notin[k]$. Since
$i_{0}\beta-\xi_{M}(i_{0}\beta)=\delta^{\prime}_{0}>\delta^{\prime}$, then
$i_{0}\beta-\delta^{\prime}>i_{0}\beta-\delta^{\prime}_{0}=\xi_{M}(i_{0}\beta)>0$.
So we have $i_{0}\beta-\delta^{\prime}>k$ and $i_{0}\beta>k+\delta^{\prime}$.
By (15) and assumption, we have

$\xi_{M}(i_{0}\beta)\geq\xi_{M}(k+\delta^{\prime})\geq k.$

By Claim 2, $\xi_{M}(i_{0}\beta)=\xi_{M_{0}}(i_{0})$. Then above equation
implies $\xi_{M}(i_{0}\beta)=\xi_{M_{0}}(i_{0})\geq k$, which contradicts to
Claim 1.

In both cases, we can derive a contradiction. Thus, we conclude that
$\xi_{M}(\ell+\delta_{0}^{\prime})<\ell$ for some $\ell\in[k]$.

Above discussion shows that $\delta_{0}^{\prime}$ is the smallest number that
satisfies the condition that
$\xi_{M}(\ell+\delta_{0}^{\prime})\geq\ell,~{}\forall\ell\in[k]$.

Thirdly, we prove $\delta_{0}^{\prime}\leq n-k$.

Let $J_{0}$ and $\mathcal{G}_{J_{0}}$ be constructed as in the proof of Lemma
15 $($We can denote $J_{0}=\\{j_{1},j_{2},\cdots,j_{k}\\}.)$. Then
$\mathcal{G}_{J_{0}}$ has a perfect matching. Thus, there exists a permutation
$(i_{1},i_{2},\cdots,i_{k})$ of $(1,2,\cdots,k)$ such that
$m_{i_{\lambda},j_{\lambda}}=1$ for all $\lambda\in[k]$ and we have
$|\textstyle\bigcup_{j\in J^{\prime}}C_{M}(j)|\geq|J^{\prime}|$ for all
$J^{\prime}\subseteq J_{0}$. Now, for any $\ell\in[k]$ and $J\subseteq[n]$ of
size $|J|=\ell+n-k$, since $|J_{0}|=k$, we have $|J\cap J_{0}|\geq\ell$. So
$|\textstyle\bigcup_{j\in J}C_{M}(j)|\geq|\textstyle\bigcup_{j\in J\cap
J_{0}}C_{M}(j)|\geq|J\cap J_{0}|\geq\ell$. By (15), we have
$\xi_{M}(\ell+n-k)\geq\ell$. Thus, we proved that $\delta^{\prime}=n-k$ also
satisfies the condition that
$\xi_{M}(\ell+\delta^{\prime})\geq\ell,~{}\forall\ell\in[k]$.

Note that $\delta_{0}^{\prime}$ is the smallest number that satisfies the
condition that
$\xi_{M}(\ell+\delta_{0}^{\prime})\geq\ell,~{}\forall\ell\in[k]$. So
$\delta_{0}^{\prime}\leq n-k$.

Finally, we prove $\delta_{0}^{\prime}\geq 0$.

By (17), there exists a $J\subseteq[t]$ such that $|J|=i_{0}$ and
$\xi_{M_{0}}(i_{0})=\left|\textstyle\bigcup\limits_{j\in
J}C_{M_{0}}(j)\right|\leq\textstyle\sum\limits_{j\in
J}|C_{M_{0}}(j)|=\textstyle\sum\limits_{j\in J}|S_{j}|=i_{0}\alpha\leq
i_{0}\beta$. So by Claim 2,
$i_{0}\beta-\xi_{M}(i_{0}\beta)=i_{0}\beta-\xi_{M_{0}}(i_{0})\geq 0.$

Thus, we proved that $0\leq\delta_{0}^{\prime}\leq n-k$ and
$\delta_{0}^{\prime}$ is the smallest number that satisfies the condition that
$\xi_{M}(\ell+\delta_{0}^{\prime})\geq\ell,~{}\forall\ell\in[k]$. By (16), we
have $\delta_{0}=\delta_{0}^{\prime}=i_{0}\beta-\xi_{M_{0}}(i_{0})$.

##  Appendix D Proof of Lemma 20

######  proof 30 (Proof of Lemma 20)

Since $k-r\leq{t\choose s}$, we can construct a $k\times t$ binary matrix
$M_{0}=(m_{i,j})$ such that: 1) $R_{M_{0}}(i)$, $i=1,\cdots,k-r$, are mutually
different and $|R_{M_{0}}(i)|=s$; 2) $|R_{M_{0}}(i)|=s+1,i=k-r+1,\cdots,k$.
Since $t\alpha=sk+r$ and $0\leq r\leq k-1$, the total number of $1$s in
$M_{0}$ is

$N_{\text{one}}=(k-r)s+r(s+1)=ks+r=t\alpha.$

Clearly, $M_{0}$ satisfies condition (ii). We can further modify $M_{0}$
properly so that it satisfies conditions (i) and (ii).

Suppose there is a $j_{1}\in[t]$ such that $|C_{M_{0}}(j_{1})|<\alpha$. Since
the total number of ones in $M$ is $N_{\text{one}}=t\alpha$, there exists a
$j_{2}\in[t]$ such that $|C_{M_{0}}(j_{2})|>\alpha$. We shall modify $M_{0}$
so that $|C_{M_{0}}(j_{1})|$ increases by one and $|C_{M_{0}}(j_{2})|$
decreases by one. To do this, let

$I_{1}=\\{i;1\leq i\leq k-r,m_{i,j_{1}}=1\text{~{}and~{}}m_{i,j_{2}}=0\\}$

and

$I_{2}=\\{i;1\leq i\leq k-r,m_{i,j_{1}}=0\text{~{}and~{}}m_{i,j_{2}}=1\\}.$

Then clearly, $I_{1}\cap I_{2}=\emptyset$ and $m_{i,j_{1}}=m_{i,j_{2}}$ for
all $i\in\\{1,\cdots,k-r\\}\backslash(I_{1}\cup I_{2})$. We have the following
two cases:

Case 1: There is an $i\in\\{k-r+1,\cdots,k\\}$ such that
$m_{i,j_{1}}=0,m_{i,j_{2}}=1$ and $|R_{M_{0}}(i)|=s+1$. Then we modify $M$ by
letting $m_{i,j_{1}}=1,m_{i,j_{2}}=0$. Then $|C_{M_{0}}(j_{1})|$ increases by
one and $|C_{M_{0}}(j_{2})|$ decreases by one. Moreover, it is easy to see
that $M_{0}$ still satisfies condition (ii).

Case 2: For all $i\in\\{k-r+1,\cdots,k\\}$, $m_{i,j_{2}}=1$ implies
$m_{i,j_{1}}=1$. Note that $|C_{M_{0}}(j_{1})|<\alpha<|C_{M_{0}}(j_{2})|$,
then we have $|I_{1}|<|I_{2}|$. For each $\ell\in I_{2}$, we modify $M_{0}$ by
letting $m_{\ell,j_{1}}=1$, $m_{\ell,j_{2}}=0$ and the other entries of
$M_{0}$ remain unchanged. Denote the resulted matrix by $M_{\ell}$. Then
$|C_{M_{\ell}}(j_{1})|$ increases by one and $|C_{M_{\ell}}(j_{2})|$ decreases
by one. If there is an $\ell\in I_{2}$ such that $M_{\ell}$ does not satisfy
condition (ii), it must be that
$R_{M_{\ell}}(\ell)=R_{M_{\ell}}(\ell^{\prime})$ for some $\ell^{\prime}\in
I_{1}$. Moreover, all such $\ell$s and $\ell^{\prime}$s are in one to one
correspondence. Note that $|I_{1}|<|I_{2}|$. Then there exists an $i_{0}\in
I_{2}$ such that $M_{i_{0}}$ satisfies condition (ii). So we can let $M_{0}$
be $M_{i_{0}}$.

We can perform the above operation continuously until each column of $M_{0}$
has weight $\alpha$. Thus, we obtain a matrix $M_{0}$ that satisfies
conditions (i) and (ii).


# HD 12098: a highly distorted dipole mode in an obliquely pulsating roAp star

D. W. Kurtz,1,2 H. Saio,3 D. L. Holdsworth,2,4 Santosh Joshi,5 and S. Seetha6
1Centre for Space Research, North-West University, Dr Albert Luthuli Drive,
Mahikeng 2735, South Africa
2Jeremiah Horrocks Institute, University of Central Lancashire, Preston PR1
2HE, UK
3Astronomical Institute, Graduate School of Science, Tohoku University, Sendai
980-8578, Japan
4South African Astronomical Observatory, P.O. Box 9, Observatory 7935, Cape
Town, South Africa
5Aryabhatta Research Institute of Observational Sciences, Nainital 263001,
Uttarakhand, India
6Raman Research Institute, C.V. Raman Avenue, Bengaluru, 560080, India
E-mail<EMAIL_ADDRESS>
###### Abstract

HD 12098 is an roAp star pulsating in the most distorted dipole mode yet
observed in this class of star. Using TESS Sector 58 observations we show that
there are photometric spots at both the magnetic poles of this star. It
pulsates obliquely primarily in a strongly distorted dipole mode with a period
of $P_{\rm puls}=7.85$ min ($\nu_{\rm puls}=183.34905$ d-1; 2.12210 mHz) that
gives rise to an unusual quadruplet in the amplitude spectrum. Our magnetic
pulsation model cannot account for the strong distortion of the pulsation in
one hemisphere, although it is successful in the other hemisphere. There are
high-overtone p modes with frequencies separated by more than the large
separation, a challenging problem in mode selection. The mode frequencies
observed in the TESS data are in the same frequency range as those previously
observed in ground-based Johnson $B$ data, but are not for the same modes.
Hence the star has either changed modes, or observations at different
atmospheric depth detect different modes. There is also a low-overtone p mode
and possibly g modes that are not expected theoretically with the $>1$ kG
magnetic field observed in this star.

###### keywords:

stars: oscillations; stars: individual: (TIC 445543326; HD 12098); stars:
chemically peculiar; Physical Data and Processes: asteroseismology

††pagerange: HD 12098: a highly distorted dipole mode in an obliquely
pulsating roAp star–LABEL:lastpage††pubyear: 2024

##  1 Introduction

Magnetic peculiar A (Ap) stars are found in the main-sequence band from
spectral types early-B to mid-F. They have global magnetic fields that are
roughly dipolar with strengths up 34 kG and with a magnetic axis that is
inclined to the rotation axis, so that the field is observed from varying
aspect with rotation. Atomic diffusion gives rise to surface abundance
anomalies that can reach a million times that of normal stars for some rare
earth elements. Those enhanced abundances are concentrated in surface patches,
usually referred to as spots, that are closely associated with the magnetic
poles, giving rise to rotational variations in the spectral line strengths
(hence abundances) and in brightness. These stars are known as $\alpha^{2}$
CVn stars; they constitute about 10 per cent of all main-sequence stars in
that spectral type range.

A notable characteristic of the $\alpha^{2}$ CVn stars is that the surface
spots are stable over time-scales of at least decades, in strong contrast to
lower main-sequence spotted stars for which those spots can evolve on time-
scales of days. The Sun is the prime example of this. This stability in the Ap
stars means that the rotational light curves can be used to determine the
rotation period to high precision. While the spots are stable, they have a
wide variety of surface configurations, often giving rise to non-sinusoidal
light curves. When the rotational inclination, $i$, and the magnetic
obliquity, $\beta$, of the dipolar field sum to greater than 90∘, both
magnetic poles are seen; also, when there are spots associated with both
poles, the rotational light curve has a double-wave.

The rapidly oscillating Ap (roAp) stars are a subset of the magnetic Ap stars
that show high radial overtone p mode pulsation with periods in the range
$4.7-23.6$ min (see Holdsworth et al., 2024, in press). The spectral types of
the roAp stars range from early A to late F with effective temperatures of
$6500\leq T_{\rm eff}\leq 8800$ K. They partially overlap with the $\delta$
Sct stars in the HR Diagram, but differ from those because of the impact of
the magnetic field on the pulsations. The roAp stars generally pulsate in
nonradial, zonal dipole and quadrupole modes ($l=1,2;m=0$) with the pulsation
axis lying close to the magnetic axis. This gives rise to oblique pulsation
where the pulsation mode is seen from varying aspect as the star rotates. That
provides information on the mode geometry, hence constrains mode
identification, which in many other stars can be problematic. Mode
identification is requisite for the application of asteroseismic modelling.

The oblique pulsator model was introduced by Kurtz (1982) and further
developed and improved by Shibahashi & Saio (1985), Shibahashi & Takata
(1993), Takata & Shibahashi (1994, 1995), Bigot & Dziembowski (2002) and Bigot
& Kurtz (2011), among others. For pulsation modes that can be described by
single spherical harmonics, the pulsation amplitude and phase changes that are
observed over the rotation cycle allow the oblique pulsator model to give
constraints on $i$ and $\beta$, thus on the pulsation geometry, hence
identifying the mode. Two well-studied cases, HR 3831 and HD 99563, pulsate in
slightly distorted dipole modes for which the rotational pulsation amplitude
and phase modulation provide good constraints on the pulsation geometry (Kurtz
et al. 1990, Handler et al. 2006).

Observations show that in other roAp stars the modes are often more strongly
distorted. Saio (2005) made a nonadiabatic analysis of nonradial pulsation
modes in the presence of a dipole field for roAp stars, finding that the
dipole and quadrupole modes distorted by the magnetic field are most likely to
be excited. Several cases of strongly distorted quadrupole modes were studied
by Holdsworth et al. (2018, and references therein) and modelled with the
method of Saio (2005). This was particularly successful in explaining the
flattening of the pulsation phase curve as a function of rotation phase.

However, the models are not fully capable of explaining the distortion of the
pulsation modes, and further complications and challenges to the oblique
pulsator model, as applied to the roAp stars, have arisen. In particular,
Kurtz & Holdsworth (2020) showed that the geometry deduced for the dipole
pulsation mode in the roAp star HD 6532 is dramatically different for
observations made in Johnson $B$ and for those made with the red-dominated
bandpass of the Transiting Exoplanet Survey Satellite (TESS) mission. Since
observations at these different wavelengths probe to different atmospheric
depths because of differences in opacity, this suggests strong changes in
pulsation geometry as a function of depth. In a high-resolution spectroscopic
study of the distorted dipole mode in HR 3831, Kochukhov (2006) first pointed
out that the pulsation geometry inferred using the oblique pulsator model is
dependent on the depth of the observations.

Hence the roAp stars continue to present challenges to our understanding of
their oblique pulsation. This is particularly true for the stars with the most
distorted mode geometries. This has recently become relevant in the context of
the tidally tilted pulsators, where tidally distorted zonal and sectoral
dipole modes have been observed (Jayaraman et al. 2022; Rappaport et al. 2021;
Fuller et al. 2020; Kurtz et al. 2020; Handler et al. 2020). Thus the study of
oblique pulsation of distorted nonradial modes has expanding applications.
Therefore, in this work we present the most distorted dipole mode yet observed
in an roAp star. Extreme examples provide the strongest challenges to theory.

###  1.1 HD 12098

HD 12098 has only one published spectral classification, which is F0 from the
original HD catalogue. However, its Strömgren colours and indices are
characteristic of cool Ap stars; $b-y=0.191$, $m_{1}=0.328$, $c_{1}=0.517$,
H$\beta=2.796$ (Olsen, 1983), from which the indices $\delta m_{1}=-0.122$ and
$\delta c_{1}=-0.255$ can be calculated from the calibration of Crawford
(1979). Based on these indices, in 1999 the star was tested for pulsation
under the Nainital-Cape Survey project (Ashoka et al. 2000, Martinez et al.
2001, Joshi et al. 2006, 2009, 2016) using 10-s integrations through a Johnson
$B$ filter on the 1.04-m Sampurnanand telescope of the Aryabhatta Research
Institute of Observational Sciences (ARIES; at that time called the Uttar
Pradesh State Observatory). Martinez et al. (2000) found it to be an roAp star
with a pulsation frequency of 189.2 d-1 (2.19 mHz; $P=7.6$ min).

Girish et al. (2001) then obtained further data from Mt. Abu Observatory,
India, and found the star to be multiperiodic with a dominant frequency of
187.82 d-1 (2.17 mHz). They also found rotational variation, but could not
discriminate between periods of 1.2 d and 5.5 d. That ambiguity was addressed
by Wade et al. (2001) and then resolved by Ryabchikova et al. (2005) who found
a rotation period of $5.460\pm 0.001$ d from a study of the mean longitudinal
field, which varies almost sinusoidally between $+2000$ G and $-500$ G with
that period. That shows that both magnetic poles are seen over the rotation
cycle.

##  2 HD 12098 data and analysis

HD 12098 was observed at 120-s cadence by the TESS mission in Sector 58 in
late 2022. We have used the PDCSAP (Presearch-Data Conditioning Simple
Aperture Photometry) data to study the rotation and pulsation variations of
this star. The data span 27.72 d and comprise 19475 data points. No outliers
were removed.

###  2.1 The rotation period

Fig. 1 shows the Sector 58 light curve in the top panel showing a clear double
wave. This is consistent with polar spots and the longitudinal magnetic field
curve of Ryabchikova et al. (2005). The second panel shows the first two
harmonics of the rotational light variation in an amplitude spectrum
calculated using the Discrete Fourier Transform algorithm of Kurtz (1985). The
rotation period determined from those harmonics is $5.4815\pm 0.0002$ d, which
is significantly different to that determined from the magnetic variation by
Ryabchikova et al. (2005) of $5.460\pm 0.001$ d.

After fitting 10 harmonics of the rotation frequency, the third panel of Fig.
1 shows significant peaks that may indicate some g modes. One of these is not
fully resolved from the second harmonic of the rotation frequency, hence may
have perturbed the value of the rotation period determined. Panel 4 shows a
5$\sigma$ peak at 11.819 d-1 that is potentially from a low-overtone p mode.
Because of this possible perturbation of the rotation frequency by an
unresolved g mode frequency, we adopt the rotation period (frequency) of
$P_{\rm rot}=5.460$ d ($\nu_{\rm rot}=0.18315$ d-1) of Ryabchikova et al.
(2005) for the pulsation analysis. Pre-whitening by a 10-harmonic series with
this rotation frequency provides a good fit to the data.

Figure 1: Panel 1: The Sector 58 TESS light curve for HD 12098 showing the
double-wave rotational variation typical of the $\alpha^{2}$ CVn stars. Panel
2: A low-frequency amplitude spectrum showing the first two harmonics of the
rotation frequency. Panel 3: A low-frequency amplitude spectrum after pre-
whitening a 10-harmonic fit for the rotation frequency. There are significant
peaks visible that may be from g modes. One of these is not fully resolved
from the second harmonic of the rotation frequency. Panel 4 shows a 5$\sigma$
peak that is potentially from a low-order p mode. Note the changes of ordinate
scale on the panels.

###  2.2 The pulsations

A high-pass filter was used to remove the low-frequency rotational frequency
and its harmonics, the (probable) g mode and p mode frequencies, and
instrumental variations so that the noise in the amplitude spectrum is white.
This gives the best uncertainty estimates for the derived roAp pulsation
frequencies, amplitudes and phases. The top panel of Fig. 2 shows a section of
the amplitude spectrum in the range of the roAp pulsation frequencies where 6
significant peaks can be seen, four of which form a quadruplet split by
exactly the rotation frequency. The middle panel shows the amplitude spectrum
of the residuals after those 6 frequencies were pre-whitened. The bottom panel
shows a higher resolution view of the quadruplet. Table 1 gives the
frequencies derived from a least-squares fits of the quadruplet with a forced
splitting equal to the rotation frequency, and the other two pulsation
frequencies.

Fig. 3 shows the rotational light variations and pulsation amplitude and phase
as a function of rotation phase. The time zero point, $t_{0}={\rm
BJD}\,245\,9893.80$, was chosen to be the time of maximum rotational
brightness. The pulsation amplitude and phase were calculated from the
frequency quadruplet, taking $\nu_{2}=183.34905$ d-1 (2.1221 mHz) to be the
pulsation frequency, and the other three frequencies, $\nu_{1}$, $\nu_{3}$,
and $\nu_{4}$ to be rotational sidelobes generated by oblique pulsation. A
noise-free time series was generated for this frequency quadruplet as given in
Table 1, sampled at the times of the actual observations. The pulsation
amplitudes and phases were then derived by least-squares fitting of the
pulsation mode frequency, $\nu_{2}$, to sections of the generated data
$0.05$-d long, which is just over 9 pulsation cycles. Those were then plotted
as a function of rotation phase. The choice of $\nu_{1}$ or $\nu_{3}$ as the
pulsation frequency generated pulsation phase plots, such as the bottom panel
of Fig. 3, that had strong slopes, indicating that those are not the pulsation
frequency.

###  2.3 Discussion of the pulsation frequencies

Several characteristics of the curves in Fig. 3 are notable. 1) The pulsation
phase changes by $\uppi$ radians at the times when the pulsation amplitude
goes to zero (or nearly so). This is characteristic of an oblique dipole
pulsation when the pulsation node crosses the line of sight. 2) One pulsation
pole dominates for about 30 per cent of the rotation period and the other for
about 70 per cent. This is consistent with the longitudinal magnetic curve of
Ryabchikova et al. (2005), which shows the longitudinal magnetic field to be
negative for about 30 per cent of the rotation and positive for the other 70
per cent. 3) The double-humped pulsation amplitude maximum between rotation
phases $0.3-1.0$ shows that the dipole mode is heavily distorted on this
magnetic hemisphere of the star. The corresponding pulsation phase is also
significantly distorted. 4) The pulsation amplitude and phase variation on the
other magnetic hemisphere does not appear to be distorted. 5) The time of
brightest light in the rotation curve coincides with the time of one pulsation
minimum. This suggests that the star is brightest around the pulsation equator
and dimmest near the poles, as is characteristic of $\alpha^{2}$ CVn
stars.111The rotational photometric maximum and minimum in Ap stars is a
function of the bandpass used for the observations. For some stars the maximum
in a blue bandpass coincides with the minimum in a red bandpass. This is a
consequence of the observations sampling different atmospheric depths and the
line blocking from enhanced abundances changing the temperature gradient.
However, the pulsation mode is so distorted from a simple dipole, that this is
a conjecture. 6) The mode frequency separation $\nu_{6}-\nu_{5}=2.54$ d-1
($29$ $\upmu$Hz) is plausibly half the large separation, suggesting that these
two modes are of alternatively even and odd degree, $\ell$, and that the large
separation is about $\Delta\nu_{0}\sim 60$ $\upmu$Hz. 7) The other mode
frequency separation $\nu_{5}-\nu_{2}=13.350$ d-1 ($155$ $\upmu$Hz) is then
about $2.5\,\Delta\nu_{0}$, so that some intermediary modes are not excited to
observable amplitude. This is seen in some other roAp stars, particularly,
e.g., HD 217522 (Medupe et al., 2015).

The rotational variations in the mean longitudinal magnetic field shown in
Figure 2 of Ryabchikova et al. (2005) shows that pulsation maximum occurs at
the time of positive magnetic extremum. The magnetic ephemeris of Ryabchikova
et al. (2005) cannot be meaningfully extrapolated across the nearly 20-yr time
gap between the magnetic measurements and the TESS photometry to compare the
time of pulsation maximum in the TESS data with then extrema of the magnetic
field. Interestingly, Figure 2 of Ryabchikova et al. (2005) shows that the
mean longitudinal magnetic field of HD 12098 is negative for 30 per cent of
the rotation period and positive for 70 per cent. Those are the same
percentages of the rotation period for which we see the two pulsation
amplitude maxima in Fig. 3. We therefore conclude that the first pulsation
maximum occurs when the negative magnetic hemisphere is observed, and the
second, more complex maximum occurs when the positive magnetic hemisphere is
visible. As with other roAp stars, it is likely that the pulsation amplitude
maxima occur at the times of magnetic extrema, as appears to be the case in
Figure 2 of Ryabchikova et al. (2005) for the Johnson $B$ observations of
Girish et al. (2001) (see the next section). New contemporaneous magnetic and
photometric observations are needed to confirm these reasonable conclusions.

There are no systematic studies of the pulsation amplitude and phase as a
function of rotation phase, as shown in Fig. 3, compared to the rotational
light curves in roAp stars. With TESS data, such a study would be useful.

Figure 2: Panel 1: The roAp pulsation frequencies. Panel 2: same as panel 1
after pre-whitening the 6 pulsation frequencies. Panel 3: a higher resolution
view of the 183.3491 d-1 (2.1221 mHz) rotational multiplet.

Figure 3: Panel 1: The Sector 58 TESS light curve phased; the data have been binned by 10. Panels 2 and 3: The pulsation amplitude and phase as a function of rotation phase. These have been calculated from the frequency quadruplet only, with $\nu_{2}=183.34905$ d-1 as the mode frequency.  Table 1: A linear least-squares fit of the frequencies derived from the Sector 58 data for HD 12098. The zero point for the phases is $t_{0}={\rm BJD}~{}2459893.80$, which matches the time of magnetic maximum predicted from the ephemeris of Ryabchikova et al. (2005). The second frequency of the quadruplet, $\nu_{2}=183.3491$ d-1 ($2.1221$ mHz) is taken to be the mode frequency from a distorted dipole. The other two frequencies are assumed to be from independent pulsation modes, for which there is no sign of rotational sidelobes as expected for oblique pulsation; those, if present, could be lost in the noise. The frequencies $\nu_{1}$ to $\nu_{4}$ are over-specified to 5 decimals so that it can be seen that they are exactly equally split by $0.18315$ d-1 ($P_{\rm rot}=5.460$ d).  | frequency | amplitude | phase
---|---|---|---
| d-1 | mmag | radians
|  | $\pm 0.007$ |
$\nu_{1}$ | $183.16590\pm 0.00141$ | $0.098$ | $0.190\pm 0.070$
$\nu_{2}$ | $183.34905$ | $0.061$ | $2.303\pm 0.114$
$\nu_{3}$ | $183.53220$ | $0.047$ | $-2.056\pm 0.148$
$\nu_{4}$ | $183.71535$ | $0.040$ | $-2.443\pm 0.173$
$\nu_{5}$ | $196.6986\pm 0.0040$ | $0.035$ | $1.470\pm 0.200$
$\nu_{6}$ | $199.2402\pm 0.0025$ | $0.054$ | $-1.832\pm 0.128$

###  2.4 Comparison with ground-based data

Observing through a Johnson $B$ filter, Girish et al. (2001) obtained ground-
based observations and found four pulsation frequencies in the range
$187.7-198.7$ d-1 ($2.17-2.30$ mHz). It is clear from comparison with Fig. 2
that peaks in this frequency range are not present in the TESS Sector 58 data,
although $\nu_{6}=199.2402$ d-1 ($2.3060$ mHz) is close. Similarly, the
frequency quadruplet seen in Fig. 2 in the range $183.166-183.715$ d-1
($2.120-2.126$ mHz) is clearly not present in the Girish et al. (2001) data
(see Fig. 5 in Section 3 below). As some roAp stars are known to have modes
that show amplitude variation on time scales as short as days, and others have
been observed to change modes on longer time scales, this may be the
explanation for the different frequency ranges found in these two studies.

Alternatively, it is known that the pulsation amplitudes and phases in roAp
stars vary strongly both as a function of atmospheric depth and over the
surface as seen in the spectral lines of elements trapped in abundance spots,
usually associated with the magnetic poles (see, e.g., Kurtz et al. (2006) and
Freyhammer et al. (2009) for graphic examples). A theoretical study of
magneto-acoustic modes as a function of atmospheric depth by Quitral-Manosalva
et al. (2018) provides insight into how the acoustic and Alfvén components of
the modes vary throughout the line-forming layers of the observable
atmosphere. It thus seems possible that mode observed by Girish et al. (2001)
in Johnson $B$ may have lower amplitudes, or be undetectable, in the deeper
region observed by TESS with its red bandpass.

Yet unexplained complexity in the roAp pulsation modes and in the application
of the oblique pulsator model to those stars gives rise to uncertainty in the
inference of geometrical information about those modes. Two examples are the
suggested discovery of modes with two different pulsation axes in the roAp
star KIC 10195926 (Kurtz et al., 2011), and the finding that the pulsation
geometry inferred from application of the oblique pulsator model is very
different in ground-based Johnson $B$ data and TESS red data in the roAp star
HD 6532 (Kurtz & Holdsworth, 2020).

The measured photometric amplitudes of pulsation modes in roAp stars vary
significantly depending on the bandpass used to make the observations (Medupe
& Kurtz, 1998) with amplitudes dropping from the blue to the red. This is
simply a consequence of the spectral energy distribution and the photometric
amplitude being primarily the result of temperature variations. Cunha et al.
(2019) compared photometric amplitudes measured through Johnson $B$ and TESS
red bandpass for some roAp stars and found that measurements in Johnson $B$
typically show about 6 times the amplitude of measurements in TESS red.
However, there is also an atmospheric depth effect, since photometric
observations in different bandpasses sample different atmospheric depths, on
average. Given the strong dependence of pulsation amplitude on atmospheric
depth, it is not possible to conclude whether HD 12098 has changed modes
between the time of the ground-based Johnson $B$ observations and the TESS
observations, or whether the detected modes have very different amplitudes
when observed through different bandpasses. Simultaneous observations in
multiple bandpasses, including Johnson $B$, and with TESS are needed to
discriminate between these possibilities.

##  3 Modelling

Table 2: Adopted parameters of HD 12098 Parallax $=6.833\pm 0.022$ mas, $T_{\rm eff}=7600$ K | 1)
---|---
$V=7.97$ mag, $E(B-V)=0.~{}$, $BC=0.~{}$ | 2)
$M_{V}=2.14$ mag, $\log(L/{\rm L}_{\odot})=1.04$, $\log T_{\rm eff}=3.881$ | 3)
1) GAIA DR3: Gaia Collaboration et al. (2023, 2016) |
2) Netopil et al. (2008) |
3) $\log$ means logarithm of base 10. |

In this section we model the pulsational amplitude and phase modulations
against rotational phase of the main p mode pulsation of HD 12098 (middle and
bottom panels of Fig. 3). We obtain these modulations by integrating the
eigenfunction of the p mode on the visible hemisphere at each rotational phase
for an assumed set of angles $\beta$ and $i$; the angle between
rotational/magnetic axes and the inclination angle of the line-of-sight
against the rotation axis, respectively (Saio & Gautschy, 2004; Holdsworth et
al., 2016). We assume the limb-darkening parameter $\mu=0.6$ in this paper.

The pulsational eigenfunctions are calculated by taking into account the
effect of a dipole magnetic field (Saio, 2005) with strength specified by the
field strength $B_{\rm p}$ at the magnetic poles. Non-adiabatic pulsation
variables (assumed to be axisymmetric to the magnetic axis neglecting rotation
effects) are represented as a sum of the terms proportional to the Legendre
function $P_{\ell_{j}}(\cos\theta)$ with $\ell_{j}=\ell_{0}+2j$ where
$j=1,2,\ldots j_{\rm max}$ ($\ell_{0}=0$ for even modes and $\ell_{0}=1$ for
odd modes). We set $j_{\rm max}=12$ in this study.

Although even and odd modes are independent of each other, there is no pure
dipole, or quadrupole mode since the pulsation energy is distributed among
other values of $\ell_{j}$ because of the effects of the magnetic field.
However, for convenience, we call a mode a distorted dipole mode if the
$\ell_{j}=1$ component is dominant, or a distorted quadrupole mode if the
$\ell_{j}=2$ component is dominant.

First, we choose a stellar model for the pulsation analysis. Table 2 lists
observational parameters of HD 12098 adopted from the literature from which we
also calculate the bolometric luminosity. Taking into account these
parameters, we chose a $M=1.75$ M⊙ model having $\log(L/{\rm
L}_{\odot})={1.034}$ and $\log T_{\rm{eff}}({\rm K})={3.875}$ from the
evolutionary models computed with the initial composition $(X,Z)=(0.70,0.02)$
in the fully ionised layers. The evolutionary models, common to our previous
works (e.g. Holdsworth et al., 2016, 2018; Shi et al., 2021), were based on
assumptions similar to the polar model of Balmforth et al. (2001), in which
the helium mass fraction is depleted to 0.01 in the layers above the second He
ionisation zone to the surface, and convection in the envelope is neglected
assuming a strong magnetic field to stabilise the outer layers.

Figure 4: Comparison of observed Fourier amplitude (top), rotational
modulations of the pulsation amplitude (middle) and the phase modulation
(bottom) of HD 12098 with a $1.75$ M⊙ dipole pulsator model at a 2.5 kG
magnetic field.

Fig. 4 compares a dipole pulsation model ($\ell_{0}=1$) with the observed
pulsational amplitude and phase modulations of HD 12098. For this model we
have chosen angles $\beta=30^{\circ}$ and $i=73^{\circ}$ to match the rotation
phase at which sudden changes of the pulsation phases are seen. We have
normalised the model amplitude to approximately fit the (secondary) maximum at
a rotation phase of 0.15. At this phase the rotation axis, the line-of-sight
and the magnetic axis are on a meridional plane with the visible magnetic pole
at the angle $(180^{\circ}-\beta-i)$ from the line of sight. During the range
of rotation phase between 0.0 to 0.3 (when the negative magnetic pole is seen
in the lower part of the visible hemisphere) the amplitude and phase
variations reasonably agree with those observed.

During the rotation phases between 0.3 and 1.0, the positive magnetic pole is
visible. The angle between the visible pole and the line of sight attains
minimum $(i-\beta)$ at the rotation phase 0.65, when the predicted pulsation
amplitude is maximum. However, the predicted amplitude during this range of
rotation phase deviates considerably from the observed one. The observed
amplitude variation is asymmetric with a bump and tends to be lower than the
model prediction. In this range of rotation phase, the other positive magnetic
pole is visible with angles between $(i-\beta)$ and ${\pi\over 2}$ rad from
the line of sight. The cause of the deviation, and in particular the cause of
the broad bump in amplitude, is not clear. The pulsation phase of our model is
constant during this phase interval, while the observed one gradually
decreases, which is probably caused by the effect of rotation (neglected in
this model) as discussed in Bigot & Kurtz (2011).

The deviation of the predicted amplitude variation from the observed one
results in a lack of the fourth frequency component in the Fourier spectrum
shown in the top panel of Fig. 4. Our model always predicts a triplet-
dominated frequency spectrum for an odd-mode oscillation even if it is
significantly affected by contributions from components with $\ell_{j}\geq 3$,
because such contributions are mostly cancelled through the surface
integration as discussed in Saio & Gautschy (2004). For this reason, the
Fourier amplitude at $(\nu-\nu_{2})/\nu_{\rm rot}=2$ detected in the pulsation
of HD 12098 cannot be explained by an axisymmetric odd mode. Some non-
axisymmetric variation is needed for the Fourier component. In this respect,
the bump in the amplitude modulation of HD 12098 might be caused by a non-
axisymmetric (with respect to the magnetic axis) phenomenon and might be
related with the Fourier component at $(\nu-\nu_{2})/\nu_{\rm rot}=2$.

Our model has a p-mode large separation of $5.47~{}$d${}^{-1}($63.3$\,\mu$Hz)
similar to the observational value $\sim$$60$ $\mu$Hz. Fig. 5 compares model
frequencies of distorted dipole and quadrupole p modes at $B_{\rm p}=2.5$ kG
(upper panel) in the frequency range of HD 12098 (lower panel). This figure
indicates that the observed highest frequency $\nu_{6}$ corresponds to the
dipole mode of order 36, while $\nu_{5}$ is the quadrupole mode of order 35.
In addition, it is interesting to note that the frequency $189.2$ d-1 (2.19
mHz) obtained by Martinez et al. (2000) is close to a dipole mode of order 34,
one order higher than the order 33 for $\nu_{2}$, indicating that the most
strongly excited modes seem to shift with time, or that different modes are
detected at different atmospheric depths (see section 2.4 above). We do not
know why the frequencies of highest amplitude found by Girish et al. (2001) do
not match any of our model mode frequencies. We note, however, that these
frequencies are all above the acoustic cut-off frequency, $\approx 135~{}$d-1
($1.56$ mHz), as in a number of other roAp stars (see Figure 12 of Holdsworth
et al. 2018). The excitation mechanism for these high-frequency pulsations in
roAp stars is not known.

Figure 5: Comparison of observed frequencies with dipole and quadrupole modes
of our model at $B_{\rm p}=2.5$ kG. The integer along each frequency of the
dipole $(\ell=1)$ modes indicates the radial order. The blue dashed lines show
the frequencies found by Girish et al. (2001) from ground-based Johnson $B$
data.

Finally, we find that quadrupole modes (even modes ($\ell_{0}=0$) with the
maximum amplitude at $\ell_{j}=2$) affected with similar magnetic fields are
not good for HD 12098. This is because the pulsational phase variations are
significantly suppressed just as in our previous cases presented in, e.g.,
Holdsworth et al. (2018) and Holdsworth et al. (2016).

##  4 conclusions

HD 12098 is an roAp star with a dipolar magnetic field and a rotation period
of $P_{\rm rot}=5.460$ d. Using data from Sector 58 of the TESS mission, we
have shown that there are rotational light variations consistent with spots,
or patches, of enhanced abundances near to each of the magnetic poles. In
these senses, HD 12098 is a typical $\alpha^{2}$ CVn star.

HD 12098 is a known roAp star (Girish et al., 2001) for which the TESS data
give far more insight to the pulsations than previous ground-based data. The
star pulsates with several modes in the range $183-200$ d-1 ($2.12-2.31$ mHz).
While this encompasses the same frequency range found by Girish et al., the
star has either changed modes, or the observations through the Johnson $B$
bandpass and the TESS red bandpass sample different depths with different mode
visibility. To discriminate between these possibilities requires simultaneous
Johnson $B$ and TESS observations.

The interesting new discovery for HD 12098 is that its principal pulsation
mode is a dipole mode that is far more distorted than has been observed in
other roAp stars. Using models that have reasonably explained the mode
distortion in other roAp stars, we are unable to account for the double-humped
pulsation amplitude modulation between rotation phases $0.3-1.0$. This
characteristic has not been observed in any other roAp star. On the dipole
pulsation mode hemisphere seen with best aspect during those $0.3-1.0$
rotation phases, the mode is strongly distorted from a simple dipole.

Interestingly, recently oblique pulsators have been discovered in close binary
stars where dipole pulsations are strongly trapped in one hemisphere, or
another – the tidally tilted pulsators and so-called single-sided pulsators
(Handler et al. 2020, Kurtz et al. 2020, Fuller et al. 2020, Rappaport et al.
2021, Zhang et al. 2023). Whether the clear asymmetry of the pulsation in the
dipole hemispheres of HD 12098 has any relation to this is unknown.

HD 12098 also shows a low-overtone p mode and possibly some g modes. These,
too, are unusual in roAp stars and theoretically unexpected (Saio, 2005) for
this star’s magnetic field strength of over a kG (Ryabchikova et al., 2005).
This star calls for simultaneous multi-colour photometric observations, and it
presents new, challenging behaviour to theory.

## acknowledgements

DLH and DWK acknowledge support from the Fundação para a Ciência e a
Tecnologia (FCT) through national funds (2022.03993.PTDC). This paper includes
data collected by the TESS mission. Funding for TESS is provided by NASA’s
Science Mission Directorate. Resources used in this work were provided by the
NASA High End Computing (HEC) Program through the NASA Advanced Supercomputing
(NAS) Division at Ames Research Center for the production of the SPOC data
products.

## data availability

The TESS data used in this study are available on MAST.

## References

  * Ashoka et al. (2000) Ashoka B. N., et al., 2000, Bulletin of the Astronomical Society of India, 28, 251
  * Balmforth et al. (2001) Balmforth N. J., Cunha M. S., Dolez N., Gough D. O., Vauclair S., 2001, MNRAS, 323, 362
  * Bigot & Dziembowski (2002) Bigot L., Dziembowski W. A., 2002, A&A, 391, 235
  * Bigot & Kurtz (2011) Bigot L., Kurtz D. W., 2011, A&A, 536, A73
  * Crawford (1979) Crawford D. L., 1979, AJ, 84, 1858
  * Cunha et al. (2019) Cunha M. S., et al., 2019, MNRAS, 487, 3523
  * Freyhammer et al. (2009) Freyhammer L. M., Kurtz D. W., Elkin V. G., Mathys G., Savanov I., Zima W., Shibahashi H., Sekiguchi K., 2009, MNRAS, 396, 325
  * Fuller et al. (2020) Fuller J., Kurtz D. W., Handler G., Rappaport S., 2020, MNRAS, 498, 5730
  * Gaia Collaboration et al. (2016) Gaia Collaboration et al., 2016, A&A, 595, A2
  * Gaia Collaboration et al. (2023) Gaia Collaboration et al., 2023, A&A, 674, A1
  * Girish et al. (2001) Girish V., et al., 2001, A&A, 380, 142
  * Handler et al. (2006) Handler G., et al., 2006, MNRAS, 366, 257
  * Handler et al. (2020) Handler G., et al., 2020, Nature Astronomy, 4, 684
  * Holdsworth et al. (2016) Holdsworth D. L., Kurtz D. W., Smalley B., Saio H., Handler G., Murphy S. J., Lehmann H., 2016, MNRAS, 462, 876
  * Holdsworth et al. (2018) Holdsworth D. L., Saio H., Bowman D. M., Kurtz D. W., Sefako R. R., Joyce M., Lambert T., Smalley B., 2018, MNRAS, 476, 601
  * Jayaraman et al. (2022) Jayaraman R., Handler G., Rappaport S. A., Fuller J., Kurtz D. W., Charpinet S., Ricker G. R., 2022, ApJ, 928, L14
  * Joshi et al. (2006) Joshi S., Mary D. L., Martinez P., Kurtz D. W., Girish V., Seetha S., Sagar R., Ashoka B. N., 2006, A&A, 455, 303
  * Kochukhov (2006) Kochukhov O., 2006, A&A, 446, 1051
  * Kurtz (1982) Kurtz D. W., 1982, MNRAS, 200, 807
  * Kurtz (1985) Kurtz D. W., 1985, MNRAS, 213, 773
  * Kurtz & Holdsworth (2020) Kurtz D. W., Holdsworth D. L., 2020, in Monteiro M. J. P. F. G., García R. A., Christensen-Dalsgaard J., McIntosh S. W., eds, Astrophysics and Space Science Proceedings Vol. 57, Dynamics of the Sun and Stars; Honoring the Life and Work of Michael J. Thompson. pp 313–319, doi:10.1007/978-3-030-55336-4_43
  * Kurtz et al. (1990) Kurtz D. W., Shibahashi H., Goode P. R., 1990, MNRAS, 247, 558
  * Kurtz et al. (2006) Kurtz D. W., Elkin V. G., Mathys G., 2006, in Fletcher K., Thompson M., eds, ESA Special Publication Vol. 624, Proceedings of SOHO 18/GONG 2006/HELAS I, Beyond the spherical Sun. p. 33
  * Kurtz et al. (2011) Kurtz D. W., et al., 2011, MNRAS, 414, 2550
  * Kurtz et al. (2020) Kurtz D. W., et al., 2020, MNRAS, 494, 5118
  * Martinez et al. (2000) Martinez P., et al., 2000, Information Bulletin on Variable Stars, 4853, 1
  * Martinez et al. (2001) Martinez P., et al., 2001, A&A, 371, 1048
  * Medupe & Kurtz (1998) Medupe R., Kurtz D. W., 1998, MNRAS, 299, 371
  * Medupe et al. (2015) Medupe R., Kurtz D. W., Elkin V. G., Mguda Z., Mathys G., 2015, MNRAS, 446, 1347
  * Netopil et al. (2008) Netopil M., Paunzen E., Maitzen H. M., North P., Hubrig S., 2008, A&A, 491, 545
  * Olsen (1983) Olsen E. H., 1983, A&AS, 54, 55
  * Quitral-Manosalva et al. (2018) Quitral-Manosalva P., Cunha M. S., Kochukhov O., 2018, MNRAS, 480, 1676
  * Rappaport et al. (2021) Rappaport S. A., et al., 2021, MNRAS, 503, 254
  * Ryabchikova et al. (2005) Ryabchikova T., et al., 2005, A&A, 429, L55
  * Saio (2005) Saio H., 2005, MNRAS, 360, 1022
  * Saio & Gautschy (2004) Saio H., Gautschy A., 2004, MNRAS, 350, 485
  * Shi et al. (2021) Shi F., Kurtz D. W., Holdsworth D. L., Saio H., Cunha M. S., Zhang H., Fu J., Handler G., 2021, MNRAS, 506, 5629
  * Shibahashi & Saio (1985) Shibahashi H., Saio H., 1985, PASJ, 37, 245
  * Shibahashi & Takata (1993) Shibahashi H., Takata M., 1993, PASJ, 45, 617
  * Takata & Shibahashi (1994) Takata M., Shibahashi H., 1994, PASJ, 46, 301
  * Takata & Shibahashi (1995) Takata M., Shibahashi H., 1995, PASJ, 47, 219
  * Wade et al. (2001) Wade G. A., Bagnulo S., Donati J. F., Lueftinger T., Petit P., Sigut T. A. A., 2001, A Peculiar Newsletter 35, 35
  * Zhang et al. (2023) Zhang V., Rappaport S., Jayaraman R., Kurtz D. W., Handler G., Fuller J., Borkovits T., 2023, arXiv e-prints, p. arXiv:2311.16248