# Perfect codes in circulant graphs of degree $p^{l}-1$

Xiaomeng Wang E-mail<EMAIL_ADDRESS>School of Mathematics and
Statistics, Gansu Center for Applied Mathematics, Lanzhou University, Lanzhou,
Gansu 730000, China Oriol Serra E-mail<EMAIL_ADDRESS>Department of
Mathematics, Universitat Politècnica de Catalunya, Barcelona, Spain  Shou-Jun
Xu E-mail<EMAIL_ADDRESS>School of Mathematics and Statistics, Gansu Center
for Applied Mathematics, Lanzhou University, Lanzhou, Gansu 730000, China
Sanming Zhou E-mail<EMAIL_ADDRESS>School of Mathematics and
Statistics, The University of Melbourne, Parkville, VIC 3010, Australia

###### Abstract

A perfect code in a graph is an independent set of the graph such that every
vertex outside the set is adjacent to exactly one vertex in the set. A
circulant graph is a Cayley graph of a cyclic group. In this paper we study
perfect codes in circulant graphs of degree $p^{l}-1$, where $p$ is a prime
and $l\geq 1$. We obtain a necessary and sufficient condition for such a
circulant graph to admit perfect codes, give a construction of all such
circulant graphs which admit perfect codes, and prove a lower bound on the
number of distinct perfect codes in such a circulant graph. This extends known
results for the case $l=1$ and provides insight on the general problem on the
existence and structure of perfect codes in circulant graphs.

Key words: perfect code, efficient dominating set, Cayley graph, circulant
graph, tiling

AMS subject classifications (2020): 05C25, 05C69

##  1 Introduction

All graphs considered in this paper are finite, undirected and simple, and all
groups considered are finite. Let $\Gamma=(V(\Gamma),E(\Gamma))$ be a graph
and $e\geq 1$ an integer. A subset $D$ of $V(\Gamma)$ is called [1, 22] a
_perfect $e$-code_ in $\Gamma$ if every vertex of $\Gamma$ is at distance no
more than $e$ to exactly one vertex in $D$. In what follows a perfect $1$-code
is simply called a _perfect code_. So a subset $D$ of $V(\Gamma)$ is a perfect
code in $\Gamma$ if and only if $D$ is an independent set of $\Gamma$ and
every vertex in $V(\Gamma)\setminus D$ has exactly one neighbour in $D$, which
holds if and only if $\\{\Gamma[x]:x\in D\\}$ is a partition of $V(\Gamma)$,
where $\Gamma[x]$ is the closed neighbourhood of $x$ in $\Gamma$. A perfect
code in a graph is also called an _efficient dominating set_ [6] or
_independent perfect dominating set_ [11]. A graph is distance-transitive [1]
if any pair of vertices can be permuted to any other pair of vertices at the
same distance by an automorphism of the graph. Given a group $G$ and an
inverse-closed subset $S$ of $G$ excluding the identity element, the _Cayley
graph_ $\mathrm{Cay}(G,S)$ of $G$ with _connection set_ $S$ is the group with
vertex set $G$ such that $x,y$ are adjacent if and only if $xy^{-1}\in S$.
Cayley graphs of cyclic groups are widely known as _circulant graphs_.

The study of perfect $e$-codes in graphs began with N. Biggs [1] who among
other things generalized the celebrated Lloyd’s theorem in coding theory to
all distance-transitive graphs. Since the Hamming graph $H(d,q)$ is distance-
transitive, perfect $e$-codes in distance-transitive graphs can be considered
as a generalization of perfect $e$-codes in classical coding theory. On the
other hand, since $H(d,q)$ is the Cayley graph of $\mathbb{Z}_{q}^{d}$ with
respect to the set of elements of $\mathbb{Z}_{q}^{d}$ with exactly one
nonzero coordinate, perfect $e$-codes in Cayley graphs can be viewed as
another generalization of perfect $e$-codes in coding theory. Also, perfect
codes in Cayley graphs are essentially factorizations and tilings of the
underlying group [8, 15, 16]. Because of these connections, perfect codes in
Cayley graphs have attracted considerable attention in recent years. See [7,
Section 1] and [8, Section 1] for short surveys of related results and
background information. See also [3, 9, 19, 20, 21] for recent results on
subgroup perfect codes in Cayley graphs, where a perfect code in a Cayley
graph is a _subgroup perfect code_ if it is a subgroup of the underlying
group.

In this paper we study perfect codes in circulant graphs of degree $p^{l}-1$,
where $p$ is a prime and $l\geq 1$. We obtain a necessary and sufficient
condition for such a circulant graph to admit perfect codes, give a
construction of all such circulant graphs admitting perfect codes, and obtain
a lower bound on the number of distinct perfect codes in such a circulant
graph. The characterization extends to the case $l\geq 1$ the known one for
the case $l=1$ and provides a relatively rich set of perfect codes in
circulant graphs. A particular motivation of this paper is also to provide a
deeper insight on the existence and structure of perfect codes. We note that a
subset $D$ of an abelian group $G$ containing $0$ is a perfect code in
$\mathrm{Cay}(G,S)$ if and only if $(S_{0},D)$ is a tiling of $G$, that is,
every element of $G$ can be expressed in a unique way as $a+b$ with $a\in
S_{0}$ and $b\in D$. So our results in this paper can be stated in terms of
tilings of $\mathbb{Z}_{n}$.

###  1.1 Some history

Before presenting our results, let us give a brief account of known results on
perfect codes in circulant graphs. It was observed in [13, Remark 1] (see also
[7, Lemma 2.3]) that a connected circulant graph ${\rm Cay}(\mathbb{Z}_{n},S)$
of order $n\geq 4$ admits a perfect code if $|S_{0}|$ divides $n$ and
$s\not\equiv s^{\prime}$ (mod $|S_{0}|$) for distinct $s,s^{\prime}\in S_{0}$,
and in this case the unique subgroup of $\mathbb{Z}_{n}$ with order
$n/|S_{0}|$ is a perfect code in ${\rm Cay}(\mathbb{Z}_{n},S)$. This
sufficient condition has been proved to be necessary in the following cases:

  1. (i)

$|S_{0}|=p$ for an odd prime $p$ ([5, Theorem 3.1] and [7, Theorem 1.1]);

  2. (ii)

$|S_{0}|=p^{l}$ with $p$ a prime and $l$ the exponent of $p$ in $n$ ([5,
Theorem 3.4] and [7, Theorem 1.2]);

  3. (iii)

$|S_{0}|=pq$ for some (not necessarily distinct) prime divisors $p,q$ of $n$
with $pq<n$ such that $n/pq$ and $pq$ are coprime and $S_{0}$ is periodic ([5,
Theorem 3.2]);

  4. (iv)

$n\in\\{p^{k},p^{k}q,p^{2}q^{2},pqr,p^{2}qr,pqrs:p,q,r,s\text{ are primes and
}k\geq 1\\}$, $|S_{0}|<n$, and $n/|S_{0}|$ and $|S_{0}|$ are coprime ([5,
Theorem 3.5]);

  5. (v)

$n/|S_{0}|$ is a prime and $S_{0}$ is aperiodic ([4, Theorem 3.2]).

In [13], Obradović, Peters and Ružić gave a necessary and sufficient condition
for the existence of perfect codes in a circulant graph of degree $3$ or $4$,
and showed that under this condition all perfect codes are equally spaced
(that is, they are cosets of some subgroup perfect codes). In a recent paper,
Kwon, Lee and Sohn [10] gave a classification of all perfect codes in any
circulant graph of degree $5$. In [17, Theorem 3.6], Tamizh Chelvam and
Mutharasu proved that a proper subgroup $H$ of $\mathbb{Z}_{n}$ is a perfect
code in some connected Cayley graph of $\mathbb{Z}_{n}$ if and only if either
$|H|$ or $n/|H|$ is odd. A few years later Huang, Xia and Zhou proved that
this result is a special case ([8, Corollary 2.8]) of a general result [8,
Theorem 2.7] in the framework of studying when a given subgroup is a perfect
code in some Cayley graph of the group.

In [14], Kumar and MacGillivray constructed infinitely many examples of
circulant graphs which admit non-equally spaced perfect codes, and they gave a
characterization of circulant graphs which admit perfect codes of size $2$ or
$3$ using the wreath product of a circulant graph and a complete graph. Their
research prompted the following question [14]: Is it true that in any
circulant graph admitting perfect codes either all perfect codes are equally
spaced or the circulant graph is the wreath product of a smaller circulant
graph admitting perfect codes and a complete graph on at least two vertices?
Our work in this paper shows that the answer to this question is negative; a
counterexample will be given in Example 3.1.

In [22], the fourth author studied two families of cyclotomic graphs and
perfect $e$-codes in them; they are Cayley graphs on the additive group of
$\mathbb{Z}[\zeta_{m}]/A$ with respect to $\\{\pm(\zeta_{m}^{i}+A):0\leq i\leq
m-1\\}$ and $\\{\pm(\zeta_{m}^{i}+A):0\leq i\leq\phi(m)-1\\}$, respectively,
where $\zeta_{m}$ ($m\geq 2$) is an $m$th primitive root of unity, $A$ is a
nonzero ideal of $\mathbb{Z}[\zeta_{m}]$, and $\phi$ is Euler’s function. A
family of circulant cyclotomic graphs of degree $2p$, $p$ being an odd prime,
was identified in [22, Section 5] (see also [18, Section 3]) as certain Cayley
graphs associated with finite Frobenius groups. In the special case when
$p=3$, a complete characterization of subgroup perfect $e$-codes in such
circulant cyclotomic graphs was given in [22, Theorem 4.7] in conjunction with
[12, Theorem 24].

###  1.2 Periodic sets

We will only consider Cayley graphs of abelian groups. We will use additive
notation for abelian groups and denote their identity elements by $0$. Thus,
for an abelian group $G$, a subset $S$ of $G\setminus\\{0\\}$ is inverse-
closed if $S=-S$, where $-S=\\{-x:x\in S\\}$, and for this connection set $S$,
$x,y\in G$ are adjacent in $\mathrm{Cay}(G,S)$ if and only if $x-y\in S$.
Write

$S_{0}=S\cup\\{0\\}$

and call it the _extended connection set_ of $\mathrm{Cay}(G,S)$. It is
readily seen that $\mathrm{Cay}(G,S)$ is a regular graph with degree $|S|$,
and $\mathrm{Cay}(G,S)$ is connected if and only if $\langle S\rangle=G$,
where for any subset $X\subseteq G$, $\langle X\rangle$ denotes the subgroup
of $G$ generated by $X$. It can be verified that a subset $D$ of $G$ is a
perfect code in $\mathrm{Cay}(G,S)$ if and only if $D+g$ is a perfect code in
$\mathrm{Cay}(G,S)$ for every $g\in G$. Thus, in studying perfect codes in
Cayley graphs of abelian groups, we may assume without loss of generality that
$0$ is in the perfect code under consideration. Given a subgroup $H$ of $G$,
let $\pi_{H}:G\to G/H,g\mapsto g+H$ denote the canonical projection. Slightly
abusing notation, for $X\subseteq G$ we use $X/H$ to denote the image of $X$
under $\pi_{H}$. Any non-zero element $a\in G$ satisfying $X+a=X$ is called a
_period_ of $X$. The periods of $X$ together with $0$ form a subgroup of $G$,
denoted by $G_{X}$, which is called [16] the _subgroup of periods_ of $X$.
Note that $X$ is the union of some cosets of $G_{X}$ in $G$. If $G_{X}$ is
nontrivial, then $X$ is _periodic_ (or _$G_{X}$ -periodic_ in order to
emphasize the subgroup $G_{X}$); otherwise, $X$ is _aperiodic_.

###  1.3 Main results

As one can see above, even for circulant graphs (which are simplest Cayley
graphs in a sense) we are far from a good understanding of perfect codes in
them. In this paper we focus on existence, construction and enumeration of
perfect codes in connected circulant graphs $\mathrm{Cay}(\mathbb{Z}_{n},S)$
with $|S_{0}|$ a prime power. The following concept is vital for establishing
our main results.

######  Definition 1.1.

Let $G$ be an abelian group. A subset $X$ of $G$ with $0\in X$ is called a
_pyramidal set_ of $G$ if there exists a subgroup series

$H_{0}<H_{1}<\cdots<H_{2t-1}\leq H_{2t}=G$ (1)

of $G$ with $t\geq 1$ such that either (a) or (b) below holds:

  1. (a)

$H_{0}=\\{0\\}$, $X$ is aperiodic, and

    1. (T1)

$(X/H_{2i}-X/H_{2i})\cap(H_{2i+1}/H_{2i})=\\{0\\}$ for $0\leq i\leq t-1$;

    2. (T2)

$X/H_{2i-1}$ is $(H_{2i}/H_{2i-1})$-periodic for $1\leq i\leq t$;

    3. (T3)

$|X/H_{2t-1}|=|G/H_{2t-1}|$ and $|X/H_{2i}|=|X/H_{2i+1}|$ for $0\leq i\leq
t-1$.

  2. (b)

$H_{0}\neq\\{0\\}$, $X$ is $H_{0}$-periodic, and $X/H_{0}$ satisfies (T1),
(T2) and (T3) in $G/H_{0}$ with respect to the subgroup series

$\\{0\\}=H_{0}/H_{0}<H_{1}/H_{0}<\cdots<H_{2t-1}/H_{0}\leq
H_{2t}/H_{0}=G/H_{0}$

of $G/H_{0}$.

In both aperiodic and periodic cases, we call (1) an _admissible subgroup
series_ of $G$ with _length_ $2t$ associated with $X$.

A pyramidal set is not necessarily an extended connection set. For example,
$X=\\{0,1,14,15,16,29,30,31,44\\}$ is a pyramidal set of $\mathbb{Z}_{315}$
with $H_{0}<H_{1}<H_{2}<H_{3}<H_{4}=\mathbb{Z}_{315}$ as an associated
admissible subgroup series, where $H_{0}=\\{0\\}$, $H_{1}=\langle 45\rangle$,
$H_{2}=\langle 15\rangle$, $H_{3}=\langle 3\rangle$ and
$H_{4}=\mathbb{Z}_{315}$, but $X$ does not satisfy $-X=X$.

Condition (T2) above determines a pyramidal structure which gives the name to
the set, as illustrated in Figure 1. Condition (T3) is a rule for determining
the length $2t$ of series (1). It may happen that there are multiple
admissible subgroup series of $G$ associated with the same pyramidal set of
$G$ (see Example 3.1). However, as will be seen in Construction 5.1 and Lemma
5.2, for any pyramidal set $X$ of the cyclic group $\mathbb{Z}_{n}$, there is
a unique longest admissible subgroup series of $\mathbb{Z}_{n}$ associated
with $X$.

012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788890115163159747589012345678910111213141516171819202122232425262728293031323334353637383940414243440153011631142944$G/H_{1}$012345678910111213140114$G/H_{2}$012$G/H_{3}$
Fig. 1: In $G=\mathbb{Z}_{90}$, $S_{0}=\\{0,1,15,16,31,59,74,75,89\\}$ is a
pyramidal set with the longest admissible subgroup series $H_{1}=\langle
45\rangle,H_{2}=\langle 15\rangle,H_{3}=\langle 3\rangle$. For $i=1,2,3$, the
members of $G/H_{i}$ in red colour form $S_{0}/H_{i}$. This diagram looks like
a pyramid, hence the eponym.

Our first main result, stated below, gives a necessary and sufficient
condition for a connected circulant graph of degree $p^{\ell}-1$ to admit
perfect codes. Moreover, it tells us when a perfect code in such a graph with
an aperiodic extended connection set can be a subgroup perfect code.

######  Theorem 1.2.

Let $n\geq 3$ be an integer, and let $\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a
connected non-complete circulant graph with order $n$ and degree $p^{\ell}-1$,
where $p$ is a prime and $\ell\geq 1$ is an integer. Then
$\mathrm{Cay}(\mathbb{Z}_{n},S)$ admits a perfect code if and only if
$p^{\ell}$ divides $n$ and $S_{0}$ is a pyramidal set of $\mathbb{Z}_{n}$.

Moreover, if $p^{\ell}$ divides $n$, $S_{0}$ is pyramidal and aperiodic, and
the longest admissible subgroup series associated with $S_{0}$ has length
$2t$, then the following hold:

  * (a)

if $(S_{0}-S_{0})\cap\langle p^{\ell}\rangle=\\{0\\}$, then the subgroup
$\langle p^{\ell}\rangle$ of $\mathbb{Z}_{n}$ is a perfect code in $\Gamma$
containing $0$; furthermore, when $t=1$ this is the only perfect code in
$\Gamma$ containing $0$, whilst when $t>1$ there are perfect codes in $\Gamma$
containing $0$ which are not subgroups of $\mathbb{Z}_{n}$;

  * (b)

if $(S_{0}-S_{0})\cap\langle p^{\ell}\rangle\neq\\{0\\}$, then there are
perfect codes in $\Gamma$ containing $0$, but none of them is the subgroup
$\langle p^{\ell}\rangle$ of $\mathbb{Z}_{n}$.

As will be seen in Lemma 2.12, if $S_{0}$ is pyramidal and aperiodic, then
every admissible subgroup series $\iota:H_{0}<H_{1}<\cdots<H_{2t-1}\leq
H_{2t}=\mathbb{Z}_{n}$ associated with $S_{0}$ gives rise to two sequences of
positive integers (see (6)), namely
$\mathbf{l}_{\iota}=(\ell_{1},\ell_{2},\ldots,\ell_{t})$ and
$\mathbf{m}_{\iota}=(m_{1},m_{2},\ldots,m_{t})$, such that
$\sum_{i=1}^{t}\ell_{i}=\ell$, $\prod_{i=1}^{t}m_{i}$ divides $m$,
$|H_{2i}/H_{2i-1}|=p^{\ell_{i}}$ and $|H_{2i-1}/H_{2i-2}|=m_{i}$ for $1\leq
i\leq t$, and
$\mathrm{Cay}(\mathbb{Z}_{n}/H_{2t-1},(S_{0}/H_{2t-1})\setminus\\{H_{2t-1}\\})\cong
K_{p^{r}}$, where $r=\ell_{t}$. We will see in Construction 4.3 that $\Gamma$
can be reduced to $K_{p^{r}}$ through a sequence of projections. Conversely,
for any sequences
$\mathbf{l}=(\ell_{1},\ell_{2},\ldots,\ell_{t}),\mathbf{m}=(m_{1},m_{2},\ldots,m_{t})$
of positive integers such that $\sum_{i=1}^{t}\ell_{i}=\ell$ and
$\prod_{i=1}^{t}m_{i}=m$, we will construct a family of connected circulant
graphs with order $n$ and degree $p^{\ell}-1$ through $2t+1$ lifts of
$K_{p^{r}}$ (see Construction 4.6), where $r=\ell_{t}$. Denote this family of
circulant graphs by $\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{\ell})$. Our
second main result, Theorem 1.3 below, asserts that this construction produces
all circulant graphs of degree $p^{\ell}-1$ which admit perfect codes.

######  Theorem 1.3.

Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq 1,m\geq 2$ are integers.
Then a connected circulant graph with order $n$ and degree $p^{\ell}-1$ admits
a perfect code if and only if it is isomorphic to a graph in
$\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{\ell})$ for some sequences
$\mathbf{l}=(\ell_{1},\ell_{2},\ldots,\ell_{t}),\mathbf{m}=(m_{1},m_{2},\ldots,m_{t})$
of positive integers satisfying $\sum_{i=1}^{t}\ell_{i}=\ell$ and
$\prod_{i=1}^{t}m_{i}=m$.

It is natural to ask how many distinct perfect codes containing $0$ a
connected circulant graph satisfying the condition in Theorem 1.2 may have.
Our third main result, Theorem 1.4 below, provides a lower bound on this
number. This bound is given in terms of two sequences of integers obtained
from the longest admissible subgroup series of $\mathbb{Z}_{n}$ associated
with the pyramidal set $S_{0}$, namely $\mathbf{h}(S_{0})$ and
$\mathbf{k}(S_{0})$ (see (9)) to be given in Construction 5.1.

######  Theorem 1.4.

Let $n=p^{\ell}m$, and let $\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a connected
circulant graph with order $n$ and degree $p^{\ell}-1$, where $p$ is a prime
and $\ell\geq 1,m\geq 2$ are integers. Assume that $S_{0}$ is pyramidal with
associated sequences $\mathbf{h}(S_{0})=(h_{0},h_{1},\ldots,h_{t-1},h_{t})$
and $\mathbf{k}(S_{0})=(k_{0},k_{1},\ldots,k_{t-1},k_{t})$. Then the number
$c(S)$ of distinct perfect codes containing $0$ in
$\mathrm{Cay}(\mathbb{Z}_{n},S)$ satisfies

$c(S)\geq p^{\left(\sum_{i=0}^{t-1}(h_{i-1}-h_{i})k_{i}\right)+h_{t-1}-\ell},$

where $h_{-1}=\ell$.

###  1.4 Organisation of the paper

The rest of the paper is organized as follows. As preparations for the proof
of our main results, in the next section we present several known results and
prove two lemmas on admissible subgroup series associated with a pyramidal
set. Theorem 1.2 will be proved in Section 3. In Section 4, we give two
constructions (Constructions 4.3 and 4.6), hence defining the family
$\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{\ell})$, prove several lemmas around
them, and use these lemmas to prove Theorem 1.3. In Section 5, we first
construct a specific admissible subgroup series associated with a pyramidal
extended connection set $S_{0}$ of $\mathbb{Z}_{n}$ (where $n=p^{l}m$) with
$|S_{0}|=p^{l}$ together with the integer sequences $\mathbf{h}(S_{0})$ and
$\mathbf{k}(S_{0})$ (Construction 5.1), and then prove that this series is the
unique longest admissible subgroup series of $\mathbb{Z}_{n}$ associated with
$S_{0}$ (Lemma 5.2). Based on these we give a method for constructing various
perfect codes in $\mathrm{Cay}(\mathbb{Z}_{n},S)$ containing $0$ (Construction
5.3) and use this construction to prove Theorem 1.4. The paper concludes with
some final comments and remarks in Section 6.

##  2 Preliminaries

In our proof of Theorem 1.2 we will use the following result.

######  Theorem 2.1.

([4, Theorem 3.1]) Let $n\geq 3$ be an integer, and let $S$ be a connection
set of $\mathbb{Z}_{n}$ such that $|S_{0}|$ divides $n$. Then
$\mathrm{Cay}(\mathbb{Z}_{n},S)$ admits a perfect code $H$ which is a subgroup
of $\mathbb{Z}_{n}$ if and only if $(S_{0}-S_{0})\cap H=\\{0\\}$. Moreover,
under this condition $H$ must be the subgroup $\langle|S_{0}|\rangle$ of
$\mathbb{Z}_{n}$ generated by $|S_{0}|$.

In our proof of Theorems 1.2 and 1.3 we will use the following result.

######  Theorem 2.2.

([5, Theorem 3.1] and [7, Theorem 1.1]) Let $n\geq 3$ be an integer, and let
$\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a connected non-complete circulant graph
with order $n$ and degree $|S|=p-1$, where $p$ is a prime. Then
$\mathrm{Cay}(\mathbb{Z}_{n},S)$ admits a perfect code if and only if $p$
divides $n$ and $(S_{0}-S_{0})\cap H=\\{0\\}$, where $H=\langle p\rangle$ is
the subgroup of $\mathbb{Z}_{n}$ generated by $|S_{0}|$.

Let $G$ be an abelian group. For two subsets $A,B$ of $G$, their sumset is
defined as $A+B=\\{a+b:a\in A\text{ and }b\in B\\}$. Set $-B=\\{-b:b\in B\\}$
and $A-B=A+(-B)$. If the elements in $A+B$ are pairwise distinct, then $A+B$
is a _direct sum_ and we write $A\oplus B$ to indicate this. If $A\oplus B=G$,
then we say that $G=A\oplus B$ is a _factorization_ of $G$ into $A$ and $B$;
if in addition $0\in A\cap B$, then $(A,B)$ is called a _tiling_ of $G$. It
can be verified (see, for example, [4]) that a subset $D$ of $G$ is a perfect
code in a Cayley graph $\mathrm{Cay}(G,S)$ of $G$ if and only if
$G=S_{0}\oplus D$. For a subgroup $H$ of $G$, a _transversal_ of $H$ in $G$ is
a subset $X$ of $G$ which contains precisely one element from each coset of
$H$ in $G$. It can be verified that $H$ is a perfect code in
$\mathrm{Cay}(G,S)$ if $S_{0}$ is a transversal of $H$ in $G$.

######  Lemma 2.3.

[16, Lemma 2.2] Let $G$ be an abelian group, and let $A$ and $B$ be non-empty
subsets of $G$. The following statements are all equivalent:

  * (a)

$G=A\oplus B$;

  * (b)

$G=A+B$ and $|G|=|A||B|$;

  * (c)

$|G|=|A||B|$ and $(A-A)\cap(B-B)\subseteq\\{0\\}$;

  * (d)

$G=A+B$ and $(A-A)\cap(B-B)\subseteq\\{0\\}$.

######  Lemma 2.4.

[4, Lemma 2.4] Let $A$ and $B$ be subsets of an abelian group $G$. Assume that
$A$ is periodic with subgroup of periods $H$. Then $G=A\oplus B$ if and only
if $G/H=(A/H)\oplus(B/H)$ and $(B-B)\cap H=\\{0\\}$.

######  Lemma 2.5.

[16, Theorem 3.19] If an abelian group $G$ can be factorized as $G=H\oplus
K=A\oplus B$, where $H,K$ are subgroups of $G$ with relatively prime orders
and $A,B$ are subsets of $G$ with $|A|=|H|$ and $|B|=|K|$, then $G=H\oplus
B=A\oplus K$.

######  Lemma 2.6.

Let $H$ be a subgroup of $\mathbb{Z}_{n}$, and let $A$ and $B$ be non-empty
subsets of $\mathbb{Z}_{n}$ with $|A/H|=|A|$. If
$\mathbb{Z}_{n}/H=(A/H)\oplus(B/H)$, then $\mathbb{Z}_{n}=A\oplus(B+H)$.

###### Proof.

Since $\mathbb{Z}_{n}/H=(A/H)\oplus(B/H)$ and $|A/H|=|A|$, we have
$n/|H|=|\mathbb{Z}_{n}/H|=|A/H||B/H|=|A||B/H|$. Since $H$ is a subgroup of
$\mathbb{Z}_{n}$, it is of the form $H=\langle y\rangle$ for some integer $y$
between $1$ and $n-1$. Define $D=\\{d<y:d+H\in B/H\\}$. Since
$\\{0,1,\ldots,y-1\\}$ is a transversal of $H$ in $\mathbb{Z}_{n}$, we have
$|D|=|B/H|$.

Define $\phi:D+H\rightarrow B+H$ such that $\phi((d,h))=d+h$ for $d\in D$ and
$h\in H$. If $\phi((d_{1},h_{1}))=\phi((d_{2},h_{2}))$ for
$(d_{1},h_{1}),(d_{2},h_{2})\in D+H$, then $d_{1}+h_{1}=d_{2}+h_{2}$, which
implies $d_{1}=d_{2}$ and so $h_{1}=h_{2}$ as $0\leq d_{1},d_{2}<y$. Hence
$\phi$ is injective. Also, for any $x\in B+H$, there exists an integer $z$
with $0\leq z<y$ such that $x=z+h=\phi((z,h))$. So $\phi$ is surjective as
well. Therefore, $\phi$ is a bijection and hence $|D||H|=|B+H|$. Thus,
$n=|A||B/H||H|=|A||D||H|=|A||B+H|$. Since $\mathbb{Z}_{n}/H=(A/H)\oplus(B/H)$,
we then have $\mathbb{Z}_{n}=A+(B+H)$. This together with Lemma 2.3 yields
$\mathbb{Z}_{n}=A\oplus(B+H)$. $\Box$

If $G$ is a cyclic group and $G=A\oplus B$ is a factorization of $G$ with
${\rm gcd}(|A|,|B|)=1$, then the conclusion in Lemma 2.5 follows automatically
because in this case there is a unique pair of subgroups $H,K$ of $G$ with
$|H|=|A|$ and $|K|=|B|$. For cyclic groups, we have the following more
specific result.

######  Lemma 2.7.

[16, Theorem 4.4] Let $G$ be a cyclic group and $G=A\oplus B$ a factorization
of $G$. If $|A|=p^{l}$ with $p$ a prime, then either $A$ or $B$ is periodic.

Let $\Gamma$ and $\Sigma$ be graphs. The wreath product of $\Gamma$ and
$\Sigma$ is the graph $\Gamma\otimes\Sigma$ with vertex set $V(\Gamma)\times
V(\Sigma)$ such that $(u,v),(x,y)$ are adjacent if and only if either $u,x$
are adjacent in $\Gamma$ or $u=x$ and $v,y$ are adjacent in $\Sigma$.

######  Lemma 2.8.

[14, Proposition 3.2] Let $\Gamma$ be a graph without isolated vertices and
$\Sigma$ a graph with at least one vertex. Then $\Gamma\otimes\Sigma$ admits a
perfect code if and only if $\Gamma$ admits a perfect code and $\Sigma$ is a
complete graph.

######  Lemma 2.9.

Let $\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a circulant graph such that $S_{0}$ is
periodic with subgroup of periods $H$. Then

$\mathrm{Cay}(\mathbb{Z}_{n},S)\cong\mathrm{Cay}(\pi_{H}(\mathbb{Z}_{n}),\pi_{H}(S)\setminus\\{H\\})\otimes\mathrm{Cay}(H,H\setminus\\{0\\}).$
(2)

###### Proof.

Let $X$ be a transversal of $H$ in $G$. Then the map $f:G\to(G/H)\times H$
defined by $f(g)=(\pi_{H}(x),h)$, where $x\in X$ and $h\in H$ are the unique
pair of elements of $G$ such that $g=x+h$, is a graph isomorphism from the
left-hand side to the right-hand side of (2). $\Box$

Note that $\mathrm{Cay}(H,H\setminus\\{0\\})$ is the complete graph on $H$.
The following lemma says that the converse of the statement in Lemma 2.9 is
also true.

######  Lemma 2.10.

[2, Theorem 28] A circulant graph $\mathrm{Cay}(\mathbb{Z}_{mn},S)$ with order
$mn$ is isomorphic to the wreath product of a circulant graph with order $n$
and the complete graph $K_{m}$ if and only if $S_{0}$ is $\langle
n\rangle$-periodic.

It follows from Lemmas 2.8 and 2.9 that, if $S_{0}$ is $H$-periodic, then
every perfect code $C$ in $\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ can be
obtained from a perfect code $D=\\{d_{1},\ldots,d_{t}\\}$ in
$\Sigma=\mathrm{Cay}(\pi_{H}(\mathbb{Z}_{n}),\pi_{H}(S)\setminus\\{H\\})$ and
a collection of (not necessarily distinct) elements $h_{1},\ldots,h_{t}\in H$
in such a way that $C=\\{(d_{1},h_{1}),\ldots,(d_{t},h_{t})\\}$, and vice
versa. Thus we can obtain $|H|^{t-1}$ distinct perfect codes containing $0$ in
$\Gamma$ from a given perfect code $D$ in $\Sigma$. Moreover, for distinct
perfect codes $D=\\{d_{1},\ldots,d_{t}\\}$ and
$D^{\prime}=\\{d^{\prime}_{1},\ldots,d^{\prime}_{t}\\}$ in $\Gamma$, we have
$d^{\prime}_{i}\notin D$ for some $1\leq i\leq t$ and hence
$\\{(d_{1},h_{1}),\ldots,(d_{t},h_{t})\\}\neq\\{(d^{\prime}_{1},h^{\prime}_{1}),\ldots,(d^{\prime}_{t},h^{\prime}_{t})\\}$
for any $h_{1},\ldots,h_{t}\in H$ and $h^{\prime}_{1},\ldots,h^{\prime}_{t}\in
H$. Therefore, if there are exactly $c(\Sigma)$ distinct perfect codes
containing $0$ in $\Sigma$, then there are exactly $c(\Sigma)\cdot|H|^{t-1}$
distinct perfect codes containing $0$ in $\Gamma$. Moreover, $\pi_{H}(S_{0})$
is aperiodic as $H$ is the subgroup of periods of $S_{0}$.

######  Lemma 2.11.

Let $G$ be an abelian group. Let $X$ be a pyramidal set of $G$ with

$\iota:H_{0}<H_{1}<\cdots<H_{2t-1}\leq H_{2t}=\mathbb{Z}_{n}$

as an associated admissible subgroup series. Then the following statements
hold:

  1. (a)

if $H_{0}=\\{0\\}$ and $X$ is aperiodic, then for each $0\leq i\leq t-1$,
$X/H_{2i}$ is a pyramidal set of $G/H_{2i}$ with

$\iota^{\prime}:H_{2i}/H_{2i}<H_{2i+1}/H_{2i}<\cdots<H_{2t-1}/H_{2i}\leq
H_{2t}/H_{2i}=\mathbb{Z}_{n}/H_{2i}$ (3)

as an associated admissible subgroup series;

  2. (b)

if $H_{0}\neq\\{0\\}$ and $X$ is $H_{0}$-periodic, then for each $0\leq i\leq
t-2$, $X/H_{2i+1}$ is a pyramidal set of $G/H_{2i+1}$ with

$\iota^{\prime\prime}:H_{2i+2}/H_{2i+1}<H_{2i+3}/H_{2i+1}<\cdots<H_{2t-1}/H_{2i+1}\leq
H_{2t}/H_{2i+1}=\mathbb{Z}_{n}/H_{2i+1}$ (4)

as an associated admissible subgroup series.

###### Proof.

Since $X$ is a pyramidal set of $G$, we have $0\in X$.

(a) Since $H_{0}=\\{0\\}$ and $X$ is an aperiodic pyramidal set of $G$ with
$\iota$ as an associated admissible subgroup series, by (T2), for $0\leq i\leq
t-1$, $X/H_{2i-1}$ is $(H_{2i}/H_{2i-1})$-periodic and so $X/H_{2i}$ is
aperiodic. By (T1), we have
$\left((X/H_{2i})/(H_{2j}/H_{2i})-(X/H_{2i})/(H_{2j}/H_{2i})\right)\cap\left((H_{2j+1}/H_{2i})/(H_{2j}/H_{2i})\right)=(X/H_{2j}-X/H_{2j})\cap(H_{2j+1}/H_{2j})=\\{0\\}$
for $i\leq j\leq t-1$. By (T2), for $i+1\leq j\leq t$,
$(X/H_{2i})/(H_{2j-1}/H_{2i})=X/H_{2j-1}$ is $(H_{2j}/H_{2j-1})$-periodic, so
$(X/H_{2i})/(H_{2j-1}/H_{2i})$ is
$((H_{2j}/H_{2i})/(H_{2j-1}/H_{2i}))$-periodic. Moreover, for $i+1\leq j\leq
t-1$, we have $|(X/H_{2i})/(H_{2j}/H_{2i})|$
$=|X/H_{2j}|=|X/H_{2j+1}|=|(X/H_{2i})/(H_{2j+1}/H_{2i})|$ and
$|(X/H_{2i})/(H_{2t-1}/H_{2i})|=|X/H_{2t-1}|=|G/H_{2t-1}|=|(G/H_{2i})/(H_{2t-1}/H_{2i})|$.
Thus $\iota^{\prime}$ satisfies (T1)–(T3) and so for any $0\leq i\leq t-1$,
$X/H_{2i}$ is a pyramidal set of $G/H_{2i}$ with $\iota^{\prime}$ as an
associated admissible subgroup series.

(b) Since $H_{0}\neq\\{0\\}$ and $X$ is an $H_{0}$-periodic pyramidal set of
$G$ with $\iota$ as an associated admissible subgroup series, by (T2), for
$0\leq i\leq t-2$, $X/H_{2i+1}$ is $(H_{2i+2}/H_{2i+1})$-periodic and
$H_{2i+2}/H_{2i+1}\neq\\{0\\}$. Note that
$(H_{k}/H_{2i+1})/(H_{2i+2}/H_{2i+1})=H_{k}/H_{2i+2}$ for $2i+1\leq k\leq 2t$.
Similarly to part (a), using the definition of a pyramidal set, we can show
that $X/H_{2i+1}$ is a pyramidal set of $G/H_{2i+1}$ with
$\iota^{\prime\prime}$ as an associated admissible subgroup series. $\Box$

######  Lemma 2.12.

Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq 1,m\geq 2$ are integers.
Let $\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a connected circulant graph with order
$n$ and degree $p^{\ell}-1$ such that $S_{0}$ is pyramidal. Then every
admissible subgroup series

$\iota:H_{0}<H_{1}<\cdots<H_{2t-1}\leq H_{2t}=\mathbb{Z}_{n}$ (5)

of $\mathbb{Z}_{n}$ associated with $S_{0}$ (where $t\geq 1$) determines two
sequences of positive integers

$\mathbf{l}_{\iota}=(\ell_{1},\ell_{2},\ldots,\ell_{t}),\;\mathbf{m}_{\iota}=(m_{1},m_{2},\ldots,m_{t})$
(6)

with the following properties:

  1. (a)

$\prod_{i=1}^{t}m_{i}$ divides $m$;

  2. (b)

$\sum_{i=1}^{t}\ell_{i}=\ell$ if $S_{0}$ is aperiodic, and
$\sum_{i=1}^{t}\ell_{i}<\ell$ if $S_{0}$ is periodic;

  3. (c)

for $1\leq i\leq t$, we have

$|H_{2i}/H_{2i-1}|=p^{\ell_{i}},\;\,|H_{2i-1}/H_{2i-2}|=m_{i};$ (7)

  4. (d)

$\mathrm{Cay}(\mathbb{Z}_{n}/H_{2t-1},(S_{0}/H_{2t-1})\setminus\\{H_{2t-1}\\})\cong
K_{p^{\ell_{t}}}$.

###### Proof.

We prove the result by induction on $t$. Assume $t=1$ first. Then
$\iota:H_{0}<H_{1}\leq H_{2}=\mathbb{Z}_{n}$. Since $\iota$ is an admissible
subgroup series of $\mathbb{Z}_{n}$ associated with $S_{0}$, either (i)
$H_{0}=\\{0\\}$ and $S_{0}$ is aperiodic, or (ii) $H_{0}\neq\\{0\\}$ and
$S_{0}$ is $H_{0}$-periodic. In the former case, by (T3), we have
$|S_{0}/H_{1}|=|\mathbb{Z}_{n}/H_{1}|$ and $|S_{0}/H_{0}|=|S_{0}/H_{1}|$.
Since $H_{0}=\\{0\\}$, it follows that
$p^{\ell}=|S_{0}|=|S_{0}/H_{0}|=|S_{0}/H_{1}|=|\mathbb{Z}_{n}/H_{1}|$, and so
$H_{1}=\langle p^{\ell}\rangle$ and $|H_{1}|=m$. Set $\ell_{1}=\ell$ and
$m_{1}=m$. Then $\mathbf{l}_{\iota}=(\ell)$ and $\mathbf{m}_{\iota}=(m)$. By
(T2) and (T3), we obtain that $S_{0}/H_{1}$ is
$(\mathbb{Z}_{n}/H_{1})$-periodic, which implies that $\mathbb{Z}_{n}/H_{1}$
is a subset of $S_{0}/H_{1}$. Since $S_{0}\subseteq\mathbb{Z}_{n}$, it follows
that $S_{0}/H_{1}=\mathbb{Z}_{n}/H_{1}$. Therefore, $S_{0}/H_{1}$ is a group
with order $p^{\ell}$ and consequently
$\mathrm{Cay}(\mathbb{Z}_{n}/H_{1},(S_{0}/H_{1})\setminus\\{H_{1}\\})\cong
K_{p^{\ell}}$ as desired.

Now let us consider the case where $H_{0}\neq\\{0\\}$ and $S_{0}$ is
$H_{0}$-periodic. In this case there is an integer $\ell_{1}<\ell$ such that
$H_{0}=\langle p^{\ell_{1}}m\rangle$ and $S_{0}/H_{0}$ is a pyramidal set of
$\mathbb{Z}_{n}$ with $\\{0\\}=H_{0}/H_{0}<H_{1}/H_{0}\leq
H_{2}/H_{0}=\mathbb{Z}_{n}/H_{0}\cong\mathbb{Z}_{p^{\ell_{1}}m}$ as an
associated admissible subgroup series. Set $L_{0}=H_{0}/H_{0}$,
$L_{1}=H_{1}/H_{0}$ and $L_{2}=\mathbb{Z}_{n}/H_{0}$. Since $S_{0}/H_{0}$ is
aperiodic and $L_{0}=\\{0\\}$, we can use what we have proved above in case
(i) to obtain $\mathbf{l}_{\iota}=(\ell_{1})$ and $\mathbf{m}_{\iota}=(m)$. We
have $|H_{2}/H_{1}|=|L_{2}/L_{1}|=p^{\ell_{1}}$ and
$|H_{1}/H_{0}|=|L_{1}/L_{0}|=m$. Similarly to case (i), we can obtain that
$\mathrm{Cay}(\mathbb{Z}_{n}/L_{1},S_{0}/L_{1}\setminus\\{L_{1}\\})\cong
K_{p^{\ell_{1}}}$.

Suppose that for some integer $k>1$ the result is true for all $t<k$. We aim
to prove that the result is also true for $t=k$. We distinguish between the
following two cases.

Case 1. $H_{0}=\\{0\\}$ and $S_{0}$ is aperiodic.

By (T2), $S_{0}/H_{1}$ is $(H_{2}/H_{1})$-periodic. Since $H_{0}=\\{0\\}$, by
(T3), $|S_{0}/H_{1}|=|S_{0}/H_{0}|=|S_{0}|=p^{\ell}$. Thus there is an integer
$a<\ell$ such that $|H_{2}/H_{1}|=p^{a}$. Since $S_{0}/H_{1}$ is
$(H_{2}/H_{1})$-periodic, by Theorem 1.2, Lemma 2.9 and [14, Proposition 3.2],
$\mathrm{Cay}(\mathbb{Z}_{n}/H_{1},S_{0}/H_{1}\setminus\\{H_{1}\\})$ also
admits perfect codes. Let $D$ be a perfect code in
$\mathrm{Cay}(\mathbb{Z}_{n}/H_{1},S_{0}/H_{1}\setminus\\{H_{1}\\})$. By Lemma
2.6 and (T1), we have $\mathbb{Z}_{n}=S_{0}\oplus(D+H_{1})$. Thus $|H_{1}|$ is
a divisor of $m$. Set $|H_{1}|=m^{\prime}$. Then
$|H_{1}/H_{0}|=|H_{1}|=m^{\prime}$, and so $H_{1}=\langle
p^{\ell}m/m^{\prime}\rangle$. This together with $|H_{2}/H_{1}|=p^{a}$ implies
that $H_{2}=\langle p^{\ell-a}m/m^{\prime}\rangle$.

Now by Lemma 2.11, $S_{0}/H_{2}$ is a pyramidal set of $\mathbb{Z}_{n}/H_{2}$,
and

$\iota^{\prime}:H_{2}/H_{2}<H_{3}/H_{2}<\cdots<H_{2k-1}/H_{2}\leq
H_{2k}/H_{2}=\mathbb{Z}_{n}/H_{2}$

is an associated admissible subgroup series. Thus, by Theorem 1.2,
$\mathrm{Cay}(\mathbb{Z}_{n}/H_{2},S_{0}/H_{2}\setminus\\{H_{2}\\})$ admits
perfect codes. By the induction hypothesis, we have two sequences of positive
integers

$\mathbf{l^{\prime}}_{\iota}=(a_{1},a_{2},\ldots,a_{k-1}),\;\mathbf{m^{\prime}}_{\iota}=(b_{1},b_{2},\ldots,b_{k-1})$

with $\sum_{i=1}^{k}a_{i}=\ell-a$ and $\prod_{i=1}^{k}b_{i}$ dividing
$m/m^{\prime}$ such that

$|H_{2i}/H_{2i-1}|=p^{a_{i}},\;\,|H_{2i-1}/H_{2i-2}|=b_{i}$

for $2\leq i\leq k$ and
$\mathrm{Cay}(\mathbb{Z}_{n}/H_{2k-1},(S_{0}/H_{2k-1})\setminus\\{H_{2k-1}\\})\cong
K_{p^{r}}$, where $r=a_{k-1}$. Set

$\mathbf{l}_{\iota}=(a,a_{1},a_{2},\ldots,a_{k-1}),\;\mathbf{m}_{\iota}=(m^{\prime},b_{1},b_{2},\ldots,b_{k-1}).$

Then $\mathbf{l}_{\iota}$ and $\mathbf{m}_{\iota}$ satisfy (7). So we have
proved that the result is true for $t=k$ when $H_{0}=\\{0\\}$ and $S_{0}$ is
aperiodic.

Case 2. $H_{0}\neq\\{0\\}$ and $S_{0}$ is $H_{0}$-periodic.

In this case,

