Binary extremal self-dual codes of length 60 and related codes

Abstract

We give a classification of four-circulant singly even self-dual [60, 30, d] codes for $d=10$ and 12. These codes are used to construct extremal singly even self-dual [60, 30, 12] codes with weight enumerator for which no extremal singly even self-dual code was previously known to exist. From extremal singly even self-dual [60, 30, 12] codes, we also construct optimal singly even self-dual [58, 29, 10] codes with weight enumerator for which no optimal singly even self-dual code was previously known to exist. Finally, we give some restriction on the possible weight enumerators of certain singly even self-dual codes with shadow of minimum weight 1.

1 Introduction

Let C be a (binary) singly even self-dual code. All codes in this note are binary. Let $C_0$ denote the subcode of C consisting of codewords having weight $\equiv 0\pmod 4$. The shadow S of C is defined to be $C_0^\perp \setminus C$. Shadows for self-dual codes were introduced by Conway and Sloane [3] in order to derive new upper bounds for the minimum weight of singly even self-dual codes, and to provide restrictions on the weight enumerators of singly even self-dual codes. In addition, Rains [11] showed that the minimum weight d of a self-dual code C of length n is bounded by $d\le 4 \lfloor n/24 \rfloor +4$ unless $n \equiv 22 \pmod {24}$ when $d \le 4 \lfloor n/24 \rfloor +6$ by considering the shadows. A self-dual code meeting the upper bound is called extremal. We say that a self-dual code is optimal if it has the largest minimum weight among all self-dual codes of that length.

The possible weight enumerators of singly even self-dual codes with the largest possible minimum weights given in [3, Table I] are given in [3] for lengths up to 64 and length 72 (see also [7] for length 60). It is a fundamental problem to find which weight enumerators actually occur for the possible weight enumerators (see [3]). The possible weight enumerators of extremal singly even self-dual [60, 30, 12] codes are known as follows:

$$\begin{aligned} W_{60,1}= & {} 1 +(2555+64 \beta ) y^{12} + (33600 - 384 \beta )y^{14} + \cdots , \\ W_{60,2}= & {} 1 + 3451y^{12} + 24128 y^{14} + \cdots , \end{aligned}$$

where $\beta$ is an integer. If there is an extremal singly even self-dual [60, 30, 12] code with weight enumerator $W_{60,1}$, then $\beta \in \{0,1,2,\ldots ,8,10\}$ [8]. For $\beta =0,1,5,7$ and 10, an extremal singly even self-dual code with weight enumerator $W_{60,1}$ was found in [13],[2],[14],[5]] and [7], respectively. An extremal singly even self-dual code with weight enumerator $W_{60,2}$ was found in [3].

One of the main aims of this note is to show the following:

Proposition 1

There is an extremal singly even self-dual [60, 30, 12] code with weight enumerator $W_{60,1}$ for $\beta =2,6$.

These codes are constructed from four-circulant singly even self-dual [60, 30, d] codes for $d=10$ and 12 by considering self-dual neighbors. It remains to determine whether there is an extremal singly even self-dual [60, 30, 12] code with weight enumerator $W_{60,1}$ for $\beta =3,4,8$.

The largest minimum weight among singly even self-dual codes of length 58 is 10 [3]. The possible weight enumerators of optimal singly even self-dual [58, 29, 10] codes are known as follows:

$$\begin{aligned} W_{58,1}= & {} 1 + (165 - 2 \gamma )y^{10} + (5078 + 2 \gamma )y^{12} + \cdots , \\ W_{58,2}= & {} 1 +(319 - 24 \beta - 2 \gamma )y^{10} + (3132 + 152 \beta + 2\gamma )y^{12} + \cdots , \end{aligned}$$

where $\beta ,\gamma$ are integers [3]. If there is an optimal singly even self-dual [58, 29, 10] code with weight enumerator $W_{58,2}$, then $\beta \in \{0,1,2\}$ [8]. An optimal singly even self-dual code with weight enumerator $W_{58,1}$ is known for $\gamma =55$ [12]. An optimal singly even self-dual code with weight enumerator $W_{58,2}$ is known for

$$\begin{aligned} \beta =0 \text { and }&\gamma \in \{2m \mid m =0,1,5,6,8,9,10,11,13,\ldots ,65,68,71,79\}, \\ \beta =1 \text { and }&\gamma \in \{2m \mid m =13,14,16,\ldots ,58,63\}, \\ \beta =2 \text { and }&\gamma \in \{2m \mid m =0,16,\ldots ,50,55\} \end{aligned}$$

