On the Enumeration of Self-Dual Codes

Akihiro Munemasa Department of Mathematics Kyushu University

1 Statement of the result

The contents of this note is a summary of a talk given at University of Tokyo by the author. One of the main goal of this note is to give a brief account of the recent work by the author of the enumeration of singly-even self-dual binary codes of length 32. There are 3210 such codes up to equivalence. It is known that there are 85 doubly-even self-dual binary codes of length 32 up to equivalence [2], and every singly-even self-dual binary code of length a multiple of 8 is a neighbour of some doubly-even self-dual binary code. We have enumerated all neighbours of the 85 doubly-even self-dual binary codes of length 32, and performed the equivalence testing. The whole computation was done by Magma [1], and it took 5–20 hours, depending on the CPU speed.

We denote by F_{2} a finite field of two elements. A binary linear code of length n is a linear subspace of F_{2}^{n}. Since all codes considered in this note are binary linear, we omit the adjectives “binary” and “linear.” Two codes are said to be equivalent if one is obtained from the other by a permutation of coordinates. The set of permutations which give equivalences of a code C to itself forms a group called the automorphism group, and is denoted by Aut(C). We define the standard inner product on F_{2}^{n} by

u · v = ∑_{j=1}^{n} u_{j}v_{j}, (u, v ∈ F_{2}^{n}).

The dual C^{⊥} of a code C is defined by

C^{⊥} = {u ∈ F_{2}^{n} | u · v = 0 for all v ∈ C},

and C is said to be self-dual if C = C^{⊥}. The weight of a vector u ∈ F_{2}^{n} is defined by

wt(u) = #{j | 1 ≤ j ≤ n, u_{j} ≠ 0}.

and the minimum weight of a code C is defined by

min(C) = min{wt(u) | u ∈ C, u ≠ 0}.

Then the fundamental problem in coding theory is to find a code C ⊂ F_{2}^{n} with dim C = k such that min(C) is as large as possible, for given positive integers n, k.

If C is a self-dual code, then clearly

wt(u) ≡ 0 (mod 2) for all u ∈ C

holds. A code C is called doubly-even if for all u ∈ C,

wt(u) ≡ 0 (mod 4)

holds. A doubly-even self-dual code is also called a Type II code. A self-dual code which is not doubly-even is called singly-even or Type I. A doublyeven self-dual binary code of length n exists if and only if n ≡ 0 (mod 8). Among the doubly-even self-dual codes, the best codes in the sense of the fundamental problem are defined to be the codes achieving the following bound (see e.g., [8]).

Theorem 1. If C is a doubly-even self-dual code of length n, then

min(C) ≤ 4 [\frac{n}{24}] + 4.

A code achieving this bound is called extremal. Table 1 summarizes our current knowledge about extremal doubly-even self-dual codes. For unexplained notation and terminologies, we refer the reader to [5].

The only difference between Table 1 and Table X of [8] is our nonconstructive lower bound on the number of extremal codes of length 40. This follows easily from a result of MacWilliams, Sloane and Thompson [6], so we explain it here. The weight enumerator of a code C of length n is the polynomial W_{C}(x, y) of degree n in two indeterminates, x, y, defined by

W_{C}(x, y) = ∑_{u∈C} x^{n−wt(u)}y^{wt(u)}.

In [6], its mass formula is given:

Theorem 2. If n is a positive integer divisible by 8, then

∑_{C: d.e.s.d. ; length n} W_{C}(x, y) = ∏_{j=0}^{n/2−3}(2^{j} + 1) (2^{n/2−2}(x^{n} + y^{n}) + ∑_{4|k} \binom{n}{k}x^{n−k}y^{k}) ,

where the sum is taken over all doubly-even self-dual codes C of length n.

Table 1: Extremal Type II Codes

n  bound number  example
8  4  1  Hamming
16  4  2  Hamming^{2}, d_{16}^{+}
24  8  1  Golay
32  8  5  Reed–Muller, QR
40  8  ≥ 11395  double circulant [3]
48  12  ≥ 1  QR
56  12  ≥ 166  double circulant [3]
64  12  ≥ 3270  double circulant [3]
72  16  ?  ?
80  16  ≥ 2 QR, Gulliver–Harada [4]
≥ 3952  0  ∄

If n = 40, then one checks easily the inequality:

2^{n/2−2} > \binom{n}{4}.

This implies that, in the mass formula, the coefficient of x^{40} is greater than the coefficient of x^{36}y^{4}. Since each W_{C}(x, y) has integral coefficients and the coefficient of x^{40} is 1, it follows that there exists a doubly-even self-dual code C such that the coefficient of x^{36}y^{4} in W_{C}(x, y) is zero. Such a code C has minimum weight 8, hence is extremal. This is the argument used in the proof of Theorem 2.5 of [6]. In fact, one can derive not only the existence of an extremal code, but also a lower bound on the number of extremal codes. The above argument also shows that there are at least

∏_{j=0}^{n/2−2}(2^{j} + 1) − \binom{n}{4} ∏_{j=0}^{n/2−3}(2^{j} + 1)  (1)

extremal codes of length n = 40. Even considering equivalence, the number of extremal codes of length 40 is at least the smallest integer not less than the quotient of (1) by 40!, which is 11395.

Now we turn to the enumeration of self-dual codes. All doubly-even selfdual codes of length up to 32 have been classified, and all singly-even self-dual codes of length less than 32 have been classified. The main result of this note is the following theorem, which fills the last entry in Table 2.

Table 2: The Number of Self-Dual Codes

n 2 4 6 8 10 12 1 16 18 20 22 24 26 28 30 32
II 1 2 9 85
I 1 1 1 1 2 3 4 5 9 16 25 46 103 261 731 3210

Theorem 3. There are 3210 Type I codes of length 32 up to equivalence.

The first row indicates the lengths, the second row gives the number of doubly-even self-dual (Type II) codes, and the third row gives the number of singly-even self-dual (Type I) codes, both up to equivalence. Among the Type I codes of length 32, only those codes with minimum weight 2 or 8 were classified before. Type I codes of length 32 with minimum weight 2 are the direct sums of self-dual codes of length 30 and the unique self-dual code of length 2, hence there are 731 such codes. It is known that there are three Type I codes of length 32 with minimum weight 8 (see [3]).

Theorem 2 shows that the total number of Type II codes of length n is given by

∏_{j=0}^{n/2−2}(2^{j} + 1).

A similar formula for the total number of self-dual codes of length n is known ([8], see also [7, 9]):

∏_{j=1}^{n/2−1}(2^{j} + 1).

These formulas can be used to check that a classification of Type I codes is complete for small lengths. In fact, suppose that we have a collection C of Type I codes in which all members are pairwise inequivalent. If C satisfies

