ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 14 (2018) 345-357 https://doi.org/10.26493/1855-3974.1240.515
(Also available at http://amc-journal.eu)
Alphabet-almost-simple 2-neighbour-transitive
codes
Neil I. Gillespie
Heilbronn Institute for Mathematical Research, School of Mathematics, Howard House, University of Bristol, BS81SN, United Kingdom
Daniel R. Hawtin *
Centre for the Mathematics ofSymmetry and Computation, University of Western Australia, 35 Stirling Highway, Crawley, WA 6009, Australia
Received 28 November 2016, accepted 12 June 2017, published online 30 September 2017
Let X be a subgroup of the full automorphism group of the Hamming graph H (m, q), and C a subset of the vertices of the Hamming graph. We say that C is an (X, 2)-neighbour-transitive code if X is transitive on C, as well as Ci and C2, the sets of vertices which are distance 1 and 2 from the code. It has been shown that, given an (X, 2)-neighbour-transitive code C, there exists a subgroup of X with a 2-transitive action on the alphabet; this action is thus almost-simple or affine. This paper completes the classification of (X, 2)-neighbour-transitive codes, with minimum distance at least 5, where the subgroup of X stabilising some entry has an almost-simple action on the alphabet in the stabilised entry. The main result of this paper states that the class of (X, 2) neighbour-transitive codes with an almost-simple action on the alphabet and minimum distance at least 3 consists of one infinite family of well known codes.
Keywords: 2-neighbour-transitive, alphabet-almost-simple, automorphism groups, Hamming graph, completely transitive.
Math. Subj. Class.: 05E20, 68R05, 20B25
* This author was supported by an Australian Postgraduate Award and a University of Western Australia Safety-Net-Top-Up scholarship while this research was conducted, and would like to acknowledge an accommodation grant from the Heilbronn Institute for Mathematical Research.
E-mail addresses: neil.gillespie@bristol.ac.uk (Neil I. Gillespie), dan.hawtin@gmail.com (Daniel R. Hawtin)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
346
Ars Math. Contemp. 14 (2018) 267-284
1 Introduction
Ever since Shannon's 1948 paper [18, 19] there has been a great deal of interest around families of error-correcting codes with a high degree of symmetry. The rationale behind this interest is that codes with symmetry should have good error correcting properties. The first families classified were perfect (see [21] or [22]) and nearly-perfect (defined in [12], classified in [15]) codes over prime power alphabets. Note that the classification of nearly-perfect codes follows from the earlier results of [17] on uniformly packed codes, since nearly-perfect codes are uniformly packed codes with maximal packing density. These classifications show that perfect and nearly-perfect codes are rare. In an effort to find further classes of efficient codes, Delsarte [4] introduced completely regular codes, a more general class of codes that posses a high degree of combinatorial symmetry. Much effort has been put into classifying particular classes of completely regular codes (see for instance [1, 2]), and new completely regular codes continue to be found [6]. However, completely regular codes have proven to be hard to classify, and this remains an open problem.
Completely transitive codes (first defined in [20], with a generalisation studied in [10]) are a class of codes with a high degree of algebraic symmetry and are a subset of completely regular codes. As such a classification of completely transitive codes would be interesting from the point of view of classifying completely regular codes. This problem also remains open.
Here, the conditions of complete transitivity are relaxed and the family of 2-neighbour-transitive codes is studied, a class of codes with a moderate degree of algebraic symmetry. Note that every completely transitive code (see Section 2) is 2-neighbour-transitive. By studying this class of codes we hope to find new codes and gain a better understanding of completely transitive codes. Indeed a classification of 2-neighbour-transitive codes would have as a corollary a classification of completely transitive codes. We also note that codes with 2-transitive actions on the entries of the Hamming graph (which 2-neighbour-transitive codes indeed have), have been of interest lately, where this fact can be used to prove that certain families of codes achieve capacity on erasure channels [14]. The analysis of 2-neighbour-transitive codes is being attacked as three separate problems: entry-faithful (see [7]), alphabet-almost-simple, and alphabet-affine. This paper concerns the alphabetalmost-simple case. The results of this paper do not return any new examples.
However, the results here are of interest from the point of view of perfect codes over an alphabet of non-prime-power size, since in this case a code cannot be alphabet-affine (and also not entry-faithful, by [7]), but may be alphabet-almost-simple. The existence of perfect codes over non-prime-power alphabets with covering radius 1 or 2, is still an open question (see [13]). By Theorem 1.1, if such codes exist, then they cannot be 2-neighbour-transitive (unless they are equivalent to the repetition code of length 3). Note that in the prime power case, for each set of parameters for which a perfect code with covering radius p > 2 exists, a 2-neighbour-transitive code with those parameters exists. That is, the repetition and Golay codes are 2-neighbour-transitive. In fact, the repetition, Hamming and Golay codes are completely transitive (by [11, Example 3.1] for the repetition codes, [20, Proposition 7.3] for the Hamming and binary Golay codes, and [10, Example 3.5.6] for the ternary Golay codes).
N. I. Gillespie and D. R. Hawtin: Alphabet-almost-simple 2-neighbour-transitive codes
347
1.1 Statement of the main results
Let X be a subgroup of the full automorphism group S^ X Sm of the Hamming graph r = H(m, q) and let C be a code, that is, a subset of the set of vertices Vr. We say that C is an (X, s)-neighbour-transitive code if X fixes C setwise and acts transitively on C = C0, Ci,..., Cs (where Ci are parts of the distance partition, see Section 2). In joint work with Giudici and Praeger [7], the authors classified all (X, 2)-neighbour-transitive codes for which the group X acts faithfully on the set of entries of the Hamming graph. In this paper, we begin the study of (X, 2)-neighbour-transitive codes such that the action of X on the entries has a non-trivial kernel.
Let M be the set of entries of the Hamming graph H(m, q) and Qi be the copy of the alphabet Q in the corresponding entry i e M. Then the vertex set of H(m, q) is:
Vr = n Qi.
ieM
If C is an (X, 2)-neighbour-transitive code with minimum distance S > 3, then the subgroup Xi < X stabilising the entry i e M has a 2-transitive action on the alphabet Qi in that entry (see [7, Proposition 2.7]). Any 2-transitive group G is of affine type (G < AGLd(p) for some integer d and prime p) or almost-simple type (S < G < Aut(S) for some non-abelian simple group S) [5, Theorem 4.1B]. If the action of X on M (see Section 2.1) is transitive with a non-trivial kernel and the action of Xi on the alphabet Qi is almost-simple then we say C is X-alphabet-almost-simple. Our main aim here is to prove the non-existence of codes which are X-alphabet-almost-simple and (X, 2)-neighbour-transitive with minimum distance S > 4.
Theorem 1.1. Let C be an X-alphabet-almost-simple and (X, 2)-neighbour-transitive code in H(m, q) with minimum distance S > 3. Then S = 3 and C is equivalent to the repetition code in H(3, q), where q > 5.
In Section 2 we define the notation used in the paper. In Section 3 we give some results on the structure of codes that are X-alphabet-almost-simple and (X, 2)-neighbour-transitive, as well as pose some questions about codes for which the action of Xi on the alphabet in the entry i e M is affine. We present some examples of codes with properties of interest in relation to our results in Section 4. Finally, in Section 5, we give a classification of diagonally (X, 2)-neighbour-transitive codes (see Definition 3.1) and prove Theorem 1.1.
2 Preliminaries
Throughout this paper we let M = {1,..., m} and Q = {1,..., q}, with m, q > 2, though if q = 2 we will at times use Q = {0,1}. We refer to M as the set of entries and Q as the alphabet. We use Qi to denote the disjoint copy of the alphabet Q in the entry i e M. The vertex set Vr of the Hamming graph r = H(m, q) consists of all m-tuples with entries labeled by the set M, taken from the set Q. An edge exists between two vertices if they differ as m-tuples in exactly one entry. For vertices a, ft of H(m, q) the Hamming distance d(a, ,0) is the number of entries in which a and ft differ, i.e. the usual graph distance in r. For a e Vr, we refer to the element of Q appearing in the i-th entry of a as ai, so that a = (a1,..., am) throughout.
348
Ars Math. Contemp. 14 (2018) 267-284
A code C is a subset of the vertex set of the Hamming graph. The minimum distance of C is S = min{d(a, p) | a, p G C, a = p}. For a vertex a G H(m, q), define
rr (a) = {p G r | d(a, p) = r}, and d(a, C) = min{d(a, p) | p G C}.
We then define the covering radius to be
p = max{d(a, C) | a G r}.
For any r < p, define Cr = {a G r | d(a, C) = r}. Note that Cj is the disjoint union
Uaecrj(a) for i < L^J.
2.1 Automorphism groups
The automorphism group Aut(r) of the Hamming graph is the semi-direct product B x L, where B = and L = Sm (see [3, Theorem 9.2.1]). We refer to B as the base group, and L as the top group, of Aut(r). Let g = (g^ ..., gm) G B, a G L and a be a vertex in H(m, q). Then g and a act on a as follows:
ag = (ag1,..., am") and aCT = (aiff-i ,...,amCT-i).
We define the automorphism group of a code C in H(m, q) to be Aut(C) = Aut(r)C, the setwise stabiliser of C in Aut(r). For a subgroup X < Aut(C) we define two other important actions of X which will be useful to us. First, consider the action of X on the set of entries M, which we will write as XM. In particular XM = ^(X), that is, the image of the homomorphism:
M :	X	-^ Sm
(hi ,...,hm)a i—> a
Note that a here is not necessarily an automorphism of C, that is, a is a permutation of M but may not necessarily fix C setwise, though its pre-image (hi,..., hm)a is an element of Aut(C). We define K to be the kernel of the map m and note that K = X n B. In this paper we are concerned with (X, 2)-neighbour-transitive codes where K = 1.
We also consider the action of the stabiliser Xj < X of the entry i G M, on the alphabet Qj in that entry. We denote this action by XQi = ^j(Xj), and it is the image of the homomorphism:
:	Xj	->	Sq
(hi, ...,hm )a i—> hj
Let C be a code in H(m, q) and let X be a subgroup of Aut(r). Recall that C is (X, s) -neighbour-transitive if each Cj is an X-orbit for i = 0,..., s. Note that this implies X < Aut(C) and C is also (X, r)-neighbour-transitive, for r < s. If s = 1 then C is simply X-neighbour-transitive and if s = p, the covering radius, then C is X-completely transitive.
An almost-simple group is a group G where S < G < Aut(S) for some non-abelian simple group S. The socle of a group G, denoted soc(G), is the product of its minimal normal subgroups. The socle of an almost-simple group G is the non-abelian simple group S such that S < G < Aut(S). Recall, if C is a code and X < Aut(C) such that K = 1,
N. I. Gillespie and D. R. Hawtin: Alphabet-almost-simple 2-neighbour-transitive codes
349
XM is transitive on M and the XQi is almost-simple, then we say C is X-alphabet-almost-simple. We may sometimes omit the group X from any of the above terms, if the meaning is clear from the context.
We say that two codes, C and C', in H(m, q), are equivalent if there exists x G Aut(r) such that Cx = C'. Since elements of Aut(r) preserve distance, equivalence preserves minimum distance.
2.2 Projections
For a subset J = {j1,... , jk} Q M we define the projection of a with respect to J as ■kj (a) = (aj1,..., ajk). For a code C we then define the projection of C with respect to J as nJ(C) = {nJ(a) | a G C}. So nJ maps a vertex or code from H(m, q) into the smaller Hamming graph H(k, q).
Let XJ be the setwise stabiliser of a subset J = {j1,... , jk} Q M. For x = (h1,..., hm)a G XJ, we define the projection of x with respect to J as xJ (x) where
n j (a)XJ (x) = n j (ax).
To be well defined, this requires x g Xj and it follows that
XJ(x) = (hj, .. ., hjk)<r G Aut(H(k, q)),
where a is the element of Sym( J) induced by a. Moreover, we define xj (X) = {xj(x) |
x G Xj}.
3 Structural results
Some results from [8], in which X-alphabet-almost-simple and X-neighbour-transitive codes with S > 3 are characterised, are stated below. This is our starting point when looking at codes that are X-alphabet-almost-simple and (X, 2)-neighbour-transitive with S > 3, since we then have that C is indeed X-neighbour-transitive. The following definitions are needed first. For a subgroup T < Sq define Diagm(T) = {(h,..., h) G B | h G T}.
Definition 3.1. A code C in H(m, q) is diagonally (X, s)-neighbour-transitive if C is (X, s)-neighbour-transitive and X < Diagm(Sq) xi L.
Each part of Proposition 3.2 is proved in the relevant citation of [8]. Recall the definitions of: nJ (C) and xj(X) (see Section 2.2), the socle soc(G) and the kernel K = X n B for the action of X on M, where B = Sm is the base group of Aut(r) (see Section 2.1). Note also that G is a sub-direct subgroup of a direct product "=1 T of isomorphic groups T = T, where i G {1,..., n}, if the projection of G in each coordinate is isomorphic to T.
Proposition 3.2. Suppose C is an X-neighbour-transitive code in H(m, q) with S > 3. Then the following hold:
i) Let J be an X-invariant partition of M and J G J such that nJ(C) is not the complete code. Then nJ(C) is xj(X)-neighbour-transitive [8, Proposition 3.4]. (Note that the assumption that nJ (C) is not the complete code does not appear in [8], but is necessary since the proof assumes that nJ (C )1 is non-empty.)
350
Ars Math. Contemp. 14 (2018) 267-284
ii)	Let J be an X-invariant partition of M and J e J such that nJ(C) is not the complete code. Then nJ(C) has minimum distance at least 2 [8, Corollary 3.7].
iii)	If C is also X-alphabet-almost-simple, then soc(K) is a sub-direct subgroup of nieM soc (xq<) [8, Proposition 5.2].
While the next result is not explicitly stated in [8], it is the basis of the characterisation contained within it.
Proposition 3.3. Let C be an X-alphabet-almost-simple and X-neighbour-transitive code with S > 3. Then there exists an X-invariant partition J of M such that for all J e J the code nJ(C) is equivalent to a diagonally xJ(X)-neighbour-transitive with minimum distance S(nJ(C)) > 2.
Proof. Let T be the non-abelian simple socle of the almost-simple 2-transitive group XQi. By Proposition 3.2-(iii), the group soc(K) is a sub-direct subgroup of ni£M soc (xQi j. Following the discussion after [8, Proposition 5.2], Scott's Lemma [16, p. 328] can be applied to give a partition J of M such that soc(K) = f]JeJ DJ, where each DJ = Diagk(T) acts on -kj(Vr), for all J e J, where k = | J|. Moreover, by [8, Remark 5.5], J is X-invariant. By examining soc(K), it can be shown [8, Section 5] that, up to equivalence, two possibilities occur. Either xJ(X) < Diagk(Sq) x Sk, where k = | J|, for all J e J, or J can be replaced by a more refined X-invariant partition J of M such that Xj(X) < Diagg (Sq) x Sg, where k = | J|, for all J e J.
In either case, it follows from Proposition 3.2-(i) and (ii) that, for all J e J or J respectively, xJ(X) acts transitively on nJ(C) and either nJ(C) is the complete code or it is xJ(X)-neighbour-transitive with minimum distance at least 2. Since xJ(X) is a diagonal subgroup, we deduce that nJ(C) is as in the second case, since no diagonal subgroup acts transitively on the complete code.	□
Proposition 3.4. Let C be an (X, 2)-neighbour-transitive code with S > 3 in H(m, q), and suppose J is an X-invariant partition of M. Then for all J e J, either;
i)	nJ(C) is the complete code, S(nJ(C)) = 1, and xJ(X) is transitive on nJ(C);
ii)	nJ(C) has covering radius 1, S(nJ(C)) = 2 or 3, and is (xJ(X), 1)-neighbour-transitive; or,
iii)	nJ(C) is (xJ(X), 2)-neighbour-transitive.
Proof. Let <5 = nJ(C). The fact that xJ(X) is transitive on C and Ci, if Ci is non-empty, follows from Proposition 3.2-(i). From this we deduce (i) and (ii). In particular, suppose the covering radius of C is at most 1. If the covering radius is 0 then C is the complete code, and if the covering radius is 1 then C is not the complete code and the minimum distance is at most 3 so, by Proposition 3.2-(ii), the minimum distance is at least 2. Therefore, we need only show that when C2 is non-empty xJ (X) is transitive on C2.
Suppose C has covering radius at least 2. Let e C2. Then there exists a, ¡3 e C such that d(^, nJ(a)) = d(v, nJ(¡)) = 2. Let k e H(m, q) with ku = vu for u in J and kv = av otherwise. Similarly, let 7 e H(m, q) with /tu = for u in J and /tv = 3v otherwise. We claim that V, 7 e C2. We show this for v and note that an identical argument holds for 7. First, note that d(a, k) = 2 and S > 3, so v / C. Suppose V e C1. Then
N. I. Gillespie and D. R. Hawtin: Alphabet-almost-simple 2-neighbour-transitive codes
351
there exists a' e C such that d(v, a') = 1. We then have d(v, nJ(a')) < 1. However, this contradicts v e C2. Hence j, ù e C2.
As C is (X, 2)-neighbour-transitive, there exists an x = ha e X mapping l to j. We claim x e XJ. Suppose x e XJ. Then, since J is a system of imprimitivity for the action of X on M, there exists J' e J such that J = J' and J'a = J. Since nJ> (l) = nJ> (a), this implies that nJ(lx) = nJ(ax) e C and hence nJ(lx) = j, which contradicts the fact that vx = j. Thus x e XJ and
vXJ (x) = nJ (l)XJ (x) = nJ (lx) = nJ (j) = j.
□
Proposition 3.5. Let C be an (X, 2)-neighbour-transitive code in H (m, q) with S > 3, and J be an X-invariant partition of M. Then, for all J e J and i e J,
1.	xJ(X)Qi is 2-transitive on Q; and,
2.	for a e C, xJ(X)nj(a) is transitive on J.
Proof. As C is X-neighbour-transitive with S > 3, we have that XQi is 2-transitive, by [7, Proposition 2.7], and XM is transitive, by [7, Proposition 2.5]. One then deduces that XQi is 2-transitive for all i. Now, because J is an X-invariant partition, it follows that Xi = (XJ)i for all i e J. This in turn implies that xJ(X)i = xJ(Xj). It is now straight forward to show that xJ (Xi)Qi = XQi.
Now, since Xa is transitive on M and J is an X-invariant partition of M, it follows that (Xa)J is transitive on J. Thus xJ(Xa) < xJ(X)n(a) is transitive on J.	□
The previous two propositions suggest a study of codes that are (X, 2)-neighbour-transitive, have minimum distance S > 2, and where X acts primitively on M. An answer to the following questions would provide us with the building blocks for (X, 2)-neighbour-transitive codes with S > 3.
Question 3.6. Can we classify all (X, 2)-neighbour-transitive codes with S > 2 such that XM is primitive and XQi is 2-transitive?
Question 3.7. Can we classify all (X, 1)-neighbour-transitive codes with S = 2 or 3 and p =1 such that XM is primitive and XQi is 2-transitive?
Let C be a code and X < Aut(C ). If X acts faithfully on M, that is K = X n B = 1, we say C is X-entry-faithful. If K = 1, XM is transitive on M and XQ is affine (X^ < AGLd(p) for some integer d and prime p) we say C is X-alphabet-affine. Questions 3.6 and 3.7 can be further broken down into X-entry-faithful and non-trivial kernel cases, that is, X-alphabet-affine and X-alphabet-almost-simple (see Section 2.1 for the definition of X-alphabet-almost-simple). By the main result of this paper, the outstanding cases of Question 3.6 are X-alphabet-almost-simple and (X, 2)-neighbour-transitive with S = 2, and X-alphabet-affine and (X, 2)-neighbour-transitive, where XM is primitive and XQi is 2-transitive.
Given Proposition 3.3, a third question is the following.
Question 3.8. Can we construct (X, 2)-neighbour-transitive codes with S > 3 by taking copies of (X, 1)-neighbour-transitive codes with S = 2 or 3 and p =1.
352
Ars Math. Contemp. 14 (2018) 267-284
4 Examples
We begin this section by considering some examples of codes which have properties relating to the results of the previous section. We first introduce the operators Prod and Rep which allow the construction of new codes from old ones. For an arbitrary code C in
H(m, q) we define Prod(C, i) and Rep,(C) in H(mi, q) as
Prod(C, i) = {(ai,..., a,) | a e C},
and
Rep,(C) = {(a,..., a) | a e C}.
The repetition code Rep(m, q) in H(m, q) is the set of all vertices (a,..., a) consisting of a single element a e Q repeated m times.
The next two examples present codes which are both X-alphabet-almost-simple and X-completely transitive, though the second example has minimum distance S = 2.
Example 4.1. Let C = Rep(3, q), where q > 5, and X = Diag3(Sq) x S3, as in [11, Example 3.1]. Now,
Ci = {(a, a, b), (a, b, a), (6, a, a) | a, 6 e Q; a = 6},
and
C2 = {(a, b, c) | a, b, c e Q; a = b = c = a}.
Since Sq acts 3-transitively on Q and S3 acts transitively on M, it follows that X acts transitively on C, C1 and C2. Thus C is (X, 2)-neighbour-transitive and X-completely transitive, since C has covering radius p = 2. Also, XQi = Sq is almost-simple, since q > 5, and XM = S3 is transitive on M. Hence C is X-alphabet-almost-simple and X -completely transitive.
Example 4.2. Let q > 5, i > 2, C = Prod(Rep(2, q), i) and X = (Diag2(Sq))e x U, where Diag2(Sq) is a subgroup of the base group of Aut(H(2, q)) and U = S2 I S, = S2 x S, is a subgroup of the top group of Aut(H(2i, q)). Let J = {J1,..., J,}, with Ji = {2i - 1,2i}, be the partition of M preserved by U. Note that S = 2. Let R C {1,..., i} of size s, and v e H(m, q) be such that J (v) = (a, b), where a = b for all i e R, and a = b for all i e R. Any codeword ft is at least distance s from v, since d(nj.(v),nj.(^)) > 1 for each i e R. Also, there exists some codeword a with nj. (a) = (a, a) whenever nj (v) = (a, b) for i e {1,..., i}, and hence d(a, v) = s. So v e Cs. Any vertex v of H(2i, q) can be expressed in this way, for some R, since nj (v) = (a, b) has either a = b or a = b. Thus, for each s, Cs consists of all such vertices v where |R| = s. It also follows from this that p = i.
Let v e Cs, with R as above. Let x = (hJl,..., hj)a e X where hJi e Diag2(Sq) such that nJi (v)hj* = (1,2), for i e R, and nJi (v= (1,1), for all i e R. Mlore-over, since S, is i-transitive, there exists a e S, < S2 ^ S, mapping {J4l,..., Jis} to {J1,..., Js} (where R = {i1,..., is}), whilst preserving order within each Jj. Then vx = 7 e Cs, where nJi (7) = (1, 2) for all i e {1,..., s} and nJi (7) = (1,1) for all i e {s + 1,..., i}. Since we can map any such v to 7, X is transitive on Cs for each s e {1,..., i}. Hence C is X-completely transitive, and in particular (X, 2)-neighbour-transitive for i > 2. Since XQ = Sq and XM = S2 ? S, is transitive on M, C is X-alphabet-almost-simple.
N. I. Gillespie and D. R. Hawtin: Alphabet-almost-simple 2-neighbour-transitive codes
353
Lemma 4.3. Suppose C is an (X, 2)-neighbour-transitive code in H(m, q), with q > 3, and J is an X-invariant partition of M, such that nJ(C) = Rep(k, q), for all J G J where k = | J|. Then either S = k = 2, or J is a trivial partition.
Proof. Let x = (hi,..., hm)a G X and J G J .By the hypothesis it follows that for all a G Q, there exists a G C such that nJ (a) = (a,..., a). Suppose Ja = J' G J. Then nJ / (ax) = (ahii,..., ahik )a = (b,... ,b) for some b G Q, that is, ahis = ahit for all is,it G J. In particular xJ (xa-1) = (h,... ,h) for some h G Sq, and X < Diagk (Sq) IU, where U is the stabiliser of J in the top group.
Suppose that the partition J is non-trivial, so that k,l > 2. Since C is a subset of Prod(Rep(k, q), I), which has minimum distance k, it follows that S > k > 2.
Suppose S > 3. As C is a subset of Prod(Rep(k, q),i) we can replace C by an equivalent code contained in Prod(Rep(k, q),i) containing a = (1,..., 1) and such that
J = {{1, ...,k}, {k + 1,. .., 2k}, • • • , {m - k + 1, ..., m}} .
Consider,
V = (2,3,1,1,..., 1,1,1,1,..., 1, • • • , 1,..., 1) and v = (2,1,1,1,...,1, 2,1,1,...,1, ••• ,1,...,1).
k entries	k entries	k entries
If k = 2, then we claim v G C2. Any vertex ft G Prod(Rep(2, q),£) D C with d(p, ft) = 1 is of the form 7 = (a, a, 1,..., 1), where a = 2 or 3. However, no such 7 is an element of C, since each is distance 2 from a. If k > 3 then v G C2 since d(a, v) = 2 and there is no closer codeword as nJl (p) G nJl (C)2. In both cases v G C2 since d(a, v) = 2 and no codeword is closer, as nJi(v) G nJi(C)1 for i = 1, 2. Let x = (h1,..., hm)a G X such that px = v. We reach a contradiction here, since h1 = h2 = • • • = hk = h cannot, assuming k > 3, map the set {1,2,3} to either of the sets {1,2} or {1}. In the case k = 2, in at least one block we must map the set {1} to {1, 2}, which is not possible. Hence 2 > S > k > 2.	□
Suppose J is a system of imprimitivity for the action of X on M and C is an X-neighbour-transitive code, with S > 3. The next example shows that it is possible that the projection of C onto each block of J gives the complete code, though this is not the system of imprimitivity of interest to us in Proposition 3.3.
Example 4.4. Let <5 = Prod(C, I) be a code in r = H(m, q), where m = ki and C is an X-neighbour-transitive code in H(k, q) where X n B is transitive on C and S > 3. Let X = ((X n B)e, Diag£(X), Se) preserve the partition
J = {{1, ...,k},..., {m - k + 1, ..., m}} = {J1,...,Ji},
of M, where xj((X n B)e) = X n B and xj(Diag£(X)) = X for all J G J, and S£ acts as pure permutations by permuting the blocks of J whilst preserving the order of entries within a given block. It follows that we preserve two X-invariant partitions. These being J and J', where J' is attained by taking the corresponding entries, by order, from each copy of C to form each block:
J' = {{1, k + 1,...,m - k + 1}, .. ., {i,k + i,..., m}}.
354
Ars Math. Contemp. 14 (2018) 267-284
Given any a = (ai,..., af) e C, a, e C, and ft = ..., fie) e C, ft, e C there exists an x e (X nB)f mapping a to ft since X nB is transitive on C. Hence X is transitive on ¿7. Given any two neighbours v e r1 (a), where v differ from a in the respective blocks J, and Jj, we can map J to J, via some element a e Sf. Then, since Xa. is transitive on ri(aj), there exists an element x e Diagf (X) such that j(vCTX) = j(^). We can then map vCTX to ^ via some element h e (X n B)f, where x j (h) = 1, since each nJt (vCTX) and nJt are elements of C for t = i and X n B is transitive on C. Hence axh maps v to ^ and X is transitive on C1.
When we consider the projection nJ(C) for any J e J' we are left with the complete code. To see this, consider that for (a1,..., af) e C, a, e C, we may choose an arbitrary element of C as a, for each i. Since xQ* is 2-transitive on Q,, each element appears in the first entry for some codeword. Thus, as nJ((a1,..., af)) when J = {1, k + 1,..., m -k +1} is the first entry of each a,, we have that nJ(C1) is the complete code.
5 Alphabet-almost-simple (X, 2)-neighbour-transitive codes
Before we prove the final results we define the codes used in this section, which first requires the following definition.
Definition 5.1. Define the composition of a vertex a e H(m, q) to be the set
Q(a) =	. . . , (aq,Pq)},
where p, is the number of entries of a which take the value a, e Q. For a e H(m, q) define the set
Num(a) = {(p1, S1),..., (pj, sj)}, where (p,, s,) means that s, distinct elements of Q appear precisely p, times in a. Definition 5.2. We define the following codes:
1.	Inj(m, q), where m < q, is the set of all vertices a e H(m, q) such that Num(a) = {(1, m)};
2.	for m odd, W([m/2], 2) is the set of vertices in a e H(m, 2) such that Num(a) = {(m + 1)/2,1), (m - 1)/2,1)}; and,
3.	All(pq, q), with pq = m, is the set of all vertices a e H(m, q) such that Num(a) =
{(p, q)}.
More information on these codes is available in [9, Definition 2]. The following lemma is [9, Lemma 4].
Lemma 5.3. Let a be a vertex in H(m, q). Then Num(a) is preserved by Diagm(Sq) x L.
The last result, in combination with the classification of diagonally neighbour-transitive codes [9, Theorem 4.3], allows us to prove the next result.
Proposition 5.4. Let C be a diagonally (X, 2)-neighbour-transitive code in H(m, q). Then one of the following holds:
1.	q = 2 and C = {(a,..., a)};
2.	m = 3 or q = 2, and C = Rep(m, q);
N. I. Gillespie and D. R. Hawtin: Alphabet-almost-simple 2-neighbour-transitive codes	355
3.	C = Inj(3,q);
4.	m is odd and C = W([m/2], 2); or,
5.	q = 2 or q = m = 3, and there exists some p such that m = pq and C is a subset of All(pq, q).
Proof. From [9, Theorem 4.3], we have that a diagonally neighbour-transitive code C is one of: {(a,..., a)} for some a G Q, Rep(m, q), Inj(m, q) with m < q, W([m/2], 2) with m odd, or there exists a p such that m = pq and C is a subset of All(pq, q). Here we consider m > 2, since if m =1 then C2 is empty, so C is not (X, 2)-neighbour-transitive. Also to prove some C is (X, 2)-neighbour-transitive, we need only find some X < Aut(C) such that X < Diagm(Sq) x L and X is transitive on C2, since C is already X-neighbour-transitive, for some X, by [9, Theorem 4.3].
First, if C = Inj(2, q) then C2 is empty. Thus, C is not (X, 2)-neighbour-transitive. Table 1 lists the remaining cases which are not 2-neighbour-transitive. The second and third columns give a pair p, v G C2 such that Num(p) = Num(v). Hence, by Lemma 5.3, X is not transitive on C2. It can be deduced from Num(p), Num(v) that p, v G C2, since this makes it clear that we must change p, v in at least two entries to get a vertex in C. Note that we let a = (1, 2,3,..., q) G H(q, q) and in the second last and last rows we assume a G C and (a,..., a) G C, respectively, and observe for the last row p = (1,1,1,4,5,..., q), > = (1,1, 3,4,5,..., q) are in r2(a).
C Conditions	P e C2 Num(p)	v e C2 Num(v)
{(a,...,a)} q > 3	(b, b, a,... , a) {(m - 2,1), (2,1)}	(b, c, a,... , a) {(m - 2,1), (1, 2)}
Rep(m, q) m > q > 3	(2, 2,1,...,1) {(m - 2,1), (2,1)}	(2,3,1,...,1) {(m - 2,1), (1, 2)}
Inj(m, q) m > 4	(1,1,1, 4, 5,... , m) {(3,1), (1, m - 3)}	(1,1, 3, 3, 5, 6,... , m) {(2, 2), (1, m - 4)}
C All(q, q) q > 4	(1,1,1, 4, 5,. . . , q) {(3,1),(1,q - 3)}	(1,1,3, 3,5, 6,... , q) {(2,2),(1,q - 4)}
C All(pq,q) q > p > 2	(p, a,... , a) {(p - 1, 2), (p, q - 3), (p + 2,1)}	(£, ;>, a,... , a) {(p - 2,1), (p, q - 2), (p + 2,1)}
Table 1: Diagonally neighbour-transitive codes C which are not diagonally 2-neighbour-transitive, and elements of C2 which illustrate this. Note: p = (1,1,1,4,5,..., q), > =
(1,1,3,4, 5,..., q) and a = (1,2,3,..., q).
Now we prove the result for the cases which are 2-neighbour-transitive. Suppose C = {(a,..., a)} for some a G Q. Let q = 2 and Q = {0,1}. Then L = Sm = Aut(C). Without loss of generality, let a = 0 so that C2 is the set of weight two vertices. Since L is transitive on the sets of weight 2 and weight 1 vertices, it follows C is diagonally (X, 2)-neighbour-transitive. Let C = Rep(m, q). It follows from Example 4.1 that Rep(3, q) is (Diag3(Sq) x S3,2)-neighbour-transitive. If q = 2 then Aut(C) = Diagm(S2) x Sm and C is completely transitive [11, Example 3.1]. Consider C = Inj(m, q) with 3 = m < q and q > 4. If v G C2 then v1 = v2 = v3, since otherwise v G C or Ci. Since Diagm(Sq) < Aut(C), we are transitive on C2. Suppose C = W([m/2], 2) and m is odd. Then by [9, Corollary 3.4] C is Diag(S2) x Sm-completely transitive. Finally, suppose C is a subset
356
Ars Math. Contemp. 14 (2018) 267-284
of All(pq, q) for some p such that m = pq. Let p > 2, q = 2 and C = All(2p, 2). Then C2 is the set of all weight p ± 2 vertices, which Diag2(S2) x Sm < Aut(C) is transitive on. Let p =1, q = 3 and C = All(3, 3). Then C2 = Rep(3, q) and is Aut(C)-completely transitive by Example 4.1.	□
With our classification of diagonally (X, 2)-neighbour-transitive codes from the previous result, Propositions 3.3 and 3.4 mean we are now in a position to prove the main theorem.
Proof of Theorem 1.1. Suppose C is an X-alphabet-almost-simple and (X, 2)-neighbour-transitive code with S > 3 such that X n B = 1. By Proposition 3.3, there exists an X-invariant partition J = { Ji,..., J^}, for some i, for the action of X on M. Moreover, j (C) has minimum distance at least 2 and is diagonallyxj (X)-neighbour-transitive. By Proposition 3.4, either j (C) has covering radius p < 1, or j(C) is also (xj(X), 2)-neighbour-transitive. Note p = 0, that is, j (C) is not the complete code, since j (C) has minimum distance at least 2.
Suppose j (C) has covering radius p > 2. Since XQi is almost-simple, it follows that q > 5. By Proposition 5.4, the only diagonally 2-neighbour-transitive code with q > 5 and S > 2 is Rep(3, q) for q > 5 (note that S = 1 for Inj(3, q)). Then Lemma 4.3 implies J is a trivial partition. Since J = k = 3 > 1, it follows that i = 1, k = m, and C = Rep(3, q).
Suppose j (C) has covering radius p =1. Now, by [9, Thm. 4 and Cor. 2], the only diagonally neighbour-transitive code with S > 2 and p =1 is Rep(2, q). If l = 1 then we have S = 2, a contradiction. Suppose l > 2. Then Lemma 4.3 implies S = 2, a contradiction.	□
References
[1]	J. Borges and J. Rifa, On the nonexistence of completely transitive codes, IEEE Trans. Inform. Theory 46 (2000), 279-280, doi:10.1109/18.817528.
[2]	J. Borges, J. Rifa and V. A. Zinoviev, Families of completely transitive codes and distance transitive graphs, Discrete Math. 324 (2014), 68-71, doi:10.1016/j.disc.2014.02.008.
[3]	A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, volume 18 of Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer-Verlag, Berlin, 1989, doi: 10.1007/978-3-642-74341-2.
[4]	P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, Philips Research Reports: Supplements, N. V. Philips' Gloeilampenfabrieken, Eindhoven, 1973.
[5]	J. D. Dixon and B. Mortimer, Permutation Groups, volume 163 of Graduate Texts in Mathematics, Springer, New York, 1996, doi:10.1007/978-1-4612-0731-3.
[6]	N. Gill, N. I. Gillespie and J. Semeraro, Conway groupoids and completely transitive codes, Combinatorica (2017), doi:10.1007/s00493-016-3433-7.
[7]	N. I. Gillespie, M. Giudici, D. R. Hawtin and C. E. Praeger, Entry-faithful 2-neighbour transitive codes, Des. Codes Cryptogr. 79 (2016), 549-564, doi:10.1007/s10623-015-0069-3.
[8]	N. I. Gillespie and C. E. Praeger, Characterisation of a family of neighbour transitive codes, 2014, arXiv:1405.5427 [math.CO].
[9]	N. I. Gillespie and C. E. Praeger, Diagonally neighbour transitive codes and frequency permutation arrays, J. Algebraic Combin. 39 (2014), 733-747, doi:10.1007/s10801-013-0465-6.
N. I. Gillespie and D. R. Hawtin: Alphabet-almost-simple 2-neighbour-transitive codes
357
[10]	M. Giudici, Completely transitive codes in Hamming graphs, Master's thesis, The University of Western Australia, Perth, Australia, 1998.
[11]	M. Giudici and C. E. Praeger, Completely transitive codes in Hamming graphs, European J. Combin. 20 (1999), 647-662, doi:10.1006/eujc.1999.0313.
[12]	J. M. Goethals and S. L. Snover, Nearly perfect binary codes, Discrete Math. 3 (1972), 65-88, doi:10.1016/0012-365x(72)90025-8.
[13]	Y. Hong, On the nonexistence of unknown perfect 6- and 8-codes in Hamming schemes H(n, q) with q arbitrary, Osaka J. Math. 21 (1984), 687-700, http://projecteuclid. org/euclid.ojm/12 00 777 44 8.
[14]	S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Sa§oglu and R. Urbanke, Reed-Muller codes achieve capacity on erasure channels, in: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (Cambridge, Massachusetts, 2016), ACM, New York, 2016 pp. 658-669, doi:10.1145/2897518.2897584.
[15]	K. Lindstrom, All nearly perfect codes are known, Inf. Control 35 (1977), 40-47, doi:10.1016/ s0019-9958(77)90519-8.
[16]	L. L. Scott, Representations in characteristic p, in: The Santa Cruz Conference on Finite Groups (University of California, Santa Cruz, California, 1979), American Mathematical Society, Providence, Rhode Island, volume 37 of Proceedings of Symposia in Pure Mathematics, 1980 pp. 319-331.
[17]	N. V. Semakov, V. A. Zinoviev and G. V. Zaitsev, Uniformly packed codes, Probl. Peredachi Inf. 7 (1971), 38-50, http://mi.mathnet.ru/eng/ppi1621.
[18]	C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J. 27 (1948), 379423, doi:10.1002/j.1538-7305.1948.tb01338.x.
[19]	C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J. 27 (1948), 623656, doi:10.1002/j.1538-7305.1948.tb00917.x.
[20]	P. Sole, Completely regular codes and completely transitive codes, Discrete Math. 81 (1990), 193-201, doi:10.1016/0012-365x(90)90152-8.
[21]	A. Tietavainen, On the nonexistence of perfect codes over finite fields, SIAM J. Appl. Math. 24 (1973), 88-96, doi:10.1137/0124010.
[22]	V. A. Zinoviev and V. K. Leontiev, The nonexistence of perfect codes over Galois fields, Probl. Control Inf. Theory 2 (1973), 123-132, http://real-j.mtak.hu/7 981/.