From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Generating Rubik's Cube Date: 29 Nov 1995 20:58:21 GMT Just a couple of high-end leads for those who want to pursue more of the math behind the cube. First of all we have: In article <9511291210.Hoey@aic.nrl.navy.mil>, Dan Hoey wrote: >About the minimal presentation of the cube group on the usual generators, >frb6006@cs.rit.edu (Frank R Bernhart) writes: > >> The answers may be in SINGMASTER, et.al. >> "Handbook of Cubic Math" or BANDEMEISTER (sp?) "Beyond R. Cube" > >I recall Singmaster wanted to know if anyone found a reasonably-sized >presentation; I don't know if any have been found in the intervening >fifteen years. The best I know of is a few thousand relations, some >of them several thousand letters long. Whew! I didn't know that. It is true that the question has a clearer statement than "what's the shortest way you've found to present the group". For the record it goes like this: You have a group Rubik generated by the 6 90-degree rotations g_i. Let F be the free group on 6 generators x_i and f: F --> Rubik the obvious homomorphism. There is a big kernel N of f. (It is actually a free group: subgroups of free groups are free). You wish to find the smallest (free) subgroup K of N such that N is the normal closure of K in F. (When you give a presentation of Rubik in the form Rubik = , you are implicitly describing K as the subgroup of F generated by the corresponding words in the x_i.) To give this process at least a chance of success, you abelianize it: Let N_ab be the free abelian group N/[N,N], so that there is a natural map from N into N_ab. Since N is normal in F and [N,N] is characteristic in N, the action of F by conjugation on N lifts to an action of F on N_ab; even better, the subgroup N < F acts trivially on N_ab, so that F/N (i.e., the Rubik group itself) acts on N_ab. We think of N_ab as a Rubik-module (or better, as a Z[Rubik]-module). The subgroup K < N also maps to a subgroup K[N,N]/[N,N] of N_ab; significantly, N is the F-closure of K iff N=[K,F]K so that N_ab is generated as a Z[Rubik]-module by F. Thus, the question of what constitutes a minimal set of relations is the same as asking for the number of generators needed for a certain Rubik-module. (Of course, while you're at it, you might as well ask for a whole presentation or resolution of the Rubik-module. Inevitably, you will be led to questions of group cohomology.) =========================================================== Separately, I should point out that these computations can be automated to an extent. I enclose a portion of the readme file from the (free!) GAP computer algebra system, which Martin Sch"onert was perhaps too modest to post. dave Analyzing Rubik's Cube with GAP =============================== Ideal Toy Company stated on the package of the original Rubik cube that there were more than three billion possible states the cube could attain. It's analogous to Mac Donald's proudly announcing that they've sold more than 120 hamburgers. (J. A. Paulos, Innumeracy) To show you what GAP can do a short example is probably best. If you are not interested in this example skip to the section "An Overview of GAP". For the example we consider the group of transformations of Rubik's magic cube. If we number the faces of this cube as follows +--------------+ | 1 2 3 | | 4 top 5 | | 6 7 8 | +--------------+--------------+--------------+--------------+ | 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 | | 12 left 13 | 20 front 21 | 28 right 29 | 36 rear 37 | | 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 | +--------------+--------------+--------------+--------------+ | 41 42 43 | | 44 bottom 45 | | 46 47 48 | +--------------+ then the group is generated by the following generators, corresponding to the six faces of the cube (the two semicolons tell GAP not to print the result, which is identical to the input here). gap> cube := Group( > ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19), > ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35), > (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11), > (25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24), > (33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27), > (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40) > );; First we want to know the size of this group. gap> Size( cube ); 43252003274489856000 Since this is a little bit unhandy, let us factorize this number. gap> Collected( Factors( last ) ); [ [ 2, 27 ], [ 3, 14 ], [ 5, 3 ], [ 7, 2 ], [ 11, 1 ] ] (The result tells us that the size is 2^27 3^14 5^3 7^2 11.) Next let us investigate the operation of the group on the 48 points. gap> orbits := Orbits( cube, [1..48] ); [ [ 1, 3, 17, 14, 8, 38, 9, 41, 19, 48, 22, 6, 30, 33, 43, 11, 46, 40, 24, 27, 25, 35, 16, 32 ], [ 2, 5, 12, 7, 36, 10, 47, 4, 28, 45, 34, 13, 29, 44, 20, 42, 26, 21, 37, 15, 31, 18, 23, 39 ] ] The first orbit contains the points at the corners, the second those at the edges; clearly the group cannot move a point at a corner onto a point at an edge. So to investigate the cube group we first investigate the operation on the corner points. Note that the constructed group that describes this operation will operate on the set [1..24], not on the original set [1,3,17,14,8,38,9,41,19,48,22,6,30,33,43,11,46,40,24,27,25,35,16,32]. gap> cube1 := Operation( cube, orbits[1] ); Group( ( 1, 2, 5,12)( 3, 7,14,21)( 9,16,22,20), ( 1, 3, 8,18)( 4, 7,16,23)(11,17,22,12), ( 3, 9,19,11)( 5,13, 8,16)(12,21,15,23), ( 2, 6,15, 9)( 5,14,10,19)(13,21,20,24), ( 1, 4,10,20)( 2, 7,17,24)( 6,14,22,18), ( 4,11,13, 6)( 8,15,10,17)(18,23,19,24) ) gap> Size( cube1 ); 88179840 Now this group obviously operates transitively, but let us test whether it is also primitive. gap> corners := Blocks( cube1, [1..24] ); [ [ 1, 7, 22 ], [ 2, 14, 20 ], [ 3, 12, 16 ], [ 4, 17, 18 ], [ 5, 9, 21 ], [ 6, 10, 24 ], [ 8, 11, 23 ], [ 13, 15, 19 ] ] Those eight blocks correspond to the eight corners of the cube; on the one hand the group permutes those and on the other hand it permutes the three points at each corner cyclically. So the obvious thing to do is to investigate the operation of the group on the eight corners. gap> cube1b := Operation( cube1, corners, OnSets ); Group( (1,2,5,3), (1,3,7,4), (3,5,8,7), (2,6,8,5), (1,4,6,2), (4,7,8,6) ) gap> Size( cube1b ); 40320 Now a permutation group of degree 8 that has order 40320 must be the full symmetric group S(8) on eight points. The next thing then is to investigate the kernel of this operation on blocks, i.e., the subgroup of 'cube1' of those elements that fix the blocks setwise. gap> blockhom1 := OperationHomomorphism( cube1, cube1b );; gap> Factors( Size( Kernel( blockhom1 ) ) ); [ 3, 3, 3, 3, 3, 3, 3 ] gap> IsElementaryAbelian( Kernel( blockhom1 ) ); true We can show that the product of this elementary abelian group 3^7 with the S(8) is semidirect by finding a complement, i.e., a subgroup that has trivial intersection with the kernel and that generates 'cube1' together with the kernel. gap> cmpl1 := Stabilizer( cube1, [1,2,3,4,5,6,8,13], OnSets );; gap> Size( cmpl1 ); 40320 gap> Size( Intersection( cmpl1, Kernel( blockhom1 ) ) ); 1 gap> Closure( cmpl1, Kernel( blockhom1 ) ) = cube1; true There is even a more elegant way to show that 'cmpl1' is a complement. gap> IsIsomorphism( OperationHomomorphism( cmpl1, cube1b ) ); true Of course, theoretically it is clear that 'cmpl1' must indeed be a complement. In fact we know that 'cube1' is a subgroup of index 3 in the wreath product of a cyclic 3 with S(8). This missing index 3 tells us that we do not have total freedom in turning the corners. The following tests show that whenever we turn one corner clockwise we must turn another corner counterclockwise. gap> (1,7,22) in cube1; false gap> (1,7,22)(2,20,14) in cube1; true More or less the same things happen when we consider the operation of the cube group on the edges. gap> cube2 := Operation( cube, orbits[2] );; gap> Size( cube2 ); 980995276800 gap> edges := Blocks( cube2, [1..24] ); [ [ 1, 11 ], [ 2, 17 ], [ 3, 19 ], [ 4, 22 ], [ 5, 13 ], [ 6, 8 ], [ 7, 24 ], [ 9, 18 ], [ 10, 21 ], [ 12, 15 ], [ 14, 20 ], [ 16, 23 ] ] gap> cube2b := Operation( cube2, edges, OnSets );; gap> Size( cube2b ); 479001600 gap> blockhom2 := OperationHomomorphism( cube2, cube2b );; gap> Factors( Size( Kernel( blockhom2 ) ) ); [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ] gap> IsElementaryAbelian( Kernel( blockhom2 ) ); true gap> cmpl2 := Stabilizer(cube2,[1,2,3,4,5,6,7,9,10,12,14,16],OnSets);; gap> IsIsomorphism( OperationHomomorphism( cmpl2, cube2b ) ); true This time we get a semidirect product of a 2^11 with an S(12), namely a subgroup of index 2 of the wreath product of a cyclic 2 with S(12). Here the missing index 2 tells us again that we do not have total freedom in turning the edges. The following tests show that whenever we flip one edge we must also flip another edge. gap> (1,11) in cube2; false gap> (1,11)(2,17) in cube2; true Since 'cube1' and 'cube2' are the groups describing the actions on the two orbits of 'cube', it is clear that 'cube' is a subdirect product of those groups, i.e., a subgroup of the direct product. Comparing the sizes of 'cube1', 'cube2', and 'cube' we see that 'cube' must be a subgroup of index 2 in the direct product of those two groups. gap> Size( cube ); 43252003274489856000 gap> Size( cube1 ) * Size( cube2 ); 86504006548979712000 This final missing index 2 tells us that we cannot operate on corners and edges totally independently. The following tests show that whenever we exchange a pair of corners we must also exchange a pair of edges (and vice versa). gap> (17,19)(11,8)(6,25) in cube; false gap> (7,28)(18,21) in cube; false gap> (17,19)(11,8)(6,25)(7,28)(18,21) in cube; true Finally let us compute the centre of the cube group, i.e., the subgroup of those operations that can be performed either before or after any other operation with the same result. gap> Centre( cube ); Subgroup( cube, [ ( 2,34)( 4,10)( 5,26)( 7,18)(12,37)(13,20) (15,44)(21,28)(23,42)(29,36)(31,45)(39,47) ] ) We see that the centre contains one nontrivial element, namely the operation that flips all 12 edges simultaneously. This concludes our example. Of course, GAP can do much more, and the next section gives an overview of its capabilities, but demonstrating them all would take too much room. ============================================================================== From: Paul Arendt Date: Fri, 1 Dec 1995 15:38:49 -0700 To: rusin@math.niu.edu Subject: Rubik Hi there, Thanks for your mail about my cube questions. Another respondent has written saying that 5 of the 1/4 turn generators are sufficient; explicit sequences were found by many. There was a post by someone that 2 generators actually suffice; I'm assuming that the generators are a longer sequence of turns whose commutator generates more generators, or something like that. A question: you mentioned the group generated by the 2 simple relations I gave as being isomorphic to something called a Coxeter group, and gave some diagram (kinda Dynkin-looking) which classified it. I haven't heard of these; is there a reference you could give me? (Sorry; that should be "a subgroup of the group generated by the 2 relations I gave".) Thanks also for the GAP documentation; I hadn't heard of such a package! The examples it gave on the cube were truly impressive. Many thanks, - Paul Arendt (parendt@aoc.nrao.edu) ============================================================================== Date: Fri, 1 Dec 95 17:12:08 CST From: rusin (Dave Rusin) To: parendt@mailhost.nmt.edu Subject: Re: Rubik Yes, the Coxeter groups are related to Dynkin diagrams. The DD's are supposed to illustrate roots systems of Lie algebras or Lie groups; the group of automorphisms of these algebras is the Weyl group, which is an example of the Coxeter groups. In general though you can use this shorthand for a wider family of groups. Each dot corrresponds to a generator of order 2. Each edge gives a relation (gh)^n=1 [n=label on the edge, 3 if unlabelled, and (gh)^2=1, i.e. g and h commute, if there is no edge] There are to be no other generators or relations implied. I suppose a reference is Coxeter and Moser, "Generators and RElations for Discrete Groups", but I don't remember exactly what's in there. Bourbaki has a volume on Lie Groups and Algebras. There's a book by Hller on Geometry of Coxeter Groups. (That's Hiller, sorry). One gets into geometric questions by asking if these abstract groups act on spaces with the generators being reflections; constraints on the labels make the groups act on a sphere, a plane, or hyperbolic space. It's quite fun, actually. dave ============================================================================== From: Paul Arendt Date: Fri, 1 Dec 1995 16:21:08 -0700 To: rusin@math.niu.edu Subject: Re: Rubik Thanks for the references. The diagram had me confused; I've only seen these for continuous groups before, never infinite discrete groups. I've seen the Bourbaki Lie group book before; it would take me quite some time to work all the way through! - Paul Arendt ============================================================================== Date: Sun, 17 Dec 95 02:41:02 EST From: hoey@AIC.NRL.Navy.Mil To: Cube-Lovers@life.ai.mit.edu, rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Presenting Rubik's Cube A few weeks ago I mentioned the old problem of finding a presentation of the Rubik's cube group in terms of the usual generators. This was posed by Singmaster over 15 years ago, and as far as I know has never been addressed. I've made some progress. I work using a specially selected set of generators, rather than the usual generators given for the cube. First I give presentations separately for the permutation groups of the corners and edges, and the orientation groups of the corners and edges. Then I join the permutation groups with their respective orientation groups to form the wreath groups, which describe the possible motions of the respective piece types. I join the two wreath groups in such a way that the permutation parity of the two is equal. Finally, I discuss a method of converting to the usual generators. In Coxeter and Moser's _Generators and Relations for Discrete Groups, 2nd ed_ I found Coxeter's presentation 6.271 for the symmetric group on {1,2,...,n}, n even. With a modest change of variables, his presentation is on generators v=(1 2) and s=(2 3 ... n) ((1)) and relators v^2, v s^(n-2) (v s^-1)^(n-1), (s^-1 v s v)^3, and ((s^-1 v)^i (s v)^i)^2, i=2,...,n/2-1. ((2)) Here n will be 8 or 12 to present the group of the permutations of corners or edges, respectively. The orientation group of the corners (or edges) is the direct product of n-1 cyclic groups, which can be presented with generators r_0=(1)+(2)- r_1=(1)+(3)-, ..., r_(n-2)=(1)+(n)-, ((3)) where (k)+ indicates a reorientation of piece k in place and (k)- indicates the inverse reorientation. The relators here are r_i^d, (d=3 (corners) or 2 (edges)), and r_i r_j r_i^-1 r_j^-1, 0 <= i < j <= n-2. ((4)) I generate the wreath group with the union of the generators ((1,3)). The added relators v r_0 v r_0 v r_i v r_0 r_i i=1,...,n-2, s^-1 r_i s^i r_(i+1)^-1 i=0,...,n-3, and s^-1 r_(n-2) s^i r_0^-1 ((5)) will permit moving the r_i to the end of a word, after which the previous relators ((2)) and ((4)) may be used to manipulate the parts separately, just as a Rubik's cube solvers can perform any needed permutations before reorientations. In the wreath group, the r_i are conjugate to each other. The third line of ((5)) may be used to define r_k = s^-k r_0 s^k, so I eliminate r_1,...,r_(n-1) and write r_0 as r. The last line of ((5)) is then a consequence of s^(n-1)=e, which is implied by ((2)), according to Coxeter. The conjugacy also lets me rewrite ((4)) as r^d, (d=3 (corners) or 2 (edges)), and s^-j r s^j r' s^-j r' s^j r, j=1,...,(n-2)/2. ((6)) As the discussion turns to working with corners and edges together, I write cs,cr and es,er for the respective generators. I use a single generator v that acts on both corners and edges, to ensure that the corner permutation has the same parity as the edge permutation. Since any identity in {v,cs,cr} must use an even number of v's, the identity will hold in the when the v operates on edges as well; similarly for {v,es,er} operating on the corners. To present the whole cube group, I use all five generators, relators ((2,5,6)) for both corners and edges, and new relators es cs es' cs', er cs er cs', es cr es' cr', er cr er cr' to make the two kinds of generators commute, so they may be separated in a word. According to GAP, the complete set of relators is er^2, v^2, cr^3, er cr er cr^-1, er cs er cs^-1, es cr es^-1 cr^-1, es cs es^-1 cs^-1, (v cr)^2, (v er)^2, cr cs cr cs^-1 cr^-1 cs cr^-1 cs^-1, (er es er es^-1)^2, cs cr^-1 cs^-1 v cs cr cs^-1 v cr, cs^-1 cr^-1 cs v cs^-1 cr cs v cr, (es er es^-1 v)^2 er, (es^-1 er es v)^2 er, cr cs^2 cr cs^-2 cr^-1 cs^2 cr^-1 cs^-2, (cs^-1 v cs v)^3, (er es^2 er es^-2)^2, (es^-1 v es v)^3, cr^-1 cs^-2 v cs^2 cr cs^-2 v cr cs^2, cr^-1 cs^2 v cs^-2 cr cs^2 v cr cs^-2, er es^-2 v es^2 er es^-2 v er es^2, er es^2 v es^-2 er es^2 v er es^-2, cr cs^3 cr cs^-3 cr^-1 cs^3 cr^-1 cs^-3, ((cs^-1 v)^2 (cs v)^2)^2, (er es^3 er es^-3)^2, ((es^-1 v)^2 (es v)^2)^2, cs^-3 v cs^3 cr cs^-3 v cr cs^3 cr^-1, cs^3 v cs^-3 cr cs^3 v cr cs^-3 cr^-1, (es^3 er es^-3 v)^2 er, (es^-3 er es^3 v)^2 er, (cs^-2 v cs^-1 v cs v cs^2 v)^2, (es^-2 v es^-1 v es v es^2 v)^2, (er es^4 er es^-4)^2, (es^-4 er es^4 v)^2 er, (es^4 er es^-4 v)^2 er, v cs^6 (v cs^-1)^7, (es^-3 v es^-1 v es v es^3 v)^2, (er es^5 er es^-5)^2, (es^5 er es^-5 v)^2 er, (es^-5 er es^5 v)^2 er, (es^4 v es^-4 v es^-1 v es v)^2, v es^10 (v es^-1)^11, ((7)) which has 43 relators of total length 597. It is apparently beyond GAP's ability to verify that these relators present the cube group, though I have verified some smaller wreath groups. This presentation is of course in terms of generators {v,es,er,cs,cr}, not the generators {F,B,L,R,T,D} natural to the cube. But they can be translated as follows. Each quarter-turn Q can be expressed as a word w(Q) over {v,es,er,cs,cr}, and adding the relators F' w(F), B' w(B), L' w(L), R' w(R), T' w(T), D' w(D) ((8)) will create a presentation on eleven generators {v,es,er,cs,cr,F,B,L,R,T,D}. I estimate that the added relators will be under 70 letters each, and probably less. If it is desired to completely eliminate {v,es,er,cs,cr}, that may be done by replacing each of {v,es,er,cs,cr} with processes in terms of F,B,L,R,T,D, throughout ((7,8)). My understanding of the current state of the software is that the processes will probably be less than 30 quarter-turns each. This would yield a presentation of 49 relators and perhaps 2000 letters. It should be possible to improve this quite a bit. I would suggest: 1. Choosing the corner and edge numbering to reduce the rewriting blowup, 2. Allowing w(Q) to use previously-related Q's as well as {v,es,er,cs,cr}. 3. Adding new relators to abbreviate higher powers, especially of es and cs, in the presentation. 4. Introducing short relators such as F^4=FBF'B'=e to cut down on the general verbosity of the relators. But improvement to the level of actual comprehensibility may require new ideas. Perhaps Dave Rusin's "clearer statement" of the question may help, if I can figure out what it means. Dan posted and e-mailed Hoey@AIC.NRL.Navy.Mil ============================================================================== Date: Sun, 17 Dec 95 21:09:25 EST From: hoey@AIC.NRL.Navy.Mil To: Cube-Lovers@AIC.NRL.Navy.Mil, Frank R Bernhart , rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Presenting Rubik's Cube In my article on a presentation of the Rubik's cube group last night, I omitted a relator from list ((7)): v es v cs v es^-1 v cs^-1. This brings the number of relators to 44, with a total length of 605. Experiments with GAP on some smaller cube-like groups indicate that with this addition, the presentation is correct. My apologies for the error. Dan Hoey Posted and e-mailed. Hoey@AIC.NRL.Navy.Mil