betaFeedback

WorksMathematics

CRCs in four-dimensional lattice graphs

Abstract

We obtain series of new completely regular codes in Cayley graphs of the groups ZqnZ_q^n with the Lee metric. Combined with binary linear programming methods, the constructions lead to enumeration of all completely regular codes in such graphs for the groups Zq4Z_q^4, q≤7q\leq 7 up to parameter matrices.

Introduction

The undirected Cayley graph Cay⁡(G,S)\operatorname{Cay}(G,S) of an abelian group GG with a generating set SS such that 0∉S0 \notin S, −S=S-S=S, is the graph with vertex set GG whose edges are the pairs {x,x+a}\{x,x+a\}, x∈Gx \in G, a∈Sa \in S. The graphs considered in this paper are Cayley graphs of abelian groups. By ei=(0,…,0,1,0,…,0)e^i=(0,\ldots,0,1,0,\ldots,0) we denote the word with the one in the iith position and all other coordinates equal to zero. Below we define the classes of graphs used in the paper.

  • H(n,q)=Cay⁡(Zqn,{αei:1≤i≤n, α∈Zq∖{0}})H(n,q)=\operatorname{Cay}(\mathbb{Z}_q^n,\{\alpha e^i:1 \le i \le n,\ \alpha\in\mathbb{Z}_q\setminus\{0\}\}) is the Hamming graph;

  • Gqn=Cay⁡(Zqn,{±ei:1≤i≤n})G_q^n=\operatorname{Cay}(\mathbb{Z}_q^n,\{\pm e^i:1 \le i \le n\}) and Gn=Cay⁡(Zn,{±ei:1≤i≤n})G^n=\operatorname{Cay}(\mathbb{Z}^n,\{\pm e^i:1 \le i \le n\}) are the lattices with the Lee metric (l1l_1-metric);

  • Dqn=Cay⁡(Zqn,{0,1,−1}n∖{0n})D_q^n=\operatorname{Cay}(\mathbb{Z}_q^n,\{0,1,-1\}^n\setminus\{0^n\}) and Dn=Cay⁡(Zn,{0,1,−1}n∖{0n})D^n=\operatorname{Cay}(\mathbb{Z}^n,\{0,1,-1\}^n\setminus\{0^n\}) are the lattices with the l∞l_\infty-metric.

For q≥3q \ge3 the graph GqnG_q^n is regular of degree 2n2n, and the graph DqnD_q^n is regular of degree 3n−13^n-1; G4nG^n_4 is isomorphic to H(2n,2)H(2n,2) (the cycle G4G_4 is the square H(2,2)H(2,2)), G3n=H(n,3)G^n_3=H(n,3), G2n=H(n,2)G^n_2=H(n,2). For even qq the graph GqnG_q^n is bipartite: the parts are formed by the words with even and with odd Lee weight.

The notion of a completely regular code arose in the 1970s in connection with the solution of the problem of the existence of perfect codes with arbitrary covering radius in the Hamming metric over field alphabets [19, 20, 17]. Perfect codes in the Lee metric have been studied since the seminal paper of Golomb and Welch [10]. One of the classical problems for completely regular codes is the classification of their parameters in a given family of graphs. In particular, classifications of the parameters of all completely regular codes (CRCs) in the Hamming graphs H(n,2)H(n,2) were obtained [14 Section 7] for n≤13n \le13 (in G4nG_4^n, n≤6n \le6 respectively) and in the Hamming graphs H(n,3)H(n,3) for n≤6n \le6.

For the Lee metric graphs, the problem of classifying CRCs has been considered in several papers. In the graph of the infinite square lattice G2G^2, the case of covering radius 1 was studied in [4], and the case of covering radius 2 by Puzynina in [13]. For covering radius 1, several restrictions on the parameter matrix were obtained in [7]. A complete classification of CRCs of arbitrary covering radius in G2G^2 was obtained in [3]. Thus, the first open cases are the lattices G3G^3 and G4G^4.

In [12], CRCs in GnG^n whose first two diagonal elements of the parameter matrix are equal to zero were studied. In particular, all such codes in the graph G3G^3 were enumerated. We also mention an important paper [2], in which, for CRCs in the graphs GqnG_q^n and GnG^n, the monotonicity of the superdiagonal and subdiagonal elements of the parameter matrix was established, as well as the upper bound 2n2n on the covering radius.

The main definitions concerning completely regular codes and the basic constructions are given in § 2. In Section 3 we propose new series of CRCs with covering radius 2 in the graphs G6r3l−12G_{6r}^{\frac{3l-1}{2}} (two constructions) and Gq2lG_q^{2l} for any l,r≥1l,r \ge1, and in the graph Gq2m+1G_q^{2m+1} for even q≥4q \ge4 if there exists a perfect code in GqmG_q^m. Mostly, the constructions are based on the composite nature of the alphabet size 6 and combine binary or ternary perfect codes with special symbol functions or with classical methods such as the Solov’eva construction [16]. Moreover, the new codes are not obtained from binary and ternary codes of small length in the Hamming metric by an inverse homomorphism, which follows from the enumeration of the parameters of these CRCs [14 Section 7]. In the final Section 4 we list the parameter matrices of all CRCs in GqnG_q^n, n≤4n \le4, q≤7q \le7, obtained using binary linear programming; each matrix is confirmed by a construction of a CRC.

Basic definitions and results

Perfect colorings and codes in graphs

Perfect colorings and CRCs A partition (C0,…,Ck−1)(C_0,\ldots,C_{k-1}) of the vertex set of a graph is called a perfect coloring with parameter matrix M=(Mij)i,j=0k−1M=(M_{ij})_{i,j=0}^{k-1} if every vertex of CiC_i has exactly MijM_{ij} neighbors in CjC_j. For a code (a nonempty set of vertices) CC we put CiC_i as the set of vertices at distance ii from CC in the graph. The number ρ=max⁡{i:Ci≠∅}\rho=\max\{i:C_i\ne\varnothing\} is the covering radius of the code CC. A code CC is called completely regular (briefly, a CRC) if the partition (C0,…,Cρ)(C_0,\ldots,C_\rho) is a perfect coloring. The parameter matrix of a CRC is tridiagonal (i.e. Mij=0M_{ij}=0 for ∣i−j∣≥2|i-j|\ge2) and if the graph is δ\delta-regular, it is recovered from the intersection array

[b0,…,bρ−1;c1,…,cρ],bi=Mi,i+1,ci=Mi,i−1,Mii=δ−bi−ci.[b_0,\ldots,b_{\rho-1};c_1,\ldots,c_\rho],\qquad b_i=M_{i,i+1},\quad c_i=M_{i,i-1},\quad M_{ii}=\delta-b_i-c_i.

The intersection array is mostly used for the compact notation of CRCs in the tables of Section 4 and in the rest of the text CRCs are represented by their parameter matrices MM. A classic example of CRC is a one-vertex code in a distance-regular graph and its intersection array coincides with the intersection array of the graph. For a one-vertex code in the Hamming graph H(n,q)H(n,q) we have ci=ic_i=i, 1≤i≤n1\le i\le n, bi=(n−i)(q−1)b_i=(n-i)(q-1), 0≤i≤n−10\le i\le n-1.

A perfect code (one-error-correcting perfect code) in a δ\delta-regular graph is a CRC with intersection array [δ;1][\delta;1], i.e. with the matrix

(0δ1δ−1);\begin{pmatrix}0 & \delta\\ 1 & \delta-1\end{pmatrix};

thus, for n=1n=1 the singleton in H(1,q)=KqH(1,q)=K_q from the example above is a perfect code with the matrix

(0q−11q−2).\begin{pmatrix}0 & q-1 \\ 1 & q-2\end{pmatrix}.

Such codes exist in GnG^n for all n≥1n\ge1 [10].

More generally, for 1≤k≤δ1\le k\le\delta a kk-fold perfect code in a δ\delta-regular graph is a CRC with parameter matrix

(k−1δ+1−kkδ−k),\begin{pmatrix}k-1 & \delta+1-k \\ k & \delta-k\end{pmatrix},

i.e. a code meeting every ball of radius 1 in exactly kk vertices; a 1-fold perfect code is a perfect code.

Linear codes. A code C⊆ZqnC\subseteq\mathbb{Z}_q^n is called linear if it is a subgroup of the group Zqn\mathbb{Z}_q^n. Every linear code is given by a parity-check matrix, i.e. a matrix HH over Zq\mathbb{Z}_q with columns h1,…,hnh_1,\ldots,h_n such that C={x∈Zqn:HxT=0}C=\{x\in\mathbb{Z}_q^n:Hx^{\mathsf{T}}=0\}. For Theorems 3–4, in the case when all input codes are linear, we briefly indicate the description of the resulting code in terms of the parity-check matrices of the input codes. We note that there are also nonlinear perfect codes in Lee metric [8], [11 Remarks 2, 4].

Coverings

A surjective map ff from the vertices of a graph Γ′\Gamma' onto the vertices of a graph Γ\Gamma is called a λ\lambda-fold covering if for every vertex v′v' of Γ′\Gamma' the map ff sends the neighbors of v′v' to neighbors of f(v′)f(v') and every neighbor of f(v′)f(v') has exactly λ\lambda preimages among the neighbors of v′v' (for λ=1\lambda=1 this is the usual notion of a covering). For Cayley graphs, the homomorphisms described in Proposition 1 are λ\lambda-fold coverings.

Proposition 1. [5 Lemma 4.1] Let ϕ:G′→G\phi:G'\to G be a surjective homomorphism of a group G′G' to a group GG, and let S′⊆G′S'\subseteq G' and S⊆GS\subseteq G be such that 0∉S,S′0\notin S,S', −S=S-S=S, −S′=S′-S'=S', ϕ(S′)=S\phi(S')=S and every element of SS has exactly λ\lambda, λ≥1\lambda\ge1, preimages in S′S'. If CC is a CRC in Cay⁡(G,S)\operatorname{Cay}(G,S) with parameter matrix MM, then ϕ−1(C)\phi^{-1}(C) is a CRC in Cay⁡(G′,S′)\operatorname{Cay}(G',S') with parameter matrix λM\lambda M.

A homomorphism Zqn→Zqm\mathbb{Z}_q^n\to\mathbb{Z}_q^m has the form x↦xTx\mapsto xT for an n×mn\times m matrix TT; it is surjective, for example, if some minor of order mm of the matrix TT is coprime to qq. Let ϕq:Zqrn→Zqn\phi_q:\mathbb{Z}_{q^r}^n\to\mathbb{Z}_q^n (or Zn→Zqn\mathbb{Z}^n\to\mathbb{Z}_q^n) be the coordinatewise reduction modulo qq:

ϕq(x1,…,xn)=(x1 mod q,…,xn mod q).\phi_q(x_1,\ldots,x_n)=(x_1\bmod q,\ldots,x_n\bmod q).

Consider several basic constructions for CRCs arising from group homomorphisms (see also [12]).

K1. Let rr be any integer, r≥2r \ge2 and CC be a CRC in G2n=H(n,2)G_{2}^{n}=H(n,2) with parameter matrix MM. Then ϕ2−1(C)\phi_{2}^{-1}(C) is a CRC in G2rnG_{2r}^{n} (respectively, in GnG^{n}) with matrix 2M2M (here λ=2\lambda=2, since ei=−eie^{i}=-e^{i} in Z2n\mathbb{Z}_{2}^{n}).

K2. Let rr be any integer, r≥1r \ge1, q≥3q \ge3 and CC be a CRC in GqnG_{q}^{n} with parameter matrix MM. Then ϕq−1(C)\phi_{q}^{-1}(C) is a CRC in GqrnG_{qr}^{n} (respectively, in GnG^{n}) with matrix MM (here λ=1\lambda=1).

K3. Let qq be odd, N=m(q−1)2N=\frac{m(q-1)}{2}, and let the rows of the N×mN \times m matrix TT be all the words αej\alpha e^{j}, 1≤j≤m1 \le j \le m, 1≤α≤q−121 \le\alpha\le\frac{q-1}{2}. Then ϕ(x)=xT\phi(x)=xT maps {±ei:1≤i≤N}\{\pm e^{i}:1 \le i \le N\} bijectively onto {αej:1≤j≤m, α∈Zq∖{0}}\{\alpha e^{j}:1 \le j \le m,\ \alpha\in\mathbb{Z}_{q}\setminus\{0\}\}. Consequently, if CC is a CRC in H(m,q)H(m,q) with matrix MM, then ϕ−1(C)\phi^{-1}(C) is a CRC in GqNG_{q}^{N} with matrix MM.

K4. Let q≥3q \ge3, N=3m−12N=\frac{3^{m}-1}{2}, and let the rows of the N×mN \times m matrix TT be all the words of length mm over {0,1,−1}\{0,1,-1\} whose first nonzero symbol is 11. Then ϕ(x)=xT\phi(x)=xT maps {±ei:1≤i≤N}\{\pm e^{i}:1 \le i \le N\} bijectively onto {0,1,−1}m∖{0m}\{0,1,-1\}^{m}\setminus\{0^{m}\}. Consequently, if CC is a CRC in DqmD_{q}^{m} with matrix MM, then ϕ−1(C)\phi^{-1}(C) is a CRC in GqNG_{q}^{N} with matrix MM.

Basic CRCs, addition and multiplication

We regard the following codes as the basic, simplest sources of CRCs.

  • A one-vertex code in a distance-regular graph, for example in the cycle GqG_{q} or in a Hamming graph;

  • Perfect codes in the Hamming metric and in the Lee metric. In particular, a binary perfect code of length nn in H(n,2)H(n,2) exists if and only if n=2m−1n=2^{m}-1, m≥1m \ge1 (necessity follows from the Hamming bound, sufficiency from the Hamming codes). If (2n+1)∣q(2n+1)\mid q, then the code {x∈Zqn:∑i=1nixi≡0(mod2n+1)}\{x\in\mathbb{Z}_{q}^{n}:\sum_{i=1}^{n}ix_{i}\equiv0\pmod{2n+1}\} is perfect in GqnG_{q}^{n} [1].

  • Extended binary perfect codes. Appending a parity check to each codeword gives an extended perfect code of length n=2mn=2^{m} and cardinality 2n−m−12^{n-m-1} with minimum distance 44 (for m≥2m \ge2). For m≥2m \ge2 it is known [14 Proposition 1.38] that this code is a CRC in H(n,2)=G2nH(n,2)=G_{2}^{n} with covering radius ρ=2\rho=2 and parameter matrix

M=(0n010n−10n0)M=\begin{pmatrix}0&n&0\\1&0&n-1\\0&n&0\end{pmatrix}

For example, for m=2m=2 the extended Hamming code {0000,1111}\{0000,1111\} is a CRC in H(4,2)=G24H(4,2)=G_{2}^{4} with array [4,3;1,4][4,3;1,4], and for m=3m=3 the extended perfect code CC of length 88 is a CRC in H(8,2)=G28H(8,2)=G_{2}^{8} with array [8,7;1,8][8,7;1,8]. By Construction K1, for r≥2r \ge2 the preimage ϕ2−1(C)\phi_{2}^{-1}(C) is a CRC in G2rnG_{2r}^{n} (and in GnG^{n}) with matrix 2M2M, i.e. with array [2n,2n−2;2,2n][2n,2n-2;2,2n]; for example, for n=4n=4 we obtain a CRC in G64G_{6}^{4} with array [8,6;2,8][8,6;2,8].

Note that recently, in [18], a criterion for the extension of CRC code to be CRC was obtained in terms of the parameter matrices in a wide family of bipartite graphs, including the Hamming graphs over binary alphabets and the Lee graphs over alphabets of even size.

A criterion for CRCs with covering radius 2

  • For even q≥4q \ge4 each part of the graph GqnG_q^n is a CRC with matrix

(02n2n0)\begin{pmatrix} 0 & 2n \\ 2n & 0 \end{pmatrix}

(the even-weight code);

  • Even-weight subcodes of perfect codes. Let PP be a perfect code in a bipartite δ\delta-regular graph with parts V0,V1V_0,V_1 that meets both parts. Then (see e.g., [14 Proposition 1.32]) P∩V0P \cap V_0 is a CRC with parameter matrix

(0δ0010δ−100δ−10100δ0).\begin{pmatrix} 0 & \delta& 0 & 0 \\ 1 & 0 & \delta-1 & 0 \\ 0 & \delta-1 & 0 & 1 \\ 0 & 0 & \delta& 0 \end{pmatrix}.
  • kk-fold perfect codes are CRCs with parameter matrix

(k−1δ−k+1kδ−k).\begin{pmatrix} k-1 & \delta-k+1 \\ k & \delta-k \end{pmatrix}.

In particular, if PP is a perfect code in a Cayley graph Cay⁡(G,S)\operatorname{Cay}(G,S), ∣S∣=δ|S|=\delta, that is a subgroup of the group GG, and the group GG is abelian, then the union of any kk cosets of PP, 1≤k≤δ1 \le k \le\delta, is a kk-fold perfect code. As indicated at the beginning of this section, if (2n+1)∣q(2n+1)\mid q, then there exists a perfect code of the graph GqnG_q^n that is a subgroup of Zqn\mathbb{Z}_q^n, and therefore for every kk, 1≤k≤2n1 \le k \le2n, there exists a kk-fold perfect code in GqnG_q^n.

The following two operations, see [9] provide new CRCs from existing ones. Let q≥3q \ge3 and CC be a CRC in GqnG_q^n with parameter matrix MM.

  • Addition (+2k+2k): C×ZqkC \times\mathbb{Z}_q^k is a CRC in Gqn+kG_q^{n+k} with matrix M+2kIM+2kI, where II is the identity matrix.

  • Multiplication (∗k*k): the preimage of CC under the homomorphism

ϕ:Zqkn→Zqn,\phi:\mathbb{Z}_q^{kn}\to\mathbb{Z}_q^n,
ϕ(x1,…,xkn)=(∑t=0k−1x1+tn,∑t=0k−1x2+tn,…,∑t=0k−1xn+tn),\phi(x_1,\ldots,x_{kn})=\left(\sum_{t=0}^{k-1}x_{1+tn},\sum_{t=0}^{k-1}x_{2+tn},\ldots,\sum_{t=0}^{k-1}x_{n+tn}\right),

is a CRC in GqknG_q^{kn} with matrix kMkM.

In the tables of Section 4, the notation Gqn+2kG_q^n+2k means a CRC in Gqn+kG_q^{n+k} obtained by addition from a CRC in GqnG_q^n, and the notation Gqn∗kG_q^n*k means a CRC obtained by multiplication by kk from a CRC in GqnG_q^n; the operations can be combined, for example Gqn∗k+2lG_q^n*k+2l. In all cases GqnG_q^n is the graph in which the original code is constructed (the construction of the original code is indicated in the table for GqnG_q^n; its intersection array does not change under addition, and is multiplied by kk under multiplication).

A criterion for CRCs with covering radius 2

All the new codes of Section 3 are obtained using the following simple criterion.

Proposition 2. Let Γ\Gamma be a δ\delta-regular graph, and let T=C∪C~T=C\cup\widetilde{C}, where CC and C~\widetilde{C} are nonempty, disjoint, and there are no edges between CC and C~\widetilde{C}. Suppose that every vertex of TT is adjacent to exactly AA, A<δA<\delta, vertices of TT, and every vertex of T‾\overline{T} is adjacent to exactly CC, C≥1C\geq1, vertices of CC and to exactly BB vertices of C~\widetilde{C}. Then the following holds.

  1. We have C1=TC_1=T, C2=C~C_2=\widetilde{C}, and CC is a CRC with parameter matrix

M=(Aδ−A0Cδ−B−CB0δ−AA).M=\begin{pmatrix} A & \delta-A & 0\\ C & \delta-B-C & B\\ 0 & \delta-A & A \end{pmatrix}.
  1. The code TT is a CRC in Γ\Gamma with parameter matrix

M=(Aδ−AB+Cδ−B−C).M=\begin{pmatrix} A & \delta-A\\ B+C & \delta-B-C \end{pmatrix}.

Proof. 1. Since there are no edges between CC and C~\widetilde{C}, all AA neighbors of a vertex of CC in TT are in CC, and the remaining δ−A≥1\delta-A\geq1 are in T‾\overline{T}; the same holds for C~\widetilde{C}. In particular T‾≠∅\overline{T}\ne\varnothing. Since C≥1C\geq1, every vertex of T‾\overline{T} is adjacent to CC, so T‾=C1\overline{T}=C_1. The vertices of C~\widetilde{C} are not adjacent to CC and have neighbors in T‾=C1\overline{T}=C_1, hence C~=C2\widetilde{C}=C_2. The rows of the matrix are obtained by direct counting.

  1. Follows directly from the parameters established in the previous item. □

New constructions of CRCs over Z6\mathbb{Z}_6 in the Lee metric

Each construction of Sections 3.1–3.3 gives a code in G6nG_6^n, to which K2 is then applied; therefore the resulting CRCs also exist in G6rnG_{6r}^n for all r≥1r\geq1 and in G6nG_6^n. The construction of Section 3.4 works for any even q≥4q\geq4.

A concatenation construction from ternary punctured perfect codes

The general form of this construction resembles the Solov’eva concatenation construction for perfect and extended perfect codes [16]. We say that a triple (Q0,Q1,Q2)(Q^0,Q^1,Q^2) of subsets of Z6m\mathbb{Z}_6^m is admissible if Q0,Q1,Q2Q^0,Q^1,Q^2 are nonempty and pairwise disjoint, their union SS is an independent set of the graph G6mG_6^m, and every vertex outside SS is adjacent to exactly one vertex of each of Q0,Q1,Q2Q^0,Q^1,Q^2. This is equivalent to SS being a CRC with matrix

(02m32m−3),\begin{pmatrix} 0 & 2m\\ 3 & 2m-3 \end{pmatrix},

each QiQ^i being a CRC with matrix

(02m012m−3202m0),\begin{pmatrix} 0 & 2m & 0\\ 1 & 2m-3 & 2\\ 0 & 2m & 0 \end{pmatrix},

and Q2i=S∖QiQ^i_2=S\setminus Q^i. The same definition is used for subsets of Z3m\mathbb{Z}_3^m and the graph G3m=H(m,3)G_3^m=H(m,3).

Lemma 1. For l≥2l\geq2 and m=3l−32m=\frac{3^l-3}{2} there exists an admissible triple in Z6m\mathbb{Z}_6^m.

Proof. Let PP be the ternary perfect (for example, Hamming code) in H(m+1,3)=G3m+1H(m+1,3)=G_{3}^{m+1}. Put Q′i={y∈Z3m:(y,i)∈P}Q^{\prime i}=\{y\in\mathbb{Z}_{3}^{m}:(y,i)\in P\}, α∈Z3\alpha\in\mathbb{Z}_{3}, and S′=⋃i∈Z3Q′iS^{\prime}=\bigcup_{i\in\mathbb{Z}_{3}}Q^{\prime i}. Using code terms, S′S^{\prime} is the punctured Hamming code, and the sets Q′iQ^{\prime i} are shortened codes. Thus (Q′0,Q′1,Q′2)(Q^{\prime0},Q^{\prime1},Q^{\prime2}) is an admissible triple in G3mG_{3}^{m}, because each shortened perfect code Q′iQ^{\prime i}, i∈Z3i\in\mathbb{Z}_{3} is a CRC with required parameter matrix [15].

The triple (Q0,Q1,Q2)=(ϕ3−1(Q′0),ϕ3−1(Q′1),ϕ3−1(Q′2))(Q^{0},Q^{1},Q^{2})=(\phi_{3}^{-1}(Q^{\prime0}),\phi_{3}^{-1}(Q^{\prime1}),\phi_{3}^{-1}(Q^{\prime2})) under ϕ3:Z6m→Z3m\phi_{3}:\mathbb{Z}_{6}^{m}\to\mathbb{Z}_{3}^{m} is an admissible triple in G6mG_{6}^{m}, since ϕ3\phi_{3} maps the neighbors of each vertex bijectively onto the neighbors of its image. □

Theorem 1. Let (Q0,Q1,Q2)(Q^{0},Q^{1},Q^{2}) be an admissible triple in Z6m\mathbb{Z}_{6}^{m}, Ri={2i,2i+1}⊂Z6R^{i}=\{2i,2i+1\}\subset\mathbb{Z}_{6}, i=0,1,2i=0,1,2. Then the code

C=⋃i∈Z3Qi×RiC=\bigcup_{i\in\mathbb{Z}_{3}}Q^{i}\times R^{i}

is a CRC in G6m+1G_{6}^{m+1} with parameter matrix

(12m+1012m102m+11).\begin{pmatrix} 1 & 2m+1 & 0 \\ 1 & 2m & 1 \\ 0 & 2m+1 & 1 \end{pmatrix}.

Proof. Let R~i={2i+3,2i+4}⊂Z6\widetilde{R}^{i}=\{2i+3,2i+4\}\subset\mathbb{Z}_{6}. In the cycle G6G_{6} each of the families {Ri:i∈Z3}\{R^{i}:i\in\mathbb{Z}_{3}\} and {R~i:i∈Z3}\{\widetilde{R}^{i}:i\in\mathbb{Z}_{3}\} partitions Z6\mathbb{Z}_{6}, and for each ii the sets RiR^{i}, R~i\widetilde{R}^{i} and Ni=Z6∖(Ri∪R~i)N^{i}=\mathbb{Z}_{6}\setminus(R^{i}\cup\widetilde{R}^{i}) have the following properties: a vertex of RiR^{i} (of R~i\widetilde{R}^{i}) has one neighbor in RiR^{i} (in R~i\widetilde{R}^{i}) and none in R~i\widetilde{R}^{i} (in RiR^{i}); a vertex of NiN^{i} has one neighbor in RiR^{i} and one in R~i\widetilde{R}^{i}, see Figure 1 a, b. In other words, for any i∈Z3i\in\mathbb{Z}_{3} RiR^{i}, NiN^{i}, R~i\widetilde{R}^{i} is the distance partition w.r.t. the CRC RiR^{i} in G6G_{6} with the parameter matrix

Two partitions of the graph $G_{6}$

Figure 1. Two partitions of the graph G6G_{6} (a) R0∪R1∪R2R^{0}\cup R^{1}\cup R^{2}, Ri={2i,2i+1}R^{i}=\{2i,2i+1\} and (b) R~0∪R~1∪R~2\widetilde{R}^{0}\cup\widetilde{R}^{1}\cup\widetilde{R}^{2}, R~i=Ri+3\widetilde{R}^{i}=R^{i}+3; (c) the distance partition (R0,N0,R~0)(R^{0},N^{0},\widetilde{R}^{0}) of G6G_{6} with respect to the CRC R0R^{0} with parameter matrix (110101011)\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix}.

(110101011),\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix},

see Figure 1 c.

We now check the conditions of Proposition 2 for T=C∪C~T=C\cup\widetilde{C}, δ=2m+2\delta=2m+2, where C~=⋃i∈Z3Qi×R~i\widetilde{C}=\bigcup_{i\in\mathbb{Z}_{3}}Q^{i}\times\widetilde{R}^{i}. Since the sets QiQ^{i} are pairwise disjoint, for x∈Qix\in Q^{i} we have (x,γ)∈T(x,\gamma)\in T if and only if γ∈Ri∪R~i\gamma\in R^{i}\cup\widetilde{R}^{i}; in particular C∩C~=∅C\cap\widetilde{C}=\varnothing.

Consider a vertex (x,β)∈C(x,\beta)\in C, x∈Qix\in Q^{i}, β∈Ri\beta\in R^{i}. Its neighbors of the form (x′,β)(x^{\prime},\beta) are not in TT, since x′∉Sx^{\prime}\notin S by the independence of the set SS. By the remark at the beginning of the proof, among the neighbors (x,β±1)(x,\beta\pm1) exactly one lies in Qi×Ri⊆CQ^{i}\times R^{i}\subseteq C and the other is in Qi×NiQ^{i}\times N^{i}, so not in TT. Hence (x,β)(x,\beta) has exactly one neighbor in TT, and it lies in CC. The same holds for C~\widetilde{C}; in particular, there are no edges between CC and C~\widetilde{C}, and A=1A=1.

Let (x,β)∉T(x,\beta)\notin T and x∈Qi⊂Sx\in Q^{i}\subset S for some i∈Z3i\in\mathbb{Z}_{3}. Then β\beta belongs to Ni=Z6∖(Ri∪R~i)N^{i}=\mathbb{Z}_{6}\setminus(R^{i}\cup\widetilde{R}^{i}). The neighbors of the vertex (x,β)(x,\beta) of the form (x′,β)(x^{\prime},\beta) do not lie in TT (again by the independence of SS), and of the neighbors (x,β±1)(x,\beta\pm1) one lies in Qi×Ri⊂CQ^{i}\times R^{i}\subset C and one in Qi×R~i⊂C~Q^{i}\times\widetilde{R}^{i}\subset\widetilde{C} by the remark at the beginning of the proof. Let (x,β)∉T(x,\beta)\notin T and x∉Sx\notin S. Then the neighbors (x,β±1)(x,\beta\pm1) are not in TT because xx is not in S=⋃i∈Z3QiS=\bigcup_{i\in\mathbb{Z}_{3}}Q^{i}. Moreover, by definition of admissible triple (Q0,Q1,Q2)(Q^{0},Q^{1},Q^{2}), a vertex xx, x∉Sx\notin S, has exactly one neighbor xj∈Qjx^{j}\in Q^{j} for each j∈Z3j\in\mathbb{Z}_{3}, these are all its neighbors in SS, and the vertex (xj,β)(x^{j},\beta) is in Qj×Rj⊂CQ^{j}\times R^{j}\subset C (in Qj×R~j⊂C~Q^{j}\times\widetilde{R}^{j}\subset\widetilde{C}) if and only if β∈Rj\beta\in R^{j} (β∈R~j\beta\in\widetilde{R}^{j}), which holds for exactly one jj. In both cases C=B=1C=B=1, and the statement follows from Proposition 2. □

Corollary 1. For all l,r≥1l,r\ge1, CRCs with parameter matrix (13l−2013l−3103l−21)\begin{pmatrix}1&3^{l}-2&0\\1&3^{l}-3&1\\0&3^{l}-2&1\end{pmatrix} exist in the graphs G63l−12rG_{6^{\frac{3^{l}-1}{2r}}} and G63l−12G_{6^{\frac{3^{l}-1}{2}}}.

Proof. For l=1l=1 the required code in G6G_{6} is the edge R0R^{0}, see Figure 1c. For l≥2l\ge2 we apply Theorem 1 to the admissible triple from Lemma 1: m+1=3l−12m+1=\frac{3^{l}-1}{2}, 2m+1=3l−22m+1=3^{l}-2. We use K2K_{2} to obtain CRCs over Z6r\mathbb{Z}_{6^{r}} and Z\mathbb{Z}. □

CRCs in the l∞l_{\infty} metric

By K4K_{4}, every CRC in D6lD_{6}^{l} with l∞l_{\infty} metric provides a CRC with the same parameter matrix in G63l−12G_{6^{\frac{3^{l}-1}{2}}}. Consider the code T={0,1,3,4}l⊆Z6lT=\{0,1,3,4\}^{l}\subseteq\mathbb{Z}_{6}^{l}. We call the symbols 0, 1 lower and 3, 4 upper. Let CC (C~\widetilde{C}) be the set of words of TT with an even (odd) number of lower symbols. A neighbor x+εx+\varepsilon, ε∈{0,±1}l∖{0l}\varepsilon\in\{0,\pm1\}^{l}\setminus\{0^{l}\}, of a vertex xx in D6lD_{6}^{l} is obtained by changing each symbol by 0 or ±1\pm1.

Theorem 2. The code CC is a CRC in D6lD_{6}^{l} with parameter matrix

(2l−13l−2l02l−13l−1−2l2l−103l−2l2l−1)\begin{pmatrix} 2^{l}-1 & 3^{l}-2^{l} & 0 \\ 2^{l-1} & 3^{l}-1-2^{l} & 2^{l-1} \\ 0 & 3^{l}-2^{l} & 2^{l}-1 \end{pmatrix}

Proof. Let xx be in TT. A symbol xk∈{0,1,3,4}x_k\in\{0,1,3,4\} can be changed by 00 or ±1\pm1 while staying in {0,1,3,4}\{0,1,3,4\} in exactly two ways: by leaving it unchanged or by replacing it with its “partner” in this set (that is, 0↔10\leftrightarrow1 or 3↔43\leftrightarrow4); in this case a lower symbol remains lower and an upper symbol remains upper. Therefore xx has exactly 2l−12^{l}-1 neighbors in TT, and all of them lie in the same one of the codes CC, C~\widetilde{C} as xx; in particular, there are no edges between CC and C~\widetilde{C}.

Let x∉Tx\notin T, i.e. w≥1w\geq1 symbols of xx are equal to 22 or 55. The symbol 22 can be replaced by 11 (lower) or 33 (upper), the symbol 55 by 00 (lower) or 44 (upper), and each of the lower and upper symbols in two ways preserving its type. Since w≥1w\geq1, all 2l2^{l} resulting words are different from xx, i.e. they are neighbors of xx in TT, and, since the type of a symbol equal to 22 or 55 can be chosen freely, exactly half of them have an even number of lower symbols. Thus C=B=2l−1C=B=2^{l-1}, A=2l−1<3l−1A=2^{l}-1<3^{l}-1, and the statement follows from Proposition 2. □

Corollary 2. For any l≥1l\geq1 and r≥1r\geq1 there exists a CRC in G6r3l−12G_{6r}^{\frac{3^{l}-1}{2}} and in G23l−12G_{2}^{\frac{3^{l}-1}{2}} with the parameter matrix of Theorem 2.

Proof. By Theorem 2 and construction K4 (with q=6q = 6, m=lm = l), the preimage of CC is a CRC in G63l−12G_{6}^{\frac{3^{l}-1}{2}} with the same parameter matrix; then construction K2 from § 2.2 gives the CRCs in G6r3l−12G_{6r}^{\frac{3^{l}-1}{2}} and G3l−12G^{\frac{3^{l}-1}{2}}.

Remark 1. The example of the code from Theorem 2 for l=2l = 2 in Figure 2 was proposed by S.V. Avgustinovich.

The adjacency in the graph $D_{6}^{2}$ and the CRC in $D_{6}^{2}$

Figure 2. (a) The adjacency in the graph D62D_{6}^{2} (b) The CRC C={0,1}2∪{3,4}2C=\{0,1\}^{2}\cup\{3,4\}^{2} in D62D_{6}^{2} with parameter matrix (350242053)\begin{pmatrix}3&5&0\\2&4&2\\0&5&3\end{pmatrix}.

Open problem (S.V. Avgustinovich). Obtain a classification of CRCs in the graphs DqnD_q^n (Cayley graphs of the group Zqn\mathbb{Z}_q^n with the l∞l_\infty metric), n≥2n \ge2.

CRCs from binary perfect codes

Let n=2ln = 2^l, l≥1l \ge1, and let PP be a binary perfect code of length n−1n - 1.

By K1, the code B=ϕ2−1(P)⊂Z6n−1\mathcal{B} = \phi_2^{-1}(P) \subset\mathbb{Z}_6^{n-1} is a CRC in G6n−1G_6^{n-1} with matrix

(02n−222n−4)\begin{pmatrix} 0 & 2n-2 \\ 2 & 2n-4 \end{pmatrix}

From the parameter matrix of the perfect code PP in H(n−1,2)H(n-1,2) we have the following obvious fact:

(H) if z∉Bz \notin\mathcal{B}, then the neighbors of zz in B\mathcal{B} are exactly z+ejz+e^j and z−ejz-e^j for a unique jj.

We write the vertices of the graph G6nG_6^n in the form x=(z,α)x = (z,\alpha), z∈Z6n−1z \in\mathbb{Z}_6^{n-1}, α∈Z6\alpha\in\mathbb{Z}_6, and consider the homomorphism ψ\psi from Z6n\mathbb{Z}_6^n onto Z3\mathbb{Z}_3:

ψ(z,α)=α−∑i=1n−1zi(mod3).\psi(z,\alpha) = \alpha- \sum_{i=1}^{n-1} z_i \pmod3.

Note that the homomorphism ψ\psi maps the graph G6nG_6^n onto a multigraph which is the complete graph K3K_3 with each edge of multiplicity nn.

Put

T=ker⁡ψ=⋃z∈Z6n−1z×s(z),s(z)={∑zi,∑zi+3}⊂Z6,T = \ker\psi= \bigcup_{z\in\mathbb{Z}_6^{n-1}} z \times s(z), \qquad s(z) = \left\{\sum z_i,\sum z_i+3\right\} \subset\mathbb{Z}_6,
C=⋃z∈Bz×s(z),C~=⋃z∉Bz×s(z).\mathcal{C} = \bigcup_{z\in\mathcal{B}} z \times s(z), \qquad\widetilde{\mathcal{C}} = \bigcup_{z\notin\mathcal{B}} z \times s(z).

Theorem 3. For each l≥1l \ge1 the code C\mathcal{C} is a CRC in G62lG_6^{2^l} with parameter matrix

(02l+1012l2l−102l+10)\begin{pmatrix} 0 & 2^{l+1} & 0 \\ 1 & 2^l & 2^l-1 \\ 0 & 2^{l+1} & 0 \end{pmatrix}

Moreover, for all l≥1l \ge1, r≥1r \ge1 CRCs with the same parameter matrix exist in G6r2lG_{6r}^{2^l} and in G2lG^{2^l}.

Proof. Since ψ(T)\psi(T) is a single vertex of the multigraph K3K_3 (with each edge of multiplicity nn), which has no loops, and since ψ\psi is a homomorphism from G6nG_6^n onto this multigraph, no pair of vertices of T=C∪C~T = \mathcal{C} \cup\widetilde{\mathcal{C}} is adjacent, i.e. A=0A = 0; in particular, there are no edges between C\mathcal{C} and C~\widetilde{\mathcal{C}}. Let x=(z,α)∉Tx=(z,\alpha)\notin T and β=ψ(x)∈Z3∖{0}={1,−1}\beta=\psi(x)\in\mathbb{Z}_3\setminus\{0\}=\{1,-1\}. Denote

yn=(z,α−β),yk=x+βek=(z+βek,α), k<n.y^n=(z,\alpha-\beta),\qquad y^k=x+\beta e^k=(z+\beta e^k,\alpha),\ k<n.

Here ek=(0,…,0,1,0,…,0)e^k=(0,\ldots,0,1,0,\ldots,0) is the word of length n−1=2l−1n-1=2^l-1 with the one in the kkth position.

For each 1≤k≤n1\leq k\leq n, exactly one of the neighbors x±ekx\pm e^k lies in TT, namely yky^k, since ψ(yn)=β−β=0\psi(y^n)=\beta-\beta=0 and ψ(yk)=β−β=0\psi(y^k)=\beta-\beta=0 for k<nk<n, while the other neighbors have ψ(z,α+β)=2β≠0\psi(z,\alpha+\beta)=2\beta\neq0 and ψ(z−βek,α)=2β≠0\psi(z-\beta e^k,\alpha)=2\beta\neq0. Thus xx has exactly nn neighbors y1,…,yny^1,\ldots,y^n in TT and exactly 2n−n=n2n-n=n neighbors in T‾\overline{T}. By the definition of CC we have

yn∈C⟺z∈B,yk∈C⟺z+βek∈B for all k<n.y^n\in C\Longleftrightarrow z\in\mathcal{B},\qquad y^k\in C\Longleftrightarrow z+\beta e^k\in\mathcal{B}\text{ for all }k<n.

Recall that the code B\mathcal{B} is an independent set in Gqn−1G_q^{n-1}, since the parameter matrix of this CRC has 0 in the upper left corner. We have the following cases.

Case A. Let z∈Bz\in\mathcal{B}. Then yn∈Cy^n\in C, and by the independence of B\mathcal{B}, z+βek∉Bz+\beta e^k\notin\mathcal{B} for all k<nk<n. The vertex xx has exactly n−1n-1 neighbors y1,…,yn−1y^1,\ldots,y^{n-1} in C~\widetilde{C} and exactly one, namely yny^n, in CC.

Case B. Let z∉Bz\notin\mathcal{B}. Then yn∈C~y^n\in\widetilde{C}, and by (H) the neighbors of zz in B\mathcal{B} are exactly z+ejz+e^j and z−ejz-e^j for a unique j<nj<n; hence z+βek∈B⟺k=jz+\beta e^k\in\mathcal{B}\Longleftrightarrow k=j. Therefore yj∈Cy^j\in C and yk∈C~y^k\in\widetilde{C} for k≠jk\neq j. In both cases xx has exactly C=1C=1 neighbors in CC and B=n−1B=n-1 in C~\widetilde{C}. The conditions of Proposition 2 are satisfied with δ=2n\delta=2n, A=0A=0, C=1≥1C=1\geq1, B=n−1B=n-1, and the parameter matrix of the code CC is

M=(Aδ−A0Cδ−C−BB0δ−AA)=(02n012n−(n−1)−1n−102n0)=(02n01nn−102n0).M=\begin{pmatrix} A & \delta-A & 0\\ C & \delta-C-B & B\\ 0 & \delta-A & A \end{pmatrix} = \begin{pmatrix} 0 & 2n & 0\\ 1 & 2n-(n-1)-1 & n-1\\ 0 & 2n & 0 \end{pmatrix} = \begin{pmatrix} 0 & 2n & 0\\ 1 & n & n-1\\ 0 & 2n & 0 \end{pmatrix}.

We use K2 to obtain a CRC in G6rnG_{6r}^n and GqnG_q^n. □

Parity-check matrix. Let PP be the binary Hamming code with an l×(n−1)l\times(n-1) parity-check matrix HH. The code B={z∈Z6n−1:HzT≡0(mod2)}\mathcal{B}=\{z\in\mathbb{Z}_6^{n-1}:Hz^{\mathsf{T}}\equiv0\pmod2\} has the parity-check matrix 3H3H over Z6\mathbb{Z}_6, and T=ker⁡ψ={(z,α):2(α−∑zi)=0}T=\ker\psi=\{(z,\alpha):2(\alpha-\sum z_i)=0\}. Since C=(B×Z6)∩TC=(\mathcal{B}\times\mathbb{Z}_6)\cap T, the code CC is linear with parity-check matrix

(3H04⋅12) over Z6,\begin{pmatrix} 3H & 0\\ 4\cdot\mathbf{1} & 2 \end{pmatrix} \text{ over }\mathbb{Z}_6,

where 1\mathbf{1} is the all-ones row.

``Lengthening'' of a doubled perfect code

Let q≥4q\geq4 be even and let PP be a perfect code in GqmG_q^m. We write the vertices of Gq2m+1G_q^{2m+1} in the form (u,v,α)(u,v,\alpha), u,v∈Zqmu,v\in\mathbb{Z}_q^m, α∈Zq\alpha\in\mathbb{Z}_q, and put x=u+vx=u+v; for x∈Zqmx\in\mathbb{Z}_q^m let t(x)={∑i=1mxi+2j:0≤j<q/2}⊂Zqt(x)=\left\{\sum_{i=1}^{m}x_i+2j:0\le j<q/2\right\}\subset\mathbb{Z}_q. Consider the codes

