Decoding the Mathieu group M12


Authors Robert F. Bailey and John N. Bray.
Title Decoding the Mathieu group M12.
Published as Advances in Mathematics of Communications, to appear.
Availability DVI-format (requires this eps-file too) or PDF-format. Older versions are DVI-format or PDF-format.
Abstract The sporadic Mathieu group M12 can be viewed as an error-correcting code, where the codewords are the group’s elements written as permutations in list form, and with the usual Hamming distance. We investigate the properties of this group as a code, in particular determining completely the probabilities of successful and ambiguous decoding of words with more than 3 errors (which is the number that can be guaranteed to be corrected).

Extra information

The GAP program for dealing with 4 errors is here, and the uncovering used is here. (We also dealt with this case in a more theoretical manner, see the paper.)
The GAP program for dealing with 5 errors is here, and the uncovering used is here.
The GAP programs for dealing with 6 errors are here, here and here, and the uncovering used (also required) is here.
A sample GAP program for dealing with 7 errors is here, which loads this file. This program deals with the case 7 maps to 1 (where 8, 9, 10, 11, 12 are fixed). The programs to deal with the cases 7 maps to 2, 3, 4, 5, 6, 8, 9, 10, 11, 12 are isomorphic to this one.
Uncoverings suitable for (respectively) 1, 2, 3, 4, 5 and 6 errors are here, here, here, here, here and here.
The uncovering for 7 errors consists of all 792 5-element subsets of {1, . . . , 12}.
A here is file containing all the above uncoverings.
We have not provided the output files of the GAP programs. Some are rather large.

A MAGMA program for producing the (interesting) yellow words at distance 7 is here, and a quicker version is here. The resulting 1161 such words are here.

A newer program for determining word colour, and M12 orbits on these words by conjugation is available, and requires this data. The results of this search are available in various files that are readable both by humans and MAGMA.

Finally, this is a link to the La Jolla Covering Repository.

Last updated 26th September 2007
John N. Bray