On the classification of extremal even formally self-dual codes

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

September 17, 1998

In memory of Ed Assmus

Abstract

Bachoc [2] has recently introduced harmonic polynomials for binary codes. Computing these for extremal even formally self-dual codes of length 12, she found intersection numbers for such codes and showed that there are exactly three inequivalent [12,6,4] even formally self-dual codes, exactly one of which is self-dual. We prove a new theorem which gives a generator matrix for formally self-dual codes. Using the Bachoc polynomials we can obtain the intersection numbers for extremal even formally self-dual codes of length 14. These same numbers can also be obtained from the generator matrix. We show that there are precisely ten inequivalent [14,7,4] even formally self-dual codes, only one of which is self-dual.

1 Introduction

In this paper we present a form for generator matrices of formally self-dual codes which generalizes a similar form already known for self-dual codes [12]. We then use this theorem to construct the [14,7,4] even formally self-dual codes. In [2], Bachoc introduced the concept of harmonic polynomials for binary codes and proved a MacWilliams/Gleason type theorem for these polynomials. These polynomials provided systems of linear equations whose solutions gave the intersection numbers for the extremal even formally self-dual codes of length 12. We find the corresponding harmonic polynomials, systems of linear equations, and consequently the intersection numbers for the [14,7,4] even formally self-dual codes. Inspired by the solutions to these systems of equations, beginning with the form of the generator matrix, we produced equivalent linear equations leading to the same intersection numbers using purely coding theoretic techniques.

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

†INRIA - Department of Mathematics, Statistics, and Computer Science, 322 SEO, University of Illinois–Chicago, 851 S. Morgan, Chicago, IL 60607-7045, USA; e -mail:

gaborit@math.uic.edu

‡Department of Mathematical and Computer Sciences, Loyola University, Chicago, IL 60626, USA; e-mail: wch@math.luc.edu

In Section 2, we present preliminary notation and the generator matrix for formally self-dual codes. In Section 3, we describe the classification of the [14,7,4] even formally self-dual codes. In Section 4, we give Bachoc’s harmonic polynomials and the equations whose solutions lead to the intersection numbers. We then show how the same numbers can be obtained directly from the generator matrix. More information on the ten [14,7,4] even formally self-dual codes is given in Section 5. In Section 6 we present a table giving information on the extremal even formally self-dual codes of lengths less than or equal to 30, and a theorem which gives conditions on the dimension of C ∩ C^{⊥}.

2 Generator Matrices

A code C is called formally self-dual (or f.s.d.) if the weight distribution of C equals that of C^{⊥} [7]. If C is a binary doubly-even f.s.d. code, then C is self-dual. However, if all the weights in C are even but not all doubly-even, then C will be either a Type I self-dual code or a non-self-dual f.s.d. code. It is difficult to classify all f.s.d. codes of a given length up to equivalence since there is no known mass formula for them.

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. It is known that at certain lengths, for example 10, 18, 20, 28 and 30, there are extremal f.s.d. codes but not extremal self-dual codes. With our results on extremal f.s.d. codes of length 14, all extremal even f.s.d. codes of length n ≤ 18 are known. We begin with a new theorem which we use to classify these codes of length 14. 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 n_{1} (respectively n_{2}):

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}.

Proof: From the assumption that A and B generate the subcodes of C of largest dimension with supports n_{1} and n_{2}, it follows that k_{D} = k_{E}. Similarly k_{L} = k_{M}. Notice that dim{F ∪ L} = k_{F} + k_{L} by the assumption that F and J have maximal dimension with supports n_{1} and n_{2}.

Clearly {F ∪ L} ⊆ {A}^{⊥} and {B ∪ E} ⊆ {J}^{⊥}. Hence k_{F} + k_{L} ≤ n_{1} − k_{A} and k_{B} + k_{E} ≤ n_{2} − k_{J} so that k_{A} + k_{F} + k_{L} + k_{J} + k_{B} + k_{E} ≤ n_{1} + n_{2}. As dim C = dim C^{⊥},

\frac{n_{1} + n_{2}}{2} = k_{A} + k_{B} + k_{E} = k_{F} + k_{J} + k_{L}  (1)

which shows that all the inequalities above are equalities and all the containments are also equalities. Similar arguments hold for the other equalities in part (b).

As n_{1} = k_{A} + k_{F} + k_{L} and also n_{1} = k_{F} + k_{A} + k_{D}, it follows that k_{L} = k_{D} demonstrating part (a).

Using part (a) and (1) we have k_{A} + k_{B} = k_{F} + k_{J}. We also know that n_{1} = k_{A}+k_{F} +k_{L} and n_{2} = k_{B}+k_{J} +k_{L}. Hence n_{1}−(k_{A}+k_{F}) = n_{2}−(k_{B}+k_{J}) = n_{2} − (k_{B} + k_{A} + k_{B} − k_{F}) which demonstrates the first statement in (c). The second statement can be shown similarly. □

Theorem 2.1 is a generalization of a similar result for self-dual codes [12].

3 Classification of the [14,7,4] f.s.d. Even Codes

Let C be a [14, 7, 4] even f.s.d. code. Its weight enumerator is

WC(x, y) = x^{14} + 14x^{10}y^{4} + 49x^{8}y^{6} + 49x^{6}y^{8} + 14x^{4}y^{10} + y^{14}.  (2)

It is known [7] that the vectors of a fixed weight in C ∪ C^{⊥} hold a 1-design. Following Assmus and Key [1], we call H = C ∩ C^{⊥} the hull of C. The following is a useful result on dim H holding for arbitrary codes.

Lemma 3.1 Let C and C^{⊥} be even binary codes of length n and dimension n/2. If C is not self-dual, then dim(C ∩ C^{⊥}) = dim H ≤ n/2 − 2.

Proof: If not then dim H = n/2 − 1. Extend a basis B of H to a basis of C by adjoining x ∈ C \ C^{⊥} to B. As C is even, x is orthogonal to itself. As x is in C, it is orthogonal to C^{⊥}, and hence to B. Thus x is orthogonal to a basis of C, implying x ∈ C^{⊥}, a contradiction. □

With the assistance of this lemma, we present a result that helps narrow the possibilities for the generator matrix of even f.s.d. codes of length 14.

Lemma 3.2 Let C be an f.s.d. even code of length 14 that is not self-dual. Then there exists a codeword of C of weight 4 that is not in C^{⊥}.

Proof: As C is not self-dual, dim(C∩C^{⊥}) = dim H ≤ 5 by Lemma 3.1. Suppose that weight 4 vectors in C are also in C^{⊥}. Then as the all-one vector is in the hull, H would contain at least 30 vectors, 14 of weight 4, 14 of weight 10, and 1 each of weights 0 and 14. So dim H would have to be exactly 5, which means that H would contain exactly one vector of weight 8.

Let c be a weight 4 vector in C and hence in H. Rearrange coordinates so that the first row of the generator matrix G(C) in Theorem 2.1 is c and A = (1111). Then n_{1} = 4, n_{2} = 10 and k_{B} = 4. Further, {B} contains the all-one vector of length 10, so that it has 7 vectors of weight 4 (corresponding to 7 vectors of weight 4 in C which must all be in H) and 7 vectors of weight 6. The 7 weight 8 vectors obtained by adding c to these 7 of weight 4 in H give 7 weight 8 vectors in H, a contradiction. □

Theorem 3.3 Up to equivalence there are 10 [14, 7, 4] even f.s.d. codes, one of which is self-dual.

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

G(C) = ( \begin{matrix}1111 & 0 ⋯ 0 \\ 0 & B \\ 1000 \\ 0100 & E \\ 0010 \end{matrix} )

where dim{B} = 3. As the all-one vector of length 10 is in {B}, its weight distribution is a_{0} = a_{10} = 1, a_{4} = a_{6} = 3. Hence, up to equivalence, B has two possible forms:

B_{1} = ( \begin{matrix}1111000000 \\ 0000111111 \\ 1100110000 \end{matrix} ) or B_{2} = ( \begin{matrix}1111000000 \\ 0000111111 \\ 1000111000 \end{matrix} ) .

As {B} contains the all-one vector of length 10, we may assume the rows of E have weights 3 and 5. We used both B_{1} and B_{2} for B and considered all vectors W of length 10 and weights 3 and 5 for the rows of E (say e_{1}, e_{2}, e_{3}) in order to determine generator matrices for all possible C. However, there are too many possibilities to check as W contains \binom{10}{5} + \binom{10}{3} = 372 vectors. We reduced this number by two main shortcuts.

First, from the structure of the matrix G(C), we know that in fact the rows of E only need to be chosen modulo addition of vectors in {B}. Rather than using W, we consider a set W_{1} such that

W = Words of weight 3 and 5 in the set {b + w_{1} | b ∈ {B}, w_{1} ∈ W_{1}}.

More generally the problem of finding a minimum size set W_{1} is known as the ‘lotto’ problem [5]. But even if the set we obtained was not optimum, using W_{1} rather than W allowed us to cut the number of vectors of W by more than one third.

The second shortcut comes from the fact that the first row e_{1} of E can be chosen ‘up to’ the automorphism group of {B}. Indeed if e′_{1} and e_{1} are two vectors of W_{1} such that e′_{1} = g.e_{1} with g ∈ Aut({B}), for any code C associated to a given matrix E with first row e_{1}, there is a code C′ equivalent to C with associated matrix E′ having first row e′_{1}. Therefore for the first row we consider a set W_{2} such that

W_{1} = Words of weight 3 and 5 in the set {g.w_{2} | w_{2} ∈ W_{2}, g ∈ Aut({B})}.

Here again the set W_{2}, even if it is not optimal, cuts the number of choices for the first row by one fourth.

We searched through all possibilities using W_{2} for the first row of E and W_{1} for the second and third rows, keeping all the inequivalent codes. We found 9 inequivalent non-self-dual even f.s.d. codes. In fact, the same 9 codes were found in each separate case B_{1} and B_{2} used for B. Since in the case of f.s.d. codes, there is no known mass formula, the computation has been checked three times independently with the MAGMA [3] and GAP [15] systems, and a C language program. These 9 + 1 [14, 7, 4] even f.s.d. codes are enumerated with their properties in Section 5. □

4 Structure of [14,7,4] f.s.d. Even Codes

In [2] Bachoc developed harmonic weight enumerators for binary codes. From these weight enumerators arise systems of equations whose solutions give useful invariants, called intersection numbers, associated with a code. In this section we derive these numbers (for extremal even f.s.d. codes of length 14) from two points of view: from the Bachoc polynomials and from Theorem 2.1.

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. In what follows k and t are positive integers, and i and w are nonnegative integers. Also let T be a set of t coordinates of the code. The following numbers are invariants of the code C, 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}|.

These quantities are also calculated in studies of the split weight enumerator of a code [6].

Define the Hahn polynomial Q_{k}^{t}(x) by

Q_{k}^{t}(x) = w_{k} ∑_{j=0}^{k}(−1)^{j}\binom{k}{j}\binom{n + 1 − k}{j}\binom{t}{j}^{−1}\binom{n − t}{j}^{−1}\binom{x}{j},

where w_{k} = \binom{n}{k} − \binom{n}{k−1}. From these Hahn polynomials, define the rational numbers

h_{k,t}(w, i)

= \frac{1}{λ_{k,t}} ∑_{I} \binom{i}{i_{1}}\binom{t − i}{i_{2}}\binom{w − i}{i_{3}}\binom{n − w − t + i}{t − i_{1} − i_{2} − i_{3}}\binom{i_{1} + i_{3}}{k}Q_{k}^{t}(t − i_{1} − i_{2}),

where λ_{k,t} = \binom{n−2k}{t−k} and I = \{i_{1}, i_{2}, i_{3} | 0 ≤ i_{1} ≤ i, 0 ≤ i_{2} ≤ t − i, 0 ≤ i_{3} ≤ w − i, i_{1} + i_{2} + i_{3} ≤ t, i_{1} + i_{3} ≥ k}. Finally, for 1 ≤ k ≤ t ≤ n/2, define the harmonic weight enumerators of C and C^{⊥} by

W_{C,k,T} (x, y) = ∑_{w=0}^{n}(∑_{i=0}^{t} h_{k,t}(w, i)n_{w,i}(T))x^{n−w}y^{w},  (3)

W_{C⊥,k,T} (x, y) = ∑_{w=0}^{n}(∑_{i=0}^{t} h_{k,t}(w, i)n_{w,i}^{∗}(T))x^{n−w}y^{w}.  (4)

Note that the term x^{n−w}y^{w} can occur in W_{C,k,T} (respectively, W_{C⊥,k,T}) only

if w is the weight of a codeword in C (respectively, C^{⊥}).

In Theorem 2.1, Corollary 2.2, and Lemma 3.2 of [2], the following is proved.

Theorem 4.1 Let C be a binary linear code of length n. Let T be a set of size t. Then for 1 ≤ k ≤ t ≤ n/2,

W_{C,k,T} (x, y) = (xy)^{k}Z_{C,k,T} (x, y)

where Z_{C,k,T} (x, y) is a homogeneous polynomial of degree n − 2k. Furthermore if C is an even f.s.d. code, then

(a) for k even,

Z_{C,k,T} (x, y) + Z_{C⊥,k,T} (x, y) ∈ ℂ[P_{2}, P_{8}] and
Z_{C,k,T} (x, y) − Z_{C⊥,k,T} (x, y) ∈ Q_{4}ℂ[P_{2}, P_{8}];

(b) for k odd,

Z_{C,k,T} (x, y) + Z_{C⊥,k,T} (x, y) ∈ Q_{8}ℂ[P_{2}, P_{8}] and
Z_{C,k,T} (x, y) − Z_{C⊥,k,T} (x, y) ∈ R_{4}ℂ[P_{2}, P_{8}],

where P_{2} = x^{2} + y^{2}, P_{8} = x^{2}y^{2}(x^{2} − y^{2})^{2}, Q_{4} = x^{4} − 6x^{2}y^{2} + y^{4}, Q_{8} = xy(x^{6} − 7x^{4}y^{2} + 7x^{2}y^{4} − y^{6}), and R_{4} = xy(x^{2} − y^{2}).

We now apply this theorem to extremal [14,7,4] even f.s.d. codes in order to compute the intersection numbers. Notice that such codes contain the all-one vector 1 and this vector is in fact in the hull H = C ∩ C^{⊥}. We will only be interested in sets T where T is the support of a codeword of C. To that end, let c(T) be a codeword in C of weight t where t = 4 or t = 6 with supp(c(T)) = T. There are certain relations among n_{w,i}(T) and n_{w,i}^{∗}(T) that are obvious. For example because 1 ∈ C ∩ C^{⊥},

n_{14−w,t−i}(T) = n_{w,i}(T), and
n_{14−w,t−i}^{∗}(T) = n_{w,i}^{∗}(T).

Thus we only need consider w equal to either 4 or 6. The contents of Table 1, called intersection tables, give other obvious relations. For example, n_{w,i}^{∗}(T) = 0 when i is odd as a codeword of C intersects a codeword of C^{⊥} in an even number of places. As the minimum weight of C and C^{⊥} is 4, n_{4,3}(T) = n_{6,4}(T) = 0 when t = 4 and n_{4,4}(T) = n_{6,5}(T) = 0 when t = 6. Obviously when t = 6, n_{4,i}(T) = n_{4,i}^{∗}(T) = 0 for i = 5 or i = 6. Also, n_{4,4}(T) = 1 when t = 4, and n_{6,6}(T) = 1 when t = 6. As C contains no weight 12 vectors, n_{6,0}(T) = 0 when t = 6. It will turn out that the remaining entries in the tables will depend upon whether c(T) is in C^{⊥} or not. For example,

n_{w,i}(T) = 0 for c(T) ∈ C^{⊥} and i odd,  (5)

again as a codeword of C intersects a codeword of C^{⊥} in an even number of places. Also

n_{4,4}^{∗}(T) = 1 and n_{6,4}^{∗}(T) = 0 for c(T) ∈ C^{⊥} if t = 4,  (6)

and

n_{6,6}^{∗}(T) = 1 and n_{6,0}^{∗}(T) = n_{4,4}^{∗}(T) = 0 for c(T) ∈ C^{⊥} if t = 6.  (7)

Finally,

n_{4,4}^{∗}(T) = 0 if t = 4 and n_{6,6}^{∗}(T) = 0 if t = 6 for c(T) ∉ C^{⊥}.  (8)

\begin{matrix}wt(c(T)) = 4 \\ i & 0 & 1 & 2 & 3 & 4 \\ n_{4,i}(T) & 0 & 1 \\ n_{6,i}(T) & & 0 \\ n_{4,i}^{∗}(T) & 0 & 0 \\ n_{6,i}^{∗}(T) & 0 & 0 \end{matrix}  \begin{aligned}& wt(c(T)) = 6 \\ i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{4,i}(T) & & 0 & 0 & 0 \\ n_{6,i}(T) & 0 & & 0 & 1 \\ n_{4,i}^{∗}(T) & 0 & 0 & 0 & 0 \\ n_{6,i}^{∗}(T) & 0 & 0 & 0 \end{aligned}

Table 1: Partial intersection tables

With this information, there remain 8 entries to fill in each table when c(T) ∈ C^{⊥}, 12 entries when c(T) ∉ C^{⊥} if t = 4, and 14 entries when c(T) ∉ C^{⊥} if t = 6. To complete these tables, we use the following four equations that come directly from the weight enumerator (2)of C (and C^{⊥}):

∑_{i=0}^{t} n_{4,i}(T) = ∑_{i=0}^{t} n_{4,i}^{∗}(T) = 14, and  (9)

∑_{i=0}^{t} n_{6,i}(T) = ∑_{i=0}^{t} n_{6,i}^{∗}(T) = 49,  (10)

together with equations that arise from Theorem 4.1. We now derive these equations.

Consider first k = 1. Notice that by definition

W_{C,1,T} (x, y) = a_{0}x^{14} + a_{4}x^{10}y^{4} + a_{6}x^{8}y^{6} + a_{8}x^{6}y^{8} + a_{10}x^{4}y^{10} + a_{14}y^{14}

where the a_{j}’s are rational; by Theorem 4.1, W_{C,1,T} (x, y) = xyZ_{C,1,T} (x, y) (and W_{C⊥,1,T} (x, y) = xyZ_{C⊥,1,T} (x, y)). This implies that a_{0} = a_{14} = 0 and so

Z_{C,1,T} (x, y) = (xy)^{3}(a_{4}x^{6} + a_{6}x^{4}y^{2} + a_{8}x^{2}y^{4} + a_{10}y^{6}).

A similar equation holds for Z_{C⊥,1,T} (x, y) and hence for the sum or difference

of Z_{C,1,T} (x, y) and Z_{C⊥,1,T} (x, y). By Theorem 4.1(b),

Z_{C,1,T} (x, y) + Z_{C⊥,1,T} (x, y) ∈ Q_{8}ℂ[P_{2}, P_{8}].

By comparing Z_{C,1,T} (x, y) + Z_{C⊥,1,T} (x, y), which has factor (xy)^{3}, and the

degree 12 elements of Q_{8}ℂ[P_{2}, P_{8}], we conclude that

Z_{C,1,T} (x, y) + Z_{C⊥,1,T} (x, y) = 0.  (11)

\begin{matrix}k & Z_{C,k,T} (x, y) + Z_{C⊥,k,T} (x, y) & Z_{C,k,T} (x, y) − Z_{C⊥,k,T} (x, y) \\ 2 & βx^{2}y^{2}(x^{2} + y^{2})(x^{2} − y^{2})^{2} & 0 \\ 3 & γxy(x^{6} − 7x^{4}y^{2} + 7x^{2}y^{4} − y^{6}) & δxy(x^{2} − y^{2})(x^{2} + y^{2})^{2} \\ 4 & μ(x^{2} + y^{2})^{3} & ν(x^{4} − 6x^{2}y^{2} + y^{4})(x^{2} + y^{2}) \\ 5 & 0 & ϵxy(x^{2} − y^{2}) \\ 6 & λ(x^{2} + y^{2}) & 0 \end{matrix}

Table 2: Polynomials from Bachoc’s theorem

An analogous argument again using Theorem 4.1(b) yields

Z_{C,1,T} (x, y) − Z_{C⊥,1,T} (x, y) = αR_{4}P_{8} = α(xy)^{3}(x^{6} − 3x^{4}y^{2} + 3x^{2}y^{4} − y^{6}). (12)

Using (3), (4), and as the coefficient of x^{14−w}y^{w} is 0 in (11), we obtain for w ∈ {4, 6} and t ∈ {4, 6}

∑_{i=0}^{t} h_{1,t}(w, i)(n_{w,i}(T) + n_{w,i}^{∗}(T)) = 0  (13)

Using (3) and (4), since the coefficient of x^{10}y^{4} is α and the coefficient of x^{8}y^{6} is −3α in (12), we obtain for t ∈ {4, 6}

∑_{i=0}^{t} h_{1,t}(4, i)(n_{4,i}(T) − n_{4,i}^{∗}(T)) = α and

∑_{i=0}^{t} h_{1,t}(6, i)(n_{6,i}(T) − n_{6,i}^{∗}(T)) = −3α.

From this we obtain

− 3 ∑_{i=0}^{t} h_{1,t}(4, i)(n_{4,i}(T) − n_{4,i}^{∗}(T)) = ∑_{i=0}^{t} h_{1,t}(6, i)(n_{6,i}(T) − n_{6,i}^{∗}(T)). (14)

When k = 2, …, 6 and t ∈ {4, 6} with k ≤ t, there are analogous equations. Table 2 contains the information on Z_{C,k,T} (x, y) ± Z_{C⊥,k,T} (x, y) while Table 3

gives the equations corresponding to (13) and (14). These equations plus (9) and (10) yield Tables 4, 5, 6, and 7, completing Table 1. In Tables 5 and 7, the bound on a and bounds on x and y are obtained by observing that the values n_{w,i}(T) and n_{w,i}^{∗}(T) are nonnegative integers. Thus there are 6 possible solutions in Table 5 and 12 possible solutions in Table 7.

For the remainder of this section, we show how to also obtain all of the information (plus a bit more) given in the intersection tables using only the form

k  equations
2  ∑_{i=0}^{t} h_{2,t}(w, i)(n_{w,i}(T) − n_{w,i}^{∗}(T)) = 0
2 − ∑_{i=0}^{t} h_{2,t}(4, i)(n_{4,i}(T) + n_{4,i}^{∗}(T)) = ∑_{i=0}^{t} h_{2,t}(6, i)(n_{6,i}(T) + n_{6,i}^{∗}(T))
3 −7 ∑_{i=0}^{t} h_{3,t}(4, i)(n_{4,i}(T) + n_{4,i}^{∗}(T)) = ∑_{i=0}^{t} h_{3,t}(6, i)(n_{6,i}(T) + n_{6,i}^{∗}(T))
3 ∑_{i=0}^{t} h_{3,t}(4, i)(n_{4,i}(T) − n_{4,i}^{∗}(T)) = ∑_{i=0}^{t} h_{3,t}(6, i)(n_{6,i}(T) − n_{6,i}^{∗}(T))
4 3 ∑_{i=0}^{t} h_{4,t}(4, i)(n_{4,i}(T) + n_{4,i}^{∗}(T)) = ∑_{i=0}^{t} h_{4,t}(6, i)(n_{6,i}(T) + n_{6,i}^{∗}(T))
4 −5 ∑_{i=0}^{t} h_{4,t}(4, i)(n_{4,i}(T) − n_{4,i}^{∗}(T)) = ∑_{i=0}^{t} h_{4,t}(6, i)(n_{6,i}(T) − n_{6,i}^{∗}(T))
5  ∑_{i=0}^{6} h_{5,6}(6, i)(n_{6,i}(T) + n_{6,i}^{∗}(T)) = 0
6  ∑_{i=0}^{6} h_{6,6}(6, i)(n_{6,i}(T) − n_{6,i}^{∗}(T)) = 0

Table 3: Equations for intersection numbers

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 \\ n_{4,i}(T) & 7 & 0 & 6 & 0 & 1 \\ n_{6,i}(T) & 7 & 0 & 42 & 0 & 0 \\ n_{4,i}^{∗}(T) & 7 & 0 & 6 & 0 & 1 \\ n_{6,i}^{∗}(T) & 7 & 0 & 42 & 0 & 0 \end{matrix}

Table 4: wt(c(T)) = t = 4 with c(T) ∈ C ∩ C^{⊥}

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 \\ n_{4,i}(T) & 3 & 10 − 2a & 2a & 0 & 1 \\ n_{6,i}(T) & 3 & 12 + 4a & 24 − 2a & 10 − 2a & 0 \\ n_{4,i}^{∗}(T) & 5 + a & 0 & 9 − a & 0 & 0 \\ n_{6,i}^{∗}(T) & 10 − 2a & 0 & 39 + a & 0 & a \end{matrix}

Table 5: wt(c(T)) = t = 4 with c(T) ∈ C and c(T) ∉ C^{⊥}; 0 ≤ a ≤ 5

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{4,i}(T) & 2 & 0 & 12 & 0 & 0 & 0 & 0 \\ n_{6,i}(T) & 0 & 0 & 36 & 0 & 12 & 0 & 1 \\ n_{4,i}^{∗}(T) & 2 & 0 & 12 & 0 & 0 & 0 & 0 \\ n_{6,i}^{∗}(T) & 0 & 0 & 36 & 0 & 12 & 0 & 1 \end{matrix}

Table 6: wt(c(T)) = t = 6 with c(T) ∈ C ∩ C^{⊥}

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{4,i}(T) & 2x & 6 − 2x & 4 + 2y & 4 − 2y & 0 & 0 & 0 \\ n_{6,i}(T) & 0 & 6 − 2x & 22 − 2x − 4y & 16 + 4x + 2y & 4 + 2y & 0 & 1 \\ n_{4,i}^{∗}(T) & 3 − y & 0 & 11 − x + y & 0 & x & 0 & 0 \\ n_{6,i}^{∗}(T) & y & 0 & 32 + 3x + y & 0 & 17 − 3x − 2y & 0 & 0 \end{matrix}

Table 7: wt(c(T)) = t = 6 with c(T) ∈ C and c(T) ∉ C^{⊥}, 0 ≤ x ≤ 3, 0 ≤ y ≤ 2

