Fan2Cube

Pour les fans de Rubik's Cube
https://fan2cube.fr/forum-fr/

Le mystérieux nombre 901083404981813616

https://fan2cube.fr/forum-fr/viewtopic.php?f=58&t=586

Page 1 sur 1

Le mystérieux nombre 901083404981813616

Publié : Ven 2/02/2024 12:56
par Morphocode
Le mystérieux nombre 901083404981813616
Ce nombre a fait coulé beaucoup d'encre ... parfois on dit que c'est le nombre d'états du Rubik's Cube !
En réalité ce sont des classes d'équivalence des états nommé les J-conjugaison classes.

Tout s'est passé vers les années 1994 ... On voulait chercher le diamètre du Rubik's Cube, mais le graphe des états
est trop gros, on voulait donc réduire ce graphe à un graphe ayant le même diamètre.
Jerry BRYAN a eu l'idée de classer les états suivant le critère nommé "J-conjugaison" où J est le groupe d'isométrie de cube.
Le graphe de J-conjugaison est 48 fois plus petit donc l'exploration du graphe est plus vite.

Le symétrie J-conjugaison
On sait que J est inclus dans S48 grâce au théorème : G goupe fini alors G est isomorphe à un sous groupe S|G|
Λ est aussi inclus dans S48
On va définir une action de J sur Λ de la façon suivante:

Λ = < pH, pB, pA, pP, pG, pD >

Λ x J -> Λ
(p,f) -> p•f = f p f-1 ; p,f ∈S48

et la relation d 'équivalence associée à '•' :
p,q ∈Λ sont équivalentes ssi : il existe f ∈J tel que fpf-1 = q
les classes de cette relation se nomment J-conjugaison-classes

La formule de Burnside donne
w = 1/|J| Σ |Ff| ; sommer sur (f ∈J)
Ff = {p ∈ Λ | fpf-1 = p}
Ff = {p ∈ Λ | fp = pf}

On calcule w en GAP :

Code : Tout sélectionner

# gap_J-rubik-burnside.txt
#         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" ;;
                
Jcjg := Sum(J,f -> Size(Centralizer(G,f))) / Size(J);;
Print("\n\n ",GG," = ", Size(G), "\n" );
Print("\n ",JJ,"-cjg = ", Jcjg, "\n" );



Image

Re: Le mystérieux nombre 901083404981813616

Publié : Sam 3/02/2024 14:36
par Morphocode
Définition : Les J-conjugaison classes (J=groupe isométrie du cube à 48 éléments)
Deux états s=e•V , V€M et t sont équivalents ssi :
il existe f∈ J tel que e•(fVf-1) = t ; e=état résolu

Les classes de cette relation se nomment les J-conjugaison classes
Voici un programme en GAP qui permet de calculer le nombre de J-conjugaison classes

Code : Tout sélectionner

# gap_J-rubik-cjg.txt
#         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" ;;
                   
Jcjg := Sum(ConjugacyClasses(J),i -> (Size(i) * Size(Centralizer(G,Representative(i)))) / Size(J));;
Print("\n\n ",GG," = ", Size(G), "\n" );
Print("\n ",JJ,"-cjg = ", Jcjg, "\n" );
   
   

Image

Re: Le mystérieux nombre 901083404981813616

Publié : Jeu 15/02/2024 11:25
par Morphocode
Voici un autre programme en GAP pour calculer le nombre de J-conjugaison-classes du Rubik's Cube.
REMARQUE : Le programme permet de calculer :
1) Le nombre de J-conjugaison-classes du Rubik's Cube.
2) Le nombre de Dep-conjugaison-classes du Rubik's Cube.
3) Le nombre de J-conjugaison-classes du Pocket.
4) Le nombre de Dep-conjugaison-classes du Pocket.

Code : Tout sélectionner

# gap_J-rubik.txt
#         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" );
   


Image
Le fuseau horaire UTC+01:00
Page 1 sur 1
Powered by phpBB® Forum Software © phpBB Limited
https://www.phpbb.com/