# Group actions on codes in graphs

Daniel R. Hawtin and Cheryl E. Praeger

##  Chapter 0 Group actions on codes in graphs

Daniel R. Hawtin and Cheryl E. Praeger

###### Contents

  1. 0 Group actions on codes in graphs
    1. 1 Introduction: Codes in Graphs
      1. 1 Codes in graphs: neighbour-transitivity and complete transitivity
    2. 2 Fundamental concepts: neighbour-transitive codes
      1. 1 Parameters and regularity properties for codes in graphs
      2. 2 Symmetry of codes in graphs
      3. 3 Elusive codes
      4. 4 $s$-Neighbour-transitive codes and $s$-distance-transitive graphs
      5. 5 Further techniques for analysing codes
    3. 3 Commentary on the origins of completely-transitive codes
    4. 4 Graphs of interest
      1. 1 Hamming graphs
      2. 2 Johnson and Kneser graphs
      3. 3 $q$-Analogues of various graphs
      4. 4 Two graphs related to incidence structures
    5. 5 Codes in Hamming graphs
      1. 1 Alphabet-almost-simple codes in Hamming graphs
      2. 2 Alphabet-affine codes in Hamming graphs
      3. 3 Codes in binary Hamming graphs
      4. 4 A non-existence result: proof of Theorem 3.1
      5. 5 Codes in Hamming graphs from permutation modules
    6. 6 Codes in Kneser graphs
    7. 7 Codes in incidence graphs of generalised quadrangles
    8. 8 Coda: final reflections and summary of open problems

###  1 Introduction: Codes in Graphs

Traditionally error-correcting codes are modelled as subsets ${\mathcal{C}}$
of vectors in a finite vector space $V=\mathbb{F}_{q}^{n}$ over a field of
order $q$, where the vectors are represented as $n$-dimensional row vectors
with entries from $\mathbb{F}_{q}$, and distance between two vectors is the
number of entries where they differ. The _minimum distance_ $\delta$ of
${\mathcal{C}}$ is the smallest distance between two codewords, and the code
is called _perfect_ if the balls of radius $\lfloor(\delta-1)/2\rfloor$
partition the space $V$. Much work was devoted by many researchers to
understanding and finding new perfect codes, and eventually, Tietäväinen [89],
and Zinoviev and Leontiev [92], independently showed that the only non-trivial
perfect codes over finite fields are ‘Hamming-like’ codes (perfect single-
error correcting codes), and the famous Golay codes in $\mathbb{F}_{2}^{23}$
and $\mathbb{F}_{3}^{11}$, (see for example, the 1975 survey on perfect codes
by Van Lint [90]). Larger families of codes with desirable properties were
sought. For example, in 1971, Semakov, Zinoviev, and Zaitsev[81] introduced a
family of codes, properly containing the perfect codes, which they called
uniformly packed codes, and which retained strong regularity properties for
‘packing’ codewords in the vector space. Then independently, around 1973,
Norman Biggs [13, 14] and Philippe Delsarte [28, 29] suggested a complete
change of focus. Biggs introduced the concept of a perfect code in a graph,
while Delsarte developed a general theory of association schemes in coding
theory. This led to the notion of codes in graphs, which is the theme of this
chapter.

The chapter will provide an overview of recent work on codes in graphs which
are neighbour-transitive, or have stronger symmetry properties. Most of the
graphs considered are distance-regular, and our particular focus is codes in
Hamming graphs since the current work on neighbour-transitive codes in Johnson
graphs (a particular study advocated by Delsarte) has been recently covered in
the 2021 survey by the second author [74]111This was the Clay Lecture at the
British Combinatorial Conference 2021, and a version of the survey may be
downloaded from https://www.claymath.org/events/british-combinatorial-
conference-2021/. In Section 3 we give a brief historical account of
completely transitive codes in Hamming graphs and Johnson graphs which
motivated the more general developments on neighbour-transitivity,
particularly in Hamming graphs, surveyed in Section 5. We also summarise very
recent work on codes in other graphs, such as Kneser graphs and the incidence
graphs of generalised quadrangles, as well as state some results for Grassmann
graphs and bilinear forms graphs (the $q$-analogues of the Johnson and Hamming
graphs).

####  1 Codes in graphs: neighbour-transitivity and complete transitivity

A graph $\Gamma=(V,E)$ consists of a set $V$ of vertices and a set $E$ of
edges (unordered pairs of vertices), and a code ${\mathcal{C}}$ in $\Gamma$ is
defined as a subset of $V$. Distance between distinct codewords (elements of
${\mathcal{C}}$) is given by the length of a shortest path between them in the
graph $\Gamma$, and the minimum distance $\delta({\mathcal{C}})$ is the
minimum distance between distinct codewords. This viewpoint also suggests a
natural measure for the symmetry of a code ${\mathcal{C}}$ in $\Gamma$.
Symmetry of the graph $\Gamma$ is measured by its automorphism group ${\rm
Aut}(\Gamma)$, namely the subgroup of permutations of $V$ which leave
invariant the edge-set $E$. We take as the _automorphism group_ ${\rm
Aut}({\mathcal{C}})$ of the code ${\mathcal{C}}$ the subgroup of ${\rm
Aut}(\Gamma)$ consisting of all elements that leave ${\mathcal{C}}$ invariant
(setwise). Delsarte suggested choosing $\Gamma$ to be a distance-regular
graph: that is to say, for any (possibly equal) vertices $v$ and $w$, the
number of vertices at distance $j$ from $v$ and at distance $k$ from $w$
depends only upon $j,k$, and the distance between $v$ and $w$. He defined a
special type of code, now called a completely-regular code, ‘which enjoys
combinatorial (and often algebraic) symmetry akin to that observed for perfect
codes’ (see [68, page 1]). Again, disappointingly, not many examples of
completely regular codes were found with good error-correcting properties –
that is to say, with large distance between distinct codewords (see the
comments and references in [74, Section 1.1]).

A useful notion for exploring a code ${\mathcal{C}}$ in a graph $\Gamma$ is
the _distance partition_ of ${\mathcal{C}}$. This is the partition:

$\\{{\mathcal{C}}_{0},{\mathcal{C}}_{1},\ldots,{\mathcal{C}}_{\rho}\\}$ of $V$
such that ${\mathcal{C}}_{0}={\mathcal{C}}$ and, for $i\geq 1$,
${\mathcal{C}}_{i}$ is the set of all vertices $\gamma$ such that the minimum
distance between $\gamma$ and a codeword is equal to $i$. The largest integer
$i$ such that ${\mathcal{C}}_{i}\neq\emptyset$ is called the covering radius
of ${\mathcal{C}}$, and is denoted $\rho$ and sometimes $\rho({\mathcal{C}})$.
(1)

Since graph automorphisms preserve distance, the automorphism group ${\rm
Aut}({\mathcal{C}})$ fixes each of the subsets ${\mathcal{C}}_{i}$ setwise,
and so each ${\mathcal{C}}_{i}$ is a union of ${\rm
Aut}({\mathcal{C}})$-orbits. A natural, but very strong, symmetry condition to
place on a code is to require that each ${\mathcal{C}}_{i}$ is a single orbit
of ${\rm Aut}({\mathcal{C}})$. Codes with this property are called _completely
transitive_ , and this family of codes was among the first family of codes to
be studied in various families of graphs. We discuss some of the results about
completely transitive codes in Section 3.

Most recent studies of codes in graphs have focused on strictly larger
families than the completely regular codes or the completely transitive codes,
where their strict regularity or symmetry conditions have been replaced by
more ‘local’ conditions. This new approach perhaps dates back to a discussion
between the second author and (Bob) Liebler in 2005 (leading to [66]). In the
context of codes in Johnson graphs, Bob suggested that the stringent
regularity conditions imposed for complete regularity, could be replaced by a
‘local transitivity’ property. This led to the notion of a _neighbour-
transitive code_ in an arbitrary graph $\Gamma$, that is to say, a code
${\mathcal{C}}$ such that ${\rm Aut}({\mathcal{C}})$ is transitive both on
${\mathcal{C}}$ and on the set ${\mathcal{C}}_{1}$ of the distance partition.
The vertices in ${\mathcal{C}}_{1}$ are called code-neighbours (the non-
codewords that are adjacent in $\Gamma$ to some codeword). More recently, for
any positive integer $s\leq\rho({\mathcal{C}})$, a code ${\mathcal{C}}$ in
$\Gamma$ is called _$s$ -neighbour-transitive_ if each of
${\mathcal{C}}_{0},{\mathcal{C}}_{1},\dots,{\mathcal{C}}_{s}$ is an ${\rm
Aut}({\mathcal{C}})$-orbit. Thus the neighour-transitive codes are
$1$-neighbour-transitive, and the completely transitive codes are
$\rho({\mathcal{C}})$-neighbour-transitive.

###  2 Fundamental concepts: neighbour-transitive codes

In this section we present some general concepts and results regarding codes
in graphs. We begin with a discussion in arbitrary graphs before specialising
to the Hamming graphs and other specific graph families.

####  1 Parameters and regularity properties for codes in graphs

Let $\Gamma=(V,E)$ be a graph. Note that we will always assume that $\Gamma$
is simple, finite, undirected and connected. Let $\alpha,\beta\in V$. Denote
by $d(\alpha,\beta)$ the _distance_ in $\Gamma$ between $\alpha$ and $\beta$,
that is, the length of the shortest path between $\alpha$ and $\beta$. Define
$\Gamma_{i}(\alpha)=\\{\gamma\in V\mid d(\alpha,\gamma)=i\\}$. Furthermore,
the _ball_ $B_{i}(\alpha)$ of radius $i$ centered at $\alpha$ is defined to be
$\bigcup_{j=0}^{i}\Gamma_{j}(\alpha)$.

Let ${\mathcal{C}}$ be a code in a graph $\Gamma=(V,E)$. We refer to elements
of ${\mathcal{C}}$ as _codewords_. A code ${\mathcal{C}}$ such that
$|{\mathcal{C}}|\leq 1$ or ${\mathcal{C}}=V(\Gamma)$ is called _trivial_ , and
we will often be assuming without statement that ${\mathcal{C}}$ is non-
trivial. If ${\mathcal{C}}^{\prime}$ is a subset of ${\mathcal{C}}$ then we
say that ${\mathcal{C}}^{\prime}$ is a _subcode_ of ${\mathcal{C}}$. The
_minimum distance_ $\delta$ of ${\mathcal{C}}$ is the smallest distance
between a pair of distinct elements of ${\mathcal{C}}$. The _error-correction
capacity_ $e$ of ${\mathcal{C}}$ is defined to be the largest value of $i$ for
which, given distinct $\alpha,\beta\in{\mathcal{C}}$, the balls
$B_{i}(\alpha)$ and $B_{i}(\beta)$ are disjoint. These two parameters are
related by $e=\lfloor(\delta-1)/2\rfloor$. The _covering radius_ $\rho$ of
${\mathcal{C}}$ is the smallest value of $i$ for which
$\bigcup_{\alpha\in{\mathcal{C}}}B_{i}(\alpha)=V$.

######  Lemma 2.1.

Let ${\mathcal{C}}$ be a code with error-correction capacity $e$ in a graph
$\Gamma$ and let $i\leq e$. Then the following hold.

  1. $(1)$

For each $\gamma\in{\mathcal{C}}_{i}$ there exists a unique
$\alpha\in{\mathcal{C}}$ such that $\gamma\in\Gamma_{i}(\alpha)$.

  2. $(2)$

${\mathcal{C}}_{i}$ is the disjoint union
$\bigcup_{\alpha\in{\mathcal{C}}}\Gamma_{i}(\alpha)$.

  3. $(3)$

$\Gamma_{i}(\alpha)\neq\emptyset$ for all $\alpha\in{\mathcal{C}}$.

###### Proof.

All the assertions hold for a trivial code ${\mathcal{C}}$, with $i=e=0$, so
we may assume that ${\mathcal{C}}$ is non-trivial. Then its minimum distance
$\delta=\delta({\mathcal{C}})$ is a positive integer. Since every element of
${\mathcal{C}}_{i}$ is at distance $i$ from some element of ${\mathcal{C}}$ we
have
${\mathcal{C}}_{i}\subseteq\bigcup_{\alpha\in{\mathcal{C}}}\Gamma_{i}(\alpha)$.
Let $\alpha\in{\mathcal{C}}$ and $\gamma\in\Gamma_{i}(\alpha)$. Consider a
codeword $\beta\in{\mathcal{C}}$ such that $\alpha\neq\beta$. If
$d(\beta,\gamma)\leq i$, then $\gamma\in B_{i}(\alpha)\cap B_{i}(\beta)$ and
hence $d(\alpha,\beta)\leq 2i\leq 2e<\delta$, which is a contradiction. Thus
$d(\beta,\gamma)>i$. In particular, $\alpha$ is the unique codeword in
${\mathcal{C}}$ at distance $i$ from $\gamma$, and part (1) holds. This
implies moreover that $\gamma\in{\mathcal{C}}_{i}$. Thus
$\Gamma_{i}(\alpha)\subseteq{\mathcal{C}}_{i}$ for each
$\alpha\in{\mathcal{C}}$, and hence
$\bigcup_{\alpha\in{\mathcal{C}}}\Gamma_{i}(\alpha)={\mathcal{C}}_{i}$. Now,
if $\beta_{1}$ and $\beta_{2}$ are distinct codewords in ${\mathcal{C}}$, then
the assumption $i\leq e$ implies that $B_{i}(\alpha)\cap
B_{i}(\beta)=\emptyset$ so that
$\Gamma_{i}(\alpha)\cap\Gamma_{i}(\beta)=\emptyset$. Thus the union is
disjoint, and part (2) is proved.

Consider distinct codewords $\alpha,\beta\in{\mathcal{C}}$, and let
$(\gamma_{0},\gamma_{1},\dots,\gamma_{r})$ be a path in $\Gamma$ of length
$r=d(\alpha,\beta)$ from $\alpha=\gamma_{0}$ to $\gamma_{r}=\beta$. It follows
from the minimality in the definition of $d(\alpha,\beta)$ that
$d(\alpha,\gamma_{j})=j$ and $d(\beta,\gamma_{r-j})=j$ whenever $0\leq j\leq
r$. If $r\leq i$, then taking $j=r$ we have $\beta\in B_{i}(\alpha)\cap
B_{i}(\beta)$, which is a contradiction, since $i\leq e$. Hence $r>i$ and
$\gamma_{i}\in\Gamma_{i}(\alpha)$, proving part (3). ∎

######  Definition 2.2.

For a code ${\mathcal{C}}$ in a graph $\Gamma$ and a non-negative integer $s$
at most the covering radius $\rho$, ${\mathcal{C}}$ is said to be _$s$
-regular_ if for each $i\in\\{0,1,\ldots,s\\}$ there exist non-negative
integers $a_{i}$, $b_{i}$ (if $s<\rho$), and $c_{i}$ (if $i>0$), such that for
each vertex $\alpha\in{\mathcal{C}}_{i}$ there are precisely:

  1. (1)

$a_{i}$ vertices in $\Gamma_{1}(\alpha)\cap{\mathcal{C}}_{i}$,

  2. (2)

$b_{i}$ vertices in $\Gamma_{1}(\alpha)\cap{\mathcal{C}}_{i+1}$, and,

  3. (3)

$c_{i}$ vertices in $\Gamma_{1}(\alpha)\cap{\mathcal{C}}_{i-1}$,

and $a_{i},b_{i},c_{i}$ depend only on $i$, and not on the particular choice
of $\alpha$. If $s=\rho$ then ${\mathcal{C}}$ is said to be _completely
regular_.

It is worth mentioning that a graph $\Gamma$ is distance-regular, according to
the usual definition, if and only if, for every vertex $\alpha$ of $\Gamma$,
the singleton set $\\{\alpha\\}$ is a completely regular code in $\Gamma$.

####  2 Symmetry of codes in graphs

The _symmetric group_ ${\rm Sym}(V)$ is the group of all permutations of $V$,
and, for $\alpha\in V$ and $g\in G$, we write $\alpha^{g}$ for the image of
$\alpha$ under $g$. Each element $g\in{\rm Sym}(V)$ permutes subsets of $V$ in
a natural way, namely for $U\subseteq V$, the image $U^{g}$ of $U$ under $g$
is the set $\\{\alpha^{g}\mid\alpha\in U\\}$ of images for the elements of
$U$. The _setwise stabiliser_ of $U$ is the set ${\rm Sym}(V)_{U}:=\\{g\in{\rm
Sym}(V)\mid U^{g}=U\\}$, and this is a subgroup of ${\rm Sym}(V)$. In
particular, for each $i<|V|$, $g$ permutes the $i$-element subsets of $V$
among themselves and, for a set $E$ of $i$-element subsets, we say that $g$
_leaves $E$ invariant_ if $U^{g}\in E$ for all $U\in E$. We often deal with
_permutation groups on $V$_, that is, subgroups $G\leq{\rm Sym}(V)$. A
permutation group is _transitive_ on $V$ if, for all $u,v\in V$, there exists
$g\in G$ such that $u^{g}=v$. For $1<i<v$, we say that $G$ is _$i$
-transitive_ on $V$ if $G$ is transitive on $V$ and, for $v\in V$, the
stabiliser $G_{v}$ is $(i-1)$-transitive on $V\setminus\\{v\\}$. Also $G$ is
said to be _$i$ -homogeneous_ on $V$ if $G$ is transitive on the set of
$i$-element subsets of $V$.

Let $\Gamma=(V,E)$ be a graph. Then an _automorphism_ of $\Gamma$ is a
permutation $g\in{\rm Sym}(V)$ such that $g$ leaves the edge set $E$
invariant. The set of all automorphisms of $\Gamma$ forms a subgroup ${\rm
Aut}(\Gamma)$ called the _automorphism group_ of $\Gamma$.

If ${\mathcal{C}}$ is a code in $\Gamma$ then, as introduced in Section 1, the
automorphism group of ${\mathcal{C}}$ is the setwise stabiliser ${\rm
Aut}({\mathcal{C}})$ of ${\mathcal{C}}$ in ${\rm Aut}(\Gamma)$, that is to
say, ${\rm Aut}({\mathcal{C}})={\rm Sym}(V)_{\mathcal{C}}\cap{\rm
Aut}(\Gamma)$. (2)

Two codes are _equivalent_ if there exists an automorphism of $\Gamma$ mapping
one to the other. Note that equivalent codes have many of the same properties,
for instance, the same minimum distance, the same covering radius and
isomorphic automorphism groups. Hence, we will often be interested in codes
only up to equivalence.

The following concepts are the main focus of this chapter and may be viewed as
algebraic analogues of Definition 2.2.

######  Definition 2.3.

Let ${\mathcal{C}}$ be a code with covering radius $\rho$ in a graph $\Gamma$,
let $G\leq{\rm Aut}({\mathcal{C}})$, and let $s\in\\{1,\ldots,\rho\\}$. Then
we make the following definitions.

  1. (1)

${\mathcal{C}}$ is _$(G,s)$ -neighbour-transitive_ if $G$ acts transitively on
each of the sets ${\mathcal{C}},{\mathcal{C}}_{1},\ldots,{\mathcal{C}}_{s}$.

  2. (2)

${\mathcal{C}}$ is _$G$ -neighbour-transitive_ if ${\mathcal{C}}$ is
$(G,1)$-neighbour-transitive.

  3. (3)

${\mathcal{C}}$ is _$G$ -completely transitive_ if ${\mathcal{C}}$ is
$(G,\rho)$-neighbour-transitive.

Moreover, we say that ${\mathcal{C}}$ is _neighbour-transitive_ , _$s$
-neighbour-transitive_, or _completely transitive_ , respectively, if
${\mathcal{C}}$ is ${\rm Aut}({\mathcal{C}})$-neighbour-transitive, $({\rm
Aut}({\mathcal{C}}),s)$-neighbour-transitive, or ${\rm
Aut}({\mathcal{C}})$-completely transitive, respectively.

It turns out that many famous codes have these symmetry properties. We mention
several of them in Example 2.4. We also give in Example 2.5 a simple example
of an explicit infinite family of completely transitive codes.

######  Example 2.4.

The following well-known codes are completely-transitive codes in the Hamming
graphs (see Section 1 for introductory material relating to the Hamming graphs
and see [18, Sections 5.1 and 5.2] for more examples):

  1. (1)

