David Madore's WebLog: On the beauty of the Steiner system of index (5,8,24)

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #0308 [older|newer] / Entrée #0308 [précédente|suivante]:


On the beauty of the Steiner system of index (5,8,24)

If there were a beauty prize for mathematical objects, I think the Steiner system of index (5,8,24) (I will describe what this means in a moment) would be one of the most serious candidates. It is something extremely easy to define (but not so easy to exhibit or represent!) but of breathtaking intellectual elegance and having absolutely unique and “magical” properties. This is the sort of mathematical objects that holds (for me) all the fascination that numerology can have for some people, except that there is “really something” there (when I get mystical, I think: some deep insight into the fabric of reality).

To define naïvely what a Steiner system of index (5,8,24) means is, as I just said, very easy: it is a set of 24 “points” (objects, elements, whatever) together with 759 “blocks”, each consisting of 8 points, having the property that any 5 of the 24 points lie in one and only one of the 759 blocks. I know this doesn't sound impressive when said like that.

Maybe to give the feel of things I should explicitly describe the Steiner system of index (2,3,7) (the projective plane over F2, to be precise, also called the “Fano plane”). Consider 7 objects (“points”) which will be labeled (1:0:0), (0:1:0), (1:1:0), (0:0:1), (1:0:1), (0:1:1) and (1:1:1) (the labels are unimportant: I could just as well be calling these objects “red”, “green”, “yellow”, “blue”, “magenta”, “cyan” and “white”, or “Valor”, “Compassion”, “Sacrifice”, “Honesty”, “Honor”, “Justice” and “Spirituality” or whatever I wanted); and define the following seven blocks of three objects each: {(0:1:0), (0:0:1), (0:1:1)}, {(1:0:0), (0:0:1), (1:0:1)}, {(1:1:0), (0:0:1), (1:1:1)}, {(1:0:0), (0:1:0), (1:1:0)}, {(0:1:0), (1:0:1), (1:1:1)}, {(1:0:0), (0:1:1), (1:1:1)} and {(1:1:0), (1:0:1), (0:1:1)}. Then any choice of two of the seven points belongs to one, and only one, of the seven blocks. Try it!

The previous example has a classical geometric representation: draw an equilateral triangle, label its vertices (1:0:0), (0:1:0) and (0:0:1); label (1:1:0) the middle of the edge joining (1:0:0) and (0:1:0), label (0:1:1) the middle of the edge joining (0:1:0) and (0:0:1) and label (1:0:1) the middle of the third edge of the triangle; finally, label (1:1:1) the center of the triangle, and draw the inscribed center of the triangle as well as the three medians (which are also at once mediators, heights and bisectors since the triangle is equilateral). This defines seven points in the plane, and seven “lines” between them (the three sides of the triangles, the three medians and the seventh “line” is the inscribed circle), each of them joining exactly three points, and it is easily seen that any two points are joined by exactly one line.

Now the Steiner system of index (5,8,24) does the same with different numbers: there are 24 points and blocks of 8 points (“octads”) are defined such that any set of 5 different points belongs to exactly one of the octads. The first remarkable, and by no means obvious fact, is that there is only one Steiner system of index (5,8,24): if you find two of them, then there is some way of reordering the 24 points so that in fact they agree exactly. So it is justified to speak of the such Steiner system. (There is also a unique Steiner system of index (2,3,7); however not all Steiner systems are unique for their index: for example, there are exactly 2 Steiner systems of index (2,3,13), 18 of index (2,4,25). Also, not all Steiner systems exist even if there is no evident impossibility; for example, there is no Steiner system of index (2,7,43); it is not known whether there exists one of index (2,13,157), although it is conjectured that there is none. But very elementary knowledge of combinatorics suffices to prove that there is no Steiner system of index (6,9,25), say: the number of blocks could not be an integer.)

