# The Fundamental Theorem of the Megaminx

by Coreyanne Rickwalt (class of 1998)

Defining the Megaminx Group

The Megaminx is the shape of a dodecahedron. A dodecahedron is a 12-sided regular platonic solid for which each of the 12 faces is a pentagon. (Platonic solids are the five regular polyhedrons that have "Platonic" groups, or symmetries.) Two faces are neighboring if they share an edge. There are 20 vertices and 30 edges on a dodecahedron. There are a total of 11*12=132 facets on the puzzle. Each face of the solid is parallel to a face on the opposite side. Fix a face of the dodecahedron and consider a plane parallel to that face slicing through the solid and about one-fifth of the way to the opposite face; there are 12 such slices. Two of these slices associated to two neighboring faces will intersect inside the solid, but two such slices associated to two non-neighboring, but non-parallel, faces will not intersect inside the solid; instead, they will intersect outside the solid. This slicing creates a smaller dodecahedron in the center and several other irregular smaller pieces.

For each such slice associated to a given face fi, there is a basic move, still denoted fi , of the Megaminx given by clockwise rotating the slice of the Megaminx by 72 degrees, leaving the rest of the Megaminx unchanged. The following list of these twelve "basic" moves shows that every basic move is a product of 5-cycles. Recall, each move is composed of permutations of the form

(i1 j1 k1 l1 m1)(i2 j2 k2 l2 m2). . .(in jn kn ln mn).
Since any 5-cycle is even, any product of 5-cycles must also be even. Therefore, for each move fi, sgn(fi) = 1 by the definition of the sgn function. Such a move affects 26 facets of the Megaminx and leaves the remaining 106 facets completely fixed.

BASIC MOVES

f1 = (1 3 5 7 9)(2 4 6 8 10)(20 31 42 53 64)(19 30 41 52 63)(18 29 40 51 62)

f2 = (12 14 16 18 20)(13 15 17 19 21)(1 60 73 84 31)(3 62 75 86 23)(2 61 74 85 32)

f3 = (23 25 27 29 31)(24 26 28 30 32)(82 95 42 3 16)(83 96 43 4 17)(84 97 34 5 18)

f4 = (34 36 38 40 42)(35 37 39 41 43)(27 93 106 53 5)(28 94 107 54 6)(29 95 108 45 7)

f5 = (45 47 49 51 53)(46 48 50 52 54)(38 104 117 64 7)(39 105 118 65 8) (40 106 119 56 9)

f6 = (56 58 60 62 64)(57 59 61 63 65)(49 115 75 20 9)(50 116 76 21 10) (51 117 67 12 1)

f7 = (67 69 71 73 75)(68 70 72 74 76)(58 113 126 86 12)(59 114 127 7 13) (60 115 128 78 14)

f8 = (78 80 82 84 86)(79 81 83 85 87)(71 124 97 23 14)(72 125 98 24 15) (73 126 89 25 16)

f9 = (89 91 93 95 97)(90 92 94 96 98)(80 122 108 34 25)(81 123 109 35 26) (82 124 100 36 27)

f10 = (100 102 104 106 108)(101 103 105 107 109)(91 130 119 45 36) (92 131 120 46 37)(93 122 111 47 38)

f11 = (111 113 115 117 119)(112 114 116 118 120)(102 128 67 56 47) (103 129 68 57 48)(104 130 69 58 49)

f12 = (122 124 126 128 130)(123 125 127 129 131)(100 89 78 69 111) (101 90 79 70 112)(102 91 80 71 113)

The solid's 12 faces are labeled f1, f2, ..., f12 in some fixed way. Placing the dodecahedron in 3-space in such a way that one side is on the xy-plane and is centered along the positive z-axis gives the solid an "up" side and a "down" side. Figure 1, Figure 2, Figure 3, and Figure 4, show the labeling of the Megaminx. The "up" face is labeled as f1. Each vertex is uniquely determined by specifying the three faces it has in common. The notation x.y.z is used for the vertex of the solid which lies on the three faces x, y, and z. Each facet of each face can be labeled with an intrinsic label by which the permutations are each most naturally described. The intrinsic label for the center facet on the f1 face is [f1].

Defining a Move

Let M = <f1, f2, ..., f12> be the group generated by the moves of the Megaminx and let H be the "enlarged" group generated by f1, f2, ..., f12, and all the "illegal" moves. (Illegal moves can be done by disassembling and reassembling the solid without removing any stickers from the facets.)

Let V denote the set of vertices of the dodecahedron, and let D:H -> SV denote the homomorphism which associates to each move of the Megaminx the corresponding permutation of the vertices.

Let E denote the set of edges of the dodecahedron, and let F:H -> SE denote the homomorphism which associates to each move of the Megaminx the corresponding permutation of the edges.

For m in M, let D(m) be the permutation of the set of vertices V of the solid, and let F(m) be the corresponding permutation of the set of edges E of the solid. Let Sn denote the symmetric group on n letters, and identify SV (the symmetric group on the vertices) with S20, and SE (the symmetric group on the edges) with S30. Then the following is true:

(a) D: M -> S20 is a homomorphism.

(b) F: M -> S30 is a homomorphism.

If M, S20 are groups with *1 denoting the group operation for M and *2 denoting the group operation for S20, then for all a,b in M,

D(a*1b) = D(a)*2D(b).

This same argument can be applied for F: M -> S30.

In order to mathematically describe the moves of the Megaminx, the corners and the edges must be oriented as in figures 1-4. Beginning with a solved Megaminx, label the facets with an invisible "+" (i.e., mark the spatial position of the facet on the cube with a "+"). In the figures, each facet that receives a "+" is numbered so that the effect of a move m on each particular facet can be observed. These "+" signs are called the "standard reference markings." Each move m of the Megaminx yields a new collection of "+" labels, called the "markings relative to m." A position of the Megaminx is determined by answering the following questions:

(a) How are the edges permuted?

(b) How are the centers permuted?

(c) How are the corners permuted?

(d) Which of the relative edge markings are flipped (relative to the standard reference

markings)?

(e) Which of the relative corner markings are rotated from the standard reference markings and, if so, by how much (120 or 240 degrees clockwise, relative to the standard reference markings)?

Corner Orientations

Let v: H -> C320 (where C320 = C3XC3X . . . XC3 (twenty times), and C3 denotes the cyclic group of order 3, with addition mod 3 as the operation) be the function which associates each move m in H with the corresponding corner orientations. Let m in H and say m moves corner i to corner j. Then vi (m) in C3 is the orientation which the ith vertex gets sent to by m, where the vertices are labelled as shown in figures 1 and 2, and where the orientation is the number of 120 degree clockwise twists required to turn the relative reference "+" (obtained by moving corner i to j using the move m) into the standard reference "+" on corner j. The effect of a move m in H on the corner orientations can also be regarded as a relabeling of the "+" markings. Note that a move m in H has two effects on the corners:

(a) a permutation D(m) in SV of the vertices

(b) a reorientation of the vertices moved in (a).

Now, using m,n in H, we must verify that the "relative" orientation v (mn) - v (m) is the same as the orientation v (n), provided that the effect of m on the vertices is taken into account:

v (n) = D(m)(v (mn) - v (m)), i.e., v (mn) = v (m) + D(m)-1( v (n)).

A sketch of the proof:

The move mn orients the ith corner subcube by vi(mn) and permutes the vertices by D(mn), by definition. On the other hand, mn will first act by m, then n. The move m will reorient the ith corner subcube by vi(m) and send the ith vertex to the D(m)(i)th vertex. Subtract v (m) from v (mn) to study the effect of n on this so that the original orientation is back. (This is called the modified position.) The move n firsts orients the jth corner subcube of the modified solid by vi(n) and then permutes it to vertex D(n)(j). The ith subcube of the modified solid comes from (via m) the

D(m)-1(i)th subcube of the original solid. Therefore the ith corner subcube of the modified cube is, by means of n, reoriented by vD(m)-1(i) (n). Now add vi(m) to get the total effect of mn on the ith vertex of the original:

vi(mn) = vi(m) + vD(m)-1(i) (n) for each 1<i<20.

This implies v (mn) = v (m) + D(m)-1( v (n)).

Edge Orientations

Let w: H -> C230 (where C230 = C2XC2X . . . XC2 (thirty times), and C2 denotes the cyclic group of order 2, with addition mod 2 as the operation) be the function which associates each move m in H with the corresponding edge orientations. Let m in H and say m moves edge i to edge j. Then wi (m) in C2 is the orientation which the ith edge gets sent to by m, where the edges are labelled as shown in figures 3 and 4, and where the orientation is the number of 180 degree flips required to turn the relative reference "+" (obtained by moving edge i to j using the move m) into the standard refernce "+" on edge j. The effect of a move m in H on the edge orientations can also be regarded as a relabeling of the "+" markings. Note that a move m in H has two effects on the edges:

(a) a permutation F(m) in SE of the edges

(b) a reorientation of the edges moved in (a).

Now, as with D, we must verify, using m,n in H, that the "relative" orientation

w (mn) - w (m) is the same as the orientation w (n), provided that the effect of m on the edges is taken into account:

w (n) = F(m)(w (mn) -w (m)), i.e., w (mn) = w (m) + F(m)-1(w (n)).

A sketch of the proof:

The move mn orients the ith edge subcube by wi(mn) and permutes the edges by F(mn), by definition. On the other hand, mn will first act by m, then n. The move m will reorient the ith edge subcube by wi(m) and send the ith edge to the F(m)(i)th edge. Subtract w (m) from w (mn) to study the effect of n on this so that the original orientation is back. The move n firsts orients the jth edge subcube of the modified solid by wi(n) and permutes it to edge F(n)(j). The ith subcube of the modified solid comes from (via m) the F(m)-1(i)th subcube of the original solid. Therefore the ith edge subcube of the modified solid is, by means of n, reoriented by wF(m)-1(i) (n). Now add wi(m) to get the total effect of mn on the ith edge of the original:

wi(mn) = wi(m) + wF(m)-1(i) (n) for each 1<i<30.

This implies w(mn) = w (m) + F(m)-1( w (n)).

The Fundamental Theorem of the Megaminx

Now, using previously defined functions and homomorphisms, each min M can be identified with a 4-tuple (D(m),F(m),v(m),w(m)).

Given a 4-tuple (r,s,v,w) where:

r in S20 is a permutation on the corners,

s in S30 is a permutation on the edges, and

v in C320 , w in C230 ,

there must be conditions on r,s,v, and w to insure that (r,s,v,w) corresponds to a possible position of the Megaminx. (In the section on corner and edge orientations, it was already shown that (r,s,v,w) is at least an impossible position of the Megaminx, since it is simply a combination of permutations on the edges and corners and reorientations of the edges and vertices.)

Now, it is possible to state

The Fundamental Theorem of the Megaminx :

A 4-tuple (r,s,v,w) (r0S20, s0S30, v0C320, w0C230) corresponds to a possible position of the Megaminx if and only if:

(a) sgn(r) = sgn(s) = 1 (equal parity of permutations)

(b) v1 + v2 + . . . + v20 /0 (mod 3) (conservation of total twists)

(c) w1 + w2 + . . . + w30 /0 (mod 2) (conservation of total flips)

Proof:

The "only if" part:

As stated before, each (r,s,v,w)0S20*S30*C320*C230 uniquiely determines a possibly illegal position of the Megaminx.

(a) Let m in M be the element which moves the Megaminx from the solved position to the position associated with this 4-tuple. Then r =D(m) and s = F(m). The element m may be written as a word in the basic moves f1, f2, ..., f12, say m = X1 . . . Xk, where each Xi is equal to one of the f1, f2, ..., f12. If X is any one of these basic moves then sgn (D(X)) = sgn (F(X)). For the megaminx, since every permutation is even, sgn (D(X)) = sgn (F(X)) = 1. (Recall that

sgn : Sn ->{1,-1} is the homomorphism which associates to a permutation either 1, if it is even,

or -1, if it is odd. Also, An = ker(sgn)dSn. and *An* =.5*Sn* ). Since sgn,D, and F are

homomorphisms, it follows that

sgn(r) = sgn (D(m)) = Jsgn (D(Xi )) = Jsgn (F(Xi )) = sgn (F(m )) = sgn(s).

This proves (a).

(b) To show this, each possible face move, and several "words" from these moves were performed, (Here, fin is n clockwise rotations of the fi face, and (0^p) simply denotes p zeroes in a row.) and their sums were shown to be 0 (mod 3) as follows:

 v(X) X f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f1-1 f2-1 f1*f2 f1*f2-1 f1-1*f2 f1-1*f2-1 f2*f1 f2*f1-1 f2-1*f1 f2-1*f1-1 (f1-1*f2-1*f1*f2)3 = [f1,f2]3 m=f3*f-1*f4*f2-1*f5*f3-1*f6*f4-1*f2*f5-1 ; (actual move) f6*f1*m6*f1-1*f6-1 f1*f6*f1-1*f2*f1*f6-1*f1-1*f2-1 f6*f2*f1*f2-1*f1-1*f6-1*f3-1*f1-1*f2-1*f1*f2*f3 (f6-1*f2-1*f3-1*f6*f2*f3)6 f3-2*f62*f2*f1-1*f6*f1*f32*f62*f1*f6-2*f3-2*f1-1*f6-1*f1*f2-1*f6-2*f32*f1-1 f6-1*f2-1*f1*f3-1*f1-1*f3*f2*f6*f3*f2*f1-1*f6*f1*f6-1*f2-1*f3-1

It should also be shown that the conservation of total twists holds for the composition of some of these moves. For instance, when composing the moves (f6-1*f2-1*f3-1*f6*f2*f3)6 and

f1*f6*f1-1*f2*f1*f6-1*f1-1*f2-1, the reorientation of the corners due to the first move is (2,2,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0) while the reorientation due to the second move is

(0,0,0,0,0,2,0,0,0,0,0,0,0,0,1,0,0,0,0,0); the vector sum of these two vectors is: (mod 3)

(2,2,0,0,2,2,0,0,0,0,0,0,0,0,1,0,0,0,0,0). This sum is 9, which is equal to 0 (mod 3).

(i) the conservation of twists condition in (b) is true for (v1, . . . ,v20) if and only if it is true for any permutation (vD(1), . . . ,vD(20)),

(ii) as shown above, if (v1, . . . ,v20) and (v'1, . . . ,v'20) each satisfy the conservation of twists condition in (b) then their sum also satisfies it.

As above, say m = X1 . . . Xk, where each Xi is equal to one of the f1, f2, ..., f12. Choose Xi so that k is as small as possible. This k is the length of m. In the previous listing of some v(X)'s, all words of length k = 1 were checked for conservation of twists. Assume k > 1. Using the formula giving the orientation of the product of two moves in terms of the two orientations of the moves, it can be shown that

v(X1 . . . Xk-1Xk) = D(X1 . . . Xk-1)-1(v(Xk)) + v(X1 . . . Xk-1).

The term D(X1 . . . Xk-1)-1(v(Xk)) satisfies the conservation of twists condition in (b) by (i) above. The term v(X1 . . . Xk) satisfies the conservation of twists condition in (b) by the induction hypothesis. Their sum satisfies the conservation of twists condition in (b) by (ii) above. This proves (b).

(c) To show conservation of total flips, each possible face move, and several "words" from these moves were performed, and their sums were shown to be 0 (mod 2) as follows:

 w(X) X f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f1-1 f2-1 f1*f2 f1*f2-1 f1-1*f2 f1-1*f2-1 f2*f1 f2*f1-1 f2-1*f1 f2-1*f1-1 (f1-1*f2-1*f1*f2)3 = [f1,f2]3 m=f3*f-1*f4*f2-1*f5*f3-1*f6*f4-1*f2*f5-1 ; (actual move) f6*f1*m6*f1-1*f6-1 f1*f6*f1-1*f2*f1*f6-1*f1-1*f2-1 f6*f2*f1*f2-1*f1-1*f6-1*f3-1*f1-1*f2-1*f1*f2*f3 (f6-1*f2-1*f3-1*f6*f2*f3)6 f3-2*f62*f2*f1-1*f6*f1*f32*f62*f1*f6-2*f3-2*f1-1*f6-1*f1*f2-1*f6-2*f32*f1-1 f6-1*f2-1*f1*f3-1*f1-1*f3*f2*f6*f3*f2*f1-1*f6*f1*f6-1*f2-1*f3-1