(see [9, 10, 14]).

The following proposition is one of the main results of this note.

Proposition 2

There is an optimal singly even self-dual [58, 29, 10] code with weight enumerator $W_{58,2}$ for

$$\begin{aligned} \beta =0 \text { and }&\gamma \in \{2m \mid m =2,3,4,7,12\}, \\ \beta =1 \text { and }&\gamma \in \{2m \mid m =8,9,10,11,12,15\}, \\ \beta =2 \text { and }&\gamma \in \{2m \mid m =4,6,7,8,9,10,11,12,13,14,15,51,52,53,54\}. \end{aligned}$$

These codes are constructed from extremal singly even self-dual [60, 30, 12] codes constructed in this note by subtracting and their self-dual neighbors. Finally, we give some restriction on the possible weight enumerators of certain singly even self-dual codes with shadow of minimum weight 1 (Proposition 5). As a consequence, it is shown that $\gamma =55$ for the possible weight enumerator $W_{58,1}$ (Corollary 6). All self-dual codes in this note are singly even. From now on, we omit the term singly even.

All computer calculations in this note were done with the help of Magma [1].

2 Extremal four-circulant self-dual [60, 30, 12] codes

An $n \times n$ circulant matrix has the following form:

$$\begin{aligned} \left( \begin{array}{ccccc} r_0&{}r_1&{}r_2&{} \cdots &{}r_{n-1} \\ r_{n-1}&{}r_0&{}r_1&{} \cdots &{}r_{n-2} \\ \vdots &{}\vdots &{} \vdots &{}&{} \vdots \\ r_1&{}r_2&{}r_3&{} \cdots &{}r_0 \end{array} \right) , \end{aligned}$$

so that each successive row is a cyclic shift of the previous one. Let A and B be $n \times n$ circulant matrices. Let C be a [4n, 2n] code with generator matrix of the following form:

(1)

where $I_n$ denotes the identity matrix of order n and $A^T$ denotes the transpose of A. It is easy to see that C is self-dual if $AA^T+BB^T=I_n$. The codes with generator matrices of the form (1) are called four-circulant.

In this section, we give a classification of extremal four-circulant self-dual [60, 30, 12] codes. Two codes are equivalent if one can be obtained from the other by a permutation of coordinates. Our exhaustive search found all distinct extremal four-circulant self-dual [60, 30, 12] codes, which must be checked further for equivalence to complete the classification. This was done by considering all pairs of $15 \times 15$ circulant matrices A and B satisfying the condition that $AA^T+BB^T=I_{15}$, the sum of the weights of the first rows of A and B is congruent to $1 \pmod 4$ and the sum of the weights is greater than or equal to 13. Since a cyclic shift of the first rows gives an equivalent code, we may assume without loss of generality that the last entry of the first row of B is 1. Then our computer search shows that the above distinct extremal four-circulant self-dual [60, 30, 12] codes are divided into 13 inequivalent codes.

Proposition 3

Up to equivalence, there are 13 extremal four-circulant self-dual [60, 30, 12] codes.

We denote the 13 codes by $C_{60,i}$ $(i=1,2,\ldots ,13)$. For the 13 codes $C_{60,i}$ $(i=1,2,\ldots ,13)$, the first rows $r_A$ (resp. $r_B$) of the circulant matrices A (resp. B) in generator matrices (1) are listed in Table 1. We verified that the codes $C_{60,i}$ have weight enumerator $W_{60,1}$, where $\beta$ are also listed in Table 1.

Table 1 Extremal four-circulant self-dual [60, 30, 12] codes $C_{60,i}$

3 Extremal self-dual [60, 30, 12] neighbors

Two self-dual codes C and $C'$ of length n are said to be neighbors if $\dim (C \cap C')=n/2-1$. Any self-dual code of length n can be reached from any other by taking successive neighbors (see [3]). It is known that a self-dual code C of length n has $2(2^{n/2-1}-1)$ self-dual neighbors. These neighbors are constructed by finding $2^{n/2-1}-1$ subcodes of codimension 1 in C containing the all-one vector. A computer program written in Magma, which was used to find self-dual neighbors, can be obtained electronically from http://www.math.is.tohoku.ac.jp/~mharada/Paper/neighbor.txt. In this section, we construct extremal self-dual [60, 30, 12] codes by considering self-dual neighbors.