$\iota^{\prime\prime}:H_{0}/H_{0}<H_{1}/H_{0}<\cdots<H_{2k-1}/H_{0}\leq
H_{2k}/H_{0}=\mathbb{Z}_{n}/H_{0}$

is an admissible subgroup series associated with $S_{0}$. Since $S_{0}$ is
$H_{0}$-periodic, there is an integer $1\leq a<\ell$ such that $H_{0}=\langle
p^{\ell-a}m\rangle$ and $|S_{0}/H_{0}|=p^{\ell-a}$. Thus, by what we proved in
Case 1, we have two sequences of positive integers

$\mathbf{l}_{\iota}=(\ell_{1},\ell_{2},\ldots,\ell_{t}),\;\mathbf{m}_{\iota}=(m_{1},m_{2},\ldots,m_{t})$

with $\sum_{i=1}^{t}\ell_{i}=\ell-a$ and $\prod_{i=1}^{t}m_{i}$ dividing $m$
such that

$|H_{2i}/H_{2i-1}|=p^{\ell_{i}},\;\,|H_{2i-1}/H_{2i-2}|=m_{i}$

for $1\leq i\leq t$ and
$\mathrm{Cay}(\mathbb{Z}_{n}/H_{2k-1},(S_{0}/H_{2k-1})\setminus\\{H_{2k-1}\\})\cong
K_{p^{\ell_{t}}}$. Since $\ell-a<\ell$, we have $\sum_{i=1}^{t}\ell_{i}<\ell$.
Moreover, $\mathbf{l}_{\iota}$ and $\mathbf{m}_{\iota}$ satisfy (7). So we
have proved that the result is true for $t=k$ when $H_{0}\neq\\{0\\}$ and
$S_{0}$ is $H_{0}$-periodic.

By mathematical induction, we have completed the proof. $\Box$

##  3 Proof of Theorem 1.2

Proof of Theorem 1.2. Throughout the proof we assume that $G=\mathbb{Z}_{n}$
and $\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ is a connected non-complete
circulant graph with order $n\geq 3$ and degree $|S|=p^{\ell}-1$, where $p$ is
a prime and $\ell\geq 1,m\geq 2$ are integers. We prove the necessary and
sufficient condition first.

Necessity. Suppose that $\Gamma$ admits a perfect code, say, $D$, so that
$G=S_{0}\oplus D$. Then by Lemma 2.3, $|S_{0}|=p^{\ell}$ is a divisor of $n$.
Write $n=p^{\ell}m$. We will prove by induction on $\ell$ that $S_{0}$ is a
pyramidal set of $G$. The base case $\ell=1$ is ensured by Theorem 2.2. In
fact, if $S_{0}$ is periodic with size $p$, then it is the subgroup of $G$
with order $p$ and so cannot be a generating set of $G$ as $m\geq 2$. Thus,
$S_{0}$ is aperiodic and pyramidal with subgroup sequence
$\\{0\\}=H_{0}<H_{1}<H_{2}=G$, where $H_{1}=\langle p\rangle$.

Suppose $\ell>1$. By Theorem 2.1, $\Gamma$ admits a perfect code $H$ which is
a subgroup of $G$ if and only if $H=\langle p^{\ell}\rangle$ and
$(S_{0}-S_{0})\cap H=\\{0\\}$. In this case $S_{0}$ is a pyramidal set with
admissible subgroup series $\\{0\\}=H_{0}<H_{1}<H_{2}=G$, where $H_{1}=\langle
p^{\ell}\rangle$. It remains to consider the case where
$(S_{0}-S_{0})\cap\langle p^{\ell}\rangle\neq\\{0\\}$. We claim that ${\rm
gcd}(p,m)\neq 1$ in this case. Suppose otherwise. Then by Lemma 2.5 there are
subgroups $H,K$ of $G$ such that $|H|=|S_{0}|=p^{\ell}$, $|K|=|D|=m$, and
$G=S_{0}\oplus D=H\oplus K=S_{0}\oplus K$. Since the sum $S_{0}\oplus K$ is
direct, the elements of $S_{0}$ are pairwise distinct modulo $K$, and $K$ is
the cyclic group of $G$ generated by $p^{\ell}$. Therefore,
$(S_{0}-S_{0})\cap\langle p^{\ell}\rangle=\\{0\\}$, but this is a
contradiction. Hence ${\rm gcd}(p,m)\neq 1$ as claimed.

Case 1. $S_{0}$ is periodic.

The subgroup of periods of $S_{0}$ must be of the form $H=\langle
p^{\ell_{1}}m\rangle$ for some $\ell_{1}<\ell$. Hence
$|S_{0}/H|=p^{\ell_{1}}$. By Theorem 2.1 and Lemma 2.4,
$G/H=(S_{0}/H)\oplus(D/H)$ and $(D-D)\cap H=\\{0\\}$. So, by the induction
hypothesis, $S_{0}/H$ is a pyramidal set of $G/H$. Therefore, $S_{0}$ is a
pyramidal set of $G$ by definition.

Case 2. $S_{0}$ is aperiodic.

In this case, by Lemma 2.7, $D$ must be periodic, say, $D=D_{1}\oplus K$ for
some subgroup $K$ with order $m_{1}$ dividing $m$. By Theorem 2.1,
$G/K=(S_{0}/K)\oplus(D/K)$ and $(S_{0}-S_{0})\cap K=\\{0\\}$. The second
condition implies that $|S_{0}/K|=p^{\ell}$. By a further application of Lemma
2.7, we see that $S_{0}/K$ is periodic, say, with subgroup of periods $H/K$.
Thus, by what we have proved in Case 1, $S_{0}/K$ is a pyramidal set of $G/K$.
Hence, if $H/K$ is the subgroup of periods of $S_{0}/K$, where $H$ is a
subgroup containing $K$, then $S_{0}/H$ is an aperiodic pyramidal set of
$G/H$. Let $\\{0\\}<H_{1}/H<\cdots<H_{2t-1}/H<H_{2t}/H=G/H$ be an admissible
subgroup series of $G/H$ associated with $S_{0}/H$. Then
$\\{0\\}<K<H<H_{1}<\cdots<H_{2t-1}\leq H_{2t}=G$ is an admissible subgroup
series of $G$ associated with $S_{0}$ and therefore $S_{0}$ is a pyramidal set
of $G$.

Sufficiency. Suppose that $p^{\ell}$ divides $n$ and $S_{0}$ is pyramidal.
Then $n=p^{\ell}m$ for some integer $m\geq 2$. (Note that $m\neq 1$ for
otherwise $\Gamma$ would be a complete graph, which contradicts our
assumption.) Let $H_{0}<H_{1}<\cdots<H_{2t-1}\leq H_{2t}=G$ be an admissible
subgroup series of $G$ associated with $S_{0}$. To prove that $\Gamma$ admits
a perfect code, it suffices to prove the existence of a subset $D$ of $G$ such
that $G=S_{0}\oplus D$.

Suppose first that $S_{0}$ is aperiodic. Then $H_{0}=\\{0\\}$. If $t=1$, then,
by (T1), $(S_{0}-S_{0})\cap H_{1}=0$. In particular, $|S_{0}/H_{1}|=|S_{0}|$
and, by (T3), $n=|S_{0}/H_{1}|\cdot|H_{1}|=|S_{0}|\cdot|H_{1}|$. Therefore,
the sum $S_{0}\oplus H_{1}$ is direct and is equal to $G$, completing the
proof in this case. Assume $t>1$. By (T3), $|G/H_{2t-1}|=|S_{0}/H_{2t-1}|$. So
$|(G/H_{2t-2})/(H_{2t-1}/H_{2t-2})|=|G/H_{2t-1}|=|S_{0}/H_{2t-1}|$. Again, by
(T3),
$|G/H_{2t-2}|=|S_{0}/H_{2t-1}||H_{2t-1}/H_{2t-2}|=|S_{0}/H_{2t-2}||H_{2t-1}/H_{2t-2}|$.
Combining (T1) and Lemma 2.6, we obtain that
$G/H_{2t-2}=(S_{0}/H_{2t-2})\oplus(H_{2t-1}/H_{2t-2})$. Using Theorem 2.10 and
(T2), we see that there exists a subset $D\subset G$ such that
$G/H_{2t-3}=(S_{0}/H_{2t-3})\oplus(D/H_{2t-3})$. Moreover,

$(G/H_{2t-4})/(H_{2t-3}/H_{2t-4})=\left((S_{0}/H_{2t-4})/(H_{2t-3}/H_{2t-4})\right)\oplus\left((D/H_{2t-4})/(H_{2t-3}/H_{2t-4})\right).$

Again, using Lemma 2.6 and (T1), we obtain that
$G/H_{2t-4}=(S_{0}/H_{2t-4})\oplus((D/H_{2t-4})+(H_{2t-3}/H_{2t-4}))$. Since
$t$ is finite, repeating this process we can eventually obtain a subset
$D^{\prime}\subset G$ containing $0$ such that
$G/H_{1}=(S_{0}/H_{1})\oplus(D^{\prime}/H_{1})$, and a further application of
Theorem 2.1 using (T1) with $i=1$ gives $G=S_{0}\oplus(D^{\prime}+H_{1})$ as
desired.

In the case when $S_{0}$ is period, the proof is essentially the same as above
with $G/H_{0},S_{0}/H_{0}$ playing the role of $G,S_{0}$, respectively, where
$H_{0}$ is the subgroup of periods of $S_{0}$ in $G$.

Up to now we have proved the necessary and sufficient condition in Theorem
1.2.

We now prove (a) and (b). Suppose that $p^{\ell}$ divides $n$, $S_{0}$ is
pyramidal and aperiodic, and the longest admissible subgroup series associated
with $S_{0}$ is $H_{0}<H_{1}<H_{2}<\dots<H_{2t-1}\leq H_{2t}=\mathbb{Z}_{n}$.
Then $n=p^{\ell}m$, where $m\geq 2$ as $\Gamma$ is non-complete, and
$H_{0}=\\{0\\}$ as $S_{0}$ is aperiodic. By what we have proved above,
$\Gamma$ admits perfect codes.

(a) Assume $(S_{0}-S_{0})\cap\langle p^{\ell}\rangle=\\{0\\}$. Consider the
case $t=1$ first. In this case we have $H_{1}=\langle p^{\ell}\rangle$ and
$\mathrm{Cay}(\mathbb{Z}_{n}/H_{1},(S_{0}/H_{1})\setminus\\{H_{1}\\})$ is a
complete graph with $0+H_{1}$ as the unique perfect code containing the
identity element of $\mathbb{Z}_{n}/H_{1}$. By Lemma 2.4, we have
$\mathbb{Z}_{n}=S_{0}\oplus H_{1}$. Hence $H_{1}$ is the only perfect code of
$\Gamma$ containing $0$.

Now consider the case $t>1$. In this case $S_{0}/H_{1}$ is periodic and its
subgroup of periods has order $p^{\ell_{1}}$ for some integer
$0<\ell_{1}<\ell$. Thus,
$\mathrm{Cay}(\mathbb{Z}_{n}/H_{1},(S_{0}/H_{1})\setminus\\{H_{1}\\})$ admits
a perfect code $D/H_{1}$ which is not a subgroup of $\mathbb{Z}_{n}/H_{1}$.
So, by Theorem 2.1 and the definition of a pyramidal set, $\Gamma$ admits
$D+H_{1}$ as a perfect code which is not a subgroup of $\mathbb{Z}_{n}$. On
the other hand, since $(S_{0}-S_{0})\cap\langle p^{\ell}\rangle=\langle
0\rangle$ and $|S_{0}|\cdot|\langle p^{\ell}\rangle|=p^{\ell}m$,
$S_{0}+\langle p^{\ell}\rangle$ is a direct sum and $S_{0}\oplus\langle
p^{\ell}\rangle=\mathbb{Z}_{n}$ by Lemma 2.3(c), and so $\langle
p^{\ell}\rangle$ is a perfect code in $\Gamma$. Thus the subgroup $\langle
p^{\ell}\rangle$ of $\mathbb{Z}_{n}$ with order $n/p^{\ell}$ is a perfect code
in $\Gamma$.

(b) Assume $(S_{0}-S_{0})\cap\langle p^{\ell}\rangle\neq\\{0\\}$. Then by
Theorem 2.1, $\langle p^{\ell}\rangle$ is not a perfect code in $\Gamma$.
Since any perfect code in $\Gamma$ has size $n/p^{\ell}$ and $\langle
p^{\ell}\rangle$ is the only subgroup of $\mathbb{Z}_{n}$ with order
$n/p^{\ell}$, it follows that $\Gamma$ admits no subgroup of $\mathbb{Z}_{n}$
as a perfect code. However, $\Gamma$ admits perfect codes as mentioned
earlier. Hence there are perfect codes in $\Gamma$ but none of them is
$\langle p^{\ell}\rangle$ . $\Box$

We illustrate the two cases in Theorem 1.2 by two examples.

######  Example 3.1.

Consider the circulant graph $\mathrm{Cay}(\mathbb{Z}_{3^{2}\cdot 10},S)$ with
order $3^{2}\cdot 10$ and degree $3^{2}-1$, where
$S=\\{1,5,6,7,83,84,85,89\\}$. It can be verified that $S_{0}$ is aperiodic
and $(S_{0}-S_{0})\cap\langle 3^{2}\rangle=\\{0\\}$. Setting $H_{0}=\\{0\\}$,
$H_{1}=\langle 18\rangle$, $H_{2}=\langle 6\rangle$ and $H_{3}=\langle
3\rangle$, we see that $S_{0}$ is a pyramidal set of $\mathbb{Z}_{3^{2}\cdot
10}$ with $H_{0}<H_{1}<H_{2}<H_{3}<H_{4}=\mathbb{Z}_{3^{2}\cdot 10}$ as an
admissible subgroup series. One can verify that $\langle 3^{2}\rangle$ is a
perfect code in $\mathrm{Cay}(\mathbb{Z}_{3^{2}\cdot 10},S)$ as guaranteed by
part (a) of Theorem 1.2. Since $t=2>1$ in this case, by part (a) of Theorem
1.2 there should have perfect codes in $\mathrm{Cay}(\mathbb{Z}_{3^{2}\cdot
10},S)$ containing $0$ which are different from $\langle 3^{2}\rangle$.
Indeed, this is the case as $D=\\{0,3,18,21,36,39,54,57,72,75\\}\neq\langle
3^{2}\rangle$ is such a perfect code in $\mathrm{Cay}(\mathbb{Z}_{3^{2}\cdot
10},S)$. Note that $D$ is not equally spaced. One can verify that
$\mathrm{Cay}(\mathbb{Z}_{3^{2}\cdot 10},S)$ is not isomorphic to the wreath
product of a smaller circulant graph admitting perfect codes and a complete
graph with at least two vertices. This shows that there exist circulant graphs
which admit a non-equally spaced perfect code but are not the wreath product
of a smaller circulant graph admitting perfect codes and a complete graph with
at least two vertices.

Setting $L_{0}=\\{0\\}$ and $L_{1}=\langle 9\rangle$, we see that
$L_{0}<L_{1}<L_{2}=\mathbb{Z}_{3^{2}\cdot 10}$ is another admissible subgroup
series associated with $S_{0}$. This shows that the same extended connection
set can be pyramidal with respect to different admissible subgroup series.
$\Box$

######  Example 3.2.

Let

$\displaystyle S=\\{1,44,45,46,224,225,226,269,270,271,314,315,316,2114,2115,$
$\displaystyle 2116,2159,2160,2161,2204,2205,2206,2384,2385,2386,2429\\}.$

Then $\mathrm{Cay}(\mathbb{Z}_{3^{3}\cdot 90},S)$ is a circulant graph with
order $3^{3}\cdot 90$ and degree $3^{3}-1$. We have $(S_{0}-S_{0})\cap\langle
3^{3}\rangle\neq\\{0\\}$ and $S_{0}$ is aperiodic. It can be verified that
$S_{0}$ is a pyramidal set of $\mathbb{Z}_{3^{3}\cdot 90}$ with
$H_{0}<H_{1}<H_{2}<H_{3}<H_{4}<H_{5}<H_{6}=\mathbb{Z}_{3^{3}\cdot 90}$ as an
admissible subgroup series, where $H_{0}=\\{0\\}$, $H_{1}=\langle 810\rangle$,
$H_{2}=\langle 270\rangle$, $H_{3}=\langle 135\rangle$, $H_{4}=\langle
45\rangle$ and $H_{5}=\langle 3\rangle$. Thus, by part (b) of Theorem 1.2,
there are perfect codes in $\mathrm{Cay}(\mathbb{Z}_{3^{3}\cdot 90},S)$
containing $0$, but none of them is $\langle 3^{3}\rangle$. It can be verified
that

$\displaystyle D=\\{0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,135,138,141,144,$
$\displaystyle 147,150,153,156,159,162,165,168,171,174,177\\}+\langle
810\rangle$

is such a perfect code.

Note that $\\{0,270\\}\subset S_{0}$ and $270-0\equiv 0\pmod{3^{3}}$. So this
example shows that a circulant graph $\mathrm{Cay}(\mathbb{Z}_{n},S)$ with
$|S_{0}|=p^{\ell}$ can admit perfect codes even if there are distinct elements
$s,s^{\prime}\in S_{0}$ such that $s-s^{\prime}\equiv 0\pmod{p^{\ell}}$.
$\Box$

##  4 Proof of Theorem 1.3

A graph $\Sigma$ is a _covering graph_ of a graph $\Gamma$ if there exists a
surjective map $\rho:V(\Sigma)\rightarrow V(\Gamma)$ such that for each $v\in
V(\Sigma)$ the restriction of $\rho$ to the neighourhood of $v$ in $\Sigma$ is
a bijection onto the neighbourhood of $\rho(v)$ in $\Gamma$. Call $\rho$ a
_covering map_ from $\Sigma$ to $\Gamma$. When all fibres $\rho^{-1}(u)$,
$u\in V(\Gamma)$ have the same size, say, $k$, we also say that $\Sigma$ is a
_$k$ -fold cover_ of $\Gamma$.

######  Definition 4.1.

Let $\Sigma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a circulant graph. Let $m$ be a
divisor of $n$ and $H=\langle n/m\rangle$ the unique subgroup of
$\mathbb{Z}_{n}$ with order $m$. If $(S_{0}-S_{0})\cap H=\\{0\\}$, then define

$f_{m}(\Sigma)=\mathrm{Cay}(\mathbb{Z}_{n}/H,S/H);$

if $S_{0}$ is $H$-periodic, then define

$g_{m}(\Sigma)=\mathrm{Cay}(\mathbb{Z}_{n}/H,(S_{0}/H)\setminus\\{H\\}).$

######  Remark 4.2.

(i) If $(S_{0}-S_{0})\cap H=\\{0\\}$, then
$f_{m}(\Sigma)\cong\mathrm{Cay}(\mathbb{Z}_{n/m},T)$, where
$T=\\{s\pmod{(n/m)}:s\in S_{0}\\}\setminus\\{0\\}=\\{s\pmod{(n/m)}:s\in S\\}$.
(Note that $|T|=|S/H|=|S|$.) Since $(S_{0}-S_{0})\cap H=\\{0\\}$, each coset
of $H$ in $\mathbb{Z}_{n}$ is an independent set of $\Sigma$ and so $\Sigma$
is an $m$-fold cover of $f_{m}(\Sigma)$. We may view $f_{m}$ as the canonical
projection from $\mathbb{Z}_{n}$ to $\mathbb{Z}_{n}/H$ which sends
$x\in\mathbb{Z}_{n}$ to $x+H\in\mathbb{Z}_{n}/H$, so that $f_{m}$ is a
covering map from $\Sigma$ to $f_{m}(\Sigma)$. If $\Sigma$ is connected, then
so is $f_{m}(\Sigma)$.

(ii) If $S_{0}$ is $H$-periodic, then
$g_{m}(\Sigma)\cong\mathrm{Cay}(\mathbb{Z}_{n/m},T)$, where
$T=\\{s\pmod{(n/m)}:s\in S_{0}\\}\setminus\\{0\\}$. (Note that
$|T|=(|S_{0}|/|H|)-1$.) Again, we may view $g_{m}$ as the canonical projection
from $\mathbb{Z}_{n}$ to $\mathbb{Z}_{n}/H$ which sends $x\in\mathbb{Z}_{n}$
to $x+H\in\mathbb{Z}_{n}/H$, so that $g_{m}$ is a graph homomorphism from
$\Sigma$ to $g_{m}(\Sigma)$.

######  Construction 4.3.

Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq 1,m\geq 2$ are integers.
Let $\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a connected circulant graph
with order $n$ and degree $p^{\ell}-1$ such that $S_{0}$ is aperiodic and
pyramidal. Let $\iota:H_{0}<H_{1}<\cdots<H_{2t-1}\leq H_{2t}=\mathbb{Z}_{n}$
be an admissible subgroup series associated with $S_{0}$, where $t\geq 1$ and
$H_{0}=\\{0\\}$. By Lemma 2.12, this series determines two sequences of
positive integers (see (6)), namely
$\mathbf{l}_{\iota}=(\ell_{1},\ell_{2},\ldots,\ell_{t})$ and
$\mathbf{m}_{\iota}=(m_{1},m_{2},\ldots,m_{t})$, such that
$\sum_{i=1}^{t}\ell_{i}=\ell$, $\prod_{i=1}^{t}m_{i}$ divides $m$,
$|H_{2i}/H_{2i-1}|=p^{\ell_{i}}$ and $|H_{2i-1}/H_{2i-2}|=m_{i}$ for $1\leq
i\leq t$, and
$\mathrm{Cay}(\mathbb{Z}_{n}/H_{2t-1},(S_{0}/H_{2t-1})\setminus\\{H_{2t-1}\\})\cong
K_{p^{\ell_{t}}}$. Set

$\Gamma_{i}=\mathrm{Cay}(\mathbb{Z}_{n}/H_{i},(S_{0}/H_{i})\setminus\\{H_{i}\\})$

for $0\leq i\leq 2t-1$. Then each $\Gamma_{i}$ is a connected circulant graph.
We have $\Gamma_{0}=\Gamma$ (as $H_{0}=\\{0\\}$) and $\Gamma_{2t-1}\cong
K_{p^{\ell_{t}}}$.

Let

$f_{m_{i}}:\mathbb{Z}_{n}/H_{2(i-1)}\to\mathbb{Z}_{n}/H_{2i-1}$

for $1\leq i\leq t$ and

$g_{p^{\ell_{i}}}:\mathbb{Z}_{n}/H_{2i-1}\to\mathbb{Z}_{n}/H_{2i}$

