From mschoene@math.rwth-aachen.de Wed Dec 7 18:55:27 1994 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AB15276; Wed, 7 Dec 94 18:55:27 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rFSIx-000MPUC; Wed, 7 Dec 94 20:45 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rFSIx-0000PsC; Wed, 7 Dec 94 20:45 PST Message-Id: Date: Wed, 7 Dec 94 20:45 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Subject: Models for the Cube I wrote in my e-mail message of 1994/11/08 The way I view this is as follows. The entire cube group C is a permutation group group on 6*9 points, generated by the six face turns U, D, L, R, F, B; the three middle slice turns M_U, M_L, M_F; and the reflection S. This group has a subgroup M of symmetries of the cube (of order 48), generated by U M_U D', L M_L R', F M_F B', and S. Another subgroup is G, generated by the six face turns, which has index 48 in G. G is a normal divisor of C, G is the semidirect product of M and G. The same is true for GE and GC. Jerry Bryan writes in his e-mail message of 1994/11/08 I have discussed a similar view of things recently, except that I was not brave enough to include a reflection in the generators. C is normally used to denote the set of twenty-four rotations of the cube (a sub-group of M), so let's call your "entire cube group" big_G instead. My version of big_G was generated by Q plus the slice moves (like yours without the reflection), or alternatively by Q plus C. Your version of big_G is hence the same as the one I discussed except that you added a reflection. C (the rotations C, that is) is a sub-group of both versions of big_G. M is a sub-group of your version of big_G, but not of mine. Your big_G has the obvious advantage of including M as a sub-group. Mine has the advantage (?) of being physically realizable on a real cube. That is, for X in your big_G, rX or Xr (r is a reflection) is also in your big_G. For X in my big_G, rX or Xr is not in big_G, and correspondingly a single reflection is not physically realizable on a real cube. Of course, r'Xr is in big_G in either case, r being in M. Also, cX and Xc are in either version of big_G for all c in C. OK, I guess I have to be a little bit more precise and also to adapt my terminology to common usage. First a picture. MG (48*|G|) /| / CG (24*|G|) / /| / / | / / | / / G (|G| = 8!*3^7 * 12!*2^11 / 2) / / | / / | / / | / / | / / | / / / / / / / / / (48) M / / |/ / (24) C / \ / \ / \ / <1> The maximal cube group *MG* is a permutation group on 6*9 points. It is generated by the six face turns < U, D, L, R, F, B >, the three rotations of the entire cube < u, l, f >, and the reflection < x >. The complete cube group *CG*, generated by < U, D, L, R, F, B > and < u, l, f >, is a subgroup of MG of index 2. The cube group *G*, generated by < U, D, L, R, F, B >, is a subgroup of index 24 in CG. G can be viewed as a permutation group on 48 points, since it fixes the 6 center cubies. The group *M* of symmetries of the entire cube, generated by < u, l, f > and < x >, is a subgroup of MG of size 48. The group *C* of rotations of the entire cube, generated by < u, l, f >, is a subgroup of CG of size 24. (I would have preferred S instead of M and R instead of C, but M and C are too widely used to change that notation. Of course MG is not called MG because it is the maximal cube group, but as a reminder that it is the product of M and G. Likewise for CG.) Jerry continues I tend to think that Singmaster's standard G= is not what people think of when they hold a real cube in their hand. Rather, they tend to think of big_G/C. That is, the cosets of C in big_G are common sensically considered to be equivalent because rotating a real cube in space is "doing nothing". Also, for my version of big_G we have |big_G/C| = |G|. True, what people really see is the complete cube group CG (what you call big_C). That is, patterns corresponding to two different elements of CG are distinct. Now if two patterns can be made equal by rotations of the entire cube, they ``look alike'' and most people feel that they are equivalent since rotations ``cost nothing''. Especially they feel that any pattern corresponding to an element in C is solved. Mathematically we describe this equivalence by saying that all 24 elements in each coset of C are equivalent. Unfortunately C is *not* a normal subgroup of CG, and therefore CG/C is *not* a group. If we want to apply group theory, we need a better model. I argue that G is indeed a good model for the 3x3x3 cube. First note that for each coset of C in CG, there is exactly one element of G in this coset. This follows since C and G together generate CG and have trivial intersection. We call this element the representative in G of the coset. Thus G is a set of representatives for the cosets of C in CG. In group theory terminology G is a *supplement* for C (if C was a normal subgroup, then G would be called a complement of C). An immediate consequence is that |G| = |CG| / |C|. Next note that, if we assume that rotations ``cost nothing'' and middle slice turns cost (at least) twice as much as face turns, then any two elements in a coset of C have the same *cost*, i.e., distance from the solved cube, and this is equal to the cost of the representative in G. This is a simple consequence of the fact that we can transform each process p_1 p_2 ... p_l, where each p_i is either a face turn or a rotation of the entire cube, into one which has a single rotation of the entire cube first and then only face turns afterwards. This can be done using the rule => , which obviously doesn't change the cost of the process (remember rotations cost nothing). Finally note that G's structure as a group is in a certain sense CG without C. Namely G is a normal subgroup of CG, and the factor group CG/G is isomorphic to C. Ideally we would like to have G be isomorphic to CG modulo C, but this is not well defined, as C is not a normal subgroup. Put another way, CG is the semidirekt product of G with C. Unfortunately the existence of this model is particular to the 3x3x3 cube. It does not work as well for other cubes. First take the 2x2x2 cube group CG_2 (I use a _2 to distinguish the 2x2x2 subgroups from their 3x3x3 counterparts). Again we have a subgroup C_2, generated by the rotations, of size 24. But the subgroup G_2, generated by the six face turns, is in fact equal to CG_2. In particular it is not a supplement to C_2. But we can make a similar construction. Namely in the case of the 3x3x3 we can view CG as generated by the six face turns and the three middle slice turns < M_U, M_D, M_F > (instead of the six face turns and the three rotations < u, d, f >). And our supplement G was the subgroup of CG generated by 6 of those 9 generators, were the 3 removed ones are pairwise perpendicular. In the case of the 2x2x2 cube we can take the subgroup H_2 that is generated by three turns < U, L, F >. Using the transformations => and D => u' U, R => l' L, B => f' F, we can again transform any process into one which has a single rotation first and then only < U, L, F > turns afterwards, without changing the cost of the process (again rotations cost nothing). Thus H_2, of size 7!*3^6, is a good model to use when one is looking for God's algorithm for the 2x2x2 cube. Nothing of this is really new, I have just casted it into a different language. For example see 'http://www.math.rwth-aachen.de:8000/~mschoene/Cube-Lovers/ Jerry_Bryan__God's_Algorithm_for_the_2x2x2_Pocket_Cube.html'. But H_2 is *not* normal, and is not CG_2 without C_2 (in the sense in which G was CG without C). For example CG_2 has a factor group isomorphic to S8, but there is no such factor in H_2. Things get worse when we look at the nxnxn cube groups CG_n. We can find again find a supplement H_n for C_n, if we leave out three pairwise perpendicular slice turns. If n is odd and if we leave out the three middle slice turns, then H_n is again a normal subgroup (and in the same sense as above, it is again CG_n without C_n). On the other hand if n is even then H_n is never a normal subgroup. Moreover if 3 < n, then the transformation rules tell us to replace one of the removed slice turns by a rotation and the product of the n-1 parallel slice turns. Thus the transformation would only respect the cost, if we assume that the removed three slice turns have cost n-1. While this is arguably true for n = 3, where most people feel that the middle slice turns have cost 2, I don't think anybody feels that for the 4x4x4 cube nine of the slice turns have cost 1 and 3 have cost 3. And now for something completely different (no, not really ;-). I have argued that G is a good model for the 3x3x3 cube assuming that rotations of the entire cube cost nothing, and that middle slice turns have cost 2 (or higher). In a certain sense, we got rid of C. That doesn't mean we can't use C anymore. In fact, C is still very useful. Namely let c be any element of C, and g be any element of G. Then c' g c is another element of G, because G is a normal subgroup. Moreover the cost of c' g c is the same as the cost of g. This is trivial because each process effecting g can be turned into a process effecting c' g c, by replacing each generator x in this process by c' x c. But C is not the largest such group. The largest such group is M, i.e., the full group of symmetries of the entire cube. This is the reason why I prefer to view G as a subgroup of MG, which is the semidirekt product of M and G, even though I realize that MG is not physically realizable. Have a nice day. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany