Algèbre T1
10. Écrire rapidement une procédure image:=proc(g,n,i) calculant l’image de
l’entier i par une permutation g de degré n (donnée comme toujours par une liste
de cycles à supports disjoints). On pourra utiliser la conversion en une permlist
ou, au contraire, s’en passer, ce qui est préférable.
L’algorithme suivant, qui permet de tester si une permutation g appartient
au groupe G défini par un système générateur fort L = (S 1 , . . . , S n−1 ), résulte
directement de la preuve de la proposition 1 :
(a) On pose g = g.
(b) Pour i de 1 à n, on effectue les opérations suivantes : on regarde si g (i)
appartient à O i = {σ(i), σ ∈ S i } ; si c’est le cas, on note σ i l’unique élément
de S i tel que g (i) = σ i (i) et remplace g par σ
−1
i
◦ g ∈ G i ; dans le cas
contraire, g n’appartient pas à G et c’est terminé.
(c) Si tous les tests ont été positifs, alors g appartient à G et il s’écrit g =
σ 1 ◦ · · · ◦ σ n−1 .
Écrire une procédure appart:=proc(g,SGF) réalisant cet algorithme et tester sur
les exemples habituels.
11. Afin de compléter le programme d’étude prévu, il reste à expliquer comment, à
partir d’un système de générateurs, obtenir un système générateur fort de manière
efficace.
Tout d’abord, modifier la procédure appart pour qu’elle renvoie le couple
(i, g ) obtenu en sortie de l’algorithme si g ∈ G (autrement dit, g = σ 1 ◦· · ·◦σ i−1 ◦g
avec σ j ∈ S j pour j < i et g ∈ G i−1 , mais il n’existe pas σ i ∈ S i tel que
g (i) = σ i (i)) et (n, Id) si g ∈ G.
La stratégie est la suivante : si SG = {g 1 , . . . , g r } engendre le groupe, on
part du système générateur fort du groupe trivial {Id} et rajoute progressivement
les g i . Il s’agit donc de construire, à partir d’un système générateur fort L =
(S 1 , . . . , S n−1 ) d’un groupe G, un système générateur fort L = (S
1 , . . . , S
n−1 ) du
groupe G engendré par G ∪ {g}. Pour cela :
(a) On applique la procédure appart (modifiée) à g : si i = n, alors il n’y a rien
à faire ; dans le cas contraire, on rajoute g à S i puis on applique (a) avec
g = g ◦ h, pour tout h ∈ S j , 1 j i.
(b) Lorsqu’il n’y a plus rien à faire, on a obtenu un système générateur fort
pour G .
Implémenter cet algorithme (appelé algorithme de Schreier-Sims) et tester sur les
exemples habituels. On écrira une procédure récursive sgf_plus:=proc(g,SGF)
62
10. Écrire rapidement une procédure image:=proc(g,n,i) calculant l’image de
l’entier i par une permutation g de degré n (donnée comme toujours par une liste
de cycles à supports disjoints). On pourra utiliser la conversion en une permlist
ou, au contraire, s’en passer, ce qui est préférable.
L’algorithme suivant, qui permet de tester si une permutation g appartient
au groupe G défini par un système générateur fort L = (S 1 , . . . , S n−1 ), résulte
directement de la preuve de la proposition 1 :
(a) On pose g = g.
(b) Pour i de 1 à n, on effectue les opérations suivantes : on regarde si g (i)
appartient à O i = {σ(i), σ ∈ S i } ; si c’est le cas, on note σ i l’unique élément
de S i tel que g (i) = σ i (i) et remplace g par σ
−1
i
◦ g ∈ G i ; dans le cas
contraire, g n’appartient pas à G et c’est terminé.
(c) Si tous les tests ont été positifs, alors g appartient à G et il s’écrit g =
σ 1 ◦ · · · ◦ σ n−1 .
Écrire une procédure appart:=proc(g,SGF) réalisant cet algorithme et tester sur
les exemples habituels.
11. Afin de compléter le programme d’étude prévu, il reste à expliquer comment, à
partir d’un système de générateurs, obtenir un système générateur fort de manière
efficace.
Tout d’abord, modifier la procédure appart pour qu’elle renvoie le couple
(i, g ) obtenu en sortie de l’algorithme si g ∈ G (autrement dit, g = σ 1 ◦· · ·◦σ i−1 ◦g
avec σ j ∈ S j pour j < i et g ∈ G i−1 , mais il n’existe pas σ i ∈ S i tel que
g (i) = σ i (i)) et (n, Id) si g ∈ G.
La stratégie est la suivante : si SG = {g 1 , . . . , g r } engendre le groupe, on
part du système générateur fort du groupe trivial {Id} et rajoute progressivement
les g i . Il s’agit donc de construire, à partir d’un système générateur fort L =
(S 1 , . . . , S n−1 ) d’un groupe G, un système générateur fort L = (S
1 , . . . , S
n−1 ) du
groupe G engendré par G ∪ {g}. Pour cela :
(a) On applique la procédure appart (modifiée) à g : si i = n, alors il n’y a rien
à faire ; dans le cas contraire, on rajoute g à S i puis on applique (a) avec
g = g ◦ h, pour tout h ∈ S j , 1 j i.
(b) Lorsqu’il n’y a plus rien à faire, on a obtenu un système générateur fort
pour G .
Implémenter cet algorithme (appelé algorithme de Schreier-Sims) et tester sur les
exemples habituels. On écrira une procédure récursive sgf_plus:=proc(g,SGF)
62