for $1\leq i\leq t-1$ be the natural projections. Slightly abusing notation,
for any graph $\Sigma$ with vertex set $\mathbb{Z}_{n}/H_{2(i-1)}$ we use
$f_{m_{i}}(\Sigma)$ to denote the graph with vertex set
$\mathbb{Z}_{n}/H_{2i-1}$ and adjacency relation inherited from $\Sigma$
(thus, $f_{m_{i}}$ becomes a graph homomorphism from $\Sigma$ to
$f_{m_{i}}(\Sigma)$). For any graph $\Sigma$ with vertex set
$\mathbb{Z}_{n}/H_{2i-1}$, the graph $g_{p^{\ell_{i}}}(\Sigma)$ is similarly
defined. In particular, $f_{m_{i}}(\Gamma_{2(i-1)})$ is well defined for
$1\leq i\leq t$ and $g_{p^{\ell_{i}}}(\Gamma_{2i-1})$ is well defined for
$1\leq i\leq t-1$. So we have the chain of graph homomorphisms:

$\Gamma_{0}\xrightarrow{f_{m_{1}}}\Gamma_{1}\xrightarrow{g_{p^{\ell_{1}}}}\Gamma_{2}\xrightarrow{}\cdots\xrightarrow{}\Gamma_{2(t-2)}\xrightarrow{f_{m_{t-1}}}\Gamma_{2t-3}\xrightarrow{g_{p^{\ell_{t-1}}}}\Gamma_{2(t-1)}\xrightarrow{f_{m_{t}}}\Gamma_{2t-1}.$

This means that $\Gamma$ can be reduced to the complete graph
$\Gamma_{2t-1}\cong K_{p^{\ell_{t}}}$ through the $2t-1$ projections in this
chain. We may present this fact as

$(f_{m_{t}}g_{p^{\ell_{t-1}}}f_{m_{t-1}}\cdots
g_{p^{\ell_{1}}}f_{m_{1}})(\Gamma)\cong K_{p^{\ell_{t}}}.$

Note that $f_{m_{i}}$ is a covering map from $\Gamma_{2(i-1)}$ to
$\Gamma_{2i-1}$ as $\iota$ and $S_{0}$ satisfy (T1)–(T3). $\Box$

An important remark is in order: Since $\iota$ and $S_{0}$ satisfy (T1)–(T3),
one can verify that $f_{m_{i}}(\Sigma)$ and $g_{p^{\ell_{i}}}(\Sigma)$ defined
in Construction 4.3 are the same as $f_{m_{i}}(\Sigma)$ and
$g_{p^{\ell_{i}}}(\Sigma)$ obtained from Construction 4.6 below for
appropriate $\Sigma$, respectively. So there is no ambiguity to use the graph
homomorphisms $f_{m}$ and $g_{m}$ defined in Definition 4.1.

We now introduce two other maps which are right-inverses of $f_{m}$ and
$g_{m}$, respectively.

######  Definition 4.4.

Let $\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ and let $m\geq 1$ be an integer. A
map $\sigma:S_{0}\rightarrow\\{0,1,\ldots,m-1\\}$ is said to be _feasible_ if
$\sigma(0)=0$ and $-T(\sigma)=T(\sigma)$ in $\mathbb{Z}_{mn}$, where
$T(\sigma)=\\{s+\sigma(s)n:s\in S\\}$. Set
$T(\sigma)_{0}=T(\sigma)\cup\\{0\\}=\\{s+\sigma(s)n:s\in S_{0}\\}$.

Given a feasible map $\sigma:S_{0}\rightarrow\\{0,1,\ldots,m-1\\}$, define

$\Gamma(\sigma)=\mathrm{Cay}(\mathbb{Z}_{mn},T(\sigma)).$

Define

$\bar{f}_{m}(\Gamma)=\\{\Gamma(\sigma):\sigma:S_{0}\rightarrow\\{0,1,\ldots,m-1\\}\text{
is feasible}\\}$
$\bar{f}_{m}(S_{0})=\\{T(\sigma)_{0}:\sigma:S_{0}\rightarrow\\{0,1,\ldots,m-1\\}\text{
is feasible}\\}.$

Define

$\bar{g}_{m}(\Gamma)=\mathrm{Cay}(\mathbb{Z}_{mn},T)$

to be the Cayley graph of $\mathbb{Z}_{mn}$ with extended connection set
$T_{0}=\\{s+in:s\in S_{0},0\leq i\leq m-1\\}$. Write
$T_{0}=\bar{g}_{m}(S_{0})$.

We often write $\bar{f}_{m}(S)$, $\bar{g}_{m}(S_{0})$ in place of
$\bar{f}_{m}(\Gamma),\bar{g}_{m}(\Gamma)$, respectively.

######  Remark 4.5.

(i) By definition $\bar{f}_{m}(S_{0})$ is the family of extended connection
sets of the circulant graphs in $\bar{f}_{m}(\Gamma)$. More specifically,
$\mathrm{Cay}(\mathbb{Z}_{mn},T)\in\bar{f}_{m}(\Gamma)$ if and only if
$T_{0}\in\bar{f}_{m}(S_{0})$.

Note that $(T(\sigma)_{0}-T(\sigma)_{0})\cap\langle n\rangle=\\{0\\}$ and
$\pi:\mathbb{Z}_{mn}\rightarrow\mathbb{Z}_{mn}/\langle n\rangle,x\mapsto
x+\langle n\rangle$ is a covering map from $\Sigma(\sigma)$ to $\Gamma$, where
$\langle n\rangle\cong\mathbb{Z}_{m}$ is the subgroup of $\mathbb{Z}_{mn}$
generated by $n$. Therefore, $\bar{f}_{m}(\Gamma)$ can be described as the set
of circulant graphs $\Sigma=\mathrm{Cay}(\mathbb{Z}_{mn},T)$ such that the
natural projection $\pi:\mathbb{Z}_{mn}\to\mathbb{Z}_{n}$ is an $m$-covering
of $\Sigma$ onto $\Gamma$. In this way $\bar{f}_{m}$ can be seen as a right
inverse of $f_{m}$ as $f_{m}(\bar{f}_{m}(\Gamma))=\Gamma$.

(ii) We observe that a graph $\Sigma$ in $\bar{f}_{m}(\Gamma)$ needs not be
connected (and it is certainly disconnected if $\Gamma$ is not connected).
However, if $\Gamma$ is connected, then $\bar{f}_{m}(\Gamma)$ contains
connected graphs. Write $S$ as the disjoint union $S=S_{1}\cup(-S_{1})$ and
define $\sigma(s)=1$ for $s\in S_{1}$ and $\sigma(-s)=m-1$, so that $\sigma$
is feasible. The connectivity of $\Gamma$ implies ${\rm
gcd}(S_{1}\cup\\{n\\})=1$ and then ${\rm gcd}((S_{1}+m)\cup\\{nm\\})=1$ as
well, implying that $\Gamma(\sigma)$ is connected.

(iii) $\Gamma$ is the quotient graph of $\bar{g}_{m}(\Gamma)$ with respect to
the partition $\\{i+\langle n\rangle:0\leq i\leq n-1\\}$ of $\mathbb{Z}_{mn}$.
Moreover,
$\bar{g}_{m}(\Gamma)=\Gamma\otimes\mathrm{Cay}(\mathbb{Z}_{m},\mathbb{Z}_{m}\setminus\\{0\\})\cong\Gamma\otimes
K_{m}$ and the subgroup of periods of $T_{0}$ in $\mathbb{Z}_{mn}$ is $\langle
n\rangle$. Hence, if $\Gamma$ is connected, then so is $\bar{g}_{m}(\Gamma)$.

(iv) We note that, if $n$ is even and $|S|$ is odd, then for every feasible
map $\sigma$, $|T(\sigma)|$ is odd and therefore $T(\sigma)$ contains the
element $mn/2=s+\sigma(s)m$. If $m$ is also even, as $0\leq\sigma(s)\leq m-1$
we must have $\sigma(s)=m/2$ and $s=0\in S$, which is not possible. Hence, we
must have $m$ odd in this case.

######  Construction 4.6.

Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq 1$, $m\geq 2$ are
integers. Let $\mathbf{l}=(\ell_{1},\ell_{2},\ldots,\ell_{t})$ and
$\mathbf{m}=(m_{1},m_{2},\ldots,m_{t})$ be sequences of positive integers such
that $\sum_{i=1}^{t}\ell_{i}=\ell$ and $\prod_{i=1}^{t}m_{i}=m$. Set
$r=\ell_{t}$. Consider the following $2t-1$ “lifts” of $K_{p^{r}}$: First,
choose a connected graph $\Gamma_{t}$ from $\bar{f}_{m_{t}}(K_{p^{r}})$; set
$\Sigma_{t-1}=\bar{g}_{p^{\ell_{t-1}}}(\Gamma_{t})$ and choose a connected
graph $\Gamma_{t-1}$ from $\bar{f}_{m_{t-1}}(\Sigma_{t-1})$; iterate this
procedure till, finally, set $\Sigma_{1}=\bar{g}_{p^{\ell_{1}}}(\Gamma_{2})$
and choose a connected graph $\Gamma_{1}$ from $\bar{f}_{m_{1}}(\Sigma_{1})$.
Note that, as noted in Remark 4.5 (ii), $\bar{f}_{m_{i}}(\Sigma_{i})$ contains
connected graphs, which are the ones chosen in this procedure.

Denote by $\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{\ell})$ the family of
circulant graphs $\Gamma_{1}$ (as above) obtained from this construction. In
view of Definition 4.4 and Remark 4.5, we see that all graphs in
$\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{\ell})$ are connected with order $n$
and degree $p^{\ell}-1$. Symbolically,
$\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{\ell})$ is obtained from applying
$\bar{f}_{m_{1}}\bar{g}_{p^{\ell_{1}}}\dots\bar{f}_{m_{t-1}}\bar{g}_{p^{\ell_{t-1}}}\bar{f}_{m_{t}}$
to $K_{p^{\ell_{t}}}$. $\Box$

The following lemma can be easily proved.

######  Lemma 4.7.

Let $p$ be a prime, $m,\ell\geq 1,n\geq 3$ integers, and
$\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ a circulant graph of order $n$. Then
the following hold:

  * (a)

if $|S_{0}|$ is a divisor of $n$ and
$(S_{0}-S_{0})\cap\langle|S_{0}|\rangle=\\{0\\}$ in $\mathbb{Z}_{n}$, then
$(T(\sigma)_{0}-T(\sigma)_{0})\cap\langle|T(\sigma)_{0}|\rangle=\\{0\\}$ in
$\mathbb{Z}_{mn}$ for any $T(\sigma)_{0}\in\bar{f}_{m}(S_{0})$;

  * (b)

if $|S_{0}|$ is a divisor of $n$, then $\\{x\pmod{|S_{0}|}:x\in
S_{0}\\}=\\{x\pmod{|T(\sigma)_{0}|}:x\in T(\sigma)_{0}\\}$ for any
$T(\sigma)_{0}\in\bar{f}_{m}(S_{0})$;

  * (c)

if $|S_{0}|$ is a divisor of $n$, $p$ is a divisor of $n/|S_{0}|$, and
$(S_{0}-S_{0})\cap\langle|S_{0}|\rangle=\\{0\\}$ in $\mathbb{Z}_{n}$, then
$(T_{0}-T_{0})\cap\langle|T_{0}|\rangle\neq\\{0\\}$ in
$\mathbb{Z}_{p^{\ell}n}$ for $T_{0}=\bar{g}_{p^{\ell}}(S_{0})$.

Set

$f_{m}(\bar{f}_{m}(\Gamma))=\\{f_{m}(\Gamma(\sigma)):\Gamma(\sigma)\in\bar{f}_{m}(\Gamma)\\},\;\bar{f}_{m}(f_{m}(\Gamma))=\bar{f}_{m}(\Sigma)\text{
where }\Sigma=f_{m}(\Gamma).$

######  Lemma 4.8.

Let $n\geq 3$ be an integer, $m\geq 1$ a divisor of $n$, and
$\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ a circulant graph of order $n$. Then
the following hold:

  * (a)

if $(S_{0}-S_{0})\cap\langle n/m\rangle=\\{0\\}$ in $\mathbb{Z}_{n}$, then all
graphs in $f_{m}(\bar{f}_{m}(\Gamma))$ are isomorphic to $\Gamma$, and
moreover $f_{m}(\bar{f}_{m}(\Gamma))\subseteq\bar{f}_{m}(f_{m}(\Gamma))$;

  * (b)

if $S_{0}$ is $\langle n/m\rangle$-periodic, then $\Gamma\cong
g_{m}(\bar{g}_{m}(\Gamma))\cong\bar{g}_{m}(g_{m}(\Gamma))$.

###### Proof.

(a) If $(S_{0}-S_{0})\cap\langle n/m\rangle=\\{0\\}$ in $\mathbb{Z}_{n}$, then
by the definitions of $f_{m}$ and $\bar{f}_{m}$ we see that all graphs in
$f_{m}(\bar{f}_{m}(\Gamma))$ are isomorphic to $\Gamma$ and
$f_{m}(\bar{f}_{m}(\Gamma))\subseteq\bar{f}_{m}(f_{m}(\Gamma))$.

(b) Denote $k=n/m$. Assume that $S_{0}$ is $\langle k\rangle$-periodic. Then
$\Gamma\cong g_{m}(\bar{g}_{m}(\Gamma))$ by the definitions of $g_{m}$ and
$\bar{g}_{m}$. Recall that $g_{m}(\Gamma)=\mathrm{Cay}(\mathbb{Z}_{n}/\langle
k\rangle,(S_{0}/\langle k\rangle)\setminus\\{\langle
k\rangle\\})\cong\mathrm{Cay}(\mathbb{Z}_{k},T)$, where $T$ satisfies
$T_{0}=\\{s\pmod{k}:s\in S_{0}\\}$. So the connection set of
$\bar{g}_{m}(g_{m}(\Gamma))$ together with the identity element is given by
$\\{s\pmod{k}+ik:s\in S_{0},0\leq i\leq m-1\\}$, which is identical to $S_{0}$
since $S_{0}$ is $\langle k\rangle$-periodic (and hence $S_{0}$ is the union
of some $\langle k\rangle$-cosets in $\mathbb{Z}_{n}$). Hence
$\bar{g}_{m}(g_{m}(\Gamma))\cong\Gamma$. $\Box$

######  Lemma 4.9.

Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq 1,m\geq 2$ are integers.
Let $\mathrm{Cay}(\mathbb{Z}_{n},R)$ and $\mathrm{Cay}(\mathbb{Z}_{n},S)$ be
distinct circulant graphs of $\mathbb{Z}_{n}$ with degree
$|R|=|S|=p^{\ell}-1$. Then
$\bar{f}_{m}(R_{0})\cap\bar{f}_{m}(S_{0})=\emptyset$.

###### Proof.

Since $\mathrm{Cay}(\mathbb{Z}_{n},R)$ and $\mathrm{Cay}(\mathbb{Z}_{n},S)$
are distinct circulant graphs of $\mathbb{Z}_{n}$, we have $R\neq S$. Thus one
of the following cases happens.

Case 1. $\\{x\pmod{|R_{0}|}:x\in R_{0}\\}\neq\\{x\pmod{|S_{0}|}:x\in
S_{0}\\}$.

In this case, by part (b) of Lemma 4.7, for any
$T(\delta)_{0}\in\bar{f}_{m}(R_{0})$ and $T(\sigma)_{0}\in\bar{f}_{m}(S_{0})$,
we have $\\{x\pmod{|T(\delta)_{0}|}:x\in
T(\delta)_{0}\\}\neq\\{x\pmod{|T(\sigma)_{0}|}:x\in T(\sigma)_{0}\\}$ and
hence $T(\delta)_{0}\neq T(\sigma)_{0}$. It follows that
$\bar{f}_{m}(R_{0})\cap\bar{f}_{m}(S_{0})=\emptyset$.

Case 2. $\\{x\pmod{|R_{0}|}:x\in R_{0}\\}=\\{x\pmod{|S_{0}|}:x\in S_{0}\\}$
but there are elements $r\in R_{0},s\in S_{0}$ such that $r\neq s$ but
$r\equiv s\pmod{p^{\ell}}$.

We claim that, for any $T(\delta)_{0}\in\bar{f}_{m}(R_{0})$ and
$T(\sigma)_{0}\in\bar{f}_{m}(S_{0})$, the element $r+\sigma(r)n$ of
$T(\delta)_{0}$ and the element $s+\tau(s)n$ of $T(\sigma)_{0}$ are distinct.
Suppose otherwise. Then $(s-r)+(\tau(s)-\sigma(r))n=0$ and hence $s-r\equiv
0\pmod{n}$. Since $0\leq r,s\leq n-1$, we must have $r=s$, which is a
contradiction. So $r+\sigma(r)n\neq s+\tau(s)n$ and thus $T(\delta)_{0}\neq
T(\sigma)_{0}$. It follows that
$\bar{f}_{m}(R_{0})\cap\bar{f}_{m}(S_{0})=\emptyset$. $\Box$

######  Lemma 4.10.

Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq 1,m\geq 2$ are integers
such that ${\rm gcd}(m,p)=1$, and let $\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a
circulant graph with order $n$ and degree $|S|=p^{\ell}-1$. Then the following
hold for any integers $a,b\geq 2$ and $r\geq 1$:

  * (a)

$(\bar{f}_{b}\bar{f}_{a})(S_{0})=\bar{f}_{ab}(S_{0})$;

  * (b)

$(\bar{g}_{b}\bar{g}_{a})(S_{0})=\bar{g}_{ab}(S_{0})$;

  * (c)

if ${\rm gcd}(a,p)=1$, then
$(\bar{g}_{p^{r}}\bar{f}_{a})(S_{0})\subseteq(\bar{f}_{a}\bar{g}_{p^{r}})(S_{0})$;

  * (d)

if $p$ is a divisor of $a$, then
$(\bar{g}_{p^{r}}\bar{f}_{a})(S_{0})\cap(\bar{f}_{a}\bar{g}_{p^{r}})(S_{0})=\emptyset$;

  * (e)

if $p$ is a divisor of $a$, then for any nonnegative integers $c,h,k$ with
$1\leq c<h$ and $k\neq 0$, we have
$(\bar{g}_{p^{k}}\bar{f}_{a}\bar{g}_{p^{h}})(S_{0})\cap(\bar{g}_{p^{k+c}}\bar{f}_{a}\bar{g}_{p^{h-c}})(S_{0})=\emptyset$;

  * (f)

if $p$ is a divisor of $a$, then for any divisor $d$ of $a$ which is divisible
by $p$, we have
$(\bar{f}_{bd}\bar{g}_{p^{r}}\bar{f}_{a/d})(S_{0})\cap(\bar{f}_{b}\bar{g}_{p^{r}}\bar{f}_{a})(S_{0})=\emptyset$.

###### Proof.

(a) Every member of $(\bar{f}_{b}\bar{f}_{a})(S_{0})$ is of the form
$T(\eta)_{0}\in\bar{f}_{b}(T(\zeta)_{0})$ for some
$T(\zeta)_{0}\in\bar{f}_{a}(S_{0})$, where
$\zeta:S_{0}\rightarrow\\{0,1,\ldots,a-1\\}$ is feasible in $\mathbb{Z}_{an}$
and $\eta:T(\zeta)_{0}\rightarrow\\{0,1,\ldots,b-1\\}$ is feasible in
$\mathbb{Z}_{abn}$. We have $T(\eta)_{0}=\\{x+\eta(x)an:x\in
T(\zeta)_{0}\\}=\\{s+\zeta(s)n+\eta(s+\zeta(s)n)an:s\in
S_{0}\\}=\\{s+\sigma(s)n:s\in S_{0}\\}$, where we set
$\sigma(s)=\zeta(s)+\eta(s+\zeta(s)n)a$ for any $s\in S_{0}$. Since
$0\leq\zeta(s)\leq a-1$ and $0\leq\eta(s+\zeta(s)n)\leq b-1$, we have
$0\leq\sigma(s)\leq ab-1$ for any $s\in S_{0}$. Note that
$\sigma(0)=\zeta(0)+\eta(0+\zeta(0)n)a=0+\eta(0+0)a=0$. Since
$-T(\eta)_{0}=T(\eta)_{0}$, we have $-T(\sigma)_{0}=T(\sigma)_{0}$ and hence
$\sigma:S_{0}\rightarrow\\{0,1,\ldots,ab-1\\}$ is feasible in
$\mathbb{Z}_{abn}$. Moreover, by the definition of $T(\sigma)$ we have
$T(\eta)_{0}=T(\sigma)_{0}\in\bar{f}_{ab}(S_{0})$. Since this holds for any
$T(\eta)_{0}\in(\bar{f}_{b}\bar{f}_{a})(S_{0})$, it follows that
$(\bar{f}_{b}\bar{f}_{a})(S_{0})\subseteq\bar{f}_{ab}(S_{0})$.

Conversely, let $T(\sigma)_{0}\in\bar{f}_{ab}(S_{0})$, where
$\sigma:S_{0}\rightarrow\\{0,1,\ldots,ab-1\\}$ is feasible in
$\mathbb{Z}_{abn}$. Define $\delta:S_{0}\rightarrow\\{0,1,\ldots,a-1\\}$ in
such a way that for any $s\in S_{0}$ we have $\delta(-s)=a-1-\delta(s)$ (and
in particular $\delta(0)=0$) in $\mathbb{Z}_{an}$, and
$\tau(s):=(\sigma(s)-\delta(s))/a$ is an integer between $0$ and $b-1$ and
$\tau(-s)=b-1-\tau(s)$. (Since for each $s\in S_{0}$, $0\leq\sigma(s)\leq
ab-1$, we have $\sigma(x)=x_{s}+y_{s}a$ for some integers $0\leq x_{s}\leq
a-1$ and $0\leq y_{s}\leq b-1$, and thus $(\sigma(s)-x_{s})/a$ is an integer
between $0$ and $b-1$. Set $\delta(s)=x_{s}$ and $\tau(s)=y_{s}$ to obtain the
required $\delta$.) Since $\delta(-s)=a-1-\delta(s)$ in $\mathbb{Z}_{abn}$ for
each $s\in S$, we have $T(\delta)=-T(\delta)$, and so by Definition 4.4,
$\delta$ is feasible. It can be verified that
$T(\delta)_{0}\in\bar{f}_{a}(S_{0})$ and $\tau$ is a feasible map from $S_{0}$
to $\\{0,1,\ldots,b-1\\}$. Note that $T(\sigma)_{0}=\\{s+\sigma(s)n:s\in
S_{0}\\}=\\{s+(\delta(s)+\tau(s)a)n:s\in
S_{0}\\}=\\{(s+\delta(s)n)+\tau(s)an:s\in S_{0}\\}$ and
$T(\delta)_{0}=\\{s+\delta(s)n:s\in S_{0}\\}$. Since $|S_{0}|=|T(\delta)_{0}|$
and $\tau(s)=b-1-(\tau(-s))$ for any $s\in S_{0}$, we obtain a map
$\nu:T(\delta)_{0}\rightarrow\\{0,1,\ldots,b-1\\}$ such that
$\nu(s+\delta(s)n)=\tau(s)$ for any $s\in S_{0}$ and
$\nu(0)=\nu(0+\delta(0)n)=\tau(0)=0$. Since
$T(\delta)_{0}\in\bar{f}_{a}(S_{0})$ and $T(\sigma)$ is inverse-closed in
$\mathbb{Z}_{abn}$, $T(\nu)$ is also inverse-closed in $\mathbb{Z}_{abn}$ and
moreover $T(\nu)_{0}\in\bar{f}_{b}(T(\delta)_{0})$. So
$T(\sigma)_{0}\in\bar{f}_{b}(T(\delta)_{0})\subseteq(\bar{f}_{b}\bar{f}_{a})(S_{0})$.
Since this holds for any $T(\sigma)_{0}\in\bar{f}_{ab}(S_{0})$, it follows
that $\bar{f}_{ab}(S_{0})\subseteq(\bar{f}_{b}\bar{f}_{a})(S_{0})$ and hence
$(\bar{f}_{a}\bar{f}_{b})(S_{0})=\bar{f}_{ab}(S_{0})$ as desired.