The perfect binary Golay code is a $12$-dimensional vector-subspace of
${\mathbb{F}}_{2}^{23}$ with minimum distance $7$ and covering radius $3$, and
its extended code is a $12$-dimensional vector-subspace of
${\mathbb{F}}_{2}^{24}$ with minimum distance $8$ and covering radius $4$.
These codes are $G$-completely transitive for $G=T\rtimes{\rm M}_{23}$ and
$G=T\rtimes{\rm M}_{24}$, respectively, where $T$ is the group of translations
by codewords in each case; see [84, p. 199]. This extended Golay code was used
by NASA’s Voyager spacecraft to send back to earth hundreds of colour pictures
of Jupiter and Saturn in their 1979, 1980, and 1981 fly-bys. Error correction
was vital to data transmission since memory constraints dictated offloading
data virtually instantly leaving no second chances, and the data needed to be
transmitted within a constrained telecommunications bandwidth.222See
en.wikipedia.org/wiki/Binary_Golay_code.

  2. (2)

The perfect ternary Golay code is a $6$-dimensional vector-subspace of
${\mathbb{F}}_{3}^{11}$ with minimum distance $5$ and covering radius $2$ and
its extended code is a $6$-dimensional vector-subspace of
${\mathbb{F}}_{3}^{12}$ with minimum distance $6$ and covering radius $3$.
These codes are $G$-completely transitive for $G=T\rtimes(2.{\rm M}_{11})$ and
$G=T\rtimes(2.{\rm M}_{12})$, respectively, where $T$ is the group of
translations by codewords in each case; see [46, p. 653].

  3. (3)

The Nordstrom–Robinson code is a non-linear code consisting of $256$ codewords
with minimum distance $5$ and covering radius $3$ in ${\mathbb{F}}_{2}^{15}$
and its extended code is a non-linear code consisting of $256$ codewords with
minimum distance $6$ and covering radius $4$ in ${\mathbb{F}}_{2}^{16}$. These
codes are $G$-completely transitive for $G\cong 2^{5}\rtimes{\rm A}_{8}\cong
2^{5}\rtimes{\rm GL}_{4}(2)$ and $G\cong 2^{5}\rtimes{\rm AGL}_{4}(2)$,
respectively; see [43].

######  Example 2.5.

Let $\Gamma$ be the graph with vertex set ${\mathbb{Z}}_{2n}$ and vertices
$i,j$ defined to be adjacent if $i-j=\pm 1$ (i.e., $\Gamma$ is a cycle of
length $2n$) and let ${\mathcal{C}}=\\{0,n\\}$. Then ${\rm
Aut}({\mathcal{C}})$ is generated by the rotation $i\mapsto i+n$ (for
$i\in{\mathbb{Z}}_{2n}$), and the reflection $i\mapsto-i$ (for
$i\in{\mathbb{Z}}_{2n}$). Hence ${\rm Aut}({\mathcal{C}})\cong C_{2}^{2}$ and
${\rm Aut}({\mathcal{C}})$ acts transitively on ${\mathcal{C}}$. We also have
${\mathcal{C}}_{i}=\\{\pm i,n\pm i\\}$ for each $i$ satisfying $1\leq i\leq
n/2$. Note that when $1\leq i<n/2$ the cardinality $|{\mathcal{C}}_{i}|=4$,
but when $n$ is even we have $|{\mathcal{C}}_{n/2}|=2$. In all cases ${\rm
Aut}({\mathcal{C}})$ acts transitively on ${\mathcal{C}}_{i}$ for each $i$
satisfying $1\leq i\leq n/2$, and thus ${\mathcal{C}}$ is completely
transitive.

Lemma 2.6, below, gives two additional equivalent conditions for
$(G,s)$-neighbour-transitivity for integers $s$ at most the error-correction
capacity. It is most useful for $s$-neighbour-transitive codes with ‘large’
minimum distance $\delta$, namely $\delta\geq 2s+1$. Applications of this
result are two-fold. Firstly, it is often simpler to prove $s$-neighbour-
transitivity of a code in terms of the ‘local action’ of the stabiliser of a
codeword $\alpha$ on the ball $B_{s}(\alpha)$ (Lemma 2.6(2)). Secondly, Lemma
2.6 often allows, in the case of a specific graph, for us to prove structural
results. We will see examples of such structural results in later sections.

######  Lemma 2.6.

Let ${\mathcal{C}}$ be a code in a graph $\Gamma$ such that ${\mathcal{C}}$
has error-correction capacity $e\geq 1$, let $G\leq{\rm Aut}({\mathcal{C}})$,
let $\alpha\in{\mathcal{C}}$, and let $s$ be an integer such that $1\leq s\leq
e$. Then the following are equivalent.

  1. $(1)$

${\mathcal{C}}$ is $(G,s)$-neighbour-transitive.

  2. $(2)$

$G$ acts transitively on ${\mathcal{C}}$ and, for each $i\in\\{1,\ldots,s\\}$,
the stabiliser $G_{\alpha}$ is transitive on $\Gamma_{i}(\alpha)$.

  3. $(3)$

For each $i\in\\{1,\ldots,s\\}$, $G$ acts transitively on the set
$\\{(\beta,\gamma)\mid\beta\in{\mathcal{C}},\gamma\in\Gamma_{i}(\beta)\\}$.

###### Proof.

Suppose that part (1) holds. Then, by Definition 2.3, $G$ acts transitively on
${\mathcal{C}}$ and transitively on ${\mathcal{C}}_{i}$, for each
$i\in\\{1,\ldots,s\\}$. Let $\gamma_{1},\gamma_{2}\in\Gamma_{i}(\alpha)$.
Then, by Lemma 2.1(2), $\gamma_{1},\gamma_{2}\in{\mathcal{C}}_{i}$ and so
there exists $g\in G$ such that $\gamma_{1}^{g}=\gamma_{2}$. By Lemma 2.1(1),
$\alpha$ is the unique element of ${\mathcal{C}}$ such that
$d(\alpha,\gamma_{1})=d(\alpha,\gamma_{2})=i$, and hence $\alpha^{g}=\alpha$,
that is, $g\in G_{\alpha}$. Thus $G_{\alpha}$ acts transitively on
$\Gamma_{i}(\alpha)$ and so part (1) implies part (2).

Suppose that part (2) holds. Let $1\leq i\leq s$ and let
$\beta\in{\mathcal{C}}$ and $\gamma\in\Gamma_{i}(\beta)$. Since $G$ acts
transitively on ${\mathcal{C}}$, there exists $g_{1}\in G$ such that
$(\beta,\gamma)^{g_{1}}=(\alpha,\gamma^{\prime})$ for some
$\gamma^{\prime}\in\Gamma_{i}(\alpha)$. Furthermore, $G_{\alpha}$ acts
transitively on $\Gamma_{i}(\alpha)$, and hence there exists $g_{2}\in
G_{\alpha}$ such that $(\gamma^{\prime})^{g_{2}}=\gamma_{1}$. Thus,
$(\beta,\gamma)^{g_{1}g_{2}}=(\alpha,\gamma_{1})$ and so part (2) implies part
(3).

Finally, suppose that part (3) holds. Let $i\in\\{1,\ldots,s\\}$, let
$\nu_{1},\nu_{2}\in{\mathcal{C}}_{i}$ and, as in Lemma 2.1, let
$\beta_{1},\beta_{2}$ be the unique elements of ${\mathcal{C}}$ such that
$d(\beta_{1},\nu_{1})=d(\beta_{2},\nu_{2})=i$. Then $(\beta_{j},\nu_{j})$ (for
$j=1,2$) lies in the set of pairs in part (3), and so there exists an element
$h\in G$ such that $(\beta_{1},\nu_{1})^{h}=(\beta_{2},\nu_{2})$. Thus
$\nu_{1}^{h}=\nu_{2}$ and $G$ acts transitively on ${\mathcal{C}}_{i}$. Also
by Lemma 2.1 part (3), for $\beta_{1},\beta_{2}\in{\mathcal{C}}$, there exist
$\nu_{1},\nu_{2}$ such that, for each $j=1,2$,
$\nu_{j}\in\Gamma_{i}(\beta_{j})$ so $(\beta_{j},\nu_{j})$ lies in the set of
pairs in part (3). Thus by part (3), we have
$(\beta_{1},\nu_{1})^{h}=(\beta_{2},\nu_{2})$ for some $h\in G$, and it
follows that $G$ is transitive also on ${\mathcal{C}}$. Thus part (3) implies
part (1). ∎

The case $s=1$ of Lemma 2.6 follows from [66, Theorem 1.2], noting that
$\delta({\mathcal{C}})\geq 3$ is equivalent to error capacity $e\geq 1$. A
$G$-neighbour-transitive code ${\mathcal{C}}$ with the property of Lemma
2.6(2) is called _strongly-incidence-transitive_ , and the theory of strongly
incidence transitive codes in Johnson graphs is developed in [66]. The
expository chapter [74] gives a recent account focusing especially on links
between such codes and a family of combinatorial designs called Delandtsheer
designs.

In the following proposition we assume the conclusion Lemma 2.6(2) holds with
$s=2$.

######  Proposition 2.7.

Let ${\mathcal{C}}$ be a non-trivial code with covering radius $\rho$ and
minimum distance $\delta$ in a connected graph $\Gamma$. Suppose that
$G\leq{\rm Aut}({\mathcal{C}})$ such that $G$ acts transitively on
${\mathcal{C}}$ and, for $\alpha\in{\mathcal{C}}$, $G_{\alpha}$ acts
transitively on each of $\Gamma_{1}(\alpha)$ and $\Gamma_{2}(\alpha)$. Then
one of the following holds:

  1. $(1)$

$\rho\geq 2$;

  2. $(2)$

$\rho=1$, $\delta=3$ and ${\mathcal{C}}$ is a perfect code.

  3. $(3)$

$\rho=1$, $\delta=2$, and either

    1. $(a)$

$\Gamma$ is bipartite and ${\mathcal{C}}$ is one of the biparts; or

    2. $(b)$

for every pair $\mu,\nu\in{\mathcal{C}}_{1}$ with $d(\mu,\nu)=1$ we have that
$\Gamma_{1}(\mu)\cap{\mathcal{C}}=\Gamma_{1}(\nu)\cap{\mathcal{C}}$.

###### Proof.

If $\rho=0$ then ${\mathcal{C}}=V(\Gamma)$ is a trivial code, but since this
is not the case we have $\rho\geq 1$. If $\rho\geq 2$ then part (1) holds.
Hence, we may assume that $\rho=1$. Since $\Gamma$ is connected, $G$ acts
transitively on ${\mathcal{C}}$ and $G_{\alpha}$ acts transitively on
$\Gamma_{1}(\alpha)$, it follows that
${\mathcal{C}}_{1}=\bigcup_{\beta\in{\mathcal{C}}}\Gamma_{1}(\beta)$. In
particular $\delta\geq 2$. If $\delta\geq 3$, then this union is disjoint, and
since $\rho=1,|{\mathcal{C}}|\geq 2$ and $\Gamma$ is connected, there must be
an edge between some vertex of $\Gamma_{1}(\beta)$ and some vertex of
$\Gamma_{1}(\beta^{\prime})$ for some distinct codewords $\beta$ and
$\beta^{\prime}$, and hence $d(\beta,\beta^{\prime})=3$, so $\delta=3$. This
implies that ${\mathcal{C}}$ has error-correction capacity $e=1$, and any pair
of balls of radius $1$ centered at distinct codewords is disjoint. Moreover,
since $\rho=1$, the vertex set $V(\Gamma)={\mathcal{C}}\cup{\mathcal{C}}_{1}$,
and hence the set of balls of radius $1$ centered at the codewords of
${\mathcal{C}}$ partitions $V(\Gamma)$. Thus ${\mathcal{C}}$ is perfect, as in
part (2).

Thus we may assume that $\delta=2$. Then, since $G$ acts transitively on
${\mathcal{C}}$ and $G_{\alpha}$ acts transitively on $\Gamma_{2}(\alpha)$, it
follows, for each codeword $\beta\in{\mathcal{C}}$, that $\Gamma_{2}(\beta)$
is contained in ${\mathcal{C}}$. If there are no edges between distinct
vertices of ${\mathcal{C}}_{1}$, then all edges of $\Gamma$ are incident with
a vertex of ${\mathcal{C}}$ and a vertex of ${\mathcal{C}}_{1}$, that is to
say, $\Gamma$ is bipartite and ${\mathcal{C}},{\mathcal{C}}_{1}$ form a
bipartition as in part (3)(a). Hence we may assume that there exists some pair
$\mu,\nu\in{\mathcal{C}}_{1}$ such that $d(\mu,\nu)=1$. For any such pair
$\mu,\nu$, suppose that $\gamma\in\Gamma_{1}(\mu)\cap{\mathcal{C}}$. Then
$(\gamma,\mu,\nu)$ is a path of length $2$ in $\Gamma$ so $d(\gamma,\nu)\leq
2$. We have shown that $\Gamma_{2}(\gamma)\subseteq{\mathcal{C}}$, and since
$\nu\in{\mathcal{C}}_{1}$ this implies that $d(\gamma,\nu)=1$, that is,
$\gamma\in\Gamma_{1}(\nu)\cap{\mathcal{C}}$ also. A similar argument holds
with $\mu$ and $\nu$ interchanged, and hence
$\Gamma_{1}(\mu)\cap{\mathcal{C}}=\Gamma_{1}(\nu)\cap{\mathcal{C}}$ and part
(3)(b) holds. ∎

In Section 5 we apply Proposition 2.7 to codes in Hamming graphs (see Remark
5.35). In that case Proposition 2.7(3)(b) never holds, so we are able to make
much stronger conclusions. We pose the following problem related to this.

######  Problem 2.8.

Investigate codes satisfying Proposition 2.7(3)(b).

####  3 Elusive codes

In this subsection we make a short commentary on the concept of neighbour-
transitivity. Let ${\mathcal{C}}$ be a code in a connected graph $\Gamma$ such
that the minimum distance $\delta({\mathcal{C}})\geq 3$ so, by Lemma 2.1, the
set of code neighbours is the disjoint union
${\mathcal{C}}_{1}=\cup_{\alpha\in{\mathcal{C}}}\Gamma_{1}(\alpha)$. It turns
out that ${\mathcal{C}}_{1}$ determines the code ${\mathcal{C}}$ if
$\delta({\mathcal{C}})$ is large enough and if the graph $\Gamma$ is _reduced_
, that is, if:

$\Gamma_{1}(\alpha)=\Gamma_{1}(\alpha^{\prime})$ if and only if
$\alpha=\alpha^{\prime}$. (3)

We note that all the graphs we consider in the chapter are reduced in this
sense.

######  Lemma 2.9.

Let ${\mathcal{C}}_{1}$ be the set of code-neighbours of a non-trivial code in
a connected regular reduced graph $\Gamma$. If $\delta({\mathcal{C}})\geq 5$
then ${\mathcal{C}}=\\{\alpha\in
V(\Gamma)\mid\Gamma_{1}(\alpha)\subseteq{\mathcal{C}}_{1}\\}$, and hence
${\mathcal{C}}_{1}$ determines ${\mathcal{C}}$.

###### Proof.

Let $X:=\\{\alpha\in
V(\Gamma)\mid\Gamma_{1}(\alpha)\subseteq{\mathcal{C}}_{1}\\}$. Since
$\delta({\mathcal{C}})\geq 5$, ${\mathcal{C}}_{1}$ contains
$\Gamma_{1}(\alpha)$ for each codeword $\alpha$ and hence
${\mathcal{C}}\subseteq X$. We claim that equality holds. Suppose to the
contrary that $\alpha\in X\setminus{\mathcal{C}}$, and let
$\beta,\beta^{\prime}$ be distinct vertices in
$\Gamma_{1}(\alpha)\subseteq{\mathcal{C}}_{1}$. By the definition of
${\mathcal{C}}_{1}$ there are codewords
$\gamma,\gamma^{\prime}\in{\mathcal{C}}$ such that
$(\gamma,\beta,\alpha,\beta^{\prime},\gamma^{\prime})$ is a path in $\Gamma$
of length $4$. Since the minimum distance $\delta({\mathcal{C}})\geq 5$, it
follows that $\gamma=\gamma^{\prime}$. For fixed $\alpha,\beta$ and $\gamma$,
letting $\beta^{\prime}$ range over $\Gamma_{1}(\alpha)$, we see that
$\Gamma_{1}(\alpha)=\Gamma_{1}(\gamma)$, which is a contradiction since
$\Gamma$ is reduced. Thus $X={\mathcal{C}}$. ∎

It follows from Lemma 2.9 that, under the conditions of that lemma, the
setwise stabilisers in ${\rm Aut}(\Gamma)$ of ${\mathcal{C}}$ and of
${\mathcal{C}}_{1}$ are equal, that is to say, ${\rm Aut}({\mathcal{C}})={\rm
Aut}({\mathcal{C}}_{1})$. Then since ${\mathcal{C}}_{1}$ is the disjoint union
$\cup_{\alpha\in{\mathcal{C}}}\Gamma_{1}(\alpha)$, if ${\rm
Aut}({\mathcal{C}}_{1})$ is transitive on ${\mathcal{C}}_{1}$ then it must
also be transitive on ${\mathcal{C}}$. Thus ${\mathcal{C}}$ is neighbour-
transitive if and only if ${\rm Aut}({\mathcal{C}}_{1})$ is transitive on
${\mathcal{C}}_{1}$; and this would be a simplification of Definition 2.3 of
neighbour-transitivity.

However for smaller $\delta({\mathcal{C}})$, it is possible for
${\mathcal{C}}_{1}$ to be the set of code neighbours of more than one code.
Such a code ${\mathcal{C}}$ is said to be _elusive_. An infinite family of
elusive neighbour-transitive codes in binary Hamming graphs (see Definition
4.1) was described by Gillespie and the second author in [40, Section 5], and
the smallest code in the family is given in Example 2.10.

######  Example 2.10.

Let $\Gamma=H(4,2)$ (see Definition 4.1) and write the vertex set as
$V\Gamma=F\times F$ with $F=\mathbb{F}_{2}^{2}$. Define

$\displaystyle{\mathcal{C}}$ $\displaystyle:=\\{(0,0,0,0),(1,1,1,1)\\}$
$\displaystyle\mathcal{C^{\prime}}$
$\displaystyle:=\\{(0,0,0,0),(1,0,1,0),(0,1,0,1),(1,1,1,1)\\}$
$\displaystyle\mathcal{X}$
$\displaystyle:=\\{(\beta,\beta^{\prime}),(\beta^{\prime},\beta)\mid\beta\in\\{(0,0),(1,1)\\},\beta^{\prime}\in\\{(0,1),(1,0)\\}\\}.$

Then ${\mathcal{C}}$ and $\mathcal{C^{\prime}}$ are both linear codes in
$\Gamma$, with $\delta({\mathcal{C}})=4$ and $\delta(\mathcal{C^{\prime}})=2$.
Further, $\mathcal{X}$ is the set of code neighbours of both of the codes
${\mathcal{C}}$ and $\mathcal{C^{\prime}}$; and the code ${\mathcal{C}}$ is
neighbour-transitive.

Two new constructions for infinite families of elusive neighbour-transitive
codes in $H(n,q)$ were given by Gillespie and the authors in [55, Sections 3.1
and 3.2], this time with minimum distance $3$. The constructions produce
_elusive pairs_ $({\mathcal{C}},X)$, where ${\mathcal{C}}$ is an elusive code
and $X\leq{\rm Aut}({\mathcal{C}}_{1})$ such that $X$ does not fix
${\mathcal{C}}$ setwise. For these examples there were precisely two distinct
images of ${\mathcal{C}}$ under elements of $X$, but very recent constructions
by the first author in [52, Theorem 1.1 and 1.2] show that the number of
images can be arbitrarily large, answering [55, Question 1.4].

A _spherical bitrade_ in a graph $\Gamma$ is a pair
$({\mathcal{C}},{\mathcal{C}}^{\prime})$ of codes in $\Gamma$ with the
property that for any $\alpha\in V(\Gamma)$ we have
$|\Gamma_{1}(\alpha)\cap{\mathcal{C}}|=|\Gamma_{1}(\alpha)\cap{\mathcal{C}}^{\prime}|\in\\{0,1\\}$.
Spherical bitrades are investigated in [69] in relation to a type of switching
construction for obtaining new perfect codes from known ones. If
${\mathcal{C}}$ is an elusive code with $\delta({\mathcal{C}})\geq 3$, and
$g\in{\rm Aut}({\mathcal{C}}_{1})\setminus{\rm Aut}({\mathcal{C}})$, then
$({\mathcal{C}},{\mathcal{C}}^{g})$ is a spherical bitrade. As is pointed out
in [69], the examples of spherical bitrades in $H(q,q)$ given in [69, Theorem
2] were first constructed as elusive codes in [55, Example 1]. Moreover, one
application of the product construction of [69, Theorem 1] is to produce
spherical bitrades in $H(kq,q)$ for arbitrary $k$; examples of elusive codes
in $H(kq,q)$ were first given in [55, Lemma 3.9]. It is worth noting also that
if elusive codes are used as input for [69, Theorem 1] then the resulting
codes are also elusive.

An extension of the concept of an elusive code relevant to $s$-neighbour-
transitive codes was introduced in [52]: a code ${\mathcal{C}}$ in a graph
$\Gamma$ is said to be _$s$ -elusive_ if there exists a code
${\mathcal{C}}^{\prime}$ distinct from ${\mathcal{C}}$, but equal to the image
of ${\mathcal{C}}$ under an element of ${\rm Aut}(\Gamma)$, such that the sets
of $s$-neighbours of ${\mathcal{C}}$ and ${\mathcal{C}}^{\prime}$ are the
same. Interesting new examples were found in [52, Theorem 1.1] for $s=1,2,3$
developed from Reed–Muller codes, Preparata codes, and binary Golay codes. It
would be interesting to know of examples of $s$-elusive codes in graphs other
than the Hamming graphs.

######  Problem 2.11.

Find $s$-elusive, neighbour-transitive codes ($s\geq 1$) in other interesting
distance-regular graphs, or show that none exist.

####  4 $s$-Neighbour-transitive codes and $s$-distance-transitive graphs

There is a beautiful link between $(G,s)$-neighbour-transitive codes and
_$(G,s)$ -distance-transitive graphs_, namely connected graphs $\Gamma=(V,E)$
for which $G\leq{\rm Aut}(\Gamma)$ is transitive on the distance sets
$\Gamma_{i}:=\\{(\alpha,\beta)\mid d(\alpha,\beta)=i\\}$, for $i=0,1,\dots,s$.
The link involves a _quotient graph_ $\Gamma_{N}$ modulo a normal subgroup
$N\unlhd G$: the quotient $\Gamma_{N}$ is the graph with vertices the
$N$-orbits in $V$ such that distinct $N$-orbits $U,U^{\prime}$ form an edge of
$\Gamma_{N}$ provided there exist $\alpha\in U$ and $\beta\in U^{\prime}$ such
that $\\{\alpha,\beta\\}\in E$. For a vertex $\alpha\in V$, we denote the
$N$-orbit containing $\alpha$ by $\alpha^{N}:=\\{\alpha^{x}\mid x\in N\\}$.

######  Proposition 2.12.

Let $\Gamma=(V,E)$ be a graph and $G\leq{\rm Aut}(\Gamma)$ such that $G$ acts
transitively on $V$, and let $N\lhd G$ be intransitive on $V$. Suppose further
that, for some $\alpha\in V$, the set ${\mathcal{C}}=\alpha^{N}$ is a
$(G_{{\mathcal{C}}},s)$-neighbour-transitive code in $\Gamma$. Then the
quotient graph $\Gamma_{N}$ is $(G/N,s)$-distance-transitive.

###### Proof.

Since $N\lhd G$ and $G$ is transitive on $V$, it follows that $G$ acts
transitively on the set of $N$-orbits in $V$, that is to say, the vertex set
$V(\Gamma_{N})$ of $\Gamma_{N}$, see [75, Lemma 2.20]. As $N$ leaves each of
its orbits invariant, $N$ is contained in the kernel of this $G$-action and
the quotient group $G/N$ acts vertex-transitively on $\Gamma_{N}$. Recall that
${\mathcal{C}}=\alpha^{N}$ is one of the $N$-orbits, and as a code in
$\Gamma$, it is $(G_{{\mathcal{C}}},s)$-neighbour-transitive, by assumption.

Let $U,U^{\prime}$ be adjacent vertices of $\Gamma_{N}$, and let
$\\{\alpha_{1},\alpha_{2}\\}\in E$ such that $\alpha_{1}\in U$ and
$\alpha_{2}\in U^{\prime}$. Since $N$ acts transitively on $U$ and on
$U^{\prime}$, it follows that every vertex of $U$ is adjacent in $\Gamma$ to
some vertex in $U^{\prime}$, and every vertex of $U^{\prime}$ is adjacent in
$\Gamma$ to some vertex in $U$.

Let $X,Y$ be vertices of $\Gamma_{N}$ at distance $i$ in $\Gamma_{N}$ from
${\mathcal{C}}$, where $1\leq i\leq s$. Then, arguing as in the preceding
paragraph, there exist vertices $\beta\in X$ and $\gamma\in Y$ such that there
are paths of length $i$ in $\Gamma$ from $\alpha$ to each of $\beta$ and
$\gamma$. Suppose that there exists a codeword
$\alpha^{\prime}\in{\mathcal{C}}$ such that there is a path of length $j$ from
$\alpha^{\prime}$ to $\beta$ with $0<j<i$. Then ${\mathcal{C}}$ and $X$ would
be at distance less than $i$ in $\Gamma_{N}$, which is not the case. Hence
each codeword of ${\mathcal{C}}$ has distance at least $i$ from $\beta$, and
it follows that $\beta\in{\mathcal{C}}_{i}$. By an identical argument
$\gamma\in{\mathcal{C}}_{i}$. Since ${\mathcal{C}}$ is
$(G_{{\mathcal{C}}},s)$-neighbour-transitive, there exists an element $g\in
G_{{\mathcal{C}}}$ such that $\beta^{g}=\gamma$. Since $G$ permutes the
$N$-orbits among themselves, this means that $g$ maps the $N$-orbit $X$
containing $\beta$ to the $N$-orbit $Y$ containing $\gamma$. Thus
$G_{{\mathcal{C}}}$ induces a transitive action on the vertices of
$\Gamma_{N}$ at distance $i$ from ${\mathcal{C}}$. Since we have already shown
that $\Gamma_{N}$ is vertex-transitive, and since $N$ is in the kernel of the
$G$-action on $\Gamma_{N}$, it follows that $G/N$ acts transitively on the set
of ordered pairs of $\Gamma_{N}$-vertices at distance $i$. Finally since this
holds for all $i\leq s$, the result follows. ∎

On the one hand this observation can be used to produce $s$-distance-
transitive graphs from certain $s$-neighbour-transitive codes in Hamming
graphs:

######  Example 2.13.

Let ${\mathcal{C}}$ be an $s$-neighbour-transitive and linear code in the
Hamming graph $H(n,q)$ (see Section 1 for the definitions of ‘linear’ and
$H(n,q)$). Moreover, let $T_{\mathcal{C}}$ be the group of translations by
codewords of ${\mathcal{C}}$ and let $H={\rm Aut}({\mathcal{C}})_{\mathbf{0}}$
be the stabiliser of the codeword ${\mathbf{0}}\in{\mathcal{C}}$. Then we may
apply Proposition 2.12 with $N=T_{\mathcal{C}}$, so that
${\mathcal{C}}={\mathbf{0}}^{N}$, and $G=T_{V(\Gamma)}\rtimes H$, where
$T_{V(\Gamma)}\cong{\mathbb{F}}_{q}^{n}$ is the group of translations by all
vectors in $V(\Gamma)$, to obtain a $(G/N,s)$-distance-transitive graph
$\Gamma_{N}$. For examples of such codes ${\mathcal{C}}$, with $s=2$, see
Theorem 5.21(3) and Propositions 5.29–5.34.

On the other hand, there are many $(G,s)$-distance-transitive graphs $\Gamma$
known for which the group $G$ has a nontrivial vertex-intransitive normal
subgroup $N$, and the question arising here is whether an $N$-orbit provides
an example of an $s$-neighbour-transitive code:

######  Example 2.14.

  1. (1)

Let $\Gamma$ be a $(G,2)$-arc-transitive graph333That is, $G$ acts
transitively on the set of all paths $(u,v,w)$ in $\Gamma$ with $u\neq w$. and
let $N$ be a normal subgroup of $G$ with at least $3$ orbits on $V(\Gamma)$.
It was shown by the second author in [72, Theorem 4.1] that the quotient
$\Gamma_{N}$, as defined above, is $(G/N,2)$-arc-transitive and the graph
$\Gamma$ is a cover of $\Gamma_{N}$. This means that, for each $\alpha\in
V(\Gamma)$, the code ${\mathcal{C}}=\alpha^{N}$ in $\Gamma$ has minimum
distance at least the girth of $\Gamma_{N}$. Note that

$\rho({\mathcal{C}})=1$ $\Longleftrightarrow$ $\Gamma_{N}$ is a complete graph
$\Longleftrightarrow$ $\delta({\mathcal{C}})=3$.

In all other cases $\Gamma_{N}$ has girth at least $4$, so
$\delta({\mathcal{C}})\geq 4$, $\rho({\mathcal{C}})\geq 2$, and
${\mathcal{C}}$ is $(G_{\mathcal{C}},2)$-neighbour-transitive.

  2. (2)

Let $\Gamma$ be an antipodal $G$-distance-transitive graph with diameter
$\delta$. Then an antipodal block ${\mathcal{C}}$ (that is, a maximal set of
vertices mutually at distance $\delta$) is a code in $\Gamma$ with minimum
distance $\delta$, and usually ${\mathcal{C}}$ is an orbit of a normal
subgroup of $G$. For example, $(G_{\mathcal{C}},1)$-neighbour-transitive codes
${\mathcal{C}}$ with $\delta=3$ may be obtained in this way from antipodal
distance-transitive covers of complete graphs, and these graphs have been
classified in [47]. Similarly $(G_{\mathcal{C}},2)$-neighbour-transitive codes
${\mathcal{C}}$ with $\delta=4$ arise in this way from antipodal distance-
transitive covers of complete bipartite graphs, which are classified in [58].

Regarding the examples in Example 2.14(1), we observe that for a $(G,2)$-arc-
transitive graph $\Gamma$, a vertex-stabiliser $G_{\alpha}$ is $2$-transitive
on $\Gamma_{1}(\alpha)$ [73, Lemma 9.4] and in particular is primitive, so
$\Gamma$ is $G$-locally-primitive. The 2-arc-transitivity condition can be
weakened to local primitivity, and each code of the form
${\mathcal{C}}=\alpha^{N}$, for an intransitive normal subgroup $N$ of $G$,
will be neighbour-transitive with $\delta\geq 3$ (since $\Gamma$ covers
$\Gamma_{N}$ by [73, Theorem 10.2]). Weakening the condition further to
$\Gamma$ being $G$-locally-quasiprimitive will yield neighbour-transitive
codes ${\mathcal{C}}=\alpha^{N}$ with $\delta\geq 2$, see [64, Theorem 1.3].

In seeking examples, if we start with a $(G,s)$-distance-transitive graph
$\Gamma$ and a normal subgroup $N\lhd G$ with at least three vertex-orbits,
then the normal quotient $\Gamma_{N}$ is always $(G/N,s)$-distance-transitive
[33, Theorem 1.1]. It would be interesting to have examples for Proposition
2.12 where the graph $\Gamma$ is not itself $(G,s)$-distance-transitive.

######  Problem 2.15.

Find graph-group pairs $(\Gamma,G)$ such that $G\leq{\rm Aut}(\Gamma)$ is
vertex-transitive, $\Gamma$ is not $(G,s)$-distance-transitive, and for some
vertex-intransitive subgroup $N\lhd G$ the code ${\mathcal{C}}=\alpha^{N}$ is
$(G_{\mathcal{C}},s)$-neighbour-transitive – thus giving a $(G/N,s)$-distance-
transitive quotient graph $\Gamma_{N}$.

####  5 Further techniques for analysing codes

We now define a concept that has proved useful for keeping track of code
invariants, especially for analysing $s$-neighbour-transitive codes.

######  Definition 2.16.

Let $G$ be a group acting on a set $\Omega$ and let $\iota:\Omega\rightarrow
S$, for some set $S$. If for all $\alpha\in\Omega$ and $g\in G$ the equality
$\iota(\alpha)=\iota(\alpha^{g})$ holds, then $\iota$ is called _$G$
-invariant_. The elements of $S$ are called _types_ , namely if
$\alpha\in\Omega$, then we say that $\alpha$ has _type_ $\iota(\alpha)$.

The archetypal example of a $G$-invariant map $\iota:\Omega\rightarrow S$ is
to take $S$ as the set of $G$-orbits in $\Omega$ and define
$\iota(\alpha)=\alpha^{G}$, for each $\alpha\in\Omega$. We consider another
example below for the Johnson graphs which are defined in Definition 4.5. Note
that this example will be typical for us, in that $\Omega$ will often be the
vertex set of a graph containing a code of interest.

######  Example 2.17.

Let ${\mathcal{C}}$ be a $G$-neighbour-transitive code in the Johnson graph
$J(v,k)$ (see Section 2) with underlying set ${\mathcal{V}}$ such that $G$
fixes setwise some subset $U\subseteq{\mathcal{V}}$ with $0<|U|<v$. For a
vertex $\alpha$ of $J(v,k)$ define $\iota(\alpha)=|\alpha\cap U|$. Let $g\in
G$. Then, since $U^{g}=U$, it follows that $\iota(\alpha^{g})=|\alpha^{g}\cap
U|=|(\alpha\cap U)^{g}|=\iota(\alpha)$. Hence $\iota$ is $G$-invariant.

In Example 2.17, since $G$ acts transitively on ${\mathcal{C}}$, every element
of ${\mathcal{C}}$ has the same type. The next result expands on this
observation.

######  Lemma 2.18.

Let ${\mathcal{C}}$ be a $(G,s)$-neighbour-transitive code with minimum
distance $\delta$ in the connected graph $\Gamma=(V,E)$, let $\iota$ be a
$G$-invariant map on $V$, let $\alpha\in{\mathcal{C}}$ and let
$i\in\\{0,1,\ldots,s\\}$. Then the following hold.

  1. $(1)$

All vertices in ${\mathcal{C}}_{i}$ have the same type.

  2. $(2)$

$B_{i}(\alpha)$ contains at most $i+1$ different types of vertices.

  3. $(3)$

If $\delta\geq 2i$ then all vertices in $\Gamma_{i}(\alpha)$ have the same
type.

###### Proof.

Let $\nu_{1},\nu_{2}\in{\mathcal{C}}_{i}$. By Definition 2.3, $G$ acts
transitively on ${\mathcal{C}}_{i}$ and hence there exists $g\in G$ such that
$\nu_{1}^{g}=\nu_{2}$. Since $\iota$ is $G$-invariant,
$\iota(\nu_{1})=\iota(\nu_{1}^{g})=\iota(\nu_{2})$. This proves part (1).
Next,
$B_{i}(\alpha)\subseteq{\mathcal{C}}\cup{\mathcal{C}}_{1}\cup\cdots\cup{\mathcal{C}}_{i}$.
By part (1), the type of any vertex $\mu\in B_{i}(\alpha)$ is the same as the
type of a vertex in ${\mathcal{C}}_{j}$, for some $j\in\\{0,1,\ldots,i\\}$.
Hence there are at most $i+1$ possibilities for $\iota(\mu)$, and part (2) is
proved. Finally, if $\beta\in\Gamma_{i}(\alpha)$ and $\delta\geq 2i$ then, by
the triangle inequality, $d(\beta,\gamma)\geq i$ for all
$\gamma\in{\mathcal{C}}\setminus\\{\alpha\\}$, and hence
$\beta\in{\mathcal{C}}_{i}$. Thus
$\Gamma_{i}(\alpha)\subseteq{\mathcal{C}}_{i}$, and so, by part (1), all
vertices in $\Gamma_{i}(\alpha)$ have the same type, proving part (3). ∎

Lemma 2.18 was used implicitly in [66] to classify the codes in Example 2.17,
that is, $G$-neighbour-transitive codes in $J(v,k)$ (see Section 2) where $G$
acts intransitively on ${\mathcal{V}}$. We include a different proof of this
result, below, in order to illustrate how Lemma 2.18 may be applied. For a set
$U$ and integer $j\leq|U|$, we denote by $\binom{U}{j}$ the set of all
$j$-element subsets of $U$.

######  Theorem 2.19.

[66, Proposition 3.3] Let ${\mathcal{C}}$ be a non-trivial $G$-neighbour-
transitive code in $\Gamma=J(v,k)$, where $2\leq k<v$, and suppose that
$U\subseteq{\mathcal{V}}$ is such that $G$ fixes $U$ setwise and $0<|U|<v$.
Then ${\mathcal{C}}$ has minimum distance $1$ and, possibly replacing $U$ by
${\mathcal{V}}\setminus U$, one of the following holds.

  1. $(1)$

$k<|U|$ and ${\mathcal{C}}=\\{\alpha\in V(\Gamma)\mid\alpha\subseteq U\\}$;

  2. $(2)$

$k>|U|$ and ${\mathcal{C}}=\\{\alpha\in V(\Gamma)\mid U\subseteq\alpha\\}$.

###### Proof.

We consider the type $\iota(\alpha)=|\alpha\cap U|$ of a vertex $\alpha$ of
$\Gamma$, as in Example 2.17. By Lemma 2.18, all vertices in ${\mathcal{C}}$
have the same type, and all vertices in ${\mathcal{C}}_{1}$ have the same
type. Moreover, for every $\alpha\in{\mathcal{C}}$,
$\Gamma_{1}(\alpha)\subseteq{\mathcal{C}}\cup{\mathcal{C}}_{1}$, and hence
either every vertex of $\Gamma_{1}(\alpha)$ has the same type, or
$\delta({\mathcal{C}})=1$ and the vertices in $\Gamma_{1}(\alpha)$ have one of
precisely two different types. Note that $\iota(\alpha)\leq|\alpha|=k$, and
equality holds if and only if $\alpha\subseteq U$.

First, suppose that $\iota(\alpha)=k$ for all $\alpha\in{\mathcal{C}}$. Then
$\cup_{\alpha\in{\mathcal{C}}}\,\alpha\subseteq U$ and since ${\mathcal{C}}$
is non-trivial (i.e., $|{\mathcal{C}}|\geq 2$) we have $|U|>k$. Let
$\alpha\in{\mathcal{C}}$. Then $\alpha\subseteq U$ and $\Gamma_{1}(\alpha)$
consists of the set of all vertices $\nu\cup\\{a\\}$, where
$\nu\in{\alpha\choose k-1}$ and $a\in{\mathcal{V}}\setminus\alpha$. Moreover,
$\iota(\nu\cup\\{a\\})=k$ if $a\in U$ (there are $k(|U|-k)>0$ such pairs
$(\nu,a)$) and $\iota(\nu\cup\\{a\\})=k-1$ if $a\notin U$ (there are
$k(v-|U|)>0$ such pairs $(\nu,a)$). Hence $\Gamma_{1}(\alpha)$ contains
precisely two types of vertices and so, by Lemma 2.18,
$\delta({\mathcal{C}})=1$ and, for every codeword $\alpha\in{\mathcal{C}}$,
each element of $\Gamma_{1}(\alpha)$ having type $k$ is again a codeword.
Observe that the induced subgraph of $\Gamma$ on the set ${U\choose k}$ is
isomorphic to $J(|U|,k)$ and is thus connected, and hence the set ${U\choose
k}$ is precisely the set of vertices of type $k$; the previous sentence
implies that ${U\choose k}\subseteq{\mathcal{C}}$. Hence
${\mathcal{C}}={U\choose k}$ and part (2) holds.

Thus we may assume that codewords $\alpha$ have (constant) type
$\iota(\alpha)=\ell$ strictly less than $k$. Suppose next that $\ell=|U|$.
This implies that $|U|<k$. Let $\alpha\in{\mathcal{C}}$. Then $U\subset\alpha$
and $\Gamma_{1}(\alpha)$ consists of the set of all vertices $\nu\cup\\{a\\}$,
where $\nu\in{\alpha\choose k-1}$ and $a\in{\mathcal{V}}\setminus\alpha$.
Moreover, $\iota(\nu\cup\\{a\\})=\ell$ if $\nu\cap U=\alpha\cap U=U$ (there
are $(k-\ell)(v-k)>0$ such pairs $(\nu,a)$) and $\iota(\nu\cup\\{a\\})=\ell-1$
if $\nu\cap U\neq\alpha\cap U$ (there are $\ell(v-k)>0$ such pairs $(\nu,a)$).
Hence $\Gamma_{1}(\alpha)$ contains precisely two types of vertices, and by
Lemma 2.18, each element of $\Gamma_{1}(\alpha)$ of type $\ell$ is again a
codeword. Now the induced subgraph of $\Gamma$ on the set of vertices
$\\{\alpha\in V(\Gamma)\mid U\subseteq\alpha\\}$ is isomorphic to
$J(v-\ell,k-\ell)$ with vertex set ${{{\mathcal{V}}\setminus
U}\choose{k-\ell}}$. Since $J(v-\ell,k-\ell)$ is connected, we deduce that
$\\{\alpha\in V(\Gamma)\mid U\subseteq\alpha\\}\subseteq{\mathcal{C}}$ and in
fact equality holds as in part (1).

