1 Introduction

In coding theory, one of the classical problems is to determine A(n, d), the maximum size of a binary (n, d) code with length n and minimum distance at least d. The (Hamming) distance distribution of a code is considered since the MacWilliams identities provide a linear relation between the distance distribution and its transform [27]. With this linear relation, the maximum possible size of a code can be formulated as a linear programming problem. Delsarte showed that the transform of the distance distribution is nonnegative and used linear programming techniques to derive upper bounds on A(n, d) [11].

Schrijver considered the distance relations among triplets of codewords and derived positive-semidefinite relations based on the Terwilliger algebra of Hamming scheme [32]. Thus one can formulate a semidefinite program (SDP) on the maximum possible size of a code and derive a semidefinite programming bound on the size of a binary code. Several linear programming upper bounds on A(n, d) are improved since Schrijver’s semidefinite constraints imply Delsarte’s linear inequalities [32] by diagonalizing certain positive semidefinite matrices derived from Schrijver’s semidefinite constraints in the Bose–Mesner algebra.

This method was later extended to nonbinary codes by Gijswijt et al. [17]. Gijswijt et al. further studied the distance relations among quadruples of codewords and generalized Schrijver’s SDP [16], called quadruple SDP, which improved many upper bounds for A(n, d). Although an SDP based on the distance relations of m-tuple codewords for any m is studied, an SDP based on quadruple distances has already many variables, leading to high computation complexity.

On the other hand, there are several known linear constraints for binary codes, including Delsarte’s inequalities [11], the ones derived by Best [5] and Mounits et al. [25], which can be used to strengthen linear programming or semidefinite programming bounds on A(n, d). Moreover, Kim and Toan proved additional linear constraints on the variables of Schrijver’s SDP and improved upper bounds on A(18, 8) and A(19, 8) [19]. Then, \(A(18, 8) = 64\) has later been settled by Östergård [28] by using a computer-aided search.

The A(n, d) problem can be regarded as finding the maximum number of an independent set of a graph as follows. Let E be a graph with \(2^n\) vertices corresponding to all the binary vectors of length n. There is an edge between two binary vectors if their Hamming distance is less than d. Now an (n, d) code corresponds to an independent set of E. Consequently, Delsarte’s linear programming bound can be viewed an upper bound on the independent number of E. Moreover, this bound can be extended to serve as an upper bound on the independent number an arbitrary graph [31]. Based on this connection, Laurent gave a hierarchy for semidefinite programming bounds on A(n, d) and proposed strengthened bounds [21], which improve bounds on A(20, 8) and A(25, 6).

Upper bounds for several related coding problems in various spaces can also be derived using semidefinite programming techniques. For instance, Bachoc and Vallentin studied SDPs for codes in Hamming balls, projective spaces and spherical codes (kissing number problems) [2, 8]. Barg and Yu also used semidefinite programming techniques to obtain better upper bounds for spherical two-distance sets and equiangular lines [9, 10].

In this paper, we would like to study Schrijver’s SDP and derive additional semidefinite constraints. One can define a split distance distribution of a code, and derive a split version of Delsarte’s inequalities, which provide subtler linear constraints [33]. Recently, split Hamming weight distributions and their MacWilliams identities have been studied in various quantum codes [1, 20, 22]. It has been demonstrated that linear programming bounds on quantum codes can be improved with additional constraints from split MacWilliams identities [20].

Inspired by the effects of split distance or weight distributions in linear programming, we would like to study a similar notion in Schrijver’s SDP. Consider a partition of the support of a code with two subsets. We define a split Terwilliger algebra with respect to the partition. Similar to the derivation of Schrijver’s semidefinite constraints, we show that this split Terwilliger algebra can be block-diagonalized to derive finer positive-semidefinite constraints. Moreover, we show that these split Schrijver’s semidefinite constraints also imply corresponding split Delsarte’s inequalities, and hence they are natural generalizations of Schrijver’s constraints. Together with Schrijver’s semidefinite constraints and the known linear constraints in the literature, we have a strengthened SDP on A(n, d). In particular, we improve the semidefinite programming bound on A(18, 4) to 6551, while the previously known upper bound is 6552, by linear programming with Delsarte’s inequalities and Best’s inequalities [5]. The number has not been updated since more than four decades ago [4, 7]. The numerical error of this SDP program can be pessimistically estimated from its dual SDP as suggested by Gijswijt [14]. Using this method, we are able to verify that \(A(18,4) \le 6551\).

One of our semidefinite constraint \(R_{s}\) can be derived from the quadruple SDP. It is not clear whether the other semidefinite constraint on \(R_{s}'\) obtained by a split Terwilliger algebra is included in the constraints of the quadruple SDP as well. However, in our experiment, we are able to improve the bound A(18, 4) over the quadruple SDP in [16].

All the results and proofs can be generalized to a split Terwilliger algebra on m subsets of a partition with \(m \le n\) (called m-split Terwilliger algebra), from which we may derive more additional positive-semidefinite constraints. However, this m-split Terwilliger induces an SDP with \(O((\frac{n}{m})^{3m})\) variables and may not be practical in implementation with large m.

Finally, we mention m-split Terwilliger algebras for the Hamming scheme, which might allow us to apply our method to other association schemes. To implement an SDP program, one of the key points is to block diagonalize the algebra in use and Gijswijt has developed a general method to handle this problem [15]. Gijswijt’s method was refined and extended to nonbinary codes by Litjens et al. [23]. Moreover, the method can be further generalized to the groups of the form \((G^{n_{1}} \rtimes S_{n_{1}}) \times \cdots \times (G^{n_{m}} \rtimes S_{n_{m}})\) with \(\sum _{i = 1}^{m}n_{m} = n\) and \(S_{n_{i}}\) are symmetric groups [29]. Together with those approaches, one can calculate the block diagonalization formula of split Terwilliger algebras in various types of codes, such as constant-weight codes and nonbinary codes with Hamming or Lee distances.

The paper is organized as follows. We introduce the Terwilliger algebra of the Hamming scheme and Schrijver’s SDP. In Sect. 3 we define a split Terwilliger algebra and derive semidefinite constraints. Then we provide our SDP together with the linear constraints in the literature in Sect. 4. A generalization of the method on m-split Terwilliger algebra is given in Sect. 5. Finally, we conclude our work in Sect. 6.

2 Terwilliger algebra and Schrijver’s SDP

Let \({{\mathcal {P}}}\) be the power set of \(\left\{ 1, \dots , n\right\} \). A binary code C is a subset of \({{\mathcal {P}}}\). For \(X,Y \in {{\mathcal {P}}}\), denote

$$\begin{aligned} X\Delta Y= \left\{ a\in \{1,\dots ,n\}: a\in (X {\setminus } Y) \cup (Y {\setminus } X) \right\} . \end{aligned}$$

Let \(|S |\) denote the size of a set \(S \in {{\mathcal {P}}}\). Hence the (Hamming) distance of X and \(Y \in {{\mathcal {P}}}\) is \(|X \Delta Y |\). The distance distribution of the code C is

$$\begin{aligned} A_{j} = \frac{1}{|C |} \sum _{x \in C}\{ y \in C: |x \Delta y |= j\} \end{aligned}$$
(1)

for \(j=0,\dots , n\). The minimum distance d of C is the minimum Hamming distance of two distinct elements in C and hence

$$\begin{aligned} d= \min \{j>0: A_j>0\}. \end{aligned}$$

Note that for \(|C |\le 1\), its minimum distance is defined to be \(\infty \). C is said to be an (n, d) code if C has minimum distance d and length n. See more details about codes in [27].

We review the Terwilliger algebra of the Hamming scheme [3, 34, 35]. Let G be the group of all distance-preserving automorphisms of \({{\mathcal {P}}}\). Consider the action of G on \({{\mathcal {P}}} \times {{\mathcal {P}}}\) defined by \(g(X, Y) = (g X, g Y)\) for \(g \in G\) and \((X, Y) \in {{\mathcal {P}}} \times {{\mathcal {P}}}\) with orbits \({{\mathcal {O}}}_{1}, \dots , {{\mathcal {O}}}_{m}\) for some m. For each \({{\mathcal {O}}}_{u}\), we define a \(|{{\mathcal {P}}} |\times |{{\mathcal {P}}} |\) matrix \(M_{{{\mathcal {O}}}_{u}}\), indexed by the elements in \({{\mathcal {P}}}\), as

$$\begin{aligned} \left( M_{{{\mathcal {O}}}_{u}}\right) _{X, Y} = \left\{ \begin{aligned}&1,{} & {} \text{ if } (X, Y) \in {{\mathcal {O}}}_{u};\\ {}&0,{} & {} \text{ otherwise. } \end{aligned} \right. \end{aligned}$$

Observe that (X, Y) and \((U, V)\in {{\mathcal {P}}} \times {{\mathcal {P}}}\) belong to the same orbit if and only if there is an automorphism \(g\in G\) such that \(gX = U\) and \(gY = V\), that is, if and only if \(|X |= |U |,\) \(|Y |= |V |,\) and \(|X \Delta Y |= |U \Delta V |\). Thus, \(M_{{{\mathcal {O}}}_{u}}\) can be rewritten as

$$\begin{aligned} \left( M_{i, j}^{t}\right) _{X, Y} = \left\{ \begin{aligned}&1,{} & {} \text{ if } |X |= i, |Y |= j, |X \cap Y |= t;\\ {}&0,{} & {} \text{ otherwise, } \end{aligned} \right. \end{aligned}$$

where each orbit \({{\mathcal {O}}}_{u}\) is represented by some (i, j, t) for \(i, j, t \in \{0, \dots , n\}\) with \(i+j-2t \in \{0, \dots , n\}\). Let \({{\mathcal {A}}}_{n}\) be the collection of all linear combinations of \(\left\{ M_{i, j}^{t}\right\} \) over the complex field \(\mathbb {C}\). Then \(\mathcal{A}_{n}\) is closed under matrix multiplication and adjoint. Moreover, \({{\mathcal {A}}}_{n}\) is a \(\mathbb {C}^{*}\)-algebra, called the Terwilliger algebra of the Hamming scheme. \({{\mathcal {A}}}_{n}\) is finitely generated with dimension \(\left( {\begin{array}{c}n+3\\ 3\end{array}}\right) \).

Schrijver described a block diagonal formula for the Terwilliger algebra of the Hamming scheme.

Theorem 1

[32, Theorem 1] There is an isomorphism from \({{\mathcal {A}}}_{n}\) to \(\bigoplus _{k = 0}^{\lfloor \frac{n}{2} \rfloor } \mathbb {C}^{(n-2k+1) \times (n-2k+1)}\) that maps \(A = \sum _{i, j, t}x_{i, j}^{t}M_{i, j}^{t} \in {{\mathcal {A}}}_{n}\) to \(\bigoplus _{k = 0}^{\lfloor \frac{n}{2} \rfloor } B_{k}\), where

$$\begin{aligned} B_{k} = \left( \sum _{t} \left( {\begin{array}{c}n-2k\\ i-k\end{array}}\right) ^{-\frac{1}{2}} \left( {\begin{array}{c}n-2k\\ j-k\end{array}}\right) ^{-\frac{1}{2}} \beta _{i, j, k}^{t} x_{i, j}^{t} \right) _{i, j = k}^{n-k} \end{aligned}$$

with

$$\begin{aligned} \beta _{i, j, k}^{t} = \sum _{u = 0}^{n} (-1)^{u-t} \left( {\begin{array}{c}u\\ t\end{array}}\right) \left( {\begin{array}{c}n-2k\\ u-k\end{array}}\right) \left( {\begin{array}{c}n-k-u\\ i-u\end{array}}\right) \left( {\begin{array}{c}n-k-u\\ j-u\end{array}}\right) . \end{aligned}$$

The formula says \({{\mathcal {A}}}_{n}\) as the direct sum of matrices. Therefore, we can represent the elements of \({{\mathcal {A}}}_{n}\) on a computer with a minimal memory.

Now, Schrijver’s semidefinite constraints for a nontrivial code C [32] can be derived as follows. Consider the action of G. Let \(\Pi = \{\pi \in G \mid \emptyset \in \pi (C)\}\) and \(\Pi ' = \{\pi \in G \mid \emptyset \notin \pi (C)\}\). Let \(\chi ^{\pi (C)}\) be the incidence vector (as a column vector) of \(\pi (C)\) indexed by \({{\mathcal {P}}}\). Define \( |{{\mathcal {P}}} |\times |{{\mathcal {P}}} |\) matrices

$$\begin{aligned}&R = \frac{1}{|\Pi |} \sum _{\pi \in \Pi } \chi ^{\pi (C)} (\chi ^{\pi (C)})^{T}, \\&R' = \frac{1}{|\Pi ' |} \sum _{\pi \in \Pi '} \chi ^{\pi (C)} (\chi ^{\pi (C)})^{T}. \end{aligned}$$

It is obvious that R and \(R'\) are positive semidefinite. Let

$$\begin{aligned} x_{i, j}^{t} = \frac{1}{|C |\left( {\begin{array}{c}n\\ i-t, j-t, t\end{array}}\right) } \lambda _{i, j}^{t}, \end{aligned}$$

where \(\left( {\begin{array}{c}n\\ a, b, c\end{array}}\right) = \frac{n!}{a!b!c!}\) for \(a, b, c \ge 0\) with \(a+b+c \le n\), and

$$\begin{aligned} \lambda _{i, j}^{t} =&|\{ (X, Y, Z) \in C^{3} : |X \Delta Y |= i, |X \Delta Z |= j, |(X \Delta Y) \cap (X \Delta Z)|= t\}|, \end{aligned}$$

for each \(i, j, t \in \{0, \dots , n\}\) with \(i-t \ge 0\), \(j-t \ge 0\), and \(i+j-2t \le n\). \(\lambda _{i, j}^{t}\) counts the number of triple codewords in C satisfying certain distance relations. The following proposition says that \(R,R'\in {{\mathcal {A}}}_n\).

Proposition 2

[32, Proposition 1]

$$\begin{aligned}&R = \sum _{i, j, t} x_{i, j}^{t} M_{i, j}^{t},\\ {}&R' = \frac{|C |}{2^{n}-|C |}\sum _{i, j, t}\left( x_{i+j-2t, 0}^{0}-x_{i, j}^{t}\right) M_{i, j}^{t}. \end{aligned}$$

By Theorem 1, R and \(R'\) are positive semidefinite if and only if for \(k = 0, \dots , \lfloor \frac{n}{2} \rfloor \), the following matrices

$$\begin{aligned}&\left( \sum _{t} \left( {\begin{array}{c}n-2k\\ i-k\end{array}}\right) ^{-\frac{1}{2}} \left( {\begin{array}{c}n-2k\\ j-k\end{array}}\right) ^{-\frac{1}{2}} \beta _{i, j, k}^{t} x_{i, j}^{t} \right) _{i, j = k}^{n-k}, \end{aligned}$$
(2)
$$\begin{aligned}&\left( \sum _{t} \left( {\begin{array}{c}n-2k\\ i-k\end{array}}\right) ^{-\frac{1}{2}} \left( {\begin{array}{c}n-2k\\ j-k\end{array}}\right) ^{-\frac{1}{2}} \beta _{i, j, k}^{t} \left( x_{i+j-2t, 0}^{0}-x_{i, j}^{t}\right) \right) _{i, j = k}^{n-k} \end{aligned}$$
(3)

are positive semidefinite. Schrijver also showed that \(x_{i,j}^t\) satisfy the following constraints.

Proposition 3

[32] Let C be a code with length n and minimum distance at least d. Then \(x_{i, j}^{t}\)’s corresponding to C satisfy the following constraints:

$$\begin{aligned} \begin{array}{cl} \text{(i) } &{} x_{0, 0}^{0} = 1;\\ \text {(ii)} &{} 0 \le x_{i, j}^{t} \le x_{i, 0}^{0};\\ \text {(iii)} &{} x_{i,0}^{0} + x_{j,0}^{0} \le 1+x_{i, j}^{t};\\ \text {(iv)} &{} x_{i, j}^{t} = x_{i', j'}^{t'} \text{ if } (i, j, i+j-2t) \text{ is } \text{ a } \text{ permutation } \text{ of } (i', j', i'+j'-2t');\\ \text {(v)} &{} x_{i, j}^{t} = 0 \text{ if } \{i, j, i+j-2t\} \cap \{1, \dots , d-1\} \ne \emptyset ; \end{array} \end{aligned}$$
(4)

Also, we have

$$\begin{aligned} |C |= \sum _{i}\left( {\begin{array}{c}n\\ i\end{array}}\right) x_{i, 0}^{0}. \end{aligned}$$

Note that \(\left\{ \left( {\begin{array}{c}n\\ i\end{array}}\right) x_{i, 0}^{0}\right\} \) is the distance distribution of C. Constraints (i) and (iv) are from the definition directly. Consider \(|X |= i\) and \(|Y |= j\) and then we have

$$\begin{aligned}&\left( R\right) _{X,X} = x_{i, i}^{i} = x_{i, 0}^{0}, \quad \left( R\right) _{X,Y} = x_{i, j}^{t}. \end{aligned}$$

The first inequality of Constraint (ii) follows because of the non-negativity of \(\lambda _{i,j}^t\) and the second inequality is because R is positive semidefinite and a diagonal element of a positive semidefinite matrix would dominate its row entries. Constraint (iii) can be similarly derived from \((R)_{X,X}'\ge (R)_{X,Y}'\) and (iv). To see this, we consider \(|X |= i\) and \(|Y |=j'= i+j-2t\) at \(t'= i-t\). Then

$$\begin{aligned}&(R')_{X, X} = x_{0, 0}^{0} - x_{i, 0}^{0}, \\&(R')_{X, Y} = x_{i+j'-2t', 0}^{0} - x_{i, j'}^{t'}= x_{j, 0}^{0} - x_{i, i+j-2t}^{i-t}= x_{j, 0}^{0} - x_{i, j}^{t}, \end{aligned}$$

where \(x_{i, i+j-2t}^{i-t}= x_{i, j}^{t}\) is because of (iv). Constraint (v) is the requirement from the minimum distance of the code. To sum up, Schrijver’s SDP is as follows with variables \( x_{i, j}^{t} \in \mathbb {R}\):

$$\begin{aligned} \textrm{maximize}&\sum _{i}\left( {\begin{array}{c}n\\ i\end{array}}\right) x_{i, 0}^{0} \\ \mathrm{subject\ to\ }&\text{ positive } \text{ semidefiniteness } \text{ of } (2) \text{ and } (3)\\&(4). \end{aligned}$$

3 Split Terwilliger algebra of the Hamming scheme

In this section, we consider split distance distribution on a partition of \(\{1, \dots , n\}\) with two subsets \(T_{1}\) and \(T_{2}\) such that \(T_{1}\cap T_{2}=\emptyset \), \(|T_{1}|= n_{1}\), \(|T_{2}|= n_{2}\), and \(n_1+n_2=n\).

Let \(G_{u}\) be the group of all distance-preserving automorphisms of the power set of \(T_{u}\), for \(u = 1, 2\). We consider the group \(G_{1} \times G_{2}\) acting on \({{\mathcal {P}}}\) by

$$\begin{aligned} (g, h) \cdot X = g(X \cap T_{1}) \cup h(X \cap T_{2}) \end{aligned}$$

for \((g, h) \in G_{1} \times G_{2}\) and \(X \in {{\mathcal {P}}}\). Observe that an orbit of \(G_{1} \times G_{2}\) on \({{\mathcal {P}}} \times {{\mathcal {P}}}\) can be similarly represented by \((i, j, t, i', j', t')\) with \(i, j, t \in \{0, \dots , n_{1}\}\), \(i', j', t' \in \{0, \dots , n_{2}\}\), \(i+j-2t \in \{0, \dots , n_{1}\}\) and \(i'+j'-2t' \in \{0, \dots , n_{2}\}\) and we define \(|{{\mathcal {P}}} |\times |{{\mathcal {P}}}|\) matrices \(M_{i, j, i', j'}^{t, t'}\) by

$$\begin{aligned} \left( M_{i, j, i', j'}^{t, t'}\right) _{X,Y} = \left\{ \begin{aligned}&1,{} & {} \begin{aligned}&\text{ if } |X \cap T_{1}|= i, |X \cap T_{2} |= i',\\ {}&|Y \cap T_{1}|= j, |Y \cap T_{2}|= j', \\ {}&\text{ and } |X \cap Y \cap T_{1}|= t, |X \cap Y \cap T_{2}|= t'; \end{aligned}\\ {}&0,{} & {} \text{ otherwise. } \end{aligned} \right. \end{aligned}$$

Let \({{\mathcal {A}}}_{n_{1}, n_{2}}\) be the collection of all linear combinations of \(\left\{ M_{i, j, i', j'}^{t, t'}\right\} \) over the complex field \(\mathbb {C}\). One can verify that \({{\mathcal {A}}}_{n_{1}, n_{2}}\) is closed under matrix multiplication and adjoint, and \({{\mathcal {A}}}_{n_{1}, n_{2}}\) forms a \(\mathbb {C}^{*}\)-algebra, which we call a 2-split Terwilliger algebra of the Hamming scheme. By definition, we have the following lemma.

Lemma 4

The algebra \({{\mathcal {A}}}_{n_{1}, n_{2}}\) is isomorphic to the algebra \({{\mathcal {A}}}_{n_{1}} \otimes {{\mathcal {A}}}_{n_{2}}\), where \(\otimes \) is the matrix tensor product.

Proof

We denote \(M_{i, j}^{n_{1}, t}\)’s and \(M_{i', j'}^{n_{2}, t'}\)’s as the generators of \({{\mathcal {A}}}_{n_{1}}\), \({{\mathcal {A}}}_{n_{2}}\), respectively, for \(i, j, t \in \{0, \dots , n_{1}\}\), \(i', j', t' \in \{0, \dots , n_{2}\}\). For \(X, Y \in {{\mathcal {P}}}\),

$$\begin{aligned} \left( M_{i, j, i', j'}^{t, t'}\right) _{X, Y} = 1 \end{aligned}$$
(5)

if and only if \(|X \cap T_{1}|= i\), \(|Y \cap T_{1}|= j\), \(|X \cap Y \cap T_{1}|= t\) and \(|X \cap T_{2}|= i'\), \(|Y \cap T_{2}|= j'\), \(|X \cap Y \cap T_{2}|= t'\).

Suppose that the generators of \({{\mathcal {A}}}_{n_{1}}\) and \({{\mathcal {A}}}_{n_{2}}\) are indexed by the power sets \({{\mathcal {P}}}_{1}\), \({{\mathcal {P}}}_{2}\) of \(T_{1}\) and \(T_{2}\), respectively. We observe that (5) is equivalent to

$$\begin{aligned} \left( M_{i, j}^{n_{1}, t}\right) _{X\cap T_{1}, Y\cap T_{1}} = 1 { \text{ and } } \left( M_{i', j'}^{n_{2}, t'}\right) _{X\cap T_{2}, Y\cap T_{2}} = 1. \end{aligned}$$

Also, the size of the matrix \(M_{i, j}^{n_{1}, t} \otimes M_{i', j'}^{n_{2}, t'}\) is equal to \(2^{n_{1}+n_{2}} \times 2^{n_{1}+n_{2}}\). Immediately, we have

$$\begin{aligned} M_{i, j, i', j'}^{t, t'} = M_{i, j}^{n_{1}, t} \otimes M_{i', j'}^{n_{2}, t'}, \end{aligned}$$
(6)

since the right (left) hand side of (6) forms a set of generators for \({{\mathcal {A}}}_{n_{1}, n_{2}}\) (\({{\mathcal {A}}}_{n_{1}} \otimes {{\mathcal {A}}}_{n_{2}}\)). \(\square \)

As a consequence, we have a block-diagonal formula for the 2-split Terwilliger algebra of the Hamming scheme, which is an extension of the block-diagonal formula for the Terwilliger algebra of the Hamming scheme with the definition of tensor product. As in Schrijver’s decomposition of the Terwilliger algebra, this split decomposition is irreducible. By certain basic results from representation theory, \({{\mathcal {A}}}_{n_{1}, n_{2}}\) will be mapped to a direct sum of simple \({{\mathcal {A}}}_{n_{1}, n_{2}}\)-modules. Thus we have the following corollary.

Corollary 5

[32, equation (56)] There is an isomorphism from \({{\mathcal {A}}}_{n_{1}, n_{2}}\) to

$$\begin{aligned} \bigoplus _{k = 0}^{\left\lfloor \frac{n_{1}}{2} \right\rfloor } \bigoplus _{k' = 0}^{\left\lfloor \frac{n_{2}}{2} \right\rfloor } \mathbb {C}^{N_{k, k'} \times N_{k. k'}}, \end{aligned}$$

with \(N_{k, k'} = (n_{1}-2k+1)(n_{2}-2k'+1)\) that maps \(A = \sum _{i, j, i', j', t, t'}x_{i, j, i', j'}^{t, t'} M_{i, j, i', j'}^{t, t'}\) to

$$\begin{aligned} \bigoplus _{k = 0}^{\lfloor \frac{n_{1}}{2} \rfloor } \bigoplus _{k' = 0}^{\lfloor \frac{n_{2}}{2} \rfloor } {{\mathcal {B}}}_{k, k'}, \end{aligned}$$

where

$$\begin{aligned} {{\mathcal {B}}}_{k, k'} = \left( \sum _{t, t'} \alpha _{i, j, i', j'}^{k, n_{1}, n_{2}} \beta _{i, j, k}^{n_{1}, t} \beta _{i', j', k'}^{n_{2}, t'} x_{i, j, i', j'}^{t, t'} \right) _{((i, i'), (j, j')) = ((k, k'), (k, k'))}^{((n_{1}-k, n_{2}-k'), (n_{1}-k, n_{2}-k'))} \end{aligned}$$

with

$$\begin{aligned} \beta _{i, j, k}^{n_{l}, t} =&\sum _{u = 0}^{n_{l}} (-1)^{u-t} \left( {\begin{array}{c}u\\ t\end{array}}\right) \left( {\begin{array}{c}n_{l}-2k\\ u-k\end{array}}\right) \left( {\begin{array}{c}n_{l}-k-u\\ i-u\end{array}}\right) \left( {\begin{array}{c}n_{l}-k-u\\ j-u\end{array}}\right) , \end{aligned}$$

for \(l = 1, 2\) and

$$\begin{aligned} \alpha _{i, j, i', j'}^{k, n_{1}, n_{2}} = \left( {\begin{array}{c}n_{1}-2k\\ i-k\end{array}}\right) ^{-\frac{1}{2}} \left( {\begin{array}{c}n_{1}-2k\\ j-k\end{array}}\right) ^{-\frac{1}{2}} \left( {\begin{array}{c}n_{2}-2k'\\ i'-k'\end{array}}\right) ^{-\frac{1}{2}} \left( {\begin{array}{c}n_{2}-2k'\\ j'-k'\end{array}}\right) ^{-\frac{1}{2}}. \end{aligned}$$

Remark 6

The formula in Corollary 5 was provided by Schrijver in [32] to provide SDP constraints for a constant-weight code of weight w by choosing \(n_{1}=w\) and \(n_{2}=n-w\).

Now we can derive additional semidefinite constraints on a nontrivial code \(C\subset {{\mathcal {P}}}\) from the 2-split Terwilliger algebra of the Hamming scheme. Define

$$\begin{aligned} x_{i, j, i', j'}^{t, t'} = \frac{1}{|C|\left( {\begin{array}{c}n_{1}\\ i-t, j-t, t\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ i'-t', j'-t', t'\end{array}}\right) } \lambda ^{t, t'}_{i, j, i', j'}, \end{aligned}$$
(7)

where

$$\begin{aligned} \begin{aligned} \lambda ^{t, t'}_{i, j, i', j'} = |\{&(X, Y, Z) \in C^{3}: |(X \Delta Y)\cap T_{1}|= i, |(X \Delta Z)\cap T_{1}|= j, \\ {}&|((X \Delta Y)\cap (X \Delta Z))\cap T_{1}|= t,\\ {}&|(X \Delta Y)\cap T_{2}|= i', |(X \Delta Z)\cap T_{2}|= j',\\ {}&|((X \Delta Y)\cap (X \Delta Z))\cap T_{2}|= t' \}|, \end{aligned} \end{aligned}$$
(8)

for \(i, j, t \in \{0, \dots , n_{1}\}\), \(i', j', t' \in \{0, \dots , n_{2}\}\) with \(i-t \ge 0\), \(j-t \ge 0\), \(i+j-2t \le n_{1}\), \(i'-t' \ge 0\), \(j'-t' \ge 0\) and \(i'+j'-2t' \le n_{2}\). Also, the size of the code is

$$\begin{aligned} |C |=\sum _{a = 0}^{n} \sum _{i+i' = a} \left( {\begin{array}{c}n_{1}\\ i\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ i'\end{array}}\right) x_{i, 0, i', 0}^{0, 0}. \end{aligned}$$

Let \(\lambda _{a, b}^{c}\), \(x_{a, b}^{c}\) and \(M_{a, b}^{c}\) be defined as in Schrijver’s SDP in the previous section. From the definitions, we have the following identities:

$$\begin{aligned} \lambda _{a, b}^{c} =&\sum _{i+i' = a, j+j' = b, t+t' = c} \lambda _{i, j, i', j'}^{t, t'}, \end{aligned}$$
(9)
$$\begin{aligned} x_{a, b}^{c} =&\sum _{i+i' = a, j+j' = b, t+t' =c} \frac{\left( {\begin{array}{c}n_{1}\\ i-t, j-t, t\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ i'-t', j'-t', t'\end{array}}\right) }{\left( {\begin{array}{c}n\\ a-c, b-c, c\end{array}}\right) }x_{i, j, i', j'}^{t, t'}, \end{aligned}$$
(10)
$$\begin{aligned} M_{a, b}^{c} =&\sum _{i+i' = a, j+j' = b, t+t' = c} M_{i, j, i', j'}^{t, t'}. \end{aligned}$$
(11)

Consider the following two sets of automorphisms:

$$\begin{aligned}&\Pi _{\textrm{s}} = \{(\pi _{1}, \pi _{2}) \in G_{1} \times G_{2} \mid \emptyset \in (\pi _{1}, \pi _{2})(C)\},\\&\Pi _{\textrm{s}}' = \{(\pi _{1}, \pi _{2}) \in G_{1} \times G_{2} \mid \emptyset \notin (\pi _{1}, \pi _{2})(C)\}. \end{aligned}$$

Here the subscript \(\mathrm s\) stands for split. Similarly, we define

$$\begin{aligned}&R_{\textrm{s}} = \frac{1}{|\Pi _{\textrm{s}} |} \sum _{(\pi _{1}, \pi _{2}) \in \Pi _{\textrm{s}}} \chi ^{(\pi _{1}, \pi _{2})(C)} (\chi ^{(\pi _{1}, \pi _{2})(C)})^{T}, \\&R_{\textrm{s}}' = \frac{1}{|\Pi _{\textrm{s}}'|}\sum _{(\pi _{1}, \pi _{2}) \in \Pi _{\textrm{s}}'} \chi ^{(\pi _{1}, \pi _{2})(C)} (\chi ^{(\pi _{1}, \pi _{2})(C)})^{T}. \end{aligned}$$

One can immediately see that \(R_{\textrm{s}}\) and \(R_{\textrm{s}}'\) are positive semidefinite and they only depend on the action \(G_{1} \times G_{2}\) on C. Moreover, \(R_{\textrm{s}}\) and \(R_{\textrm{s}}'\) are elements of \({{\mathcal {A}}}_{n_{1}, n_{2}}\) as a consequence of the following proposition.

Proposition 7

$$\begin{aligned} \begin{aligned}&R_{\text {s}} = \sum _{i, j, i', j', t,t'} x_{i, j, i', j'}^{t, t'}M_{i, j, i', j'}^{t, t'},\\ {}&\begin{aligned} R_{\text {s}}' =&\frac{|C |}{2^{n}-|C|}\sum _{i, j, i', j', t,t'} \left( x_{i+j-2t, 0, i'+j'-2t', 0}^{0, 0}-x_{i, j, i', j'}^{t, t'}\right) M_{i, j, i', j'}^{t, t'}. \end{aligned} \end{aligned} \end{aligned}$$

Proof

Let \(X \in {{\mathcal {P}}}\). We define \(\Pi _{s}^{X} = \left\{ (\pi _{1}, \pi _{2}) \in \Pi _{1} \times \Pi _{2} \mid (\pi _{1}, \pi _{2})(X) = \emptyset \right\} \). For an element \((\pi _{1}, \pi _{2}) \in \Pi _{s}^{X}\), we can see \(\pi _{1}\) as a permutation of \(T_{1}\) and \(\pi _{2}\) as a permutation of \(T_{2}\). Hence, we have \(\left| \Pi _{s}^{X}\right| = n_{1} ! n_{2} !\). Define

$$\begin{aligned}&R_{s}^{X} = \frac{1}{|\Pi _{s}^{X} |} \sum _{(\pi _{1}, \pi _{2}) \in \Pi _{s}^{X}} \chi ^{(\pi _{1}, \pi _{2})(C)} \left( \chi ^{(\pi _{1}, \pi _{2})(C)}\right) ^{T}, \\ {}&\begin{aligned} \lambda ^{t, t', X}_{i, j, i', j'} = |\{&(Y, Z) \in C^{2} : |(X \Delta Y)\cap T_{1}|= i, |(X \Delta Z)\cap T_{1}|= j,\\ {}&|((X \Delta Y)\cap (X \Delta Z))\cap T_{1}|= t,\\ {}&|(X \Delta Y)\cap T_{2}|= i', |(X \Delta Z)\cap T_{2}|= j',\\ {}&|((X \Delta Y)\cap (X \Delta Z))\cap T_{2}|= t' \}|. \end{aligned} \end{aligned}$$

For \((\pi _{1}, \pi _{2}) \in \Pi _{s}^{X}\) and fixed \(i, j, t, i', j', t'\), observe that the number of 1’s in

$$\begin{aligned} \left( \chi ^{(\pi _{1}, \pi _{2})(C)} \left( \chi ^{(\pi _{1}, \pi _{2})(C)}\right) ^{T}\right) _{Y, Z} \end{aligned}$$

such that \(\left( M_{i, j, i', j'}^{t, t'}\right) _{Y, Z} = 1\) is \(\lambda ^{t, t', X}_{i, j, i', j'}\). There are \(\left( {\begin{array}{c}n_{1}\\ i-t, j-t, t\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ i'-t', j'-t', t'\end{array}}\right) \) such (Y, Z). Thus,

$$\begin{aligned} R_{s}^{X} = \sum _{i, j, i', j', t, t'} \frac{1}{\left( {\begin{array}{c}n_{1}\\ i-t, j-t, t\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ i'-t', j'-t', t'\end{array}}\right) } \lambda ^{t, t', X}_{i, j, i', j'} M_{i, j, i', j'}^{t, t'}. \end{aligned}$$

Next, we see that

$$\begin{aligned} R_{s} = \sum _{X \in C} \frac{R_{s}^{X}}{|C|}, \quad R_{s}' = \sum _{X \notin C} \frac{R_{s}^{X}}{|{{\mathcal {P}}} \setminus C |}, \end{aligned}$$

and

$$\begin{aligned} \sum _{X \in C} \lambda ^{t, t', X}_{i, j, i', j'} = \lambda ^{t, t'}_{i, j, i', j'}. \end{aligned}$$

Therefore,

$$\begin{aligned} \begin{aligned} R_{s} =&\sum _{X \in C} \frac{R_{s}^{X}}{|C |}\\ =&\frac{1}{|C |} \sum _{i, j, i', j', t, t'} \frac{1}{\left( {\begin{array}{c}n_{1}\\ i-t, j-t, t\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ i'-t', j'-t', t'\end{array}}\right) } \left( \sum _{X \in C} \lambda ^{t, t', X}_{i, j, i', j'}\right) M_{i, j, i', j'}^{t, t'}\\ =&\sum _{i, j, i', j', t, t'} \frac{\lambda ^{t, t'}_{i, j, i', j'}}{|C|\left( {\begin{array}{c}n_{1}\\ i-t, j-t, t\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ i'-t', j'-t', t'\end{array}}\right) } M_{i, j, i', j'}^{t, t'}\\ =&\sum _{i, j, i', j', t, t'} x_{i, j, i', j'}^{t, t'} M_{i, j, i', j'}^{t, t'}. \end{aligned} \end{aligned}$$

For \((Y, Z) \in C^{2}\) with \(|Y \Delta Z \cap T_{1}|= i+j-2t\), \(|Y \Delta Z \cap T_{2}|= i'+j'-2t'\). The number of \(X \in {{\mathcal {P}}}\) such that \(|(X \Delta Y)\cap T_{1}|= i, |(X \Delta Z)\cap T_{1}|= j, |((X \Delta Y)\cap (X \Delta Z))\cap T_{1}|= t, |(X \Delta Y)\cap T_{2}|= i', |(X \Delta Z)\cap T_{2}|= j', |((X \Delta Y)\cap (X \Delta Z))\cap T_{2}|= t'\) is \(\left( {\begin{array}{c}i+j-2t\\ i-t\end{array}}\right) \left( {\begin{array}{c}n_{1}-t-j+2t\\ t\end{array}}\right) \left( {\begin{array}{c}i'+j'-2t'\\ i'-t'\end{array}}\right) \left( {\begin{array}{c}n_{2}-i'-j'+2t'\\ t'\end{array}}\right) \).

Thus we have

$$\begin{aligned} \sum _{X \in {{\mathcal {P}}}} \lambda _{i, j, i', j'}^{t, t', X} =&\left( {\begin{array}{c}i+j-2t\\ i-t\end{array}}\right) \left( {\begin{array}{c}n_{1}-t-j+2t\\ t\end{array}}\right) \left( {\begin{array}{c}i'+j'-2t'\\ i'-t'\end{array}}\right) \\&\cdot \left( {\begin{array}{c}n_{2}-i'-j'+2t'\\ t'\end{array}}\right) \lambda _{i+j-2t, 0, i'+j'-2t', 0}^{0, 0}. \end{aligned}$$

Hence,

$$\begin{aligned} \begin{aligned} R_{s}' =&\sum _{X \in {{\mathcal {P}}} \setminus C} \frac{R_{s}^{X}}{2^{n}-|C |}\\ =&\frac{1}{2^{n}-|C |} \sum _{i, j, i', j', t, t'} \frac{1}{\left( {\begin{array}{c}n_{1}\\ i-t, j-t, t\end{array}}\right) \left( {\begin{array}{c}n{2}\\ i'-t', j'-t', t'\end{array}}\right) } \left( \sum _{X \in {{\mathcal {P}}} \setminus C} \lambda _{i, j, i', j'}^{t, t', X} \right) M_{i, j, i', j'}^{t, t'}\\ =&\frac{|C |}{2^{n}-|C |} \sum _{i, j, i', j', t, t'} \frac{1}{|C |\left( {\begin{array}{c}n_{1}\\ i-t, j-t, t\end{array}}\right) \left( {\begin{array}{c}n{2}\\ i'-t', j'-t', t'\end{array}}\right) }\\ {}&\cdot \left( \left( {\begin{array}{c}i+j-2t\\ i-t\end{array}}\right) \left( {\begin{array}{c}n_{1}-t-j+2t\\ t\end{array}}\right) \right. \left( {\begin{array}{c}i'+j'-2t'\\ i'-t'\end{array}}\right) \\ {}&\cdot \left( {\begin{array}{c}n_{2}-i'-j'+2t'\\ t'\end{array}}\right) \left. \lambda _{i+j-2t, 0, i'+j'-2t', 0}^{0, 0} - \lambda _{i, j, i', j'}^{t, t'} \right) M_{i, j, i', j'}^{t, t'}\\ =&\frac{|C |}{2^{n}-|C|} \sum _{i, j, i', j', t, t'} \left( \frac{\left( {\begin{array}{c}i+j-2t\\ i-t\end{array}}\right) \left( {\begin{array}{c}n_{1}-t-j+2t\\ t\end{array}}\right) \left( {\begin{array}{c}i'+j'-2t'\\ i'-t'\end{array}}\right) \left( {\begin{array}{c}n_{2}-i'-j'+2t'\\ t'\end{array}}\right) }{|C |\left( {\begin{array}{c}n_{1}\\ i-t, j-t, t\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ i'-t', j'-t', t'\end{array}}\right) } \right. \\&\quad \left. \cdot \lambda _{i+j-2t, 0, i'+j'-2t', 0}^{0, 0} - x_{i, j, i', j'}^{t, t'} \right) M_{i,j, i', j'}^{t, t'}. \end{aligned} \end{aligned}$$

Using the identities

$$\begin{aligned}&\left( {\begin{array}{c}n_{1}\\ i-t, j-t, t\end{array}}\right) ^{-1} \left( {\begin{array}{c}i+j-2t\\ i-t\end{array}}\right) \left( {\begin{array}{c}n_{1}-i-j+2t\\ t\end{array}}\right) = \left( {\begin{array}{c}n_{1}\\ i+j-2t\end{array}}\right) ^{-1} \text { and }\\&\left( {\begin{array}{c}n_{2}\\ i'-t', j'-t', t'\end{array}}\right) ^{-1} \left( {\begin{array}{c}i'+j'-2t'\\ i'-t'\end{array}}\right) \left( {\begin{array}{c}n_{2}-i'-j'+2t'\\ t'\end{array}}\right) = \left( {\begin{array}{c}n_{2}\\ i'+j'-2t'\end{array}}\right) ^{-1}, \end{aligned}$$

we have

$$\begin{aligned} \begin{aligned} R_{s}' =&\frac{|C|}{2^{n}-|C|}\! \sum _{i, j, i', j', t, t'}\! \left( \frac{1}{|C|\left( {\begin{array}{c}n_{1}\\ i+j-2t\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ i'+j'-2t'\end{array}}\right) } \!\lambda _{i+j-2t, 0, i'+j'-2t', 0}^{0, 0} - x_{i, j, i', j'}^{t, t'} \right) \! M_{i, j, i', j'}^{t, t'}\\ =&\frac{|C |}{2^{n}-|C|} \sum _{i, j, i', j', t, t'} \left( x_{i+j-2t, 0, i'+j'-2t', 0}^{0, 0}-x_{i, j, i', j'}^{t, t'}\right) M_{i, j, i', j'}^{t, t'}. \end{aligned} \end{aligned}$$

\(\square \)

Using Theorem 5 and the positive semidefiniteness of \(R_{\textrm{s}}\) and \(R_{\textrm{s}}'\), we have the following semidefinite constraints. For each \(k = 0, \dots , \left\lfloor \frac{n_{1}}{2} \right\rfloor \) and \(k' = 0, \dots , \left\lfloor \frac{n_{2}}{2} \right\rfloor \), the following matrices are positive semidefinite:

$$\begin{aligned}&\left( \sum _{t, t'} \alpha _{i, j, i', j'}^{k, n_{1}, n_{2}} \beta _{i, j, k}^{n_{1}, t} \beta _{i', j', k'}^{n_{2}, t'} x_{i, j, i', j'}^{t, t'} \right) _{((i, i'), (j, j')) = ((k, k'), (k, k'))}^{((n_{1}-k, n_{2}-k'), (n_{1}-k, n_{2}-k'))}, \end{aligned}$$
(12)
$$\begin{aligned}&\left( \sum _{t, t'} \alpha _{i, j, i', j'}^{k, n_{1}, n_{2}} \beta _{i, j, k}^{n_{1}, t} \beta _{i', j', k'}^{n_{2}, t'} (x_{i+j-2t, 0, i'+j'-2t', 0}^{0, 0} -x_{i, j, i', j'}^{t, t'}) \right) _{((i, i'), (j, j')) = ((k, k'), (k, k'))}^{((n_{1}-k, n_{2}-k'), (n_{1}-k, n_{2}-k'))}. \end{aligned}$$
(13)

Proposition 8

Let C be a code with length n and minimum distance at least d. Then \(x_{i,j,i',j'}^{t,t'}\) corresponding to C satisfy the following linear constraints: for \(i, j, t, a, b, c \in \{0, \dots ,\) \(n_{1}\}\) and \(i', j', t', a', b', c' \in \{0, \dots , n_{2}\}\),

$$\begin{aligned} \begin{array}{cl} \text{(i) } &{} x_{0, 0, 0, 0}^{0, 0} = 1; \\ \text{(ii) } &{} 0 \le x_{i, j, i', j'}^{t, t'} \le x_{i, 0, i', 0}^{0, 0}; \\ \text{(iii) } &{} x_{i, 0, i', 0}^{0, 0} + x_{0, j, 0, j'}^{0, 0} \le 1 + x_{i, j, i', j'}^{t, t'}; \\ \text{((iv)) } &{} x_{i, j, i', j'}^{t, t'} = x_{a, b, a', b'}^{c, c'} \text{ if } ((i, i'), (j, j'), (i+j-2t, i'+j'-2t')); \\ &{} \text{ is } \text{ a } \text{ permutation } \text{ of } ((a, a'), (b, b'), (a+b-2c, a'+b'-2c')), \\ \text{((v)) } &{} x_{i, j, i', j'}^{t, t'} = 0 \text{ if } \{i+i', j+j', (i+i')+(j+j')-2(t+t')\} \cap \{1, \dots , d-1\} \ne \emptyset . \end{array} \end{aligned}$$
(14)

Constraints (i) and (iv) come from the definition of \(x_{i, j, i', j'}^{t, t'}\). Constraints (ii) and (iii) are because of the positive semidefiniteness of R and \(R'\). Constraint (iv) is the requirement of the minimum distance.

The split distance distribution of C with respect to the partition \(\left\{ T_1,T_2\right\} \) is \(\left\{ A_{i, j}\right\} \), where

$$\begin{aligned} A_{i, j} = \frac{1}{|C |} |\{(a, b) \in C \times C \mid |a \Delta b \cap T_{1}|= i, |a \Delta b \cap T_{2}|= j\}|. \end{aligned}$$

It has been shown that generalized Delsarte’s inequalities on \(\left\{ A_{i,j}\right\} \) hold [33].

Corollary 9

[33, Generalized Delsarte’s inequalities]

$$\begin{aligned} \sum _{i, j} A_{i, j} K_{p}^{n_{1}}(i) K_{q}^{n_{2}}(j) \ge 0, \end{aligned}$$
(15)

for \(p = 0, \dots , n_{1}\) and \(q = 0, \dots , n_{2}\), where

$$\begin{aligned} K_{k}^{n}(x) = \sum _{y=0}^k (-1)^{y} \left( {\begin{array}{c}x\\ y\end{array}}\right) \left( {\begin{array}{c}n-x\\ k-y\end{array}}\right) \end{aligned}$$

is the binary Krawchuk polynomial.

We can show that the generalized Delsarte’s inequalities on \(\{A_{i,j}\}\) can be derived from the positive semidefiniteness of \(R_s\) and \(R_s'\) in Proposition 7.

Lemma 10

If \(R_s\) and \(R_s'\) are positive semidefinite, then (15) holds.

Proof

Define a matrix

$$\begin{aligned} D_{s} = R_{s} + \frac{2^{n}-|C |}{|C |}R_{s}'= \sum _{i, j, i', j', t, t'} x_{i+j-2t, 0, i'+j'-2t', 0}^{0, 0} M_{i, j, i', j'}^{t, t'}, \end{aligned}$$

which is a nonnegative linear combination of positive semidefinite matrices \(R_{s}\) and \(R_{s}'\), and hence is positive semidefinite. We can rewrite \(D_{s}\) as

$$\begin{aligned} D_{s} = \sum _{k, k'} x_{k, 0, k', 0}^{0, 0} M_{k, k'}, \end{aligned}$$

where

$$\begin{aligned} \left( M_{k, k'}\right) _{X, Y} = \left\{ \begin{aligned}&1,{} & {} \text{ if } |X \Delta Y \cap T_{1}|= k, |X \Delta Y \cap T_{2}|= k';\\ {}&0,{} & {} \text{ otherwise. } \end{aligned} \right. \end{aligned}$$

Define matrices \(D_{a}^{m}\) for \(0\le a,m\le n\) with entries

$$\begin{aligned} \left( D_{a}^{m}\right) _{X, Y} = \left\{ \begin{aligned}&1,{} & {} \text{ if } |X \Delta Y|= a;\\ {}&0,{} & {} \text{ otherwise, } \end{aligned} \right. \end{aligned}$$

for indexes X, Y in the power set of \(\{1, \dots , m\}\). Notice that \(\left\{ D_{a}^{m}\right\} \) forms a basis for the Bose–Mesner algebra of the Hamming scheme with length m. Using the isomorphism in Lemma 4, one finds that \(M_{k, k'}\) is isomorphic to \(D_{k}^{n_{1}} \otimes D_{k'}^{n_{2}}\). By [11], we learn that Krawchuk polynomials \(K_{a}^{m}(p)\) are eigenvalues of the matrices \(\{D_{a}^{m}\}\) for \(0 \le p \le m\) and, moreover, the matrices \(\{M_{k, k'}\}\) are commutative. Consequently, to diagonalize \(D_{s}\), we simply have to diagonalize \(M_{k, k'}\) and the semidefinite conditions become

$$\begin{aligned} \sum _{k, k'} x_{k, 0, k', 0}^{0, 0} K_{k}^{n_{1}}(p) K_{k'}^{n_{2}}(q) \ge 0, \end{aligned}$$
(16)

for \(p \in \{0, \dots , n_{1}\}\) and \(q \in \{0, \dots , n_{2}\}\). Recall that the Krawchuk polynomial obeys the following symmetric relation [27]:

$$\begin{aligned} \left( {\begin{array}{c}m\\ a\end{array}}\right) K_{b}^{m}(a) = \left( {\begin{array}{c}m\\ b\end{array}}\right) K_{a}^{m}(b). \end{aligned}$$

Thus the inequality (16) becomes

$$\begin{aligned} \sum _{k, k'} \left( {\begin{array}{c}n_{1}\\ k\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ k'\end{array}}\right) x_{k, 0, k', 0}^{0, 0} \left( {\begin{array}{c}n_{1}\\ p\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ q\end{array}}\right) K_{k}^{n_{1}}(p) K_{k'}^{n_{2}}(q) \ge 0, \end{aligned}$$

which implies the result. \(\square \)

Let \({{\mathcal {N}}}_{k}\) be the collection of codes \(S \subset {{\mathcal {P}}}\) with minimum distance at least d and \(|S |\le k\). Schrijver’s SDP can be generalized by considering the k-points relation of codewords. The generalized version is as follows [16].

Proposition 11

[16, Generalized SDP bound] For \(S \in {{\mathcal {N}}}_{k}\), define

$$\begin{aligned} {{\mathcal {N}}}(S) = \{S' \subset {{\mathcal {P}}}: S \subset S', |S |+ 2|S' \setminus S |\le k \}. \end{aligned}$$

Let \(x = \{x_{i}\}_{i \in {{\mathcal {N}}}_{k}} \subset \mathbb {R}\) be a set of non-negative numbers. Define the \(|{{\mathcal {N}}}(S)|\times |{{\mathcal {N}}}(S)|\) matrix indexed by \({{\mathcal {N}}}(S)\) as

$$\begin{aligned} \left( M_{S}(x)\right) _{S', S''} = \left\{ \begin{aligned}&x_{S' \cup S''},{} & {} \text{ if } S' \cup S'' \text{ has } \text{ minimum } \text{ distance } \text{ at } \text{ least } d;\\ {}&0,{} & {} \text{ otherwise, } \end{aligned}\right. \end{aligned}$$

for \(S', S'' \in {{\mathcal {N}}}(S)\). Then,

$$\begin{aligned} {} {} A(n, d){} & {} {} \le A_{k}(n, d) \nonumber \\{}{} & {} {} = \text {max}\left\{ \sum _{i \in {{\mathcal {P}}}}x_{\{i\}}: x_{\emptyset } = 1, x_{S} \ge 0 \text{ and } M_{S}(x) \text{ is } \text{ positive } \text{ semidefinite } \text{ for } \text{ each } S \in {{\mathcal {N}}}_{k} \right\} . \nonumber \\ \end{aligned}$$
(17)

It can be shown that the generalized Schrijver’s SDP constraints with \(k = 4\) induce our positive semidefinite constraint on \(R_{s}\).

Proposition 12

The positive semidefinite constraints in the quadruple semidefinite program in (17) imply the positive semidefiniteness of \(R_{s}\).

Proof

Let C be a code of length n and minimum distance d. Consider \(S = \{\emptyset , u\} \in {{\mathcal {N}}}_{4}\), where u has 1 in the first \(n_{1}\) positions and 0 in the other \(n_{2}\) positions, which is a subset of C. Let x be defined as \(x_{i} = 1\) if \(i \subset C\) and \(x_{i} = 0\) for the other cases. Observe that there is an one-to-one correspondence between \(N(S) = \{S \cup \{v\}: v \in {{\mathcal {P}}}\}\) and \({{\mathcal {P}}}\) by sending \(S \cup \{v\}\) to v. Thus, \(M_{S}(x)\) can be indexed by \({{\mathcal {P}}}\) and

$$\begin{aligned} \left( M_{S}(x)\right) _{v, w} = \left\{ \begin{aligned}&1,{} & {} \text{ if } \{v, w\} \subset C;\\ {}&0,{} & {} \text{ otherwise. } \end{aligned}\right. \end{aligned}$$

Notice that \(M_{S}(x) = \chi ^{C} \left( \chi ^{C}\right) ^{T}\) is positive semidefinite and

$$\begin{aligned} R_{s}^{u} = \frac{1}{|\Pi _{s}^{u}|} \sum _{(\pi _{1}, \pi _{2}) \in \Pi _{s}^{u}} \chi ^{(\pi _{1}, \pi _{2})(C)} \left( \chi ^{(\pi _{1}, \pi _{2})(C)}\right) ^{T}. \end{aligned}$$

We observe that each \(\chi ^{(\pi _{1}, \pi _{2})(C)} \left( \chi ^{(\pi _{1}, \pi _{2})(C)}\right) ^{T}\) is similar to \(M_{S}(x) = \chi ^{C} \left( \chi ^{C}\right) ^{T}\) by changing the order of the basis. Thus, \(R_{s}^{u}\) is semidefinite. \(\square \)

4 Semidefinite program

In this section, we provide an SDP that gives an upper bound on the size of an (n, d) code \(C\subset {{\mathcal {P}}}\). We include the known linear constraints in the literature, which are critical in the SDP. We observe that an SDP with semidefinite constraints based on quadruple distances [16] does not improve the upper bounds of A(18, 4) and A(19, 4). In fact, the bounds obtained with only Schrijver’s semidefinite constraints are even worse than the bounds with linear constraints [5, 11] in some cases. For instance, \(A(18, 4) \le 6552\) can be obtained by certain linear constraints, while the SDP gives us an upper bound of 6553.

4.1 Linear constraints

The distance distribution \(A_j\) of C in (1) can be represented in terms of \(x_{i,i',j,j'}^{t,t'}\) as

$$\begin{aligned} A_{j} = \sum _{i+i' = j} \left( {\begin{array}{c}n_{1}\\ i\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ i'\end{array}}\right) x_{i, 0, i', 0}^{0, 0}. \end{aligned}$$

Furthermore, the propagation rule \(A(n-1, 2e-1) = A(n, 2e)\) [27] implies that we need to consider only even distance j.

Lemma 13

[5, Lemma 7]

$$\begin{aligned} \sum _{i = 0}^{n} \left( {\begin{array}{c}n-i\\ k\end{array}}\right) A_{i} \le \left( {\begin{array}{c}n\\ k\end{array}}\right) A(n-k, d). \end{aligned}$$
(18)

Lemma 14

[25, Theorem 9]

$$\begin{aligned} A_{n-\frac{d}{2}}+\left\lfloor \frac{2n}{d} \right\rfloor \sum _{i < \lfloor \frac{d}{2} \rfloor }A_{n-i} \le \left\lfloor \frac{2n}{d} \right\rfloor . \end{aligned}$$
(19)

Our SDP also benefits from bounds on A(n, d, w), the maximum size of a length-n code with minimum distance d and constant weight w.

Lemma 15

[5, Lemma 5] Let \(P = A(n-1, d, \frac{1}{2}d+1)\), \(Q = A(n-\frac{1}{2}d, d, \frac{1}{2}d+1)\), \(R = A(n-\frac{1}{2}d+2, d, \frac{1}{2}d+2)\), then

$$\begin{aligned}{} & {} \left( \frac{1}{2}d+2\right) A_{n-\frac{1}{2}d-2}+\frac{1}{2}d(P-Q)A_{n-\frac{1}{2}d}\nonumber \\{} & {} \quad +\left( n P-\left( \frac{1}{2}d+2\right) R\right) A_{n-\frac{1}{2}d+2}+n P\sum _{i = n-\frac{1}{2}d+3}^{n} A_{i} \le n P. \end{aligned}$$
(20)

Lemma 16

[25, Theorem 10] For \(i = 1, \dots , \frac{d}{2}-1\),

$$\begin{aligned} {}{} & {} {} A_{n-\frac{d}{2}-i}+\left( A(n, d, \frac{d}{2}+i)-A(n-\frac{d}{2}+i, d, \frac{d}{2}+i)\right) A_{n-\frac{d}{2}+i}\nonumber \\{}{} & {} {} \quad +A(n, d, \frac{d}{2}+i)\sum _{j>i}A_{n-\frac{d}{2}+j} \le A(n, d, \frac{d}{2}+i). \end{aligned}$$
(21)

Lemma 17

[32, (25)] For \(i = 0, \dots , n\),

$$\begin{aligned} A_{i} \le A(n, d, i). \end{aligned}$$
(22)

We also have additional linear constraints from doubly constant-weight codes. Let \(T(w_{1}, t_{1}, w_{2}, t_{2}, d)\) be the maximum possible size of a doubly constant-weight code, which is a \((t_{1}+t_{2}, d, w_{1}+w_{2})\) constant-weight code such that every codeword has exactly \(w_{1}\) and \(w_{2}\) ones on the first \(t_{1}\) and next \(t_{2}\) coordinates, respectively.

Lemma 18

[19, Theorem 3] For \(i, j, t \in \{0, \dots , n\}\), we have

$$\begin{aligned} x_{i, j}^{t} \le \frac{T(t, i, j-t, n-i, d)}{\left( {\begin{array}{c}i\\ t\end{array}}\right) \left( {\begin{array}{c}n-i\\ j-t\end{array}}\right) }x_{i, 0}^{0}. \end{aligned}$$
(23)

4.2 Semidefinite program for binary codes

Collecting all the mentioned linear and semidefinite constraints, we have the following SDP on A(n, d) with variables \( x_{i, j,i',j'}^{t,t'} \in \mathbb {C}\):

$$\begin{aligned} \mathrm{maximize\ }&\sum _{a = 0}^{n} \sum _{i+i' = a} \left( {\begin{array}{c}n_{1}\\ i\end{array}}\right) \left( {\begin{array}{c}n_{2}\\ i'\end{array}}\right) x_{i, 0, i', 0}^{0, 0}. \nonumber \\ \mathrm{subject\ to\ }&\text{ positive } \text{ semidefiniteness } \text{ of } (2), (3), (12), (13) \nonumber \\&(4),(9), (10), (14) \nonumber \\&(18), (19), (20), (21), (22), (23). \end{aligned}$$
(24)

As mentioned in the previous section, the generalized Delsarte’s inequalities (15) are implicitly included in the SDP.

4.3 The correctness of computer computational results

Since numerical methods will be used to approximate the optimal solution to an SDP, when we have a large number of variables, the accuracy of computer simulations may not be sufficient. In [14], Gijswijt used the weak duality of the optimization program to verify the SDP bounds. We describe his method here.

Consider an SDP of the following form:

$$\begin{aligned}&\text {maximize} \quad \sum _{i=1}^{m}x_{i}c_{i}\\&\text {subject to} \quad \sum _{i=1}^{m}x_{i}F_{i} + F_{0} \text { is positive semidefinite} \end{aligned}$$

with variables \(x_{1}, \dots , x_{m}\in \mathbb {R}\), constants \(c_{1}, \dots , c_{m}\in \mathbb {R}\) and symmetric matrices \(F_{0}, \dots , F_{m}\in \mathbb {R}^{n\times n}\). Its dual problem is as follows:

$$\begin{aligned} \text{ minimize } \quad&\text{ tr }{\left( F_{0} Y\right) } \\ \text{ subject } \text{ to } \quad&\text{ tr }{\left( F_{i}Y\right) } + c_{i}=0 \text{ for } i=1,\dots , m\\ {}&Y \text{ is } \text{ positive } \text{ semidefinite. } \end{aligned}$$

Every feasible Y in the dual problem gives an upper bound of the primal problem.

In a numerical computation, a dual solution Y may not exactly satisfy the constraints, but

$$\begin{aligned} \text{ tr } \left( F_{i} Y\right) + c_{i} = \epsilon _{i} \end{aligned}$$

for some small numbers \(\epsilon _{1}, \dots , \epsilon _{m}\) due to the computer accuracy. Similarly, a primal solution may not be reliable. However, we can estimate the computation error as follows. Let \(x_{1}^\star , \dots , x_{m}^\star \) be an optimal solution for the primal problem with objective value \(P = \sum _{i = 1}^{m}x_{i}^\star c_{i}\). Let \(X=\sum _{i=1}^{m}x_{i}^\star F_{i} + F_{0}\), which is positive semidefinite since \(x_i^\star \) are feasible. Then

$$\begin{aligned} \text{ tr } \left( F_{0} Y\right)&= \text{ tr } \left( \left( -\sum _{i = 1}^{m} x_{i}^\star F_{i} +X\right) Y \right) \\ {}&\ge \text{ tr } \left( -\sum _{i = 1}^{m} x_{i}^\star F_{i} Y \right) \\ {}&= -\sum _{i=1}^{m} x_{i}^\star \text{ tr } \left( F_{i} Y\right) \\ {}&= -\sum _{i = 1}^{m} x_{i}^\star (-c_{i}+ \epsilon _{i})\\ {}&= P - \sum _{i = 1}^{m} x_{i}^\star \epsilon _{i}. \end{aligned}$$

In our SDP (24), the variables \(x_{i,j,i',j'}^{t,t'}\) are negative and no larger than one by (14). For our purpose, we can have an upper bound on the optimal value P that

$$\begin{aligned} P \le \text{ tr } \left( F_{0} Y\right) + \sum _{i = 1}^{m}x_{i}^{*}\epsilon _{i} \le \text{ tr } \left( F_{0} Y\right) + \sum _{i=1}^{m}\text {max}\{0,\epsilon _{i}\}. \end{aligned}$$

Therefore, we may use the dual optimal value and error terms to estimate an upper bound in our computational results.

4.4 Computational results

We use the CVX toolbox [12, 13] in MATLAB with the MOSEK solver to run our SDP. Our main results are as follows. In our SDP, we have tested all possible values of splits \(n_{1}\) and \(n_{2}\). The computational results give us two improvements \(A(18,4) \le 6551\) and \(A(19,4) \le 13087\). However, using Gijswijt’s method in the previous subsection, we are only able to ensure one of them is improved.

Theorem 19

\(A(18,4) \le 6551\).

Proof

Using \(n_{1} = 2\), we obtain \(A(18,4)\le 6551.93\) with an error term less than \(10^{-16}\). Thus \(A(18,4)\le 6551\). \(\square \)

Remark 20

\(A(18,4) \le 6551\) can be obtained by the split SDP with \(n_{1} = 2\) and only the constraints (12), (13), (18) and (20). Then, we have \(A(18,4) \le 6551.98\) with an error term less than \(10^{-16}\). All the above mentioned constraints are necessary in this case.

5 Generalization

In this section, we consider an m-split distance distribution defined on a partition of \(\{1, \dots , n\}\) with arbitrary m subsets, say \(T_{1}, \dots , T_{m}\), each of size \(|T_{p}|= n_{p}\) for \(p \in \{1, \dots , m\}\). Our method can be generalized in this case to introduce more semidefinite constraints. Proofs to these generalizations are similar to the 2-split case and will be omitted. Finally, we discuss the underlying association scheme structure.

5.1 Semidefinite constraints from m-split Terwilliger algebras

Consider a group \(G = \prod _{p = 1}^{m}G_{p}\), where \(G_{p}\) is the isometry group on the power set of \(T_{p}\). Let \(\sigma _{1}, \dots , \sigma _{q}\) be the orbits of G acting on \({{\mathcal {P}}}\) for some q. Then we define \(|{{\mathcal {P}}}|\times |{{\mathcal {P}}}|\) matrices, indexed by \({{\mathcal {P}}}\),

$$\begin{aligned} \left( M_{\sigma _{k}}\right) _{X, Y} = \left\{ \begin{aligned}&1,{} & {} \text{ if } X, Y \in \sigma _{k},\\ {}&0,{} & {} \text{ otherwise } \end{aligned}\right. \end{aligned}$$

for all k. Observe that (X, Y) and (U, V) belong to the same orbit if and only if \(|X \cap T_{k}|= |U \cap T_{k}|\), \(|Y \cap T_{k}|= |V \cap T_{k}|\) and \(|X \Delta Y \cap T_{k}|= |U \Delta V \cap T_{k}|\) for each k. Let \({\varvec{i}}= (i_{1}, \dots , i_{m})\), \({\varvec{j}}= (j_{1}, \dots , j_{m})\), and \({\varvec{t}}= (t_{1}, \dots , t_{m})\) for \(i_{k}, j_{k}, t_{k} \in \{0, \dots , n_{k}\}\) with \(i_{k} + j_{k} - 2t_{k} \in \{0, \dots , n_{k}\}\), for all \(k \in \{1, \dots , m\}\). Then the orbits of G can be indexed by \(({\varvec{i}}, {\varvec{j}}, {\varvec{t}})\) and we may rewrite \(M_{\sigma _{k}}\) as

$$\begin{aligned} (M_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}})_{X, Y} = \left\{ \begin{aligned}&1,{} & {} \text{ if } |X \cap T_{k}|= i_{k}, |Y \cap T_{k}|= j_{k}, |X \cap Y \cap T_{k}|= t_{k} \text{ for } \text{ all } k;\\ {}&0,{} & {} \text{ otherwise. } \end{aligned}\right. \end{aligned}$$

For \({\varvec{n}}= (n_{1}, \dots , n_{m})\), we denote the algebra generated by \(\{M_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}}\}\) over \(\mathbb {C}\), defined as above, by \({{\mathcal {A}}}_{{\varvec{n}}}\), which is called an m-split Terwilliger algebra of the Hamming scheme.

Lemma 21

\({{\mathcal {A}}}_{{\varvec{n}}}\) is isomorphic to \(\bigotimes _{i = 1}^{m} {{\mathcal {A}}}_{n_{i}}\).

Corollary 22

There is an isomorphism from \({{\mathcal {A}}}_{{\varvec{n}}}\) to

$$\begin{aligned} \bigoplus _{k_{1} = 0}^{\left\lfloor \frac{n_{1}}{2} \right\rfloor } \cdots \bigoplus _{k_{m} = 0}^{\left\lfloor \frac{n_{m}}{2} \right\rfloor } \mathbb {C}^{N_{{\varvec{k}}} \times N_{{\varvec{k}}}}, \end{aligned}$$

with \(N_{{\varvec{k}}} = \prod _{a = 1}^{m} (n_{a}-2k_{a}+1)\), that maps \(A = \sum _{{\varvec{i}}, {\varvec{j}}, {\varvec{t}}}x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}} M_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}}\) to

$$\begin{aligned} \bigoplus _{k_{1} = 0}^{\left\lfloor \frac{n_{1}}{2} \right\rfloor } \cdots \bigoplus _{k_{m} = 0}^{\left\lfloor \frac{n_{m}}{2} \right\rfloor } {{\mathcal {B}}}_{{\varvec{k}}}, \end{aligned}$$

where

$$\begin{aligned} \begin{aligned} {{\mathcal {B}}}_{{\varvec{k}}} = \left( \sum _{{\varvec{t}}} \prod _{a = 1}^{m} \left( {\begin{array}{c}n_{a}-2k_{a}\\ i_{a}-k_{a}\end{array}}\right) ^{-\frac{1}{2}} \left( {\begin{array}{c}n_{a}-2k_{a}\\ j_{a}-k_{a}\end{array}}\right) ^{-\frac{1}{2}} \beta _{i_{a}, j_{a}, k_{a}}^{n_{a}, t_{a}} x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}} \right) _{({\varvec{i}}, {\varvec{j}}) = ({\varvec{k}}, {\varvec{k}})}^{({\varvec{n}}-{\varvec{k}}, {\varvec{n}}-{\varvec{k}})} \end{aligned} \end{aligned}$$

Next we derive additional semidefinite constraints for an (n, d) code C from the m-split Terwilliger algebra. Define

$$\begin{aligned} x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}} = \frac{1}{|C|\prod _{k = 1}^{m}\left( {\begin{array}{c}n_{k}\\ i_{k}-t_{k}, j_{k}-t_{k}, t_{k}\end{array}}\right) } \lambda ^{{\varvec{t}}}_{{\varvec{i}}, {\varvec{j}}}, \end{aligned}$$
(25)

where

$$\begin{aligned} \begin{aligned} \lambda ^{{\varvec{t}}}_{{\varvec{i}}, {\varvec{j}}} = |\{&(X, Y, Z) \in C^{3}: |(X \Delta Y)\cap T_{k}|= i_{k}, |(X \Delta Z)\cap T_{k}|= j_{k}, \\&|((X \Delta Y)\cap (X \Delta Z))\cap T_{k}|= t_{k}, \text { for } k=1,\dots , m \} |. \end{aligned} \end{aligned}$$
(26)

Now, the size of the code C is

$$\begin{aligned} |C|=\sum _{a = 0}^{n} \sum _{{\varvec{i}}\cdot {{\varvec{1}}}= a} \prod _{k = 1}^{m} \left( {\begin{array}{c}n_{k}\\ i_{k}\end{array}}\right) x_{{\varvec{i}}, {{\varvec{0}}}}^{{{\varvec{0}}}}, \end{aligned}$$

where \({{\varvec{1}}}\) denotes the all-one vector and \({{\varvec{0}}}\) denotes the zero vector. Then the group G acts on C as follows:

$$\begin{aligned} (g_{1}, \dots , g_{m}) \cdot (c) = \bigcup _{k=1}^{m} g_{k}(c \cap T_{k}), \end{aligned}$$

for \(g_{i} \in G_{i}\), \(i = 1, \dots , m\) and \(c \in C\). We define the sets

$$\begin{aligned}&\Pi _{\mathrm{{\varvec{s}}}} = \{g \in G \mid \emptyset \in g(C)\},\\&\Pi _{\mathrm{{\varvec{s}}}}' = \{g \in G \mid \emptyset \notin g(C)\}, \end{aligned}$$

and consider the semidefinite matrices

$$\begin{aligned}&R_{\mathrm {{\varvec{s}}}} = \frac{1}{|\Pi _{\mathrm {{\varvec{s}}}}|} \sum _{g \in \Pi _{\mathrm {{\varvec{s}}}}} \chi ^{g(C)} \left( \chi ^{g(C)}\right) ^{T}, \\ {}&R_{\mathrm {{\varvec{s}}}}' = \frac{1}{|\Pi _{\mathrm {{\varvec{s}}}}'|}\sum _{g \in \Pi _{\mathrm {{\varvec{s}}}}'} \chi ^{g(C)} \left( \chi ^{g(C)}\right) ^{T}, \end{aligned}$$

which are elements of \({{\mathcal {A}}}_{{\varvec{n}}}\). In fact, we have the following proposition.

Proposition 23

$$\begin{aligned} \begin{aligned}&R_{\mathrm{{\varvec{s}}}} = \sum _{{\varvec{i}}, {\varvec{j}}, {\varvec{t}}} x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}}M_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}},\\&\begin{aligned} R_{\mathrm{{\varvec{s}}}}' =&\frac{|C|}{2^{n}-|C|}\sum _{{\varvec{i}}, {\varvec{j}}, {\varvec{t}}} \left( x_{{\varvec{i}}+{\varvec{j}}-2{\varvec{t}}, {{\varvec{0}}}}^{{{\varvec{0}}}}-x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}}\right) M_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}}. \end{aligned} \end{aligned} \end{aligned}$$

From Proposition 23, we can also obtain the m-split generalized Delsarte’s inequalities [33]. Consider the generalized distance distribution \(\{A_{{\varvec{i}}}\}\) of C, where

$$\begin{aligned} A_{{\varvec{i}}} = \frac{1}{|C|}|\{(a, b) \in C \times C \mid |a \Delta b \cap T_{k}|= i_{k} \text { for } k=1,\dots ,m\}|. \end{aligned}$$

Corollary 24

If \(R_{\mathrm{{\varvec{s}}}}\) and \(R_{\mathrm{{\varvec{s}}}}'\) are positive semidefinite, then

$$\begin{aligned} \sum _{{\varvec{i}}} A_{{\varvec{i}}} \prod _{k = 1}^{m}K_{p_{k}}^{n_{k}}(i_{k}) \ge 0, \end{aligned}$$
(27)

for \({\varvec{p}}= (p_{1}, \dots , p_{m})\) with \(0 \le p_{k} \le n_{k}\) for all k.

It can be showed that the generalized Schrijver’s SDP constraints with \(k = m+2\) induce our positive semidefinite constraint on \(R_{s}\).

Proposition 25

The positive semidefinite constraints in the generalized Schrijver’s SDP with \(k = m+2\) implies the positive semidefiniteness of \(R_{s}\).

By the block diagonal form for \({{\mathcal {A}}}_{{\varvec{n}}}\), we have additional semidefinite constraints. For \({\varvec{k}}= (k_{1}, \dots , k_{m})\) with \(k_{a} \in \{0, \dots , \lfloor \frac{n_{a}}{2} \rfloor \}\) and \(a \in \{1, \dots , m\}\), the matrices

$$\begin{aligned}{} & {} \left( \sum _{{\varvec{t}}} \prod _{a = 1}^{m} \left( {\begin{array}{c}n_{a}-2k_{a}\\ i_{a}-k_{a}\end{array}}\right) ^{-\frac{1}{2}} \left( {\begin{array}{c}n_{a}-2k_{a}\\ j_{a}-k_{a}\end{array}}\right) ^{-\frac{1}{2}} \beta _{i_{a}, j_{a}, k_{a}}^{n_{a}, t_{a}} x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}} \right) _{({\varvec{i}}, {\varvec{j}}) = ({\varvec{k}}, {\varvec{k}})}^{({\varvec{n}}-{\varvec{k}}, {\varvec{n}}-{\varvec{k}})}, \end{aligned}$$
(28)
$$\begin{aligned}{} & {} \left( \sum _{{\varvec{t}}} \prod _{a = 1}^{m} \left( {\begin{array}{c}n_{a}-2k_{a}\\ i_{a}-k_{a}\end{array}}\right) ^{-\frac{1}{2}} \left( {\begin{array}{c}n_{a}-2k_{a}\\ j_{a}-k_{a}\end{array}}\right) ^{-\frac{1}{2}} \beta _{i_{a}, j_{a}, k_{a}}^{n_{a}, t_{a}} (x_{{\varvec{i}}+{\varvec{k}}-2{\varvec{t}}, {{\varvec{0}}}}^{{{\varvec{0}}}}-x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}}) \right) _{({\varvec{i}}, {\varvec{j}}) = ({\varvec{k}}, {\varvec{k}})}^{({\varvec{n}}-{\varvec{k}}, {\varvec{n}}-{\varvec{k}})} \end{aligned}$$
(29)

are semidefinite.

Proposition 26

Let C be a code with length n and minimum distance at least d. Then we have the following linear constraints on \(x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}}\) corresponding to C: for proper \({\varvec{i}}, {\varvec{j}}, {\varvec{t}}\),

$$\begin{aligned} \begin{array}{cl} \text{(i) } &{} x_{{{\varvec{0}}}, {{\varvec{0}}}}^{{{\varvec{0}}}} = 1 \\ \text{(ii) }&{} 0 \le x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}} \le x_{{\varvec{i}}, {{\varvec{0}}}}^{{{\varvec{0}}}} \\ \text{(iii) }&{} x_{{\varvec{i}}, {{\varvec{0}}}}^{{{\varvec{0}}}} + x_{{{\varvec{0}}}, {\varvec{j}}}^{{{\varvec{0}}}} \le 1 + x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}} \\ \text{(iv) }&{} x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}} = x_{{\varvec{a}}, {\varvec{b}}}^{{\varvec{c}}} \text{ if } ({\varvec{i}}, {\varvec{j}}, {\varvec{i}}+{\varvec{j}}-2{\varvec{t}}) \\ &{} \text{ is } \text{ a } \text{ permutation } \text{ of } ({\varvec{a}}, {\varvec{b}}, {\varvec{a}}+{\varvec{b}}-2{\varvec{c}}), \\ \text{(v) }&{} x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}} = 0 \text{ if } \{{\varvec{i}}, {\varvec{j}}, {\varvec{i}}+{\varvec{j}}-2{\varvec{t}}\} \cap \{1, \dots , d-1\} \ne \emptyset . \end{array} \end{aligned}$$
(30)

To sum up, we have an SDP for A(n, d) with variables \(x_{{\varvec{i}}, {\varvec{j}}}^{{\varvec{t}}} \in \mathbb {C}\):

$$\begin{aligned} \textrm{maximize }&\sum _{a = 0}^{n} \sum _{{\varvec{i}}\cdot {{\varvec{1}}}= a} \prod _{k = 1}^{m} \left( {\begin{array}{c}n_{k}\\ i_{k}\end{array}}\right) x_{{\varvec{i}}, {{\varvec{0}}}}^{{{\varvec{0}}}}. \\ \mathrm{subject\ to\ }&\text{ positive } \text{ semidefiniteness } \text{ of } (28) \text { and } (29) (30) \end{aligned}$$

This SDP is called an m-split SDP, which corresponds to an m-split Terwilliger algebra \({{\mathcal {A}}}_{{\varvec{n}}}\).

5.2 Underlying structure

Herein we describe a special structure for an association scheme, which is inspired by the split method used in this paper.

Definition 27

(m-split property) Let \(S = (X, \{R_{i}\}_{i=0}^{k})\) be an association scheme. We say that S is m-split for some \(1 \le m \le |X|\) if there exist m association schemes \(S_{1} = (X_{1}, \{R_{i}^{(1)}\}_{i=0}^{k_{1}}), \dots , S_{m} = (X_{m}, \{R_{i}^{(m)}\}_{i=0}^{k_{m}})\) and a collection of maps \(\{f_{i}\}\) such that \(f_{i}: X \longrightarrow X_{i}\) is surjective for each i and for \((x, y) \in X \times X\), \((x, y) \in R_{j}\) if and only if \(\sum _{i = 1}^{m} d_{i} = j\), where \((f_{i}(x), f_{i}(y)) \in R_{d_{i}}^{(i)}\) for each i.

Clearly, we have the following lemma.

Lemma 28

Every association scheme is 1-split.

For an m-split association scheme S, we can define an m-split Bose–Mesner algebra by \(\bigotimes _{i=1}^{m} {{\mathcal {B}}}(S_{i})\) and an m-split Terwilliger algebra by \(\bigotimes _{i=1}^{m} {{\mathcal {T}}}(S_{i})\), where \({{\mathcal {B}}}(S_{i})\) is the Bose–Mesner algebra of \(S_{i}\) and \({{\mathcal {T}}}(S_{i})\) is the Terwilliger algebra of \(S_{i}\).

In our case of binary codes, \(S = {{\mathcal {H}}}(n, 2)\) is the Hamming scheme of length n over \(\mathbb {F}_{2}\) and each \(S_{i}\) is \({{\mathcal {H}}}(n_{i}, 2)\). Clearly, S is m-split for \(1 \le m \le n\). We may observe that m-split Bose–Mesner algebras induce the m-split generalized Delsarte’s inequalities and m-split Terwilliger algebras induce m-split triple distances SDP. Moreover, there are ascending chains for algebras.

$$\begin{aligned}{} & {} {{\mathcal {B}}}_{1} \le {{\mathcal {B}}}_{2} \le \cdots \le {{\mathcal {B}}}_{n}, \end{aligned}$$
(31)
$$\begin{aligned}{} & {} {{\mathcal {T}}}_{1} \le {{\mathcal {T}}}_{2} \le \cdots \le {{\mathcal {T}}}_{n}. \end{aligned}$$
(32)

In here, \({{\mathcal {B}}}_{m}\) is an m-split Bose–Mesner algebra of S, and \({{\mathcal {T}}}_{m}\) is an m-split Terwilliger algebra of S for \(m = 1, \dots , n\). The chain (31) allows us to combine an l-split generalized Delsarte’s inequalities to an m-split generalized Delsarte’s inequalities for \(l \le m\) by merging some partitions as the one. On the other hand, the chain (32) allows us to add constraints in an l-split triple distances SDP to an m-split triple distances SDP for some \(l \le m\) without increasing the number of variables.

6 Conclusion

In conclusion, we have derived generalized Schrijver semidefinite constraints by considering the split of Terwilliger algebra. Our split semidefinite constraints are a natural generalization of Schrijver’s constraints since they also implied the generalized Delsarte inequalities.

By implementing a 2-split SDP, we have improved the upper bounds for A(18, 4) and A(19, 4). The MATLAB programs of the SDPs in this paper can be found at:

https://github.com/PinChiehTseng/Split_SDP_solution

We have confirmed that \(A(18,4)\le 6551\) by showing that an upper bound on the numerical error is small enough. As for A(19, 4), we obtain \(A(19,4)\le 13087.5\) using \(n_{1} = 9\). The currently best known bound for A(19, 4) is 13104. As for the error estimate, we obtained an upper bound on the numerical error as large as 215.7376. Since this estimate is over pessimistic, it provides no information about out result. Since the solver normally returned without any warning, we believed this figure is correct. More accurate solvers could be considered.

Our split approach can be extended to other related problems. For example, one may consider an arbitrary finite field or k-distance SDP for arbitrary k. Notice that the method described in [16] with \(|S |= 2\) has been applied to improve upper bounds for constant weight codes. Moreover, the algebra considered in [30] is of the form \(\bigotimes _{i} \mathcal {A}_{n_{i}}\) with \(\sum _{i}n_{i} = n\). The constraint \(R_{s}\) for constant weight codes has been studied. We can have a similar application by adding the constraint \(R'_{s}\), which potentially opens a way to strengthen the upper bounds for constant weight codes. As for the upper bounds on the size of a set with few distances or intersecting families of subsets [6, 26], we may directly apply our method to those problems. Moreover, as Schrijver’s SDP has been extended to the maximum size problem of a code in the fold of n-cube by Hou et al. [18], we might have a similar extension. The idea of isometry groups might be applied to spherical codes as well.

As an example of association schemes, our method corresponds to a special case of the m-split property of the Hamming scheme. Thus, our method may be extended to other association schemes, which share this m-split property. It is an interesting research direction.

Finally, it has been shown that certain polynomial symmetric properties can be exploited to obtain additional matrix inequalities and hence improve the semidefinite programming bounds for the kissing number problem [24]. It is unknown whether a similar ideas could be applied to the case of binary codes to obtain better bounds for A(n, d).