The Rubik’s Icosahedron and the Mathieu Group M12

I sometimes pick up a math book that I can’t put back down. A year ago, it was Conway and Sloane’s Sphere Packings, Lattices, and Groups. In this post I’ll describe a neat connection between the sporadic Mathieu group M12 and the icosahedron that they describe.

I’ll use GAP (Groups, Algorithms, and Programming) to show how this works. Feel free to try to build it yourself at home!

Construct the Graph

Let’s start by constructing a graph of the icosahedron. A graph is a set of points (also called vertices) and a set of edges between the points, i.e., pairs of points. For example:

To work with graphs in GAP I like using the Digraphs package:

gap> LoadPackage("Digraphs");
true

To construct our graph, we will take as points and edges the vertices and edges of the icosahedron as labeled in this diagram from Conway and Sloane:

I’ll identify the edges manually (and I’ll relabel the 0 vertex as 12):

gap> edges := [ [ 1, 2 ], [ 1, 7 ], [ 1, 8 ], [ 1, 11 ], [ 1, 12 ], [ 2, 3 ], [ 2, 6 ], [ 2, 7 ], [ 2, 11 ], [ 3, 4 ], [ 3, 6 ], [ 3, 10 ], [ 3, 11 ], [ 4, 5 ], [ 4, 6 ], [ 4, 9 ], [ 4, 10 ], [ 5, 6 ], [ 5, 7 ], [ 5, 8 ], [ 5, 9 ], [ 6, 7 ], [ 7, 8 ], [ 8, 9 ], [ 8, 12 ], [ 9, 10 ], [ 9, 12 ], [ 10, 11 ], [ 10, 12 ], [ 11, 12 ] ];;

Now I’ll use the “Digraphs” package to construct the graph:

gap> D := DigraphSymmetricClosure(DigraphByEdges(edges));
<digraph with 12 vertices, 60 edges>

The “Digraphs” package counts [1, 2] and [2, 1] as distinct edges, but for our purposes they are two labels for the same thing. So we have a symmetric digraph, which is also known as a graph, with 30 edges.

gap> IsSymmetricDigraph(D);
true

Construct the Group Generators

In our figure we see that every vertex has 5 neighbours:

We can confirm this using the “Digraphs” package:

gap> OutDegrees(D);
[ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 ]

We can also identify the five neighbours of each vertex:

gap> Display(OutNeighbours(D));
[ [ 2, 7, 8, 11, 12 ],
[ 1, 3, 6, 7, 11 ],
[ 2, 4, 6, 10, 11 ],
[ 3, 5, 6, 9, 10 ],
[ 4, 6, 7, 8, 9 ],
[ 2, 3, 4, 5, 7 ],
[ 1, 2, 5, 6, 8 ],
[ 1, 5, 7, 9, 12 ],
[ 4, 5, 8, 10, 12 ],
[ 3, 4, 9, 11, 12 ],
[ 1, 2, 3, 10, 12 ],
[ 1, 8, 9, 10, 11 ] ]

What I need now is to put the neighbours of each vertex in a clockwise order. This is because I want to be able to cycle the five neighbours of a vertex one step in the clockwise direction. I can do this by taking another close look at the diagram and defining permutations (which in GAP have the form (1,3,2), for example). Here’s the diagram again for reference:

gap> clockwise := [
( 2,11,12, 8, 7),
( 1, 7, 6, 3,11),
( 2, 6, 4,10,11),
( 3, 6, 5, 9,10),
( 4, 6, 7, 8, 9),
( 2, 7, 5, 4, 3),
( 1, 8, 5, 6, 2),
( 1,12, 9, 5, 7),
( 4, 5, 8,12,10),
( 3, 4, 9,12,11),
( 1, 2, 3,10,12),
( 1,11,10, 9, 8) ];

We can quickly compute the anticlockwise permutation:

gap> anticlockwise := List(clockwise, x -> x^(-1));
[ (2,7,8,12,11), (1,11,3,6,7), (2,11,10,4,6), (3,10,9,5,6), (4,9,8,7,6), (2,3,4,5,7), (1,2,6,5,8), (1,7,5,9,12), (4,10,12,8,5), (3,11,12,9,4), (1,12,10,3,2), (1,8,9,10,11) ]

We now have everything we need to construct the group M12.

A Rubik’s Icosahedron Game

What Conway and Sloane point out is that the group M12 is the group of a certain type of Rubik’s cube game, except with an icosahedron rather than a cube. The rule is that we must always alternate clockwise and anticlockwise turns, and that we must take an equal number of clockwise and anticlockwise turns. For instance, suppose we make a clockwise move at point 4 and and anticlockwise move at point 2:

gap> clockwise[4];
(3,6,5,9,10)
gap> anticlockwise[2];
(1,11,3,6,7)
gap> clockwise[4]*anticlockwise[2];
(1,11,3,7)(5,9,10,6)

The third line here represents a permitted move in this game since we alternate between clockwise and anticlockwise and even number of times.

Let’s write a function to produce a random permitted move, to help clarify what is permitted. Let’s take three steps to build the function. First we make our function choose and return a random list of our vertices of length 2n.

gap> RandomMoveOfLength := function(n)
> local vertex_choices;
> vertex_choices := List([1..2*n], m -> Random([1..12]));
> return vertex_choices;
> end;
function( n ) ... end
gap> RandomMoveOfLength(4);
[ 11, 8, 8, 2, 11, 3, 5, 5 ]

Next we assign a clockwise permutation to the odd positions and anticlockwise permutation to the even choices in this list:

gap> RandomMoveOfLength := function(n)
> local vertex_choices, permutations, x;
> vertex_choices := List([1..2*n], m -> Random([1..12]));
> permutations := [];
> for x in vertex_choices do
> if x mod 2 = 0 then Append(permutations,[clockwise[x]]);
> else Append(permutations, [anticlockwise[x]]); fi;
> od;
> return permutations;
> end;
function( n ) ... end
gap> RandomMoveOfLength(3);
[ (1,12,9,5,7), (1,11,10,9,8), (3,6,5,9,10), (2,7,8,12,11), (1,12,9,5,7), (1,11,10,9,8) ]

Finally, we need to compose this list of permutations into a single permitted permutation:

gap> RandomMoveOfLength := function(n)
> local vertex_choices, permutations, x;
> vertex_choices := List([1..2*n], m -> Random([1..12]));
> permutations := [];
> for x in vertex_choices do
> if x mod 2 = 0 then Append(permutations,[clockwise[x]]);
> else Append(permutations, [anticlockwise[x]]); fi;
> od;
> return Product(permutations);
> end;
function( n ) ... end
gap> RandomMoveOfLength(3);
(1,10,12,4,6,5,9,8)(2,11)

We now have a function RandomMoveOfLength(n) that computes a permitted move in our Rubik’s Icosahedron game. The sporadic Mathieu group M12 is simply the set of all permitted moves in this game.

Constructing M12

Instead of computing random permitted moves, let’s just construct the whole game at once using moves of length 1, namely one clockwise and one anticlockwise permutation in succession. We’ll take every possible ordered pair of vertices:

gap> generators := Set(Arrangements([1..12],2), t -> anticlockwise[t[1]]*clockwise[t[2]]);;
gap> Length(generators);
132

Now we construct the group generated by these moves:

gap> G := Group(generators);
<permutation group with 132 generators>
gap> Size(G);
95040
gap> StructureDescription(G);
"M12"

GAP identifies this group as M12, as advertised. We have constructed the sporadic Mathieu group of permutations on 12 points. Perhaps the most important property of this group is that it is 5-transitive:

gap> Transitivity(G);
5

More on that another time.