This leaves the case where $0\leq\ell<\min\\{|U|,k\\}$. If $\ell=0$, then all
codewords $\alpha$ are contained in ${\mathcal{V}}\setminus U$, and replacing
$U$ with ${\mathcal{V}}\setminus U$, the argument in the previous paragraph
shows that part (1) holds. Similarly, if $v-|U|=k-\ell$ then all codewords
$\alpha$ contain ${\mathcal{V}}\setminus U$, and replacing $U$ with
${\mathcal{V}}\setminus U$, the argument in paragraph two of the proof shows
that part (2) holds. Thus we may assume in addition that $0<\ell$ and
$v-|U|>k-\ell$. However in this case a codeword $\alpha$ is adjacent to
vertices of types $\ell-1,\ell$ and $\ell+1$. This contradicts Lemma 2.18(2),
completing the proof. ∎

###  3 Commentary on the origins of completely-transitive codes

In a 1987 preprint [83, Section 7], Patrick Solé introduced the term
‘completely transitive code’ in the context of binary linear codes. His
concept is different in a number of respects from that introduced in
Definition 2.3(3), and we comment more below. To the best of our knowledge,
the notion of a ‘completely-transitive code in a graph’ dates back to 1988,
when Chris Godsil suggested to the second author the study of completely-
transitive codes in Johnson graphs (see Definition 4.5). Since a subset of
vertices in a Johnson graph $J(v,k)$ is a set of $k$-subsets of the underlying
$v$-set ${\mathcal{V}}$, each code ${\mathcal{C}}$ in $J(v,k)$ has a natural
interpretation as a ‘design’ with point-set ${\mathcal{V}}$ and with constant
block size $k$. Thus completely-transitive codes in Johnson graphs were first
called _completely-transitive designs_. In 1988, Bill Martin was a PhD student
of Chris Godsil studying completely regular designs (completely regular codes
in $J(v,k)$) and Chris’s hope was that by studying the more restricted family
of completely transitive designs we might discover new examples, and
characterisations. An account of this investigation, dating from 1997, can be
found in [48]. It was never published as a journal article, but was posted on
the arXiv in 2014 because of repeated requests for copies.

When regarded as codes in the Hamming graph $H(n,2)$ (Definition 4.1), the
‘completely-transitive codes’ defined by Solé [83, Section 7], or see [84] for
the 1990 published version, are precisely those binary linear codes
${\mathcal{C}}\subseteq\mathbb{F}_{2}^{n}$ that are $G$-completely-transitive
in the sense of Definition 2.3(3) for the subgroup $G=T\rtimes G_{0}$ of
affine transformations, where $T$ is the group of translations of
$\mathbb{F}_{2}^{n}$ by codewords in ${\mathcal{C}}$, and $G_{0}$ is the
subgroup of permutation matrices which leave ${\mathcal{C}}$ invariant. Note
that $G_{0}$ is the group traditionally regarded as the automorphism group of
a linear code. In [84, Section 7], Solé gave examples of such codes, and also
a necessary condition, and a sufficient condition (separate conditions), for
complete transitivity in terms of the natural action of $G_{0}$ as a
permutation group on a set of $n$ points. Shortly afterwards, in 1991, Rifà
and Pujol [76] (or see [18, Proposition 13]) showed that, for a binary linear
completely transitive code ${\mathcal{C}}$ of length $n$, the natural coset
graph on the set $\mathbb{F}_{2}^{n}/{\mathcal{C}}$ of additive cosets of
${\mathcal{C}}$ in $\mathbb{F}_{2}^{n}$ is distance-transitive. Solé’s concept
of complete transitivity extends naturally to linear codes in $H(n,q)$ for
arbitrary prime powers $q$, as does the link with distance transitivity of the
quotient graph $\mathbb{F}_{q}^{n}/{\mathcal{C}}$ (see Proposition 2.12 with
$s=\rho({\mathcal{C}})$). For this reason, in order to distinguish Solé’s
completely transitive linear codes from the more general family of completely
transitive codes in Hamming graphs, Solé’s notion is sometimes called _coset-
complete-transitivity_ , see [45, 46]. For linear codes in $H(n,q)$, where $q$
is a prime power, the concepts of complete transitivity and coset-complete
transitivity are equivalent if $q\leq 3$ and definitely not equivalent if
$q=7$ or $q\geq 9$, see [46, Theorem 1.3 and Example 3.1].

Giudici, in his masters thesis [45] and a joint paper with the second author
[46], introduced the notion given in Definition 2.3 of a $G$-completely-
transitive code in a Hamming graph $H(n,q)$ for arbitrary $n$ and $q$, and
made a general study of the structure of such graphs. He gave families of
examples, and significant structural descriptions, which pointed to the
importance of those codes in $H(n,q)$ for which the automorphism group $G$
induces a transitive action on the set of $n$ entries of codewords, see [46,
Sections 4, 5 and 6]. A recent survey article of Borges, Rifa and Zinoviev
contains an overview of this and more recent work, see in particular [18,
Section 3] on coset-completely transitive codes.

The error-correcting capacity $e$ of a binary coset-completely transitive code
was shown by Borges, Rifà and Zinoviev to be no larger than three, [16, 17] or
see [18, Theorem 12], but there are families of examples with unbounded
covering radius (with $e=1$) [78]. We will see that similar statements can be
made about the more general family of $s$-neighbour-transitive codes. In
particular we will prove the following result in Section 4.

######  Theorem 3.1.

Suppose that ${\mathcal{C}}$ is an $s$-neighbour-transitive code in the
Hamming graph $H(n,q)$ such that ${\mathcal{C}}$ has error-correcting capacity
$e$ with $\min\\{e,s\\}\geq 4$. Then $n\geq 9$, $q=2$,
$e=\lfloor\frac{n-1}{2}\rfloor$, $s=\lceil\frac{n-1}{2}\rceil$, and
${\mathcal{C}}$ is equivalent to the binary repetition code ${\rm Rep}_{n}(2)$
(see Definition $\ref{def:productandrepetition}(3)$).

Borges, Rifà and Zinoviev showed further that coset-completely transitive
codes may be obtained via some innovative combinatorial methods, such as a
Kronecker product construction ([79] or see [18, Section 5.5]), or a lifting
procedure ([80] or see [18, Section 5.2]), while Gill, Gillespie and Semeraro
[37, Theorem C] constructed new families from the incidence matrices of
certain designs. Also, sometimes a well-known family of codes may contain only
a few codes which are completely transitive. For example, a Preparata code of
length $n$, or its extension, is completely transitive if and only if $n=15$,
([43] or see [18, Theorem 15]); these exceptional completely transitive codes
are the Nordstrom–Robinson codes.

In this chapter we will see that a similar situation arises for the larger
families of neighbour-transitive, and 2-neighbour-transitive codes, where
substructures in graphs, and in finite geometries such as generalised
quadrangles, have been used in constructions, and where group theory,
sometimes relying on the finite simple group classification, has been applied
to achieve classifications.

###  4 Graphs of interest

In this section we introduce several families of graphs. For each family we
provide at least one example of a code arising from an interesting
combinatorial or algebraic structure. Most of these families are analysed
further in later sections. We have already informally met the first family of
graphs, the Hamming graphs. They will also receive the most attention
throughout the chapter.

####  1 Hamming graphs

######  Definition 4.1.

Let ${\mathcal{N}}$ be a set of size $n$ and ${\mathcal{Q}}$ a set of size
$q$, where $n,q\geq 2$. We define the _Hamming graph_ $H(n,q)$ in the
following two equivalent, but dual, ways:

  1. (1)

The vertex set of $H(n,q)$ is the set of all $n$-tuples
$(a_{1},\ldots,a_{n})$, where $a_{i}\in{\mathcal{Q}}$ for each
$i\in{\mathcal{N}}$ and we have identified ${\mathcal{N}}$ with
$\\{1,\ldots,n\\}$. Two such $n$-tuples form an edge if and only if they
differ in precisely one position.

  2. (2)

The vertex set of $H(n,q)$ is the set of all functions
$\alpha:{\mathcal{N}}\rightarrow{\mathcal{Q}}$ with an edge between vertices
$\alpha$ and $\beta$ when there exists a unique $i\in{\mathcal{N}}$ such that
$\alpha(i)\neq\beta(i)$.

The set ${\mathcal{N}}$ is called the _set of entries_ , and the set
${\mathcal{Q}}$ the _alphabet_ , of $H(n,q)$. We may use the notation
$H({\mathcal{N}},q)$, $H(n,{\mathcal{Q}})$ or $H({\mathcal{N}},{\mathcal{Q}})$
if we wish to indicate either or both of the sets ${\mathcal{N}}$ or
${\mathcal{Q}}$ explicitly.

To see that the two definitions given above are equivalent: let
${\mathcal{N}}=\\{1,\ldots,n\\}$ and consider functions
$\alpha,\beta:{\mathcal{N}}\rightarrow{\mathcal{Q}}$. The $n$-tuples
$(\alpha(1),\ldots,\alpha(n))$ and $(\beta(1),\ldots,\beta(n))$ differ in
precisely one entry if and only if there exists a unique $i\in{\mathcal{N}}$
such that $\alpha(i)\neq\beta(i)$. We will use whichever is the most
convenient notation for each particular context, functions or $n$-tuples. The
following example illustrates this further.

######  Example 4.2.

Let ${\mathcal{N}}={\mathbb{F}}_{2}^{3}$, let
${\mathcal{Q}}={\mathbb{F}}_{2}$, let ${\mathbb{F}}_{2}[x_{1},x_{2},x_{3}]$
denote the polynomial ring over ${\mathbb{F}}_{2}$ in the three variables
$x_{1},x_{2},x_{3}$, and let ${\mathcal{C}}$ be the ${\mathbb{F}}_{2}$-vector
space

${\mathcal{C}}=\langle
1,x_{1},x_{2},x_{3}\rangle\subseteq{\mathbb{F}}_{2}[x_{1},x_{2},x_{3}].$

Considering each polynomial in ${\mathcal{C}}$ as a function from
${\mathcal{N}}$ to ${\mathcal{Q}}$, the set ${\mathcal{C}}$ defines a linear
code in $H(8,2)$. The elements $0$ and $1$ in ${\mathcal{C}}$ correspond to
the $8$-tuples $(0,\ldots,0)$ and $(1,\ldots,1)$, respectively. The remaining
elements of ${\mathcal{C}}$ are precisely the linear polynomials in
${\mathbb{F}}_{2}[x_{1},x_{2},x_{3}]$ and, upon evaluation on the elements of
${\mathcal{N}}$, these correspond to the characteristic vectors of the
$2$-flats (the affine $2$-spaces) of the affine geometry ${\rm AG}_{3}(2)$. If
the entries are labelled by the elements of ${\mathcal{N}}$ as follows

$(0,\,e_{1},\,e_{2},\,e_{1}+e_{2},\,e_{3},\,e_{1}+e_{3},\,e_{2}+e_{3},\,e_{1}+e_{2}+e_{3}),$

then we find that ${\mathcal{C}}$ consists of the following $8$-tuples:

$\begin{array}[]{cc}(1,1,1,1,1,1,1,1)&(0,0,0,0,0,0,0,0)\\\
(1,1,1,1,0,0,0,0)&(0,0,0,0,1,1,1,1)\\\ (1,1,0,0,1,1,0,0)&(0,0,1,1,0,0,1,1)\\\
(1,1,0,0,0,0,1,1)&(0,0,1,1,1,1,0,0)\\\ (1,0,1,0,1,0,1,0)&(0,1,0,1,0,1,0,1)\\\
(1,0,1,0,0,1,0,1)&(0,1,0,1,1,0,1,0)\\\ (1,0,0,1,1,0,0,1)&(0,1,1,0,0,1,1,0)\\\
(1,0,0,1,0,1,1,0)&(0,1,1,0,1,0,0,1).\end{array}$

Note that ${\mathcal{C}}$ is an extended Hamming code of length $8$ [67,
Example, p. 27], but is also known as the Reed–Muller code
${\mathcal{R}\mathcal{M}}_{2}(1,3)$ (see Definition 5.27).

The full automorphism group of the Hamming graph $\Gamma=H(n,q)$ is the semi-
direct product ${\rm Aut}(\Gamma)=B\rtimes L$, where the _base group_ $B$ is
${\rm Sym}({\mathcal{Q}})^{n}$ and the _top group_ $L$ is ${\rm
Sym}({\mathcal{N}})$ (see [20, Theorem 9.2.1]). Let $x=h\sigma\in{\rm
Aut}(\Gamma)$, where $h=(h_{1},\ldots,h_{n})\in B$ and $\sigma\in L$. Then
$h,\sigma$ and $x$ act on an $n$-tuple $\alpha=(a_{1},\ldots,a_{n})$ via

$\alpha^{h}=\left(a_{1}^{h_{1}},\ldots,a_{n}^{h_{n}}\right),\quad\alpha^{\sigma}=\left(a_{\left(1^{\sigma^{-1}}\right)},\ldots,a_{\left(n^{\sigma^{-1}}\right)}\right),\quad\text{and}\quad\alpha^{x}=\left(a_{1{\sigma^{-1}}}^{h_{1{\sigma^{-1}}}},\ldots,a_{n{\sigma^{-1}}}^{h_{n{\sigma^{-1}}}}\right).$
(4)

For example,
$(a_{1},a_{2},a_{3},a_{4})^{(1\,2\,3\,)}=(a_{3},a_{1},a_{2},a_{4})$. If
instead we consider a vertex $\alpha$ to be a function
${\mathcal{N}}\rightarrow{\mathcal{Q}}$ then $h,\sigma$ and $x$ act on
$\alpha$ via

$\alpha^{h}(i)=\left(\alpha(i)\right)^{h_{i}},\quad\alpha^{\sigma}(i)=\alpha\left(i^{\sigma^{-1}}\right),\quad\text{and}\quad\alpha^{x}(i)=\left(\alpha(i^{\sigma^{-1}})\right)^{h_{i\sigma^{-1}}}.$
(5)

Let ${\mathcal{C}}$ be a code in $H(n,q)$, $G\leq{\rm Aut}({\mathcal{C}})$ and
let ${\mathcal{M}}$ be a subset of ${\mathcal{N}}$ with $m=|{\mathcal{M}}|$.
Then we define

  1. (a)

the _projection_ $\pi_{\mathcal{M}}({\mathcal{C}})$ of ${\mathcal{C}}$ with
respect to ${\mathcal{M}}$ to be the code in $H({\mathcal{M}},q)$ consisting
of the functions $\alpha|_{\mathcal{M}}:{\mathcal{M}}\rightarrow{\mathcal{Q}}$
given by restricting $\alpha$ to ${\mathcal{M}}$, for each
$\alpha\in{\mathcal{C}}$. Moreover, we define

  2. (b)

$\chi_{\mathcal{M}}(G)$ to be the subgroup of ${\rm Aut}(H({\mathcal{M}},q))$
induced by the setwise stabiliser $G_{{\mathcal{M}}}$ in its action on the
restrictions $\alpha|_{\mathcal{M}}$ to ${\mathcal{M}}$ of functions
${\mathcal{N}}\rightarrow{\mathcal{Q}}$.

  3. (c)

We say that a code ${\mathcal{C}}$ is _linear_ , or _${\mathbb{F}}_{q}$
-linear_, if ${\mathcal{Q}}={\mathbb{F}}_{q}$ and ${\mathcal{C}}$ is an
${\mathbb{F}}_{q}$-vector subspace of ${\mathbb{F}}_{q}^{n}$.

  4. (d)

If ${\mathcal{Q}}={\mathbb{F}}_{q}$ then it makes sense to define the
translation $t_{\alpha}:\beta\mapsto\alpha+\beta$ by a vertex $\alpha$ of
$H(n,q)$, and if ${\mathcal{C}}$ is linear then ${\rm Aut}({\mathcal{C}})$
contains the subgroup
$T_{{\mathcal{C}}}=\\{t_{\alpha}\mid\alpha\in{\mathcal{C}}\\}$. If $0$ is a
distinguished element of ${\mathcal{Q}}$ and $\alpha$ is a vertex in $H(n,q)$
then ${\rm supp}(\alpha)=\\{i\in{\mathcal{N}}\mid\alpha(i)\neq 0\\}$ and ${\rm
wt}(\alpha)=|{\rm supp}(\alpha)|$.

######  Example 4.3.

Consider the code ${\mathcal{C}}=\langle 1,x_{1},x_{2},x_{3}\rangle$ (an
${\mathbb{F}}_{2}$ vector subspace) in $H(8,2)$ with
${\mathcal{N}}={\mathbb{F}}_{2}^{3}$ and ${\mathcal{Q}}={\mathbb{F}}_{2}$, as
in Example 4.2. Then for each $\alpha\in{\mathcal{C}}$, ${\rm
Aut}({\mathcal{C}})$ contains the translation
$t_{\alpha}:\beta\rightarrow\alpha+\beta$, and moreover each $\sigma\in{\rm
AGL}_{3}(2)\leq{\rm Sym}({\mathcal{N}})$ defines an automorphism of
${\mathcal{C}}$. Hence ${\rm Aut}({\mathcal{C}})$ contains
$G=T_{{\mathcal{C}}}.{\rm AGL}_{3}(2)$. Let ${\mathcal{M}}=\langle
e_{1},e_{2}\rangle$, where $e_{i}$ corresponds to $x_{i}$ in Example 4.2. Then
the projection code
${\mathcal{C}}^{\prime}=\pi_{{\mathcal{M}}}({\mathcal{C}})=\langle
1,x_{1},x_{2}\rangle$ and we may express the codewords of
$\pi_{{\mathcal{M}}}({\mathcal{C}})$ as $4$-tuples by taking the first four
entries of each $8$-tuple from Example 4.2:

$\begin{array}[]{cc}(1,1,1,1)&(0,0,0,0)\\\ (1,1,0,0)&(0,0,1,1)\\\
(1,0,1,0)&(0,1,0,1)\\\ (1,0,0,1)&(0,1,1,0).\end{array}$

Also, the projection $\chi_{{\mathcal{M}}}(G)=T_{{\mathcal{C}}^{\prime}}.{\rm
AGL}_{2}(2)$ is a subgroup of ${\rm Aut}({\mathcal{C}}^{\prime})$.

######  Definition 4.4.

Let ${\mathcal{C}}$ be a code in $H({\mathcal{N}},{\mathcal{Q}})$ and let
${\mathcal{M}}={\mathcal{N}}\times\\{1,\ldots,k\\}$, from which we introduce
the following definitions related to $H({\mathcal{M}},{\mathcal{Q}})$.

  1. (1)

If $\alpha_{1},\ldots,\alpha_{k}$ are vertices of
$H({\mathcal{N}},{\mathcal{Q}})$ (that is, functions
${\mathcal{N}}\rightarrow{\mathcal{Q}}$) then we define a vertex of
$H({\mathcal{M}},{\mathcal{Q}})$,
$\beta_{\alpha_{1},\ldots,\alpha_{k}}:{\mathcal{M}}\rightarrow{\mathcal{Q}}$,
by

$\beta_{\alpha_{1},\ldots,\alpha_{k}}:(i,j)\mapsto\alpha_{j}(i).$

  2. (2)

The _$k$ -fold product_ ${\rm Prod}_{k}({\mathcal{C}})$ is the code in
$H({\mathcal{M}},{\mathcal{Q}})$ given by

${\rm
Prod}_{k}({\mathcal{C}})=\\{\beta_{\alpha_{1},\ldots,\alpha_{k}}\mid\alpha_{1},\ldots,\alpha_{k}\in{\mathcal{C}}\\}.$

  3. (3)

The _$k$ -fold repetition_ ${\rm Rep}_{k}({\mathcal{C}})$ in
$H({\mathcal{M}},{\mathcal{Q}})$ is

${\rm
Rep}_{k}({\mathcal{C}})=\\{\beta_{\alpha,\ldots,\alpha}\mid\alpha\in{\mathcal{C}}\\};$

and if $|{\mathcal{N}}|=1$ so $H({\mathcal{N}},{\mathcal{Q}})$ is degenerate
(a complete graph on $q$ vertices), then this code is the usual repetition
code, and we write ${\rm Rep}_{k}(q)$ if ${\mathcal{C}}=H(1,{\mathcal{Q}})$.

  4. (4)

For $g_{1},\ldots,g_{k}\in{\rm Sym}({\mathcal{N}})$, we define
$\sigma_{g_{1},\ldots,g_{k}}$ to be the automorphism of
$H({\mathcal{M}},{\mathcal{Q}})$ that maps the vertex

$\gamma:(i,j)\mapsto\gamma(i,j)\quad\text{to}\quad\gamma^{\sigma_{g_{1},\ldots,g_{k}}}:(i,j)\mapsto\gamma\Big{(}i^{g_{j}^{-1}},j\Big{)}.$

  5. (5)

For $h_{1},\ldots,h_{k}\in{\rm Sym}({\mathcal{Q}})$, we define
$x_{h_{1},\ldots,h_{k}}$ to be the automorphism of
$H({\mathcal{M}},{\mathcal{Q}})$ that maps the vertex

