miracle octad generator
The Miracle Octad Generator (MOG) is a construction of the [24,12,8] extended binary Golay code . 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 (the field of 4 elements). The labels are from top to bottom, where is a cube root of unity. The code consists of subsets of the 24 squares of the array which satisfy the following conditions:
-
β’
the parities of the number of elements in in each of the 6 columns, and in the top row, are the same
-
β’
the sums of the row labels for elements of in each column form an element of the hexacode.
For example:
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 form an element of the hexacode. Hence, this subset of the MOG is an element of .
Notation: For any subset of the MOG, let us write for the element of corresponding to the column sums. Hence, the second condition above says that is in the hexacode for any .
When we say that a column is βevenβ or βoddβ, we are referring to the of the number of elements of in the column. When we speak of the βsumβ of a column, we are referring to the sum of the row labels of for that column, i.e., the component of for that column.
2 Proof that the construction gives a [24,12,8] code
Let us note a few facts about and the MOG.
Fact 1
is an even (http://planetmath.org/EvenCode) linear code of 24 over , 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 is a doubly even code (the weight of any element is divisible by 4). Let be an element of . If the columns of are even, then it is clear that is divisible by 4. Suppose the columns of are odd. Let (resp., ) denote the number of columns consisting of 1 (resp., 3) elements, for which the top row is filled. Let (resp., ) denote the number of columns consisting of 1 (resp., 3) elements, for which the top row is empty. The defining conditions of imply that is odd. By Fact 2, the number of 0βs in is equal to , which is therefore even by a property of the hexacode. So is odd. Since there are 6 columns, we have . Hence
Furthermore, it is not difficult to see that an element of weight 4 is impossible, hence the minimum weight of is 8. So the only possible weights of elements of are 0, 8, 12, 16, and 24.
To calculate the of , 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 = . Hence has 12, so it is a [24,12,8] code.
3 Further facts about the binary Golay code
Elements of of weight 8 are called octads. Elements of of weight 12 are called dodecads.
The octads of 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 3-problems (http://planetmath.org/hexacode) or 5-problems (http://planetmath.org/hexacode) for the hexacode. For a detailed procedure, see ([1], 11.6).
The automorphism group of is the largest Mathieu group , one of the sporadic simple groups.
The code is used in the construction of the Leech lattice (http://planetmath.org/LatticeInMathbbRn), whose automorphism group is the largest Conway group (sometimes written ). The quotient of by its center, called , is a sporadic simple group. The group 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. Springer-Verlag, 1999.
- 2 Robert L. Griess, Jr. Twelve Sporadic Groups. Springer-Verlag, 1998.
- 3 R. T. Curtis. On subgroups of , I: lattice stabilizers. Journal of Algebra, 27 (1973), 549-573.
- 4 R. T. Curtis. A new combinatorial approach to . Proceedings of the Cambridge Philosophical Society 79 (1976), 25-42.
Title | miracle octad generator |
Canonical name | MiracleOctadGenerator |
Date of creation | 2013-03-22 18:43:14 |
Last modified on | 2013-03-22 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 |