MOG (Miracle Octad Generator)

This page provides a tool for exploring the binary Golay code and its automorphism group M₂₄ in its standard representation on 24 objects, using Curtis' Miracle Octad Generator (MOG). It is inspired by a similar page by Simon Nickerson. The MOG is described in detail in Chapter 11 of the book Sphere Packings, Lattices and Groups by Conway and Sloane (hereafter abbreviated SPLAG). Below the tool is a summary of the theory and a description of the orbit classifications.

You can click the squares to select/unselect any subset of the 24 positions in the MOG. The label at the top shows the classification label of the current subset, using the notation described below as well as in SPLAG, Ch. 10, section 2.6. The buttons perform the following operations:

• Complete - given 5 squares in the MOG, shows the 3 additional squares that completes the given squares to an octad. This completion is always unique, because the octads of the MOG form a (24,8,5) Steiner system.
• Clear - clears all selected squares.
• Complement - toggles the selected/unselected status of all squares, replacing a subset of the MOG with its complement.
• Sextet - given 4 squares in the MOG (a tetrad), shows the other 5 tetrads (in different colors) that completes the given tetrad to a sextet. A sextet has the property that the union of any 2 tetrads form an octad.
• Dual Rep. - Gives a subset of size at most 4 congruent (modulo a Golay codeword) to the current subset. The resulting subset is uniquely determined except in the case of a subset of size 4, when it may be any of the six tetrads of a sextet.
• Orbit - given any subset S of the MOG, shows the orbits of the set stabilizer of S in M₂₄. Each orbit is given a different color. The label on a square indicates the classification label of the subset that would result if that square were added to or removed from S. An asterisk marks squares in S.
• Block - in addition to the information provided by Orbit, this also provides the block decomposition of each orbit with a smaller colored square at the center of each square. This button is only active for subsets of size at most 12 for which the action of the stabilizer is imprimitive. For the class T₁₀, the orbit of size 12 has two block decompositions (3 blocks of size 4, and 4 blocks of size 3); only the latter is currently shown.

Let Ω denote the set of 24 positions of the MOG. The set P(Ω) of subsets of Ω form a 24-dimensional vector space over F₂, the field of 2 elements, with the group operation being symmetric difference. The binary Golay code G is a 12-dimensional subspace of P(Ω), closed under complementation, with 1 subset of size 0, 759 subsets of size 8 (called octads), 2576 subsets of size 12 (called dodecads), 759 subsets of size 16, and 1 subset of size 24. See SPLAG, Ch. 11, for a construction of G on the MOG. Any 5 elements of Ω lie in a unique octad; in the above tool, if 5 elements are selected, then clicking on "Complete" will show the other 3 elements that complete the 5 selected elements to an octad. The Mathieu group M₂₄ is the set of permutations of Ω preserving G. It is a simple group of order 24*23*22*21*20*16*3 = 244823040, and is quintuply transitive on Ω.

Consider the quotient group G*=P(Ω)/G. Since G contains no nonempty subsets of size less than 8, it follows that if S and T are two subsets of Ω of size at most 4, then S and T lie in distinct cosets of G*, except possibly in the case when S and T are disjoint subsets of size 4. Since any two subsets of size 4 in a coset must be disjoint, there can be at most 6 subsets of size 4 in a coset. This accounts for at least C(24,0)+C(24,1)+C(24,2)+C(24,3)+C(24,4)/6 cosets, but that number is 4096 = 2¹², exactly the number of cosets in G*. It follows that every coset of G* either contains a unique element of size at most 3, or else 6 disjoint subsets of size 4. In the latter case, the union of any two of the subsets of size 4 (called tetrads) is in G and is therefore an octad; a set of 6 tetrads having this property is called a sextet. Every tetrad lies in a unique sextet. There are C(24,4)/6 = 1771 = 7*11*23 sextets. In the above tool, if a tetrad is selected, then clicking on "Sextet" will show all the tetrads in the sextet containing the selected tetrad. For any subset of Ω, clicking on "Dual Rep." will replace the current subset with a minimal coset representative in G*.

Given any S in P(Ω), a minimal coset representative of S in G* can be computed by the following algorithm. If S has size at most 4, then we are done. Otherwise, choose any 5 elements in S and complete it to an octad X (SPLAG, Ch. 11 describes how to do octad completion). Replace S with S+X, which lies in the same coset as S. Since X has at least 5 elements in common with S, in passing from S to S+X, we lose at least 5 elements and gain at most 3. Therefore we have reduced the size of S. Repeat these steps until we have a set of size at most 4.

M₂₄ acts on P(Ω). According to SPLAG, Ch. 10, section 2.6, a subset of size n < 12 is classified as special if it contains or is contained in an octad, umbral if it is contained in a dodecad (but not an octad), and otherwise transverse. These orbits of P(Ω) are denoted by S_n, U_n, and T_n respectively. A subset of size 12 is umbral if it is a dodecad, extraspecial if it contains 3 octads, special if it contains exactly 1 octad, penumbral if it contains exactly 11 points of a dodecad, and transverse otherwise. These orbits of P(Ω) are denoted by U₁₂, S₁₂⁺, S₁₂, U₁₂^-, and T₁₂ respectively. Subsets of size n>12 are described by the same terms as their complements, so that a set lies in S_n, U_n, or T_n if and only if its complement lies in S_24-n, U_24-n, or T_24-n, respectively.

The orbits of the action of M₂₄ on P(Ω) can be distinguished by the following invariants. Let S be an element of P(Ω). Obviously, the cardinality of S is an invariant. Let S* be the set of minimal coset representatives of S in G* (S* will have either one element of size at most 3, or six elements of size 4). The cardinality of the elements of S* is an invariant. The multiset of intersection sizes of each of the elements of S* with S is also an invariant. It turns out that these three invariants are sufficient to distinguish the orbits of P(Ω), and form a complete set of invariants. The table of invariants for each orbit of size between 6 and 12 is given below. (For sets of size < 6, there is only one orbit of each size, by the quintuple transitivity of M₂₄.)

If S is an element of P(Ω), let Stab(S) be the subgroup of M₂₄ stabilizing S as a set. Consider the action of Stab(S) on Ω. It turns out that two elements x, y of Ω lie in the same orbit of Stab(S) if and only if the subsets S + {x} and S + {y} lie in the same orbit in the action of M₂₄ on P(Ω). In SPLAG, Ch. 10, Figure 10.1, there is a diagram indicating how many ways there are to remove or add an element from a given class of size n to produce a given class of size n-1 or n+1. In the above tool, these orbits can be shown by clicking the "Orbit" button.

In some cases (including, but not limited to, those cases where a minimal coset representative has size 4), the action of Stab(S) on Ω is imprimitive on some orbits, and the block decomposition of these orbits can be shown by clicking the "Block" button. (Note that for T₁₀, there are 2 block decompositions for the orbit of size 12; only one of them is shown.)

A summary of the imprimitive orbits is given in the table below. An equation such as 20=5*4 means an orbit of size 20 which splits into 5 blocks of size 4. If an equation appears multiple times, that means there are multiple orbits which decompose into blocks in the indicated way. When not obvious, a class name appears (e.g. U₈ instead of just 8) to indicate the class to which an orbit or block belongs.