$\gamma:(i,j)\mapsto\gamma(i,j)\quad\text{to}\quad\gamma^{x_{h_{1},\ldots,h_{k}}}:(i,j)\mapsto(\gamma(i,j))^{h_{j}}.$

Note that the automorphism group of ${\rm Prod}_{k}({\mathcal{C}})$ contains
the wreath product ${\rm Aut}({\mathcal{C}})\wr{\rm S}_{k}$ and the
automorphism group of ${\rm Rep}_{k}({\mathcal{C}})$ contains ${\rm
Aut}({\mathcal{C}})\times{\rm S}_{k}$.

####  2 Johnson and Kneser graphs

Recall that ${\mathcal{V}}\choose k$ denotes the set of all $k$-element
subsets of a set ${\mathcal{V}}$; this set forms the vertex set of both the
Johnson and Kneser graphs

######  Definition 4.5.

Let ${\mathcal{V}}$ be a set of size $v$ and let $k$ be an integer with $2\leq
k\leq v-1$. The _Johnson graph_ $J(v,k)$ has vertex set ${\mathcal{V}}\choose
k$ and a pair of distinct vertices are defined to be adjacent if they
intersect in $(k-1)$-subset. We say that ${\mathcal{V}}$ is the _underlying
set_ of $J(v,k)$.

If $v\neq 2k$ then ${\rm Aut}(J(v,k))={\rm Sym}({\mathcal{V}})$ and if $v=2k$
then ${\rm Aut}(J(v,k))={\rm Sym}({\mathcal{V}})\times C_{2}$ [20, Theorem
9.1.2]. As mentioned in the introduction, we refer the reader to [74] for a
recent survey regarding neighbour-transitive codes in Johnson graphs.

######  Definition 4.6.

Let ${\mathcal{V}}$ be a set of size $v$ and let $k$ be an integer with $2\leq
k\leq(v-1)/2$. The _Kneser graph_ $K(v,k)$ has vertex set
${\mathcal{V}}\choose k$ and a pair of distinct vertices are defined to be
adjacent if they are disjoint. If $v=2k+1$ then $K(v,k)$ is called the _odd
graph_ $O_{k+1}$. We say that ${\mathcal{V}}$ is the _underlying set_ of
$K(v,k)$ (or $O_{k+1}$).

The automorphism group of $K(v,k)$ is ${\rm Sym}({\mathcal{V}})$ [49,
Corollary 7.8.2]. The next example explores the relationship between codes in
Johnson graphs and codes in Kneser graphs.

######  Example 4.7.

Let ${\mathcal{V}}$ be a set of size $v$, let $k$ satisfy $2\leq
k\leq(v-1)/2$, and let $J(v,k)$ and $K(v,k)$ be the Johnson and Kneser graphs,
respectively, with underlying set ${\mathcal{V}}$. Since both graphs have the
same vertex set, namely ${{\mathcal{V}}\choose k}$, a code in one is also a
code in the other, generally with different parameters. For instance:

  1. (a)

Let $U\subseteq{\mathcal{V}}$ such that $k<|U|<v$ and let
${\mathcal{C}}=\\{\alpha\in{{\mathcal{V}}\choose k}\mid\alpha\subset U\\}$. By
Theorem 2.19(1), as a code in the Johnson graph, ${\mathcal{C}}$ has minimum
distance $1$ and is neighbour-transitive. We now consider ${\mathcal{C}}$ to
be a code in the Kneser graph. In this case, since there exists a pair of
disjoint $k$-subsets of $U$ if and only if $|U|\geq 2k$, it follows that
${\mathcal{C}}$ has minimum distance $1$ in the Kneser graph if and only if
$|U|\geq 2k$. Moreover, since there always exists a pair of $k$-subsets of $U$
at distance $2$ in $K(v,k)$ (in particular, $|U|\geq k+1$ implies there exists
such a pair intersecting in a $(k-1)$-subset of $U$), we deduce that
${\mathcal{C}}$ has minimum distance $2$ in the Kneser graph when $|U|<2k$.
Moreover, it turns out that ${\mathcal{C}}$ is neighbour-transitive in the
Kneser graph if and only if $|U|=v-1$ (see Theorem 6.4(1) and Example 6.3).

  2. (b)

Let $U\subseteq{\mathcal{V}}$ such that $0<|U|<k$ and let
${\mathcal{C}}=\\{\alpha\in{{\mathcal{V}}\choose k}\mid U\subset\alpha\\}$.
Theorem 2.19(2) again tells us that, as a code in the Johnson graph,
${\mathcal{C}}$ has minimum distance $1$ and is neighbour-transitive. However,
since every codeword contains $U$, no pair of elements of ${\mathcal{C}}$ are
disjoint. Hence ${\mathcal{C}}$ has minimum distance at least $2$ in the
Kneser graph, and it is not difficult to see that the minimum distance equals
$2$ since $v\geq 2k+1$. Moreover, it turns out that ${\mathcal{C}}$ is always
neighbour-transitive in the Kneser graph (see Theorem 6.4(3) and Example 6.3).

####  3 $q$-Analogues of various graphs

Roughly speaking, if a combinatorial definition is phrased in terms of sets
then, for a prime power $q$, the _$q$ -analogue_ of this definition is
obtained by rephrasing the original definition in terms of
${\mathbb{F}}_{q}$-vector spaces. The next definition gives the $q$-analogues
of the Hamming graphs. Codes in these graphs are known as _rank-metric_ codes,
and have received interest lately due to their application in network coding,
see [12] for a recent survey.

######  Definition 4.8.

Let $X\cong{\mathbb{F}}_{q}^{m}$ and $Y\cong{\mathbb{F}}_{q}^{n}$ with
$m,n\geq 2$. The _bilinear forms graph_ $H_{q}(m,n)$ is the graph with vertex
set the vector space of all linear maps $\alpha:X\rightarrow Y$ where two
vertices $\alpha$ and $\beta$ are adjacent if ${\rm rank}(\alpha-\beta)=1$.

######  Example 4.9.

Delsarte [30] and Gabidulin [36] independently introduced the following class
of codes. Let $n,k,s$ be positive integers such that $\gcd(n,s)=1$. Identify
$X$ and $Y$ with ${\mathbb{F}}_{q^{n}}$, considered as an $n$-dimensional
${\mathbb{F}}_{q}$-vector space, and note that each of the polynomials
$x^{q^{is}}$ defines an ${\mathbb{F}}_{q}$-linear map $X\to Y$.

Define ${\mathcal{C}}$ to be the code in $\Gamma=H_{q}(n,n)$ given by the
polynomials in the ${\mathbb{F}}_{q^{n}}$-vector space

${\mathcal{C}}=\left\langle
x,x^{q^{s}},\ldots,x^{q^{s(k-1)}}\right\rangle_{{\mathbb{F}}_{q^{n}}}.$

Note that each polynomial in ${\mathcal{C}}$ is a _linearised_ polynomial (see
[65, Section 3.4]) and thus defines an ${\mathbb{F}}_{q}$-linear map from $X$
to $Y$. Also, ${\mathcal{C}}$ has minimum distance $\delta=n-k+1$. Hence, as
long as $k\leq n-1$, the set $\Gamma_{1}(0)$ comprises all rank $1$ linear
maps. The trace function ${\rm tr}(x)=x^{q^{n-1}}+\cdots+x^{q}+x$ is one such
rank $1$ linear map and all others may be written as $f_{a,b}(x)=a\cdot{\rm
tr}(bx)$ for some $a,b\in{\mathbb{F}}_{q^{n}}^{\times}$. Since ${\mathcal{C}}$
is an ${\mathbb{F}}_{q^{n}}$-vector space, it follows that ${\rm
Aut}({\mathcal{C}})$ contains all translations by elements of ${\mathcal{C}}$.
Moreover, ${\rm Aut}({\mathcal{C}})$ contains a subgroup isomorphic to
$({\mathbb{F}}_{q^{n}}^{\times}\times{\mathbb{F}}_{q^{n}}^{\times})/{\mathbb{F}}_{q}^{\times}$
given by the maps $f(x)\mapsto a\cdot f(bx)$ for each
$a,b\in{\mathbb{F}}_{q^{n}}^{\times}$. Thus ${\rm Aut}({\mathcal{C}})$ acts
transitively on ${\mathcal{C}}$ and the stabiliser in ${\rm
Aut}({\mathcal{C}})$ of the zero map acts transitively on the set of all rank
$1$ linear maps. Hence, by Lemma 2.6, ${\mathcal{C}}$ is neighbour-transitive.

The above example suggests the following open problem.

######  Problem 4.10.

Find more examples and characterise families of $s$-neighbour-transitive codes
in $H_{q}(m,n)$.

Next we introduce the $q$-analogues of the Johnson graphs. For
$X={\mathbb{F}}_{q}^{d}$, we write ${X\choose k}_{q}$ for the set of
$k$-dimensional subspaces of $X$.

######  Definition 4.11.

Let $X={\mathbb{F}}_{q}^{d}$. The _Grassmann graph_ $J_{q}(d,k)$ has vertex
set ${X\choose k}_{q}$ and vertices $\alpha$ and $\beta$ are adjacent when
$\alpha\cap\beta$ has dimension $k-1$.

For an integer $k\geq 2$, a _$k$ -spread_ of a vector space $V$ is set of
$k$-dimensional subspaces of $V$ such that each non-zero vector of $V$ is
contained in precisely one spread element. In the setting of projective
geometry, a spread is a partition of the points of ${\rm PG}_{d-1}(q)$ such
that each part forms a $(k-1)$-dimensional projective subspace. A _regulus_ of
${\rm PG}_{2k-1}(q)$ is a set ${\mathcal{R}}$ of size $q+1$ consisting of
pairwise disjoint $(k-1)$-dimensional projective subspaces such that any line
meeting at least $3$ elements of ${\mathcal{R}}$ meets every element of
${\mathcal{R}}$; see [32, Section 5.1]. Three pairwise disjoint
$(k-1)$-dimensional projective subspaces contained in a $(2k-1)$-subspace
determine a unique regulus containing all three of them. A spread
${\mathcal{S}}$ is called _regular_ (or sometimes _Desarguesian_) if
${\mathcal{S}}$ contains all the elements of the regulus determined by any
three pairwise distinct elements of ${\mathcal{S}}$ contained in a projective
$(2k-1)$-subspace. Equivalently, a regular spread is one obtained via _field
reduction_ , see [63]. The next example uses field reduction to show that a
regular spread is a neighbour-transitive code in a Grassmann graph.

######  Example 4.12.

Let $k$ be a positive integer dividing $d$, let $Y={\mathbb{F}}_{q^{k}}^{d/k}$
and $X={\mathbb{F}}_{q}^{d}$. Then $X$ and $Y$ are isomorphic as
${\mathbb{F}}_{q}$-vector spaces. Fix such an ${\mathbb{F}}_{q}$-vector space
isomorphism $\phi:Y\rightarrow X$. Let ${\mathcal{C}}$ be the image under
$\phi$ of the set of all $1$-dimensional ${\mathbb{F}}_{q^{k}}$-subspaces of
$Y$. Then ${\mathcal{C}}$ is a regular spread of $X$ and ${\mathcal{C}}$ is a
code in $J_{q}(d,k)$ with minimum distance $\delta=k$. The stabiliser of
${\mathcal{C}}$ in $\Gamma{\rm L}_{d}(q)$ is $\Gamma{\rm L}_{d/k}(q^{k})$, and
hence ${\rm Aut}({\mathcal{C}})\cong\Gamma{\rm L}_{d/k}(q^{k})/Z$, where $Z$
is the center of ${\rm GL}_{d}(q)$. Thus ${\rm Aut}({\mathcal{C}})$ acts
transitively on ${\mathcal{C}}$. Moreover, if $\alpha\in{\mathcal{C}}$ then
${\rm Aut}({\mathcal{C}})_{\alpha}$ contains $(q^{d-k}:((q^{k}-1)\times{\rm
GL}_{d/k-1}(q^{k})))/Z$, which acts transitively on the set of $k$-dimensional
${\mathbb{F}}_{q}$-subspaces of $X$ that intersect $\alpha$ in a
$(k-1)$-dimensional ${\mathbb{F}}_{q}$-subspace. Hence, by Lemma 2.6(2),
${\mathcal{C}}$ is neighbour-transitive.

####  4 Two graphs related to incidence structures

An _incidence structure_ (see [32]) is a triple
${\mathcal{S}}=({\mathcal{P}},{\mathcal{L}},{\rm I})$, where ${\mathcal{P}}$
and ${\mathcal{L}}$ are disjoint non-empty sets of elements called _points_
and _lines_ , respectively, and ${\rm
I}\subseteq{\mathcal{P}}\times{\mathcal{L}}$ is a point-line incidence
relation. If $(p,\ell)\in{\rm I}$ then we say that $p$ _lies on_ $\ell$, $p$
is _incident_ with $\ell$, or $\ell$ is _incident_ with $p$. The elements of
${\rm I}$ are called _flags_ and if $p\in{\mathcal{P}}$,
$\ell\in{\mathcal{L}}$ and $(p,\ell)\notin{\rm I}$ then $(p,\ell)$ is called
an _antiflag_. If there exists an $\ell\in{\mathcal{L}}$ such that
$(p_{1},\ell),(p_{2},\ell)\in{\rm I}$ then $p_{1}$ and $p_{2}$ are
_collinear_. The _dual_ incidence structure
${\mathcal{S}}^{D}=({\mathcal{L}},{\mathcal{P}},{\rm I}^{D})$ is obtained from
${\mathcal{S}}$ by interchanging the sets of points and lines, with incidence
${\rm I}^{D}$ defined by $(\ell,p)\in{\rm I}^{D}$ if $(p,\ell)\in{\rm I}$.

######  Definition 4.13.

Let ${\mathcal{S}}=({\mathcal{P}},{\mathcal{L}},{\rm I})$ be an incidence
structure. Then the _incidence graph_ of ${\mathcal{S}}$ is the graph with
vertex set ${\mathcal{P}}\cup{\mathcal{L}}$ and an edge $\\{p,\ell\\}$
whenever $(p,\ell)\in{\rm I}$ (and no further edges). The _collinearity graph_
of ${\mathcal{S}}$ is the graph with vertex set ${\mathcal{P}}$ and an edge
$\\{p_{1},p_{2}\\}$ whenever $p_{1}$ and $p_{2}$ are collinear.

######  Lemma 4.14.

Let $\Gamma$ be the incidence graph of an incidence structure
${\mathcal{S}}=({\mathcal{P}},{\mathcal{L}},{\rm I})$ and let ${\mathcal{C}}$
be an $s$-neighbour-transitive code in $\Gamma$ such that
${\mathcal{C}}\subseteq{\mathcal{P}}$. Then ${\mathcal{C}}$ is an $\lfloor
s/2\rfloor$-neighbour-transitive code in the collinearity graph of
${\mathcal{S}}$.

###### Proof.

This follows from applying Lemma 2.6 to ${\mathcal{C}}$ as a vertex subset of
both the incidence graph of ${\mathcal{S}}$ and the collinearity graph of
${\mathcal{S}}$. ∎

######  Example 4.15.

Let ${\mathcal{S}}=({\mathcal{P}},{\mathcal{L}},{\rm I})$ be the incidence
structure obtained by letting ${\mathcal{P}}$ be the set of points, and
${\mathcal{L}}$ the set of lines, of the projective geometry ${\rm
PG}_{3}(q)$, with the usual point-line incidence. Let $\Gamma$ be the
incidence graph of ${\mathcal{S}}$, and let ${\mathcal{C}}$ be a regular
spread of ${\rm PG}_{3}(q)$, as defined in Example 4.12 (with $d=4$, $k=2$),
but considered now as a code in the incidence graph $\Gamma$.

  1. $(a)$

Then as a code in $\Gamma$, ${\mathcal{C}}$ is completely transitive (and
$2$-neighbour-transitive) with minimum distance $4$ and covering radius $2$;
and

  2. $(b)$

as a code in the collinearity graph of ${\mathcal{S}}^{D}$, which is
isomorphic to $J_{q}(4,2)$, ${\mathcal{C}}$ is completely transitive (and
neighbour-transitive) with minimum distance $2$ and covering radius $1$.

######  Lemma 4.16.

All the claims of Example 4.15 are valid.

###### Proof.

Let $X={\mathbb{F}}_{q}^{4}$. It follows from Definition 4.11 that the
collinearity graph of ${\mathcal{S}}^{D}$ is $J_{q}(4,2)$, with vertex set
$\binom{X}{2}_{q}$. Also, from Example 4.12, we see that ${\rm
Aut}({\mathcal{C}})$ contains ${\rm GL}_{2}(q^{2})/Z$, where $Z$ is the scalar
subgroup of ${\rm GL}_{4}(q)$, and as a code in $J_{q}(4,2)$, ${\mathcal{C}}$
has minimum distance $2$, covering radius $1$ and ${\rm Aut}({\mathcal{C}})$
is transitive on both ${\mathcal{C}}$ and
${\mathcal{L}}\setminus{\mathcal{C}}$. Thus all the assertions of part (b) are
valid. Now we consider ${\mathcal{C}}$ as a code in the incidence graph
$\Gamma$ of ${\mathcal{S}}$. The set of code neighbours comprises the whole of
the point set ${\mathcal{P}}$, since from the definition of a spread each
projective point lies on exactly one line in the spread. Thus ${\mathcal{C}}$
has covering radius $2$. Also the subgroup ${\rm GL}_{2}(q^{2})/Z$ of ${\rm
Aut}({\mathcal{C}})$ is transitive on ${\mathcal{P}}$, and it follows that
${\mathcal{C}}$ is $2$-neighbour-transitive and hence also completely
transitive. Finally, any two codewords, that is lines $\ell,\ell^{\prime}$ in
${\mathcal{C}}$, have no point in common and so are at distance strictly
greater than $2$ in $\Gamma$. Since $\Gamma$ is bipartite this means that
$\ell,\ell^{\prime}$ are at distance at least $4$. In fact their distance is
equal to $4$, since choosing points $p,p^{\prime}$ on $\ell,\ell^{\prime}$,
respectively, and letting $\ell^{\prime\prime}$ be the line containing $p$ and
$p^{\prime}$, we have a path
$(\ell,p,\ell^{\prime\prime},p^{\prime},\ell^{\prime})$ of length $4$ in
$\Gamma$. Thus all the assertions of part (a) are also valid. ∎

###  5 Codes in Hamming graphs

The next three propositions are applications of Lemma 2.6 and are the starting
point for our analysis of $s$-neighbour-transitive codes in Hamming graphs. We
include here a proof of the first in order to illustrate the general idea.
Recall the notions of $i$-homogeneous and $i$-transitive group actions from
Section 2.

######  Proposition 5.1.

[38, Proposition 2.5] Let ${\mathcal{C}}$ be a $(G,s)$-neighbour-transitive
code, with error-correction capacity $e\geq 1$, in
$\Gamma=H(n,q)=H({\mathcal{N}},q)$ and let $\alpha\in{\mathcal{C}}$. Then, for
each $i\leq\min\\{e,s\\}$, $G_{\alpha}$ acts $i$-homogeneously on
${\mathcal{N}}$.

###### Proof.

Since the automorphism group of the Hamming graph is vertex-transitive, we may
assume (replacing ${\mathcal{C}}$ if necessary by ${\mathcal{C}}^{g}$, for
some $g\in{\rm Aut}(H(n,q))={\rm Sym}(q)\wr{\rm Sym}(n)$) that
$\alpha=(0,\ldots,0)\in{\mathcal{C}}$ for some distinguished element
$0\in{\mathcal{Q}}$. By Lemma 2.6, the stabiliser $G_{\alpha}$ acts
transitively on $\Gamma_{i}(\alpha)$ for each $i\leq\min\\{e,s\\}$. Now
$\Gamma_{i}(\alpha)$ is the set of all weight $i$ vertices of $H(n,q)$. Let
$I,J\in{{\mathcal{N}}\choose i}$ and
$\beta_{1},\beta_{2}\in\Gamma_{1}(\alpha)$ such that ${\rm supp}(\beta_{1})=I$
and ${\rm supp}(\beta_{2})=J$. Then there exists $g\in G$ such that
$\beta_{1}^{g}=\beta_{2}$. Since $i\leq e$, the codeword $\alpha$ is the only
vertex of ${\mathcal{C}}$ that has distance $i$ from $\beta_{1}$ and
$\beta_{2}$, and thus $g\in G_{\alpha}$. This means that $g$ is of the form
$g=(h_{1},\ldots,h_{n})\sigma$, where $\sigma\in L$, $(h_{1},\ldots,h_{n})\in
B$, and $0^{h_{i}}=0$ for each $i=1,\ldots,n$. It follows that $I^{\sigma}=J$,
and the result is proved. ∎

Proposition 5.1 implies in particular that, for each $G$-neighbour-transitive
code ${\mathcal{C}}$ in $H({\mathcal{N}},q)$ with error correction capacity at
least $1$, the group $G$ induces a transitive action on ${\mathcal{N}}$. This
action may be imprimitive, that is to say, $G$ may leave invariant some non-
trivial partition of ${\mathcal{N}}$. It turns out that, in this case, the
projection $\pi_{J}({\mathcal{C}})$, for any part $J$ of such a partition, is
also a neighbour-transitive code in the smaller Hamming graph $H(J,q)$.
(Recall the projection maps $\pi_{J}$ and $\chi_{J}$ from Section 4.)

######  Proposition 5.2.

Suppose that ${\mathcal{C}}$ is a $G$-neighbour-transitive code in
$H({\mathcal{N}},q)$ with minimum distance $\delta\geq 3$, and suppose further
that ${\mathcal{J}}$ is a non-trivial $G$-invariant partition of
${\mathcal{N}}$, and $J\in{\mathcal{J}}$ is such that $\pi_{J}({\mathcal{C}})$
is not the complete code $H(J,q)$. Then the following hold:

  1. $(1)$

$\pi_{J}({\mathcal{C}})$ is $\chi_{J}(G)$-neighbour-transitive ([41,
Proposition 3.4]).

  2. $(2)$

$\pi_{J}({\mathcal{C}})$ has minimum distance at least $2$ ([41, Corollary
3.7]).

Now ${\rm Aut}(H({\mathcal{N}},{\mathcal{Q}}))={\rm Sym}({\mathcal{Q}})\wr{\rm
Sym}({\mathcal{N}})=B\rtimes L$. For a subgroup $G\leq B\rtimes L$, and
$i\in{\mathcal{N}}$, let $G_{i}$ denote the subgroup consisting of all
elements $x=h\sigma\in B\rtimes L$ lying in $G$ such that $i^{\sigma}=i$. By
(4), such an element $x=h\sigma$ maps each vertex
$(\alpha_{1},\dots,\alpha_{n})$ to a tuple with $i^{th}$ entry
$\alpha_{i}^{h_{i}}$. Thus $G_{i}$ induces an action on the set
${\mathcal{Q}}_{i}$ of $i^{th}$ entries of vertices of
$H({\mathcal{N}},{\mathcal{Q}})$. (Of course ${\mathcal{Q}}_{i}$ is a copy of
${\mathcal{Q}}$.) A more intricate argument than that in the proof of
Proposition 5.1 yields the following.

######  Proposition 5.3.

[38, Proposition 2.7] Let ${\mathcal{C}}$ be a $G$-neighbour-transitive code,
with minimum distance $\delta\geq 3$, in
$\Gamma=H({\mathcal{N}},{\mathcal{Q}})=H(n,q)$, and let $i\in{\mathcal{N}}$.
Then $G_{i}^{{\mathcal{Q}}_{i}}$ acts $2$-transitively on ${\mathcal{Q}}_{i}$.

By an old theorem of Burnside ([21, Section 154], or see [75, Theorem 3.21])
every finite $2$-transitive group is either a group of affine transformations
of a finite vector space, or is an almost-simple group. Thus, Proposition 5.3
implies that every $(G,2)$-neighbour-transitive code satisfies precisely one
of the conditions in Definition 5.4 below.

######  Definition 5.4.

Let ${\mathcal{C}}$ be a $G$-neighbour-transitive code in
$H({\mathcal{N}},q)$, let $K$ be the kernel of the action of $G$ on
${\mathcal{N}}$, and let $i\in{\mathcal{N}}$. Then precisely one of the
following holds for $({\mathcal{C}},G)$; i.e. ${\mathcal{C}}$ is

  1. (1)

_$G$ -entry-faithful_ if $G$ acts faithfully on ${\mathcal{N}}$, that is,
$K=1$;

  2. (2)

_$G$ -alphabet-almost-simple_ if $K\neq 1$, $G$ acts transitively on
${\mathcal{N}}$, and $G_{i}^{{\mathcal{Q}}_{i}}$ is a $2$-transitive almost-
simple group; and

  3. (3)

_$G$ -alphabet-affine_ if $K\neq 1$, $G$ acts transitively on ${\mathcal{N}}$,
and $G_{i}^{{\mathcal{Q}}_{i}}$ is a $2$-transitive affine group.

We use descriptors such as $G$-entry-faithful for arbitrary code-group pairs
$({\mathcal{C}},G)$ in Hamming graphs.

Codes that are $G$-entry-faithful and $(G,2)$-neighbour-transitive were
considered by the authors with Gillespie and Giudici in [38].

######  Theorem 5.5.

[38, Theorem 1.1] Suppose that ${\mathcal{C}}$ is a code in $H(n,q)$, with
$|{\mathcal{C}}|\geq 2$ and minimum distance $\delta\geq 5$. Then
${\mathcal{C}}$ is $G$-entry-faithful and $(G,2)$-neighbour-transitive if and
only if ${\mathcal{C}}$ is equivalent to either:

  1. $(1)$

a binary repetition code with $\delta=n$, or,

  2. $(2)$

the even weight subcode of the punctured Hadamard code of length $12$,
$G\cong{\rm M}_{11}$, and $\delta=6$.

####  1 Alphabet-almost-simple codes in Hamming graphs

It turns out that permutation codes (see [6, 15] and Definition 5.6) provide
useful building blocks for constructing a wide range of neighbour-transitive
codes, many of which are alphabet-almost-simple, as defined in Definition 5.4.

######  Definition 5.6.

Let ${\mathcal{N}}={\mathcal{Q}}=\\{1,\ldots,q\\}$ and let $T\subseteq{\rm
Sym}({\mathcal{Q}})$. Then, using the ‘function’ Definition 4.1(2) for the
Hamming graph $H({\mathcal{N}},{\mathcal{Q}})$, the _permutation code_
${\mathcal{C}}(T)$ is the code comprising the elements of $T$ considered as
functions from ${\mathcal{N}}$ to ${\mathcal{Q}}$, that is to say, $t\in T$
corresponds to the codeword $\alpha_{t}:i\to i^{t}$ (for $i\in{\mathcal{N}}$).
In terms of the ‘$q$-tuple’ Definition 4.1(1) for
$H({\mathcal{N}},{\mathcal{Q}})$, the codeword $\alpha_{t}$ in
${\mathcal{C}}(T)$ corresponding to $t\in T$ is
$\alpha_{t}=(1^{t},2^{t},\ldots,q^{t})$, that is to say,
$\alpha_{t}(i)=i^{t}$.

Here is a simple example of a permutation code in $H(4,4)$.

######  Example 5.7.

Letting $T={\rm A}_{4}$, the permutation code ${\mathcal{C}}(T)$ consists of
the following $4$-tuples:

$\begin{array}[]{cccc}(1,2,3,4)&(2,1,4,3)&(3,4,1,2)&(4,3,2,1)\\\
(3,1,2,4)&(4,1,3,2)&(4,2,1,3)&(1,4,2,3)\\\
(2,3,1,4)&(2,4,3,1)&(3,2,4,1)&(1,3,4,2).\end{array}$

Next we identify some automorphisms of ${\mathcal{C}}(T)$ among the following
elements of ${\rm Aut}(H(q,q))=B\rtimes L$, by examining their actions on
‘permutation’ type vertices, that is, vertices with pairwise distinct entries,
and hence of the form $\alpha_{t}$ for some $t\in{\rm Sym}({\mathcal{Q}})$.
For an element $g\in{\rm Sym}({\mathcal{Q}})$, we write $\sigma_{g}$ for the
corresponding element of the top group $L={\rm Sym}({\mathcal{N}})$, we write
$x_{g}=(g,g,\dots,g)$ for the corresponding ‘diagonal’ element of the base
group $B={\rm Sym}({\mathcal{Q}})^{q}$. The actions of these elements on
$H({\mathcal{N}},{\mathcal{Q}})$ are given in (4) and (5). For any Hamming
graph $H({\mathcal{N}},{\mathcal{Q}})=H(n,q)$ and any subgroup $H\leq{\rm
Sym}({\mathcal{Q}})$, we define the _diagonal subgroup_ ${\rm Diag}_{n}(H)$ of
the base group $B={\rm Sym}({\mathcal{Q}})^{n}$ of ${\rm Aut}(H(n,q))$ by

${\rm Diag}_{n}(H)=\\{x_{g}=(g,g,\dots,g)\in B\mid g\in H\\}.$ (6)

Proofs of the following assertions are given in [41, Lemma 8], and are easily
derived.

  1. (1)

For $g\in{\rm Sym}({\mathcal{Q}})$, the element $\sigma_{g}$ maps
$\alpha_{t}\in{\mathcal{C}}(T)$ to $\alpha_{tg^{-1}}$.

  2. (2)

For $g\in{\rm Sym}({\mathcal{Q}})$, the element $x_{g}$ maps
$\alpha_{t}\in{\mathcal{C}}(T)$ to $\alpha_{tg}$.

  3. (3)

For $g\in{\rm Sym}({\mathcal{Q}})$, the product $x_{g}\sigma_{g}$ maps
$\alpha_{t}\in{\mathcal{C}}(T)$ to $\alpha_{g^{-1}tg}$.

Now suppose that $T$ is a subgroup of ${\rm Sym}({\mathcal{Q}})$. Then
choosing $g$ to lie in $T$ in parts (1) and (2) we see that ${\rm
Aut}({\mathcal{C}}(T))$ contains ${\rm Diag}_{q}(T)\times\\{\sigma_{g}\mid
g\in T\\}\cong T\times T$. Moreover, choosing $g$ in the normaliser $N_{{\rm
Sym}({\mathcal{Q}})}(T)$ in part (3), we obtain the larger subgroup ${\rm
Diag}_{q}(T)\rtimes A(T)$ of ${\rm Aut}({\mathcal{C}}(T))$, where
$A(T):=\\{x_{g}\sigma_{g}\mid g\in N_{{\rm Sym}({\mathcal{Q}})}(T)\\}\cong
N_{{\rm Sym}({\mathcal{Q}})}(T)$. This group is called the holomorph of $T$,
[75, Section 3.3], and we note that ${\rm Diag}_{q}(T)\rtimes A(T)\leq{\rm
Diag}_{q}({\rm Sym}(q))\rtimes L$ (recalling that $L={\rm Sym}(q)$ is the top
group).

######  Definition 5.8.

A code ${\mathcal{C}}$ in $H(q,q)$ is _diagonally $s$-neighbour-transitive_ if
${\mathcal{C}}$ is $(G,s)$-neighbour-transitive for some $G\leq{\rm
Diag}_{n}({\rm Sym}({\mathcal{Q}}))\rtimes L$. If $s=1$ we say simply that
${\mathcal{C}}$ is diagonally neighbour-transitive.

In [42] necessary and sufficient conditions on $T$ were obtained for the code
${\mathcal{C}}(T)$ to be diagonally neighbour-transitive.

######  Theorem 5.9.

[42, Theorem 2] Let ${\mathcal{N}}={\mathcal{Q}}=\\{1,2,\dots,q\\}$, let $T$
be a subgroup of ${\rm Sym}({\mathcal{Q}})$, and let ${\mathcal{C}}(T)$ be the
permutation code as in Definition 5.6. Then ${\mathcal{C}}(T)$ is diagonally
neighbour-transitive if and and only if $N_{{\rm Sym}({\mathcal{Q}})}(T)$ is
$2$-transitive.

Examples for which this 2-transitivity condition holds include elementary
abelian groups $T$ acting regularly, as well as almost simple $2$-transitive
groups. We note that all finite $2$-transitive groups are known explicitly,
see for example [22], and that this classification depends on the finite
simple group classification. The diagonally neighbour-transitive codes
${\mathcal{C}}(T)$ are building blocks for constructing _frequency permutation
arrays_ (codes in $H(mq,q)$ where each element of ${\mathcal{Q}}$ occurs $m$
times as an entry in each codeword; introduced in [57]). It was shown in [42,
Theorem 2] that, for each diagonally neighbour-transitive permutation code
${\mathcal{C}}(T)$ and each positive integer $m$, the repetition code ${\rm
Rep}_{m}({\mathcal{C}}(T))$ (see Definiiton 4.4) is a diagonally neighbour-
transitive frequency permutation array in $H(mq,q)$. In particular, when
$N_{{\rm Sym}({\mathcal{Q}})}(T)$ is an almost simple $2$-transitive group,
all of these diagonally neighbour-transitive codes, ${\mathcal{C}}(T)$ and
${\rm Rep}_{m}({\mathcal{C}}(T))$, are alphabet-almost-simple as in Definition
5.4. In fact, these may be regarded as archetypical examples for alphabet-
almost-simple codes with minimum distance at least three. In the following
result, part (1) was proved first in [41, Section 7] and more succinctly in
[39, Proposition 3.3]; while part (2) was proved in [41, Theorem 1.1].

######  Theorem 5.10.

Let ${\mathcal{C}}$ be a code in $H({\mathcal{N}},{\mathcal{Q}})=H(n,q)$ which
is $G$-alphabet-almost-simple and $G$-neighbour-transitive with $\delta\geq
3$. Then

  1. $(1)$

there is a $G$-invariant partition ${\mathcal{J}}$ of ${\mathcal{N}}$ such
that, for $J\in{\mathcal{J}}$, the projection $\pi_{J}({\mathcal{C}})$ is
equivalent to a diagonally $\chi_{J}(G)$-neighbour-transitive code with
minimum distance $\delta(\pi_{J}({\mathcal{C}}))\geq 2$;

  2. $(2)$

${\mathcal{C}}$ has a sub-code $\SS$ which is a neighbour-transitive frequency
permutation array, and ${\mathcal{C}}$ is a disjoint union of $G$-images of
$\SS$.

We make some comments about the links between the two parts of Theorem 5.10,
and the structure of the sub-code $\SS$ in part (2).

######  Remark 5.11.

(a) It follows from [42, Theorems 1 and 3] that the projected codes
$\pi_{J}({\mathcal{C}})$ in part (1) of Theorem 5.10 are either frequency
permutation arrays or repetition codes.

(b) Some explicit information about the possibilities for the neighbour-
transitive sub-code $\SS$ in part (2) of Theorem 5.10 is provided by [41,
Theorem 1.1] as follows: $\SS$ is equivalent to a code of the form ${\rm
Prod}_{\ell}({\rm Rep}_{k}({\mathcal{C}}^{\prime}))$ (with $\ell,k\geq 1$),
where ${\rm Prod}_{\ell}$ and ${\rm Rep}_{k}$ are the product and repetition
constructions defined in Definition 4.4. Moreover, the small code
${\mathcal{C}}^{\prime}$ itself has one of three specific forms described in
[41, (7,4), (7.5), (7.6)], namely the trivial code ${\mathcal{Q}}$ of length
$1$, or a permutation code ${\mathcal{C}}(T)$ as in Definition 5.6, or a
twisted version ${\mathcal{C}}(T,T^{\sigma})$ of a permutation code defined
and studied in [3, 44].

(c) The code ${\mathcal{C}}$ in Theorem 5.10 may have minimum distance
strictly larger than that of the projected codes $\pi_{J}({\mathcal{C}})$ in
part (1). An insightful example was given in [41, Example 9.1], where
$\SS={\rm Prod}_{\ell}({\mathcal{C}}(A_{q}))$, and ${\mathcal{C}}$ is a
disjoint union of two $G$-translates of $\SS$. Each of the codes
${\mathcal{C}}$ and $\SS$ has minimum distance $3$, while
$\pi_{J}({\mathcal{C}})$ is the permutation code ${\mathcal{C}}(S_{q})$ with
minimum distance $2$.

We give some explicit constructions of alphabet-almost-simple neighbour-
transitive codes, the first built from permutation codes.

######  Example 5.12.

Let ${\mathcal{N}}={\mathcal{Q}}=\\{1,\ldots,q\\}$, and let $T\leq{\rm S}_{q}$
be such that the permutation code ${\mathcal{C}}={\mathcal{C}}(T)$ in $H(q,q)$
is diagonally neighbour-transitive (see Theorem 5.9). Then, letting
${\mathcal{M}}={\mathcal{N}}\times\\{1,\ldots,k\\}$, as in Definition 4.4, the
product code ${\rm Prod}_{k}({\mathcal{C}})$ and the repetition code ${\rm
Rep}_{k}({\mathcal{C}})$ are neighbour-transitive codes in
$H({\mathcal{M}},{\mathcal{Q}})$. Moreover, for each of these codes, and for
each $i=1,\ldots,k$, the projection with respect to
${\mathcal{N}}\times\\{i\\}$ is equal to ${\mathcal{C}}(T)$. The following
codes are additional examples of codes that again project to
${\mathcal{C}}(T)$ with respect to ${\mathcal{N}}\times\\{i\\}$, and properly
lie between ${\rm Rep}_{k}({\mathcal{C}})$ and ${\rm
Prod}_{k}({\mathcal{C}})$. Recall from Definition 4.4 that if
$g_{1},\ldots,g_{k}$ are functions ${\mathcal{N}}\rightarrow{\mathcal{Q}}$
then $\beta_{g_{1},\ldots,g_{k}}$ is a vertex of
$H({\mathcal{M}},{\mathcal{Q}})$, and note that if $g\in T$ then $g$ is a
function ${\mathcal{Q}}\rightarrow{\mathcal{Q}}$.

  1. (1)

Let $T={\rm S}_{q}$ and consider the code consisting of all
$\beta_{t_{1},\ldots,t_{k}}$ such that $t_{1},\ldots,t_{k}\in T$ and
$t_{1}t_{2}\cdots t_{k}\in{\rm A}_{n}$. (If $k$ is even then this is one of
the codes corresponding to the ‘elusive’ code ${\mathcal{C}}(q,k)$ in [55,
Lemma 3.9], from which it follows that ${\rm Prod}_{k}({\mathcal{C}})$ is
neighbour-transitive.)

  2. (2)

Let $1\neq H\lhd T$ and let

${\rm Prod}(T,k,H)=\\{\beta_{h_{1}t,\ldots,h_{k}t}\mid h_{1},\ldots,h_{k}\in
H,\,t\in T\\}.$

We state below that ${\rm Prod}(T,k,H)$ is neighbour-transitive as long as
$N_{{\rm S}_{q}}(H)$ is $2$-transitive. Note that several explicit examples
are given, and precise requirements on $H$ and $T$ related to the neighbour-
transitivity of ${\rm Prod}(T,k,H)$ are discussed further, in [54].

######  Proposition 5.13.

[54] Let $k$ be a positive integer, let $T\leq{\rm S}_{q}$ and let $1\neq
H\lhd T$ such that $N_{{\rm S}_{q}}(H)$ is $2$-transitive. Then the code ${\rm
Prod}(T,k,H)$ in Example 5.12(2) is neighbour-transitive.

######  Problem 5.14.

Investigate further the codes ${\rm Prod}(T,k,H)$ in Example 5.12.

The second construction is a general version of the twisted permutation codes
${\mathcal{C}}(T,T^{\sigma})$ from Remark 5.11(b). Not all of them will arise
as the building block ${\mathcal{C}}^{\prime}$ for alphabet-almost-simple
codes. More details of this construction are available in [3, 44].

######  Definition 5.15.

Let $T$ be a group with (not necessarily distinct) permutation representations
$\rho_{1},\ldots,\rho_{k}:G\rightarrow{\rm S}_{q}$, let
${\mathcal{Q}}=\\{1,\ldots,q\\}$ and let
${\mathcal{N}}={\mathcal{Q}}\times\\{1,\ldots,k\\}$. We define the _twisted
permutation code_ ${\mathcal{C}}(T;\rho_{1},\ldots,\rho_{k})$ in $H(kq,q)$ as
the code consisting of the functions ${\mathcal{N}}\rightarrow{\mathcal{Q}}$
given by $(i,j)\mapsto i^{\rho_{j}(t)}$, for each $t\in T$.

One benefit of a twisted permutation code
${\mathcal{C}}(T;\rho_{1},\ldots,\rho_{k})$ in $H(kq,q)$ over the usual
repetition code ${\rm Rep}_{k}({\mathcal{C}}(T))$ in the same graph $H(kq,q)$
is that the minimum distance of the twisted version may be greater than for
the untwisted code ${\rm Rep}_{k}({\mathcal{C}}(T))$. Some examples are given
in Table 1. While it is only the examples in Lines 1–3 which arise in
connection with alphabet-almost-simple codes, examples in the other lines,
especially Lines 5–6 demonstrate that the differences between the minimum
distances of the twisted and untwisted codes can be unbounded. The groups
$G_{t}$ in line 6 are defined and studied in [3, Section 3.1]; $G_{t}$ is a
certain subgroup of ${\rm AGL}_{t}(p)$, it contains the translation group and
has order $p^{t+1}$.

