La prueba de que el grupo de cubo de Rubik es generado por la 2

Question

Singmaster (1981) escribe, en la página 32 de sus Notas sobre el de Rubik Cubo Mágico:

Frank Barnes se observa que el grupo del cubo es generado por dos movimientos: \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*} Observar que $\alpha^7$ $11$- ciclo de los bordes y a $\alpha^{11}$ $7$- ciclo de las esquinas, que $\beta$ afecta el borde y esquina izquierda fija por $\alpha$, $$\beta^2 = (UF)_+(UL)_+(UBR)_-(UFL)_-(UFR)_-$ $ [ ... ] El resto de los detalles se dejan como ejercicio.

Yo no había visto esta notación antes, así que voy a explicar aquí.

La notación como $(LU, BD, DF)$ significa un borde ciclo, en el que:

• El $L$-$U$ el borde se mueve a la $B$-$D$ borde del lugar, con la $L$ la mitad terminan en las $B$ cara, y el $U$ la mitad terminan en las $D$ cara.
• Del mismo modo $BD \to DF$$DF \to LU$.

La notación para las curvas es similar.

La notación como $(UF, UL)_+$ es un trenzado de ciclo: de nuevo, $UF \to UL$, pero ahora $UL \to FU$; el borde final consigue volteadas al ciclismo vuelve a la primera borde. Para las esquinas, la notación es similar, pero las esquinas de girar, que no voltear. Un subíndice $+$ medios de rotación en sentido horario, un subíndice $-$ significa que la rotación en sentido antihorario.

$(UR)_+$ significa que de un solo filo, se voltea. $(UBR)_-$ significa una sola esquina se gira en sentido antihorario.

Me gustaría demostrar que esto es cierto, por escrito cada elemento en $\{F,B,L,R,U,D\}$ como producto de los elementos de la $\{\alpha, \beta, \alpha^{-1}, \beta^{-1}\}$ – de preferencia, tener los productos a ser tan corto como sea posible. Cómo se podría ir sobre la búsqueda de ellos? (Estoy de acuerdo con el uso de software como GAP – si lo es en todos los computacionalmente posible.)

Answer 1

Para empezar, vamos a utilizar el ejemplo de "Analizar el Cubo de Rubik con la BRECHA". Se crea el grupo generado por los seis generadores, correspondiente a las seis caras del cubo:

                 +--------------+
                 |              |
                 |  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 |
                 |              |
                 +--------------+

Es fácil identificar cuál de las seis permutaciones corresponde a la rotación de la parte superior (U), izquierda (L), frontal (F), derecho (R), la espalda (B) y (D) los lados de las mismas letras como en la pregunta anterior. Ahora vamos a crear en la BRECHA:

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);;

A continuación, vamos a construir un grupo generado por estas permutaciones:

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

Ahora podemos probar a utilizar SmallGeneratingSet encontrar un set de generación de energía que tiene menos elementos. SmallGeneratingSet no garantiza devolver un no-redundante lista de mínima longitud posible, pero esta vez tenemos la suerte:

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

Por lo tanto, de hecho, el grupo es de 2-generada. Ahora vamos a crear permutaciones a y b correspondiente a $\alpha$ $\beta$ a partir de la pregunta:

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)

Es fácil comprobar que el hecho de generar el mismo grupo:

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

Queda por mostrar cómo factorise, por ejemplo, $U$ en términos de $\alpha$ $\beta$ y sus inversas. Vamos a utilizar el mismo enfoque que se utiliza aquí para resolver el rompecabezas.

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

No se garantiza que esta factorización es la más corta de investigación que sería mucho más difícil la tarea de cálculo.

Ahora uno podría igualmente calcular la factorización para otros cinco permutaciones. Ellos se calculan más rápido que en la primera llamada a PreImagesRepresentative , ya que algunos de los datos necesarios para el algoritmo ya han sido calculados y almacenados en el grupo.