From mschoene@math.rwth-aachen.de Sat Jan 14 19:20:51 1995 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 AA03767; Sat, 14 Jan 95 19:20:51 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rTIfA-000MP6C; Sun, 15 Jan 95 01:17 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rTIf9-00025cC; Sun, 15 Jan 95 01:17 WET Message-Id: Date: Sun, 15 Jan 95 01:17 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu, ishius@ishius.com In-Reply-To: der Mouse's message of Tue, 10 Jan 1995 18:14:15 -0500 <199501102314.SAA10516@Collatz.McRCIM.McGill.EDU> Subject: Re: Difficulty of Skewb Der Mouse wrote in his e-mail message of 1995/01/10 The size of the thing is thus somewhere on the order of 500 million configurations. This is why I called it trivial next to the 3x3x3. :-) The group structure in terms of facicles, for what's-his-name to sic GAP on should he care to, derived from the following facicle labeling Of course ``what's-his-name'' couldn't resist ;-). Here are my findings about the SKEWB. The SKEWB Puzzle ================ I took the liberty to renumber the points. This makes the orbits easier recognizable. up +----------+ | 9 10 | | 27 | left | 12 11 | right back +----------+----------+----------+----------+ | 5 6 | 18 17 | 1 2 | 22 21 | | 26 | 29 | 25 | 30 | | 8 7 | 19 20 | 4 3 | 23 24 | +----------+----------+----------+----------+ | 13 14 | | 28 | | 16 15 | +----------+ down I call the 8 possible turns LUB, LUF, RUB, RUF, LDB, LDF, RDB, RDB. Here LUB denotes the turn around the corner common to the L(eft), U(p), and B(ack) faces that turns L to U, U to B, and B back to L. Those turns all have order 3, and I denote the inverses with ^-1 (at least there is no question which metric to use for the SKEWB ;-). With respect to the above numbering, the generators are the following permutations. ## corner other corners centers RUF := ( 1,11,17) ( 2,12,20)( 4,10,18)(22, 6,14) (25,27,29); RUB := ( 2,10,22) ( 1, 9,23)( 3,11,21)(17, 5,15) (25,27,30); LUF := ( 6,12,18) ( 5,11,19)( 7, 9,17)(21, 1,13) (26,27,29); LUB := ( 5, 9,21) ( 6,10,24)( 8,12,22)(18, 2,16) (26,27,30); RDF := ( 4,14,20) ( 1,15,19)( 3,13,17)( 7,11,23) (25,28,29); RDB := ( 3,15,23) ( 2,14,24)( 4,16,22)( 8,10,20) (25,28,30); LDF := ( 7,13,19) ( 6,16,20)( 8,14,18)( 4,12,24) (26,28,29); LDB := ( 8,16,24) ( 5,13,23)( 7,15,21)( 3, 9,19) (26,28,30); With r, u, and f I denote the 3 rotations of the rigid cube, which generate the full automorphism group of the cube. Here r means the rotation around the axis going through the r and l faces, turning the r face in clockwise direction. ## corners opposite centers r := ( 1, 2, 3, 4) ( 6, 5, 8, 7) (27,30,28,29) (11,22,15,20)(12,21,16,19)(10,23,14,17)( 9,24,13,18); u := ( 9,10,11,12) (16,15,14,13) (30,25,29,26) (22, 1,18, 5)(23, 4,19, 8)(21, 2,17, 6)(24, 3,20, 7); f := (17,20,19,18) (21,22,23,24) (25,28,26,27) ( 1,14, 7,12)( 2,15, 8, 9)( 3,16, 5,10)( 4,13, 6,11); Let G be the group generated by the 8 turns; G = < LUB, LUF, RUB, RUF, LDB, LDF, RDB, RDF >. Let C be the group generated by the 3 rotations; C = < r, u, f >. Obviously |C| = 24 and C ~ S_4. Let C' be the derived subgroup of C; C' = . Obviously |C'| = 12 and C' ~ A_4. Then the group CG = < C, G > is the set of all positions a puzzler could observate. There are 24 solved position in CG (solved up to rotations). The group CG has size 2 * 6!/2 * ((3^4*4!/2) * (3^4*4!/2) / 3^2). The group G has size 6!/2 * ((3^4*4!/2) * (3^4*4!/2) / 3^2) (and is a normal subgroup of CG, since |CG/G| = 2). Note that this implies that |C G| = 12. This is not suprising, since G obviously contains all the commutators: Comm(u,f) = LUB * RDF, Comm(r,u) = LUF * RDB, Comm(f,r) = RUB * LDF, Comm(u,f^-1) = RUF * LDB, (those are the rotations of the entire cube around the 4 diagonals), and so G must contain the derived subgroup C' of C. The numbers imply that of the 6! * 3^8 * 8! position one can obtain by taking the puzzle apart and randomly reassembling it, only ~ 0.04% are solvable. Much less than the ~ 8.3% one gets for Rubik's cube. If you choose to puzzle that way, it is certainly a lot more difficult than Rubik's cube ;-). The Structure of the SKEWB Group ================================ G has three orbits on [1..30]. Namely the six face centers F = [25..30], the odd corners C1 = [1,3..23], and the even corners C2 = [2,4..24]. C shall denote the set of all corners, i.e., the union of C1 and C2. The two orbits on the corners are the two tetrahedral sets of corners mentioned by der Mouse. Let G[F] be the operation of G on the faces centers, i.e., G[F] = G/G_F, where G_F is the stabilizer in G of the face centers (the subgroup of those elements of G that fix all face centers). Let G[C] be the operation of G on the corners, i.e., G[C] = G/G_C, where G_C is the stabilizer in G of the corners. As usual with the operation of a group on several orbits, the stabilizers are normal subgroups, and they intersect trivially. On the other hand the size of G_C is 6!/2 and the size of G_F is (3^4*4!/2 * 3^4*4!/2)/3^2. So |G|=|G_C||G_F| and we see that G is the direct product of G_C and G_F. What that means puzzle-wise is that there are no dependencies between the operations on the faces and corners. So take any achivable position x[F] of the faces and any achivable position y[C] of the corners. Then there is a position z that has simultaineously z[F] = x[F] and z[C] = y[C] (in the case of Rubik's cube this is not possible, you can flip a single edge if you ignore what happens at the corners, but you cannot combine this flip of a single edge with a trivial operation on the corners). So we can fully understand the structure of G simply by understanding the structures of G_C and G_F. Of course we can also analyse G[F] and G[C], since the isomorphism theorem tells us that G_C ~ G[F] and G_F ~ G[C]. Obviously G[F] is simply the alternating group A_6. That means we can achieve any even permutation on the center faces. This is not suprising. All 8 generators effect 3-cylces on the center faces. And with 8 3-cycles, one expects the full alternating group to pop up. G[C] has the 2 orbits C1 and C2. Clearly G[C1] and G[C2] are isomorphic. G[C1] is the wreath product of the cyclic group C_3 and the alternating group A_4. That means you can twist each corner independently and achieve any even permutation on the four corners. That you can only achieve even permutations is obvious, since all generators of G[C] permute 3 corners in a 3-cycle. So |G[C1]| = |G[C2]| = 3^4*4!/2. Now G[C] is the subdirect product of G[C1] and G[C1]. That means it is isomorphic to a subgroup of the direct product of G[C1] and G[C2]. It is a subgroup of index 9. That means |G[C]| = |G[C1]| |G[C2]| / 9 = (3^4*4!/2 * 3^4*4!/2) / 3^2. G[C] is the subgroup of G[C1] * G[C2] of those permutations where each (anti)clockwise twist of a corner in C1 is combined with a (anti)clockwise 3-cycle of corners in C2 and each (anti)clockwise twist of a corner in C2 is combined with a (anti)clockwise 3-cycle of corners in C1. This was the most surprising observation for me, so allow me to talk a little bit more about this aspect. The subdirect product G[C] is a product where we ``glue'' together a common factor group of G[C1] and G[C2]. Now this common factor group is the direct product C_3*C_3 of two cyclic groups of size 3. One of them, K say, comes from the normal subgroup C_3^4 of those elements that only twist the corners. The other, L say, comes from the alternating group A_4. Now those factor groups are glued together crosswise, that is, K of G[C1] is glued to L of G[C2], and L of G[C1] is glued to K of G[C2]. In case anybody cares, G has trivial center. This is because the central elements of G[C1] must be combined in G[C] with non-central elements of G[C2] and vice versa. And of course G[F] has trivial center. The Normal Subgroups of the SKEWB Group ======================================= I have also computed the lattice of normal subgroups of the SKEWB group. Since the group is so small, I don't need any complicated argument. G is a little bit too large to simply try 'NormalSubgroups(G);' in GAP. But G[F] and G[C] are both small enough. G[F] is almost trivial (GAP finds in a few seconds that G[F] has no proper normal subgroups). G[C] is a little bit more difficult (but it took me much longer to draw a reasonable picture, then it took GAP to compute the normal subgroups). Anyhow, allow me to first present the normal subgroups lattice of G[C1], which is of course identical to the normal subgroups lattice of G[C2]. G[C1] (972) //|\ / / | \ L1 L2 L3 K[C1] (324) \ \ | / \ \\|/ \ (108) G[C1]' \ \ V[C1] (81) \ / \ \ / \ (27) W[C1] \ \ \ \ \ \ \ \ Z[C1] (3) \ / \ / <1> Here V[C1] is elementary abelian subgroup (the vector space) of those 3^4 elements of G[C1] that only twist the corners, but do not permute them. G[C1]/V[C1] is the A_4 permuting the corners. K[C1]/V[C1] is the subgroup of G[C1]/V[C1] of the double transpositions, i.e, the elements that permute the corners in two pairs of two corners each. G[C1]' is the derived subgroup of G[C1], i.e., G[C1]/G[C1]' is the largest abelian factor group of G[C1] (b.t.w. note that the fact that G is a direct product implies that G[C1]' = G'[C1]). L1, L2, and L3 are three more normal subgroups of index 3, which I don't know how to describe easily. Z[C1] is the center of G[C1]. And now the lattice of normal subgroups of G[C]. G[C] (104976) //|\ / / | \ L1 L2 L3 K[C] (34992) \ \ | / \_ \\|/ | \ (11664) G[C]' \ \ \_ V1 V2 (8748) | \ / X \ \ X / \ \ (2916) W1 W2 \ \ / X \ \ \ |_/ \ \ \ \ / \ \ \ \ (729) W[C] \ \ \ \ \ \ \ \ \ \ \ \ Z1 Z2 (324) \ \ \ / / \_ \ X / | \ S1 S2 (108) \ \ / / \ \ / / \ X / T1 T2 (27) / / / / / / |_/ / / / / <1> S1 and S2 are the stabilizers G[C]_C1 and G[C]_C2, so the normal subgroup lattices above S1 and S2 are identical to the normal subgroup lattices of G[C1] (= G[C2]). Those two lattices over S1 and S2 share the normal subgroups over G[C]' (this is where G[C1] and G[C2] are glued together). W[C] (the intersection of W1 and W2) is the elementary abelian subgroups (the vectorspace) of those elements of G[C] that only twist the 8 corners, but do not permute them. G[C]/W[C] is the A_4*A_4 permuting the two sets of corners. G[C]' is the derived subgroup of G[C], i.e., G[C]/G[C]' is the largest abelian subgroup of G[C]. Now we get the normal subgroup lattice of G by taking the above picture twice, once below G_F (because G_F ~ G[C]), and once above G_C (because G/G_C ~ G[C]). G_______ //|\ \ LLL K \ D \ \ \ VV \ WW \\ G_F W \\ \\ //|\ \ \\ ZZ LLL K \\ SS D \ TT \ VV // WW \\ / W \\ \\ G_C \ \\ ZZ \ \\ SS \ TT \ // \_______ / <1> God's algorithm for the SKEWB ============================= The next was to compute God's algorithm for the SKEWB. G is not very large, but is is easier to use a smaller model. Let H be the subgroup generated by the 4 turns LUB, LUF, RUB, and RUF. Repeated application of the rules -> , LDB -> Comm(u,f^-1) * RUF^-1, LDF -> Comm(f,r) * RUB^-1, RDB -> Comm(r,u) * LUF^-1, RDF -> Comm(u,f) * LUB^-1, allows us to translate any process in CG to one that starts with a single rotation and continues with a process in H, i.e., it starts with a rotation and continues with a process that involves only LUB, LUF, RUB, and RUF and their inverses. Note however, that H is *not* a supplement for C in CG. This is because the intersection of H and C is not trivial. Namely H contains d^2, i.e., the rotation by 180 degree around the axis through the down face (which is fixed by H) and the up face. That means that H contains 2 solved positions, and each position of H contains to 12 positions of CG. In other word H has index 12 in CG. Here is the table for H. The first column contains the lenght. The second column contains the number of positions of that length in H. The third column contains the number of positions of that length that are local maxima, i.e., the number of positions such that for no generator the position * is longer. The fourth column contains the number of positions such that for one generator the position * is longer. And so on. So the eleventh column contains the number of positions such that for all eight generators * is longer (this happens of course only for the 2 solutions). length #pos #loc max 0 2 0 0 0 0 0 0 0 0 2 1 16 0 0 0 0 0 0 16 0 0 2 96 0 0 0 0 0 0 96 0 0 3 576 0 0 0 0 0 0 576 0 0 4 3456 0 0 0 0 0 240 3216 0 0 5 20496 0 0 0 48 729 2766 16953 0 0 6 118608 48 161 1231 4228 14779 32993 65168 0 0 7 630396 8266 33358 76349 121363 153892 137755 99413 0 0 8 2450966 1025322 621763 381098 234661 128570 47822 11730 0 0 9 2911712 2768641 126056 15344 1422 199 50 0 0 0 10 162056 161876 180 0 0 0 0 0 0 0 11 180 180 0 0 0 0 0 0 0 0 To get the table for CG, simply multiply each number by 12. This was computed with a small C program in 200 seconds on a Pentium 90 system using approx 16 MByte of memory. Since this is my first computation of this kind, I would be glad if somebody could independently verify this table. The SuperSKEWB ============== If we do not ignore the orientation of the face centers we obtain the SuperSKEWB. This could for example be done by drawing a line over one corner and the center for each face of the cube. Mathematically I modelled the SuperSKEWB by representing each face center with a set of four numbers (instead of a single number). That pushed the total number of moved points from 30 to 48 (still pretty small). The size of the SuperSKEWB group SG is a factor 32 greater than G's size, i.e., it is (2^5*6!/2) * ((3^4*4!/2) * (3^4*4!/2) / 3^2). The size of CSG (closure of C and SG) is also a factor 32 greater than CG's size, i.e., it is 2*(2^5*6!/2) * ((3^4*4!/2) * (3^4*4!/2) / 3^2). It is easy to see that you cannot turn a face center by 90 degrees in SG. Namely the corner pieces fall into two tetrahedral sets, which are not interchanged by SG. Now a given edge of a face center will always be adjacent to corners in one of those two sets of corner pieces. Simply by looking at the generators of SG, we see that each element of SG must turn an even number of face centers. So we can turn at most five of the six face centers independently; after that the orientation of the sixth face center is determined. So there are at most 2^5 different orientations possible. Since |SG| = 2^5 |G|, we see that all 2^5 orientations are indeed achievable. The structure of SG is of course very similar to the structure of G. SG[C] is identical to G[C]. Remember that G[F] was A_6. SG[F] is a subgroup of index 2 in the wreath product 2 A_6. The index 2 is because one cannot turn a single face. Note that SG has a nontrivial center, namely the element that turns all face centers at once. Thus the lattice of normal subgroups of SG is very similar to the lattice of G. The only difference is that SG_C (and of course also SG/SG_F) has two nontrivial normal subgroups with sizes 32 and 2 (resp. with sizes 32*104976 and 2*104976). I cannot compute God's algorithm for the SuperSKEWB. Would I use the same approach that I used for the SKEWB, I would need 32 times as much memory, i.e., ~ 1/2 GByte. Does anybody have an idea how to tackle the SuperSKEWB (provided anybody cares, I certainly don't)? Have a nice day. Martin. PS: No, I don't own a SKEWB. Yes, I intent to order one. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany