1 Introduction
The homogeneous metric is one of the most important metrics for codes over rings [Reference Shi, Alahmadi and Solé10]. It was first introduced over residue class rings in [Reference Constantinescu and Heise4], but can be defined more generally over quasi-Frobenius rings [Reference Nechaev and Khonol’d9]. Given an alphabet ring, this metric is unique up to scale, depending only on the lattice of ideals of that ring. When the ring is
$\mathbb {Z}_4$
, the homogeneous weight coincides with the Lee weight and is the Hamming weight of the Gray map [Reference Hammons, Kumar, Calderbank, Sloane and Solé7]. We focus on the ring
$\mathbb {Z}_{{2}^k}$
for an integer
$k\ge 2$
, in which case, the homogeneous weight of a vector over that ring is the Hamming weight of its image by Carlet’s Gray map [Reference Carlet3]. The study of perfect codes over
$\mathbb {Z}_{{2}^k}$
was initiated in [Reference Şiap and Özen12] for
$k=2$
and in [Reference Şiap, Özen and Şiap11] for general
$k.$
In this paper, we study unrestricted perfect codes for the homogeneous distance. We derive the sphere packing bound, correcting the expression of the sphere volume in [Reference Şiap, Özen and Şiap11] (Remark 2.1). This gives a Diophantine equation on the parameters of a perfect code, a fact which yields nonexistence results on perfect codes (Theorems 3.1, 3.2, 3.4). Following [Reference Solé13], we develop a necessary existence condition, a ‘Lloyd theorem’, in analogy to the theorem of that name in metric schemes [Reference Delsarte6, page 64], especially the Hamming scheme [Reference Cvetkovic and van Lint5]. To that end, we define an association scheme on
$\mathbb {Z}_{{2}^k}$
, which is weakly metric for the homogeneous distance. This scheme could be generalised to other rings with the homogeneous metric. We expect that our Lloyd theorem can give more extensive nonexistence results, at the price of more advanced arithmetic arguments.
The material is arranged as follows. Section 2 collects the notions on codes, homogeneous weight, Gray map and association schemes needed for the other sections. Section 3 studies the Diophantine equation for the parameters of perfect codes. Section 4 derives the Lloyd theorem.
2 Preliminaries
2.1 Codes over
$\mathbb {Z}_{{2}^k}$
For any finite set E, let
$|E|$
denote its cardinality. For any positive integer m, let the symbol
$[m]$
denote the set
$\{1,\ldots ,m\}$
. For any statement A, let 
denote its indicator function. Let
$\mathbb {Z}_{{2}^k}$
be the ring of integers modulo
$2^k$
, where k is a positive integer. Let n be a positive integer and let
$\mathbb {Z}_{{2}^k}^n$
be the set of n-tuples over
$\mathbb {Z}_{{2}^k}$
. Then,
$\mathbb {Z}_{{2}^k}^n$
is a module over
$\mathbb {Z}_{{2}^k}$
. A set
$\mathcal {C}$
is said to be a
$\textit {linear code}$
with parameters
$(n,M)$
if it is a submodule of
$\mathbb {Z}_{{2}^k}^n$
of size M.
For two vectors
$\mathbf {u}=(u_1,\ldots ,u_n)$
and
$\mathbf {v}=(v_1,\ldots ,v_n) \in \mathbb {Z}_{2^k}^n$
, the standard inner product of
$\mathbf {u}$
and
$\mathbf {v}$
is defined by
$\mathbf {u} \cdot \mathbf { v}=u_1v_1+\cdots +u_nv_n.$
In a natural way, the dual of a linear code
$\mathcal {C} \subseteq \mathbb {Z}_{2^k}^n$
is defined by
${\mathcal {C}^ \bot } = \{ \mathbf {v} \in \mathbb {Z}_{2^k}^n \mid \mathbf {u} \cdot \mathbf {v} =0 \text { for all } \mathbf {u} \in \mathcal {C}\} .$
2.2 Homogeneous weight and Gray map
The homogeneous weight of
$x\in \mathbb {Z}_{2^k}$
is given by
$$ \begin{align*} W_{\mathrm{hom}}(x) = \begin{cases} 0 & \text{if } x = \textbf{0},\\ 2^{k - 2} & \text{if } x \notin 2^{k - 1}\mathbb{Z}_{2^k},\\ 2^{k - 1} & \text{if } x \in 2^{k - 1}\mathbb{Z}_{2^k}\backslash \{ \textbf{0}\}. \end{cases} \end{align*} $$
Given two vectors
$\mathbf {{x}}=({x_1},\ldots ,{x_n})$
,
$\mathbf {{y}}=({y_1},\ldots ,{y_n}) \in \mathbb {Z}_{2^k}^n$
, the homogeneous distance
$d_{\hom }$
on
$\mathbb {Z}_{2^k}^n$
is defined from the homogeneous weight by
$$ \begin{align*}{d_{\hom }}(\mathbf{x},\mathbf{y}) = \sum_{i = 1}^n {{W _{\hom }}({y_i} - {x_i})} .\end{align*} $$
The distance
$d_{\hom }$
is a metric in
$\mathbb {Z}_{2^k}^n$
. For
$\mathbf {u} \in \mathbb {Z}_{2^k}^n$
and an integer
$t\ge 0$
, define the
$\textit {sphere}\ B_{\hom }(\mathbf {u},t)$
with
$\textit {centre}\ \mathbf {u}$
and
$\textit {radius}\ t$
by
${B_{\hom }}(\mathbf {u},t) := \{ \mathbf {v} \in \mathbb {Z}_{{2^k}}^n \mid {d_{\hom }}(\mathbf {u},\mathbf {v}) \le t\}. $
Define
$b_r=|\{\mathbf {u} \in \mathbb {Z}_{{2}^k}^n \mid d_{\hom }(\mathbf {u}, \mathbf {0})=r\}|$
. Then,
$|B_{\mathrm {hom}}(\mathbf {u},t)| = \sum _r b_r$
, where the sum is taken over the terms
$b_r= b_{2^{k-2}i}$
for
$0\le r\le t=2^{k-2}t'$
. Following [Reference Carlet3], the Gray map
$\varphi $
between
$\mathbb {Z}_{2^k}$
and
$\mathbb {Z}_2^{2^{k-1}}$
is a map from residues to elements of the Reed–Muller code
$RM(1,k-1)$
and, for each x in
$\mathbb {Z}_{2^k}$
, the homogeneous weight of x is equal to the Hamming weight of
$\varphi (x)$
. Since the homogeneous weight of
$\mathbf {x} = (x_1,\ldots ,x_n)\in \mathbb {Z}_{2^k}^n$
is the sum of the homogeneous weights of the coordinates of
$\mathbf {x}$
and the weight enumerator of
$RM(1,k-1)$
is
$1+(2^k-2)x^{2^{k-2}}+x^{2^{k-1}}$
, it follows that the generating function for the numbers
$b_r$
for
$k\ge 2$
is
$$ \begin{align} \sum_r b_r x^r=(1+(2^k-2)x^{2^{k-2}}+x^{2^{k-1}})^n. \end{align} $$
From (2.1),
$$ \begin{align*}b_r = \sum_{s = 0}^{\lfloor {{i}/{2}} \rfloor} \binom{n}{s}\binom{n-s}{i-2s} (2^k-2)^{i-2s}\end{align*} $$
and the volume of the sphere
$B_{\hom }(\mathbf {u},t)$
is
$$ \begin{align*}| B_{\hom}(\mathbf{u},t)| = \sum_r b_r = \sum_{i = 0}^{t'} \sum_{s = 0}^{\lfloor {{i}/{2}} \rfloor} \binom{n}{s}\binom{n-s}{i-2s} (2^k-2)^{i-2s}.\end{align*} $$
Remark 2.1. We note an error in [Reference Şiap, Özen and Şiap11], where the volume of the sphere
$B_{\hom }(\mathbf {u},t)$
with centre
$\mathbf {u}$
and radius t is given as
$| {{B_{\hom }}(\mathbf {u},t)} | = \sum _{i = 0}^t \binom {n}{i} (2^k-1)^i$
.
A code
$\mathcal {C}$
over
$\mathbb {Z}_{2^k}$
is t-error correcting if the following condition holds:
$$ \begin{align*}\text{for all } \mathbf{u},\ \mathbf{v} \in \mathcal{C}, \quad \mathbf{u} \ne \mathbf{v} \Rightarrow {B_{\hom }}(\mathbf{u},\ t) \cap {B_{\hom }}(\mathbf{v},\ t) = \emptyset.\end{align*} $$
If for such a t-error correcting code
$\mathcal {C}$
, the union of these spheres is
$\mathbb {Z}_{{2}^k}^n$
, that is,
$\mathbb {Z}_{{2^k}}^n = \bigcup \nolimits _{\mathbf {u} \in \mathcal {C}} {{B_{\hom }}(\mathbf {u},t)} $
, then the code is said to be perfect. In this situation, by counting the points in
$\mathbb {Z}_{{2}^k}^n$
, we have the Diophantine equation
$2^{nk} =M (\sum _{r=0}^t b_r),$
where M is the size of the perfect code. Thus, M must be a power of
$2$
. Note also that
$b_0=1$
. For later reference, for any integer c with
$0\le c \le {nk}$
, we define the Diophantine equation
$$ \begin{align*} E(c,k,t): \quad 2^{c}=\sum_{r=2^{k-2}}^t b_r+1.\end{align*} $$
2.3 Association schemes
Let X be a finite set with at least two elements and let
$R=\{R_0,R_1,\ldots ,R_s\}$
be a family of
$s+1$
relations
$R_i$
on X for
$s\ge 1$
.
Definition 2.2 [Reference Delsarte6].
The pair
$(X,R)$
will be called an association scheme with s classes if the following three conditions are satisfied:
-
(A1) the set R is a partition of
$X^2$
and
$R_0=\{(x,x) \mid x\in X\}$
is the diagonal relation; -
(A2) for
$i=0,1, \ldots , s$
, the inverse
$R_i^{-1}=\{(y,x)\mid (x,y)\in R_i\}$
of the relation
$R_i$
also belongs to R; -
(A3) for any triple of integers
$i,j,k=0,1,\ldots ,s$
, there exists a number
$p_{ij}^k=p_{ji}^k$
such that
$|\{z\in X \mid (x,z)\in R_i,\ (z,y)\in R_j\}|=p_{ij}^k$
for all
$(x,y)\in R_k$
.
For
$i=0,1,\ldots ,s$
, the relation
$R_i$
can be described by its
$\textit {adjacency matrix}\ {D_i} $
, which is defined by
$$ \begin{align*}{D_i} (x,y) = \begin{cases} 1 & \text{if } (x,y) \in R_i,\\ 0 & \text{if } (x,y) \notin R_i. \end{cases} \end{align*} $$
It is well known that
$T = \{ \sum _{i = 0}^s {{\alpha _i}{D_i}\ |\ } {\alpha _i} \in \mathbb {C}\}$
constitutes a complex algebra called the Bose–Mesner algebra. There are two ‘natural’ bases
$\{D_i\}$
and
$\{J_i\} $
of the Bose–Mesner algebra of a scheme, where
$\{J_i\}_{i\in \{0,1,\ldots ,s\}}$
is a unique basis of minimal idempotents that satisfy
$J_i^2 = {J_i}, \ {J_i}{J_j} = \mathbf {{0}} \ (i \ne j),\ \sum _{i = 0}^s {{J_i} = {I_{|X| }}}, $
where
$I_{|X| }$
is the identity matrix of order
$|X|$
. We consider the linear transformations from
$J_k$
to
$D_k$
. First,
$D_k = \sum _{i = 0}^s P_k(i)J_i$
for
$k = 0,1,\ldots ,s.$
The complex numbers
$P_k(0),P_k(1),\ldots ,P_k(s)$
are the eigenvalues of
$D_k$
, also called the first eigenvalues of the scheme.
From [Reference Solé13], the
$\textit {quasi-distance}\ d$
on X is a mapping from
$X^2$
to the nonnegative reals satisfying the triangle inequality. An association scheme
$(X,R)$
with s classes is a
$\textit {weakly metric}$
scheme for the quasi-distance d if the quasi-distance d is constant on the classes of the scheme, that is, for all
$(a,b)\in X^2, \ aR_ib\Rightarrow d(a,b)=d(i),$
where
$i\in \{0,1,\ldots ,s\}$
. The Lloyd polynomial in a weakly metric association scheme is defined by
${\Psi _r}(l) = \sum _{d(k) \le r} {{P_k}(l)} $
. In a weakly metric scheme
$(X,R)$
with quasi-distance d, the
$\textit {dispersion function}\ \Pi $
is defined by
$\Pi (j) = | {\{ i\in \{0,1,\ldots ,s\} \mid d(i) \le j\} } |.$
3 Diophantine condition
Replacing
$x^{2^{k-2}}$
by x in (2.1), we obtain a generating function with a simpler form,
$$ \begin{align} \sum_{i=0}^{t'} d_i x^i = (1+(2^k-2)x+x^2)^n \quad\text{where } d_i = b_{2^{k-2}i} = b_r, \end{align} $$
and the equation
$E(c,k,t)$
becomes
$2^{c} =\sum _{i=1}^{t^{\prime }} d_i+1,$
where
$t = 2^{k-2} t'$
.
Theorem 3.1. There are no
$4$
-error correcting perfect codes of length n in the homogeneous metric over
$\mathbb {Z}_{8}$
for
$n>1$
.
Proof. Suppose that
$\mathcal {C}$
is a
$4$
-error correcting perfect code with parameters
$(n,M)$
over
$\mathbb {Z}_{8}$
. Then, the parameters of
$\mathcal {C}$
must satisfy the equation
$E(c,k,t)$
when
$t^{\prime }=2$
. According to the generating function (3.1),
$$ \begin{align*} {{d_i} = \sum_{s = 0}^{\lfloor {{i}/{2}} \rfloor } \binom{n}{s} \binom{n-s}{i-2s} (2^k - 2)^{i - 2s}}, \quad i = 0,1,\ldots,2n. \end{align*} $$
Then, the volume of the sphere of radius
$4$
in
$\mathbb {Z}_8^n$
is
$$ \begin{align*} \sum\limits_{i = 0}^2 {d_i} &= 1 + ({2^k} - 2)n + \frac{1}{2} {({2^k} - 2)^2}n(n - 1) + n=(2n - 1)(9n - 1). \end{align*} $$
Note that for
$n>1$
,
$2n-1$
is an odd number,
$2n-1\ne 2^l$
for any integer l with
$0\le l\le c$
and
$t^{\prime }=2<2n$
. However, the left-hand side of
$E(c,k,t)$
only has divisors of the form
$2^l$
. Consequently, the parameters of
$\mathcal {C}$
fail to satisfy the Diophantine condition when
$t'=2$
and there are no such
$4$
-error correcting perfect codes
$\mathcal {C}$
with respect to the homogeneous weight over
$\mathbb {Z}_8$
for
$n>1$
.
Theorem 3.2. Let n and k be two positive integers with
$n>1$
. There are no
$(2^{k-2}\times 3)$
-error correcting perfect codes of length n in the homogeneous metric over
$\mathbb {Z}_{2^k}$
for
$k\ge 2$
if n is even or n is odd and
$n \equiv 3\ (\bmod \ 4)$
.
Proof. According to the generating function (3.1), the volume of the sphere of radius
$2^{k-2}\times 3$
in
$\mathbb {Z}_{2^k}^n$
is
$$ \begin{align*} \sum_{i = 0}^3 {{d_i}} & =1 +\binom{n}{1}(2^k-2)+\binom{n}{2}(2^k-2)^2+\binom{n}{1}+\binom{n}{3}(2^k-2)^3+\binom{n}{1}\binom{n-1}{1}(2^k-2)\\ & ={ 1 + n + ({2^k} - 2){n^2} + } \frac{{{{({2^k} - 2)}^2}n(n - 1)}}{2}+ \frac{{{{({2^k} - 2)}^3}n(n - 1)(n - 2)}}{6}\\ & =1 + n + 2\bigg[ ({2^{k - 1}} - 1){n^2} + {{({2^{k - 1}} - 1)}^2}n(n - 1) +\frac{{2{{({2^{k - 1}} - 1)}^3}n(n - 1)(n - 2)}}{3}\bigg]. \end{align*} $$
If n is even, then
$\sum _{i = 0}^3 {{d_i}}>1$
is odd and
$t'=3\le 2n$
. The equation
$E(c,k,t)$
does not hold in this case, which is a contradiction.
If n is odd, let
$n+1=2^an_1$
, where
$n_1$
is odd and
$a\ge 1$
. Then,
$$ \begin{align*} & \sum_{i = 0}^3 {{d_i}} = {2^a}{n_1} + 2({2^{k - 1}} - 1)n[n +({2^{k - 1}} - 1) (n - 1)] + \frac{{4({2^{k - 1}} - 1)^3n(n - 1)(n - 2)}}{3}\\&\quad = 2\bigg[ {{2^{a- 1}}{n_1} {\kern-1pt}+{\kern-1pt} \frac{{2({2^{k - 1}} - 1)^3n(n - 1)(n - 2)}}{3} } {\ +\ ({2^{k - 1}} - 1)n(n {\kern-1pt}+{\kern-1pt} ({2^{k - 1}} {\kern-1pt}-{\kern-1pt} 1)(n {\kern-1pt}-{\kern-1pt} 1))} \bigg]{\kern-1pt}={\kern-1pt}2b, \end{align*} $$
where
$b>1$
is an odd number and
$3< 2n$
under the conditions that n and
$n_1$
are odd and
$n \equiv 3\ (\bmod \ 4)$
, noting that
${{n(n - 1)(n - 2)}}/{3}$
is an integer. Again, this gives a contradiction. The proof of the second part has been finished.
The following arithmetic lemma plays a crucial role in the proof of Theorem 3.4.
Lemma 3.3 (Lucas’ theorem, [Reference Lucas8]).
Let p be a prime number, and let a and b be two nonnegative integers. Then,
$$ \begin{align*}\binom{pa+r_a}{pb+r_b} \equiv \binom{a}{b} \binom{r_a}{r_b}\quad \pmod p,\end{align*} $$
where
$r_a$
,
$r_b\in \{0,1,\ldots ,p-1\}$
.
Theorem 3.4. Let
$n, k, t'$
and l be positive integers with
$k\ge 2$
. If
$n=2^l$
, then there are no
$2^{k-2} t'$
-error correcting perfect codes of length n in the homogeneous metric over
$\mathbb {Z}_{2^k}$
for
$1\le t'<2n$
.
Proof. According to the equation
$E(c,k,t)$
,
$$ \begin{align*} {2^c} = \sum\limits_{i = 0}^{t'} d_i & = 1 + \sum\limits_{i = 1}^{t'} \sum\limits_{s = 0}^{\lfloor {{i}/{2}} \rfloor} \binom{n}{s} \binom{n-2}{i-2s} (2^k-2)^{i-2s} \\ & = 1 + \sum\limits_{i\in [t'],\, i\ \mathrm{odd}} \sum\limits_{s = 0}^{\lfloor {{i}/{2}} \rfloor } \binom{n}{s} \binom{n-s}{i-2s} (2^k-2)^{i-2s} \\ &\quad + \sum\limits_{i\in [t'],\, i\ \mathrm{even}} \sum\limits_{s = 0}^{{i}/{2} - 1} \binom{n}{s} \binom{n-s}{i-2s} (2^k-2)^{i-2s} + \sum_{j=1}^{\lfloor t'/2\rfloor} \binom{n}{j}. \end{align*} $$
By Lemma 3.3, for
$n=2^l$
, the
$\binom {n}{j}$
are even for
$1\le j\le \lfloor {t{'}/{2}} \rfloor $
since
$ {\lfloor {t'}/{2} \rfloor }<n$
and so the right-hand side of the equation is odd, which is a contradiction.
4 A Lloyd theorem
In [Reference Solé13], the Lloyd theorem in a weakly metric association scheme is derived by using the Lloyd polynomial and the first eigenvalues of the scheme.
Lemma 4.1 [Reference Solé13, Theorem 2].
Let Y be e-error correcting. Then,
${\Psi _e}(l)$
vanishes for at least
$\Pi (e)-1$
values of l.
Bariffi
$\textit {et al}.$
[Reference Bariffi, Cavicchioni and Weger1] introduced a finer partition of the alphabet ring which can be applied to the ring
$\mathbb {Z}_{2^k}$
: namely,
$Z:=\{0\}, U:=\mathbb {Z}_{2^k}^{\times }, S:= \langle 2^{k-1}\rangle , V:= \langle 2 \rangle \setminus \langle 2^{k-1} \rangle .$
By [Reference Zinoviev and Ericson14, Lemma], this partition induces an association scheme on
$\mathbb {Z}_{2^k}$
with the set of relations
$R=\{R_Z, R_U, R_S, R_V\}$
, where
$xR_I y\Leftrightarrow x-y\in I$
for any
$I\in \{Z,U,S,V\}$
. Now, we consider the extension of length n of this association scheme.
Definition 4.2. Let
$\pi _I(\mathbf {x}):=|\{j=1,\ldots ,n \mid x_j\in I\}|$
, where
$\mathbf {x}=(x_1,\ldots ,x_n)\in \mathbb {Z}_{2^k}^n$
and
$I\in \{Z,U,S,V\}$
, and let
$D_{\pi }:=\{\pi ^{(i)}=(\pi _Z^{(i)},\pi _U^{(i)},\pi _S^{(i)},\pi _V^{(i)})\mid i=0,1,\ldots ,s \}$
. Take
$s=\binom {n+3}{3}$
. Then, we define the weakly metric association scheme on
$\mathbb {Z}_{2^k}^n$
with the set of relations
$R=\{R_0, R_1,\ldots ,R_s\}$
by
$$ \begin{align*}\mathbf{x} R_i \mathbf{y} \Leftrightarrow \pi(\mathbf{x}-\mathbf{y})=\pi^{(i)}\in D_{\pi}\quad \text{for any } \mathbf{x},\mathbf{y} \in \mathbb{Z}_{2^k}^n \text{ and } i\in \{0,1,2,\ldots,s\},\end{align*} $$
and the quasi-distance d by
$$ \begin{align*}\mathbf{x} R_i \mathbf{y} \Leftrightarrow d(\mathbf{x},\mathbf{y})=d(i)=\pi^{(i)}_U+\pi^{(i)}_V+2\pi^{(i)}_S \quad\text{for all } (\mathbf{x},\mathbf{y})\in(\mathbb{Z}_{2^k}^n)^2.\end{align*} $$
Following [Reference Bariffi, Cavicchioni and Weger1], for any pair
$(\pi , \rho )\in D_{\pi }^2$
, we define the set of all compositions of
$\rho $
with respect to
$\pi $
by
$$ \begin{align*} \mathrm{Comp}_\pi(\rho) := \bigg\{{\tau} = \ & (\tau_Z, \tau_U, \tau_S, \tau_V) \ \bigg|\ \tau_I = (\tau_{IZ}, \ldots,\tau_{IV}) \in \{0, \ldots, \pi_i\}^4 \ \text{with} \\ & \sum_{J \in \{Z,U,S,V\}} \tau_{IJ} = \pi_I \text{ for all } I, \sum_{I \in \{Z,U,S,V\}} \tau_{IJ} = \rho_J\ \text{ for all } J \bigg\}. \end{align*} $$
This definition is crucial for our main result in this section.
Theorem 4.3. Let
$n,\ k$
and
$t'$
be three positive integers with
$1\le t' <2n$
, and let
$H{\kern-1pt}:={\kern-1pt}\{\pi {\kern-1pt}={\kern-1pt}(\pi _Z,\ \pi _U,\ \pi _S,\ \pi _V)\ |\ \pi {\kern-1pt}\in{\kern-1pt} D_{\pi } \ and \ 0\le \pi _U{\kern-1pt}+{\kern-1pt}\pi _V{\kern-1pt}+{\kern-1pt}2\pi _S{\kern-1pt}\le{\kern-1pt} t'\}$
. Let 
. If there is a
$2^{k-2} t'$
-error correcting perfect code of length n in the homogeneous metric over
$\mathbb {Z}_{2^k}^n$
for
$k\ge 3$
, then the Lloyd polynomial
$\Phi _{t'}(\mathbf {x})$
, namely
$$ \begin{align*} \sum_{\pi \in H}\sum_{\tau \in {\mathrm{Comp}_{\mathbf{x} }(\pi)}} {\Bigg( \prod\limits_{I \in \{ Z,U,S,V\}} { \binom{x_{I}}{\tau_{IZ}, \ldots, \tau_{IV}} }\Bigg)} {( { - 1} )^{{\tau_{US}} + {\tau_{SU}} + {\tau_{VV}}}}{2^{{\tau_{VV}}}}{{(2^{k-1})}^{{\tau_{SU}} + {\tau_{ZU}}}}{(2^{k-1}-2)}^{\tau_{ZV}}f, \end{align*} $$
vanishes for at least
$\Pi ({{t'}})-1$
values of
$\mathbf {x}=(x_Z,x_U,x_S,x_V)$
, where the value of
$\Pi ({{t'}})$
is given by one of the following two cases.
-
(1) If
$1\le {t'} \le n$
, then
$$ \begin{align*} \Pi(t') = \begin{cases} \displaystyle \frac{1}{2} \binom{t'+4}{3} - \frac{1}{8}(t+2)(t'+4) & \text{if } t' \text{ is even}, \\\\[-8pt] \displaystyle \frac{1}{2}\binom{t'+3}{3} + \frac{1}{8}(t'+1)(t'+3) & \text{if } t' \text{ is odd}. \end{cases} \end{align*} $$
-
(2) If
$n\le t' \le 2n$
, then
$$ \begin{align*} \Pi(t') = \begin{cases} \displaystyle \binom{n+3}{3} - \frac{1}{2}\binom{2n-t'+2}{3} - \frac{1}{8}(2n-t')(2n-t'+2) & \text{if } t'\ \text{is even}, \\\\[-8pt] \displaystyle \binom{n+3}{3} - \binom{2n-t'+2}{3} - \frac{1}{2}\binom{2n-t'+1}{3} \\ \qquad\qquad\qquad\quad\qquad\ \displaystyle + \frac{1}{8}(2n-t'-1)(2n-t'+1) & \text{if } t' \text{ is odd}. \end{cases} \end{align*} $$
Proof. The proof of this result relies on two steps. The first is to count the number of
$\pi ^{(i)}\in D_{\pi }$
satisfying
$d(i)\le t'$
.
If
$1\le t'\le n$
, then for any
$\pi _S\in \{0,1,\ldots ,\lfloor t'/2 \rfloor \}$
, we have
$0\le \pi _U+\pi _R \le t'-2\pi _S$
. We obtain the number of
$\pi ^{(i)}\in D_{\pi }$
satisfying
$d(i)\le t'$
by computing
$\sum _{{\pi _S} = 0}^{\lfloor t'/2 \rfloor } \sum _{i = 1}^{t' - 2\pi _S + 1} i $
.
If
$n <t'<2n$
, then
$t'-n\le \lfloor {t'}/{2}\rfloor $
. Although we still have
$\pi _S\in \{0,1,\ldots ,\lfloor t'/2 \rfloor \}$
, the maximum value of
$\pi _U+\pi _R$
depends on the relationship between
$\pi _S$
and
$t'-n$
. If
$0\le \pi _S\le t'-n$
, then
$0\le \pi _U+\pi _V \le n-\pi _S$
and the corresponding number of
$\pi ^{(i)}$
is
$\sum _{{\pi _S} = 0}^{t' - n} {\sum _{j = 1}^{n - {\pi _S} + 1} j } = \binom {n+3}{3} - \binom {2n-t'+2}{3}$
for
$t'$
both even and odd. If
$t'-n< \pi _S\le \lfloor t'/2 \rfloor $
, we obtain the result by computing
$\sum _{\pi _S=t'-n+1}^{\lfloor t'/2\rfloor } \sum _{i = 1}^{t' - 2{\pi _S} + 1} i $
.
By [Reference Bariffi, Cavicchioni and Weger1, Theorem 30], combined with the general MacWilliams formula for translation association schemes ([Reference Delsarte6, page 88], [Reference Brouwer, Cohen and Neumaier2, Theorem 2.10.12, page 71]), the first eigenvalues of the weakly metric association scheme defined in Definition 4.2 are
$$ \begin{align} \sum\limits_{\tau \in {\mathrm{Comp}_{\mathbf{x} }(\pi)}} {\Bigg( \prod\limits_{I \in \{ Z,U,S,V\}} { \binom{x_{I}}{\tau_{IZ}, \ldots, \tau_{IV}} }\Bigg)} {( { - 1} )^{{\tau_{US}} + {\tau_{SU}} + {\tau_{VV}}}}{2^{{\tau_{VV}}}}{{(2^{k-1})}^{{\tau_{SU}} + {\tau_{ZU}}}}{(2^{k-1}-2)}^{\tau_{ZV}}f. \end{align} $$
The proof is completed by Lemma 4.1.
Example 4.4. Let
$n {\kern-1pt}={\kern-1pt} 2$
,
$t' {\kern-1pt}={\kern-1pt} 1$
and
$k {\kern-1pt}={\kern-1pt} 3$
. Then,
$H {\kern-1pt}={\kern-1pt} \{(2,0,0,0), (1,1,0,0), (1,0,0,1)\}$
. For
$\pi = (2,0,0,0)$
, we have
$|\operatorname {Comp}_{\mathbf {x}}(\pi )| = 1$
and the value given by (4.1) is
$1$
for any
$\mathbf {x} = (x_Z, x_U, x_S, x_V) \in D_{\pi }$
. We focus on
$\mathbf {x}$
such that
$\tau _{US}, \tau _{SU}, \tau _{VV} \neq 0$
for
$\tau \in \operatorname {Comp}_{\mathbf {x}}(\pi )$
(to analyse negative terms in (4.1)). There exist seven such
$\mathbf {x}$
, but we only detail two critical cases due to their similarity.
If
$\mathbf {x} = (0,0,2,0)$
, then
$|\!\operatorname {Comp}_{\mathbf {x}}(\pi )| = 1$
for both
$\pi = (1,1,0,0)$
and
$\pi = (1,0,0,1)$
. The corresponding
$\tau $
matrices are
$$ \begin{align*}\begin{pmatrix} 0&0&1&0 \\ 0&0&1&0 \\ 0&0&0&0 \\ 0&0&0&0 \end{pmatrix} \quad\text{and}\quad \begin{pmatrix} 0&0&1&0 \\ 0&0&0&0 \\ 0&0&0&0 \\ 0&0&1&0 \end{pmatrix},\end{align*} $$
respectively, and
$\Phi _1(\mathbf {x}) = -5$
. If
$\mathbf {x} = (1,0,1,0)$
, then
$|\!\operatorname {Comp}_{\mathbf {x}}(\pi )| = 2$
for both
$\pi = (1,1,0,0)$
and
$\pi = (1,0,0,1)$
. The
$\tau $
matrices are
$$ \begin{align*}\begin{pmatrix} 1&0&0&0 \\ 0&0&1&0 \\ 0&0&0&0 \\ 0&0&0&0 \end{pmatrix},\ \begin{pmatrix} 0&0&1&0 \\ 1&0&0&0 \\ 0&0&0&0 \\ 0&0&0&0 \end{pmatrix} \quad\text{and}\quad \begin{pmatrix} 1&0&0&0 \\ 0&0&0&0 \\ 0&0&0&0 \\ 0&0&1&0 \end{pmatrix},\ \begin{pmatrix} 0&0&1&0 \\ 0&0&0&0 \\ 0&0&0&0 \\ 1&0&0&0 \end{pmatrix},\end{align*} $$
respectively, and
$\Phi _1(\mathbf {x}) = 4$
. For the other five
$\mathbf {x}$
, the values of
$\Phi _1$
are found to be
$\Phi _1((0,1,1,0)) = -2$
,
$\Phi _1((0,0,1,1)) = -4, \Phi _1((0,0,0,2)) = -3, \Phi _1((1,0,0,1)) = 5$
and
$\Phi _1((0,1,0,1)) = -1$
. For all other
$\mathbf {x}$
, the terms in (4.1) are positive. Since
$\Pi (1) - 1 = 2$
, there exists no
$2$
-error-correcting perfect code of length
$2$
in the homogeneous metric over
$\mathbb {Z}_8$
.
