Daily Archives: 2008/05/25

The Assmus-Mattson Theorem, Golay codes, and Mathieu groups

Posted on by

A block design is a pair (X,B), where X is a non-empty finite set of v>0 elements called points, and B is a non-empty finite multiset of size b whose elements are called blocks, such that each block is a non-empty finite multiset of k points. A design without repeated blocks is called a simple block design. If every subset of points of size t is contained in exactly \lambda blocks the the block design is called a t—(v,k,\lambda) design (or simply a t-design when the parameters are not specfied). When \lambda = 1 then the block design is called a S(t,k,v) Steiner system.

Let C be an [n,k,d] code and let C_i = \{ c \in C\ |\ wt(c) = i\} denote the weight i subset of codewords of weight i. For each codeword c\in C, let supp(c)=\{i\ |\ c_i\not= 0\} denote the support of the codeword.

The first example below means that the binary [24,12,8]-code C has the property that the (support of the) codewords of weight 8 (resp, 12, 16) form a 5-design.

Example: Let $C$ denote the extended binary Golay code of length 24. This is a self-dual [24,12,8]-code. The set X_8 = \{supp(c)\ |\ c \in C_8\} is a 5-(24, 8, 1) design; X_{12} = \{supp(c)\ |\ c \in C_{12}\} is a 5-(24, 12, 48) design;and, X_{16} = \{supp(c)\ |\ c \in C_{16}\} is a 5-(24, 16, 78) design.

This is a consequence of the following theorem of Assmus and Mattson.

Assmus and Mattson Theorem (section 8.4, page 303 of [HP]):

Let A_0, A_1, ..., A_n be the weight distribution of the codewords in a binary linear [n , k, d] code C, and let A_0^\perp, A_1^\perp, ..., A_n^\perp be the weight distribution of the codewords in its dual [n,n-k, d^\perp] code C^\perp. Fix a t, 0<t<d, and let s = |\{ i\ |\ A_i^\perp \not= 0, 0<i\leq n-t\, \}|.
Assume s\leq d-t.

  • If A_i\not= 0 and d\leq i\leq n then C_i = \{ c \in C\ |\ wt(c) = i\} holds a simple t-design.
  • If A_i^\perp\not= 0 and d^\perp\leq i\leq n-t then C_i^\perp = \{ c \in C^\perp \ |\ wt(c) = i\} holds a simple t–design.
  • If A_i^\perp\not= 0 and d^\perp\leq i\leq n-t then C_i^\perp = \{ c \in C^\perp \ |\ wt(c) = i\} holds a simple t–design.

In the Assmus and Mattson Theorem, X is the set \{1,2,...,n\} of coordinate locations and B = \{supp(c)\ |\ c \in C_i\} is the set of supports of the codewords of C of weight i. Therefore, the parameters of the t-design for C_i are

  • t = given,
  • v = n,
  • k = i, (this k is not to be confused with dim(C)!),
  • b = A_i,
  • \lambda = b*binomial(k,t)/binomial(v,t)

(by Theorem 8.1.6, p. 294, in \cite{HP}). Here is a SAGE example.


sage: C = ExtendedBinaryGolayCode()
sage: C.assmus_mattson_designs(5)
['weights from C: ',
[8, 12, 16, 24],
'designs from C: ',
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)], [5, (24, 24, 1)]],
'weights from C*: ',
[8, 12, 16],
'designs from C*: ',
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)]]]
sage: C.assmus_mattson_designs(6)
0

The automorphism group of the extended binary Golay code is the Mathieu group M_{24}. Moreover, the code is spanned by the codewords of weight 8.

References:
[HP] W. C. Huffman, V. Pless, Fundamentals of error-correcting codes, Cambridge Univ. Press, 2003.
[CvL] P. Cameron, J. van Lint, Graphs, codes and designs, Cambridge Univ. Press, 1980.