On the Classification of Extremal

Even Formally Self-dual Codes

of Lengths 20 and 22

J. E. Fields^{∗}, P. Gaborit^{∗}, W. C. Huffman^{†}, V. Pless^{∗}

September 17, 1998

Abstract In this paper we prove that there are exactly 7 inequivalent [20,10,6] even extremal formally self-dual binary codes and that there are over 1000 inequivalent [22,11,6] even extremal formally self-dual binary codes. We give properties of these codes and present a summary of what is known about the classification of even extremal formally self-dual codes of small length.

1 Introduction

In [1, 4, 7] the extremal even formally self-dual binary codes of lengths up to 18 are classified. Length 12 was done by Bachoc [1]. The current authors developed a form for the generator matrix of such codes and used this, together with intersection matrices, to find the codes of length 14 [4]. The unique codes of lengths 10 and 18 were found in [7] using properties of 3designs found in any such code union its dual. As there are no [16,8,6] linear codes, the next open cases are lengths 20 and 22 which we address in this paper. In the next section we present terminology and discuss general results that we will need for the classification. In Sections 3 and 5, we discuss lengths 20 and 22, respectively. We completely classify the formally self-dual codes of length 20 and give information about their structure. At length 22 we find there are too many to classify (more than 1000); however, we do make comments about the codes we did find, noting information about their groups, hulls, and intersection tables.

∗Department of Mathematics, Statistics, and Computer Science, 322 SEO, University of Illinois–Chicago, 851 S. Morgan, Chicago, IL 60 607-7045, USA; e-mail: fields@math.uic.edu, gaborit@math.uic.edu, pless@math.uic .edu

†Department of Mathematical and Computer Sciences, Loyola University, Chicago, IL 60626, USA; e-mail:

wch@math.luc.edu

2 Preliminary Results and Notation

A code C is called formally self-dual (or f.s.d.) if the weight distribution of C equals that of C^{⊥} [7]. A binary f.s.d. [n, n/2, d] code is called extremal if it meets the bound on Type I codes, i.e. if d = 2⌊\frac{n}{8}⌋ + 2. In lengths 20 and 22, d = 6 for extremal even f.s.d. codes. In [4] the following form of a generator matrix was presented for [n, n/2] codes and used to classify the extremal even [14,7,4] f.s.d. codes. This form of the generator matrix for our codes will be critical in their classification. Let {X} denote the code with generator matrix X, and k_{X} the dimension of {X}.

Theorem 2.1 Let C and C^{⊥} be codes of length n_{1} + n_{2} with the following generator matrices, G(C) and G(C^{⊥}), under the assumption that A (respectively B) and F (respectively J) generate the subcodes of C and C^{⊥} of largest dimension with support under the first n_{1} (respectively last n_{2}) coordinates:

G(C) = ( \begin{matrix}A & 0 \\ 0 & B \\ D & E \end{matrix} ) and G(C^{⊥}) = ( \begin{matrix}F & 0 \\ 0 & J \\ L & M \end{matrix} ) .

Further assume that dim C = dim C^{⊥}. Then

(a) k_{D} = k_{E} = k_{L} = k_{M},

(b) {A}^{⊥} = {F ∪ L}, {B}^{⊥} = {J ∪ M}, {F }^{⊥} = {A ∪ D}, {J}^{⊥} = {B ∪ E}, and

(c) n_{1} − 2k_{A} = n_{2} − 2k_{J}, n_{1} − 2k_{F} = n_{2} − 2k_{B}.

Also important in the classification is the concept of intersection numbers. Knowing these numbers will allow us to eliminate certain possibilities in the generator matrices. Let C be a binary linear code of length n with dual C^{⊥}. If c ∈ C, let supp(c) denote the support of c, and let wt(c) denote the weight of c. Let k and t be positive integers, and let i and w be nonnegative integers. Also let T be a set of t coordinates of the code. The following numbers are called the intersection numbers of C:

n_{w,i}(T) = |{c ∈ C | wt(c) = w, |supp(c) ∩ T | = i}|,
n_{w,i}^{∗}(T) = |{c ∈ C^{⊥} | wt(c) = w, |supp(c) ∩ T | = i}|.

i  0 1 2 3 4 5 6
n_{6,i}(T) a b c  0 0 1
n_{8,i}(T) a d c 0 0
n_{10,i}(T) 0 b d  d b 0
n_{6,i}^{∗}(T)  0  0  0
n_{8,i}^{∗}(T)  0  0  0
n_{10,i}^{∗}(T) x 0 y 0 y 0 x

Table 1: Partial intersection table for t = 6 with c(T) ∈ C when n = 20.

We will be interested in these numbers when T is the support of a codeword of weight 6, 8, or 10 and will group them into tables we call intersection tables. There are basically two methods to compute these numbers. The first method was developed by Bachoc in [1] using harmonic polynomials. The second method was described in [4] using the form of the generator matrices from Theorem 2.1 together with other information that can be deduced about the codes. We will illustrate the latter in the case of length 20.

3 Length 20

There are a total of 7 inequivalent [20,10,6] even f.s.d. codes. None of these are self-dual. In this section we outline the methods used in this classification and give generator matrices for these codes along with some of their properties in the next section.

The weight distribution of a [20,10,6] even f.s.d. code C is

A_{0} = A_{20} = 1, A_{6} = A_{14} = 90, A_{8} = A_{12} = 255, A_{10} = 332  (1)