For $i=1,2,\ldots ,13$, by finding all $2(2^{29}-1)$ self-dual neighbors of $C_{60,i}$, we determined the equivalence classes among extremal self-dual neighbors of $C_{60,i}$. Our computer search shows that the code $C_{60,i}$ has $n_i$ inequivalent extremal self-dual neighbors, which are equivalent to none of the 13 codes $C_{60,j}$, where $n_i$ are given by

$$\begin{aligned} n_i= {\left\{ \begin{array}{ll} 3 &{} \quad \text {if }\ \ i=1, \\ 1 &{} \quad \text {if } \ \ i=2,4,10,12, \\ 0 &{} \quad \text {otherwise.}\\ \end{array}\right. } \end{aligned}$$

We denote the 7 extremal self-dual codes by $D_{60,i}$ $(i=1,2,\ldots ,7)$. These codes $C=D_{60,i}$ are constructed as

$$\begin{aligned} \langle (D \cap \langle x \rangle ^\perp ), x \rangle , \end{aligned}$$

where D and the support ${{\mathrm{supp}}}(x)$ of x are listed in Table 2. We verified that the codes $D_{60,i}$ have weight enumerator $W_{60,1}$, where W in Table 2 indicates the values $\beta$ in the weight enumerator $W_{60,1}$. The code $D_{60,3}$ has the following weight enumerator:

$$\begin{aligned}&1 + 2683 y^{12} + 32832 y^{14} + 280017 y^{16} + 1719808 y^{18} + 7800120 y^{20} \\&+ 26380032 y^{22} + 67167368 y^{24} + 130134528 y^{26} + 193185267 y^{28} \\&+ 220336512 y^{30} + \cdots + y^{60}. \end{aligned}$$

We verified that there is no pair of equivalent codes among the 13 codes $C_{60,i}$ and the 7 codes $D_{60,i}$.

We continue the search to find extremal self-dual codes by considering self-dual neighbors. We found all inequivalent extremal self-dual neighbors $E_{60,i_1}$ of $D_{60,i_2}$, which are equivalent to none of the extremal self-dual codes previously obtained in this note. For the codes $E_{60,i_1}=\langle (D \cap \langle x \rangle ^\perp ), x \rangle$, D and ${{\mathrm{supp}}}(x)$ are listed in Table 3. In the table, W indicates the values $\beta$ in the weight enumerator $W_{60,1}$. By continuing this process, we found all inequivalent extremal self-dual neighbors of $E_{60,i}$, which are equivalent to none of the extremal self-dual codes previously obtained in this note. Finally, we verified that there is no extremal self-dual neighbor of $F_{60}$, which are equivalent to none of the extremal self-dual codes previously obtained in this note.

Table 2 Extremal self-dual [60, 30, 12] neighbors $D_{60,i}$

Table 3 Extremal self-dual [60, 30, 12] neighbors $E_{60,i}$ and $F_{60}$

4 Extremal four-circulant self-dual [60, 30, 10] codes and self-dual neighbors

Using an approach similar to that given in Sect. 2, our exhaustive search found all distinct four-circulant self-dual [60, 30, 10] codes. Then our computer search shows that the distinct four-circulant self-dual [60, 30, 10] codes are divided into 113 inequivalent codes.

Proposition 4

Up to equivalence, there are 113 four-circulant self-dual [60, 30, 10] codes.

We denote the 113 codes by $G_{60,i}$ $(i=1,2,\ldots ,113)$. For the 13 codes $G_{60,i}$ $(i=1,2,\ldots ,13)$, the first rows $r_A$ (resp. $r_B$) of the circulant matrices A (resp. B) in generator matrices (1) are listed in Table 4. The first rows for the all codes can be obtained from http://www.math.is.tohoku.ac.jp/~mharada/Paper/60-4cir-d10.txt.

Table 4 Four-circulant self-dual [60, 30, 10] codes $G_{60,i}$

In addition, we found extremal self-dual [60, 30, 12] codes by considering self-dual neighbors of $G_{62,i}$ $(i=1,2,\ldots ,113)$. Using a method similar to that given in [4], we completed the classification of extremal self-dual [60, 30, 12] neighbors of $G_{62,i}$ $(i=1,2,\ldots ,113)$. Our computer search shows that there is an extremal self-dual [60, 30, 12] neighbor $H_{60,i}$ for $i=1,2,\ldots ,13$ and that there is no extremal self-dual [60, 30, 12] neighbor for $i=14,15,\ldots ,113$. The codes $H_{60,i}$ are constructed as $\langle (D \cap \langle x \rangle ^\perp ), x \rangle$, where D and ${{\mathrm{supp}}}(x)$ are listed in Table 5 and W indicates the values $\beta$ in the weight enumerator $W_{60,1}$. We verified that there are the following equivalent codes among $C_{60,i_1}, D_{60,i_2}, E_{60,i_3}, F_{60}, H_{60,i_4}$:

$$\begin{aligned}&H_{60,2} \cong C_{60,4},\quad H_{60,5} \cong C_{60,1},\quad H_{60,6} \cong C_{60,3},\quad H_{60,7} \cong C_{60,8},\quad H_{60,8} \cong C_{60,7}, \\&H_{60,9} \cong C_{60,2},\quad H_{60,11}\cong H_{60,3},\quad H_{60,12}\cong H_{60,10},\quad H_{60,13}\cong H_{60,4},\quad H_{60,10}\cong D_{60,2}, \end{aligned}$$

where $C \cong D$ means that C and D are equivalent.

Table 5 Extremal self-dual [60, 30, 12] neighbors $H_{60,i}$, $J_{60,i}$, $K_{60,i}$ and $L_{60,i}$

Similar to Sect. 3, by continuing this process, we completed a classification of extremal self-dual neighbors $J_{60,i}$ (resp. $K_{60,i}$, $L_{60,i}$), which are equivalent to none of the extremal self-dual codes previously obtained in this note, of $H_{60,j}$ (resp. $J_{60,j}$, $K_{60,j}$). Finally, we verified that there is no extremal self-dual neighbor of $L_{60,i}$ $(i=1,2)$, which are equivalent to none of the 37 codes in Tables 1, 2, 3 and 5. We remark that there is no pair of equivalent codes among the following 37 codes:

$$\begin{aligned}&C_{60,i}\ (i=1,2,\ldots ,13),\quad D_{60,i}\ (i=1,2,\ldots ,7),\quad E_{60,i}\ (i=1,2,3,4), F_{60}, \\ {}&H_{60,i}\ (i=1,3,4),\quad J_{60,i}\ (i=1,2,3,4,5),\quad K_{60,i}\ (i=1,2),\quad L_{60,i}\ (i=1,2). \end{aligned}$$

The codes $D_{60,3}$ and $J_{60,5}$ (see Tables 2, 5) establish Proposition 1. The code $J_{60,5}$ has the following weight enumerator:

$$\begin{aligned}&1 + 2939 y^{12} + 31296 y^{14} + 282321 y^{16} + 1723904 y^{18} + 7784760 y^{20} \\&+ 26386176 y^{22} + 67197064 y^{24} + 130097664 y^{26} + 193168371 y^{28} \\&+ 220392832 y^{30} + \cdots + y^{60}. \end{aligned}$$

5 Optimal self-dual [58, 29, 10] codes

An extremal self-dual [60, 30, 12] code gives an optimal self-dual [58, 29, 10] code by subtracting two coordinates. We found all the optimal self-dual [58, 29, 10] codes by subtracting from the 37 inequivalent extremal self-dual [60, 30, 12] codes given in Sects. 2, 3 and 4. The only extremal self-dual [60, 30, 12] code $D_{60,3}$ gives 18 optimal self-dual [58, 29, 10] codes $C_{58,i}$ $(i=1,2,\ldots ,18)$ with weight enumerator for which no optimal self-dual code was previously known to exist. More precisely, the codes by subtracting i and j have weight enumerator $W_{58,2}$ for $\beta =2$ and $\gamma =104$, where (i, j) are listed in Table 6. We verified that there are the following equivalent codes:

$$\begin{aligned}&C_{58, 1} \cong C_{58, i}\ (i= 2, 4, 5, 7, 8,11,12,14,15,17,18), \\ {}&C_{58, 3} \cong C_{58, i}\ (i= 6, 9,10,13,16), \end{aligned}$$

where $C_{58,1}$ and $C_{58,3}$ are inequivalent.

Table 6 Optimal self-dual [58, 29, 10] codes $C_{58,i}$

Similar to Sects. 3 and 4, we continue the search to find optimal self-dual [58, 29, 10] codes with weight enumerator for which no optimal self-dual code was previously known to exist, by considering self-dual neighbors of $C_{58,i}$ $(i=1,3)$. These codes $C=D_{58,i}$ are constructed as

$$\begin{aligned} \langle (D \cap \langle x \rangle ^\perp ), x \rangle , \end{aligned}$$

where D and ${{\mathrm{supp}}}(x)$ are listed in Table 7. We verified that the codes $D_{58,i}$ have weight enumerator $W_{58,2}$, where W in Table 7 indicates the values $(\beta ,\gamma )$ in the weight enumerator $W_{58,2}$. By continuing this process, we found more optimal self-dual [58, 29, 10] codes with weight enumerator for which no optimal self-dual code was previously known to exist. The results are listed in Table 7. From Tables 6 and 7, we have Proposition 2.

Table 7 Optimal self-dual [58, 29, 10] neighbors

6 Weight enumerator $W_{58,1}$

In this section, we give a remark on the possible weight enumerator $W_{58,1}$. First, we discuss a general case including $W_{58,1}$.

Proposition 5

Let C be a self-dual [n, n / 2, d] code with shadow S of minimum weight 1. Let $A_i$ and $B_i$ denote the numbers of vectors of weight i in C and S, respectively. Suppose that $n \equiv 2 \pmod 8$ and $d \equiv 2 \pmod 4$. Then $B_{d-1} =A_{d}$.

Proof

Let x be the vector of weight 1 and let y be a vector of weight $d-1$ in S. Since $x+y \in C$, $x+y$ has weight d. Thus, $B_{d-1} \le A_{d}$.

Now let c be a codeword of weight d in C and let x be the vector of weight 1 in S. Then we have $x+c \in S$. From the assumption that $n \equiv 2 \pmod 8$, the weight of $x+c$ is congruent to $1 \pmod 4$ by Theorem 5 in [3]. Hence, from the assumption that $d \equiv 2 \pmod 4$, $x+c$ has weight $d-1$. Thus, $B_{d-1} \ge A_{d}$. The result follows. $\square$

For example, Proposition 5 can be applied to the following parameters:

$$\begin{aligned} (n,d)=(58,10), (74,14) \text { and } (98,18). \end{aligned}$$

• $(n,d)=(58,10)$:

  The possible weight enumerator of the shadow of an optimal self-dual [58, 29, 10] code with weight enumerator $W_{58,1}$ is as follows [3]:

  $$\begin{aligned} y+ \gamma y^9 + (23918-10\gamma )y^{13} + \cdots . \end{aligned}$$

  By Proposition 5, we have

  $$\begin{aligned} 165-2\gamma = \gamma . \end{aligned}$$

  Since there is an optimal self-dual [58, 29, 10] code with weight enumerator $W_{58,1}$ for $\gamma =55$ [12], we have the following:

Corollary 6

There is an optimal self-dual [58, 29, 10] code with weight enumerator $W_{58,1}$ if and only if $\gamma =55$.

• $(n,d)=(74,14)$:

  The largest minimum weight among self-dual codes of length 74 is at most 14 [6]. The weight enumerator $W_2$ in [6, p. 2039] is the possible weight enumerator of a self-dual [74, 37, 14] code with shadow of minimum weight 1. By Proposition 5, we have $\alpha =-135$ for $W_2$ in [6, p. 2039]. The weight enumerators of such a code and its shadow are as follows:

  $$\begin{aligned}&1 + 2044 y^{14} + 159067 y^{16} + 520782 y^{18} + \cdots , \\&y + 2044 y^{13} + 679849 y^{17} + 44010824 y^{21} +\cdots , \end{aligned}$$

  respectively. It is still unknown whether there is a self-dual [74, 37, 14] code (with shadow of minimum weight 1).

• $(n,d)=(98,18)$:

  The largest minimum weight among self-dual codes of length 98 is at most 18 [6]. The weight enumerator $W_3$ in [6, p. 2041] is the unique weight enumerator for a self-dual [98, 49, 18] code with shadow of minimum weight 1. The weight enumerators of such a code and its shadow are as follows:

  $$\begin{aligned}&1 + 22116 y^{18} + 2016048 y^{20} + 7181104 y^{22} + \cdots , \\&y + 22116 y^{17} + 9197152 y^{21} + 964758896 y^{25} + \cdots , \end{aligned}$$

  respectively. It is still unknown whether there is a self-dual [98, 49, 18] code (with shadow of minimum weight 1).