Among this diverse family of alphabet-almost-simple, neighbour-transitive
codes, very few are $2$-neighbour-transitive. In fact we have the following
classification of such codes.

Line | $T$ | $q$ | $k$ | $\delta_{\rm tw}$ | $\delta_{\rm rep}$
---|---|---|---|---|---
1 | ${\rm S}_{6}$ | $6$ | $2$ | $8$ | $4$
2 | ${\rm A}_{6}$ | $6$ | $2$ | $8$ | $6$
3 | ${\rm ASL}_{3}(2)$ | $8$ | $2$ | $12$ | $8$
4 | ${\rm S}_{6}$ | $60$ | $4$ | $\leq 224$ |  $176$–$192$
5 | ${\rm Sp}_{4}(2^{n})$ | $2^{3n}+2^{2n}+2^{n}+1$ | $2$ | $2^{3n+1}+2^{2n}$ | $2^{3n+1}$
6 | $G_{t}$ | $p^{t}$ | $p$ | $p^{t+1}-p$ | $p^{t+1}-p^{2}$
Table 1: Groups $T$ giving twisted permutation codes in $H(kq,q)$ with minimum
distance $\delta_{\rm tw}$ strictly greater than the minimum distance
$\delta_{\rm rep}$ of the $k$-fold repetition of ${\mathcal{C}}(T)$. Lines 1–4
can be found in [44] while lines 5 and 6 are in [3].

######  Theorem 5.16.

[39, Theorem 1.1] Suppose that ${\mathcal{C}}$ is an alphabet-almost-simple,
$2$-neighbour-transitive code in $H(n,q)$ with minimum distance $\delta\geq
3$. Then $n=\delta=3$, $q\geq 5$, and ${\mathcal{C}}$ is equivalent to the
repetition code ${\rm Rep}_{3}(q)$.

####  2 Alphabet-affine codes in Hamming graphs

In this section we consider codes that are alphabet-affine (Definition 5.4),
that is, codes $H(n,q)$ having an automorphism group not acting faithfully on
entries, and giving rise to a $2$-transitive affine group in the action
induced on the alphabet. A natural family of examples of such codes are the
cyclic codes: a code ${\mathcal{C}}$ in $H({\mathcal{N}},{\mathbb{F}}_{q})$

is called cyclic if ${\mathcal{C}}$ is linear and there exists an $n$-cycle
$\sigma\in L\cap{\rm Aut}({\mathcal{C}})$. (7)

In particular each cyclic code ${\mathcal{C}}$ is alphabet-affine since ${\rm
Aut}({\mathcal{C}})$ contains the subgroup of translations by elements of
${\mathcal{C}}$ (acting transitively on ${\mathcal{C}}$). Moreover, a cyclic
code is neighbour-transitive since ${\rm Aut}({\mathcal{C}})$ also contains
both the subgroup of scalars and an $n$-cycle from the top group $L$. On the
other hand, if $x=h\sigma$ with $h\in B$ and $\sigma\in L$, then $x\in{\rm
Aut}({\mathcal{C}})$ does not necessarily imply that $\sigma\in{\rm
Aut}({\mathcal{C}})$. That is to say, a linear code ${\mathcal{C}}$ may not be
cyclic even if the induced group ${\rm Aut}({\mathcal{C}})^{\mathcal{N}}$ on
entries contains an $n$-cycle. We exhibit a small non-cyclic linear code with
this property in Example 5.18. In fact, as we see below, the class of codes
that are alphabet-affine and neighbour-transitive is strictly larger than the
class of cyclic codes.

######  Proposition 5.17.

Let ${\mathcal{C}}$ be a linear code with minimum distance $\delta\geq 3$ in
$H({\mathcal{N}},{\mathbb{F}}_{q})$. Then ${\mathcal{C}}$ is neighbour-
transitive if and only if ${\rm Aut}({\mathcal{C}})^{{\mathcal{N}}}$ is
transitive. In particular, if ${\mathcal{C}}$ is a cyclic code then
${\mathcal{C}}$ is neighbour-transitive.

###### Proof.

If ${\mathcal{C}}$ is neighbour-transitive then, by Proposition 5.1, ${\rm
Aut}({\mathcal{C}})^{\mathcal{N}}$ is transitive. Suppose now that ${\rm
Aut}({\mathcal{C}})^{\mathcal{N}}$ is transitive. Since ${\mathcal{C}}$ is
linear, ${\rm Aut}({\mathcal{C}})$ contains $T_{{\mathcal{C}}}$, which acts
transitively on ${\mathcal{C}}$. Moreover, this implies that ${\rm
Aut}({\mathcal{C}})=T_{{\mathcal{C}}}.{\rm
Aut}({\mathcal{C}})_{{\mathbf{0}}}$. In particular, ${\rm
Aut}({\mathcal{C}})_{{\mathbf{0}}}^{{\mathcal{N}}}$ is transitive. For each
$i\in{\mathcal{N}}$, let $e_{i}:{\mathcal{N}}\rightarrow{\mathbb{F}}_{q}$ such
that $e_{i}:i\to 1$ and $e_{i}:k\to 0$ if $k\neq i$. Then
$\Gamma_{1}({\mathbf{0}})=\\{ae_{i}\mid a\in{\mathbb{F}}_{q}^{\times}\\}$. Let
$i,j\in{\mathcal{N}}$ and $a_{i},a_{j}\in{\mathbb{F}}_{q}^{\times}$ so that
$a_{i}e_{i},a_{j}e_{j}\in\Gamma_{1}({\mathbf{0}})$. Then, since ${\rm
Aut}({\mathcal{C}})_{{\mathbf{0}}}$ induces a transitive action on
${\mathcal{N}}$, there exists an $x\in{\rm Aut}({\mathcal{C}})_{{\mathbf{0}}}$
such that $(a_{i}e_{i})^{x}=be_{j}$, for some $b\in{\mathbb{F}}_{q}^{\times}$.
Using the linearity of ${\mathcal{C}}$ again, scalar multiplication by
$a_{j}b^{-1}$ gives an element of ${\rm Aut}({\mathcal{C}})_{{\mathbf{0}}}$,
and hence we can map $a_{i}e_{i}$ to $a_{j}e_{j}$. It then follows from Lemma
2.6 that ${\mathcal{C}}$ is neighbour-transitive. The last sentence holds
since ${\mathcal{C}}$ being cyclic implies that ${\rm
Aut}({\mathcal{C}})^{\mathcal{N}}$ is transitive. ∎

######  Example 5.18.

Consider the linear code ${\mathcal{C}}$ in $H(4,{\mathbb{F}}_{3})$ consisting
of the codeword $(0,0,0,0)$ as well as the following $8$ non-zero codewords:

$\begin{array}[]{cc}(0,1,1,1)&(0,2,2,2)\\\ (1,0,1,2)&(2,0,2,1)\\\
(2,1,0,2)&(1,2,0,1)\\\ (2,2,1,0)&(1,1,2,0).\end{array}$

The automorphism $x:(a,b,c,d)\mapsto(d,a,b,2c)$ of ${\mathcal{C}}$ fixes
$(0,0,0,0)$ and cycles through the $8$ non-zero codewords of ${\mathcal{C}}$;
$x$ has order $8$ and projects to the $4$-cycle $(1\,2\,3\,4)$ in the top
group $L\cong{\rm S}_{4}$. However ${\mathcal{C}}$ is not cyclic, for if
$\sigma$ is a $4$-cycle in $L$ then, since the only codeword consisting of one
$0$ and three $1$s is $(0,1,1,1)$, the image $(0,1,1,1)^{\sigma}$ cannot lie
in ${\mathcal{C}}$. On the other hand, ${\mathcal{C}}$ has minimum distance
$\delta=3$ and satisfies all the hypotheses of Proposition 5.17, so it is
neighbour-transitive. Moreover, ${\mathcal{C}}$ is not equivalent to any
cyclic code (one way to see this is to observe that the subspace spanned by
$\\{\alpha^{\sigma^{k}}\mid k=0,1,2,3\\}$ contains a weight $2$ vector, for
each of $\alpha=(0,1,1,1),(0,1,1,2),(0,1,2,1)$ and where
$\sigma=(1\,2\,3\,4)$). Note also that ${\mathcal{C}}$ is the projective
Reed–Muller code ${\mathcal{P}\mathcal{R}\mathcal{M}}_{3}(1,2)$, which we meet
later on in Definition 5.28.

The next result suggests investigating the submodule structure of certain
modules, which we consider further in subsequent sections. For a group $G$ and
a prime $p$, $O_{p}(G)$ denotes the largest normal $p$-subgroup of $G$.

######  Proposition 5.19.

[56, Proposition 3.5] Let ${\mathcal{C}}$ be a code in the Hamming graph
$H(n,q)$, with $q=p^{d}$ for a prime $p$, such that ${\mathcal{C}}$ is
$G$-alphabet-affine and $(G,2)$-neighbour-transitive, with $\delta\geq 5$, and
suppose that $\mathbf{0}\in C$. Then ${\mathcal{C}}$ contains a subcode
${\mathcal{S}}$ such that ${\mathcal{S}}$ is the code formed by the orbit of
$\mathbf{0}$ under $O_{p}(K)$, where $K=G\cap B$. Moreover, it follows that:

  1. $(1)$

${\mathcal{S}}$ is a block of imprimitivity for the action of $G$ on
${\mathcal{C}}$, and $G_{{\mathcal{S}}}=O_{p}(K)\rtimes G_{\mathbf{0}}$,

  2. $(2)$

${\mathcal{S}}$ is $G_{{\mathcal{S}}}$-alphabet-affine and
$(G_{{\mathcal{S}}},2)$-neighbour-transitive with minimum distance
$\delta_{{\mathcal{S}}}\geq\delta$,

  3. $(3)$

${\mathcal{S}}$ is an ${\mathbb{F}}_{p}G_{\mathbf{0}}$-module, and if
${\mathcal{S}}\neq{\rm Rep}_{n}(2)$ then $q^{2}$ divides $|{\mathcal{S}}|$.

The following result gives further, fairly strong, restrictions on the
structure of the automorphism group of a $2$-neighbour-transitive code.

######  Lemma 5.20.

[53] Let ${\mathcal{C}}$ be a code in $H(n,q)=H({\mathcal{N}},{\mathcal{Q}})$
that is $(G,2)$-neighbour-transitive with minimum distance $\delta\geq 5$.

  1. $(1)$

If in addition ${\mathcal{C}}$ is $G$-alphabet-affine, then
$G_{{\mathbf{0}},i}^{{\mathcal{Q}}_{i}^{\times}}\leq\Gamma{\rm L}_{1}(q)$.

  2. $(2)$

Alternatively, if ${\mathbf{0}}\in{\mathcal{C}}$ and $K=B\cap G$, then
$K_{\mathbf{0}}\cong{\rm Diag}_{n}(H)$, where $H$ acts semi-regularly on
${{\mathcal{Q}}}_{i}^{\times}$ for all $i\in{\mathcal{N}}$.

####  3 Codes in binary Hamming graphs

When we restrict the alphabet ${\mathcal{Q}}$ to be the field
${\mathbb{F}}_{2}$ of order $2$ then we obtain very tight descriptions of the
possibilities for $(G,s)$-neighbour-transitive codes with minimal distance not
too small. Recall from Proposition 5.1 that for such codes, the stabiliser in
$G$ of a codeword induces an $s$-homogeneous action on entries. Also, for a
code ${\mathcal{C}}\leq{\mathbb{F}}_{2}^{n}$, $T_{\mathcal{C}}$ denotes the
set of all translations by elements of ${\mathcal{C}}$; if $T_{\mathcal{C}}$
is a subgroup of ${\rm Aut}({\mathcal{C}})$ then ${\mathcal{C}}$ is additively
closed. The next result gives a nearly complete description of the binary
$2$-neighbour-transitive codes with $\delta$ at least $5$.

######  Theorem 5.21.

[56, Theorem 1.2] Let ${\mathcal{C}}$ be a code in $H(n,2)$ with minimum
distance $\delta\geq 5$. Then ${\mathcal{C}}$ is $2$-neighbour-transitive if
and only if one of the following holds:

  1. $(1)$

${\mathcal{C}}$ is the binary repetition code ${\rm Rep}_{n}(2)$ with
$\delta=n$.

  2. $(2)$

${\mathcal{C}}$ is one of the following codes (see [38, Definition 4.1]):

    1. $(a)$

the Hadamard code with $n=12$ and $\delta=6$;

    2. $(b)$

the punctured Hadamard code with $n=11$ and $\delta=5$;

    3. $(c)$

the even weight subcode of the punctured Hadamard code with $n=11$ and
$\delta=6$.

  3. $(3)$

There exists a linear subcode ${\mathcal{S}}\subseteq{\mathcal{C}}$ with
dimension $k$ and minimum distance $\delta$, and a subgroup
$G_{\mathbf{0}}\leq{\rm Aut}({\mathcal{C}})_{\mathbf{0}}$, where
${\mathcal{S}}$, $G_{\mathbf{0}}$, $n,\delta$ and $k$ are as in Table 2, such
that

    1. $(a)$

${\mathcal{S}}$ is $(G,2)$-neighbour-transitive, where
$G=T_{{\mathcal{S}}}\rtimes G_{\mathbf{0}}\leq{\rm Aut}({\mathcal{C}})$, and,

    2. $(b)$

${\mathcal{C}}$ is the union of a set $\Delta$ of cosets of ${\mathcal{S}}$,
and ${\rm Aut}({\mathcal{C}})$ acts transitively on $\Delta$.

######  Remark 5.22.

Table 2 gives the possibilities for the linear subcode ${\mathcal{S}}$ of
${\mathcal{C}}$ in Theorem 5.21(3)(a). For each line of Table 2, the code
${\mathcal{C}}$ in Theorem 5.21(3)(b) is identified in the relevant part of
the proof of [56, Theorem 4.5]. We note that the minimum distance $\delta$ of
${\mathcal{C}}$ satisfies $5\leq\delta<n$ in all lines except possibly line 9.
In both of the lines 8 and 9 of Table 2 we have ${\rm
soc}(G_{\mathbf{0}})={\rm PSU}_{3}(r)$, and it follows from the proof of [56,
Theorem 4.5] that ${\mathcal{S}}$ is self-orthogonal (that is,
${\mathcal{S}}\subseteq{\mathcal{S}}^{\perp}$) if $r\equiv 3\pmod{4}$ but not
if $r\equiv 1\pmod{4}$. Self-orthogonality ensures that only the example in
line 8 of a minimal $(G,2)$-neighbour-transitive code arises when $r\equiv
3\pmod{4}$, while for $r\equiv 1\pmod{4}$ we have two different examples, one
for each of lines 8 and 9 of Table 2. It was proved, see [56, Remark 1.3],
that the codes in line 9 have minimum distance $\delta\geq 4$, and it is an
open problem to determine precisely which values of $r\equiv 1\pmod{4}$
correspond to a code with $\delta\geq 5$.

Line | ${\rm soc}(G_{\mathbf{0}})$ | $n$ | $\delta$ | $k$ | Conditions
---|---|---|---|---|---
1 | ${\mathbb{Z}}_{p}^{d}$ | $r=p^{d}$ | $\geq(r-1)^{1/2}+1$ | $\frac{r-1}{2}$ | $23\leq r\equiv 7\pmod{8}$
|  |  |  |  |  $2$-hom. not $2$-trans.
2 | ${\mathbb{Z}}_{2}^{t}$ | $2^{t}$ | $2^{t-1}$ | $t+1$ |  $t\geq 4$, $2$-trans.
3 | ${\rm PSL}_{t}(2^{a})$ | $\frac{2^{at}-1}{2^{a}-1}$ | $\geq\frac{2^{a(t-1)}-1}{2^{a}-1}+1$ | $t^{a}$ |  $t\geq 3$, $(a,t)\neq(1,3)$
4 | ${\rm A}_{7}$ | $15$ | $8$ | $4$ | -
5 | ${\rm PSL}_{2}(r)$ | $r+1$ | $\geq r^{1/2}+1$ | $\frac{r+1}{2}$ | $23\leq r\equiv\pm 1\pmod{8}$
|  |  |  |  | not $3$-trans.
6 | ${\rm Sp}_{2t}(2)$ | $2^{2t-1}-2^{t-1}$ | $2^{2t-2}-2^{t-1}$ | $2t+1$ | $t\geq 3$
7 | ${\rm Sp}_{2t}(2)$ | $2^{2t-1}+2^{t-1}$ | $2^{2t-2}$ | $2t+1$ | $t\geq 3$
8 | ${\rm PSU}_{3}(r)$ | $r^{3}+1$ | $\geq r^{2}+1$ | $r^{2}-r+1$ |  $r$ is odd
9 | ${\rm PSU}_{3}(r)$ | $r^{3}+1$ | $\geq 4$ | $r^{3}-r^{2}+r$ | $r\equiv 1\pmod{4}$
10 | ${\rm Ree}(r)$ | $r^{3}+1$ | $\geq r^{2}+1$ | $r^{2}-r+1$ | $r\geq 3$
11 | ${\rm M}_{22}$ | $22$ | $8$ | $10$ | -
12 | ${\rm M}_{23}$ | $23$ | $8$ | $11$ | -
13 | ${\rm M}_{24}$ | $24$ | $8$ | $12$ | -
14 | ${\rm HS}$ | $176$ | $\geq 50$ | $21$ | -
15 | ${\rm Co}_{3}$ | $276$ | $100$ | $23$ | -
Table 2: Parameters for the $(G,2)$-neighbour-transitive code ${\mathcal{S}}$
in Theorem 5.21(3). See Remark 5.22 for more information.

In Theorem 5.21(3) the linear subcode ${\mathcal{S}}$ (see Proposition 5.19)
is a submodule of the permutation module over ${\mathbb{F}}_{2}$ of a
$2$-homogeneous permutation group. The next lemma explores the properties of
such subcodes.

######  Lemma 5.23.

[56, Lemma 4.3] Let $H$ act $2$-homogeneously on a set ${\mathcal{N}}$ of size
$n\geq 5$, let $V\cong{\mathbb{F}}_{2}^{n}$ be the permutation module for the
action of $H$ on ${\mathcal{N}}$, and let ${\mathcal{C}}$ be a proper
${\mathbb{F}}_{2}H$-submodule of $V$. Then ${\mathcal{C}}$ is a code in
$H({\mathcal{N}},{\mathbb{F}}_{2})$ with minimum distance $\delta$ and the
group $G:=T_{{\mathcal{C}}}\rtimes H\leq{\rm Aut}({\mathcal{C}})$, where
precisely one of the following holds:

  1. $(1)$

${\mathcal{C}},\delta,G$ satisfy one of the lines of Table 3;

  2. $(2)$

$\delta=3$, ${\mathcal{C}}$ is a perfect code in
$H({\mathcal{N}},{\mathbb{F}}_{2})$, and ${\mathcal{C}}$ is $G$-neighbour-
transitive; or

  3. $(3)$

$4\leq\delta<n$ and ${\mathcal{C}}$ is $(G,2)$-neighbour-transitive.

${\mathcal{C}}$ | $\delta$ | Properties
---|---|---
${\rm Rep}_{n}(2)$ | $n$ |  $(G,2)$-neighbour-transitive
${\rm Rep}_{n}(2)^{\perp}$ | $2$ |  $G$-completely-transitive
Table 3: Codes arising in Lemma 5.23(1) and their properties.

Every perfect code with minimum distance $3$ in $H(n,2)$ has the same
parameters as a Hamming code, see [90]. Thus, in a sense, Lemma 5.23 part (2)
is well understood, as is part (1). In addition, those codes in Lemma 5.23
part (3) having minimum distance at least $5$ are described in Theorem 5.21.
Thus, the codes in Lemma 5.23 for which least is known are those in part (3)
with $\delta=4$. These are the subject of Problem 5.24.

######  Problem 5.24.

Determine all codes with minimum distance $\delta=4$ corresponding to
submodules of the permutation module over ${\mathbb{F}}_{2}$ of a
$2$-homogeneous permutation group.

Note that a completely transitive code ${\mathcal{C}}$ in
$H(n,2)=H({\mathcal{N}},2)$ with minimum distance $\delta\geq 5$ has covering
radius $\rho\geq 2$, and hence is $2$-neighbour-transitive so that Theorem
5.21 may be applied. In particular, if ${\mathcal{C}}\neq{\rm Rep}_{n}(2)$,
then the induced subgroup $S\cong{\rm soc}({\rm
Aut}({\mathcal{C}})_{\mathbf{0}}^{\mathcal{N}})$ is as in Theorem 5.21(2) or
(3), so $S$ is either a small Mathieu group ${\rm M}_{11},{\rm M}_{12}$, or
$S$ is one of the groups in the column ‘${\rm soc}(G_{\mathbf{0}})$’ of Table
2. This observation was exploited in [7] to obtain a partial classification,
stated in Theorem 5.25, of binary completely transitive codes with minimum
distance at least $5$.

