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

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, and let $s = |\{ i\ |\ A_i^\perp \not= 0, 0.
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.