Voir la source de Groupe du Rubik's Cube

Cet article présente un modèle mathématique et une [[Présentation d'un groupe|présentation]] du '''[[groupe (mathématiques)|groupe]]''' du '''[[Rubik's Cube]]'''.

== Notations utilisées ==

* <math>G \,</math> est le [[Groupe (mathématiques)|groupe]] des mouvements légaux ou le groupe des états (sans démonter le cube !).
* <math>H \,</math> est le groupe élargi ou le groupe des états étendus (ici on peut démonter le cube, mais les mouvements des sommets et des arêtes doivent rester chacun dans leur camp).
* <math>C_n \, = \, \mathbb Z/n\mathbb Z</math> est l'ensemble des classes d'[[Relation d'équivalence|équivalence]] pour la [[Congruence sur les entiers|congruence modulo ''n'']]. Il est isomorphe au groupe des ''n''-èmes de tour d'axe donné. On utilisera en particulier {{math|''C''<sub>3</sub>}} pour pivoter un coin du cube, et {{math|''C''<sub>2</sub>}} pour pivoter une arête. On note <math>C_k^n=(C_k)^n</math> à savoir <math>\underbrace{C_k \times C_k \times ... \times C_k}_{n \ fois} </math>.
* <math>\mathfrak{S}_n</math> est le [[groupe symétrique]] d'ordre ''n''. Ses éléments sont les permutations de ''n'' objets. Parmi ces permutations, celle de deux objets s'appelle [[Permutation#Permutations particulières|transposition]]. On utilisera en particulier <math>\mathfrak{S}_8</math> pour permuter les coins du cube, et <math>\mathfrak{S}_{12}</math> pour permuter ses arêtes. La composition des permutations se lit de droite à gauche.
* <math>\varepsilon \,</math> désigne la [[signature d'une permutation]] de <math>\mathfrak{S}_n \,</math>.
* Pour toute permutation ''s'' élément de <math>\mathfrak{S}_n</math>, on note ''P''(''s'') l'automorphisme défini par : <math>P(s) : \begin{matrix}C_k^n & \rightarrow & C_k^n \\(x_1,x_2,...x_n) & \mapsto & (x_{s^{-1}(1)},x_{s^{-1}(2)},...x_{s^{-1}(n)})\end{matrix}</math>. ''P''(''s'') permute les composantes <math>(x_1,x_2,...x_n)</math>. ''s'' étant une [[bijection]], on remarque que la somme des composantes est invariante : <math>\sum_{i=1}^n x_i = \sum_{i=1}^n x_{s^{-1}(i)}</math>. ''P'' est un morphisme du groupe <math>\mathfrak{S}_n</math> dans le groupe des automorphismes de <math>C_k^n</math>.
* <math>\rtimes</math> est le symbole d'un [[produit semi-direct#Produit semi-direct interne|produit semi-direct interne]], et <math> \rtimes_P \,</math> celui d'un [[produit semi-direct#Produit semi-direct externe|produit semi-direct externe]] induit par ''P''.
* Les rotations d'un quart de tour, dans le sens des aiguilles d'une montre (sens direct par rapport à un axe entrant dans le cube), sont appelées <math>R \,</math>, <math>U \,</math>, <math>L \,</math>, <math>F \,</math>, <math>B \,</math>, <math>D \,</math> pour les faces droite (right), haut (up), gauche (left), avant (front), arrière (back) et bas (down)<ref name=Singmaster3>{{harv|Singmaster|p=4}}</ref>{{,}}<ref>{{harv|Warusfel|p=33}}</ref>.
* On identifie les sommets par 3 coordonnées et les arêtes par 2 ; par exemple FUL est le sommet de face en haut à gauche et BR est l'arête arrière droite<ref name=Singmaster3/>.

== Décomposition des mouvements du cube ==
=== Isomorphisme entre ''H'' et <math>(C_3^8 \rtimes_P \, \mathfrak{S}_8) \times (C_2^{12} \rtimes_P \, \mathfrak{S}_{12})</math> ===
==== Factorisation sommets-arêtes ====

Un élément de ''H'' se décompose naturellement entre son action sur les coins et son action sur les arêtes, ces deux actions étant indépendantes. On introduit les deux sous-groupes ''H''<sub>co</sub> et ''H''<sub>ar</sub> constitués respectivement des mouvements agissant sur les coins et laissant [[invariant]]e chaque arête, et des mouvements agissant sur les arêtes et laissant invariant chaque coin. ''H'' est isomorphe au [[Produit direct (groupes)|produit direct]] des groupes <math>H_\text{co}\times H_\text{ar}</math><ref name=Colmez2/>.

On va maintenant montrer que <math>H_\text{co}</math> est isomorphe au [[produit semi-direct]] <math>C_3^8 \rtimes_P \mathfrak{S}_8</math> et <math>H_\text{ar}</math> au produit semi-direct <math>C_2^{12} \rtimes_P \mathfrak{S}_{12}</math>.

L'isomorphisme entre <math>H_\text{co}</math> et <math>C_3^8 \rtimes_P \mathfrak{S}_8</math> exprime le fait qu'une action sur les coins se décompose en une permutation des 8 coins (élément de <math>\mathfrak{S}_8</math>), et pour chaque coin, d'une rotation possible de 0, 1 ou 2 tiers de tour (pour chaque coin, le groupe de ces rotations est isomorphe à {{math|''C''<sub>3</sub>}})<ref name=Colmez3>{{Harv|Colmez|p=3}}</ref>.

De même, l'isomorphisme entre <math>H_\text{ar}</math> et <math>C_2^{12} \rtimes_P \, \mathfrak{S}_{12}</math> exprime le fait qu'une action sur les arêtes se décompose en une permutation des 12 arêtes, et pour chaque arête, d'une rotation possible de 0 ou 1 demi-tour.

==== Permutation des arêtes et des sommets ====

On numérote les sommets du Rubik's cube de 1 à 8 dans cet ordre : FUR, BUR, BUL, FUL, FDR, BDR, BDL, FDL. Les arêtes vont de 1 à 12 : UL, BL, DL, FL, FU, BU, BD, FD, UR, BR, DR, FR.

On définit alors deux morphismes surjectifs de groupes <math>\rho : H_\text{co} \rightarrow \mathfrak{S}_8</math> et <math>\sigma : H_\text{ar} \rightarrow \mathfrak{S}_{12}</math> qui extraient d'un élément de ''H'' les permutations des sommets et des arêtes correspondantes, sans tenir compte de leur orientation<ref name=Colmez2>{{Harv|Colmez|p=2}}</ref>.

Par exemple, en utilisant la notation des [[permutation circulaire|cycles]], on a <math>\rho(F) = (1,5,8,4)</math> et <math>\rho(U) = (4,3,2,1)</math>, d'où <math>\rho(U \circ F)=(1,5,8,3,2)</math>.

==== Orientation des arêtes et des sommets ====

Posons <math>\text{Rot}_\text{co} = \ker(\rho)</math> et <math>\text{Rot}_\text{ar} = \ker(\sigma)</math>. Ce sont deux [[Sous-groupe normal|sous-groupes distingués]] de ''H''. Leurs éléments sont les rotations des coins (identité ou tiers de tour, dans un sens ou dans l'autre) et des arêtes (identité ou demi-tour). Seule l'orientation des cubes change, pas leur position. Ces deux groupes vont permettre de décomposer ''H''<sub>co</sub> et ''H''<sub>ar</sub> en les [[Produit semi-direct|produits semi-directs]] annoncés.

Changer un cube de position (par exemple mettre FUL en FUR) est une opération ambiguë : dans la position d'arrivée, il y a 3 orientations possibles pour les coins, 2 pour les arêtes. Parmi tous ces mouvements possibles, on en choisit formant deux sous-groupes, Perm<sub>co</sub> et Perm<sub>ar</sub>, [[Complément d'un sous-groupe|complémentaires]] de Rot<sub>co</sub> et Rot<sub>ar</sub>.

Perm<sub>co</sub> est le groupe des mouvements des coins à orientation constante, isomorphe à <math>\mathfrak{S}_8</math>. En identifiant Perm<sub>co</sub> à <math>\mathfrak{S}_8</math>, on peut voir <math>\rho</math> comme un morphisme de ''H'' dans Perm<sub>co</sub>. Pour tout ''g'' de <math>H_\text{co}</math>, <math>g\rho(g)^{-1}</math> est alors un élément de ''H'' qui laisse en place chaque coin, mais en les pivotant sur place. C'est donc un élément <math>v(g)</math> de <math>\text{Rot}_\text{co}</math>. On a donc la décomposition <math>g = v(g)\rho(g)</math>. Cette décomposition est unique du fait que <math>\text{Rot}_\text{co} \cap \text{Perm}_\text{co} = \{\text{Id}\}</math>. <math>\rho(g)</math> indique où les coins sont déplacés, et <math>v(g)</math> comment ils sont pivotés. La rotation de chaque sommet est donnée par un élément de <math>C_3</math> indiquant de combien de tiers de tour le sommet est pivoté, de sorte que <math>\text{Rot}_\text{co}</math> est isomorphe à <math>C_3^8</math>. On peut représenter <math>v(g)</math> par un élément <math>(v_j)_{1\leq j \leq 8}</math> de <math>C_3^8</math>, la ''j''-ème composante indiquant la rotation que subira le sommet qui arrivera en ''j'' par le déplacement dû à ''g''.

On peut dessiner le choix de Perm<sub>co</sub> en plaçant un marqueur <math>\star</math> sur chaque coin du Rubik's cube. Un mouvement d'orientation constante est celui qui amène la face marquée de la position de départ sur la face marquée de la position d'arrivée<ref name=Colmez3/>. On peut prendre par exemple le marquage suivant :

::[[Image:Rubik's cube marqueurs sommets.svg|297px]]

pour lequel un mouvement élément de Perm<sub>co</sub> laisse la réunion des faces blanc-jaune globalement invariante. On note ci-dessous par les valeurs 0, 1 ou 2 la valeur à attribuer à la rotation d'un coin en fonction de la place qu'occuperait sa face marquée par une étoile :

::[[Image:Rubik's cube orientation sommets.svg|297px]]

Si ''g'' et ''h'' sont éléments de <math>H_\text{co}</math> avec :
:<math>g = v(g) \circ \rho(g)</math>
:<math>h = v(h) \circ \rho(h)</math>
alors, on a :
:<math>hg = v(h)\rho(h)v(g)\rho(g) = v(h)\rho(h)v(g)\rho(h)^{-1}\rho(h)\rho(g)</math>
<math>\rho(h)\rho(g) = \rho(hg)</math> est élément de <math>\text{Perm}_\text{co}</math> et <math>v(h)\rho(h)v(g)\rho(h)^{-1} = v(hg)</math> est élément de <math>\text{Rot}_\text{co}</math>. On n'a pas en géneral <math>v(hg)=v(h)v(g)</math> ; ''v'' n'est donc pas un morphisme de groupe, ce qui empêche d'avoir un produit direct entre Rot<sub>co</sub> et Perm<sub>co</sub>. Mais la relation <math>v(hg)=v(h)\rho(h)v(g)\rho(h)^{-1}</math> est caractéristique d'un [[produit semi-direct]]. Ainsi, <math>H_\text{co} = \text{Rot}_\text{co} \rtimes \text{Perm}_\text{co}</math>.

Si <math>v(g)</math> a pour composantes <math>(v_j)_{1 \leq j \leq 8}</math>, alors <math>\rho(h)v(g)\rho(h)^{-1}</math> a pour composantes <math>(v_{\rho(h)^{-1}(j)})_{1 \leq j \leq 8} = P(\rho(h))((v_j)_{1 \leq j \leq 8})</math>. Le remplacement de <math>\text{Rot}_\text{co}</math> par son groupe isomorphe <math>C_3^8</math> transfère le [[Produit semi-direct#Produit semi-direct interne|produit semi-direct interne]] <math>\text{Rot}_\text{co} \rtimes \text{Perm}_\text{co}</math> en le [[Produit semi-direct#Produit semi-direct externe|produit semi-direct externe]] <math>C_3^8 \rtimes_P \mathfrak{S}_8</math>.

On remarque par ailleurs que la somme des composantes de <math>v(g)</math> est égale à celle de <math>\rho(h)v(g)\rho(h)^{-1}</math>. Il en résulte que la somme des composantes de <math>v(hg)</math> est égale à la somme de celles de <math>v(h)</math> et de celles de <math>v(g)</math>. Ainsi, ''v'' n'est pas un morphisme, mais la somme des composantes (appelée rotation totale des coins) en est un, à valeurs dans <math>C_3</math><ref name=Colmez3/>.

On opère de même sur les arêtes en choisissant un marquage privilégié de chacune d'elles, ce qui permet de définir leur orientation <math>w \, : \, H \rightarrow C_2^{12}</math> par le nombre de rotations de 180° permettant de rétablir l'orientation initiale. On peut prendre par exemple : 
::[[Image:Rubik's cube marqueurs arêtes.svg|297px]]

Comme pour ''v'', ''w'' n'est pas un morphisme de groupe, et on a seulement une structure de produit semi-direct <math>H_\text{ar} = \text{Rot}_\text{ar} \rtimes \text{Perm}_\text{ar} \simeq C_2^{12} \rtimes_P \mathfrak{S}_{12}</math>, mais la somme de des composantes de ''w'' (appelée rotation totale des arêtes) est un morphisme, à valeurs dans <math>C_2</math>.

=== Théorème fondamental : caractérisation des mouvements légaux ===
On rappelle que ''H'' est le groupe des actions sur le cube de Rubik démontable, et ''G'' le groupe des actions sur le cube non démontable (en effectuant des mouvements des faces selon les règles).
Pour tout ''g'' élément de ''H'', soit ''vrws'' la décomposition de ''g'' en le produit d'un élément ''v'' de <math>C_3^8</math> (pivotements des coins), ''r'' élément de <math>\mathfrak S_8</math> (permutation des coins), ''w'' élément de <math>C_2^{12}</math> (pivotements des arêtes), ''s'' élément de <math>\mathfrak S_{12}</math> (permutation des arêtes). Alors<ref name=Colmez4>{{Harv|Colmez|p=4}}</ref>{{,}}<ref>{{harv|Warusfel|p=152-160}}</ref> :

:<math>g \in G \Longleftrightarrow \left\{ \begin{matrix} a) & \varepsilon(r)\varepsilon(s)& = & 1 \\ b) & \sum_{i=1}^{8} v_i & \equiv & 0 \;{\rm mod}\; 3 \\ c) & \sum_{i=1}^{12} w_i & \equiv & 0 \;{\rm mod}\; 2 \end{matrix} \right.</math>

Autrement dit, ''G'' est le noyau du morphisme <math>\Phi</math> de ''H'' dans <math>\{\pm 1\} \times C_3 \times C_2</math>, qui, à tout ''g'' de ''H'' associe le triplet <math>\Phi(g) = (\varepsilon(r)\varepsilon(s), \sum_{i=1}^{8} v_i, \sum_{i=1}^{12} w_i)</math>.

Le a) exprime par exemple que, selon les règles du jeu, il est impossible de transposer seulement deux sommets, ou bien seulement deux arêtes. Selon le b), il est impossible de pivoter un coin seul. Deux coins seuls peuvent être pivotés mais en sens inverse l'un de l'autre. Il dit aussi que l'orientation d'un coin est défini de manière unique par l'orientation des 7 autres coins. Le c) exprime qu'il est impossible de pivoter une arête seule. Le pivotement des arêtes s'opère nécessairement par paire. L'orientation d'une arête est définie de manière unique par l'orientation des 11 autres.

Le sens direct de la démonstration consiste à montrer que tout mouvement selon les règles vérifient ces conditions.
Le sens réciproque consiste à prouver que, si on se donne une configuration du Rubik's cube vérifiant ces conditions, alors il existe une suite de mouvements selon les règles qui conduit à cette configuration (ou inversement, qui fait passer de cette configuration à la configuration initiale). C'est la description d'un algorithme de résolution du Rubik's cube<ref name=Colmez5>{{harv|Colmez|p=5}}</ref>.

==== Démonstration de la partie directe ====
Il s'agit de montrer que ''G'' est inclus dans <math>\ker(\Phi)</math>. Pour cela, <math>\Phi</math> étant un morphisme, il suffit de le prouver pour un système générateur de ''G'', à savoir les six rotations de chacune des faces<ref name=Colmez5/>.

En ce qui concerne ε(ρ(''g''))ε(σ(''g'')), une rotation d'une face est constitué d'un 4-cycle sur les coins et d'un 4-cycle sur les arêtes. Chaque cycle a pour signature -1 et leur produit fait bien 1.

En ce qui concerne <math>\sum_{i=1}^8 v_i \;{\rm mod}\; 3</math>, observons comment chaque rotation de face  fait pivoter chacun des coins, (en utilisant le codage 0, 1 et 2 des trois faces de chaque coin donné dans le paragraphe précédent) :
:{| border="1"
! <math>g \,</math> !! <math>v(g)</math>
|-
|<math>F \,</math>
|(2,0,0,1,1,0,0,2)
|-
|<math>U \,</math>
|(0,0,0,0,0,0,0,0)
|-
|<math>D \,</math>
|(0,0,0,0,0,0,0,0)
|-
|<math>B \,</math>
|(0,1,2,0,0,2,1,0)
|-
|<math>R \,</math>
|(1,2,0,0,2,1,0,0)
|-
|<math>L \,</math>
|(0,0,1,2,0,0,2,1)
|}
On constate bien que, pour chaque face, la somme des composantes de <math>v(g)</math> est nulle modulo 3.

On peut opèrer une vérification analogue sur les arêtes pour montrer que <math>\sum_{i=1}^{12} w_i</math> est nulle modulo 2. Mais il est plus rapide de remarquer que la rotation d'une face induit sur les 2 × 12 = 24 facettes carrées des 12 arêtes une permutation qui est le produit de deux 4-cycles (l'un des 4-cycles permute circulairement 4 facettes, l'autre 4-cycle permute circulairement 4 autres facettes, adjacentes aux 4 premières). Il en résulte que la signature de la permutation des 24 facettes vaut 1, et qu'il en est de même par composition pour un mouvement quelconque du Rubik's cube. Or cette signature n'est autre que <math>(-1)^{\sum w_i}</math>. Il en résulte que <math>\sum_{i=1}^{12} w_i</math> est nulle modulo 2<ref name=Colmez5/>.

==== Démonstration de la réciproque ====
Il s'agit de montrer que <math>\ker(\Phi)</math> est inclus dans ''G''. Pour cela, partant d'une configuration ''g'' appartenant à <math>\ker(\Phi)</math>, on lui applique une suite ''S'' de rotations des faces appartenant à ''G'' de façon que <math>S \circ g = {\rm Id}</math>. Cela prouve que ''g'' est le symétrique de ''S'', donc est élément de ''G''<ref name=Colmez5/>.

Les mouvements des faces à effectuer seront donnés ici par une suite de lettres : majuscules F, R, L, B, U, D pour une rotation dans le sens des aiguilles d'une montre, minuscules f, r, l, b, u, d pour le sens inverse. La composition des mouvements se fera dans ce paragraphe dans le sens de la lecture du mot ainsi formé, i.e. de gauche à droite. Ainsi, le mouvement "FUl" est constitué d'une rotation dans le sens des aiguilles d'une montre de la face F, suivie de la face U, et on termine par une rotation en sens inverse de la face L. La suite ''S'' est construite en mettant d'abord en place les arêtes, puis les coins, puis en pivotant convenablement les arêtes, puis les coins.

'''Mise en place des arêtes''' : pour tout couple d'arêtes, il existe un élément de ''G'' qui transpose ces deux arêtes, en laissant les autres arêtes en place (à pivotement près)<ref name=Colmez6>{{harv|Colmez|p=6}}</ref>. Par exemple "uFULulf" transpose deux arêtes de la face U<ref>{{harv|Warusfel|p=186}}</ref>. Comme les transpositions engendrent le groupe symétrique, cela prouve qu'il existe un élément de ''G'' qui dispose les arêtes à leur place.

'''Mise en place des coins''' : Compte tenu de la condition de parité a) sur la signature des permutations des arêtes et des coins, si les arêtes sont en place, cela signifie que les coins sont permutés par une permutation paire. Or ces permutations sont engendrées par les 3-cycles (permutation circulaire de trois coins). Pour mettre les coins en place par un mouvement élément de ''G'', il suffit donc de montrer que, pour tout triplet de coins, il existe un élément de ''G'' qui permute ces trois coins tout en laissant les autres coins et les arêtes à leur place. C'est effectivement le cas. Par exemple, le mouvement "LurUluRU" permute trois coins de la face U tout en laissant tous les autres cubes à leur place, sans modifier aucun autre cube<ref>{{harv|Warusfel|p=182}}</ref>.

'''Pivotement des arêtes''' : Compte tenu de la condition c) sur le pivotement des arêtes, on peut pivoter convenablement les arêtes en opérant successivement sur deux arêtes à la fois. Pour tout couple d'arêtes, il existe un élément de ''G'' qui se borne à pivoter deux arêtes<ref name=Colmez6/>. Par exemple, le mouvement "BddbbdBDBddflbLF" pivote deux arêtes adjacentes de la face D sans modifier aucun autre cube<ref>{{harv|Warusfel|p=146}}. Ce mouvement a été découvert par {{Lien|langue=en|Morwen Thistlethwaite}}</ref>.

'''Pivotement des coins''' : Compte tenu de la condition b) sur le pivotement des coins, on peut pivoter convenablement les coins en opérant successivement sur deux coins à la fois, les rotations étant de sens opposé sur ces deux coins. Pour tout couple de coins, il existe un élément de ''G'' satisfaisant ces conditions<ref name=Colmez7>{{harv|Colmez|p=7}}</ref>. Par exemple, le mouvement "uBULBlFLblubUf" pivote en sens inverse deux coins de la face U<ref>{{harv|Warusfel|p=184}}</ref>.

Une fois ces opérations terminées, le cube est remis en place et on a prouvé que la configuration initiale ''g'' est bien élément de ''G''.

=== Calcul du cardinal du groupe des mouvements du Rubik's Cube ===
On rappelle qu'on a introduit un morphisme <math>\Phi</math> de ''H'' dans <math>\{\pm 1\} \times C_3 \times C_2</math>, qui, à une configuration ''g'' du cube démontable associe le triplet constitué du produit des signatures des permutations sur les coins et les arêtes, la rotation totale des coins et la rotation totale des arêtes. Le noyau de <math>\Phi</math> est le groupe ''G'' des mouvements du Rubik's cube.

Ce morphisme est [[Surjection|surjectif]] car, pour tout élément de <math>\{\pm 1\} \times C_3 \times C_2</math>, on peut trouver une configuration ''g'' de ''H'' antécédent par <math>\Phi</math> de cet élément. Il suffit pour cela de pivoter un coin et une arête de façon adéquate et éventuellement de permuter deux coins (on rappelle que, dans ''H'', tous les mouvements sont possibles). Comme <math>\{\pm 1\} \times C_3 \times C_2</math> est de cardinal 12, il en résulte que ''G'' est un sous-groupe de ''H'' d'[[indice d'un sous-groupe|indice]] 12, les classes de ''G'' étant les ''gG'' avec ''g'' parcourant dans ''H'' un sous-ensemble de 12 représentants d'antécédents par <math>\Phi</math> des 12 éléments de <math>\{\pm 1\} \times C_3 \times C_2</math>.

Par conséquent, le cardinal de ''G'' est le douzième de celui de ''H''<ref name=Colmez2/>. (C'est une variante du [[Théorème de Lagrange (algèbre)|théorème de Lagrange]] ou de la [[Indice d'un sous-groupe#Formule des indices|formule des indices]]). Or le cardinal de ''H'' est <math> |H| = 8! \times 3^8 \times 12! \times 2^{12}</math> (produit du nombre de permutations des coins par le nombre de pivotement des coins par le nombre des permutations des arêtes par le nombre de pivotement des arêtes), donc celui de ''G'' est :
:<math>|G|= \frac{|H|}{12} = 2^{27} \times 3^{14} \times 5^3 \times 7^2 \times 11 = 43\ 252\ 003\ 274\ 489\ 856\ 000 \approx 43 \times 10^{18}</math>
soit environ {{nombre|43|milliards}} de milliards de combinaisons.

On peut aussi dire qu'il y a <math>2^{11}</math> pivotements d'arêtes possibles (l'orientation de la dernière arête étant alors imposée par la condition c)), <math>3^7</math> pivotements de coins possibles (l'orientation du dernier coin étant imposé par la condition b)), <math>8!</math> placements possibles des huit sommets, mais seulement <math>\frac{12!}{2}</math> placements possibles des douze arêtes en raison de la condition de parité donnée par la condition a). Le total <math>2^{11} \times 3^7 \times 8! \times \frac{12!}{2}</math> redonne le résultat précédent<ref>http://ronan.terpereau.perso.math.cnrs.fr/Projet-L3/analyse_cube_hongrois.pdf, Proposition 3</ref>{{,}}<ref>{{harv|Warusfel|p=161}}</ref>.

== Générateurs et relations ==
=== Propriétés particulières ===
Comme précédemment, on donne les mouvements des faces à effectuer par une suite de lettres, la composition s'effectuant ici de gauche à droite : majuscules F, R, L, B, U, D pour une rotation dans le sens des aiguilles d'une montre, prime F', R', L', B', U', D' pour le sens inverse.
* On peut engendrer le groupe ''G'' en autorisant seulement les rotations de cinq faces données. En effet, le mouvement "R'LF'2B'2R'LD'R'LF'2B'2R'L", dû à Dave Benson, permet de tourner la face supérieure en utilisant uniquement les autres faces<ref>{{harv|Warusfel|p=142}}</ref>.
* L'ordre maximal d'un élément de ''G'' est 1260. Il est obtenu par exemple par le mouvement "R'B'2DU'D"<ref>{{harv|Warusfel|p=145}}</ref>.
* Le groupe ''G'' peut être engendré par deux mouvements seulement, par exemple "L'2B'R'DL" et "U'F'R'U'RUF"<ref>{{harv|Warusfel|p=144}}</ref>.

{{travail inédit|ce qui suit peut contenir|date=juillet 2019}}
{{section à sourcer|date=novembre 2015}}

=== Présentation du problème ===
{{voir|groupe libre}}

D’après les notations utilisées pour étudier le Cube, le problème peut se présenter sous deux formes. On peut le traiter en utilisant des notations totalement [[mathématiques]] ou alors le traiter sous forme de mots puisque chacune des lettres R,U etc. correspond à une permutation (voir numérotation du Cube). Il existe donc une fonction surjective de l’ensemble des mots sur X = {R,L,U,D,F,B} vers l’ensemble des permutations du Cube.
Pour une permutation, la longueur est définie comme étant, en partant du Cube résolu, le nombre minimum de mouvement (= générateurs considérés) à effectuer pour obtenir la permutation.

==== Première application : nombre minimum de mouvements ====

À partir de ces mouvements, on peut construire un arbre où chaque nœud représente une position du cube (chaque position correspond à une permutation appliquée au cube résolu). En partant du cube résolu, on peut construire une suite (<math> S_n </math>) qui, à chaque étape, compte le nombre de branches finales de l'arbre. Ce nombre est un [[Majorant ou minorant|majorant]] de la quantité de positions d'un cube réalisable avec n mouvements de base. Plusieurs branches peuvent éventuellement aboutir à la même position, on va chercher à compter les branches en minimisant les positions identiques.
On a <math>S_0 = 1, S_1 = 18 </math> (6 faces ayant 3 mouvements possibles, la double rotation d'une face compte comme un seul mouvement de la face),  <math>S_2 = 15*18</math> (le deuxième mouvement ne peut pas se faire sur la face précédemment tournée). Et ensuite pour tout n, on a 
<math> S_n = 12 S_{n-1} + 18 S_{n-2} </math>. 
Explication : remarquons qu'il n'y a que deux possibilités: soit on enchaine des mouvements de faces adjacentes en nombre quelconque, soit on enchaine au maximum deux mouvements de faces opposées (avant de refaire une face adjacente). Concernant les faces adjacentes successives : pour chacune des <math> S_{n-1} </math> positions de l'étape n-1, on peut faire un des 3 mouvements de chacune des 4 faces adjacentes (à la dernière face tournée à l'étape n-1), soit 4*3=12 mouvements possibles. Concernant les faces opposées : pour cela, on revient à l'une des <math> S_{n-2} </math> positions de l'étape d'avant (n-2) et on enchaine deux mouvements de faces opposés, ce qui conduit à l'étape n. Ces deux mouvements donnent lieu à 3*3=9  'résultats' possibles (on ne compte pas les possibilités de mouvements, mais seulement les différents résultats, et l'ordre d'exécution n'a pas d'importance). Et comme il y a deux couples de faces opposées adjacentes (à la face tournée à l'étape n-2), on obtient un total de 18 possibilités qui s'ajoutent pour arriver à l'étape n.  

On peut ensuite calculer les valeurs de la suite <math> (S_n) </math>. Comme  <math>S_{17}\simeq2.034\times10^{19}</math>  (qui est un majorant du nombre maximal de positions atteignables en 17 mouvements) est inférieur à  <math>|G|\simeq4.3\times10^{19}</math> (qui est le nombre positions du cube), on en déduit que 17 mouvements ne suffisent pas à produire toutes les positions du cube. Cela prouve que certaines positions du cube ne peuvent pas être atteintes en moins de 18 mouvements (remarque : <math>S_{18}\simeq2.716\times10^{20}>|G|</math>, donc on peut pas dire mieux avec ce raisonnement). 

Il a été prouvé par des arguments plus techniques que certaines positions nécessitent 20 mouvements. (Voir [[:en:Optimal solutions for Rubik's Cube|Optimal solutions for Rubik's Cube]])

=== Générateurs et relations : présentation d’un groupe ===

Soit ''X'' un [[ensemble fini]] avec ''n'' = card ''X''. Le [[groupe libre]] sur les générateurs éléments de <math>X</math> , noté <math> F_n </math>  est le groupe des mots réduits de <math>X</math>.
  
Soit ''Y'' un groupe de mots réduits sur ''X''. Soit ''R'' le plus petit sous groupe normal de <math>F_n</math> contenant Y''.'' ''R'' constitue l’ensemble des relations de <math>F_n</math>. Le quotient ''F<sub>n</sub>''/''R'' est un groupe ; c’est le plus grand groupe qui satisfait ces relations. On dit qu'il a pour générateurs l’ensemble ''X'' et pour relations l'ensemble ''Y''. Un ensemble de générateurs et de relations est appelé une [[présentation d'un groupe|présentation]].

En termes de notation, un élément ''r'' de ''R'' est noté sous forme d’une équation de la forme {{math|1=''r'' = 1}}.

Exemple : le [[groupe cyclique]] d’ordre ''n'' possède un générateur ''x'' et une relation <math> x^n = 1 </math> donc on a <math> X=\{x\} </math> et <math> R=\{(x^n)^k | k \in Z\} \subset F_1={x^k | k \in Z}</math>. <math> C_n </math> admet donc comme présentation : <math> C_n= \{x | x^n = 1\} </math>
Le [[groupe diédral]] d’ordre ''n'' a pour présentation 
<math> D_n = \{a,b | a^n=1, b^2=1, aba=b\} </math>

=== Produit semi-direct ===
==== Recherche d’une présentation de {{Math|§=''C''{{indexp|m|n}} &#8906; &#x1d57e;{{indexp||n+1}}}} ====

Il faut d’abord chercher les [[Représentations du groupe symétrique|représentations des groupes symétriques]] et des groupes cycliques.
Pour le groupe symétrique d’ordre n+1, on a: 
<math> \mathfrak{S}_{n+1} = <a_1,...,a_n | (a_ia_j)^{m_{i,j}}=1 , 1\le i,j\le \, n> </math>avec <math>m_{i,j}= \left\{ \begin{matrix} 3 & \mbox{si } j=i\pm \, 1 \\ 2 & \mbox{si } |i-j|>1 \\ 1 & \mbox{si } i=j \end{matrix}\right. </math>
Dans le cas où n=4, la matrice est : <math> \begin{pmatrix} 1 & 3 & 2 & 2 \\ 3 & 1 & 3 & 2 \\ 2 & 3 & 1 & 3 \\ 2 & 2 & 3 & 1 \end{pmatrix} </math>

Pour le [[produit cartésien]] du groupe cyclique d'ordre m, on a : 
<math> C_m^n = <h_1,...,h_n) | h_i^m = 1, h_i*h_j = h_j*h_i , 1\le i,j \le n> </math> 

Pour le groupe symétrique, on peut associer à chaque transposition (de deux indices consécutifs)  <math> a_i </math> une [[matrice de permutation]] de taille (n+1)*(n+1) 
<math> s_i = \begin{pmatrix} 1 & 0 & \cdots & \cdots & \cdots & \cdots & \cdots & 0 \\ \vdots & \ddots &  &  &  & & & \vdots \\ \vdots & & 1 & & &  &  & \vdots \\ \vdots & & & 0 & 1 &  & & \vdots \\ \vdots &  & & 1 & 0 &  & & \vdots  \\ \vdots &  & &  & & 1 &  & \vdots \\ \vdots & &  &  &  & & \ddots & \vdots \\ 0 & \cdots  & \cdots & \cdots & \cdots & \cdots & \cdots & 1 \end{pmatrix} </math> 
autrement dit <math> s_i = I-E_{ii}-E_{i+1,i+1}+E_{i,i+1}+E_{i+1,i}  </math>

On peut aussi identifier <math> C_m^n </math> avec le produit cartésien <math> \{(h_1(x_1),...,h_n(x_n)) | x_i \in C_m\} </math> 
où <math> h_i(t) = I-E_{ii}-E_{i+1,i+1}+tE{ii}+t^{-1}E_{i+1,i+1} </math> 

On a alors les relations suivantes entre les <math> s_i \mbox{et les } h_j(t) </math>
<math> \begin{matrix} s_ih_j(t)s_i^{-1} = h_j(t), |i-j|>1  \\ s_ih_i(t)s_i^{-1} = h_i(t)^{-1}, i=j \\ s_{j\pm 1}h_j(t)s_{j\pm 1}^{-1} = h_i(t)h_{j\pm 1}, i=j\pm 1  \end{matrix} </math>

On peut alors démontrer la propriété suivante : 
<math> (C_m^n \rtimes_P \, \mathfrak{S}_{n+1}) = \left\langle a_1,...,a_n,h_1...,h_n | \left\{\begin{matrix} {(a_ia_j)}^{m_{ij} } =1  \\  h_i^m = 1, h_ih_j = h_jh_i  \\  a_ih_ja_i^{-1}=h_j, |i-j|>1  \\  a_ih_ia_i^{-1}=h_i^{-1}  \\  a_{j \pm 1} h_ja_{j \pm 1} = h_ih_{j \pm 1} \end{matrix} \right. \right\rangle </math> 
 
Démonstration : si on appelle <math> P </math> la représentation présentée ci-dessus. Le but de la démonstration est bien sûr de montrer <math> (C_m^n \rtimes_P \, \mathfrak{S}_{n+1}) \cong P </math>. Pour cela on considère le morphisme <math> F : P \mapsto (C_m^n \rtimes_P \, \mathfrak{S}_{n+1}) </math> qui associe les générateurs de <math>  P \,</math>  avec les générateurs de <math> (C_m^n \rtimes_P \, \mathfrak{S}_{n+1})</math>. Par définition de l'application, <math>  F \, </math> est surjective. Pour prouver l'injectivité, on note <math> K=ker(F)</math>. En notant <math> card(G)= |G| </math>, on a d'après le théorème de Lagrange : 
<math>|P| = |P/K||K| \ge |P/K| = |(C_m^n \rtimes_P \, \mathfrak{S}_{n+1})| =m^n(n+1)! </math>.

En considérant maintenant <math> H=\{h_1,...,h_n | h_i^m=1, h_ih_j=h_jh_i\} \subset P </math>, <math> H \, </math> est un sous groupe normal à <math> P \,</math>. En effet, chaque <math> a_i</math> renvoie un générateur de H sur un produit de générateurs de H ou sur son inverse. Comme H est un groupe, on obtient que <math> \{a_ih_ja_i^{-1} | 1 \le i,j \le n\}=H </math>. On a donc <math> H \cong C_m^n </math>.
Si <math> w=W(a_1,...,a_n,h_1,...,h_n)=1 </math> est une relation de P, le mot <math> w \,</math> écrit dans le groupe quotient <math> P/H </math> devient un mot qui ne contiendra plus que des relations du type <math> {(a_ia_j)}^{m_{ij} }=1 </math>. On peut montrer ainsi que <math> P/H \cong S_{n+1} </math> (cette partie de la démonstration sera précisée).

Ainsi, on a <math> |P/H||H|=|C_m^n||S_{n+1}| </math> ce qui montre <math> |P|=m^n(n+1)! \, </math> et ainsi <math> |K|=1 \,</math> d'où <math> K={1} \, </math>. <math> F \, </math> est donc injectif donc bijectif.

== Liens externes ==
* {{Lien web|url=https://webusers.imj-prg.fr/~pierre.colmez/rubik.pdf|titre=Le Rubik's Cube, groupe de poche|auteur=[[Pierre Colmez]]|id=Colmez}}
* {{Lien web|url=http://www.logicalpoetry.com/rubik/math_joyner.pdf|titre=Mathematics of the Rubik's cube|auteur=W. D. Joyner|année=1996}}
* {{Lien web|url=http://ronan.terpereau.perso.math.cnrs.fr/Projet-L3/analyse_cube_hongrois.pdf|titre=Une analyse du Cube Hongrois|auteur=Matthieu Barreau|année=2011|langue=fr|date=}}

== Bibliographie ==
* {{Ouvrage|auteur1=David Singmaster|titre=Notes on Rubik's cube|éditeur=Enslow Publishers|année=1981|isbn=|id=Singmaster}}
* {{article|auteur1=Edward C. Turner|auteur2=Karen F. Gold|titre=Rubik's Groups|périodique=The American Mathematical Monthly|volume=92|numéro=9|pages=617-629|doi=10.1080/00029890.1985.11971700|année=1985|url=https://maa.tandfonline.com/doi/abs/10.1080/00029890.1985.11971700|id=Turner}}
* {{Ouvrage|auteur1=André Warusfel|titre=Réussir le Rubik's cube|éditeur=[[Éditions Denoël|Denoël]]|année=1981|isbn=|id=Warusfel}}

== Notes et références ==
{{références}}

{{Portail|mathématiques|jeux}}

[[Catégorie:Algorithmique]]
[[Catégorie:Rubik's Cube]]
[[Catégorie:Théorie des groupes]]