We first consider integral lexicographic codes (henceforth lexicodes). We enumerate all (infinite to the left) sequences of nonnegative integers that differ in at least positions from any previous sequence. The first few of these (with ) are the following:
and so forth. But after all those are done, we can continue with:
and so forth. After we have finished with all these, we can continue with
and so forth.
I think one of the nicest possible properties a code can have is linearity (i.e. it forms a vector space over some field). However, it might not appear that this lexicographic code is linear. First of all, there is no obvious field of scalars (since is certainly not a field). Furthermore, the addition and multiplication don’t work out correctly. If we add …00222 and …01012, we get …01234, but this is not in our lexicode. Multiplication doesn’t work either: if we multiply …01012 by 2, we get …02024, which is also not in our lexicode.
However, this lexicode is linear! It forms a vector space over the field of (finite) nimbers! So lexicographic codes are mysteriously connected to combinatorial games.
So that’s one kind of lexicode. We can also consider binary lexicodes. In this case, we will restrict ourselves to 24-bit binary lexicodes with . The first few sequences are
and so forth. The list will ultimately contain 4096 sequences. There are 759 of them that contain exactly 8 1’s. These 759 have a very interesting property: for any five-element subset of , there is exactly one (of the 759) sequences that has 1’s in exactly those five positions. In other words, these sequences form the Steiner system .
Now for the simple groups. Well, the Mathieu group is the automorphism group of . is one of the 26 sporadic finite simple groups.