C=⋃y∈Zqm, x∈Py×(x−y)×t(x),C~=⋃y∈Zqm, x∉Py×(x−y)×t(x),T=C∪C~.(1)\mathcal{C}=\bigcup_{\substack{y\in\mathbb{Z}_q^m,\ x\in P}}y\times(x-y)\times t(x),\qquad\widetilde{\mathcal{C}}=\bigcup_{\substack{y\in\mathbb{Z}_q^m,\ x\notin P}}y\times(x-y)\times t(x),\qquad T=\mathcal{C}\cup\widetilde{\mathcal{C}}. \tag*{(1)}

Thus T={(u,v,α):α+∑i=1m(ui+vi) is even}T=\left\{(u,v,\alpha):\alpha+\sum_{i=1}^{m}(u_i+v_i)\text{ is even}\right\} is one of the parts of the bipartite graph Gq2m+1G_q^{2m+1}, T‾\overline{T} is the other part, and C\mathcal{C} and C~\widetilde{\mathcal{C}} differ by the condition x=u+v∈Px=u+v\in P or x∉Px\notin P.

Theorem 4. If for even q≥4q\ge4 there exists a perfect code PP in GqmG_q^m, then the code C\mathcal{C} in (1) is a CRC in Gq2m+1G_q^{2m+1} with parameter matrix

(04m+20204m04m+20)\begin{pmatrix} 0 & 4m+2 & 0\\ 2 & 0 & 4m\\ 0 & 4m+2 & 0 \end{pmatrix}

Proof. The part TT is independent, so A=0A=0 and there are no edges between C\mathcal{C} and C~\widetilde{\mathcal{C}}. Let z=(u,v,α)z=(u,v,\alpha) be a vertex in the part T‾\overline{T}, x=u+vx=u+v. All neighbors of zz lie in the part TT; the neighbors (u±ei,v,α)(u\pm e^i,v,\alpha) and (u,v±ei,α)(u,v\pm e^i,\alpha), i=1,…,mi=1,\ldots,m, correspond to the word x±eix\pm e^i, and the neighbors (u,v,α±1)(u,v,\alpha\pm1) correspond to the word xx. If x∈Px\in P, then x±ei∉Px\pm e^i\notin P by the perfectness of the code PP, and the neighbors of zz in C\mathcal{C} are exactly (u,v,α±1)(u,v,\alpha\pm1). If x∉Px\notin P, then xx has a unique neighbor x+βei∈Px+\beta e^i\in P (where β∈{1,−1}\beta\in\{1,-1\}), and the neighbors of zz in C\mathcal{C} are exactly (u+βei,v,α)(u+\beta e^i,v,\alpha) and (u,v+βei,α)(u,v+\beta e^i,\alpha). In both cases C=2C=2, B=4mB=4m, and the statement follows from Proposition 2. □\square

Parity-check matrix. If PP is a linear code with parity-check matrix HH over Zq\mathbb{Z}_q, then C={(u,v,α):H(u+v)T=0, α+∑i=1m(ui+vi) is even}\mathcal{C}=\left\{(u,v,\alpha):H(u+v)^{\mathsf T}=0,\ \alpha+\sum_{i=1}^{m}(u_i+v_i)\text{ is even}\right\} is linear with parity-check matrix

(HH0q21q21q2)\begin{pmatrix} H & H & 0\\ \frac{q}{2}\mathbf{1} & \frac{q}{2}\mathbf{1} & \frac{q}{2} \end{pmatrix}

Remark 2. If (2m+1)∣q(2m+1)\mid q, then a perfect code in GqmG_q^m exists (§ 2.3). According to Horak, AlBdaiwi and Milazzo [1], perfect codes in GqmG_q^m exist for all mm such that the product of all prime divisors of 2m+12m+1 divides qq. In particular, such a code exists in G46G_4^6 (for example, the preimage under ϕ3\phi_3 of the ternary Hamming code of length 4), so Theorem 4 gives a CRC in G49G_4^9.

CRCs in the lattice graphs GqnG_q^n, n≤4n\le4, q=5,6,7q=5,6,7

The enumeration of the parameter matrices of all CRCs in the graphs GqnG_q^n for q≤7q\le7, n≤4n\le4 was carried out by solving an integer linear programming problem. The program was written in Python, and the problems were solved with the HiGHS solver.

Let C\mathcal{C} be a CRC with covering radius ρ\rho in a graph with vertex set VV and adjacency matrix LL. Its characteristic matrix is the ∣V∣×(ρ+1)|V|\times(\rho+1) binary matrix XX with Xu,i=1X_{u,i}=1 if u∈Ciu \in C_i and Xu,i=0X_{u,i}=0 otherwise. It is easy to see [14 Proposition 1.4] that a binary matrix XX is the characteristic matrix of a CRC with a tridiagonal parameter matrix MM (with nonzero sub- and superdiagonal entries) if and only if

LX=XMand∑i=0ρXu,i=1for every vertex u.LX = XM \qquad\text{and}\qquad\sum_{i=0}^{\rho} X_{u,i}=1 \quad\text{for every vertex }u.

Thus a CRC with parameter matrix MM exists if and only if this system has a binary solution.

Note that the case of the graph G74G^4_7 with 74=24017^4=2401 vertices is already borderline, since the number of variables is already very large. However, the graph has small degree and fairly large diameter, which has a positive effect on the speed of the solver. For instance, already in the Hamming graph H(4,6)H(4,6) with 64=12966^4=1296 vertices and degree 20, the solver cannot cope with the problem of the existence of CRCs.

Before solving the problem for a candidate matrix MM with covering radius ρ\rho, we checked that MM satisfies the following necessary conditions.

  1. Monotonicity of the off-diagonal entries. As proved in [2], the parameter matrix of every CRC in the lattice graphs GqnG^n_q and GsnG^n_s satisfies Mi,i+1≥Mi+1,i+2M_{i,i+1}\ge M_{i+1,i+2} for 0≤i≤ρ−20\le i\le\rho-2 and Mi,i−1≤Mi+1,iM_{i,i-1}\le M_{i+1,i} for 1≤i≤ρ−11\le i\le\rho-1, i.e. b0≥b1≥…≥bρ−1b_0\ge b_1\ge\ldots\ge b_{\rho-1} and c1≤c2≤…≤cρc_1\le c_2\le\ldots\le c_\rho.

  1. Integrality of the cell sizes. The sizes of the cells CiC_i of the distance partition of a graph of order qnq^n are determined by the relations [14 Lemma 7.2]

Mi,i+1∣Ci∣=Mi+1,i∣Ci+1∣(0≤i≤ρ−1),∑i=0ρ∣Ci∣=qn,M_{i,i+1}|C_i|=M_{i+1,i}|C_{i+1}| \quad(0\le i\le\rho-1), \qquad\sum_{i=0}^{\rho}|C_i|=q^n,

and they must be integers.

  1. Integrality of eigenvalues. By Lloyd theorem [14 Lemma 7.4], every eigenvalue of the parameter matrix of a CRC is an eigenvalue of the graph. The eigenvalues of the cycle GqG_q are 2cos⁡(2πk/q)2\cos(2\pi k/q), k=0,…,q−1k=0,\ldots,q-1, and the eigenvalues of GqnG^n_q are all sums of nn eigenvalues of GqG_q. For example, the eigenvalues of G6G_6 are 2,1,−1,−22,1,-1,-2, and for n≥2n\ge2 the eigenvalues of G6nG^n_6 are all integers from −2n-2n to 2n2n; hence for q=6q=6 all eigenvalues of MM must be integers.

These conditions significantly reduce the set of possible parameter matrices. For G64G^4_6, up to passing to the opposite code, there are 496 tridiagonal 3×33\times3 matrices with row sum 8 and positive off-diagonal entries fulfilling the monotonicity condition, 76 of them have integer cells, and only 41 fulfill all three conditions.

In all tables of this section, CRCs are given by their intersection arrays [b0,…,bρ−1;c1,…,cρ][b_0,\ldots,b_{\rho-1};c_1,\ldots,c_\rho] (see § 2), which uniquely determine the parameter matrices. If CC is a CRC with array [b0,…,bρ−1;c1,…,cρ][b_0,\ldots,b_{\rho-1};c_1,\ldots,c_\rho], then the opposite code CρC_\rho is a CRC with array [cρ,…,c1;bρ−1,…,b0][c_\rho,\ldots,c_1;b_{\rho-1},\ldots,b_0], of each such pair of arrays, only one is listed. Notation in the column “construction”: pc is a perfect code; k pc is a kk-fold perfect code obtained as the union of kk cosets of a linear perfect code (in a δ\delta-regular graph it is a CRC with array [δ+1−k;k][\delta+1-k;k]; 1 pc is pc itself); sing is a one-vertex code; even is the even-weight code; ext pc is an extended perfect code; even pc is the even-weight subcode of a perfect code; rep is the ternary repetition code of length 3, a well-known CRC in H(3,3)H(3,3) with intersection array [6,2;1,6][6,2;1,6], see Figure 3.

Hamming graph H(3, 3) and ternary code C

Figure 3. Hamming graph H(3,3)H(3,3) and ternary code C={000,111,222}\mathcal{C}=\{000,111,222\}, which is CRC with parameter matrix (060132060)\begin{pmatrix}0&6&0\\1&3&2\\0&6&0\end{pmatrix}.

A graph written after a code name, as in “sing H(2,2)H(2,2)”, means that the code is constructed in that graph and lifted to GqnG_q^n by one of the coverings K1–K3 of § 2.2; if no graph is given, the code is constructed in GqnG_q^n itself. The entries Gqm+2kG_q^m+2k and Gqm∗kG_q^m*k denote addition and multiplication (§ 2.3) applied to a CRC from the table for GqmG_q^m. For codes obtained by the constructions of Section 3, the corresponding theorem or corollary is given together with its parameters. New constructions are marked with an asterisk.

Note that all CRCs found in GqnG_q^n for q=5,6,7q=5,6,7 and n≥3n\geq3 have small covering radii, namely at most nn. For every n≥1n\geq1, a CRC with covering radius ⌊q/2⌋\lfloor q/2\rfloor exists in GqnG_q^n: take a one-vertex code in GqG_q and add n−1n-1 inessential coordinates (addition +2(n−1)+2(n-1)). By [2], the covering radius of a CRC in GqnG_q^n is at most 2n2n, and this bound is attained, for example, when qq is divisible by 4.

Open problem. Is it true that for qq not divisible by 4 and n≥⌊q/2⌋+1n\geq\lfloor q/2\rfloor+1, the covering radius of every CRC in GqnG_q^n is at most nn?

GqnG_q^n, q≤4q\leq4

Since G2n=H(n,2)G_2^n=H(n,2), G3n=H(n,3)G_3^n=H(n,3) and G4n≅H(2n,2)G_4^n\cong H(2n,2), these cases reduce to Hamming graphs; see the survey [14 Section 7].

G6nG_6^n, n≤4n \le4.

G6G_6

ρ=1\rho= 1arrayconstruction
[2, 1]pc G6G_6
[2, 2]even

Table 1.

ρ=2\rho= 2arrayconstruction
[1, 1, 1, 1]Corollary 1, l=1l = 1

Table 2.

ρ=3\rho= 3arrayconstruction
[2, 1, 1, 1, 1, 2]sing G6G_6

Table 3.

G62G_6^2

ρ=1\rho= 1arrayconstruction
[2, 1]G6+2G_6 + 2
[2, 2]G6+2G_6 + 2
[4, 2]G6∗2G_6 * 2
[4, 4]even

Table 4.

ρ=2\rho= 2arrayconstruction
[1, 1, 1, 1]G6+2G_6 + 2
[4, 2, 1, 2]sing H(2,3)H(2, 3)
[2, 2, 2, 2]G6∗2G_6 * 2
[4, 1, 1, 4]Theorem 3, n=2n = 2
[4, 2, 2, 4]sing H(2,2)H(2, 2)

Table 5.

ρ=3\rho= 3arrayconstruction
[2, 1, 1, 1, 1, 2]G6+2G_6 + 2
[4, 2, 2, 2, 2, 4]G6∗2G_6 * 2

Table 6.

G63G_6^3. New constructions are marked with an asterisk.

ρ=1\rho= 1arrayconstruction
[2, 1]G6+4G_6 + 4
[2, 2]G6+4G_6 + 4
[4, 2]G6∗2+2G_6 * 2 + 2
[4, 4]G62+2G_6^2 + 2
[6, 2]pc H(3,2)H(3, 2)
[6, 3]G6∗3G_6 * 3
[6, 6]even

Table 7.

ρ=2\rho= 2arrayconstruction
[1, 1, 1, 1]G6+4G_6 + 4
[4, 2, 1, 2]G62+2G_6^2 + 2
[2, 2, 2, 2]G6∗2+2G_6 * 2 + 2
[3, 3, 3, 3]G6∗3G_6 * 3
[4, 1, 1, 4]G62+2G_6^2 + 2
[4, 2, 2, 4]G62+2G_6^2 + 2
[6, 1, 2, 6]rep H(3,3)H(3, 3)
[6, 2, 4, 6]Theorem 4, m=1∗m = 1*

Table 8.

ρ=3\rho= 3arrayconstruction
[2, 1, 1, 1, 1, 2]G6+4G_6 + 4
[3, 2, 1, 2, 4, 6]sing H(3,3)H(3, 3)
[4, 2, 2, 2, 2, 4]G6∗2+2G_6 * 2 + 2
[6, 3, 3, 3, 3, 6]G6∗3G_6 * 3
[6, 4, 2, 2, 4, 6]sing H(3,2)H(3, 2)

Table 9.

G64G_6^4. New constructions are marked with an asterisk.

arrayconstructionarrayconstruction
[2;1][2;1]G6+6G_6+6[1,1;1,1][1,1;1,1]G6+6G_6+6
[2;2][2;2]G6+6G_6+6[2,1;2,4][2,1;2,4]G62+4G_6^2+4
[4;2][4;2]G6∗2+4G_6*2+4[2,2;2,2][2,2;2,2]G6∗2+4G_6*2+4
[4;4][4;4]G62+4G_6^2+4[3,3;3,3][3,3;3,3]G6∗3+2G_6*3+2
[5;4][5;4]4 pc H(4,3)4\ \mathrm{pc}\ H(4,3)[4,1;1,4][4,1;1,4]G62+4G_6^2+4
[6;2][6;2]G63+2G_6^3+2[4,2;2,4][4,2;2,4]G62+4G_6^2+4
[6;3][6;3]3 pc H(4,3)3\ \mathrm{pc}\ H(4,3)[4,2;4,8][4,2;4,8]G62∗2G_6^2*2
[6;6][6;6]G63+2G_6^3+2[4,4;4,4][4,4;4,4]G6∗4G_6*4
[7;2][7;2]2 pc H(4,3)2\ \mathrm{pc}\ H(4,3)[5,2;2,5][5,2;2,5]Corollary 2, l=2∗l=2*
[8;1][8;1]pc H(4,3)\mathrm{pc}\ H(4,3)[6,1;2,6][6,1;2,6]G63+2G_6^3+2
[8;4][8;4]G6∗4G_6*4[6,2;4,6][6,2;4,6]G63+2G_6^3+2 (Theorem 4, m=1)∗m=1)^*
[8;8][8;8]even[7,1;1,7][7,1;1,7]Corollary 1, l=2∗l=2^*
[8,1;3,8][8,1;3,8]Theorem 3, n=4∗n=4^*
[8,2;2,8][8,2;2,8]G62∗2G_6^2*2
[8,2;6,8][8,2;6,8]ext pc H(4,2)H(4,2)
[8,4;4,8][8,4;4,8]G62∗2G_6^2*2

Table 10.

arrayconstructionarrayconstruction
[2,1,1;1,1,2][2,1,1;1,1,2]G6+6G_6+6[4,3,2,1;2,4,6,8][4,3,2,1;2,4,6,8]sing H(4,3)H(4,3)
[3,2,1;2,4,6][3,2,1;2,4,6]G63+2G_6^3+2[8,6,4,2;2,4,6,8][8,6,4,2;2,4,6,8]sing H(4,2)H(4,2)
[4,2,2;2,2,4][4,2,2;2,2,4]G6∗2+4G_6*2+4
[6,3,3;3,3,6][6,3,3;3,3,6]G6∗3+2G_6*3+2
[6,4,2;2,4,6][6,4,2;2,4,6]G63+2G_6^3+2
[8,4,4;4,4,8][8,4,4;4,4,8]G6∗4G_6*4
[8,7,1;1,7,8][8,7,1;1,7,8]even pc G64G_6^4

Table 11.

G5nG_5^n, n≤4n \le4.

arrayconstruction
[1,1;1,2][1,1;1,2]sing

Table 12.

arrayconstruction
[4;1][4;1]pc G52G_5^2
[3;2][3;2]2 pc G522\ \mathrm{pc}\ G_5^2

Table 13.

arrayconstruction
[1,1;1,2][1,1;1,2]G5+2G_5+2
[2,2;2,4][2,2;2,4]G5∗2G_5*2

Table 14.

G53G_5^3

ρ=1\rho=1
arrayconstruction
[4;1][4;1]G52+2G_5^2+2
[3;2][3;2]G52+2G_5^2+2

Table 15.

ρ=2\rho=2
arrayconstruction
[1,1;1,2][1,1;1,2]G5+4G_5+4
[2,2;2,4][2,2;2,4]G5∗2+2G_5*2+2
[3,3;3,6][3,3;3,6]G5∗3G_5*3

Table 16.

G54G_5^4

ρ=1\rho=1
arrayconstruction
[4;1][4;1]G52+4G_5^2+4
[3;2][3;2]G52+4G_5^2+4
[6;4][6;4]G52∗2G_5^2*2
[8;2][8;2]G52∗2G_5^2*2

Table 17.

ρ=2\rho=2
arrayconstruction
[1,1;1,2][1,1;1,2]G5+6G_5+6
[2,1;4,8][2,1;4,8]K3 for a singleton in H(2,5)H(2,5)
[2,2;2,4][2,2;2,4]G5∗2+4G_5*2+4
[3,3;3,6][3,3;3,6]G5∗3+2G_5*3+2
[4,2;3,6][4,2;3,6]K3 for a cycle of length 4 in H(2,5)H(2,5) (Figure 4)
[4,4;4,8][4,4;4,8]G5∗4G_5*4

Table 18.

The adjacency in the Hamming graph H(2,5) and CRC C={0,1}^2

Figure 4. (a) The adjacency in the Hamming graph H(2,5)H(2,5) and (b) CRC C={0,1}2C=\{0,1\}^2 with parameter matrix (260233044)\begin{pmatrix}2&6&0\\2&3&3\\0&4&4\end{pmatrix}

G7nG_7^n, n≤4n\leq4

G7G_7

ρ=3\rho=3
arrayconstruction
[1,1,1;1,1,2][1,1,1;1,1,2]sing

Table 19.

G72G_7^2

ρ=3\rho=3
arrayconstruction
[1,1,1;1,1,2][1,1,1;1,1,2]G7+2G_7+2
[2,2,2;2,2,4][2,2,2;2,2,4]G7∗2G_7*2

Table 20.

G73G_7^3

ρ=1\rho=1
arrayconstruction
[6;1][6;1]pc G73G_7^3
[5;2][5;2]2 pc G73G_7^3
[4;3][4;3]3 pc G73G_7^3

Table 21.

ρ=3\rho=3
arrayconstruction
[1,1,1;1,1,2][1,1,1;1,1,2]G7+4G_7+4
[2,2,2;2,2,4][2,2,2;2,2,4]G7∗2+2G_7*2+2
[3,3,3;3,3,6][3,3,3;3,3,6]G7∗3G_7*3

Table 22.

G74G_7^4

ρ=1\rho=1
arrayconstruction
[6;1][6;1]G73+2G_7^3+2
[5;2][5;2]G73+2G_7^3+2
[4;3][4;3]G73+2G_7^3+2

Table 23.

ρ=3\rho=3
arrayconstruction
[1,1,1;1,1,2][1,1,1;1,1,2]G7+6G_7+6
[2,2,2;2,2,4][2,2,2;2,2,4]G7∗2+4G_7*2+4
[3,3,3;3,3,6][3,3,3;3,3,6]G7∗3+2G_7*3+2
[4,4,4;4,4,8][4,4,4;4,4,8]G7∗4G_7*4

Table 24.

Acknowledgments

The author is grateful to S. V. Avgustinovich for discussions and pointing out the connection between construction of the code of length 3 given in Section 3.2, to A. Yu. Vasil’eva for fruitful discussion of the material of the paper, to V. R. Danilko for kindly providing multicore computing resources for solving the binary linear programming problems and A. A. Panin for recommending the HiGHS package for Python.

The results of the paper were obtained in the pre-AI era. At the final part of the paper production the proofs were cross-verified in the Lean language using the AI Aristotle agent: aristotle.harmonic.fun, which was also used to draw all the figures and reformat raw data into tables.

Ivan Yurevich Mogilnykh

Sobolev Institute of Mathematics,

pr. Koptyuga, 4,

630090, Novosibirsk, Russia

Email address: [email protected]

References

  1. [1]B. AlBdaiwi, P. Horak, L. Milazzo, Enumerating and decoding perfect linear Lee codes, Des. Codes Cryptogr., 52:2 (2009), 155–162. DOI: 10.1007/s10623-009-9273-3.DOI
  2. [2]S.V. Avgustinovich, A.Yu. Vasil’eva, Completely regular codes in the n-dimensional rect-angular grid, Siberian Electronic Mathematical Reports, 19:2 (2022), 861–869. DOI: 10.33048/semi.2022.19.072.
  3. [3]S.V. Avgustinovich, A.Yu. Vasil’eva, I.V. Sergeeva, Distance regular colorings of an infinite rectangular grid, J. Appl. Ind. Math., 6:3 (2012), 280–285. DOI: 10.1134/S1990478912030027.DOI
  4. [4]M. Axenovich, On multiple coverings of the infinite rectangular grid with balls of constant radius, Discrete Math., 268:1–3 (2003), 31–48. DOI: 10.1016/S0012-365X(02)00744-6.DOI
  5. [5]E.A. Bespalov, D.S. Krotov, A.A. Mati ushev, A.A. Taranenko, K.V. Vorob’ev, Perfect 2-colorings of Hamming graphs, J. Combin. Des., 29:6 (2021), 367–396. DOI: 10.1002/jcd.21771.DOI
  6. [6]J. Borges, J. Rifa, V.A. Zinoviev, On completely regular codes, Probl. Inf. Transm., 55:1 (2019), 1–45. DOI: 10.1134/S0032946019010010.DOI
  7. [7]P. Dorbec, S. Gravier, I. Honkala, M. Mollard, Weighted codes in Lee metrics, Des. Codes Cryptogr., 52:2 (2009), 209–218. DOI: 10.1007/s10623-009-9277-z.DOI
  8. [8]T. Etzion, Product constructions for perfect Lee codes, IEEE Trans. Inform. Theory, 57:11 (2011), 7473–7481. DOI: 10.1109/TIT.2011.2161133.DOI
  9. [9]D.G. Fon-Der-Flaass, Perfect 2-colorings of a hypercube, Sib. Math. J., 48:4 (2007), 740–745. DOI: 10.1007/s11202-007-0075-4.
  10. [10]S.W. Golomb, L.R. Welch, Perfect codes in the Lee metric and the packing of polyominoes, SIAM J. Appl. Math., 18:2 (1970), 302–317. DOI: 10.1137/0118025.DOI
  11. [11]I. Yu. Mogilnykh, F. I. Solov’eva, Constructions and invariants of optimal codes in the Lee metric, Probl. Inf. Transm., 59:2 (2023), 71–85. doi:10.1134/S0032946023020011.
  12. [12]I.Yu. Mogilnykh, A.Yu. Vasil’eva, On null completely regular codes in Manhattan metric, Siberian Electronic Mathematical Reports, 22:2 (2025), 1311–1333. DOI: 10.33048/semi.2025.22.079.
  13. [13]S.A. Puzynina, Perfect colorings of graph G(Z²) into three colors, Diskretn. Anal. Issled. Oper., Ser. 1, 12:2 (2005), 37–54 (in Russian).
  14. [14]M. Shi, P. Solé (eds.), Completely Regular Codes in Distance Regular Graphs, Chapman and Hall/CRC, Boca Raton, 2025. DOI: 10.1201/9781003393931.DOI
  15. [15]M. Shi, R. Wu, D. S. Krotov, On q-ary shortened-1-perfect-like codes, IEEE Trans. Inf. Theory, 68:11 (2022), 7100–7106. doi:10.1109/TIT.2022.3187004.DOI
  16. [16]F.I. Solov’eva, On binary nongroup codes, in: Methods of Discrete Analysis in the Study of Boolean Functions and Graphs, vol. 37, Institute of Mathematics SB AS USSR, Novosibirsk, 1981, 65–76 (in Russian).
  17. [17]A. Tietäväinen, On the nonexistence of perfect codes over finite fields, SIAM J. Appl. Math., 24:1 (1973), 88–96. doi:10.1137/0124010.DOI
  18. [18]A.Yu. Vasil’eva, I.Yu. Mogilnykh, On K₂-extensions of completely regular codes in bipartite graphs, Probl. Inf. Transm., submitted.
  19. [19]V. A. Zinoviev, V. K. Leontiev, On perfect codes, Problems Inform. Transmission, 8:1 (1972), 17–24. Math-Net.Ru: ppi772.
  20. [20]V. A. Zinoviev, V. K. Leontiev, The nonexistence of perfect codes over Galois fields, Probl. Control Inform. Theory, 2:2 (1973), 123–132.

Paper details

vlnc:W_8yqdggge
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI Aristotle agent

View statement
Looking for related papers…
Contents