The Steiner system of index (5,8,24) has a large number of automorphisms, in other words, manners of permuting the 24 points in such a way that if eight points formed a block before the permutation, the new eight points which take their place after permutation still form a block. As a matter of fact, there are 244823040 automorphisms of the system: these constitute what is known as the Mathieu group M24. This group is five times transitive, meaning that if you take any five of the twenty-four points and place them in any five new places, there is a way (in fact, exactly 48 ways) to complete this choice into an automorphism of the system. Now this property is remarkable in the highest extent: indeed, apart from the full group of permutations on n objects (which is n times transitive) and the so-called “alternating group” of even permutations (which is n-2 times transitive), there are only two (permutation) groups which are 5-transitive: the Mathieu groups M24 (automorphisms of a Steiner system of index (5,8,24), as explained) and M12 (automorphisms of a Steiner system of index (5,6,12)), and neither is 6-transitive or more. And also, the Mathieu groups are among the twenty-six sporadic simple groups; but describing what this means (even by removing the word “sporadic”) would take just a bit too long for me to try it now.

Furthermore, I mention that the Steiner system (5,8,24) can be used to construct the (binary) Golay code, the most remarkable (and “powerful”!) error-correcting code ever, in the following way. Consider the 759 blocks (octads) of the Steiner system (5,8,24) as words of 24 bits, by putting a ‘1’ in a given place if the corresponding point is in the octad, and ‘0’ otherwise (so each of these blocks will have exactly 8 bits to ‘1’ and the others to ‘0’). Now combine these words in every possible way using (bitwise) XOR (eXclusive OR). This gives a total of 4096 words (a vector space of dimension 12 over the finite field with 2 elements), the words of the Golay code, none of which (except the entirely zero word) has fewer than 8 bits with value ‘1’; it is then possible to judiciously choose twelve columns out of the twenty-four in such a way that every combination of ‘0’'s and ‘1’'s in these columns matches one and exactly one of the 4096 words of the code. So we can code any word of 12 bits by a word of 24 bits in the Golay list: this code can correct an arbitrary error on 3 bits out of 24, and detect an arbitrary error on 4 bits. Out of the 4096 words of the Golay code, 759 have 8 bits with value ‘1’, 2576 have 12 bits with value ‘1’, 759 have 16 bits with value ‘1’ (and are the complements of the 759 with weight 8) and the last two are the fully zero and fully set words.

So far I have described some properties of the Steiner system (5,8,24) or the Golay code, but I have not described them explicitely. There is a plethora of ways to construct them, more or less intuitively understandable and more or less pleasant; however, there is at least one way I find truly remarkable: the dodecahedron construction of the Golay code, which works as follows. Take a (regular) dodecahedron and two colors of ink (say, black and red). Using the black ink, write ‘0’'s and ‘1’'s arbitrarily on the dodecahedron, one bit per face. Now using the red ink visit each of the dodecahedron's faces in turn, and compute the parity of all the black bits except those on the five faces immediately adjacent to the one on which the red bit is being written; in other words, each red bit on a given face of the dodecahedron indicates the parity of the black bits for the seven faces of the dodecahedron which are not immediately ajacent to the face in question: the red bit is ‘1’ when there are an odd number of black bits at ‘1’ among the seven faces in question, or ‘0’ when there are an even number of them. Thus, starting from twelve arbitrary black bits we get twelve red bits, to a total of twenty-four bits, two on each face of the dodecahedron: well, this is exactly the Golay code: the 4096 twenty-four bits words obtained by trying all possible combinations of black bits give exactly the 4096 words of the Golay code; and to construct the Steiner system of index (5,8,24), just take those 759 words having eight bits at ‘1’.

One of my bizarre dreams would be to find some way to construct a puzzle similar to Ernő Rubik's famous cube—only it would probably be shaped more like a dodecahedron—that has the Mathieu group M24 as group of transformations. [Update: I wrote a couple of such JavaScript games: see here, here and more importantly here; also see this link which was suggested in the comments.]

↑Entry #0308 [older|newer] / ↑Entrée #0308 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées