SPLIT WEIGHT ENUMERATORS OF EXTREMAL SELF-DUAL CODES

JOE FIELDS, VERA PLESS

Abstract. The split weight enumerator has been used to aid in the determination of the existence of a code with a particular weight enumerator. We have found a new faster method of computing split weight enumerators of self-dual codes using specific properties of these codes. These techniques are applied to the weight enumerators of putative extremal [72,36,16] and [96,48,20] codes and other interesting codes.

1. Introduction

A doubly-even, self-dual binary block code must have length n a multiple of 8. Such a code can have minimum distance at most 4 + 4⌊n/24⌋ and codes having this minimal distance are called extremal. Thus, at lengths 8 and 16, we have extremal codes having minimum distance 4 (the length 8 extended Hamming code e_{8} and two codes of length 16: d_{16} and e_{8} ⊕ e_{8}). At length 24 the remarkable extended Golay code is the unique extremal doubly-even code. At length 32 there are 5 inequivalent extremal doubly-even codes [3], and this is the largest length where the complete story is known. Conway and Pless determined these 5 inequivalent extremal codes by completely classifying all of the doubly-even self-dual codes of length 32. This approach appears to be impractical for lengths greater than 32. There is one known extremal code of length 48 (an extended quadratic residue code) and it is an open question whether there are others. The smallest length for which the existence of an extremal code is not known is 72.

The MacWilliams relations, which are a set of equations relating the weight enumerator of a code to that of its dual, often serve to completely determine the weight enumerator of a self-dual code. Indeed if the code is doubly-even and extremal, the MacWilliams relations uniquely determine the weight enumerator.

Split weight enumerators are useful in investigating whether there can be a code with a certain weight enumerator. The split weight enumerator has to exist with non-negative integer coefficients. As we shall see, it often implies the existence of other smaller codes with certain weight enumerators. Split weight enumerators can also be used to determine the weight enumerator of certain cosets of a code.

When the usual system of equations (1) are used, the calculation of the split weight enumerator takes a great deal of time. With other methods we have been able to determine the split weight enumerators of certain interesting doubly-even self-dual codes of length > 100 which were not possible to find using (1). We describe these methods and give specific results for certain doubly-even self-dual codes.

2. Preliminaries

The weight enumerator of a code is a polynomial in one variable (say x) such that the coefficient of x^{i} is the number of codewords having Hamming weight i. The split weight enumerator of a code with respect to a partition is a polynomial in several variables, one for each piece of the partition. For instance, if we consider the famous extended Golay code and a partition of the coordinates into two pieces: the support of a minimum weight codeword in the first part, and its complement, in the second part, we get a polynomial in two variables. The coefficient of x^{i}y^{j} is the number of words in the code having i ones in the first part of the partition and j ones in the second.

The split weight enumerator of the Golay code (partitioned as above) is:

1 + x^{8} + 280x^{4}y^{4} + 448x^{2}y^{6} + 30y^{8} + 448x^{6}y^{6} + 1680x^{4}y^{8}

+ 448x^{2}y^{10} + 30x^{8}y^{8} + 448x^{6}y^{10} + 280x^{4}y^{12} + y^{16} + x^{8}y^{16}

The symmetries of the situation may be more obvious if we instead display this information as a table (the number in the (i, j) position is the coefficient of x^{j}y^{i} in the split weight enumerator.

For compactness, we display only the even-numbered columns and rows:

j = 0 2  4  6 8
i = 0 1  0  0  0 1
2 0  0  0  0 0
4 0  0 280 0 0
6 0 448 0 448 0
8 30 0 1680 0 30
10 0 448 0 448 0
12 0  0 280 0 0
14 0  0  0  0 0
16 1  0  0  0 1

We will usually denote the number in the (i, j) position of such a table by X_{i,j}.

Next, let us consider a partition of the coordinates into three parts, each the support of an octad. The resulting numbers could be expressed as the coefficients of a polynomial in three variables or (as we shall do) as a three-dimensional array of numbers:

In [11], Simonis introduced the generalized MacWilliams identities which can be used to find these split weight distributions. Suppose that T is a partition of n into p parts. W (T) is the set of all possible weight vectors with respect to the partition, i.e., W (T) = {i ∈ ℕ^{p} | i_{u} ≤ n_{u} for all u with 1 ≤ u ≤ p}, where n_{u} is the size of the u-th piece of the partition T, and i_{u} is the u-th coordinate of the vector i.

For some codeword x ∈ C, the T -weight, or weight with respect to the partition, is a vector of non-negative integers giving the weight of x in each piece of the partition. Denote the T -weight of x by w_{T} (x). Clearly w_{T} (x)_{u} ≤ n_{u}, for all 1 ≤ u ≤ p. Define A_{i}(T) = {x ∈ C | w_{T} (x) = i} and similarly, define B_{i}(T) = {y ∈ C^{⊥} | w_{T} (y) = i}. Note that |A_{i}(T)| (resp. |B_{i}(T)|) is one component of the split weight distribution of C (resp. C^{⊥}).

For binary codes, the generalized MacWilliams identities are as follows.

∑_{j∈W (T)} [∏_{u=1}^{p} \binom{n_{u} − j_{u}}{i_{u}}] A_{j}(T) = 2^{k−∥i∥} ∑_{j∈W (T)} [∏_{u=1}^{p} \binom{n_{u} − j_{u}}{n_{u} − i_{u}}] B_{j}(T) (1)

Note that there is an equation for each (vector) i in W (T).

For even the most trivial examples, the generalized MacWilliams identities give us extremely large systems of equations involving an equally large number of unknowns. For instance, consider the [8, 4, 4] extended Hamming code and a partition of its coordinates into two pieces: the support of disjoint codewords. The split weight enumerator (again only the even columns and rows are shown) is:

\begin{aligned}& j = 0 & 2 & 4 \\ i = 0 & 1 & 0 & 1 \\ 2 & 0 & 12 & 0 \\ 4 & 1 & 0 & 1 \end{aligned} .

But the generalized MacWilliams identities give a system of 25 equations in 25 unknowns. By naively sending these equations to a linear system solver we find the unique solution, but by first taking into account some of the facts which are known about this code (that it is doubly-even and has minimum weight 4) we get a much smaller system. Indeed, if we also allow ourselves to note that the 4 corner entries must be 1’s, we get a system that can be solved merely by considering the dimension of the code!

If we are interested in the split weight enumerator of a code C relative to a partition of its coordinates into two parts, where one portion holds a vector of weight w in C, then knowledge of the shortened code in the other portion is useful.

Theorem 1. If C is an [n, n/2, d] self-dual binary code containing a vector v of weight w < 2d, the subcode of C, S, having zeroes on all positions in v is an [n−w, n/2−w+1, d] code if those positions are eliminated. Further, the code derived from C by puncturing on the coordinates of v is an [n − w, n/2 − 1, d′] code where d′ ≥ d − w/2 and, in fact, is S^{⊥}.

Proof. The statement about the dimension of S follows from Theorem 103 in [10] or the balance principle [6]. The fact that the punctured code is S^{⊥} is also in Theorem 103 [10].

Theorem 2. If C is a doubly-even [n, n/2, d] code and v is a vector in C of weight w < 2d, then the weight distribution of S and S^{⊥} are uniquely determined iff w ≤ 6d − n − 4.

Proof. We know that the minimum weight of S^{⊥} is ≥ d − w/2 and the minimum weight of S is d. Now S contains the all one vector of weight n − w so the number of unknown weights in S is \frac{n−w−2d}{4} + 1. Hence there is a unique solution to the power moments iff \frac{d−w}{2} ≥ \frac{n−w−2d}{4} + 1 [10]Theorem 83.

Note that this theorem implies that a unique solution for the weight enumerators of S and S^{⊥} is only possible for extremal doubly-even codes and then only for w ≤ 20.

If we consider the split weight enumerator of a doubly-even [n, n/2, d] code with respect to a vector v of weight w, then the weight distribution of S gives all the terms in this split weight enumerator of the form X_{i,0}. The terms in the weight enumerator of S^{⊥} are related to a sum of terms in the split weight enumerator, i.e. if b_{i} is the number of vectors of weight i in S^{⊥}, 2b_{i} = ∑_{j} X_{i,j}. The factor of 2 comes from the fact that for each codeword x ∈ C that is mapped to a codeword y ∈ S^{⊥}, the vector x + v is also. That is, there is a 2 to 1 correspondence between C and S^{⊥}.

Essentially, this last paragraph says that the weight distribution of S is in the far left (and far right) column of the split weight distribution table and that by summing rows of this table we get twice the weight distribution of S^{⊥}.

We also get known results if we sum the split weight distribution table along columns and diagonals.

The diagonal sums are perhaps easiest to see. If we sum along the diagonals such that i + j is constant, we will find all the vectors of a fixed weight in the original code C. Thus A_{k} = ∑_{i+j=k} X_{i,j}.

Since S may be viewed as a subcode of C, by summing the columns we find all the vectors in cosets of S with a fixed weight coset representative. Thus ∑_{i} X_{i,j} = \binom{w}{j}2^{n−w−k+1}.

We use the equations given in the last several paragraphs to define a linear system of equations whose unknowns are the variables X_{i,j} in the split weight distribution. This system is, in general, underdetermined. If we add some additional assumptions about the code (that it is doubly-even and self-orthogonal), and the fact that the split weight distribution itself has certain symmetries, we sometimes get a determinate system. This technique was sufficient to find the split weight distributions of all extremal doubly-even self-dual codes for lengths less than 72.

The complete system of equations is:

X_{i,j} = 0 if i + j ≢ 0 (mod 4) or i ≢ 0 (mod 2)
X_{i,j} = X_{i,w−j} = X_{n−w−i,j} = X_{n−w−i,w−j}

∑_{i} X_{i,j} = \binom{w}{j}2^{n−w−k+1}

∑_{i+j=k} X_{i,j} = A_{k}

∑_{j} X_{i,j} = 2b_{i}

X_{0,i} = X_{w,i} = a_{i}

Where A_{k} is the the weight distribution of C, a_{i} is the weight distribution of S and b_{i} is the weight distribution of S^{⊥}.

As was mentioned above, this system was not sufficient to determine the split weight distributions of putative extremal codes having length 72 or greater. For these codes, we developed another technique which takes advantage of the fact that vectors of all weights in such codes hold designs. This technique has its own limitations – it cannot be applied to codes having minimum weight greater than 20. This seems to be related to but not a direct consequence of Theorem 2. We are able to determine split weight distributions in terms of a single parameter for some extremal codes partitioned into the support of a weight 24 vector and its complement.

The design technique consists of generating a different linear system, the equations come from counting (in two ways) flags of the form: sets of points (of size ≤ t) from the first part of the partition contained in a block of the t-design held by vectors of a fixed weight.

For instance, consider the putative [72, 36, 16] code and a partition whose first part is the support of a minimum weight vector. The equations determined by the designs held by weight 16 vectors are:

\binom{16}{1}(λ_{1,1} − 1) = \binom{2}{1}X_{14,2} + \binom{4}{1}X_{12,4}\binom{6}{1}X_{10,6} + \binom{8}{1}X_{8,8}

\binom{16}{2}(λ_{2,2} − 1) = \binom{2}{2}X_{14,2} + \binom{4}{2}X_{12,4}\binom{6}{2}X_{10,6} + \binom{8}{2}X_{8,8}

\binom{16}{3}(λ_{3,3} − 1) = \binom{4}{3}X_{12,4}\binom{6}{3}X_{10,6} + \binom{8}{3}X_{8,8}

\binom{16}{4}(λ_{4,4} − 1) = \binom{4}{4}X_{12,4}\binom{6}{4}X_{10,6} + \binom{8}{4}X_{8,8}

\binom{16}{5}(λ_{5,5} − 1) = \binom{6}{5}X_{10,6} + \binom{8}{5}X_{8,8}

There are five equations, because the weight 16 vectors hold a 5-design, thus the first equation reflects the fact that we have a 1-design, the second a 2-design, etc.

Since there can only be 5 equations, this system can (at best) be used to discover the values of 5 unknowns. We express the coefficients of that (slightly larger) system in matrix form.

[ \begin{matrix}\binom{2}{1} & \binom{4}{1} & \binom{6}{1} & \binom{8}{1} & \binom{10}{1} \\ \binom{2}{2} & \binom{4}{2} & \binom{6}{2} & \binom{8}{2} & \binom{10}{2} \\ 0 & \binom{4}{3} & \binom{6}{3} & \binom{8}{3} & \binom{10}{3} \\ 0 & \binom{4}{4} & \binom{6}{4} & \binom{8}{4} & \binom{10}{4} \\ 0 & 0 & \binom{6}{5} & \binom{8}{5} & \binom{10}{5} \end{matrix} ]

It can easily be checked that this system is invertible (its determinant is 32768).

Fact 1. Let C be a doubly-even [n, n/2, d] code and consider its split weight enumerator with respect to a vector v in C of weight w ≤ 2d. Then if the weight distribution of S and S^{⊥} are uniquely determined, so is the split weight enumerator.

This is so by observation of the finite number of cases where this can occur, which are given in the next section.

For all the cases where we have seen that the weight enumerators of S and S^{⊥} can be given in terms of one variable, the split weight enumerator can also be given in terms of one variable.

3. The Cases

We have computed split weight enumerators for many extremal doubly-even codes. As we see from Theorem 2, the weight distributions of S and S^{⊥} are uniquely determined whenever we choose the codeword v of weight ≤ 20. We also determined the split weight enumerators for v of weight 24 where the weight distributions of S and S^{⊥} (and also, the split weight enumerator) can be given in terms of one variable. We discuss these first. The other case of interest is the extended code of the code generated by the lines of a projective plane of order 10 (notwithstanding the fact that this plane is thought not to exist!)

3.1. Extremal Doubly-even Codes. n = 24) There are unique split weight enumerators with respect to words of weights 8 and n = 32) There are unique split weight enumerators with respect to words of weights 8 and

12. There is a one-variable solution when partitioning on the support of a weight 16 codeword. Note that there are 5 inequivalent [32, 16, 8] doubly-even codes [3]. There are 8 different split weight enumerators if the partition is into two portions of size 4 and 28; clearly neither of these is the support of a codeword. These correspond to the different possible weight distributions for cosets of weight 4. Cosets of weights 1,2,3,5 and 6 have unique distributions [1].

n = 48) There are unique split weight enumerators with respect to words of weights 12, 16 and 20. There is a one-variable solution for weight 24. Here it is not known if there is any other code than the extended quadratic residue code [5]. It is known that the weight distributions of cosets of weights 1,2,3,4,5,7 and 8 are unique [1]. There are 7 possible weight distributions for cosets of weight 6. Six of them appear in the weight 6 cosets of the extended quadratic residue code.

n = 72) There are unique split weight enumerators with respect to words of weights 16 and 20. For both of these partitions, there are known codes having the parameters of S and S^{⊥} [2] but these codes do not have the weight distributions dictated by the split weight enumerators. For example, shortening a [72, 36, 16] code on the support of a weight 16 vector gives a code S having parameters [56, 21, 16]. Such a code is known [2], and it turns out to be doubly-even, but its weight distribution is

[1, 0, 0, 0, 0, 0, 0, 0, 5170, 0, 90640, 0, 508365, 0, 888800, 0, 508365, 0, 90640, 0, 5170, 0, 0, 0, 0, 0, 0, 0, 1]

whereas the weight distribution of S must be

[1, 0, 0, 0, 0, 0, 0, 0, 5082, 0, 91168, 0, 507045, 0, 890560, 0, 507045, 0, 91168, 0, 5082, 0, 0, 0, 0, 0, 0, 0, 1].

There is a one-variable solution for weight 24.

n = 96) There is a unique split weight enumerator with respect to words of weight 20. Here, S is a [76, 29, 20] code. The best known [76, 29] code has minimum weight 18 [2], on the other hand, the tightest upper bound on the minimum weight of such a code is 22 [2]. In contrast, there is a known code having parameters [76, 47, 10] (those of S^{⊥}) [2] but this code does not have the weight distribution dictated by the split weight enumerator.

There is a one-variable solution for weight 24.

n = 120) There is a one-variable solution for weight 24.

3.2. The Projective Plane of Order 10. Let C be the [111, 56, 11] code generated by vectors of a projective plane of order 10. It is known that the only vectors of weight 11 are the 111 lines of the plane. It was shown [7, 8] that C contains no vectors of weights 12,15 or 16. At this point the weight distribution of C was uniquely determined. It is not hard to see that a [111, 56, 11] code with A_{11} = 111, A_{i} = 0 unless i = 3, 0 (mod 4) and A_{12} = A_{15} = A_{16} = 0 must be the code of a plane of order 10. The sum of any two vectors of weight 11 can only have weight 20 so they must meet in exactly one point. Hence at most 11 vectors of weight 11 can contain the same point. There must be 11 if we count the number of 1’s in the matrix M of vectors of weight 11 by columns. From this it follows that any 2 points must be on exactly one line.

Let \overline{C} be the [112, 56, 12] doubly-even extended code of C, then \overline{A}_{12} = 111 and \overline{A}_{16} = 0. Note that any two vectors of weight 12 meet (indeed they meet in two points – the same point the corresponding weight 11 vectors met and the extended point). Lam [9] showed that there is no projective plane of order 10 by demonstrating, with computers running for a year, that C could not contain any vectors of weight 19. This was a contradiction as the unique solution for the weight distribution of C had A_{19} ≠ 0.

We examined \overline{C} with the stated assumptions. We consider the split weight distribution with respect to a vector of weight 12. We let S be the [100, 45, 20] shortened code and S^{⊥} be the [100, 55, 10] punctured code. Let b_{i} denote the number of vectors of weight i in S^{⊥}. All vectors in S^{⊥} have even weight. As b_{10} = 110 and b_{12} = 0 and S contains vectors of 16 unknown weights, it is possible to find the weight distributions of S and S^{⊥} in terms of one variable. The split weight enumerator can be computed and expressed in terms of one variable as well.

4. Appendix: Split weight distributions of selected codes

Since these split weight distribution tables are symmetrical around both their horizontal and vertical midpoints, we only display one quarter of the tables.

The putative [72, 36, 16] doubly-even self-dual extremal code partitioned into two parts, one being the support of a minimum weight vector.

1  0  0  0  0
0  0  0  0  0
0  0  0  0  0
0  0  0  0  0
0  0  0  0  2310
0  0  0  34496  0
0  0  123480  0  831600
0  84480  0  5396160  0
5082  0  8796480  0  62455470
0 2956800  0  198007040  0
91168  0  166529440  0  1176806400
0 29944320  0  1997318400  0
507045  0  922595520  0  6525588300
0 92843520  0  6196240512  0
890560  0  1620726800  0  11458978080

The putative [72, 36, 16] doubly-even self-dual extremal code partitioned into two parts, one being the support of a weight 20 vector.

1  0  0  0  0  0
0  0  0  0  0  0
0  0  0  0  0  0
0  0  0  0  0  476
0  0  0  0  11475  0
0  0  0  74460  0  338096
0  0  121380  0  3018435  0
0  40800  0  7956000  0  38079660
1258  0  5827260  0  152023860  0
0 940800  0  192637200  0  917613760
14637  0  71092980  0  1847582100  0
0 5986720  0  1220548320  0  5819294072
49640  0  240480300  0  6252934050  0
0 10967040  0  2237918760  0  10665686304

The putative [72, 36, 16] doubly-even self-dual extremal code partitioned into two parts, one being the support of a weight 24 vector. This distribution is not unique, but can be expressed in terms of a single variable.

1  0  0  0  0  0  0
0  0  0  0  0  0  0
0  0  0  0  0  0  2z
0  0  0  0  0  3312-12z  0
0  0  0  0  32706+30z  0  115920+64z
0  0  0  108192-40z  0  1493712-132z  0
0  0 88872+30z  0  5941728+120z  0  174z+21944944
0 16560-12z  0  7534800-20z  0  110157120+48z  0
207+2z 0 2782080-48z  0  193162464-330z  0  709708608-576z
0 232944+36z 0 114572752+300z  0  1668859392+768z  0
2208-8z 0 20714904-78z  0  1432718208-240z  0  5268973584-336z
0 880992-24z 0 429089472-240z  0  6252791040-672z  0
3360+12z 0 39876480+192z 0 2761268220+840z  0  10150959840+1344z

The putative [96, 48, 20] doubly-even self-dual extremal code partitioned into two parts, one being the support of a minimum weight vector.

1  0  0  0  0  0
0  0  0  0  0  0
0  0  0  0  0  0
0  0  0  0  0  0
0  0  0  0  0  0
0  0  0  0  0  5480
0  0  0  0  116025  0
0  0  0  792900  0  3587400
0  0  1561845  0  38674095  0
0  708300  0  137608800  0  658256800
32505  0  149665635  0  3903490260  0
0  39125000  0  8007527400  0  38155220800
1067925  0  5189589375  0  134888439900  0
0  830347740  0  169334868960  0  807213470256
14160950  0  68596589625  0  1783592557125  0
0  6975586400  0  1423096463100  0  6783305787000
76613625  0  371194697250  0  9650968485075  0
0 24546567000  0  5007424075200  0  23868921318600
176560450  0  855437680590  0  22241422629840  0
0 37220804400  0  7593113876400  0  36193606924800

The putative [96, 48, 20] doubly-even self-dual extremal code partitioned into two parts, one being the support of a weight 24 vector. This distribution is not unique, but can be expressed in terms of a single variable.

1  0  0  0  0  0  0
0  0  0  0  0  0  0
0  0  0  0  0  0  0
0  0  0  0  0  0  0
0  0  0  0  0  0  2z
0  0  0  0  0  37260-12z  0
0  0  0  0  321264+30z  0  1145676+56z
0  0  0  1217160-40z  0  16655220-84z  0
0  0  1286712+30z  0  85790529  0  316577520-70z
0  346380-12z  0  157963540+140z  0  2309802600+504z  0
8280+2z  0  94051692-168z  0  6525055656-630z  0  23981575968-896z
0 13967532+84z  0  6854100372+140z  0  99844822152-168z  0
233430-16z  0  2401572600+294z  0  166178862045+1680z  0  611041252080+2758z
0 216634608-240z  0  105554190168-1400z  0  1538135889948-2940z  0
2119680+56z 0  22816881360+96z  0  1579342749840-630z  0  5806772474580-1400z
0 1288676016+336z  0  628553881536+2560z  0  9158856560676+6300z  0
8162217-112z 0 86140360656-1092z  0  5962012330338-3600z  0  21921113408544-5250z
0 3110887080-168z  0  1517024811960-1400z  0  22105251775440-3600z  0
12507216+140z 0 133641088392+1680z  0  9250021438128+6300z  0  34009965750656+9600z

References

[1] E. Assmus and V. Pless, ”On the covering radius of extremal self-dual codes”, IEEE Trans. Inform. Th. 29 (1983),no. 3, 359–363.

[2] A.E. Brouwer and T. Verhoeff, ”An updated table of minimum-distance bounds for binary linear codes”, IEEE Trans. Inform. Th. 39 (1993) 662-677 as revised and updated at

http://www.win.tue.nl/math/dw/voorlincod.html

[3] J.H. Conway and V. Pless, ”An enumeration of self-dual codes”, IEEE Trans. Inform. Theory IT-37 1222-1225 (1991)

[4] J.H. Conway, N.J.A. Sloane Sphere packings, Lattices and Groups, Springer-Verlag, New York, 1988.

[5] W. C. Huffman, ”Automorphisms of Codes with Applications to Extremal Doubly Even Codes of Length 48”, IEEE Trans. Inform. Theory IT-28 511-521

[6] H.V. Koch, ”Unimodular Lattices and Self-dual Codes”, Proceedings of the International Congress of Mathematicians Berkeley, California, USA, 1986, pp 457-465.

[7] C.W.H. Lam, L. Thiel and S. Swiercz, ”The nonexistence of code words of weight 16 in a projective plane of order 10”, J. Combin. Theory Ser. A 42 (1986) 207-214.

[8] C.W.H. Lam, L. Thiel, S. Swiercz and J. McKay, ”The nonexistence of ovals in a projective plane of order 10”, Discrete Math. 45 (1983) 319-321.

[9] C.W.H. Lam, L. Thiel, S. Swiercz ”The nonexistence of finite projective planes of order 10”, Canad. J. Math. 41 (1989), no. 6, 1117–1123.

[10] V. Pless Introduction to the Theory of Error-Correcting Codes, second edition, Wiley, New York, 1989.

[11] Juriaan Simonis, ”MacWilliams Identities and Coordinate Partitions”, Linear Algebra Appl. 216:81-91 (1995).