As before, it should be shown that the conservation of total flips holds for the composition of some of these moves. Composing again the moves (f6-1*f2-1*f3-1*f6*f2*f3)6 and

f1*f6*f1-1*f2*f1*f6-1*f1-1*f2-1, the reorientation of the edges due to the first move is

(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,)

while the reorientation due to the second move is

(0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);

the vector sum of these two vectors is: (mod 2)

(0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0).

This sum is 2, which is equal to 0 (mod 2).

(i) the conservation of flips condition in (c) is true for (w1, . . . ,w30) if and only if it is true for any permutation (wF(1), . . . ,wF(30)),

(ii) as shown above, if (w1, . . . ,w30) and (w'1, . . . ,w'30) each satisfy the conservation of flips condition in (c) then their sum also satisfies it.

As before, in the previous listing of some w(X)'s, all words of length k = 1 were checked for conservation of flips. Assume k > 1. Using the formula giving the orientation of the product of two moves in terms of the two orientations of the moves, it can be shown that

w(X1 . . . Xk-1Xk) = F(X1 . . . Xk-1)-1(w(Xk)) + w(X1 . . . Xk-1).

The terms F(X1 . . . Xk-1)-1(w(Xk)) and w(X1 . . . Xk) satisfy the conservation of flips condition in (c) by (i) and (ii) above as shown before for the similar equation in condition (c). This proves (c).

Proof:

The "if" part:

Assuming (a), (b), and (c) are true, it needs to be shown that there is a corresponding legal position of the Megaminx. This will be a constructive proof, built by using several special cases.

CASE 1

Suppose that, given the 4-tuple (r,s,v,w), both r and s are the identity and no edges have been flipped; i.e. (w1, . . . ,w30) = (0, . . . ,0). The claim is that there exists an m in M such that

D(m) = 1 , F(m) = 1 , w(m) = (0, . . . ,0) , and v(m) = (v1, . . . ,v20).

It can be shown that, for any i,j0 {1, . . . ,20}, i = j, there is an m in M such that D(m) = 1 , F(m) = 1 , w(m) = (0, . . . ,0) , and v(m) = (v1, . . . ,v20) , where vi= 1, vj= 2, and vk= 0, k = i,j.

This calls for a move which permutes neither the corners nor the edges, flips no edges, and twists one corner clockwise (a value for the orientation of 1), and one corner clockwise twice (the same as counterclockwise once, or a value for the orientation of either (-1) or 2). The conservation of total twists is seen to be preserved in that v1+ . . . +v20 = 0 (mod 3). Such a move m is known to exist. For instance, performing the move

m = (f6-1*f2-1*f3-1*f6*f2*f3)6*f6*(f6-1*f1-1*f4-1*f6*f1*f4)12*f6-1

causes a clockwise twist of the (f1/f4/f5 ) corner and a counterclockwise twist of the (f1/f2/f3) corner.

This proves the "if" part of the theorem in the case that r and s are both the identity and that

(w1, . . . ,w30) = (0, . . . ,0).

CASE 2

Suppose that, given the 4-tuple (r,s,v,w), both r and s are the identity and no corners have been twisted; i.e. (v1, . . . ,v20) = (0, . . . ,0). The claim is that there exists an m in M such that

D(m) = 1 , F(m) = 1 , v(m) = (0, . . . ,0) , and w(m) = (w1, . . . ,w30).

It can be shown that, for any i,j0 {1, . . . ,30}, i = j, there is an m in M such that D(m) = 1 , F(m) = 1 , v(m) = (0, . . . ,0) , and w(m) = (w1, . . . ,w30) , where wi= 1, wj= 1, and wk= 0, k = i,j.

