GAP

Main BranchesDownloads Installation Overview Data Libraries Packages Documentation Contacts FAQ GAP 3 

SitemapNavigation Tree

Analyzing Rubik's Cube with GAP 3See also the corresponding GAP 4 page for an extended version of this example. This is an example by Martin Schönert, 1993. An almost classical permutation group of small degree is examined with some elementary GAP 3 commands. The associated GAP 3 input file is also available.
Ideal Toy Company stated on the package of 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 (we reduce the line length to get a more appropriate output format). gap> SizeScreen( [71, ] );; 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 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 gap> cmpl1 := Stabilizer( cube1, [1,2,3,4,5,6,8,13], OnSets );; gap> Size( cmpl1 ); 40320 We verify the complement properties: gap> Size( Intersection( cmpl1, Kernel( blockhom1 ) ) ); 1 gap> Closure( cmpl1, Kernel( blockhom1 ) ) = cube1; true
There is even a more elegant way to show that gap> IsIsomorphism( OperationHomomorphism( cmpl1, cube1b ) ); true
Of course, theoretically it is clear that
In fact we know that 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 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 (we assign a name to the group
gap> cube.name := "cube";; 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, but demonstrating them all would take too much room. Martin Schönert Lehrstuhl D für Mathematik RWTH Aachen Pontdriesch 1416 52062 Aachen Germany email: Martin.Schoenert@Team4.DE 

The GAP Group Last updated: Wed Dec 21 10:59:42 2016 