¹

Keywords: Association schemes, translation schemes, multivariate Q-polynomial schemes, weakly metric schemes, few distance codes, tight designs, perfect codes
MSC (2020): 05 E30, 05 E10, 05 B15, 05 B10, 05 B 30

1 Introduction↩︎

The landmark PhD thesis of Delsarte in 1973 created the field of algebraic combinatorics [1]. In that seminal work, the idea of association schemes (an algebraic structure coming from both statistics [2] and group theory [3], [4]) and linear programming (a tool from combinatorial optimization [5]) are combined to derive bounds on the size of certain combinatorial objects (codes, designs), and characterize the special objects meeting these bounds (perfect codes, tight designs). The applicability of these techniques was limited to some particular association schemes (metric schemes, Q-polynomial association schemes) which enjoy a very simple generator structure of their Bose-Mesner algebra. However, in many applications, association schemes that are not metric and/or not Q-polynomial are needed [6]–[11]. In [12] was introduced the notion of weakly metric association scheme, which was further developped in [13]. This idea was revisited very recently to derive asymptotic non existence results for perfect codes [14]. Last year, the concept of multivariate P-polynomial (and also Q-polynomial) association schemes was introduced by Bannai et al. [15], generalizing [16]. A companion concept of m-distance regular graph generalizing metric schemes and distance regular graphs, was derived in Bernard et al. [17] the year before. The appendix in [14] shows that multivariate P-polynomial schemes are in fact, under mild hypotheses, weakly metric for a distance related to the vectorial distance in [17].

This paper is an attempt to lay the foundations of multivariate Delsarte theory of codes and designs in general association schemes. It is clear that any association scheme is \(\ell\)-variate Q-polynomial for some \(\ell.\) See [15] for the P-polynomial version of this observation. Thus, we consider extremal properties of codes and designs in multivariate Q-polynomial association schemes. A result of [1] was popularized in [18]. It is an upper bound on the size of a set with a given number of pairwise relations, the so called degree of the set. In [18], this bound is given for the Hamming scheme as an upper bound on the size of codes with a given number of pairwise distances. In the situation of a weakly metric Q-polynomial association scheme there are two possible generalizations of this bound: for codes with a given degree or for codes with a given number of distances. This happens because the scheme being not metric in general, several relations correspond to the same distance. We give these two possible generalizations. The pairwise relations of codes in the first case are zeros of the degree Wilson polynomial. The pairwise distances of codes meeting the second bound are zeros of the distance Wilson polynomial. Codes meeting the second, in the context of self-dual translation schemes, and assuming a subgroup structure are the duals of perfect codes. What is more, these perfect codes must have a covering radius restricted by the regularity of the dispersion function of the scheme.

In an interlude section we show that many multivariate Q-polynomial association schemes of interest in Combinatorics and Information Theory satisfy an hypothesis needed for the second bound. Thus we consider bivariate (q-ary Johnson scheme [10]), \(4\)-variate schemes (weakly metric for the homogeneous metric [8]), and multivariate schemes like the Lee scheme [11], the sum rank scheme [6] (sum rank codes are used in multishot network coding [19]), mixed alphabet scheme (related to mixed level orthogonal arrays [20]).

In the final part of the paper, we consider designs in a weakly metric multivariate Q-polynomial scheme. The notion of \(T\)-design with \(T\) a set makes sense in any multivariate Q-polynomial scheme. Note that designs in this general situation were explored in [10], [20]. To define \(t\)-designs with \(t\) an integer we need a weakly metric structure. We derive a generalized Rao lower bound on the size of such designs. Designs meeting that bound with equality we call distance tight designs. We show that tight designs satisfy a Lloyd-type condition on the distance Wilson polynomial. To be complete we also give a lower bound on the size of \(T\)-designs. Tight designs in that context we call degree tight designs. They satisfy a Lloyd type condition on the degree Wilson polynomial. If furthermore, the scheme is a self-dual translation scheme then the dual of a distance tight design is shown to be a perfect code.

The material is arranged as follows. Section 2 contains preliminary notions on associations schemes needed for the rest of the paper. Section 3 derives an upper bounds on codes of given degree. Section 4 derives a similar bound on codes with a given number of pairwise distances. Section 5 gives examples of schemes where the previous bounds apply. Section 6 considers designs: Rao bound, tight designs and the Wilson polynomial. Section 7 concludes the article. An appendix collects facts on and examples of self-dual translation association schemes.

2 Preliminary↩︎

2.1 Weakly metric association schemes↩︎

We recall the axioms of commutative association schemes. See [3], [4], [21] for background and details.

We say that an association scheme \((X,R)\) is weakly metric (shortly WMAS) for a quasi-distance \(d\) if the quasi-distance is constant on the classes of the scheme [12]. Formally, let \(d\) be a mapping from \(X^2\) to the non-negative real numbers satisfying the triangle inequality. The scheme \((X,R)\) with \(s\) classes is weakly metric for \(d\) if for all \((a,b)\in X^2\) and for all ordering \(\mathcal{I}\) of \(\{0,1,\ldots,s\}\), there is a map \(d_{\mathcal{I}}: \mathcal{I} \longrightarrow \mathbb{R}^+\) such that \[\forall i \in {\mathcal{I}},\,aR_{i}b \Rightarrow d(a,b)=d_{\mathcal{I}}(i).\] If the choice of \(\mathcal{I}\) is irrelevant or obvious we just write \(d(.)=d_{\mathcal{I}}(.).\) In this paper we will use either \(\mathcal{I}=\mathcal{D}\) or \(\mathcal{I}=\mathcal{D}^*.\) These two sets are defined in the next subsection below.

For each relation \(R_i\) (\(i = 0, 1, \dots, s\)), we define its adjacency matrix \(A_i\) by: \[A_i(x, y) = \begin{cases} 1 & \text{if } (x, y) \in R_i, \\ 0 & \text{if } (x, y) \notin R_i. \end{cases}\]

The set of all complex linear combinations of these adjacency matrices forms a complex algebra: \[\mathfrak{A} = \left\{ \sum_{i=0}^s \alpha_i A_i \,\bigg|\, \alpha_i \in \mathbb{C} \right\},\] known as the Bose-Mesner algebra [3], [4], [21] of the association scheme \((X,R)\). The Bose-Mesner algebra admits two natural bases. The first is the set of adjacency matrices \(\{A_i\}_{i=0}^s\). The second is a unique basis of primitive idempotents \(\{E_j\}_{j=0}^s\) satisfying: \[E_j^2 = E_j, \quad E_j E_k = 0 \;(j \neq k), \quad \sum_{j=0}^s E_j = I_{|X|},\] where \(I_{|X|}\) denotes the identity matrix of order \(|X|\). The linear transformation between these bases is given by: \[A_i = \sum_{j=0}^s P_i(j) E_j, \quad i = 0, 1, \dots, s.\] The complex numbers \(P_i(0), P_i(1), \dots, P_i(s)\) are the eigenvalues of \(A_i\), also called the first eigenvalues of the association scheme. Similarly, the complex numbers \(Q_j(0), Q_j(1), \ldots, Q_j(s)\) where the second eigenmatrix \(Q = (Q_j(i))_{i,j}\) is defined by \[|X|E_j = \sum_{i=0}^s Q_j(i)A_i, \quad j = 0, 1, \ldots, s,\] are called the second eigenvalues of the association scheme.

The Bose-Mesner algebra \(\mathfrak{A}\) is also closed under entrywise multiplication, denoted by \(\circ\) and called the Hadamard product [15].

Let \[X_i = \bigl\{x \in X \mid (0, x) \in R_i\bigr\}, \quad \text{for } 0 \leq i \leq s.\] Then \(X_0, X_1, \dots, X_d\) give a partition of \(X\), and \[(x, y) \in R_i \iff y - x \in X_i \quad (0 \leq i \leq s).\]

Equivalently, if the code \(C\) has minimum distance \(d\) and we set \(e = \lfloor (d-1)/2 \rfloor\), then \(C\) is perfect if and only if it meets the sphere packing bound: \[|C| \cdot |B(c,e)| = |X|.\] This equivalent characterization is often used as well.

2.2 Multivariate Q-polynomial schemes↩︎

We begin with general definitions on polynomials in several variables.

Since each monomial \(x_1^{n_1} x_2^{n_2} \ldots x_\ell^{n_\ell}\) can be associated to the tuple \((n_1, n_2, \ldots, n_\ell) \in \mathbb{N}^\ell\), we use the same order and notation \(\leq\) on \[\mathbb{N}^\ell = \{(n_1, n_2, \ldots, n_\ell) \mid n_i \text{ are non-negative integers}\}.\] Note that for \(\ell = 1\), there is a unique monomial order, which is the one associated to the natural ordering of the integers.

Let \(e_i \in \mathbb{N}^\ell\) be the tuple whose \(i\)-th entry is \(1\) and all the other entries are \(0\). We can now define the main framework of our study.

2.3 Linear programming in association schemes↩︎

Let \(N = \{0,1,\ldots,n\}\) and let \(A = [A_k(i)]\) be a matrix of \(R(N,N)\) such that \(A_0(i)=1\) for all \(i\in N\) and \(A_k(0)>0\) for all \(k\in N\). Let \(M\subseteq N\) be a subset containing \(0\), denote \(M^* = M\setminus\{0\}\) and \(N^* = N\setminus\{0\}\). The linear-programming problem \((A,M)\) [1] is defined as follows: \[(A,M)\qquad \begin{cases} \text{max}\; g = \displaystyle\sum_{i\in M} b_i, \\[1em] \displaystyle\sum_{i\in M} b_i A_k(i) \;\ge\; 0, & \forall k\in N^*, \\[1em] b_i \;\ge\; 0, & \forall i\in M^*. \end{cases}\]

An \(n+1\)-tuple \(b = (b_0,b_1,\ldots,b_n)\) is called a program of \((A,M)\) if it satisfies \(b_0=1\), \(b_i=0\) for \(i \in N-M\), and the constraints (2.1). A maximal program is a program that maximizes \(g\); its value is denoted by \(g(A,M)\).

The dual problem \((A,M)'\) is given by \[(A,M)'\qquad \begin{cases} \text{min}\; \gamma = \displaystyle\sum_{k\in N} \beta_k A_k(0), \\[1em] \displaystyle\sum_{k\in N} \beta_k A_k(i) \;\le\; 0, & \forall i\in M^*, \\[1em] \beta_k \;\ge\; 0, & \forall k\in N^*. \end{cases}\]

An \(n+1\)-tuple \(\beta = (\beta_0,\beta_1,\ldots,\beta_n)\) is a program of \((A,M)'\) if \(\beta_0=1\) and it satisfies (2.2). It is a minimal program if, besides, it gives the smallest value to the function \(\gamma\).

Next we introduce a very important lemma, known in the literature of linear programming as complementary slackness Lemma [21].

[1]

1. The problems \((A,M)\) and \((A,M)'\) admit at least one extremal program (i.e. a maximal and a minimal program, respectively). Each pair of programs \(b\) of \((A,M)\) and \(\beta\) of \((A,M)'\) satisfies \(g \le \gamma\). Moreover, the extremal values of \(g\) and \(\gamma\) are equal.

2. For each pair \((b,\beta)\) of extremal programs, the following two sets of equations hold: \[\begin{align} \beta_k \left( \sum_{i \in M} b_i A_k(i) \right) &= 0, \quad \forall k \in N^*,\\ b_i \left( \sum_{k \in N} \beta_k A_k(i) \right) &= 0, \quad \forall i \in M^*. \end{align}\] Conversely, if a pair \((b,\beta)\) of programs satisfies \((2.3)\) and \((2.4)\), then it is a pair of extremal programs.

Let \(Y \subseteq X\) be a nonempty subset and let \(R = \{R_0, R_1, \ldots, R_n\}\) be a set of relations on \(X\). The inner distribution of \(Y\) with respect to \(R\) is the \((n+1)\)-tuple \(a = (a_0, a_1, \ldots, a_n)\) defined by \[a_i = \frac{1}{|Y|}\,|R_i \cap Y^2|,\] i.e., \(a_i\) is the average number of points of \(Y\) that are \(i\)-th associates of a fixed point of \(Y\). Clearly, \[a_0 = 1, \qquad \sum_{i=0}^{n} a_i = |Y|,\] and if \(R_i^T=R_j\) we have \(a_i = a_j\).

3 Codes of given degree↩︎

In this section, we adapt the proof of [1] to the multivariate setting.

Let \(\mathfrak{X}=(X, \{R_\alpha\}_{\alpha \in \mathcal{I}})\) be such a scheme, where \(\mathcal{I}\) is the index set of relations and each relation \(R_\alpha\) corresponds to a point \(z_\alpha \in \mathbb{R}^\ell\). The primitive idempotents are denoted by \(\{E_\gamma\}_{\gamma \in \mathcal{D}^*}\) with ranks \(\mu_\gamma = \operatorname{rank}(E_\gamma)\). By the \(Q\)-polynomial property there exist multivariate polynomials \(\Phi_\gamma(x_1,\dots,x_\ell)\) such that for every \(\gamma \in \mathcal{D}^*\) and every \(\alpha \in \mathcal{I}\) \[Q_\gamma(\alpha) = \Phi_\gamma(z_\alpha),\] and such that the total degree of \(\Phi_\gamma\) is \(|\gamma| = \gamma_1 + \cdots + \gamma_\ell\).

3.1 Characteristic matrices↩︎

For each \(\gamma \in \mathcal{D}^*\) we construct a characteristic matrix \(H_\gamma\) as follows: choose an orthonormal basis of the column space of \(E_\gamma\) and let \(H_\gamma\) be the \(|X| \times \mu_\gamma\) matrix whose columns are \(\sqrt{|X|}\) times these basis vectors. Then we have \[H_\gamma H_\gamma^\top = |X| E_\gamma,\] yields \[H_\gamma H_\gamma^\top = \bigl[ \Phi_\gamma(z_{\alpha(a,b)}) \bigr]_{a,b \in X}, \] where \(\alpha(a,b)\) denotes the unique index such that \((a,b) \in R_{\alpha(a,b)}\).

3.2 Code \(Y\) and its parameters↩︎

Let \(Y \subseteq X\) be a code with \(|Y| = M\). Define \[S = \{\alpha \in \mathcal{I}\setminus \{0\} : R_\alpha \cap Y^2 \neq \varnothing\},\] the set of non-identity relations that actually occur among pairs of elements of \(Y\), and set \(s = |S|\), the degree of \(C.\) For every \(\beta \in S\) choose a linear functional \(L_\beta : \mathbb{R}^\ell \to \mathbb{R}\) satisfying \[L_\beta(z_\beta) = 1, \qquad L_\beta(0) = 0.\] A natural choice is \(L_\beta(x) = \frac{\langle x, z_\beta \rangle}{\|z_\beta\|^2}\) (when \(z_\beta \neq 0\)).

3.3 Annihilator polynomial↩︎

Define the annihilator polynomial of \(Y\) by \[A(x) = M \prod_{\beta \in S} \bigl(1 - L_\beta(x)\bigr).\] Clearly \(A(0) = M\) and \(A(z_\beta) = 0\) for every \(\beta \in S\); its total degree is \(s\). Expand \(A\) in the multivariate basis \(\{\Phi_\gamma\}\): \[A(x) = \sum_{\gamma \in \mathcal{D}^*} a_\gamma \Phi_\gamma(x).\] Because \(\Phi_\gamma\) has total degree \(|\gamma|\), the coefficient \(a_\gamma\) vanishes whenever \(|\gamma| > s\). Hence we may write \[A(x) = \sum_{\gamma \in C} a_\gamma \Phi_\gamma(x), \quad\text{where}\quad C = \{\gamma \in \mathcal{D}^* : |\gamma| \le s\}.\]

3.4 Construction of the matrices \(G_s\) and \(\Delta\)↩︎

For each \(\gamma \in C\) let \(H_\gamma(Y)\) be the submatrix of \(H_\gamma\) consisting of the rows indexed by \(Y\); it is an \(M \times \mu_\gamma\) matrix. Concatenate these matrices horizontally: \[G_s = \bigl[\, H_\gamma(Y) \,\bigr]_{\gamma \in C} \qquad (\text{size } M \times M(s)),\] where \(M(s) = \sum_{\gamma \in C} \mu_\gamma\). Define a block diagonal matrix \(\Delta\) of order \(M(s)\) by \[\Delta = \bigoplus_{\gamma \in C} a_\gamma I_{\mu_\gamma},\] i.e. each block is the scalar \(a_\gamma\) times the identity matrix of size \(\mu_\gamma\).

With the notation above we have \[G_s \Delta G_s^\top = M I_M.\] Consequently \(M \le M(s) = \sum_{\gamma \in C} \mu_\gamma\).

Assume that \(M = M(s)\). Then

• The square matrix \(G_s\) of order \(M\) satisfies \(G_s G_s^\top = M I_M\).

• The annihilator polynomial \(A(x)\) equals \[Q_s(x) = \sum_{|\gamma| \le s} \Phi_\gamma(x),\] which is called the degree Wilson polynomial, and consequently every \(z_\beta\) (\(\beta \in S\)) is a zero of \(Q_s\).

4 Few distance codes↩︎

4.1 Distance degree of a code↩︎

Let \(\mathfrak{X} = (X, \{R_\alpha\}_{\alpha \in \mathcal{I}})\) be an \(\ell\)-variate \(Q\)-polynomial association scheme, with notation as in Section 3. Define a weighted distance function on the classes of the scheme by the formula \[d(\alpha) = w_1\alpha_1 + \cdots + w_\ell\alpha_\ell,\] where \(w_i>0\), \(\alpha = (\alpha_1,\dots,\alpha_\ell)\in\mathcal{I}\), and \(d(0)=0\). For a subset \(Y\subseteq X\), let \(M = |Y|\), \[S = \{\alpha\in\mathcal{I}\setminus\{0\}: R_\alpha\cap Y^2 \neq \varnothing\},\qquad D = \{d(\alpha):\alpha\in S\},\qquad s = |D|.\] We call \(s\) the distance degree of the code \(Y\).

4.2 Construction of the annihilator polynomial↩︎

Set \(f(x)=w_1x_1+\cdots+w_\ell x_\ell\), then \(f(z_\alpha)=d(\alpha)\) for every \(\alpha\in\mathcal{I}\). Form the univariate polynomial \[P(t)=\prod_{d\in D}\left(1-\frac{t}{d}\right),\] which satisfies \(P(0)=1\) and \(P(d)=0\) for all \(d\in D\). Define the annihilator polynomial of \(Y\) by \[A(x)=M\,P(f(x))=M\prod_{d\in D}\left(1-\frac{f(x)}{d}\right).\] Then \(A(0)=M\), \(A(z_\beta)=0\) for every \(\beta\in S\), and \(\deg A = s\).

4.3 Expansion and the matrices \(G_s\), \(\Delta\)↩︎

Expand \(A\) in the multivariate basis \(\{\Phi_\gamma\}\): \[A(x)=\sum_{\gamma\in\mathcal{D}^*} a_\gamma\Phi_\gamma(x).\] Because \(\Phi_\gamma\) has total degree \(|\gamma|=\gamma_1+\cdots+\gamma_\ell\), the coefficient \(a_\gamma\) vanishes when \(|\gamma|>s\). Hence we may write \[A(x)=\sum_{\gamma\in C} a_\gamma\Phi_\gamma(x),\qquad C=\{\gamma\in\mathcal{D}^*:|\gamma|\le s\}.\] Set \(M(s)=\sum_{\gamma\in C}\mu_\gamma\). For each \(\gamma\in C\), let \(H_\gamma(Y)\) be the submatrix of the characteristic matrix \(H_\gamma\) consisting of the rows indexed by \(Y\), it is an \(M\times\mu_\gamma\) matrix. Concatenate these matrices horizontally: \[G_s = [H_\gamma(Y)]_{\gamma\in C} \qquad (\text{size } M\times M(s)).\] Define a block diagonal matrix \(\Delta\) of order \(M(s)\) by \[\Delta = \bigoplus_{\gamma\in C} a_\gamma I_{\mu_\gamma}.\]

With the notation above we have \[G_s\Delta G_s^\top = M I_M.\] Consequently \(M \le M(s)\).

Analogously to Theorem [Thm4463] we obtain the following theorem.

Assume that the code \(Y\) attains the bound, i.e. \(M = M(s)\). Then

• The square matrix \(G_s\) satisfies \(G_s G_s^\top = M I_M\).

• The annihilator polynomial equals \[Q_s(x)=\sum_{|\gamma|\le s}\Phi_\gamma(x),\] which is called the distance Wilson polynomial, and consequently every point \(z_\beta\) (\(\beta\in S\)) is a zero of \(Q_s\).

4.4 Additive codes↩︎

We first recall the classical definition of the external distance \(s'\) introduced by Delsarte [18]: For a code \(C\) under the Hamming metric, the external distance \(s'\) serves as an upper bound on the covering radius [13] of \(C\), and can be derived from the distance distribution of the code. In the case where \(C\) is linear, \(s'\) is the number of non-zero weights in the orthogonal dual code \(C^\perp\).

In WMAS, we define the dispersion function [11], denoted by \(\Pi(e)\), as the number of elements \(i\) satisfying \(0 \leq d(i) \leq e\), and \(e\) is the packing radius [13]. In metric schemes, this simplifies to \(\Pi(e) = e + 1\).

We then introduce a generalized external distance, denoted \(\mu\), which is designed to extend the concept to less regular metrics (such as the Lee metric or modular distance) [13]. This new parameter is defined as: \[\mu = s' - \Pi(e) + e + 1,\] where \(s'\) is the classical external distance and \(e\) is the packing radius. In metric schemes, since \(\Pi(e) = e + 1\), the formula reduces to \(\mu = s'\), recovering the standard definition of external distance in such settings. Recall [12] that a distance is graphical if for every pair \(x,y\) with \(d(x,y)>1,\) there is a \(z\) such \(d(x,z)=d(x,y)-1,\) and \(d(z,y)=1.\)

Let \((X, R)\) be a WMAS for the distance function \(d\). Assume the distance is graphical and \((X, R)\) is a translation scheme. If \(Y\) is a subgroup of \(X\) with \(s\) distances, then \[|Y| \leq \sum_{d(i) \leq \mu'} v_i,\] where \(v_i\) is the valency of the \(i\)-th relation of the scheme, and \(\mu'= s - \Pi(e') + e' + 1,\) is the generalized external distance of \(Y^\perp.\)

Call a code \(Y\) with \(s\) distances satisfying \(|Y| = M(s)\) Generalized Hadamard code (GH for short). In the following result we derive a strong necessary existence condition for GH codes.

A translation association scheme is called self-dual if it is isomorphic to its dual in the sense of [1]. In a self-dual translation scheme, the valencies coincide with the multiplicities of the primitive idempotents, i.e., \(v_i = \mu_i\) for all \(i\). See the appendix for properties and constructions of self-dual translation schemes.

With the assumptions above, if the scheme \((X,R)\) is self-dual, then \(|Y| \leq M(\mu ').\) If \(|Y| = M(s)\), then \(\Pi(e') = e' + 1\) and \(Y^\perp\) is a perfect code with covering radius \(e'.\)

For a WMAS, define its range of metricity as the largest integer \(e\) less than the class number such that \(\Pi(e)=e+1\). We have computed it for several WMAS. If the scheme is not metric it is usually very small.

• In the Lee scheme \(L(n,q)\) we have if \(q\ge 4,\) the bound \(\Pi(e) >e + 1,\) for all \(e\ge 2.\) Thus linear GH codes must be duals of perfect one-error correcting codes. Conjecturally, only the duals of the codes of section \(4.4.1\) for q prime.

• In the homogeneous metric scheme over \(\mathbb{Z}_{2^k}\) (\(k\ge 2\)), relations are indexed by triples \((\pi_U,\pi_V,\pi_S)\) with quasi-distance \(d=\pi_U+\pi_V+2\pi_S\). One finds \(\Pi(0)=1\) and \(\Pi(1)=3>2\), therefore the range is \(0\) (no nontrivial perfect code radius).

• In the \(q\)-ary Johnson scheme \(J_q(w,n)\) (\(q\ge 3\), \(0<w\le n/2\)), relations are indexed by ordered pairs \((i,j)\) with \(i\ge j\) and distance \(d=i+j\). The piecewise closed form yields \(\Pi(0)=1\), \(\Pi(1)=2\), \(\Pi(2)=4\), so the range is \(1\).

• In the sum rank scheme with \(t\) blocks, when \(t=1\) (rank metric) we have \(\Pi(e)=e+1\) for all \(e\), the range is the class number. For \(t\ge 2\), as long as \(e\le\min_j n_j\), \(\Pi(e)=\binom{e+t}{t}\) [14]. Then \(\Pi(0)=1\) and \(\Pi(1)=t+1>2\), hence the range is \(0\).

• In the mixed alphabet scheme, for \(k=1\) (classical Hamming scheme) the range is the class number. For \(k\ge 2\) and \(e\le\min_j n_j\) we have \(\Pi(e)=\binom{e+k}{k}\) [14], giving \(\Pi(0)=1\) and \(\Pi(1)=k+1>2\), thus the range is \(0\).

• In the NRT scheme, for \(r=1\) (Hamming scheme) , the range is the class number. For \(r\ge 2\), a direct count shows \(\Pi(0)=1\), \(\Pi(1)=2\), \(\Pi(2)=4>3\), therefore the range is \(1\).

4.5 Perfect codes↩︎

To illustrate the inequality \(M \le M(s)\) of Lemma [Four2], motivated by Corollary 1, we consider some codes obtained as duals of perfect codes. The first two are linear codes in the Lee metric, and the next one is a \(1\)-perfect mixed code.

4.5.1 1-perfect Lee codes↩︎

Let \(q = 2n+1\) and let \(C_n\) be the code over \(\mathbb{Z}_q\) generated by \([1,2,\dots,n]\). Its size is \(M = q\). In the length-\(n\) Lee scheme each coordinate takes Lee values \(0,1,\dots,n\). Primitive idempotents are indexed by multi-indices \(\gamma = (\gamma_1,\dots,\gamma_n)\) with \(\gamma_i\in\{0,1,\dots,n\}\); their multiplicities satisfy \(\mu_\gamma = \prod_{i=1}^n \mu(\gamma_i)\), where \(\mu(0)=\mu(n)=1\) and \(\mu(k)=2\) for \(1\le k\le n-1\).

Magma experiments suggest that the number of distinct non-zero Lee weights of \(C_n\) is \(s = \tau(q)-1\), where \(\tau(q)\) denotes the number of positive divisors of \(q\). We can prove this conjecture in following two cases. Let \(q = 2n+1\) be an odd prime and let \(C\) be the linear code over \(\mathbb{Z}_q\) generated by \([1,2,\dots,n]\). Then all non-zero codewords of \(C\) have the same Lee weight, hence the number of distinct non-zero Lee weights is \(1\).

We now give a proof for the general case. Let \(q=2n+1\) be an odd integer, and let \(C\) be the linear code over \(\mathbb{Z}_q\) generated by \([1,2,\dots,n]\), Then the number of distinct non-zero Lee weights is \(\tau(q)-1\), where \(\tau(q)\) denotes the number of positive divisors of \(q\).

Together with the prime case, we obtain uniformly that for every odd \(q = 2n+1\), the number of distinct non-zero Lee weights of \(C_n\) equals \(s = \tau(q)-1\), where \(\tau(q)\) is the number of positive divisors of \(q\). And we have the following situation.

• If \(q\) is prime, then \(\tau(q)=2\) and \(s=1\). The multi-indices with \(|\gamma|\le 1\) are the zero vector and the \(n\) unit vectors. Their multiplicities are \(1\) and \(2\), respectively, whence \[M(1) = 1 + 2n = q = M,\] i.e., equality holds.

• If \(q\) is composite, then \(s>1\). The set of multi-indices with \(|\gamma|\le s\) strictly contains the \(1+2n\) terms above, so \(M(s) > M\).

Thus for every \(n\) we have \(M \le M(s)\), with equality exactly when \(q\) is prime (i.e., when \(2n+1\) is prime).

4.5.2 Length-\(2\) perfect codes in the Lee metric↩︎

Let \(q = 2t^2+2t+1\) and let \(C_t\) be the code over \(\mathbb{Z}_q\) generated by \([1,2t+1]\). Its size is \(M = q\). Here \(d = \frac{q-1}{2} = t^2+t\) and Magma experiments suggest the following result. Let \(t\) be a positive integer, \(q = 2t^{2}+2t+1\), and let \(C\) be the linear code over \(\mathbb{Z}_q\) generated by \([1, 2t+1]\), Then \(C\) is self-dual, and the number of distinct non-zero Lee weights of \(C\) is \[s = \frac{t^{2}+t}{2}.\]

For length \(2\) a multi-index is \(\gamma = (a,b)\) with \(0\le a,b\le d\) and multiplicity \(\mu(a,b)=\mu(a)\mu(b)\). The quantity \(M(s)\) is the sum of \(\mu(a,b)\) over all pairs with \(a+b\le s\).

• For \(t=1\) we have \(d=2\), \(s=1\). The admissible pairs are \((0,0)\), \((1,0)\), \((0,1)\) with multiplicities \(1,2,2\), so \[M(1) = 1+2+2 = 5 = M.\]

• For \(t=2\) we have \(d=6\), \(s=3\). Enumerating the ten pairs with \(a+b\le 3\) yields \(M(3)=25\), while \(M=13\); hence the inequality is strict.

• For larger \(t\) we have \(s \sim t^2/2\). The number of integer pairs with \(a,b\ge0\) and \(a+b\le s\) is \(\frac{(s+1)(s+2)}{2}\sim s^2/2\). Because \(s<d\) for all \(t\ge1\), every pair with \(a>0,b>0\) contributes multiplicity \(4\); boundary pairs (\(a=0\) or \(b=0\)) contribute \(2\) or \(1\). Hence \[M(s) \sim 4\cdot\frac{s^2}{2}=2s^2\sim \frac{t^4}{2},\] whereas \(M \sim 2t^2\). Consequently \(M(s)\gg M\) for sufficiently large \(t\), so the inequality is strict.

Thus for every \(t\ge1\) we have \(M\le M(s)\), with equality only for \(t=1\).

To illustrate the geometric structure of the perfect Lee code, Figure 1 shows the Lee ball (\(L^1\) ball) of radius \(t=2\) centered at the origin in \(\mathbb{Z}_{13}^2\). It consists of all integer lattice points whose Manhattan distance from the origin is at most \(t\). This ball contains exactly \(q=13\) points (black dots) and lies completely in the free domain, i.e., it does not overlap with any other ball in the perfect tiling of the torus \(\mathbb{Z}_{13}^2\).

4.5.3 A \(1\)-perfect mixed code↩︎

Let \(\mathbb{F}_8 = \mathbb{F}_2^3\) and consider the subspaces \[\begin{align} &\mathcal{T}_1 = \{000,\;110,\;011,\;101\},\quad \mathcal{T}_2 = \{000,\;100\},\\ &\mathcal{T}_3 = \{000,\;010\},\quad \mathcal{T}_4 = \{000,\;001\},\quad \mathcal{T}_5 = \{000,\;111\}. \end{align}\] Then \(\{\mathcal{T}_i\setminus\{0\}\}_{i=1}^5\) is a partition of \(\mathbb{F}_8^*\). By [24], the code \[C = \Bigl\{(c_1,\dots,c_5)\in\prod_{i=1}^5\mathcal{T}_i : \sum_{i=1}^5 c_i = 0 \text{ in } \mathbb{F}_8\Bigr\}\] is a \(1\)-perfect mixed code.

The size of \(C\) is \(|C| = 8\). The non-zero codewords consist of six words of weight \(3\) (when \(c_1\neq 0\)) and one word of weight \(4\) (when \(c_1=0\) and all later coordinates are non-zero). Hence the set of non-zero distances is \(D = \{3,4\}\) and the distance degree is \(s = |D| = 2\).

The ambient space \(\prod_{i=1}^5 \mathcal{T}_i\) is a direct product of five complete‑graph association schemes. Its relations are indexed by vectors \(\gamma = (\gamma_1,\dots,\gamma_5)\in\{0,1\}^5\), where \(\gamma_i=1\) indicates that the \(i\)‑th coordinate is non-zero. The multiplicity (rank of the primitive idempotent) is \[\mu(\gamma) = 3^{\gamma_1},\] since \(\mu_1^{(1)}=3\), \(\mu_1^{(i)}=1\) for \(i\ge2\), and \(\mu_0^{(i)}=1\) for all \(i\).

For \(s=2\), set \[M(s) = \sum_{|\gamma|\le 2}\mu(\gamma),\qquad |\gamma| = \sum_{i=1}^5\gamma_i.\] Summation by \(|\gamma|\) yields:

• \(|\gamma| = 0\): \(1\) term, \(\mu = 1\);

• \(|\gamma| = 1\): \(\gamma_1 = 1\) (\(1\) term, \(\mu = 3\)) and \(\gamma_1 = 0\) (\(\binom{4}{1} = 4\) terms, \(\mu = 1\)) \(\rightarrow\) \(3 + 4 = 7\);

• \(|\gamma| = 2\): \(\gamma_1 = 1\) (\(\binom{4}{1} = 4\) terms, \(\mu = 3\)) \(\rightarrow\) \(12\); \(\gamma_1 = 0\) (\(\binom{4}{2} = 6\) terms, \(\mu = 1\)) \(\rightarrow\) \(6\); total \(18\).

Thus \(M(s) = 1+7+18 = 26\). We obtain \(|C| = 8 \le 26 = M(s)\), confirming the inequality.

The \(1\)-perfect mixed code is self-dual in the mixed alphabet scheme, but [18] does not hold because the scheme requires stronger metric conditions. Hence \(M(s)=26 > |C|=8\), and the bound is not tight.

5 Some multivariate Q-polynomial schemes↩︎

To illustrate the wide applicability of the bound obtained in Section \(4\), we now examine several well-known association schemes [14] that are known to be multivariate \(Q\)-polynomial. For each of them we verify that the linear relation \(f(z_\alpha)=d(\alpha)\) holds–typically because the point \(z_\alpha\) can be identified with the index vector \(\alpha\) itself. All schemes discussed below but one are translation invariant, which guarantees that they are \(Q\)-multivariate whenever they are \(P\)-multivariate. The exception is the \(q\)-ary Johnson scheme which is known to be \(Q\)-bivariate for other reasons.

5.1 Homogeneous metric scheme over \(\mathbb{Z}_{2^k}\)↩︎

The alphabet \(\mathbb{Z}_{2^k}\) is partitioned into four subsets: the zero set \(Z\), the unit group \(U\), the ideal \(S=\langle2^{k-1}\rangle\), and the set \(V=\langle2\rangle\setminus S\). For a vector difference one counts the numbers of coordinates falling into each of these subsets, leading to an index \(\alpha=(\pi_U,\pi_V,\pi_S)\). The homogeneous distance is \(d_{\text{hom}}(\alpha)=\pi_U+\pi_V+2\pi_S\). The association scheme is \(4\)-variate. With weights \(w_U=1,w_V=1,w_S=2\) and \(f(x)=x_U+x_V+2x_S\) we obtain \(f(z_\alpha)=d_{\text{hom}}(\alpha)\) when we take \(z_\alpha=\alpha\).

5.2 \(q\)-ary Johnson scheme \(J_q(w,n)\)↩︎

For \(q\ge 3\) and \(0<w<2\), let \(X\) be the set of all vectors of length \(n\) over an alphabet of size \(q\) with exactly \(w\) non-zero coordinates. The \(q\)-ary Johnson scheme is \(2\)-variate. Its relations are indexed by pairs \(\alpha=(i,j)\) where \(i,j\) are defined by \(e(x,y)=w-i\) and \(n(x,y)=w-j\). The Hamming distance between two such vectors equals \(d(\alpha)=i+j\). Choosing \(w_1=w_2=1\) and \(f(x)=x_1+x_2\), we have \(f(z_\alpha)=i+j=d(\alpha)\) with \(z_\alpha=(i,j)\).

5.3 Lee scheme \(L(n,q)\)↩︎

Let \(q\ge 2\) and set \(s=\lfloor q/2\rfloor\). The Lee scheme on \(\mathbb{Z}_q^n\) has its relations indexed by vectors \(\alpha=(k_1,\dots,k_s)\in\mathbb{N}^s\) with \(\sum\limits_{i=1}^s k_i\le n\); here \(k_i\) counts the coordinates of a vector whose Lee composition has value \(\pm i\). The Lee distance of a relation of type \(\alpha\) is \(d_L(\alpha)=\sum\limits_{i=1}^s i\,k_i\). Taking the weights \(w_i=i\) and the linear function \(f(x)=\sum\limits_{i=1}^s i\,x_i\), we have \(f(z_\alpha)=\sum\limits_{i=1}^s\,\alpha_i = d_L(\alpha)\) because in the Lee scheme the points \(z_\alpha\) can be taken as the vector \(\alpha\) itself. Hence the required condition is satisfied.

5.4 Sum-rank scheme↩︎

Consider the space \(\bigoplus_{j=1}^t \mathbb{F}_q^{n_j\times m_j}\) with \(n_j\le m_j\) and the sum-rank distance \(d_{\text{srk}}(\alpha)=\sum_{j=1}^t k_j\), where \(\alpha=(k_1,\dots,k_t)\) and \(k_j\) is the rank of the \(j\)-th matrix block. With the trivial weights \(w_j=1\) and \(f(x)=\sum\limits_{j=1}^t x_j\), we have \(f(z_\alpha)=\sum\limits_{j=1}^t k_j = d_{\text{srk}}(\alpha)\) because \(z_\alpha\) can again be identified with \(\alpha\).

5.5 Mixed alphabet scheme↩︎

Let the alphabet be a Cartesian product \(\prod_{j=1}^k \mathbb{Z}_{p_j}\) and let the Hamming distance be used. The corresponding association scheme is the direct product \(\bigotimes_{j=1}^k H(n_j,p_j)\), it is \(k\)-variate \(Q\)-polynomial scheme. Its relations are indexed by \(\alpha=(s_1,\dots,s_k)\) where \(s_j\) is the number of error positions in the \(j\)-th block, and the distance is \(d_H(\alpha)=\sum\limits_{j=1}^k s_j\). Choosing \(w_j=1\) and \(f(x)=\sum\limits_{j=1}^k x_j\) gives \(f(z_\alpha)=\sum\limits_{j=1}^k s_j = d_H(\alpha)\) with \(z_\alpha=\alpha\).

5.6 NRT scheme↩︎

For fixed integers \(r,n\) and alphabet size \(q\), the NRT space \(\mathcal{Q}^{r,n}\) consists of vectors of length \(rn\) partitioned into \(n\) blocks of length \(r\). The NRT scheme is \(r\)-variate \(Q\)-polynomial. Its relations are indexed by \(\alpha=(\lambda_1,\dots,\lambda_r)\) where \(\lambda_i\) counts the number of blocks whose rightmost non-zero entry is in position \(i\). The NRT distance of such a relation is \(d_{\text{NRT}}(\alpha)=\sum_{i=1}^r i\,\lambda_i\). Taking weights \(w_i=i\) and \(f(x)=\sum i\,x_i\), we have \(f(z_\alpha)=\sum i\,\lambda_i = d_{\text{NRT}}(\alpha)\) because \(z_\alpha\) can be taken as \(\alpha\).
All the multivariate \(Q\)-polynomial schemes discussed above satisfy the existence of points \(z_\alpha\) such that \(f(z_\alpha)=d(\alpha)\). Consequently, the Delsarte bound \(|Y|\le M(s)\) holds for any such scheme.

6 Designs↩︎

In the next two subsections we study in turn, each of these two concepts of designs, and give, in each case, an analogue of the Rao bound, and necessary conditions for this bound to be met.

6.1 t-designs↩︎

Let \((X,\{R_i\}_{i\in\mathcal{D}})\) be a multivariate WMAS, and let \(Y\subseteq X\) be a \(t\)-design. Set \(e=\lfloor t/2\rfloor\) and \(\mu'_e=\sum_{d(i)\le e}\mu_i\), Then \[|Y|\;\ge\;\mu'_e.\]

We call \((6.1)\) the distance Rao bound, and the sum polynomial \(\Psi_e(z)=\sum_{d(i)\le e}\Phi_{i}(z)\) distance Wilson polynomial.

We shall now examine the duality, with respect to a given inner product in the context of a translation scheme with its groundset \(X\) an abelian group. If the code \(Y\) is a subgroup of \(X\), then it is clear that the subset \(Y^0\) of \(X\) defined by \[Y^0 = \{x' \in X \mid \langle x, x' \rangle = 1,\;\forall x \in Y\}\] is itself a subgroup of \(X\); it will be called the dual of \(Y\) in \(X\). We will need the following result about duality in [1].

The dual of \(Y^0\) is \(Y\) itself and \(Y^0\) is isomorphic to the factor group \(X/Y\).

We can now make the formal duality between tight designs and perfect codes concrete through the following result. Let \((X,R)\) be a self-dual translation multivariate \(Q\)-polynomial scheme, and let \(Y \subseteq X\) be an additive code with dual code \(Y^0\), Then \(Y\) is an \(e\)-perfect code if and only if \(Y^0\) is a distance tight t-design of order \(e\).

6.2 T-designs↩︎

Let \((X,\{R_\alpha\}_{\alpha\in\mathcal{I}})\) be a multivariate \(Q\)-polynomial WMAS with primitive idempotents \(\{E_\gamma\}_{\gamma\in\mathcal{D}^*}\), ranks \(\mu_\gamma = \operatorname{rank}(E_\gamma)\) and associated polynomials \(\Phi_\gamma\) whose total degree is denoted by \(|\gamma|\). For a subset \(T \subseteq \mathcal{D}^*\), define \[e(T) = \max\bigl\{ m \geq 0 : \{\gamma \in \mathcal{D}^* : 0 < |\gamma| \leq 2m\} \subseteq T \bigr\},\] and set \(e(T) = -1\) if no non‑negative integer \(s\) satisfies the inclusion. Let \(\mu'_{e(T)} = \sum_{\substack{\gamma \in \mathcal{D}^* \\ |\gamma| \leq e(T)}} \mu_\gamma.\) Then for any \(T\)-design \(Y \subseteq X\) we have \[|Y| \geq \mu'_{e(T)}.\]

We call \((6.2)\) the degree Rao bound, and the sum polynomial \(\Psi_e(x) = \sum_{|\gamma| \leq e} \Phi_\gamma(x)\) the degree Wilson polynomial.

6.3 Four important examples↩︎

The following examples translate the abstract notion of a \(t\)-design in a multivariate \(Q\)-polynomial scheme into concrete combinatorial structures, laying the groundwork for further discussions.

6.3.1 q-ary Johnson scheme \(J_q(w,n)\)↩︎

In the nonbinary Johnson scheme \(J_{q}(w,n)\), the primitive idempotents \(E_{ij}\) are indexed by \[L = \{(i,j) \mid 0 \le j \le i \le w,\; i-j \le m\}, m = \min\{w,n-w\}.\] If the non-zero indices in \(L\) are ordered lexicographically, the natural distance function corresponds to this ordering of the idempotents, so that the distance classes satisfying \(0 < d(\cdot) \le t\) are exactly those indexed by \[T_{t} = \{(i,j) \in L \mid i \le t,\; j \le t\} \setminus \{(0,0)\}.\] Consequently, a \(t\)-design is precisely a \(T_{t}\)-design. By [10], a \(t\)-design in \(J_{q}(w,n)\) is exactly a \((t,t)\)-design.

According to [10], a subset \(Y \subseteq X\) is a \((t,t)\)-design if for every \(t\)-subset \(\mathcal{R} \subseteq \{1,\dots,n\}\) and every \(\omega \in \{1,\dots,q-1\}^{t}\), \[m_{\mathcal{R},\mathcal{R}}(Y,\omega) = \bigl|\{\, y \in Y \mid \mathcal{R} \subseteq \overline{y},\; y_{i} = \omega_{i} \text{ for } i \in \mathcal{R} \,\}\bigr|\] is a constant \(\lambda\). In matrix form: arrange the vectors of \(Y\) as a \(|Y| \times n\) array, choose any \(t\) columns, and consider the subarray of rows that are non-zero in all these \(t\) columns; the condition states that every \(t\)-tuple from \(\{1,\dots,q-1\}\) appears equally often in this subarray.

6.3.2 Sum-rank scheme↩︎

In the sum-rank scheme \(\mathcal{S} = \bigotimes_{j=1}^{\ell} \Omega(n_j, m_j)\), the product of \(\ell\) bilinear forms schemes over \(\mathbb{F}_q\) with \(n_j \le m_j\), let the vertex set be \(X = \bigoplus_{j=1}^{\ell} \mathbb{F}_q^{n_j \times m_j}\) and define the distance between two \(\ell\)-tuples of matrices as the sum of the ranks of their componentwise differences. The primitive idempotents of \(\mathcal{S}\) are indexed by \(\ell\)-tuples \(\mathbf{k} = (k_1, \dots, k_\ell)\) with \(0 \le k_j \le n_j\). If the non-zero indices are ordered by the sum of their components \(|\mathbf{k}| = \sum_{j=1}^{\ell} k_j\), the natural distance function corresponds to this ordering, so that the distance classes satisfying \(0 < d(\cdot) \le t\) are exactly those indexed by \[T_t = \{\mathbf{k} \mid 1 \le |\mathbf{k}| \le t\}.\] Consequently, a subset \(Y \subseteq X\) is a \(t\)-design if and only if it is a \(T_t\)-design.

Applying [20] to this product scheme and the combinatorial characterization of \(t\)-designs in each bilinear forms scheme [25], one obtains the following interpretation: \(Y\) is a \(t\)-design precisely when, for every choice of subspaces \(U_1 \subseteq \mathbb{F}_q^{n_1}, \dots, U_\ell \subseteq \mathbb{F}_q^{n_\ell}\) such that \(\sum\limits_{j=1}^\ell \dim(U_j) \le t\), and for any fixed bilinear forms \(f_j : U_j \times \mathbb{F}_q^{m_j} \to \mathbb{F}_q\) (\(1 \le j \le \ell\)), the number of elements \((F_1, \dots, F_\ell) \in X\) whose restriction to \(U_j \times \mathbb{F}_q^{m_j}\) equals \(f_j\) for all \(j\) depends only on the dimension vector \(\mathbf{u} = (\dim(U_1), \dots, \dim(U_\ell))\) and not on the particular subspaces or forms chosen.

6.3.3 Mixed alphabet scheme↩︎

In the mixed alphabet scheme \(H(n_1,q_1) \otimes H(n_2,q_2) \otimes \dots \otimes H(n_m,q_m)\), the primitive idempotents are indexed by multi-indices \(\mathbf{j} = (j_1, j_2, \dots, j_m)\), where \(0 \le j_i \le n_i\). If the non-zero indices are ordered by the sum of their components \(|\mathbf{j}| = \sum\limits_{i=1}^m j_i\), then the natural distance function corresponds to this ordering, so that the distance classes satisfying \(0 < d(\cdot) \le t\) are exactly those indexed by \[T_t = \{\mathbf{j} \mid 1 \le |\mathbf{j}| \le t\}.\] Consequently, a subset \(Y \subseteq X\) is a \(t\)-design if and only if it is a \(T_t\)-design. By [20], a \(t\)-design in the product Hamming scheme is equivalent to a mixed-level orthogonal array of strength \(t\).

If the vectors of \(Y\) are written as a \(|Y| \times (n_1 + n_2 + \dots + n_m)\) matrix whose columns are naturally partitioned into \(m\) blocks, the \(i\)-th block containing \(n_i\) columns with entries from \(\{0,1,\dots,q_i-1\}\), then the combinatorial condition reads: for any choice of \(t\) columns, every \(t\)-tuple that can possible occur in these columns appears equally often among the rows of \(Y\).

6.3.4 NRT scheme↩︎

In the NRT scheme (the ordered Hamming scheme \(\vec{H}(s,\ell,q)\)) [7], [9], the primitive idempotents are indexed by shapes \(e = (e_0, \dots, e_\ell)\) with \(\sum_{i=0}^\ell e_i = s\). The natural distance is the height \(h(e) = \sum_{i=0}^\ell i e_i\). If the non-zero indices are ordered by this height, then the distance classes satisfying \(0 < d(\cdot) \le t\) are exactly those indexed by \[T_t = \{\, e = (e_0, \dots, e_\ell) \mid \sum_{i=0}^\ell e_i = s,\; 1 \le h(e) \le t \,\}.\] Consequently, a subset \(Y \subseteq X\) is a \(t\)-design if and only if it is a \(T_t\)-design. By [9], a \(t\)-design in the NRT scheme is equivalent to an ordered orthogonal array of strength \(t\).

The combinatorial condition reads as follows: write the vectors of \(Y\) as a \(|Y| \times s\ell\) matrix whose columns are partitioned into \(s\) blocks of size \(\ell\). For any choice of non-negative integers \(t_1, \dots, t_s\) with \(\sum_{j=1}^s t_j = t\) and \(t_j \le \ell\), select the first \(t_j\) columns from the \(j\)-th block, then every \(t\)-tuple from \(\mathbb{F}_q\) appears equally often among the rows of the resulting \(|Y| \times t\) subarray.

7 Conclusion and open problems↩︎

In this paper we have strived to extend from Q-polynomial to multivariate Q-polynomial association schemes the main results of [1] on codes of given degree and designs of given strength. Thus, to be specific, we have generalized Sections 5.3.1 and 5.3.2 of that thesis. A result that has resisted our efforts is [1] that requires multivariate analogues of Christoffel numbers. The theory of multivariate Gaussian quadrature is very involved and difficult to apply [26]. This is the first problem open by this work. An intriguing question is the combinatorial interpretation of designs in the association schemes corresponding to the homogeneous and Lee distance [8], [11].

Appendix: Self-dual association schemes↩︎

Direct Product of Association Schemes↩︎

Following the approach in [20] we describe direct products. For \(1 \leq i \leq m\), let \((Y_i, \mathcal{A}_i)\) be a \(d_i\)-class association scheme with adjacency matrices \(\mathcal{A}_i\). The direct product of these schemes [20] is the association scheme \[(X, \mathcal{A}) = (Y_1, \mathcal{A}_1) \otimes (Y_2, \mathcal{A}_2) \otimes \cdots \otimes (Y_m, \mathcal{A}_m)\] defined by \[X = Y_1 \times Y_2 \times \cdots \times Y_m\] and \[\mathcal{A} = \left\{ \bigotimes_{i=1}^m M_i : M_i \in \mathcal{A}_i, 1 \leq i \leq m \right\},\] where \[\bigotimes_{i=1}^m M_i = M_1 \otimes M_2 \otimes \cdots \otimes M_m\] is the \(m\)-fold Kronecker product of matrices. The fact that this always gives an association scheme follows from the properties \[\left( \bigotimes_{i=1}^m M_i \right) \left( \bigotimes_{i=1}^m N_i \right) = \bigotimes_{i=1}^m (M_i N_i), \left( \bigotimes_{i=1}^m M_i \right) \circ \left( \bigotimes_{i=1}^m N_i \right) = \bigotimes_{i=1}^m (M_i \circ N_i)\] of the Kronecker product. From the first identity, it follows that the \(P\)-matrix for this product scheme is given by the Kronecker product of the \(P\)-matrices for the component schemes \((Y_i, \mathcal{A}_i)\). Similarly, the second change-of-basis matrix \(Q\) for the product scheme is given by \(\bigotimes_{i=1}^m Q_i\) where \(Q_i\) is the \(Q\)-matrix for the \(i^{\text{th}}\) component scheme.

The direct product of finitely many self-dual association schemes is also self-dual.

Characterization of self-dual translation schemes↩︎

Let \(X\) be a finite abelian group. Assume \(X\) is the groundset of a translation association scheme with \(s\) classes. Then there exists a partition \(P_0=\{0\},P_1,\dots,P_s\) of \(X\) such that the relations of the scheme are given by \(x R_i y\) iff \(x-y \in P_i.\) We are going to characterize the partitions that turn \((X,R)\) into a self-dual association scheme. Denote the indicator function of \(P_i \in P\) by \(\chi_i\): \[\chi_i(x) = \begin{cases} 1 & \text{if } x \in P_i, \\ 0 & \text{if } x \notin P_i. \end{cases}\] Let \(\mathbb{C}^X\) denote the family of all complex functions \(X \to \mathbb{C}\). For any given partition \(P\), we define \[L(P) \triangleq \{ f \in \mathbb{C}^X : f(x) = \sum_{i=0}^s f_i \chi_i(x) \},\] where \(f_i \in \mathbb{C}, i = 0, 1, \dots, s\).

[27] reveals that the essence of the self-duality of a translation association scheme is the invariance of the partition \(P\) under the Fourier transform: \((X,R)\) is self-dual iff \(P\) is an \(F\)-partition. On the other hand, [22] tells us when the translation association scheme generated by the \(G\)-orbits partition ( for some group \(G\) acting on \(X\)) is self-dual. The existence of an adjoint map actually guarantees that the orbit partition satisfies Fourier invariance, and the orbit partition in [22] is a special type of \(F\)-partition in the sense of [27].

The reference [8] constructs another class of \(F\)-partitions that are not generated by group orbits (e.g., the four-block partition for the homogeneous weight) and verifies that they also satisfy the Fourier invariance condition of [27]. Therefore, [8] and [22] provide two different sources of \(F\)-partitions: the former comes from group actions with an adjoint map, the latter from coarsest constructions for concrete metrics.

Examples↩︎

We now illustrate five well-known families of translation schemes, all of which are self-dual.

1. Hamming scheme \(\mathrm{H}(n,q)\). The Hamming scheme \(\mathrm{H}(n,q)\) enjoys the MacWilliams relations on the complete weight enumerator. It is well-known to be self-dual [18].

2. Mixed alphabet scheme. A mixed alphabet scheme is essentially a direct product of Hamming schemes \(\mathrm{H}(n,q)\) over possibly different \(n\)’s and \(q\)’s. As each factor is self-dual, the product remains self-dual by Proposition [dp].

3. Lee scheme. By [8] the Lee scheme is self-dual.

4. Homogeneous metric scheme. Similarly, the homogeneous metric scheme is self-dual by [8] .

5. Sum-rank scheme. The sum-rank scheme can be viewed as a direct product of bilinear forms schemes. The bilinear forms scheme is self-dual by [25], and self-duality is preserved under direct products, consequently the sum-rank scheme is self-dual by Proposition [dp].

Acknowledgement:↩︎

The authors are grateful to Eiichi Bannai for helpful discussions.

References↩︎

---

1. The work of MS is supported by the National Natural Science Foundation of China under Grant 12471290↩︎