Théorie des groupes et Rubik's cube

- " What's commutative and purple ?
- " An Abelian grape "

  Mise en garde
  Notations
  Générateurs du groupe du cube
  Cardinal du groupe
  Des groupes finis connus dans le Rubik's cube
  Centre du groupe
  Structure du groupe
  Groupe dérivé du groupe
  Bibliographie




Mise en garde  

Je ne suis pas un spécialiste de la théorie des groupes, mias plutôt un amateur éclairé dans ce secteur.
Dans cette page, j'ai regroupé des résultats trouvés ici et là, que j'ai traduits, adaptés et retravaillés, parfois complétés mais pas toujours !
Ainsi, beaucoup de résultats étaient et restent sans démonstrations.

Je suppose connus les rudiments de la théorie des groupes (niveau de licence de mathématiques), en particulier : homorphismes, noyaux, groupes symétriques et alternés, signature d'une permutation, opération d'un groupe sur un ensemble, produits de groupes (direct, semi-direct).

Retour vers le haut de la page


Notations  

Pour les manipulations du cube, les notations utilisées sont la traduction française des notations anglaises standards de David Singmaster, qu'il faut avoir à l'esprit (si vous avez besoin de comprendre les sites en anglais).

On note respectivement pour les faces avant, postérieure, gauche, droite, haut et bas :
a, p, g, d, h et b, la manipulation qui consiste en un quart de tour dans le sens des aiguilles d'une montre de la face
a', p', g', d', h' et b', la manipulation qui consiste en un quart de tour dans le sens inverse des aiguilles d'une montre de la face. a2, p2, g2, d2, h2 et b2, la manipulation qui consiste en un demi-tour de la face.

On notera G le groupe des manipulations du Rubik's cube, c'est-à-dire le groupe des permutations des 48 facettes mobiles du Rubik's cube. G est un sous-groupe de S48.

CA et CS sont des abréviations de cube-arête et de cube-sommet.

Pour plus de clarté,
   les notations et définitions seront écrites de cette couleur,
   les résultats et théorèmes seront écrits de cette couleur
   et les démonstrations seront écrites de cette couleur

Retour vers le haut de la page


Générateurs du groupe du Rubik's cube  

Le groupe G est engendré par les rotations élémentaires d'un quart de tour des faces : G = < a, p, h, b, g, d >

On numérote les facettes du cube de 1 à 48. On peut ainsi considérer le groupe du cube comme un sous-groupe de S48

123
4h5
678
91011171819252627333435
12g1320a2128d2936p37
141516222324303132383940
414243
44b45
464748

Les générateurs de base décomposés en produit de cycles à supports disjoints :

a := (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11),

p := (33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27),

g := ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35),

d := (25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24),

h := ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19),

b := (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40).


Remarque : Il existe des ensembles générateurs du groupe à moins de 6 éléments.
  1. Les 5 générateurs a, g, d, h et p engendrent le générateur b : on a   b = P h P où P = d g' a2 p2 d g'.
    On a donc G = < a, p, h, g, d >
  2. Il y a mieux !   G = < m991, m992>    où m991 = hpghg'h'p' et m992 = d2agb'd'

Retour vers le haut de la page


Cardinal du groupe du Rubik's cube  

G est le groupe des manipulations du Rubik's cube

card G = 8! x 37 x 12! x 210 = 43 252 003 274 489 856 000

Explication (Nouvelle fenêtre)

On note :

On a card HA = 980 995 276 800    et   card HS = 88 179 840

card( G ) =card( HS ) x card( HA ) / 2


En effet, G n'est pas isomorphe au produit direct HA x HS mais à un quotient d'indice 2.
L'explication détaillée se trouve plus loin et s'explique en deux mots en disant que un élément (x,y) de HA x HS provient d'un élément de G ssi x et y sont, en tant que permutations des cubes et non des facettes, de même signature (i.e toutes les deux paires ou toutes les deux impaires)
Par exemple, un élément de HA x HS peut permuter deux CS sans rien changer d'autre , ce qui est impossible par un élément de G. Autre exemple, un élément de HA x HS peut permuter deux CS et permuter trois CA, ce qui est impossible par un élément de G.