Let T denote a set of t = 6 coordinates and c(T) the vector of length 20 with supp(c(T)) = T. In order to construct the codes, we will use the generator matrix arising in Theorem 2.1 where A = (111111); that is, we order the coordinates so that if T is the first 6 coordinates, then c(T) ∈ C. There are two possibilities to consider: either c(T) ∈ C^{⊥} or c(T) ∉ C^{⊥}. Recall that the hull of C is H = C ∩ C^{⊥}.

If T has size t = 6 such that c(T) ∈ C, Table 1 gives information for the intersection numbers n_{w,i}(T) and n_{w,i}^{∗}(T) that is easy to obtain using simple coding theory arguments. See [4] for the types of arguments used.

We first consider the case when c(T) ∈ C^{⊥}; that is, when c(T) ∈ H. Then n_{w,i}(T) = 0 for i odd by orthogonality between C and C^{⊥}. Thus the only entries among n_{w,i}(T) left to find are a, c, and d in Table 1. In Theorem 2.1 the code {B} is a [14,5,6] code which must have weight distribution a_{0} = a_{14} = 1 and a_{6} = a_{8} = 15. Therefore n_{w,0}(T) = a_{w} = 15 for w = 6 or 8; that is, a = 15. As

∑_{i=0}^{6} n_{6,i}(T) = 90

by (1), a + c + 1 = 90 implying c = 74. But by the Assmus–Mattson Theorem, the codewords of weight 6 in C hold a 1-(20,6,27) design. Therefore

∑_{i=0}^{6} in_{6,i}(T) = 6 · 27

because the left-hand side counts the total number of times the supports of codewords of weight 6 overlap the set T and this must be the right-hand side as these codewords support a 1-design. So

0 · a + 2 · c + 6 · 1 = 6 · 27,

yielding c = 78, a contradiction. We note that using the harmonic polynomials and the methods of Bachoc, we obtain a conflict also. This proves the following lemma.

Lemma 3.1 The hull of an even [20, 10, 6] f.s.d. code does not have any vectors of weight 6.

Note that this lemma shows that none of these f.s.d. codes can be self-dual consistent with the results of [9].

We now assume that c(T) ∉ C^{⊥}. In particular n_{6,6}^{∗}(T) = 0. We fill in the missing entries in Table 1. Table 2 is the final result. The code {B} is a [14,4,6] code which must have weight distribution a_{0} = a_{14} = 1 and a_{6} = a_{8} = 7. Therefore a = n_{6,0}(T) = n_{8,0}(T) = 7. Note that if v is a weight 6 vector whose support intersects T in 3 positions, so does c(T) + v, and hence n_{6,3}(T) is even and we denote its value by 2e. As above, the codewords in C (and C^{⊥}) of weight w = 6, 8, and 10 form 1-(20,w,λ_{w}) designs with λ_{6} = 27, λ_{8} = 102, and λ_{10} = 166. As above, we have

∑_{i=0}^{6} in_{w,i}(T) = 6λ_{w}  (2)
∑_{i=0}^{6} in_{w,i}^{∗}(T) = 6λ_{w}.  (3)

Also

∑_{i=0}^{6} n_{w,i}(T) = ∑_{i=0}^{6} n_{w,i}^{∗}(T) = A_{w}  (4)

where A_{w} is found in (1). Solving (2) and (4) with w = 6 yields a = n_{6,1}(T) = 8 + 2e and b = 74 − 4e.

The code {F } of Theorem 2.1 must be {0} in this case and hence by this theorem we may choose

D = ( \begin{matrix}100000 \\ 010000 \\ 001000 \\ 000100 \\ 000010 \end{matrix} ) .  (5)

Recalling that A = (111111), there are codewords in C with exactly one 1 in any of the first 6 coordinates. Such codewords must have weight 5, 7, or 9 in the right 14 coordinates as {B} contains the all-1 vector. As two such codewords that are 1 on the same position in T differ by a vector in {(0 B)}, n_{6,1}(T) + n_{8,1}(T) + n_{10,1}(T) = 6 · 2^{4} from which we deduce that n_{8,1}(T) = 80 − 4e. Now applying (2) and (4) with w = 8, we obtain d = n_{8,2}(T) = 46 + 4e and n_{8,3}(T) = 48 + 4e. Using (4) with w = 10 gives n_{10,3}(T) = 224 − 12e completing the top half of the table.

To complete the bottom half of the table, we note that {J} is a [14,5,6] code whose non-zero vectors have weights 6, 8, 10, and 12; the number of these vectors are in fact n_{6,0}^{∗}(T), n_{8,0}^{∗}(T), n_{10,0}^{∗}(T), and (by adding the all-1 codeword in C^{⊥}) n_{8,6}^{∗}(T). It is not difficult to see that {J}^{⊥} has minimum weight 3 as {J}^{⊥} = {B ∪ E} and further that e = n_{6,3}(T)/2 is the number of vectors of weight three in {J}^{⊥}. Hence by the power moments [10], we determine that n_{6,0}^{∗}(T), n_{8,0}^{∗}(T), n_{10,0}^{∗}(T), and n_{8,6}^{∗}(T) are 11+e/2, 26−3e/2, −11+3e/2, and 5−e/2, respectively. Applying (3) and (4) with w = 6 and 8 produces n_{6,2}^{∗}(T) = 77−e, n_{6,4}^{∗}(T) = 2+e/2, n_{8,2}^{∗}(T) = 157+5e/2, and n_{8,4}^{∗}(T) = 67 − e/2. Finally applying (4) with w = 10 yields n_{10,2}^{∗}(T) = n_{10,4}^{∗}(T) = 177 − 3e/2 producing Table 2. Again Bachoc’s harmonic polynomials determine the same table.

Notice that the conditions that n_{8,6}^{∗}(T) ≥ 0 and n_{10,0}^{∗}(T) ≥ 0 imply that 8 ≤ e ≤ 10; as n_{8,6}^{∗}(T) is an integer, e = 8 or 10. Thus only 2 intersection tables are actually possible. Both tables indeed occur in the codes that we found.

The intersection tables for t = 8 and t = 10 with c(T) in the hull are unique. Note that the top half and bottom half agree and that n_{w,i}(T) = n_{w,i}^{∗}(T) = 0 for i odd. These are given in Table 3.

Using methods similar to those above, we have also computed the tables of intersection numbers when c(T) is in C and not in C^{⊥} for |T | = 8 and 10.

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{6,i}(T) & 7 & 8 + 2e & 74 − 4e & 2e & 0 & 0 & 1 \\ n_{8,i}(T) & 7 & 80 − 4e & 46 + 4e & 48 + 4e & 74 − 4e & 0 & 0 \\ n_{10,i}(T) & 0 & 8 + 2e & 46 + 4e & 224 − 12e & 46 + 4e & 8 + 2e & 0 \\ n_{6,i}^{∗}(T) & 11 + \frac{e}{2} & 0 & 77 − e & 0 & 2 + \frac{e}{2} & 0 & 0 \\ n_{8,i}^{∗}(T) & 26 − \frac{3e}{2} & 0 & 157 + \frac{5e}{2} & 0 & 67 − \frac{e}{2} & 0 & 5 − \frac{e}{2} \\ n_{10,i}^{∗}(T) & −11 + \frac{3e}{2} & 0 & 177 − \frac{3e}{2} & 0 & 177 − \frac{3e}{2} & 0 & −11 + \frac{3e}{2} \end{matrix}

Table 2: Intersection table for t = 6 when n = 20 with c(T) ∈ C and c(T) ∉ C^{⊥}; e = 8 or 10.

\begin{matrix}wt(c(T)) = 8 \\ i & 0 & 2 & 4 & 6 & 8 \\ n_{6,i}(T) = n_{6,i}^{∗}(T) & 6 & 60 & 24 & 0 & 0 \\ n_{8,i}(T) = n_{8,i}^{∗}(T) & 0 & 104 & 150 & 0 & 1 \\ n_{10,i}(T) = n_{10,i}^{∗}(T) & 0 & 60 & 212 & 60 & 0 \end{matrix}  \begin{matrix}wt(c(T)) = 10 \\ i & 0 & 2 & 4 & 6 & 8 & 10 \\ n_{6,i}(T) = n_{6,i}^{∗}(T) & 0 & 45 & 45 & 0 & 0 & 0 \\ n_{8,i}(T) = n_{8,i}^{∗}(T) & 0 & 45 & 165 & 45 & 0 & 0 \\ n_{10,i}(T) = n_{10,i}^{∗}(T) & 1 & 0 & 165 & 165 & 0 & 1 \end{matrix}

Table 3: Intersection tables when n = 20, c(T) ∈ C, and c(T) ∈ C^{⊥}.

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ n_{6,i}(T) & 2 & 16 & 16 + a & 56 − 2a & a & 0 & 0 & 0 & 0 \\ n_{8,i}(T) & 0 & 16 & 80 − 2a & 56 + 2a & 46 + 2a & 56 − 2a & 0 & 0 & 1 \\ n_{10,i}(T) & 0 & 0 & 16 + a & 56 + 2a & 188 − 6a & 56 + 2a & 16 + a & 0 & 0 \\ n_{6,i}^{∗}(T) & 1 + \frac{a}{4} & 0 & 70 − \frac{a}{2} & 0 & 19 + \frac{a}{4} & 0 & 0 & 0 & 0 \\ n_{8,i}^{∗}(T) & 9 − \frac{a}{2} & 0 & 98 + \frac{a}{2} & 0 & 134 + \frac{a}{2} & 0 & 14 − \frac{a}{2} & 0 & 0 \\ n_{10,i}^{∗}(T) & −3 + \frac{a}{4} & 0 & 42 + \frac{a}{2} & 0 & 254 − \frac{3a}{2} & 0 & 42 + \frac{a}{2} & 0 & −3 + \frac{a}{4} \end{matrix}

Table 4: Intersection table for t = 8 when n = 20 with c(T) ∈ C and c(T) ∉ C^{⊥} and there are no vectors in C^{⊥} whose support is contained in T. Note that a must be either 12 or 16.

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ n_{6,i}(T) & 6 & 8 & 32 & 32 & 12 & 0 & 0 & 0 & 0 \\ n_{8,i}(T) & 0 & 8 & 64 & 88 & 62 & 32 & 0 & 0 & 1 \\ n_{10,i}(T) & 0 & 0 & 32 & 88 & 92 & 88 & 32 & 0 & 0 \\ n_{6,i}^{∗}(T) & 4 & 0 & 65 & 0 & 20 & 0 & 1 & 0 & 0 \\ n_{8,i}^{∗}(T) & 3 & 0 & 100 & 0 & 148 & 0 & 4 & 0 & 0 \\ n_{10,i}^{∗}(T) & 0 & 0 & 54 & 0 & 224 & 0 & 54 & 0 & 0 \end{matrix}

Table 5: Intersection table for t = 8 when n = 20 with c(T) ∈ C and c(T) ∉ C^{⊥} and there is a weight 6 vector in C^{⊥} whose support is contained in T.

This information is displayed for |T | = 8 in Tables 4 and 5 which give the information for the two cases: 1) there are no vectors in C^{⊥} whose support is contained in T, and 2) there is a weight 6 vector in C^{⊥} whose support is contained in T. The information for |T | = 10 is contained in Tables 6 and 7 which correspond (respectively) to the existence of weight 6 and weight 8 vectors in C^{⊥} whose support is contained in T. Note that we do not have to consider the possibility that there are no vectors in C^{⊥} whose support is contained in T because (referring to the form of the generator matrices in Theorem 2.1) {F } and {J} must both be one-dimensional. Since {A} and {B} are both one-dimensional codes each generated by complementary weight 10 codewords, their duals must be the 9 dimensional space of all even weight words of length 10. As {L} and {M} are only 8 dimensional, it follows that {F } and {J} must both be one-dimensional.

Theorem 3.2 Up to equivalence there are 7 [20, 10, 6] even f.s.d. codes, none of which is self-

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ n_{6,i}(T) & 0 & 8 & 21 & 24 + d & 37 − 2d & d & 0 & 0 & 0 & 0 & 0 \\ n_{8,i}(T) & 0 & 0 & 21 & 80 − 2d & 69 + 2d & 48 + 2d & 37 − 2d & 0 & 0 & 0 & 0 \\ n_{10,i}(T) & 1 & 0 & 0 & 24 + d & 69 + 2d & −6d + 144 & 69 + 2d & 24 + d & 0 & 0 & 1 \\ n_{6,i}^{∗}(T) & −1 + \frac{d}{4} & 0 & 48 − \frac{d}{2} & 0 & 42 + \frac{d}{4} & 0 & 1 & 0 & 0 & 0 & 0 \\ n_{8,i}^{∗}(T) & 2 − \frac{d}{4} & 0 & −4 + \frac{d}{2} + x & 0 & 257 − \frac{d}{4} − 2x & 0 & x & 0 & 0 & 0 & 0 \\ n_{10,i}^{∗}(T) & 0 & 0 & 46 − x & 0 & 120 + x & 0 & 120 + x & 0 & 46 − x & 0 & 0 \end{matrix}

Table 6: Intersection table for t = 10 when n = 20 with c(T) ∈ C and c(T) ∉ C^{⊥} and there is a weight 6 vector in C^{⊥} whose support is contained in T; d = 4 or 8 and 0 ≤ x ≤ 46.

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ n_{6,i}(T) & 0 & 4 & 29 & 20 + d & 37 − 2d & d & 0 & 0 & 0 & 0 & 0 \\ n_{8,i}(T) & 0 & 0 & 29 & 72 − 2d & 61 + 2d & 56 + 2d & 37 − 2d & 0 & 0 & 0 & 0 \\ n_{10,i}(T) & 1 & 0 & 0 & 20 + d & 61 + 2d & 168 − 6d & 61 + 2d & 20 + d & 0 & 0 & 1 \\ n_{6,i}^{∗}(T) & −1 + \frac{d}{4} & 0 & 47 − \frac{d}{2} & 0 & 44 + \frac{d}{4} & 0 & 0 & 0 & 0 & 0 & 0 \\ n_{8,i}^{∗}(T) & 2 − \frac{d}{4} & 0 & 42 + \frac{d}{2} − x & 0 & 166 − \frac{d}{4} + 2x & 0 & 44 − x & 0 & 1 & 0 & 0 \\ n_{10,i}^{∗}(T) & 0 & 0 & x & 0 & −x + 166 & 0 & −x + 166 & 0 & x & 0 & 0 \end{matrix}

Table 7: Intersection table for t = 10 when n = 20 with c(T) ∈ C and c(T) ∉ C^{⊥} and there is a weight 8 vector in C^{⊥} whose support is contained in T; d = 4 or 8 and 0 ≤ x ≤ 44. dual.

Proof: In view of the preceding results we know that for any even f.s.d. code C, there is a weight 6 vector c in C which does not belong to C^{⊥}. Reordering columns so that the support of c is in the first 6 positions, we see by Theorem 2.1 that C has a generator matrix of the form

G(C) = ( \begin{matrix}111111 & 0 ⋯ 0 \\ 0 & B \\ 100000 \\ 010000 \\ 001000 & E \\ 000100 \\ 000010 \end{matrix} )

where {B} is a [14,4,6] code with weight distribution a_{0} = a_{14} = 1 and a_{6} = a_{8} = 7. It is easy to prove by hand or with an exhaustive computer search that there are only two such codes up to permutation, which have generator matrices B = B_{i} where:

B_{1} = ( \begin{matrix}11001101111000 \\ 00101101100111 \\ 00011100011111 \\ 00000011111111 \end{matrix} ) or B_{2} = ( \begin{matrix}11000000001111 \\ 00100100111100 \\ 00011000110011 \\ 00000011111111 \end{matrix} ) .

With the same argument used in [4], the rows of E can be chosen modulo the code {B_{i}}. Since we want the minimum weight of the even f.s.d. code to be 6 or more, the rows of E can be chosen from the set CS_{i} of the coset leaders of the code {B_{i}} with odd weight 5 or more.

For {B_{1}} there are 200 coset leaders of weight 5 and for {B_{2}} there are 196 coset leaders of weight 5 and 8 coset leaders of weight 7. Therefore if we apply a brute force method to test all the different possible codes, there are 5 rows of E to determine and therefore about \frac{200^{5}}{5!} possibilities for each choice of B, if we order them, which is more than 250 × 10^{6} cases. This is beyond the actual capability of our computers.

We define an intermediate code of order k to be a [20, 5 + k, 6] code whose generator matrix is given by the first 5 + k rows of the matrix G(C), and where the first k rows of the matrix E are filled with k elements of CS_{1} or CS_{2} defining a k × 14 submatrix of E.

We use the following lemma to limit the number of cases to consider:

Lemma 3.3 Let 1 ≤ k ≤ 4 and let us consider two intermediate codes of order k, C_{1} and C_{2}, wich are equivalent under the permutation P and have respective submatrices E_{1} and E_{2}. Suppose the permutation P leaves the set of the first 6 columns invariant. Then any code with generator matrix G(C) where the first k rows of E are E_{1}, and where the remaining 5−k rows of E are filled with elements of CS_{i}, is equivalent to a code with generator matrix G(C) and where the first k rows of E are E_{2}.

Proof: Let G(C_{i}) be the generator matrix of C_{i} whose form is the same as the first 5 + k rows of G(C). Since the permutation P leaves the first 6 columns invariant as a set (and hence the last 14 columns, as well), P sends the first row of G(C_{1}) to the first row of G(C_{2}). It also must fix the code generated by (0 B) and send codewords of weight 1 on the first six coordinates to codewords of weight 1 on these same coordinates. Thus by observing the form of G(C_{i}), P must in fact leave invariant the first k columns. Therefore the k rows of (0 E_{1}) are sent to the rows of (0 E_{2}), in some order, modulo the code generated by (0 B). This proves the lemma. □

Remark: It turns out that in the following (we checked it each time with a computer), as soon as two intermediate codes are equivalent then the first 6 columns remain unchanged by the permutation.

We now proceed row by row for the determination of E, using the preceding lemma.

Let us first consider the case {B} = {B_{1}}. For the first row there are 200 possibilities, which are reduced to only 4 inequivalent cases, after using the preceding lemma and checking the equivalence. For the second row, we start from these 4 possibilities. For each of these 4 cases we consider the 200 possibilities from the set CS_{1}, and we check the possible equivalence of the intermediate codes of order 2, obtaining 4 sets of codes, for which then again we check the equivalence between codes in these 4 sets. We then obtain a set of only 41 codes to consider for the intermediate codes of order 2. Repeating the process for the third row we obtain a set of 225 possible intermediate codes for the first 3 rows. It is now possible to check all the possibilities for the 2 remaining rows. For each of the 225 ∗ \frac{200∗200}{2} possibilities we check to see if the weight enumerator is (1). As we obtain codes satisfying (1), we check equivalence among them to obtain a list with only 7 inequivalent codes.

The same method applied to B_{2} leads to the same seven codes and therefore proves the result.

□

C  dim(C ∩ C^{⊥}) Weight enumerator of C ∩ C^{⊥} |Aut(C)| CR
fsd20 2a  2  x^{20} + 2x^{10}y^{10} + y^{20}  2^{3}  5
fsd20 2b  2  x^{20} + 2x^{10}y^{10} + y^{20}  2^{3}  4
fsd20 2c  2  x^{20} + 2x^{10}y^{10} + y^{20}  2 · 5  5
fsd20 2d  2  x^{20} + 2x^{10}y^{10} + y^{20}  2 · 5  4
fsd20 2e  2  x^{20} + 2x^{10}y^{10} + y^{20}  2 · 5  5
fsd20 2f  2  x^{20} + 2x^{10}y^{10} + y^{20}  2^{2} · 5  5
fsd20 4  4  x^{20} + 3x^{12}y^{8} + 8x^{10}y^{10} + ⋯  3^{2}  4

Table 8: The 7 even extremal [20,10,6] f.s.d. codes

4 Enumeration of [20,10,6] Even F.s.d. Codes

In this section we enumerate the [20,10,6] even f.s.d. codes.

Most of these codes have the same hull H up to equivalence, so that we also give the covering radius to help distinguish the codes from one another. Table 8 gives the list of the codes, the dimension of H, the weight enumerator of H, the order of the automorphism group of C, and the covering radius (CR). All of these codes are isodual (equivalent to their dual) and 2 of them are pure double circulant [5].

In the previous section we determined all of the intersection tables that can occur in an even extremal [20,10,6] code. It is interesting, in view of what we computed theoretically, to see which intersection tables actually occur and their distribution among the seven codes; this data is presented in Table 9. The distribution is simply an enumeration giving the number of vectors in the code which, when used to define the partition T, produce a given table of intersection numbers. For example, the 90 codewords of weight 6 split into two groups: there are 30 codewords whose support give intersection numbers from Table 2 with e = 8 and 60 codewords whose supports give intersection numbers from Table 2 with e = 10. This is a computationally expensive invariant to determine. Only two distinct distributions of intersection tables occur among the seven codes. The two codes, fsd20 2c and fsd20 2e, which have the same automorphism group order and hull dimension also have the same distribution of intersection tables.

We note that the constraints on the entries in the intersection tables were sharp for t = 6 and 8, i.e., we saw (by considering integrality and non-negativity) that the variables in Tables 2 and 4 could only take certain values – and the tables which we actually found in the seven codes

t = 6  \begin{matrix}Table 2 \\ e = 8 \end{matrix}  \begin{matrix}Table 2 \\ e = 10 \end{matrix}
t = 8  \begin{matrix}Table 4 \\ a = 12 \end{matrix}  \begin{matrix}Table 4 \\ a = 16 \end{matrix}  Table 5  \begin{matrix}Table 3 \\ t = 8 \end{matrix}
t = 10 \begin{matrix}Table 6 \\ d = 8, x = 37 \end{matrix}  \begin{matrix}Table 6 \\ d = 4, x = 40 \end{matrix}  \begin{matrix}Table 7 \\ d = 8, x = 6 \end{matrix}  \begin{matrix}Table 3 \\ t = 10 \end{matrix}

\begin{matrix}t = 6 & 30 & 60 \\ t = 8 & 165 & 60 & 30 & 0 \\ t = 10 & 210 & 60 & 60 & 2 \end{matrix}  and  \begin{matrix}t = 6 & 27 & 63 \\ t = 8 & 180 & 45 & 27 & 3 \\ t = 10 & 234 & 45 & 45 & 8 \end{matrix}

Table 9: The two distributions of intersection tables that appear in the seven even extremal f.s.d. codes of length 20. The upper array serves as a template, giving the intersection table which corresponds to a given entry in one of the lower arrays.

represented all of the possible values. For t = 10 the situation is different; the variable x in Tables 6 and 7 which can take over 40 values, actually only takes on a very small number of values. Also, the value d = 4 in Table 7 is not ruled out by theoretical considerations; yet no intersection table corresponding to that value occurs in the seven codes.

We give the generator matrices of the seven codes in the form described in the last section. The first six codes have a hull of dimension 2 which is equivalent to a code with generator matrix of the form:

Hull(fsd20 2∗) = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} )

• Dimension (C ∩ C^{⊥}) = 2

fsd20 2a = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \end{matrix} )

fsd20 2b = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \end{matrix} )

fsd20 2c = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \end{matrix} )

fsd20 2d = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \end{matrix} )

fsd20 2e = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \end{matrix} )

fsd20 2f = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \end{matrix} )

• Dimension (C ∩ C^{⊥}) = 4

fsd20 4 = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \end{matrix} )

Hull(fsd20 4) = ( \begin{matrix}1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix} )

5 Length 22

For length 22 we know from the classification of [11] that there is only one self-dual [22,11,6] code up to equivalence. We have found more than 1000 inequivalent [22,11,6] even f.s.d. codes (none of them is self-dual), and there seem to be many more. Moreover it is worth noticing that length 22 is the first length for which there are non-isodual extremal even f.s.d. codes. Since a complete classification is impractical, we review the general method we used for constructing these codes. In the next section we give some information about the incomplete list of codes that we found. We also give some examples of codes with special interesting parameters.

The intersection tables are unique for the cases t = 6, 8, and 10 when c(T) ∈ C and c(T) ∈ C^{⊥}. In each case n_{w,i}(T) = n_{w,i}^{∗}(T) = 0 if i is odd, and n_{w,i}(T) = n_{w,i}^{∗}(T). We present the results in Table 10.

In the situation where |T | = 6 and c(T) is in C but not in C^{⊥}, we calculated the intersection tables in terms of three variables. This information is given in Table 11. Since two weight 8 codewords in C^{⊥} cannot have 1’s on a common 6 positions, d = 0 or d = 1. Since the entries

\begin{matrix}wt(c(T)) = 6 \\ i & 0 & 2 & 4 & 6 \\ n_{6,i}(T) = n_{6,i}^{∗}(T) & 16 & 60 & 0 & 1 \\ n_{8,i}(T) = n_{8,i}^{∗}(T) & 30 & 240 & 60 & 0 \\ n_{10,i}(T) = n_{10,i}^{∗}(T) & 16 & 360 & 240 & 0 \end{matrix}  \begin{matrix}wt(c(T)) = 8 \\ i & 0 & 2 & 4 & 6 & 8 \\ n_{6,i}(T) = n_{6,i}^{∗}(T) & 7 & 56 & 14 & 0 & 0 \\ n_{8,i}(T) = n_{8,i}^{∗}(T) & 7 & 168 & 154 & 0 & 1 \\ n_{10,i}(T) = n_{10,i}^{∗}(T) & 0 & 168 & 392 & 56 & 0 \end{matrix}

wt(c(T)) = 10
i 0 2 4 6 8 10
n_{6,i}(T) = n_{6,i}^{∗}(T) 2 45 30 0 0 0
n_{8,i}(T) = n_{8,i}^{∗}(T) 0 90 210 30 0 0
n_{10,i}(T) = n_{10,i}^{∗}(T) 0 45 360 210 0 1

Table 10: Intersection tables when n = 22, c(T) ∈ C, and c(T) ∈ C^{⊥}.

are nonnegative integers, when d = 0, we find 2 ≤ a ≤ 10 and 0 ≤ b ≤ 7, and when d = 1, we have 0 ≤ a ≤ 6 and 0 ≤ b ≤ 6, giving a total of 121 possible tables. We examined ten of our 1000 f.s.d. codes and found 43 of these intersection tables; we suspect that many others actually arise. We did not compute the possible intersection tables for t = 8 or 10 and c(T) ∉ C^{⊥} but suspect that they will be even more complicated.

Theorem 5.1 There are at least 1000 inequivalent [22, 11, 6] even f.s.d. codes.

Proof: Let C be an [22,11,6] even f.s.d. code. Suppose that there is a word of weight 6 not in the hull of C. Then by using Theorem 2.1 the code C has, up to equivalence, a generator matrix of the form:

G(C) = ( \begin{matrix}111111 & 0 ⋯ 0 \\ 0 & B \\ 100000 \\ 010000 \\ 001000 & E \\ 000100 \\ 000010 \end{matrix} )

where {B} is a [16,5,6] code.

We apply the same method as for length 20. It is not difficult to see, with a computer search,

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{6,i}(T) & 2b + 2d & 36 − 2b − 6d & 40 − 2a + 4d & 2a & 0 & 0 & 1 \\ n_{8,i}(T) & 30 − 4b − 4d & 60 + 2b + 6d & \begin{matrix}80 + 8a− \\ 2b + 14d \end{matrix} & \begin{matrix}120 − 6a+ \\ 4b − 20d \end{matrix} & 40 − 2a + 4d & 0 & 0 \\ n_{10,i}(T) & 2b + 2d & 60 + 2b + 6d & \begin{matrix}240 − 12a+ \\ 4b − 36d \end{matrix} & \begin{matrix}200 + 4a− \\ 4b + 20d \end{matrix} & \begin{matrix}80 + 8a− \\ 2b + 14d \end{matrix} & 36 − 2b − 6d & 0 \\ n_{6,i}^{∗}(T) & 12 + a + d & 0 & \begin{matrix}65 − a− \\ b − d \end{matrix} & 0 & b & 0 & 0 \\ n_{8,i}^{∗}(T) & 45 − 3a − 4d & 0 & \begin{matrix}220 + a+ \\ 5b + 4d \end{matrix} & 0 & \begin{matrix}65 + 2a− \\ 5b − d \end{matrix} & 0 & d \\ n_{10,i}^{∗}(T) & −4 + 3a + 6d & 0 & \begin{matrix}390 + 3a− \\ 10b − 6d \end{matrix} & 0 & \begin{matrix}220 − 5a+ \\ 10b + 4d \end{matrix} & 0 & 10 − a − 4d \end{matrix}

Table 11: Intersection table for n = 22, t = 6 with c(T) ∈ C and c(T) ∉ C^{⊥}, with d = 0 or d = 1.

that there are only 11 possible codes {B} = {B_{i}}. Again the rows of E can be chosen modulo the code {B_{i}}. Since we want the minimum weight of the even f.s.d. code to be 6 or more, the rows of E can be chosen from the set CS_{i} of the coset leaders of the code {B_{i}} with odd weight 5 or more.

For each of the 11 codes {B_{i}} there are about 500 coset leaders of weight 5 or more, making an exhaustive search even more difficult than for length 20. We tried several codes {B_{i}} and completed the corresponding matrices E. Using the same method of the intermediate code described in Section 3 to make the search more efficient, it quickly turned out that the number of inequivalent [22,11,6] even f.s.d. codes was very large. We stopped our search after finding 1000 inequivalent ones. □

6 Description of Some [22,11,6] Even F.s.d. Codes

In this section we give some general data concerning the 1000 [22,11,6] even f.s.d. codes that we found. We also describe three of the particularly interesting codes.

Since it is impractical to enumerate the 1000 codes, we only give statistics for three parameters: the dimension of the hull (Table 12), the order of the automorphism group (Table 13), and whether the codes are isodual or not (Table 14). All the codes we found had the same

dim(C ∩ C^{⊥})  1  3 5 7+
Number of codes 457 491 52 0

Table 12: Dimension of the hull.

|Aut(C)|  1 2 4 16 24
Number of codes 972 19 7 1 1

Table 13: Automorphism group order.

covering radius 5. We also give in Table 15 a list of the 9 different weight enumerators of hulls of dimension 5 that we found.

Among the codes that we found only two have an automorphism group order of 16 or more; there is only one code whose hull has dimension 1 whose automorphism group has order 4 or more. We give more detail on these three codes in Table 16.

fsd22 1 = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} )

dim(C ∩ C^{⊥})  1 3 5
Number of isodual codes 18 11 8

Table 14: Isoduality. x^{22} + x^{16}y^{6} + 6x^{14}y^{8} + 8x^{12}y^{10} + 8x^{10}y^{12} + 6x^{8}y^{14} + x^{6}y^{16} + y^{22} x^{22} + x^{16}y^{6} + 10x^{14}y^{8} + 4x^{12}y^{10} + 4x^{10}y^{12} + 10x^{8}y^{14} + x^{6}y^{16} + y^{22}

x^{22} + x^{16}y^{6} + 14x^{14}y^{8} + 14x^{8}y^{14} + x^{6}y^{16} + y^{22}