This calls for a move which permutes neither the corners nor the edges, twists no corners, and flips only two edges (a value of 1 for each of the orientations for the edges). The conservation of total flips is seen to be preserved in that w1+ . . . +w30 = 0 (mod 2). Such a move m is known to exist.

The move m = f6-1*f2-1*f1*f3-1*f1-1*f3*f2*f6*f3*f2*f1-1*f6*f1*f6-1*f2-1*f3-1 flips only the (f1/f2) and (f1/f3) edges. This proves the "if" part of the theorem in the case that r and s are both the identity and that

(v1, . . . ,v20) = (0, . . . ,0).

CASE 3

Finally, given the 4-tuple (r,s,v,w), assume that both (w1, . . . ,w30) = (0, . . . ,0) and

(v1, . . . ,v20) = (0, . . . ,0); i.e. no edges have been flipped and no corners have been twisted. The claims are that

(a) given any three edge subcubes, there is a move m in M which is a 3-cycle on these edges

(b) given any three corners, there is a move m in M which is a 3-cycle on these corners

and (c) given any three edges and any three corners, there is a move m in M which is a 3-cycle

on these edges and a 3-cycle on these corners.

As stated in the beginning of this paper, let H be the subgroup of Sn generated by all the 5-cycles in Sn, then H = An. In other words, a position of the Megaminx, associated to the 4-tuple (r,s,0,0) can be constructed, provided r0 SV and s0 SE . It follows that the "if" part of the theorem is true in the case that v(m) = (0, . . . ,0) and w(m) = (w1, . . . ,w30) when it can be shown that there is always a move, regardless of the Megaminx's present position, which "fixes" its orientation so that v and w are both zero.

(a) This calls for a move which is a 3-cycle on any three given edges and where sgn (s) = 1. Such a move m is known to exist. The move m = f6*f2*f1*f2-1*f1-1*f6-1*f3-1*f1-1*f2-1*f1*f2*f3 cause a

3-cycle on the (f1/f2), (f2/f3) and (f2/f6) edges.

(b) This calls for a move which is a 3-cycle on any three given corners and where

sgn (r) = 1. Such a move m is known to exist. The move

m = f3*f82*f72*f1*f6*f1-1*f2*f1*f6-1*f1-1*f2-1*(f6*f2*f1*f2-1*f1-1*f6-1*f3-1*f1-1*f2-1*f1*f2*f3)2*f72*f82*f3

is a 3-cycle on the (f1*f2*f6), (f1*f7*f6), and (f2*f6*f7) corners.

(c) This calls for a move which is a 3-cycle on any three given edges and a 3-cycle on three corners; sgn (s) = sgn (r) = 1. Such a move m is known to exist. The move

m = f1*f6*f1-1*f2*f1*f6-1*f1-1*f2-1 is a 3-cycle on the (f1/f2), (f6/f7) and (f2/f6) edges and a 3-cycle on the (f1*f2*f6), (f1*f7*f6), and (f2*f6*f7) corners.

This constructively proves the "if" part of the proof.

The Size of M

Given H, the group of all illegal moves not affecting the centers of the Megaminx group,

H = C320X S20X C230X S30, M is a subgroup of H. Because of the conditions set forth in the Fundamental Theorem (conservation of total twists and flips), an extra condition is imposed on the vectors v and w as follows:

Since v(m) = (0, . . . ,0) there are only seven degrees of freedom, and v1+ . . . +v19 = -v20.

It also follows that since w(m) = (0, . . . ,0), w1+ . . . +w29 = -w30. Therefore, M is actually a subgroup of a larger group M' = C319X S20X C229X S30. Also, by the Fundamental Theorem of the Megaminx, D(M) = A20 and F(M) = A30. The fact that *An * = (.5)*Sn * can be used in determining the size of M.

In particular,

*M* = (.5)2 *S20 **S30 **C229 **C319 * = (.5)220!30! 229219.

This number is approximately 1.006 X 1068.

Coreyanne Rickwalt