7
$\begingroup$

I'm trying to create the Rubik's Revenge (4x4x4 cube) group in GAP .

Take the following net of the 4x4x4 cube with each sticker labelled with a number. The front, left, upper, right, down, and back faces labelled with their respective initials.

                    U
                 [64][65][66][67]
                 [68][69][70][71]
                 [72][73][74][75]
                 [76][77][78][79]               R
L                       F
[48][49][50][51] [ 0][ 1][ 2][ 3] [16][17][18][19]
[52][53][54][55] [ 4][ 5][ 6][ 7] [20][21][22][23]
[56][57][58][59] [ 8][ 9][10][11] [24][25][26][27]
[60][61][62][63] [12][13][14][15] [28][29][30][31]

                D[80][81][82][83]
                 [84][85][86][87]
                 [88][89][90][91]
                 [92][93][94][95]

                B[32][33][34][35]
                 [36][37][38][39]
                 [40][41][42][43]
                 [44][45][46][47]

We will consider 12 basic moves. These are the standard definitions of moves for the 4x4x4 cube. Note that each is a quarter turn.

  1. F: a clockwise turn of front-most face.
  2. f: a clockwise turn of front-inner segment.
  3. B: a counterclockwise turn of the back-most face.
  4. b: a counterclockwise turn of the back-inner segment.
  5. U: a clockwise turn of the top-most face (viewed from above).
  6. u: a clockwise turn of of the inner-top segment (viewed from above).
  7. D: a counterclockwise turn of the bottom-most face (viewed from above).
  8. d: a counterclockwise turn of the inner-bottom segment (viewed from above).
  9. R: a clockwise turn of the right-most face (viewed from the right).
  10. r: a clockwise turn of the inner-right segment (viewed from the right).
  11. L: a counterclockwise turn of the left-most face (viewed from the right).
  12. l; a counterclockwise turn of the inner-left segment (viewed from the right).

Each of these moves permutes the numbers in the above net. I write out these permutations in GAP. Note I have substituted 96 for 0 because GAP does not permit 0 in a cycle.

F:=(96,3,15,12)(1,7,14,8)(2,11,13,4)(5,6,10,9)(16,83,63,76)(20,82,59,77)(24,81,55,78)(28,80,51,79);

f:=(72,17,87,62)(73,21,86,58)(74,25,85,54)(75,29,84,50);

B:=(32,35,47,44)(33,39,46,40)(34,43,45,36)(37,38,42,41)(64,60,95,19)(65,56,94,23)(66,52,93,27)(67,48,92,31);

b:=(68,61,91,18)(69,57,90,22)(70,53,89,26)(71,49,88,30);

U:=(64,67,79,76)(65,71,78,72)(66,75,77,68)(69,70,74,73)(96,48,47,16)(1,49,46,17)(2,50,45,18)(3,51,44,19);

u:=(4,52,43,20)(5,53,42,21)(6,54,41,22)(7,55,40,23);

D:=(80,83,95,92)(81,87,94,88)(82,91,93,84)(85,86,90,89)(12,28,35,60)(13,29,34,61)(14,30,33,62)(15,31,32,63);

d:=(8,24,39,56)(9,25,38,57)(10,26,37,58)(11,27,36,59);

L:=(48,51,63,60)(49,55,62,56)(50,59,61,52)(53,54,58,57)(96,80,32,64)(4,84,36,68)(8,88,40,72)(12,92,44,76);

l:=(1,81,33,65)(5,85,37,69)(9,89,41,73)(13,93,45,77);

R:=(16,19,31,28)(17,23,30,24)(18,27,29,20)(21,22,26,25)(3,67,35,83)(7,71,39,87)(11,75,43,91)(15,79,47,95);

r:=(2,66,34,82)(6,70,38,86)(10,74,42,90)(14,78,46,94);

I then look at the permutation group generated by these moves.

G:=Group(F,f,B,b,U,u,D,d,L,l,R,r);

Now to determine if this group G is the correct group, I look at its size divided by 24 (to account for the rotational symmetries).

gap> Size(G)/24;
707195371192426622240452051915172831683411968000000000

I compare this number to the size provided on the Wikipedia article (linked above):

7401196841564901869874093974498574336000000000

My Problem:

What is causing this discrepancy of size?