Facteurs premiers de card ( G )

card G = 11 x 72 x 53 x 314 x 227

Le plus grand facteur premier de card( G ) est 11.

Remarque : on a le théorème suivant, valable pour tous les cubes de Rubik 2x2x2, 3x3x3, 4x4x4, ...,

Le plus grand facteur premier du nombre de permutations d'un cube NxNxN est le plus grand nombre premier inférieur ou égal à la longueur du plus grand cycle possible de pièces du cube.

Dans le cas du cube 3x3x3, le plus grand cycle possible est celui des cubes-arêtes qui est de longueur 12 donc le plus grand facteur premier de card( G ) est donc 11.


Elément d'ordre maximal

Le plus grand ordre possible d'un élément du groupe du Rubik's cube est 1260.

Le mouvement de Butler    d a2 p-1 h p-1    est un élément d'ordre 1260.

Retour vers le haut de la page


Des groupes finis connus dans le groupe du Rubik's cube  

Le groupe du Rubik's cube est un exemple de groupe fini dont l'ordre est relativement grand et qui n'est pas un groupe générique ( groupes symétriques Snet groupes alternés An, groupes diédraux Dn).
Il a à ce titre quelques propriétés intéressantes :
  1. Tout groupe d'ordre inférieur à 13 est isomorphe à un sous-groupe de G.
    Z/13Z (le groupe cyclique d'ordre 13) n'est pas isomorphe à un sous-groupe de G.
  2. Tout groupe non-abélien d'ordre inférieur à 26 est isomorphe à un sous-groupe de G.
    D26 (le groupe diédral d'ordre 26) n'est pas isomorphe à un sous-groupe de G.
  3. Il existe une représentation du groupe des quaternions dans G
    on note :
    MR = "middle right quarter turn" = 1/4 de tour de la tranche de droite (celle qui coupe verticalement la face avant)
    m435 = a2 (MR)' 2 (MR)2 h' (MR)2 a2(MR)2 a2
    m706 = a2 (MR) h' (MR)' h' (MR) H (MR)' h a2
    m707 = p' a2 d' h' (MR) h d h (MR)' h' a2 p
    m710 = a h2 a' h' g' p' h2p h g

    alors   Q* =< 1, m435, m706, m707, m710> est isomorphe au groupe des quaternions
Retour vers le haut de la page


Centre du groupe du Rubik's cube  
Rappel : le centre d'un groupe est l'ensemble des éléments du groupe qui commutent avec tous les autres.

Le centre de G est Z(G) = {1, m490}
où m490 est le "superflip" qui fait pivoter tous les cubes-arêtes et laisse invariants les cubes-sommets.

m490 = dga phb dga pha2 (MR) a2h' (MR)2 p2 (MR)' p2 h (MR)2 b
avec   MR = "middle right quarter turn" = 1/4 de tour de la tranche de droite (celle qui coupe verticalement la face avant)

Retour vers le haut de la page


Structure du groupe du Rubik's cube  



L'homomorphisme fSA

On pose
fS : g dans G --> gS dans S8        où gS est la permutation des CS induite par g

On peut dire qu'à travers fS , on considère une manipulation du Rubik cube comme une simple permutation des CS, sans s'occuper des couleurs des facettes.

fA : g dans G --> gA dans S12        où gA est la permutation des CA induite par g

On peut dire que à travers fA , on considère une manipulation du Rubik cube comme une simple permutation des CA, sans s'occuper des couleurs des facettes.

fS et fA sont des homomorphismes


On pose fSA : g dans G --> (gS, gA) dans S8 x S12

fSA est un homomorphisme



Image de l'homomorphisme fSA : Im fSA

On note sgn(p) la signature d'une permutation p

Im fSA = { (x,y) dans S8 x S12 / sgn( x ) = sgn( y ) }

En d'autres termes : l'image de fSA est l'ensemble des couples de permutations de S8 x S12 qui ont la même signature (i.e toutes les deux paires ou toutes les deux impaires)

Remarque : Voila l'explication de quelques choses que tous les Rubikcubistes savent bien.

DEMONSTRATION

Posons E = { (x,y) dans S8 x S12 / sgn( x ) = sgn( y ) }
On doit montrer que Im fSA = E

1°) Démontrons que Im fSAest inclus dans E

On pose s : (x,y) dans S8 x S12 --> sgn( x ) x sgn( y ) dans {-1 ; 1}

Lemme : s est un homomorphisme   (c'est évident...)

Il faut donc montrer que pour tout g dans G,   s( fSA( g ) ) = 1

* Soit h dans G un quart de tour d'une face, hS est un 4-cycle sur 4 CS et hA est un 4-cycle sur 4 CA,
donc  sgn( hS ) = sgn( hA ) = (-1)4-1 = -1     (Rappel : sgn ( cycle ) = (-1)longueur du cycle - 1 )
donc   s( fSA( h ) ) = s ( hS , hA ) = (-1) x (-1) = 1    pour tout quart de tour h

* Soit g dans G quelconque, g est un produit d'un certain nombre de quarts de tour :    g = h1 x h2 x ... x hn où hi est un quart de tour d'une face
fSA( g ) = fSA( h1) x fSA h2 ) x ... x fSA (hn )    car fSA est un homomorphisme de groupes
s( fSA( g ) ) = s( fSA( h1) ) x s( fSA h2 ) ) x ... x s( fSA (hn ) )    car s est un homomorphisme de groupes
s( fSA( g ) ) = 1 x 1 x ... x 1     car s( fSA( h ) ) pour tout quart de tour h
donc   s( fSA( g ) ) = 1

On a donc pour tout g dans G,   s( fSA( g ) ) = 1


2°) Réciproquement : E = { (x,y) dans S8 x S12 / sgn( x ) = sgn( y ) } est inclus dans Im fSA

En d'autres termes : est-ce que tout élément de E provient d'un élément de G par SA ?

On doit montrer que pour tout  ( x ; y ) dans E, il existe g dans G tel que gS = x et gA = y

* Soit (x,y) dans S8 x S12 / sgn( x ) = sgn( y ) = 1   i.e   (x,y) dans A8 x A12

On connaît un élément g de G telle que gS est un 3-cycle sur 3 CS de la face supérieure et qui ne change rien d'autre .
En particulier, g laisse les CA à leurs places, i.e   g est dans HA = Stab ( FS ) = {g dans G / pour tout fS dans FS, g( fS )= fS}
On connaît alors un élément de G qui est un 3-cycle sur 3 CS quelconques: il suffit d'amener les 3 CS en question sur la face supérieure à l'aide d'une manipulation b, d'appliquer g puis b-1 et  b g b-1 est un 3-cycle sur les 3 CS.

Donc pour tout 3-cycle c de A8 , il existe g dans G tel que  gS = c .
Or, on a le résultat général suivant : pour n>2, An est engendré par les 3-cycles,
donc pour tout élément x de A8 , il existe g dans HA tel que  gS = x

De même, on connaît un élément g de G telle que gA est un 3-cycle sur 3 CA de la face supérieure et qui ne change rien d'autre , i.e g est dans HS = Stab ( FA ).
Et ainsi on peut montrer que : pour tout élément y de A12 , il existe h dans HS tel que  hA = y

On a donc : pour tout (x,y) dans A8 x A12 , il existe g dans HA et h dans HS tels que gS = x et hA = y

g dans HA donc gA = 1 donc fSA( g ) = ( gS , 1 ) = ( x ,1 )
h dans HS donc hS = 1 donc fSA( h ) = (1 , hA ) = ( 1 , y )
fSA est un homomorphisme donc fSA( gh ) = fSA( g ) x fSA( h ) = ( x ,1 ) ( 1 , y ) = ( x , y )
En posant   k = gh, on a fSA( k ) = ( x , y )
donc ( x , y ) appartient à Im fSA
donc A8 x A12 est inclus dans Im fSA

* (x,y) dans S8 x S12 / sgn( x ) = sgn( y ) = -1

Soit q un quart de tour d'une face et (qS , qA) = fSA( q )
alors sgn ( qS ) = sgn( qA ) = (-1)3 = -1 (qS ) et qA sont des 4-cycles)
(xqS, yqA) est dans A8 x A12 donc il existe k dans G tel que fSA( k ) = (xqS, yqA)
Alors : fSA( kq-1 ) =fSA( k ) fSA( q-1 ) = (xqS, yqA) ( qS-1 , qA-1 ) = ( x , y )
donc ( x , y ) appartient à Im fSA

FIN DE LA DEMONSTRATION


Noyau de l'homomorphisme fSA : Ker fSA

Ker fSA = { g dans G / gS = gA = 1} , c'est-à-dire l'ensemble des manipulations du cube qui ne bouge aucun CA ni CS, c'est-à-dire les manipulations qui ne font que pivoter des CA ou des CS sur eux-mêmes.

On identifie chaque g G avec le quadruplet ( fS( g ) , fA( g ), xg, yg ) où xg et y g sont les "orientations" définies ci-dessous.
Supposons que le cube soit fixé dans l'espace en position résolue.
Pour chaque sous-cube mobile (CS ou CA), on choisit une fois pour toutes une facette sur ce sous-cube et on marque cette facette avec un '+' .
Il y a trois possibilités pour un CS et deux possibilités pour un CA. Le choix est arbitraire mais sans importance : ce qui sera important sera le changement global intervenu sur ces '+'.
On numérote les CS de 1 à 8 et les CA de 1 à 12.
Alors, pour chaque g dans G, on observe la configuration du cube après la manipulation g.

Pour chaque CS, on note
On obtient ainsi un 8-uplet de '0' , '1' et de '2' : xg = (x1, ... , x8) où chaque xi mesure le changement d'orientation du CS n° i

Pour chaque CA, on note
On obtient ainsi un 12-uplet de '0' et de '1' : yg = (y1, ... , y8) où chaque yi mesure le changement d'orientation du CA n° i