(b) Let $T_{0}=\bar{g}_{a}(S_{0})$. Then $T_{0}=\\{s+in:s\in S_{0},0\leq i\leq
a-1\\}$ is a subset of $\mathbb{Z}_{an}$ and
$(\bar{g}_{b}\bar{g}_{a})(S_{0})=\\{x+jan:0\leq j\leq b-1,x\in
T_{0}\\}=\\{s+(i+ja)n:0\leq i\leq a-1,0\leq j\leq b-1,s\in
S_{0}\\}=\\{s+kn:0\leq k\leq ab-1,s\in S_{0}\\}=\bar{g}_{ab}(S_{0})$, where in
the second last step we used the fact that $\\{i+ja:0\leq i\leq a-1,0\leq
j\leq b-1\\}=\\{k:0\leq k\leq ab-1\\}$. Thus
$(\bar{g}_{b}\bar{g}_{a})(S_{0})=\bar{g}_{ab}(S_{0})$ as desired.

(c) Assume ${\rm gcd}(a,p)=1$. We aim to prove that each element of
$(\bar{g}_{p^{r}}\bar{f}_{a})(S_{0})$ is an element of
$(\bar{f}_{a}\bar{g}_{p^{r}})(S_{0})$. Let
$T_{0}\in(\bar{g}_{p^{r}}\bar{f}_{a})(S_{0})$. Then
$T_{0}=\bar{g}_{p^{r}}(T(\sigma)_{0})$ for some feasible map
$\sigma:S_{0}\rightarrow\\{0,1,\ldots,a-1\\}$ with
$T(\sigma)_{0}\in\bar{f}_{a}(S_{0})$. So, by the definitions of $\bar{f}_{a}$
and $\bar{g}_{p^{r}}$, we have $T_{0}=\\{x+ian:x\in T(\sigma)_{0},0\leq i\leq
p^{r}-1\\}=\\{s+\sigma(s)n+ian:s\in S_{0},0\leq i\leq p^{r}-1\\}$. For each
fixed $s\in S_{0}$, set
$A(s)=\\{\alpha(i)n+\beta(i)np^{r}:\alpha(i)\equiv(\sigma(s)+ia)\
(\text{mod}\,p^{r}),\beta(i)=(\sigma(s)+ia-\alpha(i))/p^{r},0\leq i\leq
p^{r}-1\\}$. Then for any distinct $0\leq i,j\leq p^{r}-1$ we have
$\alpha(i)\neq\alpha(j)$, for otherwise we would have
$(i-j)an=(\sigma(s)n+ian)-(\sigma(s)n+jan)=\alpha(i)n+\beta(i)np^{r}-(\alpha(j)+\beta(j)np^{r})=(\beta(i)-\beta(j))np^{r}$,
which contradicts our assumption that ${\rm gcd}(a,p)=1$. Moreover, for each
fixed $s\in S_{0}$, we have $\sigma(s)n+ian=\alpha(i)n+\beta(i)np^{r}$ and
$\\{\alpha(i):0\leq i\leq p^{r}-1\\}=\\{j:0\leq j\leq p^{r}-1\\}$. So
$T_{0}=\\{s+\alpha(i)n+\beta(i)np^{r}:s\in S_{0},0\leq i\leq
p^{r}-1\\}=\\{s+\alpha(i)n+\beta(i)np^{r}:s\in S_{0},0\leq\alpha(i)\leq
p^{r}-1\\}=\\{x+\beta(i)np^{r}:x\in\bar{g}_{p^{r}}(S_{0})\\}$. Note that
$\beta(i)=(\sigma(s)+a-\alpha(i))/p^{r}$ depends on $\alpha(i)$ and $s$. Since
${\rm gcd}(a,p)=1$, for any $0\leq i\leq p^{r}-1$, $ia=\beta(i)p^{r}$ if and
only if $\beta(i)=0$. Thus, if $s=0$ and $\alpha(i)=0$, then
$ia=\beta(i)p^{r}$ and hence $\beta(i)=0$. So we have $\beta(0)=0$. We can
view $\beta$ as a map from $\bar{g}_{p^{r}}(S_{0})$ to $\\{0,1,\ldots,a-1\\}$.
Since $T_{0}$ is inverse-closed in $\mathbb{Z}_{anp^{r}}$,
$T_{0}=\\{x+\beta(i)np^{r}:x\in\bar{g}_{p^{r}}(S_{0})\\}=T(\beta)$ is also
inverse-closed in $\mathbb{Z}_{anp^{r}}$ and hence $\beta$ is a feasible map.
By the definition of $\bar{f}_{a}$, we obtain that
$T_{0}\in\bar{f}_{a}(\bar{g}_{p^{r}}(S_{0}))$. Since this holds for any
$T_{0}\in(\bar{g}_{p^{r}}\bar{f}_{a})(S_{0})$, it follows that
$(\bar{g}_{p^{r}}\bar{f}_{a})(S_{0})\subseteq(\bar{f}_{a}\bar{g}_{p^{r}})(S_{0})$.

(d) Suppose that $p$ divides $a$. Every element of
$(\bar{g}_{p^{r}}\bar{f}_{a})(S_{0})$ is of the form
$X=\bar{g}_{p^{r}}(T(\sigma)_{0})$ for some
$T(\sigma)_{0}\in\bar{f}_{a}(S_{0})$, where $\sigma$ is a feasible map from
$S_{0}$ to $\\{0,1,\ldots,a-1\\}$ in $\mathbb{Z}_{an}$. So $X=\\{x+ian:x\in
T(\sigma)_{0},0\leq i\leq p^{r}-1\\}=\\{s+\sigma(s)n+ian:s\in S_{0},0\leq
i\leq p^{r}-1\\}$. Similarly, every element of
$(\bar{f}_{a}\bar{g}_{p^{r}})(S_{0})$ is of the form
$Y=\\{s+in+\tau(s+in)np^{r}:s\in S_{0},0\leq i\leq p^{r}-1\\}$ for some map
$\tau:\bar{g}_{p^{r}}(S_{0})\rightarrow\\{0,1,\ldots,a-1\\}$ satisfying
$\tau(0)=0$ and $-Y=Y$ in $\mathbb{Z}_{anp^{r}}$.

Set $A=\\{x:x\in X,x\equiv 0\pmod{n}\\}$ and $B=\\{y:y\in Y,y\equiv
0\pmod{n}\\}$. Then $|A|=|B|=p^{r}$. Since each $x\in A$ is divisible by $n$
and is of the form $x=s+\sigma(s)n+ian$, we have $x=0+\sigma(0)n+ian=ian$ for
some $0\leq i\leq p^{r}-1$. Similarly, each $y\in B$ is of the form
$y=0+in+\tau(0+in)np^{r}=in+\tau(in)np^{r}$ for some $0\leq i\leq p^{r}-1$. It
follows that there are elements $x\in A$ such that $x\neq 0$ and $x\equiv
0\pmod{anp^{r-1}}$. On the other hand, if an element $y\in B$ satisfies
$y\equiv 0\pmod{anp^{r-1}}$, then $y=in+\tau(in)np^{r}=kanp^{r-1}$ for some
integers $0\leq i\leq p^{r}-1$ and $k$, that is, $i+\tau(in)p^{r}=kap^{r-1}$.
Since $p$ is a divisor of $a$, we have $kap^{r-1}\equiv 0\pmod{p^{r}}$ and
hence $i\equiv 0\pmod{p^{r}}$. Since $0\leq i\leq p^{r}-1$, we must have $i=0$
and therefore $y=0+\tau(0)np^{r}=0$. Thus, there is no element $y\in B$ such
that $y\neq 0$ and $y\equiv 0\pmod{anp^{r-1}}$. Hence the number of elements
$x$ of $X$ satisfying $x\equiv 0\pmod{anp^{r-1}}$ differs from the number of
elements $y$ of $Y$ satisfying $y\equiv 0\pmod{anp^{r-1}}$. Therefore, $X\neq
Y$. Since this holds for any $X\in(\bar{g}_{p^{r}}\bar{f}_{a})(S_{0})$ and
$Y\in(\bar{f}_{a}\bar{g}_{p^{r}})(S_{0})$, we conclude that
$(\bar{g}_{p^{r}}\bar{f}_{a})(S_{0})\cap(\bar{f}_{a}\bar{g}_{p^{r}})(S_{0})=\emptyset$.

(e) Every element of $(\bar{g}_{p^{k}}\bar{f}_{a}\bar{g}_{p^{h}})(S_{0})$ is
of the form $X=\bar{g}_{p^{k}}(T(\sigma)_{0})$ for some
$T(\sigma)_{0}\in(\bar{f}_{a}\bar{g}_{p^{h}})(S_{0})$, where $\sigma$ is a
feasible map from $\bar{g}_{p^{h}}(S_{0})$ to $\\{0,1,\ldots,a-1\\}$ in
$\mathbb{Z}_{anp^{h}}$. So $X=\\{s+in+\sigma(s+in)np^{h}+janp^{h}:s\in
S_{0},0\leq i\leq p^{h}-1,0\leq j\leq p^{k}-1\\}$. Similarly, every element of
$(\bar{g}_{p^{k+c}}\bar{f}_{a}\bar{g}_{p^{h-c}})(S_{0})$ is of the form
$Y(\tau)=\\{s+in+\tau(s+in)np^{h-c}+janp^{h-c}:s\in S_{0},0\leq i\leq
p^{h-c}-1,0\leq j\leq p^{k+c}-1\\}$, where $\tau$ is a feasible map from
$\bar{g}_{p^{h-c}}(S_{0})$ to $\\{0,1,\ldots,a-1\\}$ with
$T(\tau)_{0}\in(\bar{f}_{a}\bar{g}_{p^{h-c}})(S_{0})$. Set $A=\\{x:x\in
X,x\equiv 0\pmod{n}\\}$ and $B=\\{y:y\in Y,y\equiv 0\pmod{n}\\}$. Then
$|A|=|B|=p^{h+k}$. We have $A=\\{in+\sigma(in)np^{h}+janp^{h}:0\leq i\leq
p^{h}-1,0\leq j\leq p^{k}-1\\}$ and $B=\\{in+\tau(in)np^{h-c}+janp^{h-c}:0\leq
i\leq p^{h-c}-1,0\leq j\leq p^{k+c}-1\\}$. Note that
$in+\sigma(in)np^{h}+janp^{h}\in A$ is divisible by $np^{h-c}$ if and only if
$i$ is divisible by $p^{h-c}$. Similarly, $in+\tau(in)np^{h-c}+janp^{h-c}\in
B$ is divisible by $np^{h-c}$ if and only if $i$ is divisible by $p^{h-c}$.
Assume $c>1$ first. Then there are exactly $\frac{p(p^{c}-1)}{p-1}p^{k}$
elements $x\in A$ satisfying $x\equiv 0\pmod{np^{h-c}}$, and there are exactly
$p^{k+c}$ elements $y\in B$ satisfying $y\equiv 0\pmod{np^{h-c}}$. Since $c>1$
and $p>1$, we have $\frac{p(p^{c}-1)}{p-1}p^{k}\neq p^{k+c}$ and therefore
$X\neq Y$. Since this holds for any
$X\in(\bar{g}_{p^{k}}\bar{f}_{a}\bar{g}_{p^{h}})(S_{0})$ and
$Y\in(\bar{g}_{p^{k+c}}\bar{f}_{a}\bar{g}_{p^{h-c}})(S_{0})$, it follows that
$(\bar{g}_{p^{k}}\bar{f}_{a}\bar{g}_{p^{h}})(S_{0})\cap(\bar{g}_{p^{k+c}}\bar{f}_{a}\bar{g}_{p^{h-c}})(S_{0})=\emptyset$.

Now assume $c=1$. Then there are exactly $p^{k}$ elements $x\in A$ satisfying
$x\equiv 0\pmod{np^{h}}$. Since $p$ is a divisor of $a$, for any $y\in B$,
$y\equiv 0\pmod{np^{h}}$ if and only if $in+\tau(in)np^{h-1}\equiv
0\pmod{np^{h}}$ for some $0\leq i\leq p^{h-1}-1$. Let $w$ be the number of
such integers $i$ satisfying $in+\tau(in)np^{h-1}\equiv 0\pmod{np^{h}}$. Then
there are exactly $wp^{k+1}$ elements $y\in B$ satisfying $y\equiv
0\pmod{np^{h}}$. Since $wp^{k+1}\neq p^{k}$, it follows that $X\neq Y$.
Therefore,
$(\bar{g}_{p^{k}}\bar{f}_{a}\bar{g}_{p^{h}})(S_{0})\cap(\bar{g}_{p^{k+c}}\bar{f}_{a}\bar{g}_{p^{h-c}})(S_{0})=\emptyset$.

(f) Assume $p$ is a divisor of $d$ and $d$ is a divisor of $a$. Then
$\bar{f}_{a}(S_{0})=\bar{f}_{d}\bar{f}_{a/d}(S_{0})$ by (a). Since $p$ is a
divisor of $d$, we have
$(\bar{g}_{p^{r}}\bar{f}_{d}\bar{f}_{a/d})(S_{0})\cap(\bar{f}_{d}\bar{g}_{p^{r}}\bar{f}_{a/d})(S_{0})=\emptyset$
by (d). This together with Lemma 4.9 yields
$(\bar{f}_{b}\bar{g}_{p^{r}}\bar{f}_{d}\bar{f}_{a/d})(S_{0})\cap(\bar{f}_{b}\bar{f}_{d}\bar{g}_{p^{r}}\bar{f}_{a/d})(S_{0})=\emptyset$.
By (a) again, we obtain
$(\bar{f}_{bd}\bar{g}_{p^{r}}\bar{f}_{a/d})(S_{0})\cap(\bar{f}_{b}\bar{g}_{p^{r}}\bar{f}_{a})(S_{0})=\emptyset$.
$\Box$

Now we are ready to prove Theorem 1.3. Set
$\sum_{\mathbf{a}}=\sum_{i=1}^{k}a_{i}$ and
$\prod_{\mathbf{a}}=\prod_{i=1}^{k}a_{i}$ for any sequence of positive
integers $\mathbf{a}=(a_{1},a_{2},\ldots,a_{k})$.

Proof of Theorem 1.3 Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq
1,m\geq 2$ are integers. We prove the statement in the theorem by induction on
$\ell$.

Consider the base case $\ell=1$ first. Let
$\Gamma=\mathrm{Cay}(\mathbb{Z}_{pm},S)$ be a connected circulant graph with
order $n=pm$ and degree $|S|=p-1$ which admits a perfect code. Then by [5,
Theorem 3.1], $H=\langle p\rangle$ is a perfect code of $\Gamma$. Since
$(S_{0}-S_{0})\cap H=\\{0\\}$, by Definition 4.1, $f_{m}(\Gamma)$ is well
defined. Moreover, $f_{m}(\Gamma)=K_{p}$ and
$\Gamma\in\bar{f}_{m}(f_{m}(\Gamma))=\bar{f}_{m}(K_{p})=\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p)$,
where $\mathbf{l}=(\ell_{1})$ with $\ell_{1}=1$ and $\mathbf{m}=(m_{1})$ with
$m_{1}=m$. Note that the only pair of sequences $\mathbf{l},\mathbf{m}$
satisfying $\sum_{\mathbf{l}}=1$ and $\prod_{\mathbf{m}}=m$ is
$\mathbf{l}=(\ell_{1})$ with $\ell_{1}=1$ and $\mathbf{m}=(m_{1})$ with
$m_{1}=m$. Note also that
$K_{p}=\mathrm{Cay}(\mathbb{Z}_{p},\mathbb{Z}_{p}\setminus\\{0\\})$ admits a
perfect code and $x-y\not\equiv 0\pmod{p}$ for any distinct elements
$x,y\in\mathbb{Z}_{p}\setminus\\{0\\}$. Thus, by Lemma 4.7(a), for any
$\mathrm{Cay}(\mathbb{Z}_{pm},S)\in\bar{f}_{m}(K_{p})=\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p)$,
we have $x-y\not\equiv 0\pmod{p}$ for distinct $x,y\in S_{0}$. Hence, by
Theorem 2.2, $\mathrm{Cay}(\mathbb{Z}_{pm},S)$ admits a perfect code. This
establishes the base case for induction.

Assume that for some integer $k\geq 2$ the result holds for any $\ell$ up to
$k-1$. We aim to prove that the result is also true for $\ell=k$. Let
$\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a connected circulant graph with
order $n=p^{k}m$ and degree $|S|=p^{k}-1$ which admits a perfect code. Let $D$
be a perfect code in $\Gamma$. Then by Lemma 2.7 either $D$ or $S_{0}$ is
periodic. Consider first the case when $S_{0}$ is aperiodic. In this case $D$
is periodic, say, with the subgroup of periods $H$ of order $d$ for some
divisor $d>1$ of $m$. Then $H=\langle n/d\rangle$ and
$\Sigma:=\mathrm{Cay}(\mathbb{Z}_{n}/H,(S_{0}/H)\setminus\\{H\\})$ is
isomorphic to some circulant graph $\mathrm{Cay}(\mathbb{Z}_{n/d},T)$ with
order $n/d$ and degree $|T|=p^{k}-1$. Since $D/H$ is aperiodic, $T_{0}$ is
periodic by Lemma 2.7. Let $K$ be the subgroup of periods of $T_{0}$. Then
$|K|=p^{h}$ for some $h\geq 1$, and
$\Delta:=\mathrm{Cay}(\mathbb{Z}_{p^{k-h}m/d},(T/K)\setminus\\{K\\})$ admits a
perfect code. Since $\Delta$ has degree $p^{k-h}-1<p^{k}-1$, by the induction
hypothesis we have
$\Delta\in\mathcal{G}_{\mathbf{l}_{1},\mathbf{m}_{1}}(p^{k-h}m/d,p^{k-h})$ for
some $\mathbf{l}_{1}=(\ell_{1},\ell_{2},\ldots,\ell_{t})$ and
$\mathbf{m}_{1}=(m_{1},m_{2},\ldots,m_{t})$ such that
$\sum_{\mathbf{l}_{1}}=k-h$ and $\prod_{\mathbf{m}_{1}}=m/d$. Note that
$\Delta=g_{p^{h}}(f_{d}(\Gamma))$ and hence
$\Gamma\in(\bar{f}_{d}\bar{g}_{p^{h}})(\Delta)$. Therefore,
$\Gamma\in\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{k})$ for
$\mathbf{l}=(h,\mathbf{l}_{1})=(h,\ell_{1},\ell_{2},\ldots,\ell_{t})$ and
$\mathbf{m}=(d,\mathbf{m}_{1})=(d,m_{1},m_{2},\ldots,m_{t})$. Now consider the
case when $S_{0}$ is periodic. In this case the subgroup of periods of $S_{0}$
is of the form $H=\langle p^{h}m\rangle$ for some $h\geq 1$. Since
$|S_{0}/H|=p^{k-h}<p^{k}$, we have
$g_{p^{h}}(\Gamma)\in\mathcal{G}_{\mathbf{l}_{2},\mathbf{m}_{2}}(p^{k-h}m,p^{k-h})$
for some $\mathbf{l}_{2}=(\ell_{1},\ell_{2},\ldots,\ell_{t})$ and
$\mathbf{m}_{2}=(m_{1},m_{2},\ldots,m_{t})$ with $\sum_{\mathbf{l}_{2}}=k-h$
and $\prod_{\mathbf{m}_{2}}=m$. Therefore,
$\Gamma\in\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{k})$ for
$\mathbf{l}=(h,\mathbf{l}_{2})=(h,\ell_{1},\ell_{2},\ldots,\ell_{t})$ and
$\mathbf{m}=(1,\mathbf{m}_{2})=(1,m_{1},m_{2},\ldots,m_{t})$.

Now we prove that for any $\mathbf{l}=(\ell_{1},\ell_{2},\ldots,\ell_{t})$ and
$\mathbf{m}=(m_{1},m_{2},\ldots,m_{t})$ with $\sum_{\mathbf{l}}=k$ and
$\prod_{\mathbf{m}}=m$, any
$\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)\in\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{k})$
admits a perfect code. Since
$\Gamma\in\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{k})$, there exist integers
$\ell_{1},m_{1}$ and a circulant graph $\Sigma$ with degree $p^{k-\ell_{1}}$
such that $\Gamma\in\bar{f}_{m_{1}}\bar{g}_{p^{\ell_{1}}}(\Sigma)$. By the
induction hypothesis, we may assume that
$\Sigma=\mathrm{Cay}(\mathbb{Z}_{p^{k-\ell_{1}}m/m_{1}},T)\in\mathcal{G}_{\mathbf{l^{\prime}},\mathbf{m^{\prime}}}(p^{k-\ell_{1}}m/m_{1},p^{k-\ell_{1}})$
and that $\Sigma$ admits a perfect code, where
$\mathbf{l^{\prime}}=(\ell_{2},\ell_{3},\ldots,\ell_{t})$ and
$\mathbf{m^{\prime}}=(m_{2},m_{3},\ldots,m_{t})$. We claim that any perfect
code $D\subset\mathbb{Z}_{p^{k-\ell_{1}}m/m_{1}}$ in $\Sigma$ is also a
perfect code in $\bar{g}_{p^{\ell_{1}}}(\Sigma)$. In fact,
$\bar{g}_{p^{\ell_{1}}}(\Sigma)=\mathrm{Cay}(\mathbb{Z}_{n/m_{1}},R)$, where
$R=\\{w+i\mathbb{Z}_{p^{k-\ell_{1}}m/m_{1}}:w\in T_{0},0\leq i\leq
p^{\ell_{1}}\\}$. For any two distinct vertices $u,v\in D$, if $u$ is adjacent
to $v$ in $\bar{g}_{p^{\ell_{1}}}(\Sigma)$, then there exist $w\in T$ and
$i\in\mathbb{Z}_{p^{\ell_{1}}}$ such that $u-v=w+(ip^{k-\ell_{1}}m/m_{1})$. So
$u-v=w\in T$ or $v-u=w\in T$ as $u,v\in\mathbb{Z}_{p^{k-\ell_{1}}m/m_{1}}$,
but this means that $D$ is not an independent set of $\Sigma$, a
contradiction. Thus, $D$ must be an independent set of
$\bar{g}_{p^{\ell_{1}}}(\Sigma)$. For any vertex $x$ of
$\bar{g}_{p^{\ell_{1}}}(\Sigma)$ outside $D$, there exists $i$ between $0$ and
$p^{\ell_{1}}-1$ such that $x=u+(ip^{k-\ell_{1}}m/m_{1})$ for some
$u\in\mathbb{Z}_{p^{k-\ell_{1}}m/m_{1}}$. So $u$ is adjacent to a unique
vertex $v$ in $D$ and $x$ is adjacent to $v$ due to the form of $R$. Hence $D$
is a perfect code in $\bar{g}_{p^{\ell_{1}}}(\Sigma)$ as claimed. Moreover, we
have $\mathbb{Z}_{n/m_{1}}=R_{0}\oplus D$. Since $(S_{0}-S_{0})\cap\langle
n/m_{1}\rangle=\\{0\\}$, by Lemmas 2.4 and 2.6 we have
$\mathbb{Z}_{n}=S_{0}\oplus(D+\langle n/m_{1}\rangle)$ and hence $\Gamma$
admits $D+\langle n/m_{1}\rangle$ as a perfect code.

Up to now we have proved that based on the induction hypothesis the result is
true for $\ell=k$. This completes the proof of the theorem by mathematical
induction. $\Box$

##  5 Proof of Theorem 1.4

As a preparation for the proof of Theorem 1.4, we now construct a special
admissible subgroup series of $\mathbb{Z}_{n}$ associated with a pyramidal
extended connection set $S_{0}$. We will soon see that this series is the
unique longest admissible subgroup series of $\mathbb{Z}_{n}$ associated with
$S_{0}$.

######  Construction 5.1.

Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq 1,m\geq 2$ are integers.
Let $S$ be a connection set of $\mathbb{Z}_{n}$ with $|S|=p^{\ell}-1$ such
that $S_{0}$ is pyramidal. We now construct a special admissible subgroup
series

$\iota(S_{0}):H_{0}<H_{1}<\cdots<H_{2t-1}\leq H_{2t}=\mathbb{Z}_{n}$ (8)

associated with $S_{0}$ together with two sequences of nonnegative integers

$\mathbf{h}(S_{0}):=(h_{0},h_{1},\ldots,h_{t-1},h_{t}),\;\mathbf{k}(S_{0}):=(k_{0},k_{1},\ldots,k_{t-1},k_{t})$
(9)

such that the following hold:

(i) $H_{2i-1}=\langle p^{h_{i-1}}k_{i}\rangle$ and $H_{2i}=\langle
p^{h_{i}}k_{i}\rangle$ for $1\leq i\leq t$;

(ii) $k_{0}=m$, $k_{t}=1$, and $k_{i}$ is a divisor of $k_{i-1}$ for $1\leq
i\leq t$;

(iii) if $S_{0}$ is aperiodic, then $0=h_{t}<h_{t-1}<\cdots<h_{1}<h_{0}=\ell$;

(iv) if $S_{0}$ is periodic, then $0=h_{t}<h_{t-1}<\cdots<h_{1}<h_{0}<\ell$;

(v) the sequences $\mathbf{l}_{\iota(S_{0})}$ and $\mathbf{m}_{\iota(S_{0})}$
defined in (6) are related to $\mathbf{h}(S_{0})$ and $\mathbf{k}(S_{0})$ by

$\ell_{i}=h_{i}-h_{i-1},\;m_{i}=k_{i-1}/k_{i},\;1\leq i\leq t.$

First, let $k_{0}=m$. If $S_{0}$ is aperiodic, then let $h_{0}=\ell$; if
$S_{0}$ is periodic, then let $1\leq h_{0}<\ell$ be such that $\langle
p^{h_{0}}k_{0}\rangle$ is the subgroup of periods of $S_{0}$, where $h_{0}$
and $k_{0}$ are positive integers such that $\langle p^{h_{0}}k_{0}\rangle$ is
the subgroup of periods of $S_{0}$. Set $H_{0}:=\langle
p^{h_{0}}k_{0}\rangle$. Since $S_{0}$ is a pyramidal set, by Theorem 1.2,
$\mathrm{Cay}(\mathbb{Z}_{n},S)$ admits a perfect code, say, $D$. Hence
$\mathbb{Z}_{n}=S_{0}\oplus D$. Since $S_{0}/H_{0}$ is aperiodic and
$|S_{0}/H_{0}|=p^{h_{0}}$, $D/H_{0}$ is periodic in $\mathbb{Z}_{n}/H_{0}$. So
there is a subgroup $H_{1}/H_{0}$ of $\mathbb{Z}_{n}/H_{0}$ such that
$(S_{0}/H_{0}-S_{0}/H_{0})\cap(H_{1}/H_{0})=\\{0\\}$ and $S_{0}/H_{1}$ is
periodic in $\mathbb{Z}_{n}/H_{1}$. Since
$(S_{0}/H_{0}-S_{0}/H_{0})\cap(H_{1}/H_{0})=\\{0\\}$, we have
$|S_{0}/H_{0}|=|S_{0}/H_{1}|$. Note that $|D/H_{0}|=m$ and $H_{1}/H_{0}$ is
the subgroup of periods of $D/H_{0}$. Hence $|H_{1}|$ is a divisor of $m$ and
so there is an integer $k_{1}$ such that $H_{1}=\langle
p^{h_{0}}k_{1}\rangle$. Let $H_{2}/H_{1}$ be the subgroup of periods of
$S_{0}/H_{1}$ in $\mathbb{Z}_{n}/H_{1}$, where $H_{2}$ is a subgroup of
$\mathbb{Z}_{n}$ which contains $H_{1}$ as a proper subgroup. This defines
$H_{2}$ uniquely, and moreover $H_{2}=\langle p^{h_{1}}k_{1}\rangle$ for some
$h_{1}<h_{0}$.

Inductively, assume that for some $i\geq 1$ we have constructed
$H_{0},H_{1},H_{2},\ldots,H_{2i-1},H_{2i}$ together with
$h_{0},h_{1},\ldots,h_{i}$ and $k_{0},k_{1},\ldots,k_{i}$ such that
$H_{2j}=\langle p^{h_{j}}k_{j}\rangle$ and $H_{2j-1}=\langle
p^{h_{j-1}}k_{j}\rangle$ for $1\leq j\leq i$. If $H_{2i}=\mathbb{Z}_{n}$, then
set $t=i$ and stop. If $H_{2i}<\mathbb{Z}_{n}$, then similarly to the proof
above we can show that there exists a positive integer $k_{i+1}$ which is a
proper divisor of $k_{i}$ such that $H_{2i+1}:=\langle
p^{h_{i}}k_{i+1}\rangle$ has the following properties:
$(S_{0}/H_{2i}-S_{0}/H_{2i})\cap(H_{2i+1}/H_{2i})=\\{0\\}$, $S_{0}/H_{2i+1}$
is periodic, and $|S_{0}/H_{2i}|=|S_{0}/H_{2i+1}|$. Let $H_{2i+2}/H_{2i+1}$ be
the subgroup of periods of $S_{0}/H_{2i+1}$ in $\mathbb{Z}_{n}/H_{2i+1}$,
where $H_{2i+2}$ is a subgroup of $\mathbb{Z}_{n}$ which contains $H_{2i+1}$
as a proper subgroup. This defines $H_{2i+2}$ uniquely, and moreover
$H_{2i+2}=\langle p^{h_{i+1}}k_{i+1}\rangle$ for some $h_{i+1}<h_{i}$.

Continuing the process, we can eventually construct an admissible subgroup
series (8) associated with $S_{0}$ and two sequences (9) such that all (i)–(v)
are respected. In fact, by the construction we see that (i)–(iv) are
satisfied. Also, by (i) and (7) we obtain that for $1\leq i\leq t$, $|\langle
p^{h_{i}}k_{i}\rangle/\langle
p^{h_{i-1}}k_{i}\rangle|=p^{h_{i-1}-h_{i}}=p^{\ell_{i}}$ and $|\langle
p^{h_{i-1}}k_{i}\rangle/\langle
p^{h_{i-1}}k_{i-1}\rangle|=k_{i-1}/k_{i}=m_{i}$, and hence (v) is satisfied as
well. $\Box$

######  Lemma 5.2.

With the notation in Construction 5.1, the special admissible subgroup series
$\iota(S_{0})$ as given in (8) is the unique longest admissible subgroup
series of $\mathbb{Z}_{n}$ associated with $S_{0}$.

###### Proof.

We use the notation in Construction 5.1. We first prove that $\iota(S_{0})$ is
an admissible subgroup series of $\mathbb{Z}_{n}$ associated with $S_{0}$.
Consider the case when $S_{0}$ is aperiodic first. In this case, by
Construction 5.1, we have $H_{0}=\langle p^{h_{0}}k_{0}\rangle=\\{0\\}$, and
$(S_{0}/H_{2i}-S_{0}/H_{2i})\cap(H_{2i+1}/H_{2i})=\\{0\\}$,
$|S_{0}/H_{2i}|=|S_{0}/H_{2i+1}|$ and $S_{0}/H_{2i+1}$ is
$(H_{2i+2}/H_{2i+1})$-periodic for $1\leq i\leq t$. Since
$H_{2t}=\mathbb{Z}_{n}$, $S_{0}/H_{2t-1}$ is
$(\mathbb{Z}_{n}/H_{2t-1})$-periodic and $S_{0}\subseteq\mathbb{Z}_{n}$, we
have $|S_{0}/H_{2t-1}|=|\mathbb{Z}_{n}/H_{2t-1}|$ and hence $\iota(S_{0})$ is
an admissible subgroup series of $\mathbb{Z}_{n}$. In the case when $S_{0}$ is
periodic, the proof is essentially the same as in the aperiodic case with
$\mathbb{Z}_{n}/H_{0}$ and $S_{0}/H_{0}$ playing the role of $\mathbb{Z}_{n}$
and $S_{0}$, respectively.

Now we prove that $\iota(S_{0})$ is the unique longest admissible subgroup
series of $\mathbb{Z}_{n}$ associated with $S_{0}$. To achieve this it
suffices to prove that any admissible subgroup series

$\iota^{\prime}:L_{0}<L_{1}<\cdots<L_{2r-1}\leq L_{2r}=\mathbb{Z}_{n}$

of $\mathbb{Z}_{n}$ associated with $S_{0}$ such that $r\geq t$ must be equal
to $\iota(S_{0})$. In fact, we may write $L_{2i-1}=\langle
p^{x_{i-1}}y_{i}\rangle$ and $L_{2i}=\langle p^{x_{i}}y_{i}\rangle$ for $1\leq
i\leq r$, so that $\iota^{\prime}$ is determined by the sequences
$\mathbf{x}:=(x_{0},x_{1},\ldots,x_{r-1},x_{r})$ and
$\mathbf{y}:=(y_{0},y_{1},\ldots,y_{r-1},y_{r})$. Note that $H_{0}=L_{0}$
regardless of whether $S_{0}$ is periodic or aperiodic. Set
$\alpha_{0}=h_{0}-h_{1}$, $\beta_{0}=k_{0}/k_{1}$, $\alpha_{1}=x_{0}-x_{1}$
and $\beta_{1}=y_{0}/y_{1}$. Since there are circulant graphs
$\mathrm{Cay}(\mathbb{Z}_{p^{h_{1}}k_{1}},T)$ and
$\mathrm{Cay}(\mathbb{Z}_{p^{x_{1}}y_{1}},T^{\prime})$ such that
$g_{p^{\alpha_{0}}}f_{\beta_{0}}(\Gamma)\cong\mathrm{Cay}(\mathbb{Z}_{p^{h_{1}}k_{1}},T)$
and
$g_{p^{\alpha_{1}}}f_{\beta_{1}}(\Gamma)\cong\mathrm{Cay}(\mathbb{Z}_{p^{x_{1}}y_{1}},T^{\prime})$,
$S_{0}$ is a member of $\bar{f}_{\beta_{0}}(\bar{g}_{p^{\alpha_{0}}}(T_{0}))$
and $\Gamma$ is a member of
$\bar{f}_{\beta_{1}}(\bar{g}_{p^{\alpha_{1}}}(T^{\prime}_{0}))$. By the
definitions of $\bar{f}_{m}$ and $\bar{g}_{m}$, there are feasible
$\sigma,\tau$ such that
$S_{0}=\\{t+ip^{h_{1}}k_{1}+\sigma(t+ip^{h_{1}}k_{1})p^{h_{0}}k_{1}:1\leq
i\leq p^{\alpha_{0}}-1,t\in T_{0}\\}$ and
$S_{0}=\\{t^{\prime}+ip^{x_{1}}y_{1}+\tau(t^{\prime}+ip^{x_{1}}y_{1})p^{x_{0}}y_{1}:1\leq
i\leq p^{\alpha_{1}}-1,t^{\prime}\in T_{0}\\}$. Since
$s=p^{h_{1}}k_{1}+\sigma(p^{h_{1}}k_{1})p^{h_{0}}k_{1}\in S_{0}$, there exist
$t^{\prime}\in T^{\prime}$ and $0\leq i\leq p^{\alpha_{1}}-1$ such that
$s=t^{\prime}+ip^{x_{1}}y_{1}+\tau(t^{\prime}+ip^{x_{1}}y_{1})p^{x_{0}}y_{1}$.
Hence
$p^{h_{1}}k_{1}-t^{\prime}-ip^{x_{1}}y_{1}=\tau(t^{\prime}+ip^{x_{1}}y_{1})p^{x_{0}}y_{1}-\sigma(p^{h_{1}}k_{1})p^{h_{0}}k_{1}$.
Since $\bar{g}_{p^{\alpha_{0}}}(T_{0})$ is a subset of
$\mathbb{Z}_{p^{h_{0}}k_{1}}$, we have
$-p^{h_{1}}k_{1}=p^{h_{0}}k_{1}-p^{h_{1}}k_{1}$. Similarly,
$-(t^{\prime}+ip^{x_{1}}y_{1})=p^{x_{0}}y_{1}-(t^{\prime}+ip^{x_{1}}y_{1})$.
Hence
$p^{h_{0}}k_{1}-p^{h_{1}}k_{1}-\sigma(p^{h_{1}}k_{1})p^{h_{0}}k_{1}=p^{x_{0}}y_{1}-(t^{\prime}+ip^{x_{1}}y_{1})-\tau(t^{\prime}+ip^{x_{1}}y_{1})p^{x_{0}}y_{1}$.
That is,
$p^{h_{0}}k_{1}-p^{x_{0}}y_{1}=p^{h_{1}}k_{1}-(t^{\prime}+ip^{x_{1}}y_{1})-\tau(t^{\prime}+ip^{x_{1}}y_{1})p^{x_{0}}y_{1}+\sigma(p^{h_{1}}k_{1})p^{h_{0}}k_{1}$.
Combining this with
$p^{h_{1}}k_{1}-t^{\prime}-ip^{x_{1}}y_{1}=\tau(t^{\prime}+ip^{x_{1}}y_{1})p^{x_{0}}y_{1}-\sigma(p^{h_{1}}k_{1})p^{h_{0}}k_{1}$,
we obtain that $p^{h_{0}}k_{1}=p^{x_{0}}y_{1}=0$. Since $h_{0}=x_{0}=\ell$, it
follows that $y_{1}=k_{1}$. So we have proved $y_{1}=k_{1}$, which implies
$H_{1}=L_{1}$. Since $S_{0}/H_{1}$ is $(H_{2}/H_{1})$-periodic, we then obtain
$H_{2}=L_{2}$ and so $x_{1}=h_{1}$. Let $i$ be the largest integer between $1$
and $t$ such that $H_{2j-1}=L_{2j-1}$, $H_{2j}=L_{2j}$, $x_{j}=h_{j}$ and
$y_{j}=k_{j}$ for $1\leq j\leq i$. (Note that $i$ is well defined as
$H_{1}=L_{1}$, $H_{2}=L_{2}$, $x_{1}=h_{1}$ and $y_{1}=k_{1}$.) We claim that
$i=t$. Suppose otherwise. Then $i<t\leq r$. Consider the subgroup series
$H_{2i}/H_{2i}<H_{2i+1}/H_{2i}<\cdots<H_{2t}/H_{2i}=\mathbb{Z}_{n}/H_{2i}$ and
$L_{2i}/L_{2i}<L_{2i+1}/L_{2i}<\cdots<L_{2r}/L_{2i}=\mathbb{Z}_{n}/L_{2i}$.
Let $H^{\prime}_{j-2i}=H_{j}/H_{2i}$ for $2i\leq j\leq 2t$ and
$L^{\prime}_{j-2i}=L_{j}/L_{2i}$ for $2i\leq j\leq 2r$. Then we have two
subgroup series
$H^{\prime}_{0}<H^{\prime}_{1}<\cdots<H^{\prime}_{2t-2i}=\mathbb{Z}_{n}/H_{2i}$
and
$L^{\prime}_{0}<L^{\prime}_{1}<\cdots<L^{\prime}_{2r-2i}=\mathbb{Z}_{n}/L_{2i}$.
Since $H_{2i}=L_{2i}$, we have $S_{0}/H_{2i}=S_{0}/L_{2i}$. Set
$S^{\prime}_{0}=S_{0}/H_{2i}=S_{0}/L_{2i}$. Similarly to the above proof
leading to $y_{1}=k_{1}$ and $H_{1}=L_{1}$, we can show that
$H^{\prime}_{1}=L^{\prime}_{1}$. That is, $H_{2i+1}/H_{2i}=L_{2i+1}/L_{2i}$.
So $H_{2i+1}=L_{2i+1}$ and $y_{i+1}=k_{i+1}$. Since
$S_{0}/H^{\prime}_{1}=S_{0}/L^{\prime}_{1}$ is
$(H^{\prime}_{2}/H^{\prime}_{1})$-periodic and
$S_{0}/H^{\prime}_{1}=S_{0}/L^{\prime}_{1}$ is
$(L^{\prime}_{2}/L^{\prime}_{1})$-periodic, from
$H^{\prime}_{1}=L^{\prime}_{1}$ we obtain $H^{\prime}_{2}=L^{\prime}_{2}$ and
$H_{2i+2}=L_{2i+2}$ as $H_{2i}=L_{2i}$. Hence $x_{i+1}=h_{i+1}$, but this
contradicts the choice of $i$. So we must have $i=t$, which forces $t=r$ and
$\iota^{\prime}=\iota(S_{0})$ as desired. $\Box$

######  Construction 5.3.

Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq 1,m\geq 2$ are integers.
Let $\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a connected circulant graph with order
$n$ and degree $p^{\ell}-1$ such that $S_{0}$ is pyramidal. Let
$\iota(S_{0}):H_{0}<H_{1}<\cdots<H_{2t-1}\leq H_{2t}=\mathbb{Z}_{n}$ be the
longest admissible subgroup series of $\mathbb{Z}_{n}$ associated with $S_{0}$
(see (8)) and $\mathbf{h}(S_{0})=(h_{0},h_{1},\ldots,h_{t-1},h_{t})$ and
$\mathbf{k}(S_{0})=(k_{0},k_{1},\ldots,k_{t-1},k_{t})$ the corresponding
sequences (see (9)). Let

$J_{i}:=\\{jp^{h_{t-i-1}}k_{t-i}:0\leq j\leq(k_{t-i-1}/k_{t-i})-1\\},\;\,1\leq
i\leq t-1.$

Set

$D_{0}:=\\{jp^{h_{t-1}}:0\leq j\leq k_{t-1}-1\\}$

and

$D_{2i-1}:=\\{x+\tau_{i}(x):x\in
D_{2i-2}\\},\,D_{2i}:=D_{2i-1}+J_{i},\;\,1\leq i\leq t-1,$ (10)

where $\tau_{i}$ is a map from $D_{2i-2}$ to
$p^{h_{t-i}}k_{t-i}\mathbb{Z}_{p^{h_{t-i-1}-h_{t-i}}}$ satisfying
$\tau_{i}(0)=0$. Note that for $1\leq i\leq t-1$,
$|D_{2i-1}|=|D_{2i-2}|=k_{t-i}$ and both $D_{2i-1}$ and $D_{2i}$ depend on
$D_{2i-2}$ and the choice of $\tau_{i}$. In addition, if $S_{0}$ is periodic
with subgroup of periods $\langle p^{h_{0}}k_{0}\rangle$, then set
$D_{2t-1}=\\{x+\tau(x):x\in D_{2t-2}\\}$, where $\tau$ is a map from
$D_{2t-2}$ to $p^{h_{0}}k_{0}\mathbb{Z}_{p^{\ell-h_{0}}}$ satisfying
$\tau(0)=0$.

Note that both $D_{2t-2}$ and $D_{2t-1}$ contain $0$. Note also that
$D_{2t-2}$ depends on $(\tau_{1},\ldots,\tau_{t-1})$ and $D_{2t-1}$ depends on
$(\tau_{1},\ldots,\tau_{t-1},\tau)$. $\Box$

######  Lemma 5.4.

Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq 1,m\geq 2$ are integers.
Let $\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a connected circulant graph
with order $n$ and degree $p^{\ell}-1$ such that $S_{0}$ is pyramidal. Let
$2t$ be the length of the longest admissible subgroup series of
$\mathbb{Z}_{n}$ associated with $S_{0}$. The the following hold:

  * (a)

if $S_{0}$ is aperiodic, then $D_{2t-2}$ is a perfect code in $\Gamma$; these
perfect codes $D_{2t-2}$ are different for different choices of
$(\tau_{1},\ldots,\tau_{t-1})$;

  * (b)

if $S_{0}$ is periodic, then $D_{2t-1}$ is a perfect code in $\Gamma$; these
perfect codes $D_{2t-1}$ are different for different choices of
$(\tau_{1},\ldots,\tau_{t-1},\tau)$.

###### Proof.

We use the notation in Construction 5.3 and set
$\Gamma_{i}=\mathrm{Cay}(\mathbb{Z}_{n}/H_{i},(S_{0}/H_{i})\setminus\\{H_{i}\\})$,
where $H_{i}$ is obtained from Construction 5.1, for $0\leq i\leq 2t$.

We prove the first statements in (a) and (b) by induction on $t$. Consider the
base case $t=1$ first. If $S_{0}$ is aperiodic, then $H_{0}=\\{0\\}$ and by
(T3), $\Gamma_{1}$ is a complete graph and $0+H_{1}$ is a perfect code in
$\Gamma_{1}$. By (T1) and Lemma 2.4, $H_{1}$ is the unique prefect code in
$\Gamma$ containing $0$. Note that
$H_{1}=\\{0,p^{h_{0}},\ldots,(m-1)p^{h_{0}}\\}=D_{0}$. Hence $D_{0}$ is the
unique perfect code in $\Gamma$ containing $0$. Now assume $S_{0}$ is
$H_{0}$-periodic. Then $H_{0}\neq\\{0\\}$ and $\Gamma_{1}$ is a circulant
graph whose extended connection set $S_{0}/H_{1}$ is an aperiodic pyramidal
set of $\mathbb{Z}_{n}/H_{1}$. Applying what we just proved to $\Gamma_{1}$,
we obtain that $D_{0}$ is the unique perfect code in $\Gamma_{1}$ containing
$0$. Moreover, $D_{0}=\\{0,p^{h_{0}},\ldots,(m-1)p^{h_{0}}\\}$. Since
$\Gamma\cong\Gamma_{0}\otimes\mathrm{Cay}(\mathbb{Z}_{p^{\ell-
h_{0}}},\mathbb{Z}_{p^{\ell-h_{0}}}\setminus\\{0\\})$, by the definition of
the wreath product we see that $D_{1}=\\{x+\tau_{1}(x):x\in D_{0}\\}$ is a
perfect code in $\Gamma$ containing $0$, where $\tau_{1}$ is a map from
$D_{0}$ to $p^{h_{0}}k_{0}\mathbb{Z}_{p^{\ell-h_{0}}}$ satisfying
$\tau_{1}(0)=0$. Since $D_{0}$ is the unique perfect code in $\Gamma_{0}$
containing $0$, by the definition of the wreath product, all perfect codes in
$\Gamma$ containing $0$ can be obtained by different choices of $\tau_{1}$. So
each perfect code in $\Gamma$ containing $0$ can be constructed from $D_{1}$.
This establishes the result in the base case $t=1$.

Suppose that the result is true when $t<l$ for some $l\geq 2$. Consider the
case when $t=l$. Assume $S_{0}$ is aperiodic first. Then $\Gamma_{2}$ is a
circulant graph whose extended connection set $T_{0}:=S_{0}/H_{2}$ is an
aperiodic pyramidal set of $\mathbb{Z}_{n}/H_{2}$. It can be verified that the
longest admissible subgroup series associated with $T_{0}$ is
$\iota(T_{0}):H_{2}/H_{2}<H_{3}/H_{2}<\cdots<H_{2l}/H_{2}=\mathbb{Z}_{n}/H_{2}$
and the corresponding sequences are
$\mathbf{h}(T_{0})=(a_{0},a_{1},\ldots,a_{l-1})$ and
$\mathbf{k}(T_{0})=(b_{0},b_{1},\ldots,b_{l-1})$, where
$a_{i}=h_{i+1},b_{i}=k_{i+1}$ for $0\leq i\leq l-1$. By our hypothesis,
$D_{2l-4}$ is a perfect code in $\Gamma_{2}$ containing $0$. Since
$\Gamma_{1}\cong\Gamma_{2}\otimes\mathrm{Cay}(\mathbb{Z}_{p^{h_{0}-h_{1}}},\mathbb{Z}_{p^{h_{0}-h_{1}}}\setminus\\{0\\})$,
$D_{2l-3}=\\{x+\tau_{l-1}(x):x\in D_{2l-4}\\}$ (see (10)) is a perfect code in
$\Gamma_{1}$ containing $0$, where $\tau_{l-1}$ is a map from $D_{2l-4}$ to
$p^{h_{1}}k_{1}\mathbb{Z}_{p^{h_{0}-h_{1}}}$ satisfying $\tau_{l-1}(0)=0$. By
(T1) and Lemma 2.4, $D_{2l-3}$ gives rise to a unique perfect code in $\Gamma$
containing $0$, namely
$D_{2l-2}=D_{2l-3}+J_{l-1}=D_{2l-3}+\\{jp^{h_{0}}k_{1}:0\leq
j\leq(k_{0}/k_{1})-1\\}$.

Now assume $S_{0}$ is periodic. Then $\Gamma_{0}$ is a connected circulant
graph whose extended connection set $S_{0}/H_{0}$ is an aperiodic pyramidal
set of $\mathbb{Z}_{n}/H_{0}$. By our hypothesis, $D_{2l-2}$ is a perfect code
in $\Gamma_{0}$. Since
$\Gamma\cong\Gamma_{0}\otimes\mathrm{Cay}(\mathbb{Z}_{p^{\ell-
h_{0}}},\mathbb{Z}_{p^{\ell-h_{0}}}\setminus\\{0\\})$, by the definition of
the wreath product, $D_{2l-1}=\\{x+\tau(x):x\in D_{2l-2}\\}$ is a perfect code
in $\Gamma$ containing $0$, where $\tau$ is a map from $D_{2l-2}$ to
$p^{h_{0}}k_{0}\mathbb{Z}_{p^{\ell-h_{0}}}$. By mathematical induction, we
have completed the proof of the first statements in (a) and (b).

Next, we prove the second statement in (a). Assume $S_{0}$ is aperiodic. Let
$D_{2t-2}$ and $D^{\prime}_{2t-2}$ be perfect codes in $\Gamma$ obtained from
$(\tau_{1},\ldots,\tau_{t-1})$ and
$(\tau^{\prime}_{1},\ldots,\tau^{\prime}_{t-1})$, respectively. It suffices to
prove that $D_{2t-2}=D^{\prime}_{2t-2}$ implies
$(\tau_{1},\ldots,\tau_{t-1})=(\tau^{\prime}_{1},\ldots,\tau^{\prime}_{t-1})$.
Note that, for $0<2i-1\leq 2t-1$ and $x\in D_{2i-1}$ we have $0\leq x\leq
p^{h_{t-i-1}}k_{t-i}-p^{h_{t-1}}$, and for $0\leq 2i<2t-1$ and $x\in D_{2i}$
we have $0\leq x\leq p^{h_{t-i-1}}k_{t-i-1}-p^{h_{t-1}}$. Note also that
$D_{2t-2}=D_{2t-3}+J_{t-1}=\\{x+jp^{h_{0}}k_{1}:x\in D_{2t-3},0\leq
j\leq(k_{0}/k_{1})-1\\}$ and
$D^{\prime}_{2t-2}=D^{\prime}_{2t-3}+J_{t-1}=\\{x+jp^{h_{0}}k_{1}:x\in
D^{\prime}_{2t-3},0\leq j\leq(k_{0}/k_{1})-1\\}$. Suppose that
$D_{2t-2}=D^{\prime}_{2t-2}$. Then for each $x+j_{1}p^{h_{0}}k_{1}\in
D_{2t-2}$ there exists $y+j_{2}p^{h_{0}}k_{1}\in D^{\prime}_{2t-2}$ such that
$x+j_{1}p^{h_{0}}k_{1}=y+j_{2}p^{h_{0}}k_{1}$. Since $0\leq x,y\leq
p^{h_{0}}k_{1}-p^{h_{t-1}}$, we have $-p^{h_{0}}k_{1}<x-y<p^{h_{0}}k_{1}$.
Thus $x+j_{1}p^{h_{0}}k_{1}=y+j_{2}p^{h_{0}}k_{1}$ (that is,
$x-y=(j_{2}-j_{1})p^{h_{0}}k_{1}$) if and only if $x=y$ and $j_{1}=j_{2}$.
Meanwhile, we also obtain $D_{2t-3}=D^{\prime}_{2t-3}$. Since
$D_{2t-3}=\\{x+\tau_{t-1}(x):x\in D_{2t-4}\\}$ and
$D^{\prime}_{2t-3}=\\{y+\tau^{\prime}_{t-1}(y):y\in D^{\prime}_{2t-4}\\}$,
this means that for each $x+\tau_{t-1}(x)\in D_{2t-3}$ there exists
$y+\tau^{\prime}_{t-1}(y)\in D^{\prime}_{2t-3}$ such that
$x+\tau_{t-1}(x)=y+\tau^{\prime}_{t-1}(y)$. Since $0\leq x,y\leq
p^{h_{1}}k_{1}-p^{h_{t-1}}$, we have $-p^{h_{1}}k_{1}<x-y<p^{h_{1}}k_{1}$. On
the other hand, $\tau^{\prime}_{t-1}(y)-\tau_{t-1}(x)$ is a multiple of
$p^{h_{1}}k_{1}$ as both $\tau_{t-1}$ and $\tau^{\prime}_{t-1}$ are maps from
$D_{2t-4}$ to $p^{h_{1}}k_{1}\mathbb{Z}_{p^{h_{2}}-h_{1}}$. Hence
$x+\tau_{t-1}(x)=y+\tau^{\prime}_{t-1}(y)$ (that is,
$x-y=\tau^{\prime}_{t-1}(y)-\tau_{t-1}(x)$) if and only if $x=y$ and
$\tau_{t-1}(x)=\tau^{\prime}_{t-1}(y)$. By the arbitrariness of $x\in
D_{2t-4}$, it follows that $D_{2t-4}=D^{\prime}_{2t-4}$ and
$\tau_{t-1}=\tau^{\prime}_{t-1}$. In the same vein as the proof that
$D_{2t-2}=D^{\prime}_{2t-2}$ implies $D_{2t-3}=D^{\prime}_{2t-3}$, we can
prove that $D_{2t-4}=D^{\prime}_{2t-4}$ implies $D_{2t-5}=D^{\prime}_{2t-5}$.
Similarly to the proof that $D_{2t-3}=D^{\prime}_{2t-3}$ implies
$D_{2t-4}=D^{\prime}_{2t-4}$ and $\tau_{t-1}=\tau^{\prime}_{t-1}$, we can
prove that $D_{2t-5}=D^{\prime}_{2t-5}$ implies $D_{2t-6}=D^{\prime}_{2t-6}$
and $\tau_{t-2}=\tau^{\prime}_{t-2}$. By induction, we can prove that
$D_{i}=D_{i}$ for $1\leq i\leq 2t-2$ and $\tau_{i}=\tau^{\prime}_{i}$ for
$1\leq i\leq t-1$. This proves the second statement in (a).

Finally, we prove the second statement in (b). Assume $S_{0}$ is periodic. Let
$D_{2t-1}$ and $D^{\prime}_{2t-1}$ be perfect codes in $\Gamma$ obtained from
$(\tau_{1},\ldots,\tau_{t-1},\tau)$ and
$(\tau^{\prime}_{1},\ldots,\tau^{\prime}_{t-1},\tau^{\prime})$, respectively.
It suffices to prove that $D_{2t-1}=D^{\prime}_{2t-1}$ implies
$(\tau_{1},\ldots,\tau_{t-1},\tau)=(\tau^{\prime}_{1},\ldots,\tau^{\prime}_{t-1},\tau^{\prime})$.
In fact, since $\\{x+\tau(x):x\in
D_{2t-2}\\}=D_{2t-1}=D^{\prime}_{2t-1}=\\{y+\tau^{\prime}(y):y\in
D^{\prime}_{2t-2}\\}$, for each $x+\tau(x)\in D_{2t-1}$ there exists
$y+\tau^{\prime}(y)\in D^{\prime}_{2t-1}$ such that
$x+\tau(x)=y+\tau^{\prime}(y)$. Since $0\leq x,y\leq
p^{h_{0}}k_{0}-p^{h_{t-1}}$, we have $-p^{h_{0}}k_{0}<x-y<p^{h_{0}}k_{0}$. On
the other hand, $\tau^{\prime}(y)-\tau(x)$ is a multiple of $p^{h_{0}}k_{0}$
as both $\tau$ and $\tau^{\prime}$ are maps from $D_{2t-2}$ to
$p^{h_{0}}k_{0}\mathbb{Z}_{p^{\ell-h_{0}}}$. Hence
$x+\tau(x)=y+\tau^{\prime}(y)$ if and only if $x=y$ and
$\tau(x)=\tau^{\prime}(y)$. By the arbitrariness of $x$, it follows that
$D_{2t-2}=D^{\prime}_{2t-2}$ and $\tau=\tau^{\prime}$. Based on this and
similarly to the argument in the previous paragraph, we can prove that
$\tau_{i}=\tau^{\prime}_{i}$ for $1\leq i\leq t-1$ and $\tau=\tau^{\prime}$,
as desired to establish the second statement in (b). $\Box$

We are now ready to prove Theorem 1.4. Denote by $c(\Gamma)$ the number of
distinct perfect codes containing $0$ in a circulant graph $\Gamma$.

Proof of Theorem 1.4. Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq
1,m\geq 2$ are integers, and let $\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a
connected circulant graph with order $n$ and degree $p^{\ell}-1$ such that its
extended connection set $S_{0}$ is pyramidal. As shown in Lemma 5.2, the
series $\iota(S_{0}):H_{0}<H_{1}<H_{2}<\cdots<H_{2t-1}\leq
H_{2t}=\mathbb{Z}_{n}$ (see (8)) is the longest admissible subgroup series of
$\mathbb{Z}_{n}$ associated with $S_{0}$. Let
$\mathbf{h}(S_{0})=(h_{0},h_{1},\ldots,h_{t-1},h_{t})$ and
$\mathbf{k}(S_{0})=(k_{0},k_{1},\ldots,k_{t-1},k_{t})$ be the associated
sequences (see (9)) so that $H_{2i}=\langle p^{h_{i}}k_{i}\rangle$ and
$H_{2i-1}=\langle p^{h_{i-1}}k_{i}\rangle$ for $1\leq i\leq t$. Set
$\Gamma_{i}=\mathrm{Cay}(\mathbb{Z}_{n}/H_{i},(S_{0}/H_{i})\setminus\\{H_{i}\\})$
for $0\leq i\leq 2t$. We aim to prove $c(\Gamma)\geq
p^{\left(\sum_{i=0}^{t-1}(h_{i-1}-h_{i})k_{i}\right)+h_{t-1}-\ell}$, where
$h_{-1}=\ell$.

We proceed by induction on $t$. Consider the base case $t=1$ first. If
$H_{0}=\\{0\\}$ (that is, $h_{0}=\ell$), then $S_{0}$ is aperiodic,
$\Gamma_{1}$ is a complete graph by (T3), $0+H$ is the only perfect code in
$\Gamma_{1}$ containing $0$, and $H_{1}$ is the only perfect code in $\Gamma$
containing $0$. Hence $c(\Gamma)=1=p^{0}=p^{h_{-1}-h_{0}}$. If
$H_{0}\neq\\{0\\}$ (that is, $h_{0}<\ell$), then applying what we just proved
to $\Gamma_{0}$ yields $c(\Gamma_{0})=1$. Note that
$\Gamma=\Gamma_{0}\otimes\mathrm{Cay}(H_{0},H_{0}\setminus\\{0\\})$ and every
element of $H_{0}$ forms a perfect code in the complete graph
$\mathrm{Cay}(H_{0},H_{0}\setminus\\{0\\})$. So, by Lemma 5.4, we can choose
different elements of $H_{0}$ to obtain different perfect codes in $\Gamma$.
Since we only count perfect codes in $\Gamma$ containing $0$, it follows that
$c(\Gamma)=c(\Gamma_{0})p^{(\ell-h_{0})(k_{0}-1)}=p^{(\ell-h_{0})(k_{0}-1)}$.
So we have proved that in the case when $t=1$ there are at least
$p^{(h_{-1}-h_{0})k_{0}+h_{0}-\ell}$ perfect codes in
$\mathrm{Cay}(\mathbb{Z}_{n},S)$ containing $0$ no matter whether
$H_{0}=\\{0\\}$ or $H_{0}\neq\\{0\\}$, where $h_{-1}=\ell$.

Suppose that the result is true when $t<l$ for some $l\geq 2$. We are going to
prove that it is true when $t=l$.

Case 1. $H_{0}=\\{0\\}$ (that is, $h_{0}=\ell$).

Note that the extended connection set $T_{0}:=S_{0}/H_{2}$ of $\Gamma_{2}$ is
a pyramidal set of $\mathbb{Z}_{n}/H_{2}$ for which the longest admissible
subgroup series is $L_{0}<L_{1}<\cdots<L_{2(l-1)}=\mathbb{Z}_{n}/H_{2}$, where
$L_{i}=H_{i+2}/H_{2}$ for $0\leq i\leq 2(l-1)$. The corresponding sequences
are $\mathbf{h}(T_{0})=(a_{0},a_{1},\ldots,a_{l-1})$ and
$\mathbf{k}(T_{0})=(b_{0},b_{1},\ldots,b_{l-1})$, where $a_{i}=h_{i+1}$ and
$b_{i}=k_{i+1}$ for $0\leq i\leq l-1$. By the induction hypothesis,
$c(\Gamma_{2})\geq
p^{\left(\sum_{i=0}^{l-2}(a_{i-1}-a_{i})b_{i}\right)+a_{l-2}-a_{0}}$. Note
that $a_{-1}=a_{0}$ and $h_{-1}=h_{0}=\ell$. Similarly to the case $t=1$,
since
$\Gamma_{1}=\Gamma_{2}\otimes\mathrm{Cay}(\mathbb{Z}_{p^{h_{0}-h_{1}}},\mathbb{Z}_{p^{h_{0}-h_{1}}}\setminus\\{0\\})$,
we have

$\displaystyle c(\Gamma_{1})$
$\displaystyle=c(\Gamma_{2})p^{(h_{0}-h_{1})(k_{1}-1)}$ $\displaystyle\geq
p^{\left(\sum_{i=0}^{l-2}(a_{i-1}-a_{i})b_{i}\right)+a_{l-2}-a_{0}}\cdot
p^{(h_{0}-h_{1})(k_{1}-1)}$
$\displaystyle=p^{(a_{-1}-a_{0})b_{0}+\left(\sum_{i=1}^{l-2}(a_{i-1}-a_{i})b_{i}\right)+(h_{0}-h_{1})k_{1}+a_{l-2}-a_{0}-h_{0}+h_{1}}$
$\displaystyle=p^{\left(\sum_{i=1}^{l-2}(h_{i}-h_{i+1})k_{i+1}\right)+(h_{0}-h_{1})k_{1}+h_{l-1}-h_{0}}$
$\displaystyle=p^{(h_{-1}-h_{0})k_{0}+\left(\sum_{i=1}^{l-2}(h_{i}-h_{i+1})k_{i+1}\right)+(h_{0}-h_{1})k_{1}+h_{l-1}-\ell}$
$\displaystyle=p^{\left(\sum_{i=0}^{l-1}(h_{i-1}-h_{i})k_{i}\right)+h_{l-1}-\ell}.$

Here we used $a_{0}=h_{1}$ and $a_{l-2}=h_{l-1}$ to obtain the fourth line. By
Lemma 5.4, we have $c(\Gamma)=c(\Gamma_{0})=c(\Gamma_{1})$ and the desired
result follows.

Case 2. $H_{0}\neq\\{0\\}$ (that is, $h_{0}<\ell$).

The extended connection set $T_{0}:=S_{0}/H_{0}$ of $\Gamma_{0}$ is a
pyramidal set of $\mathbb{Z}_{n}/H_{0}$ for which the longest admissible
subgroup series is $L_{0}<L_{1}<\cdots<L_{2l}=\mathbb{Z}_{n}/H_{0}$, where
$L_{i}=H_{i}/H_{0}$ for $1\leq i\leq 2l$. The corresponding sequences are
$\mathbf{h}(T_{0})=(a_{0},a_{1},\ldots,a_{l})$ and
$\mathbf{k}(T_{0})=(b_{0},b_{1},\ldots,b_{l})$, where $a_{i}=h_{i}$ and
$b_{i}=k_{i}$ for $1\leq i\leq l$. Applying what we proved in Case 1 to
$\Gamma_{0}$, we obtain $c(\Gamma_{0})\geq
p^{\left(\sum_{i=0}^{l-1}(a_{i-1}-a_{i})b_{i}\right)+a_{l-1}-a_{0}}$, where
$a_{-1}=h_{0}$. Similarly to the case $t=1$, we have

$\displaystyle c(\Gamma)$ $\displaystyle=c(\Gamma_{0})p^{(\ell-
h_{0})(k_{0}-1)}$ $\displaystyle\geq
p^{\left(\sum_{i=0}^{l-1}(a_{i-1}-a_{i})b_{i}\right)+a_{l-1}-a_{0}}\cdot
p^{(\ell-h_{0})(k_{0}-1)}$
$\displaystyle=p^{\left((a_{-1}-a_{0})b_{0}+\sum_{i=1}^{l-1}(a_{i-1}-a_{i})b_{i}\right)+a_{l-1}-a_{0}+(\ell-
h_{0})k_{0}-\ell+h_{0}}$
$\displaystyle=p^{\sum_{i=1}^{l-1}(a_{i-1}-a_{i})b_{i}+(\ell-
h_{0})k_{0}+a_{l-1}-a_{0}-\ell+h_{0}}\quad(\text{as $a_{-1}=a_{0}=h_{0}$})$
$\displaystyle=p^{\sum_{i=1}^{l-1}(h_{i-1}-h_{i})k_{i}+(\ell-
h_{0})k_{0}+h_{l-1}-\ell}\quad(\text{as $a_{i}=h_{i}$ and $b_{i}=k_{i}$ for
$0\leq i\leq l$})$
$\displaystyle=p^{\sum_{i=1}^{l-1}(h_{i-1}-h_{i})k_{i}+(h_{-1}-h_{0})k_{0}+h_{l-1}-\ell}\quad(\text{taking
$h_{-1}=\ell$})$
$\displaystyle=p^{\left(\sum_{i=0}^{l-1}(h_{i-1}-h_{i})k_{i}\right)+h_{l-1}-\ell}.$

So the result holds for $\Gamma$.

Combining the two cases above, we have proved that the result is true when
$t=l$. This completes the proof by mathematical induction. $\Box$

##  6 Final remarks

The main result of this paper gives a complete explicit description of the
family of circulant graphs admitting a perfect code with extended connection
set of cardinality a prime power (Theorem 1.3) as well as a structural
description of such circulant graphs (Theorem 1.2). The characterization also
leads to a counting result (Theorem 1.4) which shows that the universe of
perfect codes in circulant graphs is relatively rich.

The characterization can be extended by a similar approach to the case of
perfect codes in the directed case, namely when the connection set $S$ of
$\mathrm{Cay}(\mathbb{Z}_{n},S)$ is not symmetric, although the corresponding
results are more involved and we have not attempted to report them here. In
another direction, a result analogous to Theorem 1.2 can be obtained for the
closely related family of Cayley sum graphs
$\mathrm{Cay}^{+}(\mathbb{Z}_{n},S)$ of cyclic groups, where two vertices
$x,y\in\mathbb{Z}_{n}$ are adjacent if and only if $x+y\in S$.

The main limitation of our approach is the restriction to prime powers for the
cardinality of the extended connection sets. This is due to the use of the key
Lemma 2.7, which provides the strategy to reach the pyramidal structure in
Theorem 1.2 and then to the recursive description of the family of circulant
graphs admitting perfect codes by lifts of the complete graph given in
Construction 4.6. It is still an open problem to determine the extent to which
the statement of Lemma 2.7 can be generalized. In view of the results in the
present paper it appears that a complete characterization of perfect codes,
even in the case of circulant graphs, beyond the prime power case may become a
project of high complexity. In any case, in absence of the result in Lemma
2.7, new ideas and techniques will be required.

## References

  * [1] N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973) 288–296.
  * [2] I. Broere and J. Hattingh, Products of circulant graphs, Quaest. Math. 13 (1990) 191–216.
  * [3] J. Chen, Y. Wang and B. Xia, Characterization of subgroup perfect codes in Cayley graphs, Discrete Math. 343 (2020) 111813.
  * [4] Y. Deng, Efficient dominating sets in circulant graphs with domination number prime, Inform. Process. Lett. 114 (2014) 700–702.
  * [5] Y. Deng, Y. Sun, Q. Liu and H. Wang, Efficient domination sets in circulant graphs, Discrete Math. 340 (2017) 1503–1507.
  * [6] I. J. Dejter and O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 129 (2003) 319–328.
  * [7] R. Feng, H. Huang and S. Zhou, Perfect codes in circulant graphs, Discrete Math 340 (2017) 1522–1527.
  * [8] H. Huang, B. Xia and S. Zhou, Perfect codes in Cayley graphs, SIAM J. Discrete Math. 32(1) (2018) 548–559.
  * [9] Y. Khaefi, Z. Akhlaghi and B. Khosravi, On the subgroup perfect codes in Cayley graphs, Des. Codes Cryptogr. 91 (2023) 55–61.
  * [10] Y. S. Kwon, J. Lee and M. Y. Sohn, Classification of efficient dominating sets of circulant graphs of degree $5$, Graphs Combin. 38(4) (2022) Paper No. 120, 8 pp.
  * [11] J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory 37 (2001) 213–219.
  * [12] C. Martínez, R. Beivide and E. Gabidulin, Perfect codes for metrics induced by circulant graphs, IEEE Trans. Inform. Theory 53 (2007) 3042–3052.
  * [13] N. Obradović, J. Peters and G. Ružić, Efficient domination in circulant graphs with two chord lengths, Inform. Prcess. Lett. 102 (2007) 253–258.
  * [14] K. Reji Kumar and G. MacGillivray, Efficient domination in circulant graphs, Discrete Math. 313 (2013) 767–771.
  * [15] A. D. Sands, Factoring finite abelian groups, J. Algebra 275 (2004) 540–549.
  * [16] S. Szabó and A. D. Sands, Factoring groups into subsets, CRC Press, 2009.
  * [17] T. Tamizh Chelvam and S. Mutharasu, Subgroups as efficient dominating sets in Cayley graphs, Discrete Appl. Math. 161 (2013) 1187–1190.
  * [18] A. Thomson and S. Zhou, Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes, European J. Combin. 38 (2014) 61–78.
  * [19] G. L. Walls, K. Wang and S. Zhou, Subgroup perfect codes in Cayley graphs, SIAM J. Discrete Math. 34 (2020) 1909–1921.
  * [20] J. Zhang and S. Zhou, On subgroup perfect codes in Cayley graphs, European J. Combin. 91 (2021) 103228.
  * [21] J. Zhang and S. Zhou, Corrigendum to “On subgroup perfect codes in Cayley graphs” [European J. Combin. 91 (2021) 103228], European J. Combin. 101 (2022) 103461.
  * [22] S. Zhou, Cyclotomic graphs and perfect codes, J. Pure Appl. Algebra 223 (2019) 931–947.

##  Appendix A A formula

In this appendix we give a formula for the number of connected circulant
graphs $\mathrm{Cay}(\mathbb{Z}_{n},S)$ with order $n$ and degree $p^{\ell}-1$
such that $(S_{0}-S_{0})\cap\langle p^{\ell}\rangle=\\{0\\}$. Note that, by
Theorem 1.2, such a graph $\mathrm{Cay}(\mathbb{Z}_{n},S)$ admits $\langle
p^{\ell}\rangle$ as a perfect code if in addition $S_{0}$ is pyramidal and
aperiodic. To obtain our formula we need the following two lemmas.

######  Lemma A.1.

Let $n=p^{\ell}m$ be an integer, where $p$ is a prime and $\ell\geq 1,m\geq 2$
are integers. Let $\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ be a circulant graph
with order $n$ and degree $p^{\ell}-1$ such that $(S_{0}-S_{0})\cap\langle
p^{\ell}\rangle=\\{0\\}$. If
$\Gamma\in\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{\ell})$ for some sequences
$\mathbf{l}=(\ell_{1},\ell_{2},\ldots,\ell_{t}),\mathbf{m}=(m_{1},m_{2},\ldots,m_{t})$
of positive integers satisfying $\sum_{i=1}^{t}\ell_{i}=\ell$ and
$\prod_{i=1}^{t}m_{i}=m$, then $p$ is not a divisor of $m_{i}$ for $2\leq
i\leq t$.

###### Proof.

Let $r=\ell_{t}$. Suppose, for a contradiction, that $p$ is a divisor of
$m_{i}$ for some $i$ between $2$ and $t$. Choose $k$ to be the largest
subscript such that $p$ divides $m_{k}$. Then $2\leq k\leq t$ and $p$ is not a
divisor of $m_{i}$ for $k<i\leq t$. For $1\leq i\leq t$, let
$\mathbf{l}_{i}=(\ell_{i},\ldots,\ell_{t})$,
$\mathbf{m}_{i}=(m_{i},\ldots,m_{t})$, $\ell(i)=\ell_{i}+\cdots+\ell_{t}$, and
$n(i)=p^{\ell_{i}+\cdots+\ell_{t}}m_{i}\cdots m_{t}=p^{\ell(i)}m_{i}\cdots
m_{t}$. Let $\Gamma_{i}=\mathrm{Cay}(\mathbb{Z}_{n(i)},S(i))$ be a circulant
graph in $\mathcal{G}_{\mathbf{l}_{i},\mathbf{m}_{i}}(n(i),p^{\ell(i)})$. In
particular,
$\Gamma_{k}\in\mathcal{G}_{\mathbf{l}_{k},\mathbf{m}_{k}}(n(k),p^{\ell(k)})$.
By part (c) of Lemma 4.10, we have

$\mathcal{G}_{\mathbf{l}_{k},\mathbf{m}_{k}}(n(k),p^{\ell(k)})\subseteq(\bar{f}_{m_{k}}\cdots\bar{f}_{m_{t}})(\bar{g}_{p^{\ell_{k}}}\cdots\bar{g}_{p^{\ell_{t-1}}}(K_{p^{\ell_{t}}})).$

Moreover, by part (b) of Lemma 4.10, we have
$(\bar{g}_{p^{\ell_{k}}}\cdots\bar{g}_{p^{\ell_{t}-1}})(K_{p^{\ell_{t}}})=K_{p^{\ell(k)}}$.
So, by part (a) of Lemma 4.10,
$\Gamma_{k}\in(\bar{f}_{m_{k}}\cdots\bar{f}_{m_{t}})(K_{p^{\ell(k)}})=\bar{f}_{m_{k}\cdots
m_{t}}(K_{p^{\ell(k)}})$. Note that
$K_{p^{\ell(k)}}=\mathrm{Cay}(\mathbb{Z}_{p^{\ell(k)}},\mathbb{Z}_{p^{\ell(k)}}\setminus\\{0\\})$
and $x-y\not\equiv 0\pmod{p^{\ell(k)}}$ for distinct
$x,y\in\mathbb{Z}_{p^{\ell(k)}}$. By part (a) of Lemma 4.7, we have
$x-y\not\equiv 0\pmod{p^{\ell(k)}}$ for distinct $x,y\in S(k)_{0}$. Let
$T(\sigma)_{0}\in\bar{g}_{p^{\ell_{k-1}}}(S(k)_{0})$. Then
$T(\sigma)_{0}=\\{s+in(k):s\in S(k)_{0},0\leq i\leq p^{\ell_{k-1}}-1\\}$,
where $n(k)$ is as above. Since $p$ is a divisor of $m_{k}$ and
$\ell_{k-1}+\ell(k)=\ell(k-1)$, $p^{\ell_{k-1}-1}n(k)$ is divisible by
$p^{\ell(k-1)}$. Thus, by part (c) of Lemma 4.7, there are distinct elements
$x,y\in S_{0}$ such that $x-y\equiv 0\pmod{p^{\ell}}$, that is,
$(S_{0}-S_{0})\cap\langle p^{\ell}\rangle\neq\\{0\\}$, which contradicts our
assumption. $\Box$

For positive integers $d,n$ and prime $p$, let $\nu(d)$ be the number of prime
divisors of $d$ and $D_{n}^{p}$ the set of square-free divisors of $n$ greater
than $1$ and coprime to $p$.

######  Lemma A.2.

Let $n=p^{\ell}m$, where $p$ is a prime and $\ell>1,m\geq 2$ are integers such
that $\ell+p\geq 4$. If $D_{n}^{p}\neq\emptyset$, then the number of elements
$T(\sigma)\in\bar{f}_{m}(K_{p^{\ell}})$ satisfying ${\rm gcd}(T(\sigma))\neq
1$ are exactly $\sum\limits_{d\in
D_{n}^{p}}(-1)^{\nu(d)-1}(m/d)^{\frac{p^{\ell}-1}{2}}$.

###### Proof.

For each integer $1\leq i\leq p^{\ell}-1$, set

$P_{i}=\\{x\in\mathbb{Z}_{n}:x\equiv
i\pmod{p^{\ell}}\\}=\\{i,i+p^{\ell},\ldots,i+(m-1)p^{\ell}\\}.$

Note that for any feasible map $\sigma$ from
$\mathbb{Z}_{p^{\ell}}\setminus\\{0\\}$ to $\\{0,1,\ldots,(n/p^{\ell})-1\\}$,
$T(\sigma)=\\{x+\sigma(x)p^{\ell}:x\in\mathbb{Z}_{p^{\ell}}\setminus\\{0\\}\\}$.
Thus, for each integer $1\leq i\leq p^{\ell}-1$, $|T(\sigma)\cap P_{i}|=1$.
View $\mathbb{Z}_{p^{\ell}}$ as a set. Since $p$ is not a divisor of ${\rm
gcd}(\mathbb{Z}_{p^{\ell}}\setminus\\{0\\})$, $p$ is not a divisor of ${\rm
gcd}(T(\sigma))$.

For any integer $d\in D_{n}^{p}$, if ${\rm gcd}(p,d)=1$, then ${\rm
gcd}(p^{\ell},d)=1$. There are two integers $a,b$ such that $ad+bp^{\ell}=1$,
and so $ad=-bp^{\ell}+1$. Then for any integer $1\leq i\leq p^{\ell}-1$, there
is an integer $\alpha$ between $0$ and $d-1$ such that $d$ is a divisor of
$i+\alpha p^{\ell}$ and for any integer $0\leq\beta\leq\alpha-1$, $d$ is not a
divisor of $i+\beta p^{\ell}$. Clearly, for each integer
$j\in\\{0,1,\ldots,(m/d)-1\\}$, $d$ is also a divisor of
$i+(jd+\alpha)p^{\ell}$. Thus for each integer $1\leq i\leq p^{\ell}-1$ there
are exactly $m/d$ elements in $P_{i}$ such that $d$ is a divisor of these $m$
elements. Moreover, since $T(\sigma)$ is inverse-closed in $\mathbb{Z}_{n}$,
if $s$ is fixed, then $-s$ is also fixed. Hence for each divisor $d\in
D_{n}^{p}$ there are exactly $(m/d)^{\frac{p^{\ell}-1}{2}}$ connection sets
$T(\sigma)$ in $\bar{f}_{m}(K_{p^{\ell}})$ such that $d$ is a divisor of ${\rm
gcd}(T(\sigma))$.

Suppose $m=p^{a(0)}p^{a(1)}_{1}p^{a(2)}_{2}\cdots p^{a(b)}_{b}$, where
$a(0)\geq 0$, $p,p_{1},p_{2},\ldots,p_{b}$ are different primes and for any
integer $1\leq i\leq b$, $a(i)\geq 1$. For any integer $1\leq i\leq b$, define
$W(i)=\\{p_{1(1)}p_{1(2)}\cdots
p_{1(i)}:p_{1(1)},p_{1(2)},\ldots,p_{1(i)}\text{ are different elements of
}\\{p_{1},p_{2},\ldots,p_{b}\\}\\}$. For each integer $1\leq i\leq
p^{\ell}-1$, define

$U(i)=\\{T(\sigma)_{0}\in\bar{f}_{m}(K_{p^{\ell}}):\text{there exists $d\in
W(i)$ such that $d$ is a divisor of ${\rm gcd}(T(\sigma))$}\\}.$

Let $F(i)=\sum_{d\in W(i)}(m/d)^{\frac{p^{\ell}-1}{2}}$. Note that
$U(b)\subseteq U(b-1)\subseteq\cdots\subseteq U(1)$. Thus each extended
connection set $T(\sigma)_{0}$ in $\bar{f}_{m}(K_{p^{\ell}})$ satisfying ${\rm
gcd}(T(\sigma))\neq 1$ is counted by $F(1)$. Moreover, it is known that for
any integer $1\leq i<j\leq b$, $F(i)$ counts extended connection sets
$T(\sigma)_{0}$ in $\bar{f}_{m}(K_{p^{\ell}})$ satisfying that there is an
integer $d\in W(j)$ such that $d$ is a divisor of ${\rm gcd}(T(\sigma))$
exactly $\binom{j}{i}$ times. Thus, in order to count the number of elements
$T(\sigma)_{0}\in\bar{f}_{m}(K_{p^{\ell}})$ satisfying ${\rm
gcd}(T(\sigma))\neq 1$, we only need to consider the number of extended
connection sets $T(\sigma)_{0}\in\bar{f}_{m}(K_{p^{\ell}})$ satisfying ${\rm
gcd}(T(\sigma))\in D_{n}^{p}$. Since $\sum_{i=1}^{a}(-1)^{i-1}\binom{a}{i}=1$
for any integer $a\geq 1$, for any $1\leq j\leq b$,
$\sum_{i=1}^{j}(-1)^{j-1}F(j)$ counts each extended connection set
$T(\sigma)_{0}$ in $\bar{f}_{m}(K_{p^{\ell}})$ satisfying ${\rm
gcd}(T(\sigma))\in\cup_{i=1}^{j}W(j)$ exactly once. In particular, taking
$j=b$, we obtain that the number of elements
$T(\sigma)\in\bar{f}_{m}(K_{p^{\ell}})$ satisfying ${\rm gcd}(T(\sigma))\neq
1$ is exactly $\sum\limits_{d\in
D_{n}^{p}}(-1)^{\nu(d)-1}(m/d)^{\frac{p^{\ell}-1}{2}}$. $\Box$

######  Theorem A.3.

Let $n=p^{\ell}m$, where $p$ is a prime and $\ell\geq 1,m\geq 2$ are integers
such that $\ell+p\geq 4$. Then the number of connected circulant graphs
$\mathrm{Cay}(\mathbb{Z}_{n},S)$ with order $n$ and degree $p^{\ell}-1$ such
that $(S_{0}-S_{0})\cap\langle p^{\ell}\rangle=\\{0\\}$ is equal to

$\left(\frac{n}{p^{\ell}}\right)^{r_{\ell}}+\sum_{d\in
D_{n}^{p}}(-1)^{\nu(d)}\left(\frac{n}{p^{\ell}d}\right)^{r_{\ell}},$ (11)

where $r_{\ell}=(p^{\ell}-1)/2$ if $p$ is odd and $r_{\ell}=2^{\ell-2}$ if
$p=2$, with the understanding that the second term vanishes when
$D_{n}^{p}=\emptyset$.

Denote by $N(n,p^{\ell})$ the said number in the theorem. The condition
$\ell+p\geq 4$ ensures $\ell\geq 2$ when $p=2$. (If $\ell=1$ and $p=2$, then
$N(n,p^{\ell})=0$ as there is no connected circulant graph with order $n\geq
4$ and degree $1$.) Note that when $D_{n}^{2}=\emptyset$ we have $n=2^{\ell}$
and (11) yields $N(n,2^{\ell})=1$.

###### Proof.

By Theorem 1.3, a connected circulant graph
$\Gamma=\mathrm{Cay}(\mathbb{Z}_{n},S)$ with order $n$ and degree $p^{\ell}-1$
admits a perfect code if and only if
$\Gamma\in\mathcal{G}_{\mathbf{l},\mathbf{m}}(n,p^{\ell})$ for some
$\mathbf{l}=(\ell_{1},\ell_{2},\ldots,\ell_{t})$ and
$\mathbf{m}=(m_{1},m_{2},\ldots,m_{t})$ satisfying
$\sum_{i=1}^{t}\ell_{i}=\ell$ and $\prod_{i=1}^{t}m_{i}=m$. If in addition
$\Gamma$ satisfies $(S_{0}-S_{0})\cap\langle|S_{0}|\rangle=\\{0\\}$, then by
Lemma A.1 we have ${\rm gcd}(m_{i},p)=1$ for $2\leq i\leq t$. By parts (a)–(c)
of Lemma 4.10, we have $\Gamma\in\bar{f}_{n/p^{\ell}}(K_{p^{\ell}})$. Note
that any element of $\bar{f}_{n/p^{\ell}}(K_{p^{\ell}})$ is of the form
$T(\sigma)=\\{x+\sigma(x)p^{\ell}:x\in\mathbb{Z}_{p^{\ell}}\setminus\\{0\\}\\}$,
where $\sigma$ is a feasible map from $\mathbb{Z}_{p^{\ell}}$ to
$\\{0,1,\ldots,(n/p^{\ell})-1\\}$ (so that $\sigma(0)=0$ and
$-T(\sigma)=T(\sigma)$ in $\mathbb{Z}_{n}$).

Assume $p$ is odd. Since for each $x\in\mathbb{Z}_{p^{\ell}}\setminus\\{0\\}$,
$\sigma(-x)$ is determined by $\sigma(x)$, each
$\sigma\in\bar{f}_{n/p^{\ell}}(K_{p^{\ell}})$ is determined by $\sigma(x)$ for
$x\in\\{1,2,\ldots,(p^{\ell}-1)/2\\}\subset\mathbb{Z}_{p^{\ell}}\setminus\\{0\\}$.
Since each $\sigma(x)$ can independently take any value from
$\\{0,1,\ldots,(n/p^{\ell})-1\\}$, it follows that the cardinality of
$\bar{f}_{n/p^{\ell}}(K_{p^{\ell}})$ is exactly
$(n/p^{\ell})^{\frac{p^{\ell}-1}{2}}$. Since $\Gamma$ satisfies
$(S_{0}-S_{0})\cap\langle|S_{0}|\rangle=\\{0\\}$ and $|S_{0}|=p^{\ell}$, for
any $T(\sigma)\in\bar{f}_{n/p^{\ell}}(K_{p^{\ell}})$ and $y\in T(\sigma)$, we
have $y\not\equiv 0\pmod{p^{\ell}}$. By the definition of $T(\sigma)$, ${\rm
gcd}(T(\sigma))$ is not divisible by $p$. If $D_{n}^{p}=\emptyset$, then
$n/p^{\ell}=p^{r}$ for some integer $r\geq 0$. Since ${\rm gcd}(T(\sigma))$ is
a divisor of $n=p^{\ell+r}$, by the definition of $T(\sigma)$ again we see
that ${\rm gcd}(T(\sigma))=1$ and hence all circulant graphs in
$\bar{f}_{n/p^{\ell}}(K_{p^{\ell}})$ are connected. Hence, if
$D_{n}^{p}=\emptyset$, then
$N(n,p^{\ell})=(n/p^{\ell})^{\frac{p^{\ell}-1}{2}}$. If
$D_{n}^{p}\neq\emptyset$, then by Lemma A.2 the number of elements
$T(\sigma)\in\bar{f}_{n/p^{\ell}}(K_{p^{\ell}})$ satisfying ${\rm
gcd}(T(\sigma))\neq 1$ is exactly $\sum\limits_{d\in
D_{n}^{p}}(-1)^{\nu(d)-1}(n/(p^{\ell}d))^{\frac{p^{\ell}-1}{2}}$, and
therefore $N(n,p^{\ell})$ is given by (11).

Now assume $p=2$. Then $\ell\geq 2$ by our assumption, and $n/2$ belongs to
every $T(\sigma)\in\bar{f}_{n/2^{\ell}}(K_{2^{\ell}})$. So there are exactly
$(n/2^{\ell})^{2^{\ell-2}}$ different elements
$T(\sigma)\in\bar{f}_{n/2^{\ell}}(K_{2^{\ell}})$, all of which are such that
${\rm gcd}(T(\sigma))$ is odd. By Remark 4.5, ${\rm gcd}(n/2^{\ell},2)=1$.
Thus, if $D_{n}^{2}=\emptyset$, then $n=2^{\ell}$ and hence
$\bar{f}_{n/2^{\ell}}(K_{2^{\ell}})$ contains only one graph, yielding
$N(n,2^{\ell})=1$. If $D_{n}^{2}\neq\emptyset$, then there are exactly
$\sum\limits_{d\in D_{n}^{2}}(-1)^{\nu(d)-1}(n/(2^{\ell}d))^{2^{\ell-2}}$
different elements $T(\sigma)\in\bar{f}_{n/2^{\ell}}(K_{2^{\ell}})$ such that
${\rm gcd}(T(\sigma))\neq 1$, and hence $N(n,2^{\ell})$ is given by (11).
$\Box$