Confusion entre états et classe (orbite)

[Morphocode]

Si vous cherchez le nombre d'états du Pocket sur internet vous verrez peut-être le nombre 3674160 au lieu de 88179840.

Pour comprendre il faut revenir tout au début de l'histoire ....

En 1993, Jerry BRYAN écrivait un article expliquant le calcul du diamètre du Pocket (cet article est mal compris par beaucoup de gens).
Pour ce faire BRYAN a classé les états du Pocket suivant le critères nommé D-symétrie, plus précisément suivant le groupe de déplacement D du cube (qui contient 24 éléments),

deux états s , t sont dans la même classe ssi:
s ~ t ⇔ ∃f∈D tel que s•f = t
du coup les états du Pocket sont partagés en |G|/24 = 3674160 D-classes (de 24 éléments chaque une)

Ces classes forme un graphe T dont le diamètre est le même que celui du Pocket :
BRYAN a fait un programme informatique et a trouvé le diamètre de T qui valait 14 donc le diamètre du Pocket aussi,

Les distances du graphe T:

Distance D-classes
==============================
0 ==> 1
1 ==> 6
2 ==> 27
3 ==> 120
4 ==> 534
5 ==> 2256
6 ==> 8969
7 ==> 33058
8 ==> 114149
9 ==> 360508
10 ==> 930588
11 ==> 1350852
12 ==> 782536
13 ==> 90280
14 ==> 276
===========================
Total D-classes : 3674160


Comme le diamètre du Pocket c'est le diamètre du graphe d'états ===> d'où la confusions 3674160 est le nombre d'états du Pocket.


On a fait aussi un programme qui calcule directement le diamètre du Pocket et ça donne

Les distances du graphe du Pocket :

distance ==> nombre d'états
=================================
0 ==> 1
1 ==> 12
2 ==> 114
3 ==> 924
4 ==> 6539
5 ==> 39528
6 ==> 199926
7 ==> 806136
8 ==> 2761740
9 ==> 8656152
10 ==> 22334112
11 ==> 32420448
12 ==> 18780864
13 ==> 2166720
14 ==> 6624
===============================
total états: 88179840



(confusion entre état et classe)

[Morphocode]

Si vous chercher le nombre d'états du Rubik's Cube sur internet vous verrez parfois le nombre 901 083 404 981 813 616
au lieu de 43 252 003 274 489 856 000 .
En fait ceux qui proposent le nombre 901 083 404 981 813 616 comme le nombre d'états du Rubik's Cube, confondent entre "état" et "classe (=orbite)" !!
Voyons de plus près ...

Avant de parler "mathématiquement" du Rubik's Cube il faut "orienter" le Cube càd déclarer officielement qui est le Haut, qui est la Droite ....
traditionnellement on oriente le Cube ainsi:
H(aut)=b(lanc), B(as)=j(aune), A(vant)=v(ert), P(ostérieur)=k(lein), G(auche)=o(range), D(roite)=r(ouge).

La J-Symétrie

Parmi ces trois images ci-dessous lequel est l'état résolu ? et pourquoi ?



image (a)


image (b)


image (c)


l'image (b) est l'état résolu car les centres ne sont pas bougés, comme les centres de (a) et de (c) ont bougé ces images
ne présentent pas l'état résolu ! et pourtant si on tient un Rubik's Cube résolu dans la main ces 3 états jouent le même rôle ...
d'où l'idée de classer (mettre dans la même boîte) les états du Rubik's Cube suivante un certain nombre de critères .... afin que les états (a), (b), (c) soient dans la même classe, dans la même boîte.
Quelles sont les critères ?


On utilise le critère J-Symétrie , où J est le groupe des isométries du cube (ce groupe a 48 éléments),
plus précisément deux états s et t (on ignore les centres) sont dans la même classe (même boîte) ssi:
il existe un f€J tel que s•f = t (on ignore les centres)
On troue N = |G|/48 le nombre de J-classes


==> En 1994 Jerry BRYAN a proposé de classer les états suivant un autre critère nommé "J-conjugaison"
plus précisément deux états s=e•V , V€M et t sont dans la même classe (même boîte) ssi:
il existe un f€J tel que e•(f V f-1) = t , où e=état résolu
il a calculé et a trouvé 901 083 404 981 813 616 classes , chaque classe contient donc un certain nombre d'états .

Classe de Type . . . . . Nombre de J-conjugaison-classes
=============== . . . . ==============================
Identité (1) = 901 083 401 551 872 000

RotCentre±90° (3+3) = 18 432

RotCentre180° (3) = 955 514 880

RotArete180° (6) = 318 504 960

RotSommet±120° (4+4) = 629 856

------------------

SymCentrale (1) = 955 514 880

SymRot±90° (3+3) = 55 296

SymPlan (3) = 1 146 617 856

SymArete (6) = 53 084 160

SymRot±120° (4+4) = 1 296

================================================================
48 éléments , Total = 901 083 404 981 813 616 J-conjugaison classes

Le nombre 901 083 404 981 813 616 est donc le nombre de J-conjugaison classes et non le nombre d'états de G.

NOTE : Le but de la classification des états pour réduire le graphe du Rubik's Cube, en effet les classes forment un nouveau graphe T (gardant certaines propriétés du Rubik's Cube) beaucoup plus petit que le graphe du Rubik's Cube, on peut donc plus facilement l'exploiter comme la recherche du diamètre ....

¤ Rot=Rotation, Sym=Symétrie

[Morphocode]

GAP 4.4.12 ICI
https://www.gap-system.org/Releases/4.4.12.html


Voici un programme en GAP qui calcule le nombre de J-conjugaison classes
Dans la fenêtre de cmd
cd\
cd gap4r4
cd bin
gap < gap_J-rugik.txt

https://fan2cube.fr/gap_J-rubik.txt

Code : Tout sélectionner


#         5  6  7
#         4  H  8
#         3  2  1
#25 28 23|21 26 19|17 32 31|29 30 27
#38 G  36|12 A  10|34 D  40|16 P  14
#43 44 37|39 42 33|35 48 45|47 46 41
#         11 18 9
#         20 B  24
#         13 22 15

# Iso=le groupe isometrie du cube
j1 := (6, 46, 18, 26)(8, 14, 24, 12)(38, 48, 36, 32)(2, 30, 22, 42)(16, 20, 10, 4)(28, 40, 44, 34)
(5, 45, 11, 17)(7, 13, 9, 3)(21, 31, 41, 35)(43, 33, 23, 29)(1, 25, 15, 37)(47, 39, 19, 27) ;
j2 := (6, 16, 22, 14)(8, 24, 20, 4)(38, 30, 40, 46)(2, 10, 18, 12)(28, 32, 48, 44)(34, 42, 36, 26)
(5, 31, 15, 43)(7, 45, 13, 25)(21, 19, 33, 39)(1, 35, 11, 23)(47, 41, 27, 29)(3, 17, 9, 37);
Iso := Group(j1,j2) ;

# Dep=le groupe isometrie+ du cube (24) Dep = ssg de Iso
Dep := Group(  ( 1,11)( 2,18)( 3, 9)( 4,24)( 5,15)( 6,22)( 7,13)( 8,20)(10,12)
        (14,16)(17,37)(19,39)(21,33)(23,35)(25,45)(26,42)(27,47)(28,48)(29,41)
        (30,46)(31,43)(32,44)(34,36)(38,40),
      ( 1,15)( 2,22)( 3,13)( 4,20)( 5,11)( 6,18)( 7, 9)( 8,24)(10,16)(12,14)
        (17,45)(19,47)(21,41)(23,43)(25,37)(26,46)(27,39)(28,44)(29,33)(30,42)
        (31,35)(32,48)(34,40)(36,38),
      ( 1,17,19)( 2,32,10)( 3,31,33)( 4,40,42)
        ( 5,45,39)( 6,48,12)( 7,35,21)( 8,34,26)( 9,23,29)(11,25,47)(13,43,41)
        (14,22,44)(15,37,27)(16,18,28)(20,38,46)(24,36,30),
      ( 1,35,11,23)( 2,10,18,12)( 3,17, 9,37)( 4, 8,24,20)( 5,31,15,43)
        ( 6,16,22,14)( 7,45,13,25)(19,33,39,21)(26,34,42,36)(27,29,47,41)
        (28,32,48,44)(30,40,46,38)  ) ;

# Rubik=le groupe du Rubik's Cube      
pH := (2,4,6,8)(26,28,30,32) (1,3,5,7)(17,21,25,29)(19,23,27,31) ;
pB := (18,24,22,20)(42,48,46,44) (9,15,13,11)(33,45,41,37)(35,47,43,39);
pA := (2,34,18,36)(26,10,42,12) (1,35,11,23)(17,9,37,3)(19,33,39,21);
pP := (6,38,22,40)(30,14,46,16) (7,25,13,45)(29,27,41,47)(31,5,43 ,15);
pG := (4,12,20,14)(28,36,44,38) (3,39,13,27)(21,11,41,5)(23,37,43,25);
pD := (8,16,24,10)(32,40,48,34) (1,29,15,33)(17,31,45,35)(19,7,47,9);
Rubik := Group(pH,pB,pA,pP,pG,pD);

# Pocket=le groupe Pocket (= Rubik sans arêtes)
#pH :=  (1,3,5,7)(17,21,25,29)(19,23,27,31) ;
#pB :=  (9,15,13,11)(33,45,41,37)(35,47,43,39);
#pA :=  (1,35,11,23)(17,9,37,3)(19,33,39,21);
#pP :=  (7,25,13,45)(29,27,41,47)(31,5,43 ,15);
#pG :=  (3,39,13,27)(21,11,41,5)(23,37,43,25);
#pD :=  (1,29,15,33)(17,31,45,35)(19,7,47,9);
#Pocket := Group(pH,pB,pA,pP,pG,pD);

G := Rubik ;;
GG := "Rubik" ;;
J := Iso ;;
JJ := "J" ;;
 
etat := 0 ;;
Jcjg := 0 ;;

    # Les classes des sous groupes conjugaisons de J
    Cl := ConjugacyClassesSubgroups( J );;
    ptfixe := [];

   Print("\n\n No \tetat \tclasses-conjugaisons\n" );
   Print("================================================== \n" );
    # pour tout classe Cl[i], on cherche les pt fixes générés par Cl[i]
    for i  in [Length(Cl),Length(Cl)-1..1]  do

        # prendre un représentant
        H := Representative( Cl[i] );

        # les pt fixes engendrés par H
        aux := Size( Centralizer( G, H ) );

        # si Q inclus dans H,on supprime dans H les pt fixes générés par Q
        for k  in [Length(Cl),Length(Cl)-1..i+1]  do
            for Q  in Elements( Cl[k] )  do
                if IsSubgroup( Q, H )  then
                  aux := aux - ptfixe[k];   
                fi;
            od;
        od;

        # sauver les pt fixes génégrés par H
        ptfixe[i] := aux;

        # print N° classe
        Print("\n ", i, ":\t" );

        # le nbr de pt fixes (= nbr états) générés par Cl[i]
        Print( Size(Cl[i]) *  ptfixe[i], "\t" );
      etat := etat + ( Size(Cl[i]) *  ptfixe[i] );

        # le nbr de J-cjg classes générés par Cl[i]
        Print( (Size(Cl[i]) *  ptfixe[i]) /  Index(J,H), " " );
      Jcjg := Jcjg + ( (Size(Cl[i]) *  ptfixe[i] )/  Index(J,H) );
      
    od;
   Print("\n\n ",GG," = ", etat, "\n" );
   Print("\n ",JJ,"-cjg = ", Jcjg , "\n" );