∑_{C∈C} \frac{32!}{# Aut(C)} = ∏_{j=1}^{15}(2^{j} + 1) − ∏_{j=0}^{14}(2^{j} + 1)

= 3168896498278970068411253452090715625

then we can be sure that no other Type I codes exist, in other words, C is a complete set of representatives of equivalence classes of Type I codes of length 32.

2 Neighbours

Self-dual codes C_{1}, C_{2} of length n are called neighbours to each other if

dim C_{1} ∩ C_{2} = \frac{n}{2} − 1

Note dim C_{1} = dim C_{2} = \frac{n}{2} since C_{1} and C_{2} are self-dual. The vector in F_{2}^{n} whose entries are all 1 is called the all one vector and is denoted by 1. Every self-dual code contains 1. Thus, a self-dual code C of length n has 2^{n/2−1} − 1 hyperplanes (subcodes of codimension 1 in C) containing 1. For each such hyperplane H, dim H^{⊥}/H = 2 holds. So there are three self-dual codes (including C) lying between H and H^{⊥}. If, moreover C is Type II, then among the two other codes lying between H and H^{⊥}, one is Type I and the other is Type II. Therefore, C has 2^{n/2−1} − 1 Type I neighbours and 2^{n/2−1} − 1 Type II neighbours. All Type I codes arise in this way from a Type II code and its hyperplane. Indeed, if C_{1} is a Type I code, then there exists a unique doubly-even hyperplane H of C_{1}. The two neighbours C′, C′′ of C_{1} such that

C_{1} ∩ C′ = C_{1} ∩ C′′ = H

are both Type II.

Thus we can use the classification of Type II codes of length 32 in order to classify Type I codes of length 32. More precisely, we need to classify the pairs (C, H), where C is a Type II code of length 32, H is a hyperplane of C. Note that C can be chosen to be one of the 85 representatives of equivalence classes of Type II codes of length 32. Then H can be chosen to be one of the representatives of orbits under Aut(C).

As we mentioned before, all Type I codes of length 32 with minimum weight 2 have been classified. These codes are direct sums of self-dual codes of length 30 and the unique self-dual code of length 2, hence there are 731 such codes. If C is such a code, then the two Type II neighbours of C are equivalent to each other.

3 Computer calculation by Magma

In this section, we describe a Magma program used to classify Type I codes of length 32. The program consists of two parts. The first part classifies the hyperplanes of a given Type II code C of length 32 up to the automorphism group of C. Then for each of the hyperplanes, we compute the unique Type I neighbour sharing the hyperplane. The result is a total of 5192 Type I codes.

This includes the known 731 Type I codes with minimum weight 2 without duplication.

The second part classifies the remaining 4461 Type I codes by computing several invariants of these codes. We will see that our invariants characterize the actual equivalence of Type I codes by verifying the mass formula.

First we define our own function to compute automorphism groups of codes. Magma has a built-in function to compute automorphism groups of codes, but our function outperforms the built-in function in certain circumstances. For example, the automorphism group of the Type II code C23 of length 32 can be computed much more quickly by our function auto when the second argument t is supplied with the value 8.

    supportdesign:=function(C,t)
        return IncidenceStructure< Length(C) |
          { Support(u) : u in C | Weight(u) eq t } >;
    end function;
    supportauto:=function(C,t)
        return PointGroup(supportdesign(C,t));
    end function;
    auto:=function(C,t)
        A:=supportauto(C,t);
        orbit:=C^A;
        return Stabilizer(A,orbit,C);
    end function;

Let C be a self-dual code of length 32. Then its automorphism group A can be computed by

    A:=auto(C,8);

Now we describe how to classify Type I neighbours of C up to the action of A. To this end, it suffices to classify hyperplanes of C containing 1. Moreover, if we regard C as a vector space over F_{2}, then the hyperplanes of C containing 1 are in one-to-one correspondence with the nonzero elements of the dual space of the quotient M of C by the 1-dimensional space spanned by 1. This means that we need to construct the action of A on M, which can be done easily by Magma as follows.

    P:=PermutationModule(A,GF(2));
    N:=sub< P | VectorSpace(C) >;
    M:=quo< N | P![ 1 : i in [1..32] ] >;

The matrix representation of A in M can be obtained by

    G:=MatrixGroup(M);

and the matrix representation of A in the dual space of M is

    G1:=MatrixGroup< 15, GF(2) |
        [ Transpose(g) : g in Generators(G) ] >;

Orbit representatives of the group G1 on the set of nonzero vectors of F_{2}^{15} are given by

    X:=[ o[1] : o in Orbits(G1) | not 0 in o ];

Now let x be an element of X. As we intend to regard x as an element of the dual space of M, we should be able to construct a hyperplane of M corresponding to x. Indeed, this can be achieved by the following.

    N0:=sub< VectorSpace(P) | VectorSpace(C) >;
    M0,f0:=quo< N0 | N0![ 1 : i in [1..32] ] >;
    K1:=VectorSpace(GF(2),1);
    M0dual:=Hom(M0,K1);
    MH:=Kernel(M0dual!Eltseq(x));

Now MH is a hyperplane of M. We can construct a hyperplane of C by taking the preimage of the natual mapping from C to its quotient by 1.

    H:=LinearCode< GF(2),32 | MH @@ f0 >;

Next we construct the Type I neighbour of C sharing H.

    H0:=VectorSpace(H);
    Hd:=VectorSpace(Dual(H));
    T:=[ t : t in Transversal(Hd,H0) | Weight(t) mod 4 eq 2 ];
    y:=T[1];
    C1:=sub< V | H,y >;

Then C1 is the Type I neighbour of C sharing H. Iterating the above procedure for each x in X, we obtain all Type I neighbours of C up to the action of A. Iterating this procedure for all of the 85 Type II codes C of length 32, we obtain a total of 5192 Type I codes of length 32. Removing the 731 Type I codes with minimum weight 2, we obtain 4461 Type I codes with minimum weight at least 4. These Type I codes are not necessarily inequivalent to each other. Indeed, if a Type I code C_{1} has two inequivalent Type II neighbours, then C_{1} will appear exactly twice in the list of 4461 Type I codes. Our next task is to classify these 4461 Type I codes up to equivalence. Note that Magma has a built-in function IsIsomorphic for codes, but the use of this function is sometimes time-consuming. So we compute certain invariants of codes to distinguish inequivalent codes. The following invariants are easy to compute:

• The order of the automorphism group

• The pair of equivalence classes of the Type II neighbours

• The weight enumerator

However, there are inequivalent codes having the same value of these invariants. So we need a more elaborate invariant. It turns out that, in addition to the above three invariants, the following invariant completely characterize the equivalence of Type I codes of length 32 with minimum weight at least 4:

    twoptdegreeSorted6:=function(C)
        des:=supportdesign(C,6);
        return Sort( [ #{ b : b in BlockSet(des) |
            { Point(des,j) : j in x } subset b } :
              x in Subsets({1..32},2) ] );
    end function;

This function returns a sorted list of length \binom{32}{2} giving the number of codewords of weight 6 whose support contains a given pair of coordinates. Using the four invariants defined above, we classify the 4461 Type I codes obtained as neighbours of the 85 Type II codes. There are 2479 classes of Type I codes. One could check that codes belonging to any given class are pairwise equivalent by the function IsIsomorphic, but it is easier to verify the mass formula. That is, if aut is the list of the orders of the automorphism groups of representatives of the 2479 classes, together with the list of the orders of the automorphism groups of the 731 Type I codes of minimum weight 2, then one checks the mass formula

    print &+[ Factorial(32)/aut[i] : i in [1..3210] ] eq
    &*[ 2^i+1 : i in [1..15] ] - &*[ 2^i+1 : i in [0..14] ];

returning true. This implies that our 3210 Type I codes are in fact all the Type I codes of length 32 up to equivalence.

Acknowledgements

The author would like to thank Masaaki Harada for helpful discussion and verifying the result independently.

References

[1] W. Bosma and J. Cannon, “Handbook of Magma Functions,” Department of Mathematics, University of Sydney, November 1994.

[2] J. H. Conway, V. Pless and N. J. A. Sloane, The binary self-dual codes of length up to 32: A revised enumeration, J. Combin. Theory Ser. A, 60 (1992), 183–195.

[3] J. H. Conway and N. J. A. Sloane, A new upper bound on the minimal distance of self-dual codes, IEEE Trans. Inform. Theory, 36 (1990), 1319– 1333.

[4] T. A. Gulliver and M. Harada, A new extremal doubly-even [80,40,16] code and related codes, submitted.

[5] F.J. MacWilliams and N.J.A. Sloane, “The Theory of Error-Correcting Codes,” North-Holland, Amsterdam, 1977.

[6] F. J. MacWilliams, N. J. A. Sloane and J. G Thompson, Good self dual codes exist, Discrete Math., 3 (1972), 153–162.

[7] , V. Pless, The number of isotropic subspaces in a finite geometry, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur., (8) 39 (1965) 418–421.

[8] E. Rains and N.J.A. Sloane, “Self-dual codes,” Handbook of Coding Theory, V.S. Pless and W.C. Huffman (Editors), Elsevier, Amsterdam 1998, pp. 177–294.

[9] Z.-X. Wan, Notes on finite geometries and the construction of PBIB designs, I, Some “Anzahl” theorems in symplectic geometry over finite fields, Sci. Sinica, 13 (1964) 515–516.

Department of Mathematics Kyushu University 6–10–1 Hakozaki Higashi-ku Fukuoka 812–8581 Japan

munemasa@math.kyushu-u.ac.jp
http://www.math.kyushu-u.ac.jp/munemasa