Travaux pratiques
commutent. Est-il distingué dans S 4 ? Lister les classes à gauche et à droite de S 4
modulo H.
Remarque. On a démontré au TR.II.B que A 4 et V 4 sont les seuls sous-groupes
distingués propres de S 4 .
7. Écrire ses propres procédures classesg:=proc(G,H) et classesd (i.e. n’utilisant pas la commande cosets) renvoyant respectivement les ensembles de classes
(G/H) g et (G/H) d (indication : on pourra se contenter de l’algorithme naïf suivant : calculer des classes jusqu’à épuiser les éléments du groupe). Tester sur les
exemples précédents. En déduire que cosets calcule bien des représentants des
classes à gauche (et non à droite comme le stipule l’aide de Maple, du moins
avec notre définition de classe à gauche).
Systèmes générateurs forts et algorithme de Schreier-Sims
Soit G un groupe de permutations de degré n ; il agit donc sur l’ensemble
{1, . . . , n}. On considère la tour de groupes
G = G 0 ⊃ G 1 ⊃ · · · ⊃ G n−1 = {Id}
où G i désigne le sous-groupe constitué des éléments g de G qui laissent fixes
(i.e. g(j) = j) les indices j i. Une liste L = (S 1 , . . . , S n−1 ), où S i est un système
de représentants des classes (à gauche) G i−1 /G i , est appelé système générateur
fort de G.
8. Construire un système générateur fort pour les sous-groupes de degré 4 suivants : {Id}, < (1234) >, A 4 et S 4 (on utilisera la commande classesg).
Soit O i = {g(i), g ∈ G i−1 } (orbite de i sous G i−1 ) ; choisissons, pour tout
j ∈ O i , un élément g i
j de G i−1 tel que g i
j (i) = j. Démontrer au papier-crayon que
S i = {g i
j , j ∈ O i } représente les classes G i−1 /G i . Il n’était donc pas nécessaire de
recourir à la commande classesg.
Enfin, calculer le produit
n−1
i=1 |S i | sur les exemples précédents ; que constatet-on ?
9. Démontrer la proposition suivante :
Proposition 1. Soit L = (S 1 , . . . , S n−1 ) un système générateur fort de G. Tout
élément g de G s’écrit de manière unique comme un produit g = σ 1 ◦ · · · ◦ σ n−1 ,
où σ i ∈ S i pour 1 i n − 1.
En déduire des procédures card1:=proc(SGF) et elements1:=proc(SGF) renvoyant respectivement le cardinal et la liste des éléments d’un groupe de permutations G donné par un système générateur fort SGF . Tester sur les exemples
précédents et vérifier avec les commandes natives de Maple.
61
commutent. Est-il distingué dans S 4 ? Lister les classes à gauche et à droite de S 4
modulo H.
Remarque. On a démontré au TR.II.B que A 4 et V 4 sont les seuls sous-groupes
distingués propres de S 4 .
7. Écrire ses propres procédures classesg:=proc(G,H) et classesd (i.e. n’utilisant pas la commande cosets) renvoyant respectivement les ensembles de classes
(G/H) g et (G/H) d (indication : on pourra se contenter de l’algorithme naïf suivant : calculer des classes jusqu’à épuiser les éléments du groupe). Tester sur les
exemples précédents. En déduire que cosets calcule bien des représentants des
classes à gauche (et non à droite comme le stipule l’aide de Maple, du moins
avec notre définition de classe à gauche).
Systèmes générateurs forts et algorithme de Schreier-Sims
Soit G un groupe de permutations de degré n ; il agit donc sur l’ensemble
{1, . . . , n}. On considère la tour de groupes
G = G 0 ⊃ G 1 ⊃ · · · ⊃ G n−1 = {Id}
où G i désigne le sous-groupe constitué des éléments g de G qui laissent fixes
(i.e. g(j) = j) les indices j i. Une liste L = (S 1 , . . . , S n−1 ), où S i est un système
de représentants des classes (à gauche) G i−1 /G i , est appelé système générateur
fort de G.
8. Construire un système générateur fort pour les sous-groupes de degré 4 suivants : {Id}, < (1234) >, A 4 et S 4 (on utilisera la commande classesg).
Soit O i = {g(i), g ∈ G i−1 } (orbite de i sous G i−1 ) ; choisissons, pour tout
j ∈ O i , un élément g i
j de G i−1 tel que g i
j (i) = j. Démontrer au papier-crayon que
S i = {g i
j , j ∈ O i } représente les classes G i−1 /G i . Il n’était donc pas nécessaire de
recourir à la commande classesg.
Enfin, calculer le produit
n−1
i=1 |S i | sur les exemples précédents ; que constatet-on ?
9. Démontrer la proposition suivante :
Proposition 1. Soit L = (S 1 , . . . , S n−1 ) un système générateur fort de G. Tout
élément g de G s’écrit de manière unique comme un produit g = σ 1 ◦ · · · ◦ σ n−1 ,
où σ i ∈ S i pour 1 i n − 1.
En déduire des procédures card1:=proc(SGF) et elements1:=proc(SGF) renvoyant respectivement le cardinal et la liste des éléments d’un groupe de permutations G donné par un système générateur fort SGF . Tester sur les exemples
précédents et vérifier avec les commandes natives de Maple.
61