of the generator matrices of C and C^{⊥} given in Theorem 2.1 and various coding arguments. The latter include Table 1, equations (9) and (10) which come from the weight enumerator, equations (5)–(8), and some obvious relations that exist among the intersection numbers (originally observed in the tables) which can be verified simply. For example,

n_{6,1}(T) = n_{4,1}(T) when t = 6,  (15)

because if u ∈ C is such that wt(u) = 6 and |T ∩ supp(u)| = 1, then v = 1 + u + c(T) satisfies wt(v) = 4 and |T ∩ supp(v)| = 1. Also

n_{6,3}(T) = n_{4,1}(T) when t = 4, and  (16)
n_{6,4}(T) = n_{4,2}(T) when t = 6  (17)

because if u ∈ C is such that wt(u) = 6 and |T ∩ supp(u)| = 3 when t = 4 (|T ∩ supp(u)| = 4 when t = 6), then w = u + c(T) satisfies wt(w) = 4 and |T ∩ supp(w)| = 1 when t = 4 (|T ∩ supp(w)| = 2 when t = 6). The same argument gives

n_{6,4}^{∗}(T) = n_{4,2}^{∗}(T) when t = 6 and c(T) ∈ C^{⊥}.  (18)

By [7] the codewords of weight w ∈ {4, 6} of C∪C^{⊥} support 1-(14, w, λ_{w}) designs (with codewords in C ∩ C^{⊥} counted twice) where λ_{4} = 8 and λ_{6} = 42. Thus if T is the support of a weight t codeword with t ∈ {4, 6}, we obtain

∑_{i=0}^{t} i(n_{w,i}(T) + n_{w,i}^{∗}(T)) = tλ_{w}  (19)

The left-hand side of this equation gives the number of ones in the weight w vectors appearing in T with equality following as the words support a 1-design.

There are six cases to consider. When we refer to B, D, E, …, these are the matrices positioned as in Theorem 2.1. The codeword c(T) is always put in the first row of G(C).

Case I: wt(c(T)) = t = 4 with c(T) ∈ C ∩ C^{⊥}

The generator matrix G(C) is given below. As dim{B} = 3 and {B} contains the all-one weight 10 vector, it must have weight distribution a_{0} = a_{10} = 1, a_{4} = a_{6} = 7. This shows n_{4,0}(T) = 7, and using Table 1, (5), (9), and (10), we obtain the intersection numbers n_{w,i}(T) below. The values for n_{w,i}^{∗}(T) follow as G(C^{⊥}) has the same form using (6), (9), and (10) although it need not be the same matrix. These results agree with those of Table 4.

G(C) = ( \begin{matrix}1111 \\ & 11111111 \\ & a_{4} = a_{6} = 7 \\ {1100 \atop 1010} & E \end{matrix} ) \begin{matrix}i & 0 & 1 & 2 & 3 & 4 \\ n_{4,i}(T) & 7 & 0 & 6 & 0 & 1 \\ n_{6,i}(T) & 7 & 0 & 42 & 0 & 0 \\ n_{4,i}^{∗}(T) & 7 & 0 & 6 & 0 & 1 \\ n_{6,i}^{∗}(T) & 7 & 0 & 42 & 0 & 0 \end{matrix}

Case II: wt(c(T)) = t = 6 with c(T) ∈ C ∩ C^{⊥}

G(C) is given below which shows that n_{4,0}(T) = 2. Table 1, (5), (9), (10), and (17) now provide the values for n_{w,i}(T) as shown. Again the values for n_{w,i}^{∗}(T) follow using (7), (9), (10), and (18) as G(C^{⊥}) has a similar form.

G(C) = ( \begin{matrix}111111 \\ & 11110000 \\ & 00001111 \\ 110000 101000 100100 100010 & E \end{matrix} ) \begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{4,i}(T) & 2 & 0 & 12 & 0 & 0 & 0 & 0 \\ n_{6,i}(T) & 0 & 0 & 36 & 0 & 12 & 0 & 1 \\ n_{4,i}^{∗}(T) & 2 & 0 & 12 & 0 & 0 & 0 & 0 \\ n_{6,i}^{∗}(T) & 0 & 0 & 36 & 0 & 12 & 0 & 1 \end{matrix}

Case III: wt(c(T)) = t = 4 with c(T) ∈ C and c(T) ∉ C^{⊥}

The form of G(C) is given below where dim{B} = 2 implying that {B} has weight distribution a_{0} = a_{10} = 1, a_{4} = a_{6} = 3. So n_{4,0}(T) = n_{6,0}(T) = 3. If u ∈ C has weight 4 with 2 ones in T, so does u + c(T). Thus n_{4,2}(T) is even, say 2a. Letting b, c, d, and e designate the entries as shown below, using Table 1, (8), (9), (10), and (16), we obtain the intersection table shown.

G(C) = ( \begin{matrix}1111 \\ & 11111111 \\ & a_{4} = a_{6} = 3 \\ 1000 0100 0010 & E \end{matrix} ) G(C^{⊥}) = ( \begin{matrix}& a_{10} = 0 \\ {1100 \atop 1010} & M′ \\ 1111 & 1 ⋯ 1 \end{matrix} )

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 \\ n_{4,i}(T) & 3 & 10 − 2a & 2a & 0 & 1 \\ n_{6,i}(T) & 3 & 36 + 2a − b & b & 10 − 2a & 0 \\ n_{4,i}^{∗}(T) & 14 − c & 0 & c & 0 & 0 \\ n_{6,i}^{∗}(T) & 49 − d − e & 0 & d & 0 & e \end{matrix}

There are \binom{4}{2} possibilities for a vector of weight 2 in \{A ∪ D\} and such a vector is joined to the vectors in the coset v + {B} where v is a nonzero evenweight vector in {E}. As the all-one vector of length 10 is in {B}, there are 4 total vectors in v+{B} of weights 2 and 4. This implies that n_{4,2}(T)+n_{6,2}(T) = \binom{4}{2} × 4 = 24 giving

b = 24 − 2a.

Examining G(C) (where M′ is the top two rows of M), we see that the 6 weight 2 vectors in {L} are paired with all 16 vectors in a nonzero coset of {J}. By the presence of the length 14 all-one vector, half of these have weights 4 or 6 giving

c + d = 48.

Applying (19) when t = 4 and w ∈ {4, 6} gives

(10 − 2a) + 2(2a) + 4(1) + 2(c) = 4 × 8 and
(36 + 2a − b) + 2(b) + 3(10 − 2a) + 2(d) + 4(e) = 4 × 42.

Solving these last four equations for a gives the table

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 \\ n_{4,i}(T) & 3 & 10 − 2a & 2a & 0 & 1 \\ n_{6,i}(T) & 3 & 12 + 4a & 24 − 2a & 10 − 2a & 0 \\ n_{4,i}^{∗}(T) & 5 + a & 0 & 9 − a & 0 & 0 \\ n_{6,i}^{∗}(T) & 10 − 2a & 0 & 39 + a & 0 & a \end{matrix}

which is identical to Table 5. Since the entries must be non-negative integers, we have 0 ≤ a ≤ 5.

The next three cases examine wt(c(T)) = t = 6 where c(T) ∈ C and c(T) ∉ C^{⊥}; there are three possibilities for dim{F }.

Case IV: wt(c(T)) = t = 6 with c(T) ∈ C, c(T) ∉ C^{⊥}, and dim{F } = 0

The forms of G(C) and G(C^{⊥}) are given below. In particular n_{4,0}(T) = n_{4,4}^{∗}(T) = 0, and by adding the all-one vector of B, we may assume the rows of E all have weight 3 implying n_{4,1}(T) = n_{6,1}(T) = 6. Using Table 1, (8), (9), (10), and (17) we obtain the intersection table given.

G(C) = ( \begin{matrix}111111 \\ & 11111111 \\ 100000 010000 001000 000100 000010 & E \end{matrix} ) G(C^{⊥}) = ( \begin{matrix}& a_{8} = 0 \\ 110000 101000 100100 100010 100001 & M \end{matrix} )

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{4,i}(T) & 0 & 6 & 8 − a & a & 0 & 0 & 0 \\ n_{6,i}(T) & 0 & 6 & 34 + a − b & b & 8 − a & 0 & 1 \\ n_{4,i}^{∗}(T) & 14 − c & 0 & c & 0 & 0 & 0 & 0 \\ n_{6,i}^{∗}(T) & 49 − d − e & 0 & d & 0 & e & 0 & 0 \end{matrix}

There are \binom{6}{3} = 20 vectors in \{A∪D\} each attached to two vectors in \{B∪E\} of either weights 1 and 7 or weights 3 and 5. Hence n_{4,3}(T)+n_{6,3}(T) = 20 giving

b = 20 − a.

Now dim{J} = 2, so that n_{4,0}^{∗}(T)+n_{6,0}^{∗}(T) = (14−c)+(49−d−e) = 3 showing that

c + d + e = 60.

Applying (19) when t = 6 and w ∈ {4, 6} gives

1(6) + 2(8 − a) + 3(a) + 2(c) = 6 × 8 and
1(6) + 2(34 + a − b) + 3(b) + 4(8 − a) + 6(1) + 2(d) + 4(e) = 6 × 42.

Solving these last four equations for a give the table

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{4,i}(T) & 0 & 6 & 8 − a & a & 0 & 0 & 0 \\ n_{6,i}(T) & 0 & 6 & 14 + 2a & 20 − a & 8 − a & 0 & 1 \\ n_{4,i}^{∗}(T) & 1 + a/2 & 0 & 13 − a/2 & 0 & 0 & 0 & 0 \\ n_{6,i}^{∗}(T) & 2 − a/2 & 0 & 34 − a/2 & 0 & 13 + a & 0 & 0 \end{matrix}

Since n_{6,0}^{∗}(T) must be a non-negative integer, we see that a must be in {0, 2, 4}. This is Table 7 where x = 0 and y = 2 − a/2.

Case V: wt(c(T)) = t = 6 with c(T) ∈ C, c(T) ∉ C^{⊥}, and dim{F } = 1

The forms of G(C) and G(C^{⊥}) are given below. In particular n_{4,0}(T) = 2 and n_{4,4}^{∗}(T) = 1. If e_{1} is the first row of E, the vectors appended to the first row of D are the 4 vectors in the coset e_{1} + {B}, two of which must have weight 3 with the other two having weight 5 as {B} contains the length 8 all-one vector. A similar result holds for the second row of D implying n_{4,1}(T) = n_{6,1}(T) = 4. Using Table 1, (8), (9), (10), and (17) we obtain the intersection table given.

G(C) = ( \begin{matrix}111111 \\ & 11110000 \\ & 00001111 \\ 000010 000001 110000 101000 & E \end{matrix} ) G(C^{⊥}) = ( \begin{matrix}111100 \\ & a_{8} = 0 \\ 110000 101000 100010 000011 & M \end{matrix} )

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{4,i}(T) & 2 & 4 & 8 − a & a & 0 & 0 & 0 \\ n_{6,i}(T) & 0 & 4 & 36 + a − b & b & 8 − a & 0 & 1 \\ n_{4,i}^{∗}(T) & 13 − c & 0 & c & 0 & 1 & 0 & 0 \\ n_{6,i}^{∗}(T) & 49 − d − e & 0 & d & 0 & e & 0 & 0 \end{matrix}

There are 12 vectors of weight 3 in {A ∪ D}. Each is attached to 4 vectors in a coset x + {B} with x an odd weight vector in {E}; this coset has either one vector of each weight 1, 3, 5, and 7 or two vectors of weight 3 and two of weight 5. So each of the 12 weight 3 vectors in {A ∪ D} contributes 2 to the sum n_{4,3}(T) + n_{6,3}(T) giving

a + b = 24.

The nonzero vectors of the two dimensional code {J} have weights 4 and 6 and hence

n_{4,0}^{∗}(T) + n_{6,0}^{∗}(T) = (13 − c) + (49 − d − e) = 3.

Applying (19) when t = 6 and w ∈ {4, 6} gives

1(4) + 2(8 − a) + 3(a) + 2(c) + 4(1) = 6 × 8 and
1(4) + 2(36 + a − b) + 3(b) + 4(8 − a) + 6(1) + 2(d) + 4(e) = 6 × 42.

Solving these last four equations for a give the table

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{4,i}(T) & 2 & 4 & 8 − a & a & 0 & 0 & 0 \\ n_{6,i}(T) & 0 & 4 & 12 + 2a & 24 − a & 8 − a & 0 & 1 \\ n_{4,i}^{∗}(T) & 1 + a/2 & 0 & 12 − a/2 & 0 & 1 & 0 & 0 \\ n_{6,i}^{∗}(T) & 2 − a/2 & 0 & 37 − a/2 & 0 & 10 + a & 0 & 0 \end{matrix}

Again, non-negativity of n_{6,0}^{∗}(T) allows us to deduce that a ∈ {0, 2, 4}. This is Table 7 where x = 1 and y = 2 − a/2.

Case VI: wt(c(T)) = t = 6 with c(T) ∈ C, c(T) ∉ C^{⊥}, and dim{F } = 2

The forms of G(C) and G(C^{⊥}) are given below. In particular n_{4,0}(T) = 6, n_{4,1}(T) = n_{6,1}(T) = 0, and n_{4,4}^{∗}(T) = 3. Using Table 1, (8), (9), (10), and (17) we obtain the intersection table given.