######  Theorem 5.25.

[7, Theorem 1.3] Let ${\mathcal{C}}$ be a non-trivial completely transitive
code in $H(n,2)$ with minimum distance $\delta\geq 5$, and suppose that the
socle $S$ of the group induced by ${\rm Aut}({\mathcal{C}})_{\mathbf{0}}$ on
${\mathcal{N}}$ is as in one of the lines of Table 4. Then ${\mathcal{C}}$ is
equivalent to one of the codes in Table 5. Moreover, each code in Table 5 is
completely transitive.

$S$ | $n$ | Conditions
---|---|---
${\rm PSL}_{3}(4)$ | $21$ | -
${\rm A}_{7}$ | $15$ | -
${\rm PSL}_{2}(r)$ | $r+1$ | $23\leq r\equiv\pm 1\pmod{8}$
${\rm PSU}_{3}(r)$ | $r^{3}+1$ |  $r$ is odd
${\rm Ree}(r)$ | $r^{3}+1$ | $r\geq 3$
${\rm M}_{m}$ | $11,12,22,23,24$ | -
${\rm HS}$ | $176$ | -
${\rm Co}_{3}$ | $276$ | -
Table 4: Some groups $S$ for which there exists a non-trivial binary $2$-neighbour-transitive code ${\mathcal{C}}$ in $H(n,2)$ such that ${\mathcal{C}}\neq{\rm Rep}_{n}(2)$ and $S\cong{\rm soc}({\rm Aut}({\mathcal{C}})_{\mathbf{0}}^{\mathcal{N}})$. Line | ${\mathcal{C}}$ | ${\rm Aut}({\mathcal{C}})$ | Parameters
---|---|---|---
1 | ${\mathcal{H}}$ | $2{\rm M}_{12}$ | $(12,24,6;3)$
2 | ${\mathcal{P}\mathcal{H}}$ | $2\rtimes{\rm M}_{11}$ | $(11,24,5;3)$
3 | ${\mathcal{N}\mathcal{R}}$ | $2^{5}\rtimes{\rm A}_{8}$ | $(15,256,5;3)$
4 | $\langle{\mathcal{L}},\Delta_{1}\rangle\cup\langle{\mathcal{L}},\Delta_{2}\rangle$ | $T_{\mathcal{L}}\rtimes{\rm P}\Gamma{\rm L}_{3}(4)$ | $(21,2^{10}\cdot 3,5;6)$
5 | ${\mathcal{P}}^{\perp}$ | $T_{C}\rtimes{\rm P}\Gamma{\rm L}_{3}(4)$ | $[21,12,5;3]$
6 | $\langle{\mathcal{L}},\Delta_{1}\rangle$ | $T_{C}\rtimes{\rm P}\Sigma{\rm L}_{3}(4)$ | $[21,11,5;6]$
7 | ${\mathcal{L}}$ | $T_{C}\rtimes{\rm P}\Gamma{\rm L}_{3}(4)$ | $[21,10,5;6]$
8 | ${\mathcal{G}}_{24}$ | $T_{C}\rtimes{\rm M}_{24}$ | $[24,12,8;4]$
9 | ${\mathcal{G}}_{23}$ | $T_{C}\rtimes{\rm M}_{23}$ | $[23,12,7;3]$
10 | ${\mathcal{G}}_{23}^{\perp}$ | $T_{C}\rtimes{\rm M}_{23}$ | $[23,11,8;7]$
11 | ${\mathcal{G}}_{22}$ | $T_{C}\rtimes({\rm M}_{22}:2)$ | $[22,12,6;3]$
12 | ${\mathcal{E}\mathcal{G}}_{22}$ | $T_{C}\rtimes({\rm M}_{22}:2)$ | $[22,11,6;7]$
13 | ${\mathcal{S}\mathcal{G}}_{22}$ | $T_{C}\rtimes{\rm M}_{22}$ | $[22,11,7;6]$
Table 5: Non-trivial binary completely transitive codes ${\mathcal{C}}$ with
minimum distance $\delta\geq 5$ and where ${\rm
Aut}({\mathcal{C}})_{\mathbf{0}}^{{\mathcal{N}}}$ has as socle one of the
groups $S$ in Table 4. See [7, Section 3] for the definitions of these codes.
The codes in Lines 1–4 are non-linear with parameters
$(n,|{\mathcal{C}}|,\delta;\rho)$, while the remaining codes are linear with
parameters $[n,k,\delta;\rho]$, where $\rho$ is the covering radius of
${\mathcal{C}}$ and $k$ is the dimension.

Note that, of the groups $S$ occurring in Theorem 5.21(2) or (3), the only
ones not considered in Theorem 5.25 are the following groups ‘${\rm
soc}(G_{\mathbf{0}})$’ of Table 2: i) ${\rm PSL}_{t}(2^{a})$ unless
$(t,a)=(3,2)$, ii) ${\rm Sp}_{2t}(2)$ for $t\geq 3$, iii)
${\mathbb{Z}}_{2}^{t}$ for $t\geq 3$, or iv) ${\mathbb{Z}}_{p}^{d}$ where
$r=p^{d}\equiv 7\pmod{8}$. Thus the following problem is still open.

######  Problem 5.26.

Classify the binary completely transitive codes ${\mathcal{C}}$ in $H(n,2)$
with minimum distance at least $5$, for which ${\rm soc}({\rm
Aut}({\mathcal{C}})_{\mathbf{0}}^{\mathcal{N}})$ is one of i) ${\rm
PSL}_{t}(2^{a})$ with $(t,a)\neq(3,2)$, ii) ${\rm Sp}_{2t}(2)$ for $t\geq 3$,
iii) ${\mathbb{Z}}_{2}^{t}$ for $t\geq 3$, or iv) ${\mathbb{Z}}_{p}^{d}$ where
$23\leq n=p^{d}\equiv 7\pmod{8}$.

####  4 A non-existence result: proof of Theorem 3.1

We now have enough information about $G$-alphabet-affine and
$(G,s)$-neighbour-transitive codes to prove Theorem 3.1 which was stated in
Section 3.

###### Proof of Theorem 3.1.

If $n\geq 9$ and ${\mathcal{C}}={\rm Rep}_{n}(2)$ in $H(n,2)$ then, by Theorem
5.5, ${\mathcal{C}}$ is completely transitive with minimum distance
$\delta=n$, and hence error-correction capacity
$e=\lfloor\frac{n-1}{2}\rfloor$. Since $\Gamma_{i}({\mathbf{0}})$ consists
precisely of the weight $i$ vertices of $H(n,2)$ and
$\Gamma_{i}({\mathbf{0}})$ is contained in ${\mathcal{C}}_{i}$ if and only if
$i\leq n/2$, the largest value for $s$ for which ${\mathcal{C}}$ is
$s$-neighbour-transitive is $s=\lceil\frac{n-1}{2}\rceil$. Thus
$\min\\{e,s\\}\geq 4$ and all the conditions of Theorem 3.1 hold.

Suppose from now on that ${\mathcal{C}}$ is an $s$-neighbour-transitive code
in $H(n,q)$ with error capacity $e$ such that $\min\\{e,s\\}\geq 4$, and that
${\mathcal{C}}\neq{\rm Rep}_{n}(2)$. Let $G\leq{\rm Aut}({\mathcal{C}})$ such
that ${\mathcal{C}}$ is $(G,s)$-neighbour-transitive. Since $e\geq 4$ we have
$\delta\geq 9$, which also implies that $n\geq 9$. It now follows from Theorem
5.5 that, if ${\mathcal{C}}$ is $G$-entry-faithful then ${\mathcal{C}}$ is
equivalent to ${\rm Rep}_{n}(2)$. Let us assume now that ${\mathcal{C}}$ is
not $G$-entry-faithful, and that ${\mathcal{C}}$ is not equivalent to ${\rm
Rep}_{n}(2)$. Since $\delta\geq 9$, it follows from Theorem 5.16 that
${\mathcal{C}}$ is not $G$-alphabet-almost-simple and thus, by Proposition 5.3
and Definition 5.4, ${\mathcal{C}}$ is $G$-alphabet-affine.

Replacing ${\mathcal{C}}$ by an equivalent code we may assume that
$\mathbf{0}\in{\mathcal{C}}$. By Proposition 5.1, $G_{\mathbf{0}}$ acts
$4$-homogeneously on ${\mathcal{N}}$. Hence, by [22, Table 7.4] and [60],
$G_{\mathbf{0}}^{\mathcal{N}}$ is one of the groups in Table 6 of degree $n$.
Also, by Proposition 5.19, there exists a subcode ${\mathcal{S}}$ of
${\mathcal{C}}$ such that ${\mathcal{S}}$ is an
${\mathbb{F}}_{p}G_{\mathbf{0}}$-module. If $q=2$, then Theorem 5.21
eliminates each possibility for $G_{\mathbf{0}}^{\mathcal{N}}$ (recalling
where necessary that $\delta\geq 9$). Thus $q\geq 3$.

Let $I\subseteq{\mathcal{N}}$ with $|I|=4$. Now ${\mathcal{C}}$ is
$(G,4)$-neighbour-transitive (as $s\geq 4$), so $G_{\mathbf{0}}$ is transitive
on the set of all weight $4$ vertices of $H(n,q)$. Also, as $G_{\mathbf{0}}$
is $4$-homogeneous on ${\mathcal{N}}$, the setwise stabiliser
$G_{{\mathbf{0}},I}$ acts transitively on the set of weight $4$ vertices
having support $I$. Hence $(q-1)^{4}$ divides the order of
$G_{\mathbf{0},I}^{H(I,q)}$. Now by Lemma 5.20(1) the induced group
$G_{\mathbf{0},I}^{H(I,q)}$ is a subgroup of $\Gamma{\rm L}_{1}(q)\wr{\rm
S}_{4}$, and in particular is soluble. Also, by Lemma 5.20(2), the group
$K_{0}:=B\cap G_{\mathbf{0}}$ has order dividing $q-1$ and
$K_{\mathbf{0}}\cong K_{\mathbf{0}}^{H(I,q)}$. By the definition of $K_{0}$ we
have $G_{\mathbf{0},I}^{\mathcal{N}}\cong G_{\mathbf{0},I}/K_{\mathbf{0}}$,
and hence $G_{\mathbf{0},I}^{H(I,q)}/K_{\mathbf{0}}^{H(I,q)}$ is a soluble
quotient of $G_{\mathbf{0},I}^{\mathcal{N}}$ with order divisible by
$(q-1)^{3}$.

Recall that $n\geq 9$, and let ${\rm Sol}$ be the order of the largest soluble
normal subgroup of $G_{\mathbf{0},I}^{\mathcal{N}}$, For example, if
$G_{\mathbf{0}}^{\mathcal{N}}={\rm S}_{n}$ then
$G_{\mathbf{0},I}^{\mathcal{N}}={\rm S}_{4}\times{\rm S}_{n-4}$ so ${\rm
Sol}=2^{4}\cdot 3$. Since $(q-1)^{3}$ divides ${\rm Sol}$ it follows that the
possibilities for $q$ are as in Table 6. In particular the last three lines of
Table 6 are ruled out as there are no possibilities for $q$. If $q$ is $3$ or
$5$ then $K_{0}$ consists of scalars and the subcode ${\mathcal{S}}$ of
${\mathcal{C}}$ mentioned above is an
${\mathbb{F}}_{q}G_{\mathbf{0}}^{\mathcal{N}}$-module, of dimension $k$, say.
In particular ${\mathcal{S}}$ is a linear $[n,k,\delta^{\prime}]$ code with
$\delta^{\prime}\geq\delta\geq 9$, so by the Singleton bound [67, Theorem 11,
Chapter 1], $k\leq n-\delta+1\leq n-8$. This gives an immediate contradiction
for the first four lines of Table 6: for ${\rm A}_{n}$ and ${\rm S}_{n}$ by
[61, Proposition 5.3.7], for ${\rm M}_{11}$ and ${\rm M}_{12}$ by [61,
Proposition 5.3.8]. The remaining cases are $G_{\mathbf{0}}^{\mathcal{N}}={\rm
M}_{23}$ or ${\rm M}_{24}$. A similar argument to that in the previous
paragraph, for a subset $J\subseteq{\mathcal{N}}$ with $|J|=2$ shows that
$q-1$ divides the order of a soluble quotient of
$G_{\mathbf{0},J}^{\mathcal{N}}$. However, for
$G_{\mathbf{0}}^{\mathcal{N}}={\rm M}_{23}$ or ${\rm M}_{24}$, the largest
soluble quotient of $G_{\mathbf{0},J}^{\mathcal{N}}$ has order 2. Thus $q=3$,
and again the subcode ${\mathcal{S}}$ of ${\mathcal{C}}$ is an
${\mathbb{F}}_{q}G_{\mathbf{0}}^{\mathcal{N}}$-module, of dimension $k$, say.
This implies, by [59], that $k\geq 22$, whereas the Singleton bound requires
$k\leq n-\delta+1\leq 24-8=16$. ∎

$G_{\mathbf{0}}^{\mathcal{N}}$ | $n$ | Sol | $q\geq 3$
---|---|---|---
${\rm A}_{n}$ | $n$ | $2^{3}\cdot 3$ | 3
${\rm S}_{n}$ | $n$ | $2^{4}\cdot 3$ | 3
${\rm M}_{11}$ | $11$ | $2^{3}\cdot 3$ | 3
${\rm M}_{12}$ | $12$ | $2^{6}\cdot 3$ | 3 or 5
${\rm M}_{23}$ | $23$ | $2^{7}\cdot 3^{2}$ | 3 or 5
${\rm M}_{24}$ | $24$ | $2^{9}\cdot 3^{2}$ | 3, 5 or 9
${\rm PSL}_{2}(8)$ | $9$ | $2^{2}\cdot 3$ | –
${\rm P}\Gamma{\rm L}_{2}(8)$ | $9$ | $2^{2}\cdot 3$ | –
${\rm P}\Gamma{\rm L}_{2}(32)$ | $33$ | $2^{2}$ | –
Table 6: $4$-homogeneous groups for the proof of Theorem 3.1.

####  5 Codes in Hamming graphs from permutation modules

In this section, we present examples of linear codes that are $s$-neighbour-
transitive, for $s\geq 2$, arising from permutation modules. We construct
these modules via polynomial algebras. Historically, polynomial algebras have
been used to construct many interesting examples of codes, such as the
generalised Reed–Muller codes and the projective Reed–Muller codes; see
Definitions 5.27 and 5.28 below. We present a richer family of examples that
may eventually lead to a classification of alphabet-affine, $2$-neighbour-
transitive codes in $H(n,q)$ with minimum distance at least five: such a
classification would be a huge strengthening of Theorem 3.1.

Throughout this section let $R={\mathbb{F}}_{q}[x_{1},\ldots,x_{t}]$, the ring
of polynomials with coefficients in ${\mathbb{F}}_{q}$ in the variables
$x_{1},\ldots,x_{t}$. Each element of $R$ may be viewed as a function
${\mathbb{F}}_{q}^{t}\rightarrow{\mathbb{F}}_{q}$ and conversely, by Lagrange
interpolation (see [65, Theorem 1.7.1]), every such function may be
represented (in at least one way) by an element of $R$. A monomial
$x_{1}^{a_{1}}\cdots x_{t}^{a_{t}}$ is said to have _degree_
$a_{1}+\cdots+a_{t}$ and the degree of a polynomial is the maximum value of
the degrees of its constituent monomials. The generalised Reed–Muller codes
arise as follows as subspaces of $R$; see [31].

######  Definition 5.27.

Let $k$ be an integer with $0\leq k\leq t(q-1)$. The _$k$ -th order $q$-ary
generalised Reed–Muller code_ ${\mathcal{R}\mathcal{M}}_{q}(k,t)$ in
$H({\mathbb{F}}_{q}^{t},{\mathbb{F}}_{q})$ is the subspace of $R$ consisting
of all polynomials of degree at most $k$. When $q=2$ these are simply called
_Reed–Muller_ codes.

The parameters of the generalised Reed–Muller codes are given in [5, Theorem
5.4.1 and Corollary 5.5.4]. Let $d\in\\{1,2,\ldots,q-1\\}$ and let $R[d]$ be
the subspace of $R$ consisting of all polynomials $f$ such that
$f(ax_{1},\ldots,ax_{t})=a^{d}f(x_{1},\ldots,x_{t})$, for each
$a\in{\mathbb{F}}_{q}$. In other words, $R[d]$ consists of all polynomials $f$
of $R$ such that each monomial of $f$ has non-zero degree equivalent to $d$
modulo $q-1$. This leads to a similar construction to that in the previous
definition, but now involving $R[d]$. See [85] for more details. Note that we
are taking ${\mathcal{N}}$ to be a set of representatives for the
$1$-dimensional subspaces of ${\mathbb{F}}_{q}^{t}$ and then regarding the
elements of $R[d]$ as functions ${\mathcal{N}}\rightarrow{\mathbb{F}}_{q}$.

######  Definition 5.28.

Let $k$ be an integer with $0\leq k\leq t(q-1)$, let ${\mathcal{N}}$ be a
fixed set of representatives for the $1$-dimensional subspaces of
${\mathbb{F}}_{q}^{t}$ and let $d\in\\{1,2,\ldots,q-1\\}$ such that $d\equiv
k\pmod{q-1}$. The _$k$ -th order $q$-ary projective Reed–Muller_ code
${\mathcal{P}\mathcal{R}\mathcal{M}}_{q}(k,t)$ in
$H({\mathcal{N}},{\mathbb{F}}_{q})$ is the subspace of $R[d]$ consisting of
all polynomials having degree at most $k$.

The ${\mathbb{F}}_{q}{\rm AGL}_{t}(q)$-submodule structure of $R$ was
determined by Sin [82], while the ${\mathbb{F}}_{q}{\rm GL}_{t}(q)$-submodule
structure of $R$ (and, in particular, of each $R[d]$) is determined in [11].
Any submodule of $R$ determines a code in
$H({\mathbb{F}}_{q}^{t},{\mathbb{F}}_{q})$ and any submodule of $R[d]$
determines a code in $H({\mathcal{N}},{\mathbb{F}}_{q})$, where
${\mathcal{N}}$ is a set of representatives for the $1$-dimensional subspaces
of ${\mathbb{F}}_{q}^{t}$. Indeed, the generalised Reed–Muller code
${\mathcal{R}\mathcal{M}}_{q}(k,t)$ is an ${\mathbb{F}}_{q}{\rm
AGL}_{t}(q)$-submodule of $R$ and the projective Reed–Muller code
${\mathcal{P}\mathcal{R}\mathcal{M}}_{q}(k,t)$ is an ${\mathbb{F}}_{q}{\rm
GL}_{t}(q)$-submodule of $R[d]$, where $d\in\\{1,2\ldots,q-1\\}$ such that
$d\equiv k\pmod{q-1}$. However, the submodule lattices of $R$ and $R[d]$ are,
in general, considerably more complicated than the chains of submodules given
by varying the parameter $k$ in ${\mathcal{R}\mathcal{M}}_{q}(k,t)$ and
${\mathcal{P}\mathcal{R}\mathcal{M}}_{q}(k,t)$, respectively. In particular,
if $r$ is such that $q=p^{r}$ for some $p$ prime then the submodule lattices
of $R$ and $R[d]$ are parameterised by $r$-tuples of integers satisfying
certain restrictions, see [11, Theorems A and C]. The next two results show
that, under certain conditions on the parameters $q,d$, many submodules of $R$
and $R[d]$ (including the generalised and the projective Reed–Muller codes and
their duals) give examples of $2$-neighbour-transitive codes. Note that in
Proposition 5.29, since $q=2$ is prime, the codes arising are precisely the
Reed–Muller codes and their duals. Recall that we denote by $T_{\mathcal{C}}$
the group of translations by elements of a linear code ${\mathcal{C}}$. In all
the propositions in this section we assume that the covering radius is at
least $2$; in Remark 5.35 we discuss the situation when this does not hold.

######  Proposition 5.29.

[53] (or see [51, Proposition 9.1.8]) Let $q=2$ and ${\mathcal{C}}$ be an
${\mathbb{F}}_{2}{\rm AGL}_{t}(2)$-submodule of $R$ such that ${\mathcal{C}}$
is a code with covering radius $\rho\geq 2$ in
$H({\mathbb{F}}_{2}^{t},{\mathbb{F}}_{2})$. Then ${\mathcal{C}}$ is
$(G,2)$-neighbour-transitive, where $G=T_{{\mathcal{C}}}\rtimes{\rm
AGL}_{t}(2)$.

######  Proposition 5.30.