miracle octad generator
The Miracle Octad Generator (MOG) is a construction of the [24,12,8] extended binary Golay code ${\mathrm{\pi \x9d\x92\u2019}}_{24}$. It makes use of the hexacode. The notation [24,12,8] indicates that this linear code^{} has length (http://planetmath.org/LinearCode) 24, dimension (http://planetmath.org/LinearCode) 12, and minimum weight (http://planetmath.org/MinimumDistance) 8.
The construction is originally due to R. T. Curtis ([3], [4]). The description of the MOG below is taken from [1], Chapter 11. A proof that the construction gives a [24,12,8] code is given below. A proof of the uniqueness of the binary Golay code (up to permutation^{} of the coordinates) can be found in [2], Chapter 5.
1 Construction
The MOG consists of a rectangular array of 4 rows and 6 columns. The rows of the MOG are labelled with elements of ${\mathrm{\pi \x9d\x94\xbd}}_{4}$ (the field of 4 elements). The labels are $0,1,\mathrm{{\rm O}\x89},\stackrel{{\rm B}\u2015}{\mathrm{{\rm O}\x89}}$ from top to bottom, where $\mathrm{{\rm O}\x89}$ is a cube root of unity. The code ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ consists of subsets $S$ of the 24 squares of the array which satisfy the following conditions:

β’
the parities of the number of elements in $S$ in each of the 6 columns, and in the top row, are the same

β’
the sums of the row labels for elements of $S$ in each column form an element of the hexacode.
For example:
$$\begin{array}{ccccccc}\hfill 0\hfill & & \hfill *\hfill & & & \hfill *\hfill & \\ \hfill 1\hfill & & \hfill *\hfill & & & & \hfill *\hfill \\ \hfill \mathrm{{\rm O}\x89}\hfill & & & & \hfill *\hfill & \hfill *\hfill & \hfill *\hfill \\ \hfill \stackrel{{\rm B}\u2015}{\mathrm{{\rm O}\x89}}\hfill & & & & \hfill *\hfill & & \\ & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill \mathrm{{\rm O}\x89}\hfill & \hfill \stackrel{{\rm B}\u2015}{\mathrm{{\rm O}\x89}}\hfill \end{array}$$ 
In a MOG diagram, asterisks indicate a subset of the 24 squares. On the left side, we have written the row labels, and at the bottom we have written the column sums for our subset. For the subset above, each of the columns, as well as the top row, contains 2 elements, and the column sums $\mathrm{01\beta \x80\x89\beta \x80\x8901}\beta \x81\u2019\mathrm{{\rm O}\x89}\beta \x81\u2019\stackrel{{\rm B}\u2015}{\mathrm{{\rm O}\x89}}$ form an element of the hexacode. Hence, this subset of the MOG is an element of ${\mathrm{\pi \x9d\x92\u2019}}_{24}$.
Notation: For $S$ any subset of the MOG, let us write $\mathrm{\Xi \pounds}\beta \x81\u2019(S)$ for the element of ${\mathrm{\pi \x9d\x94\xbd}}_{4}^{6}$ corresponding to the column sums. Hence, the second condition above says that $\mathrm{\Xi \pounds}\beta \x81\u2019(S)$ is in the hexacode for any $S\beta \x88\x88{\mathrm{\pi \x9d\x92\u2019}}_{24}$.
When we say that a column is βevenβ or βoddβ, we are referring to the of the number of elements of $S$ in the column. When we speak of the βsumβ of a column, we are referring to the sum of the row labels of $S$ for that column, i.e., the component^{} of $\mathrm{\Xi \pounds}\beta \x81\u2019(S)$ for that column.
2 Proof that the construction gives a [24,12,8] code
Let us note a few facts about ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ and the MOG.
Fact 1
${\mathrm{\pi \x9d\x92\u2019}}_{24}$ is an even (http://planetmath.org/EvenCode) linear code of 24 over ${\mathrm{F}}_{\mathrm{2}}$, and is closed under complementation.
This follows from the linearity of the two conditions above (which in turn follows from the linearity of the hexacode), and the fact that the and column sums do not change under complementation.
Fact 2
If an even column has sum 0, then it contains 0 or 4 elements. If an odd column has sum 0, then the top row entry is in the column iff the column consists of exactly 1 element (and otherwise it consists of exactly 3 elements).
Fact 3
If an even column has nonzero sum, then it consists of 2 elements. If an odd column has nonzero sum, then the top row entry is in the column iff the column consists of exactly 3 elements (and otherwise it consists of exactly 1 element).
From these facts, we can show that ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ is a doubly even code (the weight of any element is divisible by 4). Let $S$ be an element of ${\mathrm{\pi \x9d\x92\u2019}}_{24}$. If the columns of $S$ are even, then it is clear that $S$ is divisible by 4. Suppose the columns of $S$ are odd. Let ${t}_{1}$ (resp., ${t}_{3}$) denote the number of columns consisting of 1 (resp., 3) elements, for which the top row is filled. Let ${u}_{1}$ (resp., ${u}_{3}$) denote the number of columns consisting of 1 (resp., 3) elements, for which the top row is empty. The defining conditions of ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ imply that ${t}_{1}+{t}_{3}$ is odd. By Fact 2, the number of 0βs in $\mathrm{\Xi \pounds}\beta \x81\u2019(S)$ is equal to ${t}_{1}+{u}_{3}$, which is therefore even by a property of the hexacode. So ${t}_{3}+{u}_{3}$ is odd. Since there are 6 columns, we have ${t}_{1}+{t}_{3}+{u}_{1}+{u}_{3}=6$. Hence
$S$  $=$  $3\beta \x81\u2019{t}_{3}+3\beta \x81\u2019{u}_{3}+{t}_{1}+{u}_{1}$  
$=$  $3\beta \x81\u2019{t}_{3}+3\beta \x81\u2019{u}_{3}+{t}_{1}+(6{t}_{1}{t}_{3}{u}_{3})$  
$=$  $2\beta \x81\u2019({t}_{3}+{u}_{3})+6$  
$\beta \x89\u2018$  $0\phantom{\rule{veryverythickmathspace}{0ex}}(mod4).$ 
Furthermore, it is not difficult to see that an element of weight 4 is impossible, hence the minimum weight of ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ is 8. So the only possible weights of elements of ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ are 0, 8, 12, 16, and 24.
To calculate the of ${\mathrm{\pi \x9d\x92\u2019}}_{24}$, we need to count the number of elements of each weight. Weights 0 and 24 are obvious, and the counts for weight 8 and weight 16 are the same. So we need only count weights 8 and 12. This is not difficult using the defining conditions above, and knowledge of the hexacode; the final result is that the number of elements of weights 0,8,12,16,and 24 are 1, 759, 2576, 759, and 1, respectively, for a total of 4096 = ${2}^{12}$. Hence ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ has 12, so it is a [24,12,8] code.
3 Further facts about the binary Golay code
Elements of ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ of weight 8 are called octads. Elements of ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ of weight 12 are called dodecads.
The octads of ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ form a (5,8,24) Steiner system^{}. In other words, given any 5 squares in the MOG, there is a unique way to add 3 squares to form an octad. To complete^{} an octad, it is necessary to solve 3problems (http://planetmath.org/hexacode) or 5problems (http://planetmath.org/hexacode) for the hexacode. For a detailed procedure, see ([1], 11.6).
The automorphism group^{} of ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ is the largest Mathieu group^{} ${M}_{24}$, one of the sporadic simple groups.
The code ${\mathrm{\pi \x9d\x92\u2019}}_{24}$ is used in the construction of the Leech lattice^{} (http://planetmath.org/LatticeInMathbbRn), whose automorphism group is the largest Conway group $C\beta \x81\u2019{o}_{0}$ (sometimes written $\beta \x8b\x850$). The quotient of $C\beta \x81\u2019{o}_{0}$ by its center, called $C\beta \x81\u2019{o}_{1}$, is a sporadic simple group. The group $C\beta \x81\u2019{o}_{1}$ plays an important role in the construction of the monster group, the largest sporadic simple group of all.
References
 1 J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices, and Groups. SpringerVerlag, 1999.
 2 Robert L. Griess, Jr. Twelve Sporadic Groups. SpringerVerlag, 1998.
 3 R. T. Curtis. On subgroups^{} of $\beta \x8b\x850$, I: lattice stabilizers^{}. Journal of Algebra, 27 (1973), 549573.
 4 R. T. Curtis. A new combinatorial approach to ${M}_{24}$. Proceedings of the Cambridge Philosophical Society 79 (1976), 2542.
Title  miracle octad generator 
Canonical name  MiracleOctadGenerator 
Date of creation  20130322 18:43:14 
Last modified on  20130322 18:43:14 
Owner  monster (22721) 
Last modified by  monster (22721) 
Numerical id  8 
Author  monster (22721) 
Entry type  Derivation 
Classification  msc 20B25 
Classification  msc 20B20 
Classification  msc 51E10 
Classification  msc 94B05 
Synonym  MOG 
Related topic  hexacode 
Related topic  LeechLattice 
Related topic  Hexacode 
Defines  miracle octad generator 
Defines  MOG 
Defines  octad 
Defines  dodecad 