Une explication plus imagée :
On place le cube en position résolue.
On numérote les CS de 1 à 8 et les CA de 1 à 12.
Pour chaque sous-cube mobile (CS ou CA), on choisit une fois pour toutes une facette sur ce sous-cube et on marque cette facette avec un '+' .
On prend une photographie du cube résolu.
On effectue la manipulation g et on prend une photographie du cube ainsi obtenu.
On note le changement des facettes '+' de chacun des CS de 1 à 8 (un '0' si elle n'a pas changé, un '1' si elle a tourné de +120° et un '2' si elle a tourné de -120°)
On note le changement des facettes '+' de chacun des CA de 1 à 12 (un '0' si elle n'a pas changé, un '1' si elle a changé).

Exemple : S on marque toutes les facettes de la face avant avec un '+', le monoswap aba2b2a2b-1a-1 qui permute les Cs ahd et ahg, en pivotant le CS ahd de 120° dans le sens des aiguilles d'une montre et le CS ahg de 120° dans le sens contraire des aiguilles d'une montre ( cette manipulation affecte aussi d'autres parties du cube).
Cette manipulation donne un '1'pour le CS ahd et un '2' pour le CS ahg.


Structure du groupe du Rubik's cube G

Théorème :
Un quadruplet (r, s, x, y) avec r S12, s S8, x {0, 1, 2} 8 et y {0, 1} 12 correspond à une position possible du Rubik's cube si et seulement si :
  1. sgn( s ) = sgn( r )        (même parité des permutations sur les CS et les CA)
  2. x1 + x2 + ... + x8 = 0 (mod 3)        (conservation de l'orientation totale des CS)
  3. y1 + y2 + ... + y12 = 0 (mod 2)        (conservation de l'orientation totale des CA)


Soit H = { (r, s, x, y) avec r S12, s S8, x {0, 1, 2} 8, x1 + x2 + ... + x8 = 0 (mod 3), y {0, 1} 12, y1 + y2 + ... + y12 = 0 (mod 2) }

L'opération (r, s, x, y) * (r ', s ', x ', y ') = ( r * r ', s * s', x + r(x ' ), y + s( y') ) définit une structure de groupe sur H.


Théorème :
Le groupe du Rubik's cube G est le noyau de l'homomorphisme
s : (r, s, x, y) H ----> sgn( r ) x sgn( s ) { -1, 1 }


STRUCTURE DU GROUPE DU RUBIK'S CUBE :

G est produit semi-direct de Ker fSA et de Im fSA    : G = Ker fSA |x Im fSA

C'est-à-dire :
G = { (r, s, x, y) avec r S12, s S8 / sgn( r ) = sgn( s ), x {0, 1, 2} 8 / x1 + x2 + ... + x8 = 0 (mod 3), y {0, 1} 12 / y1 + y2 + ... + y12 = 0 (mod 2) }
Muni de l'opération (de produit-semi-direct) : (r, s, x, y) * (r ', s ', x ', y ') = ( r * r ', s * s', x + r(x ' ), y + s( y') )


Corollaire :
G H d'indice 2

Démonstration du corollaire :
G est distingué dans H car G = Ker s et un noyau d'homomorphisme est toujours distingué (il est même caractéristique, i.e stable par tout automorphisme, et pas seulement par les automorphismes intérieurs).
G est d'indice 2 car H / Ker s Im s soit H / G {-1 ; 1}




Retour vers le haut de la page


Groupe dérivé du groupe du Rubik's cube  

On note G' le groupe dérivé de G, i.e le groupe engendré par les commutateurs [ x , y ] = xyx-1y-1

G ' = <{ [ x , y ] = xyx-1y-1   , x G, y G }> ,
.



Théorème :
G ' = { g G / sgn( fS( g ) ) = sgn( fA( g ) ) = 1}

C'est-à-dire : G' est le noyau de l'homomorphisme s' : g G ----> ( sgn( fS( g ) ) , sgn( fA( g ) ) { (-1 ; -1) ; (1 ; 1)}

D'après le premier théorème d'isomorphisme, G / Ker s' Im s' , donc il s'ensuit immédiatement

Corollaire 1 :
| G ' | = | G | / 2

G / Ker s' Im s' soit G / G' { (-1 ; -1) ; (1 ; 1)} d'où | G / G' | = 2

Corollaire 2 :
G ' G

Démonstration du corollaire 2 :
G' = Ker s' , or un noyau d'homomorphisme est un sous-groupe distingué ( et même caractéristique, i.e stable par tout automorphisme)
Autre démonstration du corollaire 2, à partir du corollaire 1 : Un sous-groupe d'indice 2 est toujours distingué


Retour vers le haut de la page



Bibliographie  

Bibliographie

Eléments de théorie des groupes, Josette Calais (P.U.F.)
Cours d'algèbre, Daniel Perrin (Polycopié du cours de l'école normale supérieure féminine, édité actuellement chez Masson)
Rubik's cube et groupes de transformations, Publication de l'IREM de DIJON
(Série ER1, Recherche primaire/secondaire ; Mathématiques et grand public : Rubik's cube et groupes de transformations)
Cliquez ici pour le commander (10 Francs + environ 10F de frais de port)
Article de "Pour la science" n°34, août 1980, "Cube hongrois et théorie des groupes" par Emmanuel Halberstadt
Réussir le Rubik's cube, André Warusfel
Tous les secrets du Rubik's cube, Jérôme Jean-Charles

Documents sur internet : (tout est en anglais ...)

Rubik's Cube Lecture Notes : un site en anglais avec tout plein de théorie sur le cube et les groupes
Les archives de Cube Lovers : Cube Lovers Index by Subject
Domain of the cube : le site de Mark Longridge's , un fervent Cube Lover (des articles de théorie des groupes)

Retour vers le haut de la page