Binary Golay code

The binary Golay code is an error-correcting code which encodes 12 bits of data in a 24-bit word in such a way that any triple-bit error can be corrected and any quadruple-bit error can be detected. In mathematical terms, the binary Golay code consists of a 12-dimensional subspace W of the space V=F₂²⁴ of 24-bit words such that any two distinct elements of W differ in at least eight coordinates or, equivalently, such that any non-zero element of W has at least eight non-zero coordinates. The possible sets of non-zero coordinates as w ranges over W are called code words. In the binary Golay code, all code words have order 0, 8, 12, 16, or 24. Up to relabelling coordinates, W is unique.

Constructions

1. Lexicographic code: Order the vectors in V lexicographically (i.e., interpret them as unsigned 24-bit binary integers and take the usual ordering). Starting with w₁ = 0, define w₂, w₃, ..., w₁₂ by the rule that w_n is the smallest integer which differs from all linear combinations of previous elements in at least eight coordinates. Then W can be defined as the span of w₁, ..., w₁₂.
2. Quadratic residue code: Consider the set N of quadratic non-residues (mod 23). This is an 11-element subset of the cyclic group Z/23Z. Consider the translates t+N of this subset. Augment each translate to a 12-element set S_t by adding an element ∞. Then labelling the basis elements of V by 0, 1, 2, ..., 22, ∞, W can be defined as the span of the words S_t together with the word consisting of all basis vectors.

Mathieu groups

The Mathieu groups were the first known sporadic groups. The largest of them, M₂₄, is the automorphism group of the binary Golay code, i.e., the group of permutations of coordinates mapping W to itself. We can also regard it as the intersection of S₂₄ and Stab(W) in Aut(V). This is a finite simple group. The simple subgroups M₂₃, M₂₂, M₁₂, and M₁₁ can be defined as the stabilizers in M₂₄ of a single coordinate, an ordered pair of coordinates, a 12-element subset of the coordinates corresponding to a code word, and a 12-element code word together with a single coordinate, respectively.

See:

• Conway, J. H.; Curtis, R. T.; Norton, S. P.; Parker, R. A.; Wilson, R. A. (1985). Atlas of finite groups. Maximal subgroups and ordinary characters for simple groups. With computational assistance from J. G. Thackray. Eynsham: Oxford University Press. ISBN 0-19-853199-0