The first thing I thought was that I had written the permutations wrong, but I rewrote them and got the same thing, so I don't think this is the case. This leads me to believe that I have some theory wrong.

Note that the ratio of my calculated to wikipedia's given size is 95551488 which is $2^{17} * 3^6$.

Also, the formula given on Wikipedia is $$\frac{8!\cdot 3^7 \cdot 24!^2}{4!^6\cdot 24}$$

$\endgroup$
  • $\begingroup$ You have 96 in some of your permutations, but no 96 on the cube itself. $\endgroup$ – TokenToucan Dec 16 '15 at 3:20
  • $\begingroup$ I used 96 instead of 0. Forgot to mention that. Gap won't let you use 0 in a cycle $\endgroup$ – Liam Dec 16 '15 at 3:21
5
$\begingroup$

It depends on the definition of the puzzle: If the faces are colored uniformly, for example a swap of 5 and 6 is not seen in the puzzle. You can see this discrepancy in the group. We construct the subgroup that fixes the corners in place, but on edges and middle pieces allows a permutation that is not seen in the puzzle:

cor:=[3,12,15,32,35,44,47];
s:=Stabilizer(G,cor,OnTuples);
edge:=[ [ 1, 2 ], [ 4, 8 ], [ 7, 11 ], [ 13, 14 ], [ 17, 18 ], [ 20, 24 ], 
[ 23, 27 ], [ 29, 30 ], [ 49, 50 ], [ 52, 56 ], [ 55, 59 ], [ 61, 62 ], 
[ 81, 82 ], [ 84, 88 ], [ 87, 91 ], [ 93, 94 ], [ 33, 34 ], [ 36, 40 ], 
[ 39, 43 ], [ 45, 46 ], [ 65, 66 ], [ 68, 72 ], [ 71, 75 ], [ 77, 78 ] ];
s:=Stabilizer(s,edge,OnTuplesSets); 
cen:=[ [ 5, 6, 9, 10 ], [ 21, 22, 25, 26 ], [ 53, 54, 57, 58 ],
[ 85, 86, 89, 90 ], [ 37, 38, 41, 42 ], [ 69, 70, 73, 74 ] ];
s:=Stabilizer(s,cen,OnTuplesSets);

gives you a subgroup of order $2^{17}3^6$ that does no recognizable action on the puzzle. This is the discrepancy you observe. You could (modulo rotations in space) consider cosets of this subgroup to describe the puzzle.

In the case of the $3\times 3\times 3$ cube this phenomenon is often hidden by fixing the middle pieces in space which deals with space rotations as well as rotations of the middle pieces. However there are similarly operations that would rotate middle pieces (and which turn up in reality if you take a Rubik's cube with pictures on the faces). If you also account for rotations of the middle pieces you get a larger group (and a more difficult puzzle).

$\endgroup$
  • $\begingroup$ For further reading I also suggest Solving Puzzles related to Permutation Groups by Sebastian Egner and Markus Püschel (Proc. ISSAC 98, pages 186-193) $\endgroup$ – Alexander Konovalov Dec 16 '15 at 18:38
  • $\begingroup$ BTW, a single swap of 5 and 6 is not possible: (5,6) in G returns false. But (5,6)(9,10) in G returns true. Similar constraints exist in 3x3x3 cube as well. $\endgroup$ – Alexander Konovalov Dec 16 '15 at 21:23
2
$\begingroup$

I haven't checked your calculations, but I suspect that it's because in the 4x4x4 cube (unlike the 3x3x3 cube), there are two identical copies of each edge piece (in the "solved" configuration of the cube, the two copies are next to each other along each edge). So the size of the permutation group is not equal to the number of configurations. If you apply a permutation which swaps 2 identical pieces (or several pairs of identical pieces), then you still end up with the same configuration.

$\endgroup$
  • $\begingroup$ Makes sense, I'll have to look into it some more $\endgroup$ – Liam Dec 16 '15 at 9:42
  • 1
    $\begingroup$ So we have an "invisible subgroup" of transformations which do not change the visible state of the cube. The result of the GAP calculations is $2^{17} 3^6$ times larger then the numbers from Wikipedia. I think there is also a "contribution" to that from having 4 central pieces on each side. $\endgroup$ – Alexander Konovalov Dec 16 '15 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.