Proof that the Rubik’s Cube group is 2-generated

Singmaster (1981) writes, on page 32 of his Notes on Rubik’s Magic Cube:

Frank Barnes observes that the group of the cube is generated by two moves: \begin{align*} \alpha &= L^2 B R D^{-1} L^{-1} &=(RF,RU,RB,UB,LD,LB,LU,BD,DF,FL,RD)& \\ &&\cdot (FUR,UBR,LDB,LBU,DLF,BDR,DFR)\\ \beta &= UFRUR^{-1}U^{-1}F^{-1} &=(UF,UL)_+(UR)_+(UBR,UFL)_-(URF)_+ \end{align*} Observe that $\alpha^7$ is an $11$-cycle of edges and $\alpha^{11}$ is a $7$-cycle of corners, that $\beta$ affects the edge and corner left fixed by $\alpha$, and that $$\beta^2 = (UF)_+(UL)_+(UBR)_-(UFL)_-(UFR)_-$$ [...] The remaining details are left as an exercise.

I hadn't seen this notation before, so I'll explain it here.

Notation like $(LU, BD, DF)$ means an edge cycle, in which:

The $L$-$U$ edge moves to the $B$-$D$ edge's place, with the $L$ half ending up on the $B$ face, and the $U$ half ending up on the $D$ face.

Similarly $BD \to DF$ and $DF \to LU$.

The notation for corners is similar.

Notation like $(UF, UL)_+$ is a twisted cycle: again, $UF \to UL$, but now $UL \to FU$; the final edge gets flipped when cycling back to the first edge. For corners, the notation is similar, but corners rotate, they don't flip. A subscript $+$ means clockwise rotation, a subscript $-$ means counterclockwise rotation.

$(UR)_+$ means a single edge is flipped. $(UBR)_-$ means a single corner is rotated counterclockwise.

I would like to show that this is indeed true, by writing each element in $\{F,B,L,R,U,D\}$ as a product of elements in $\{\alpha, \beta, \alpha^{-1}, \beta^{-1}\}$ – preferably, having those product be as short as possible. How would I go about finding them? (I'm okay with using software like GAP – if it is at all computationally possible.)

Solution 1:

To start, we will use the example from "Analyzing Rubik's Cube with GAP". It creates the group generated by the six generators, corresponding to the six faces of the cube:

                 +--------------+
                 |              |
                 |  1    2    3 |
                 |              |
                 |  4   up    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  back  37 |
  |              |              |              |              |
  | 14   15   16 | 22   23   24 | 30   31   32 | 38   39   40 |
  |              |              |              |              |
  +--------------+--------------+--------------+--------------+
                 |              |
                 | 41   42   43 |
                 |              |
                 | 44  down  45 |
                 |              |
                 | 46   47   48 |
                 |              |
                 +--------------+

It is easy to identify which of the six permutations corresponds to the rotation of the upper (U), left (L), front (F), right (R), back (B) and down (D) sides to use the same letters as in the question above. We will now create them in GAP:

gap> U:=( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19);;
gap> L:=( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35);;
gap> F:=(17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11);;
gap> R:=(25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24);;
gap> B:=(33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27);;
gap> D:= (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40);;

Next, we will construct a group generated by these permutations:

gap> G:=Group(F,B,L,R,U,D);
<permutation group with 6 generators>
gap> Size(G);
43252003274489856000

We may now try to use SmallGeneratingSet to find a generating set that has fewer elements. SmallGeneratingSet does not guarantee to return a non-redundant list of minimal possible length, but this time we're lucky:

gap> sgs:=SmallGeneratingSet(G);
[ (1,32,41,3,6,19,35,48,22,27,11,25,9,38,16,33,17,8)(2,15,37,7,5,28,45,23,10,
    20)(4,13,34,44,12,18,26,21,31,42)(14,46,40)(29,36)(39,47), 
  (1,43,27,41,11,48)(2,29,23)(3,16,6,32,9,24)(4,20,5,18,21,37,45,15,39)(7,28,
    12,31,44,47,10,13,26)(8,40)(14,25)(17,38,35,30,33,22)(19,46)(34,36,42) ]
gap> Length(sgs);
2

Thus, indeed the group is 2-generated. Now let's create permutations a and b corresponding to $\alpha$ and $\beta$ from the question:

gap> a:=L^2*B*R*D^-1*L^-1;
(1,22,32,30,25,27,40)(2,15,12,10,39,42,20,31,28,26,29)(3,14,9,41,38,43,19)(4,
47,23,13,45,21,5,36,34,44,37)(8,33,46,35,16,48,24)
gap> b:=U*F*R*U*R^-1*U^-1*F^-1;
(3,6,27,11,33,17)(4,18,10,7)(5,26)(8,25,19)

It is easy to check that they indeed generate the same group:

gap> H:=Group(a,b);
<permutation group with 2 generators>
gap> Size(G)=Size(H);
true
gap> G=H;
true

It remains to show how to factorise, for example, $U$ in terms of $\alpha$ and $\beta$ and their inverses. We will use the same approach that is used here to solve the puzzle.

gap> K:=FreeGroup("a","b");
<free group on the generators [ a, b ]>
gap> hom := GroupHomomorphismByImages( K, H, GeneratorsOfGroup(F), GeneratorsOfGroup(H) );
[ a, b ] -> [ (1,22,32,30,25,27,40)(2,15,12,10,39,42,20,31,28,26,29)(3,14,9,
    41,38,43,19)(4,47,23,13,45,21,5,36,34,44,37)(8,33,46,35,16,48,24), 
  (3,6,27,11,33,17)(4,18,10,7)(5,26)(8,25,19) ]
gap> w:=PreImagesRepresentative( hom, U );
b*a^2*b*a^-5*b*a^-1*b^-1*(a*b*a)^2*b*a^-2*b*a^-1*b^-1*a*b^-1*a^-1*b^-1*a^3*b^-\
1*a^-2*(b^-1*(a*b)^2*a^4*b*a^-6*(b^-1*a^-1*b^-1*a)^2)^2*b^-1*a^3*b*(b*a)^4*a^2\
*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^2*a*(a*b)^\
4*a^3*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^2*(a*\
(a*b)^4*a^3*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)\
^2*a^2*b^-1*a^-2*b)^2*(a*b)^2*(b*a)^4*a^2*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a\
^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^2*a^2*b^-1*a^-2*(b*a)^2*a^2*b^3*a^2*b*a^-1*b^-1\
*a^22*b*a^-1*b^-1*a^-6*b^-2*a^2*b^-1*(b^-1*a^-1)^2*b^-6*a^4*b*(b*a^4*b*a^-7*b^\
-1*a^3)^2*b*((b*a)^4*a^2*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b\
*a^-1*b^-1*a)^2*a^2)^2*b^-1*a^-2*b*a^2*b^-1*a^-2*(b*a)^2*b*((b*a)^4*a^2*b^2*a^\
-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^2*a^2)^3*b^-1*a^-\
2*((b*a)^2*b)^2*a*b*a^3*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*\
a^-1*b^-1*a)^2*a^2*b^-5*a^-1*b^2*a^-1*b*(a*b*a^2)^2*a*b*a^-1*b*a^13*b*a^-1*b^-\
1*a^-11*b*a*b^-1*a^3*(b*a^-1)^2*b^-1*a*b^-1*a^-1*b^-1*a^3*b^-1*a^-2*b^-1*a*b^2\
*a*b*a^-1*((b*a)^2*a^3*b*a^-6*(b^-1*a^-1*b^-1*a)^2*b^-1*a)^2*(b*a)^2*b^2*a^4*b\
*a^-7*b^-1*(a*b)^3*a^4*b*a^-7*b^-1*a^3*b*(b*a)^4*a^2*b^2*a^-3*b*a^-1*b^-1*a^-2\
*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^2*(a*(a*b)^4*a^3*b^2*a^-3*b*a^-1*b^-\
1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^2*a^2*b^-1*a^-2*b)^2*(a*b)^2*(\
b*a)^4*a^2*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^\
2*a^2*b^-1*a^-2*b*a^4*b^3*a^2*b*a^-1*b^-1*a^22*b*a^-1*b^-1*a^-6*b^-2*a^2*b^-1*\
(b^-1*a^-1)^2*b^-6*a^4*b*(b*a^4*b*a^-7*b^-1*a^3)^2*b*((b*a)^4*a^2*b^2*a^-3*b*a\
^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^2*a^2)^2*b^-1*a^-2*b*a^\
2*b^-1*a^-2*(b*a)^2*b*((b*a)^4*a^2*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-\
1*a*b*(a*b*a^-1*b^-1*a)^2*a^2)^3*b^-1*a^-2*((b*a)^2*b)^2*a*b*a^3*b^2*a^-3*b*a^\
-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^2*a^2*b^-1*a^-2*(b*a)^2*\
a^3*b*a^-6*(b^-1*a^-1*b^-1*a)^2*b^-1*a*b^2*a*b*a^-1*(b*a)^2*a^3*b*a^-6*(b^-1*a\
^-1*b^-1*a)^2*b^-1*(a*b)^2*a^4*b*a^-6*(b^-1*a^-1*b^-1*a)^2*b^-1*a^-1*b^-6*a*b^\
6*a^2*b^5*a^-1*b*a*b^-5*a*(b*a^2*b)^2*a^-3*b^4*a^-5*b^-2*a^2*b^-1*(b^-1*a^-1)^\
2*b^-6*a^4*b*(b*a^4*b*a^-7*b^-1*a^3)^2*b^2*a^-1*b*a*b^-1*a^-1*b^-1*a*b^3*a^-1*\
b*(b*a^3)^2*b*a^-1*b*a^13*b*a^-1*b^-1*a^-11*b*a*b^-1*a^3*(b*a^-1)^2*b^-1*a*b^-\
1*a^-1*b^-1*a^3*b^-1*a^-2*b^-1*a*b^2*a*b*a^-1*((b*a)^2*a^3*b*a^-6*(b^-1*a^-1*b\
^-1*a)^2*b^-1*a)^2*(b*a)^2*b^2*a^4*b*a^-7*b^-1*(a*b)^3*a^4*b*a^-7*b^-1*a^3*b*(\
b*a)^4*a^2*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^\
2*(a*(a*b)^4*a^3*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^\
-1*a)^2*a^2*b^-1*a^-2*b)^2*(a*b)^2*(b*a)^4*a^2*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-\
5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^2*a^2*b^-1*a^-2*b*a^4*b^3*a^2*b*a^-1*b^-1*\
a^22*b*a^-1*b^-1*a^-6*b^-2*a^2*b^-1*(b^-1*a^-1)^2*b^-6*a^4*b*(b*a^4*b*a^-7*b^-\
1*a^3)^2*b*((b*a)^4*a^2*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*\
a^-1*b^-1*a)^2*a^2)^2*b^-1*a^-2*b*a^2*b^-1*a^-2*(b*a)^2*b*((b*a)^4*a^2*b^2*a^-\
3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a^-1*b^-1*a)^2*a^2)^3*b^-1*a^-2\
*((b*a)^2*b)^2*a*b*a^3*b^2*a^-3*b*a^-1*b^-1*a^-2*b*a^-5*b*a^-1*b^-1*a*b*(a*b*a\
^-1*b^-1*a)^2*a^2*b^-1*a^-2*(b*a)^2*a^3*b*a^-6*(b^-1*a^-1*b^-1*a)^2*b^-1*a*b^2\
*a*b*a^-1*(b*a)^2*a^3*b*a^-6*(b^-1*a^-1*b^-1*a)^2*b^-1*(a*b)^2*a^4*b*a^-6*(b^-\
1*a^-1*b^-1*a)^2*b^-1*a^-1*b^-6*a*b^6*a^2*b^5*a^-1*b*a*b^-5*a^-1*b^-1*(a^-1*b^\
-1*a*b^2)^2*b^4

It's not guaranteed that this factorisation is the shortest - finding that would be much more difficult computational task.

Now one could similarly calculate factorisation for other five permutations. They will be computed faster than in the first call to PreImagesRepresentative since some data needed for the algorithm are already computed and stored in the group.

Proof that the Rubik’s Cube group is 2-generated

Solution 1:

Related

Recent Posts