G(C) = ( \begin{matrix}111111 \\ & 11110000 \\ & 00111100 \\ & 00001111 \\ 110000 001100 101010 & E \end{matrix} ) G(C^{⊥}) = ( \begin{matrix}111100 \\ 001111 \\ & a_{8} = 0 \\ 110000 101000 001010 & M \end{matrix} )

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{4,i}(T) & 6 & 0 & 8 − a & a & 0 & 0 & 0 \\ n_{6,i}(T) & 0 & 0 & 40 + a − b & b & 8 − a & 0 & 1 \\ n_{4,i}^{∗}(T) & 11 − c & 0 & c & 0 & 3 & 0 & 0 \\ n_{6,i}^{∗}(T) & 49 − d − e & 0 & d & 0 & e & 0 & 0 \end{matrix}

Consider the vectors in C that have 2 ones in T; they must have 2, 4, or 6 ones in T ’s complement, and the number having 2 is equal to the number having 6 (there is the weight 8 all-one vector in {B}). This therefore gives a total of 2n_{4,2}(T) + n_{6,2}(T) vectors. But these words come from the 3 weight 2 words in {A ∪ D} each attached to 8 words in a coset of {B} yielding

2(8 − a) + (40 + a − b) = 24.

The nonzero vectors of the two dimensional code {J} have weights 4 and 6 and hence

n_{4,0}^{∗}(T) + n_{6,0}^{∗}(T) = (11 − c) + (49 − d − e) = 3.

Applying (19) when t = 6 and w ∈ {4, 6} gives

2(8 − a) + 3(a) + 2(c) + 4(3) = 6 × 8 and
2(40 + a − b) + 3(b) + 4(8 − a) + 6(1) + 2(d) + 4(e) = 6 × 42.

Solving these last four equations for a gives the table

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ n_{4,i}(T) & 6 & 0 & 8 − a & a & 0 & 0 & 0 \\ n_{6,i}(T) & 0 & 0 & 8 + 2a & 32 − a & 8 − a & 0 & 1 \\ n_{4,i}^{∗}(T) & 1 + a/2 & 0 & 10 − a/2 & 0 & 3 & 0 & 0 \\ n_{6,i}^{∗}(T) & 2 − a/2 & 0 & 43 − a/2 & 0 & 4 + a & 0 & 0 \end{matrix}

By considering integrality and non-negativity of these numbers we find that a ∈ {0, 2, 4}. This is Table 7 where x = 3 and y = 2 − a/2.

To conclude this section, we note that except for the case wt(c(T)) = t = 6 with c(T) ∈ C and c(T) ∉ C^{⊥}, Theorem 2.1 together with coding arguments give the same intersection tables as Bachoc’s harmonic polynomials. However in the case wt(c(T)) = t = 6 with c(T) ∈ C and c(T) ∉ C^{⊥}, only nine possible tables arise from Theorem 2.1 whereas there are twelve possibilities for Table 7 (the case x = 2 not actually being possible). When c(T) is in C^{⊥}, Tables 4 and 6 are unique and of course actually occur, in particular for the [14,7,4] self-dual code. When c(T) is not in C^{⊥} and t = 4, five of the six possible intersection tables described by Table 5 actually arise. When t = 6, all of the possibilities described in Cases IV–VI actually occur in the codes. We present this more throughly in the next section.

5 Enumeration of [14,7,4] Even f.s.d. Codes

In this section we enumerate the [14,7,4] even f.s.d. codes. The 10 even extremal f.s.d. codes are: the only extremal self-dual code of length 14 from [10] and the 9 codes found in Section 3. Among these 9 codes, one was known from [7]; the others are new. It is worth noticing that all these codes are equivalent to their dual.

A convenient way to distinguish the codes C from one another is to use their hull H = C ∩ C^{⊥}. Table 8 gives the list of the codes, the dimension of H, the weight enumerator of H, and the order of the automorphism group of C. The automorphism groups of the codes have been computed with the MAGMA [3] system. When the dimension of H is greater than one, the weight distribution of the hull characterizes completely the code. The codes fsd14 1a and fsd14 7 correspond respectively to the double circulant code of [7] and to the extremal

C  dim(C ∩ C^{⊥}) Weight enumerator of C ∩ C^{⊥} |Aut(C)|
fsd14 1a  1  x^{14} + y^{14}  2 · 7
fsd14 1b  1  x^{14} + y^{14}  2^{3} · 3
fsd14 1c  1  x^{14} + y^{14}  2^{3} · 3 · 7
fsd14 3a  3  x^{14} + 3x^{8}y^{6} + ⋯  2^{2} · 3
fsd14 3b  3  x^{14} + x^{10}y^{4} + 2x^{8}y^{6} + ⋯  2^{4}
fsd14 3c  3  x^{14} + 2x^{10}y^{4} + x^{8}y^{6} + ⋯  2^{5} · 3
fsd14 3d  3  x^{14} + 3x^{10}y^{4} + ⋯  2^{7} · 3
fsd14 5a  5  x^{14} + 2x^{10}y^{4} + 13x^{8}y^{6} + ⋯  2^{6} · 3
fsd14 5b  5  x^{14} + 6x^{10}y^{4} + 9x^{8}y^{6} + ⋯  2^{7} · 3^{2}
fsd14 7  7  x^{14} + 14x^{10}y^{4} + 49x^{8}y^{6} + ⋯ 2^{7} · 3^{2} · 7^{2}

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

self-dual code of [10]. Moreover among the 3 codes which can be double circulant (the ones with an element of order 7 in their automorphism group), the only double circulant codes are fsd14 1a and fsd14 1c.

We now give the generator matrices of the 9 codes in the form described in Section 3.

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

fsd14 1a = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 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 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \end{matrix} )

fsd14 1b = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 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 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \end{matrix} )

fsd14 1c = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 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 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \end{matrix} )

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

fsd14 3a = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 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 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \end{matrix} )

Hull(fsd14 3a) = ( \begin{matrix}1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} )

fsd14 3b = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 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 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \end{matrix} )

Hull(fsd14 3b) = ( \begin{matrix}1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \end{matrix} )

fsd14 3c = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 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 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \end{matrix} )

Hull(fsd14 3c) = ( \begin{matrix}1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \end{matrix} )

fsd14 3d = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 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 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \end{matrix} )

Hull(fsd14 3d) = ( \begin{matrix}1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \end{matrix} )

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

fsd14 5a = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 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 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \end{matrix} )

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

fsd14 5b = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 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 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \end{matrix} )

Hull(fsd14 5b) = ( \begin{matrix}1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 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 \end{matrix} )

As we saw in Section 4, there are 17 tables of intersection numbers of which 16 actually occur in codes. When |T | = 4 there are six tables that occur, and when |T | = 6 there are ten. For the self-dual code, there is a unique table for each value of |T |. We call these tables I and II, respectively, as these are the cases in Section 4 where they are determined. The other tables occur only in f.s.d. non-self-dual codes. When |T | = 4 there are five additional tables called III0, III1, III2, III3, and III5, as they come from Case III in Section 4 with the parameter a taking the values 0, 1, 2, 3, and 5. When |T | = 6 there are nine additional tables corresponding to Cases IV, V, and VI in Section 4 with three values for the free parameter in each case. We label these with the case number and the value of a.

An interesting question is: How are these tables actually distributed among the f.s.d. codes? This information is given in Tables 9 and 10.

I III0 III1 III2 III3 III5
fsd14 1a 0 0  7  7  0  0
fsd14 1b 0 2  6  3  3  0
fsd14 1c 0 7  0  0  7  0
fsd14 3a 0 2  6  6  0  0
fsd14 3b 1 0  7  4  2  0
fsd14 3c 2 0  6  0  6  0
fsd14 3d 3 0  4  0  6  1
fsd14 5a 2 0  12  0  0  0
fsd14 5b 6 0  0  0  8  0

Table 9: Distribution of intersection tables with |T | = 4

Certain interesting facts can be observed in these distributions. For instance, the vectors in H, when used to define T give the self-dual intersection tables (I and II). Also, we can see that the sets of vectors which determine the same intersection tables must be a union of orbits of the automorphism group of the code.

6 Further Results on f.s.d. Codes

The extremal f.s.d. even codes have been classified only for small lengths n. For 2 ≤ n ≤ 8, the extremal f.s.d. even codes are (up to equivalence) all self-dual

II IV 0 IV 2 IV 4 V 0 V 2 V 4 V I0 V I2 V I4
fsd14 1a 0  7  14  7  7  7  7  0  0  0
fsd14 1b 0 12  12  6  0 12 6  0  1  0
fsd14 1c 0  0  28  0  0 21 0  0  0  0
fsd14 3a 3  6  16  6  0 12 6  0  0  0
fsd14 3b 2 12  8  8  5  8  5  0  0  1
fsd14 3c 1  0  24  0  18 0  6  0  0  0
fsd14 3d 0 32  0  0  0  0 12  3  0  2
fsd14 5a 13 0  24  0  0  0 12  0  0  0
fsd14 5b 9  0  16  0  24 0  0  0  0  0

Table 10: Distribution of intersection tables with |T | = 6

(classified in [10]) except for the additional code at length 6 with generator matrix

( \begin{matrix}1 & 1 \\ & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} ) .

There are unique extremal even f.s.d. [10,5,4] and [18,9,6] codes [7]; in each case there is no self-dual code with the same minimum distance. In fact an [18,9,6] code is unique [16]. There is a unique [28,14,8] code from [8] which is also extremal even f.s.d. by [7]. There are three inequivalent [12,6,4] even f.s.d. codes, only one of which is self-dual [2].

We give in Table 11 the list of known extremal even f.s.d. codes for length n ≤ 30 and some of their properties, with ‘d’ the usual bound on Type I codes, ‘sd’ the number of self-dual codes, ‘other’ the number of even f.s.d. codes which are not self-dual, ‘hull’ the various dimensions of the hull that occur, ‘iso’ if the codes are isodual (equivalent to their dual) or not, and ‘dc’ meaning that the codes have a double circulant representation. Notice that all known codes in the table are isodual. There are no [16,8,6] and [26,13,8] linear codes from [4] and therefore no extremal even f.s.d. codes for these lengths.

All of the known codes in Table 11, except 8 of the codes of length 14 and the ”odd” [22,11,6] Golay code, have double circulant representations. (At length 14 only fsd14 1a and fsd14 1c have double circulant representations.) Thus for these codes there is an ordering of coordinates so that the code has a generator matrix of the form [ I A ] where A is a circulant matrix. In Table 12 we present the first row of A (in octal, where the octal number is read left to right and is truncated on the right, if necessary, to make it the proper length) for some of the codes in Table 11 and also for a [16,8,4] code and a [26,13,6] code, which

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  [2], [14]
14  4 1  9  1,3,5,7 yes  2  §5, [7]
16  6 0  0  -  -  -  [4]
18  6 0  1  1  yes  yes  [7], [16]
20  6 0 ≥ 1  4,?  yes,?  yes,?  [7]
22  6 1 ≥ 1 1,11,? yes,? no,yes,?  [13], [7]
24  8 1  0  12  yes  yes  [9]
26  8 0  0  -  -  -  [4]
28  8 0  1  2  yes  yes  [8]
30  8 0 ≥ 1  3,?  yes,?  yes,?  [7]

Table 11: The extremal even f.s.d. codes for n ≤ 30 are f.s.d but not self-dual.

n k d

1^{st} row of ; A (octal)
10 5 4  70
12 6 4  70
12 6 4  72
12 6 4  32
14 7 4  700
14 7 4  610
16 8 4  700
18 9 6  722
26 13 6  75240

Table 12: Some double circulant even f.s.d. codes

In the table, the [14,7,4] code with first row of A equaling 700 (octal) is fsd14 1a while the one with first row 610 is fsd14 1c. Others are given in [7] .

Looking at the dimensions of the hulls in Table 11 led to the following theorem.

Theorem 6.1 If C is an even [n, k] binary code, then dim H is ≡ k (mod 2).

Proof: In the terminology of [11], C is the vector space orthogonal sum of m hyperbolic planes and its hull H; that is k = 2m + dim H . □

Corollary 6.2 If C is an even f.s.d. code of length n, then dim H is odd if n ≡ 2 (mod 4) and is even if n ≡ 0 (mod 4).

Proof: This follows directly from Theorem 6.1. □

We remark that all of the intersection tables for a vector of fixed weight are unique for the codes in Table 11 of lengths 8, 10, 18, and 24.

ACKNOWLEDGEMENT

We thank C. Bachoc for giving us a preprint of [2].

References

[1] E. F. Assmus and J. D. Key, Designs and Their Codes, Cambridge, University Press, 1992.

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

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

[4] 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.

[5] A. E. Brouwer and M. Voorhoeve, “Turán theory and the lotto problem,” Mathematical Centre Tracts 106 (1979), 99–105.

[6] J. E. Fields and V. Pless, “Split weight enumerators of extremal self-dual codes,” Proceedings, 35th Annual Allerton Conference on Communication, Control and Computing (1997), 422-431.

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

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

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

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

[11] V. Pless, “Constraints on weights in binary codes,” AAECC 8 (1997), 411– 414.

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

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

[14] 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.

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

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