x^{22} + 2x^{16}y^{6} + 3x^{14}y^{8} + 10x^{12}y^{10} + 10x^{10}y^{12} + 3x^{8}y^{14} + 2x^{6}y^{16} + y^{22} x^{22} + 2x^{16}y^{6} + 7x^{14}y^{8} + 6x^{12}y^{10} + 6x^{10}y^{12} + 7x^{8}y^{14} + 2x^{6}y^{16} + y^{22} x^{22} + 3x^{16}y^{6} + 4x^{14}y^{8} + 8x^{12}y^{10} + 8x^{10}y^{12} + 4x^{8}y^{14} + 3x^{6}y^{16} + y^{22} x^{22} + 3x^{16}y^{6} + 8x^{14}y^{8} + 4x^{12}y^{10} + 4x^{10}y^{12} + 8x^{8}y^{14} + 3x^{6}y^{16} + y^{22}

x^{22} + 5x^{14}y^{8} + 10x^{12}y^{10} + 10x^{10}y^{12} + 5x^{8}y^{14} + y^{22}

x^{22} + 9x^{14}y^{8} + 6x^{12}y^{10} + 6x^{10}y^{12} + 9x^{8}y^{14} + y^{22}

Table 15: The nine different weight enumerators for hulls of dimension 5.

C  dim(C ∩ C^{⊥})  Weight enumerator of C ∩ C^{⊥}  |Aut(C)| CR isodual
fsd22 1  1  x^{22} + y^{22}  2^{2}  5  no
fsd22 5a  5  x^{22} + x^{16}y^{6} + 14x^{14}y^{8} + 14x^{8}y^{14} + ..  2^{4}  5  yes
fsd22 5b  5  x^{22} + 2x^{16}y^{6} + 7x^{14}y^{8} + 6x^{12}y^{10} + .. 2^{3} · 3  5  no

Table 16: 3 particular even extremal [22,11,6] f.s.d. codes

fsd22 5a = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} )

Hull(fsd20 5a) = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \end{matrix} )

fsd22 5b = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} )

Hull(fsd20 5b) = ( \begin{matrix}1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \end{matrix} )

7 An updated table

In this section we update the table of [4] at lengths 20 and 22 which were investigated in this paper.

length d sd other  hull  iso  dc  references
2  2 1  0  1  yes  yes  [7]
4  2 1  0  2  yes  yes  [7]
6  2 1  1  1,3  yes  yes  [7]
8  4 1  0  4  yes  yes  [7]
10  4 0  1  1  yes  yes  [7]
12  4 1  2  2,4,6  yes  yes  [1], [12]
14  4 1  9  1,3,5,7  yes  2  [4]
16  6 0  0  -  -  -  [3]
18  6 0  1  1  yes  yes  [7], [14]
20  6 0  7  2,4  yes  2  §3
22  6 1 ≥ 1000 1,3,5,?,11 yes,? no,yes,? §5, [11], [7]
24  8 1  0  12  yes  yes  [8]
26  8 0  0  -  -  -  [3]
28  8 0  1  2  yes  yes  [6]
30  8 0  ≥ 1  3,?  yes,?  yes,?  [7]

Table 17: The extremal even f.s.d. codes for n ≤ 30.

ACKNOWLEDGMENT

We thank the Institute for Mathematics and Its Applications at the University of Minnesota for its hospitality and support during part of the time this paper was written.

Extensive computations were performed with the MAGMA [2] system, some computations were also performed with the GAP [13] system.

References

[1] C. Bachoc, “On harmonic weight enumerators of binary codes,” preprint.

[2] W. Bosma and J. Cannon, Handbook of Magma Functions, Sydney, 1995.

[3] A. E. Brouwer, “Bounds on the size of linear codes,” Handbook of Coding Theory, edited by V. Pless and W. C. Huffman, North Holland, Amsterdam, 1998.

[4] J. E. Fields, P. Gaborit, W. C. Huffman, and V. Pless, “On the classification of extremal even formally self-dual codes,” preprint.

[5] T.A. Gulliver and M. Harada, “ Classification of extremal double circulant formally self-dual even codes,” Designs, Codes and Cryptography 11 (1997), 25–35.

[6] D. Jaffe, “Optimal binary linear codes of length ≤ 30,” to appear in Discrete Math.

[7] G. T. Kennedy and V. Pless, “On designs and formally self-dual codes,” Designs, Codes and Cryptography 4 (1994), 43–55.

[8] V. Pless, “On the uniqueness of the Golay codes,” J. Comb. Theory Ser. A 5 (1968), 215– 228.

[9] V. Pless, “A classification of self-orthogonal codes over GF(2),” Discrete Math. 3 (1972), 209–246.

[10] V. Pless, Introduction to the Theory of Error Correcting Codes, Wiley, New York, 3rd edition, 1998.

[11] V. Pless and N.J.A. Sloane, “On the classification and enumeration of self-dual codes”, J. Comb. Theory Ser. A 18 (1975), 313–335.

[12] E. M. Rains and N. J. A. Sloane, “Self-dual codes,” Handbook of Coding Theory, edited by V. Pless and W. C. Huffman, North Holland, Amsterdam, 1998.

[13] M. Schönert et al., GAP – Groups, Algorithms, and Programming. Lehrstuhl D für Mathematik, Rheinisch Westfälische Technische Hochschule, Aachen, Germany, 5th edition, 1995.

[14] J. Simonis, “The [18,9,6] code is unique,” Discrete Math. 106/107 (1992), 439–448.