New 5-Designs Constructed from the Lifted Golay Code over Z_{4}^{∗}

Masaaki Harada Department of Mathematical Sciences Yamagata University Yamagata 990, Japan

January 28, 1998

Abstract

It is shown that the lifted Golay code over ℤ_{4} contains several 5-designs. In particular, a 5-(24, 12, 1584) design and a 5-(24, 12, 1632) design are constructed for the first time.

1 Introduction

A t-(v, k, λ) design D is a set of v points with a collection of k-subsets called blocks, so that any t-points are contained in exactly λ blocks. A design with no repeated block is called simple. In this paper, we consider only simple designs. The complementary design of D is a design obtained by replacing each block in D by its complement. The incidence matrix of D is the matrix M = (m_{ij}) where m_{ij} = 1 if the j-th point is contained in the i-th block and m_{ij} = 0 otherwise. Two designs are isomorphic if the incidence matrix of one design can be obtained from the incidence matrix of the other by permuting its rows and columns.

A fundamental problem in design theory is to determine if there exists a design for a given set of parameters. Coding theory has made a substantial contribution to design theory. For example, the Assmus-Mattson theorem [1] determines whether the codewords of a specified weight in a code over GF (q) form a t-design. In particular, it is well known that the codewords of weight 8 in the binary extended Golay code form the Steiner system S(5, 8, 24), which is the unique 5-(24, 8, 1) design. Moreover, the codewords of weight 12 form a 5-(24, 12, 48) design which is known as the dodecad design. This 5-design is a unique design for the parameters such that every two blocks intersect in an even number of points (cf. [10]).

∗To appear in J. Combin. Designs

Recently a number of papers have studied self-dual codes over ℤ_{4} the ring of integers modulo 4 (cf., e.g. [2], [3], [5], [6] and the references given therein). Connections of self-dual codes over ℤ_{4} with unimodular lattices and binary nonlinear codes have been found. In this paper, we present a conncetion with desgins. Type II codes have been introduced by Bonnecaze, Solé, Bachoc and Mourrain [3], as a class of self-dual codes over ℤ_{4}. This class includes the octacode O_{8} of length 8 and the Hensel lifted Golay code of length 24. In this paper, we demonstrate that certain codewords in the lifted Golay code over ℤ_{4} form 5designs. In particular, a 5-(24, 12, 1584) design and a 5-(24, 12, 1632) design are constructed. From [8] and Table 3.37 in [4], these two designs are the first designs with these parameters.

2 Self-dual codes and the lifted Golay code

2.1 Self-dual codes

A code C of length n over ℤ_{4} is an additive subgroup of ℤ_{4}^{n}. An element of C is called a codeword. The Hamming weight of a codeword is the number of its non-zero components. The dual code C^{⊥} of C is defined as C^{⊥} = {x ∈ ℤ_{4}^{n}| x · y = 0 for all y ∈ C} where x · y = x_{1}y_{1} + ⋯ + x_{n}y_{n} (mod 4), x = (x_{1}, …, x_{n}) and y = (y_{1}, …, y_{n}). C is self-dual if C = C^{⊥}. We say that two codes are permutation-equivalent if one can be obtained from the other by permuting the coordinates. The symmetrized weight enumerator (s.w.e.) of a code C over ℤ_{4} is

swe_{C}(X, Y, Z) = ∑_{c∈C} X^{n_{0}(c)}Y^{n_{1}(c)}Z^{n_{2}(c)},

where n_{0}(c), n_{1}(c) and n_{2}(c) are the numbers of 0, ±1 and 2 components of c, respectively. Any code is permutation-equivalent to a code with generator matrix of the form

( \begin{matrix}I_{k_{1}} & A & B \\ 0 & 2I_{k_{2}} & 2D \end{matrix} ) ,  (1)

where A and D are matrices over ℤ_{2} and B is a matrix over ℤ_{4}. We say that a code with generator matrix (1) is of type 4^{k_{1}}2^{k_{2}} (cf. [5]). Every code C over ℤ_{4} has two binary codes C^{(1)} and C^{(2)} associated with C:

C^{(1)} = {c (mod 2) | c ∈ C} and
C^{(2)} = \{\frac{1}{2}c | c ∈ C, c ≡ 0 (mod 2)\}.

If C is of type 4^{k_{1}}2^{k_{2}} then C^{(1)} is a binary [n, k_{1}] code and C^{(2)} is a binary [n, k_{1} + k_{2}] code. Moreover, if C is a self-dual code of length n and type 4^{\frac{n}{2}} , then C^{(1)} = C^{(2)} and C^{(1)} is a doubly-even self-dual code (cf. [5]). Our terminology for codes over ℤ_{4} follows that in [5].

2.2 The lifted Golay code

The lifted Golay code G_{24} over ℤ_{4} is defined in [2] as the extended Hensel lifted quadratic residue code of length 24. G_{24} is a Type II code constructed from the cyclic code with generator polynomial

x^{11} + 2x^{10} + 3x^{9} + 3x^{7} + 3x^{6} + 3x^{5} + 2x^{4} + x + 3,

by appending 3 to the last coordinate of the generator vectors. The s.w.e. of G_{24} is given in [3]:

W = X^{24} + Z^{24} + 24288Y^{16}Z^{8} + 4096Y^{24} + 61824XY^{12}Z^{11}
+12144X^{2}Y^{8}Z^{14} + 680064X^{2}Y^{16}Z^{6} + 1133440X^{3}Y^{12}Z^{9} + 170016X^{4}Y^{8}Z^{12}
+1700160X^{4}Y^{16}Z^{4} + 4080384X^{5}Y^{12}Z^{7} + 765072X^{6}Y^{8}Z^{10} + 680064X^{6}Y^{16}Z^{2}
+4080384X^{7}Y^{12}Z^{5} + 759X^{8}Z^{16} + 1214400X^{8}Y^{8}Z^{8} + 24288X^{8}Y^{16}
+1133440X^{9}Y^{12}Z^{3} + 765072X^{10}Y^{8}Z^{6} + 61824X^{11}Y^{12}Z + 2576X^{12}Z^{12}
+170016X^{12}Y^{8}Z^{4} + 12144X^{14}Y^{8}Z^{2} + 759X^{16}Z^{8}.

The automorphism group of the binary Golay code is the Mathieu group M_{24}. In [9] Chapman shows that the automorphism group of the lifted Golay code is SL(2, 23).

Since G_{24} is of type 4^{12}, G_{24}^{(1)} = G_{24}^{(2)}. Moreover G_{24}^{(1)} is the binary Golay code of length 24. Thus the supports of the codewords of Hamming weight 8 form the Steiner system S(5, 8, 24). Similarly, the supports of the 2576 codewords corresponding to X^{12}Z^{12} in W form a 5-(24, 12, 48) design and the supports of the 759 codewords corresponding to X^{8}Z^{16} in W form a complementary design of S(5, 8, 24). It is shown in [6] that the supports of the codewords of Hamming weight 10 in the lifted Golay code and certain extremal double circulant Type II codes of length 24 form a 5-(24, 10, 36) design. In this paper, we consider not only the codewords of Hamming weight 12 but also the codewords corresponding to X^{12}Y^{8}Z^{4}. These are used to construct a 5-(24, 12, 1584) design and a 5-(24, 12, 1632) design.

3 5-designs in the lifted Golay code

3.1 A 5-(24, 12, 1584) design and a 5-(24, 12, 1632) design

We first investigate the 170016 codewords corresponding to X^{12}Y^{8}Z^{4} in W. Let A be a 170016 by 24 matrix whose rows are the above codewords. If v is a codeword corresponding to X^{12}Y^{8}Z^{4} then 3v is also a codeword corresponding to X^{12}Y^{8}Z^{4}, but 2v is not. Moreover it is easy to see that

A = ( \begin{matrix}B_{1} \\ 3B_{1} \end{matrix} ) ,

where B_{1} = (b_{ij}) is an 85008 by 24 matrix over ℤ_{4}. Now define an 85008 by 24 (1, 0)-matrix M_{1} = (m_{ij}) where m_{ij} = 1 if b_{ij} ≠ 0 and m_{ij} = 0 otherwise. We have verified by computer that M_{1} is an incidence matrix of a (simple) 5-(24, 12, 1584) design.

As mentioned in Section 2, the supports of the codewords corresponding to X^{12}Z^{12} in W form a simple 5-(24, 12, 48) design which is isomorphic to the dodecad design. Let M_{2} be the incidence matrix of this design. Then it is easy to see that the matrix

M_{3} = ( \begin{matrix}M_{1} \\ M_{2} \end{matrix} ) ,

is an incidence matrix for a 5-(24, 12, 1632) design, however this design may contain a repeated block. Let v and w be codewords corresponding to X^{12}Y^{8}Z^{4} and X^{12}Z^{12}, respectively. Assume that v and w have identical supports in M_{3}. Then the codeword v + w corresponds to X^{16}Y^{8}, which is a contradiction. Therefore the design is simple.

Kramer, Magliveras and Mesner [8] determined all 5-designs with the Mathieu group M_{24} as the automorphism group. Thus the automorphism groups of our 5-designs are not M_{24}. Information on simple t-designs is given in Table 3.37 of [4, p. 52]. From this table, our designs are the first 5-designs with these parameters. Note that the table in [4] misses some 5-designs in [8].

Since one can easily construct the two 5-designs from the lifted Golay code, to save space the incidence matrices are not listed here. However the incidence matrices are available on

the world wide web at http://kszaoh1.kj.yamagata-u.ac.jp/harada.

3.2 More 5-designs

Our computer search shows that the supports of the codewords of Hamming weight 13 form the complementary design of a 5-(24, 11, 336) design. Let M_{4} be the matrix over ℤ_{4} obtained from the codewords of Hamming weight 13. Since the Hamming weight 13 corresponds to 61824X^{11}Y^{12}Z in W,

M_{4} (mod 2) ≡ ( M_{2} ; M_{2} ; ⋮ ; M_{2} ) .

Moreover it is not hard to see that the automorphism group of this design is M_{24}. Thus this design must be isomorphic to the design in [8]. In addition, the supports of the 24288 codewords corresponding to X^{8}Y^{16} in W form a complementary design of the Steiner system S(5, 8, 24).

3.3 Summary

As a summary, we give 5-designs in the lifted Golay code in the following proposition.

Proposition 1 There exist 5-(24, 12, λ) designs for λ = 1584 and 1632. The lifted Golay code contains 5-(24, k, λ) designs for (k, λ) = (8, 1), (10, 36), (11, 336), (12, 48), (12, 1584) and (12, 1632).

4 Concluding remarks

It is well known that the block intersection numbers of S(5, 8, 24) are 0, 2 and 4 and the incidence matrix of S(5, 8, 24) generates the binary Golay code. We have verified that the incidence matrix of any of the above eight designs cannot generate a self-orthogonal code over ℤ_{4}, as well as the lifted Golay code.

Since the supports of the codewords of Hamming weight 8 form S(5, 8, 24), its automorphism group is M_{24}. It is shown in [2] that the supports of the codewords of Hamming weight 10 form a 3-(24, 10, 360) design and P SL(2, 23) acts on the design. This design is also a 5-design. Let S be the set of the codewords of Hamming weight 10, then S (mod 2) is the S(5, 8, 24). Kitazume [7] shows that the automorphism group of the design is P SL(2, 23) using properties of the design and S(5, 8, 24).

Now we give an observation of the extremal Type II codes in [6] such that the supports of the codewords of Hamming weight 10 form 5-(24, 10, 36) designs.

Proposition 2 Let D be a double circulant code of length 24 such that D^{(1)} = D^{(2)}, D^{(1)} is the binary Golay code and D has the same symmetrized weight enumerator as the lifted Golay code. Then the supports of the codewords of Hamming weight 10 in D form a 5-(24, 10, 36) design.

We conjecture that the above proposition is ture for a code satisfying the condition. In general, we prompt the following question:

Question. Is there a result analogous to the Assmus-Mattson theorem for a code over ℤ_{4}?

Acknowledgments. The author would like to thank Dr. Masaaki Kitazume for useful discussions and comments. The author would like to thank Dr. Edward F. Assmus, Jr., Dr. Steven T. Dougherty, Dr. T. Aaron Gulliver, Dr. Patrick Solé and Dr. Vladimir D. Tonchev for reading the manuscript and making helpful comments. The author would like to thank the referees for their useful comments, in particular one of them supplied a useful reference [8]. Thanks are due also to Dr. Akihiro Munemasa for helpful conversations.

References

[1] E.F. Assmus, Jr., and H.F. Mattson, Jr., New 5-designs, J. Combin. Theory 6 (1969), 122–151.

[2] A. Bonnecaze, P. Solé and A.R. Calderbank, Quaternary quadratic residue codes and unimodular lattices, IEEE Trans. Inform. Theory 41 (1995), 366–377.

[3] A. Bonnecaze, P. Solé, C. Bachoc and B. Mourrain, Type II codes over ℤ_{4}, IEEE Trans. Inform. Theory 43 (1997), 969–976.

[4] C.J. Colbourn and J.H. Dinitz, The CRC handbook of combinatorial designs, CRC Press, Boca Raton, 1996.

[5] J.H. Conway and N.J.A. Sloane, Self-dual codes over the integers modulo 4, J. Combin. Theory Ser. A 62 (1993), 30–45.

[6] T.A. Gulliver and M. Harada, Extremal double circulant Type II codes over ℤ_{4} and construction of 5-(24, 10, 36) designs, (submitted to Discrete Math.).

[7] M. Kitazume, private communication, October 1996.

[8] E.S. Kramer, S.S. Magliveras and D.M. Mesner, t-designs from the large Mathieu groups, Discrete Math. 36 (1981), 171–189.

[9] P. Solé, private communication, October 1996.

[10] V.D. Tonchev, A characterization of designs related to dodecads in the Witt system S(5, 8, 24), J. Combin. Theory Ser. A 43 (1986), 219–227.