Travaux pratiques
4. Soit G le sous-groupe de S n défini par un ensemble S 0 = {g 1 , . . . , g r } de
générateurs et soit S = S 0 ∪ {g
−1
1 , . . . , g −1
r } (on conserve les inverses, bien que le
groupe soit fini, par souci d’efficacité algorithmique). Partant de L = S ∪ {1 G }
et N = S, quels types de « mots » en les générateurs et leurs inverses obtient-on
dans L et N après exécution de la ligne suivante ?
N:={seq(seq(multperm(g,h),g=N),h=S)} minus L; L:=L union N;
Et après exécution de cette ligne deux fois de suite ? Tester avec Maple sur
S n , pour n = 3, 4, engendré par la transposition (12) et le n-cycle (1, 2, . . . , n).
Conclusion ? Écrire une procédure elements1:=proc(G) donnant la liste des éléments du groupe G, par itération de la ligne de commandes précédente autant de
fois que nécessaire. À l’aide de la commande time, comparer sur des exemples les
temps de calcul entre cette procédure naïve et la procédure elements de Maple
dont l’implémentation est passée sous silence : conclusion ?
5. Soit G(n), pour n 3, le sous-groupe de S n engendré par :
– les cycles (1, 2, 3) et (3, . . . , n) si n est impair ;
– les permutations (1, 2, 3) et (1, 2)(3, . . . , n) si n est pair.
Que dire de la parité des éléments de G(n) ? Vérifier avec la commande parity
puis observer les cardinaux. Quelle conjecture cela suggère-t-il ? La démontrer
(indication : commencer par remarquer que (1, 2, i)(1, 2, j) −1 = (1, i)(1, j) et que
S n est engendré par les transpositions de la forme (1, i) ; en déduire que le groupe
alterné A n est, pour n 3, engendré par les 3-cycles (1, 2, i), i = 3, . . . , n). Écrire
enfin une procédure A:=proc(n) définissant A n sous Maple pour tout entier
n 2.
6. On sait que le centre de S n est trivial, sauf pour n = 2 où le groupe est abélien.
En testant avec Maple (commande center), faire une conjecture pour A n et la
démontrer.
Deux groupes de permutations de cardinal 8
☞ Quelques commandes Maple utiles : sort, Matrix.
Préliminaires : on rappelle que le type d’une permutation σ ∈ S n est la liste
[1, . . . , 1, n 1 , . . . , n r ], où les n i , rangés par ordre croissant, sont les longueurs des
cycles dans la décomposition canonique en produit de cycles disjoints, avec au
préalable autant de 1 que de points fixes : la somme des éléments de la liste vaut
donc n (en analyse combinatoire, on dit qu’une telle liste est une partition de n).
7. Écrire une procédure typ:=proc(g,n) renvoyant le type de la permutation
g ∈ S n . Tester avec les éléments (1, 2, 3) et (1, 2, 3)(4, 5) de S 6 . Comment trouver
35
4. Soit G le sous-groupe de S n défini par un ensemble S 0 = {g 1 , . . . , g r } de
générateurs et soit S = S 0 ∪ {g
−1
1 , . . . , g −1
r } (on conserve les inverses, bien que le
groupe soit fini, par souci d’efficacité algorithmique). Partant de L = S ∪ {1 G }
et N = S, quels types de « mots » en les générateurs et leurs inverses obtient-on
dans L et N après exécution de la ligne suivante ?
N:={seq(seq(multperm(g,h),g=N),h=S)} minus L; L:=L union N;
Et après exécution de cette ligne deux fois de suite ? Tester avec Maple sur
S n , pour n = 3, 4, engendré par la transposition (12) et le n-cycle (1, 2, . . . , n).
Conclusion ? Écrire une procédure elements1:=proc(G) donnant la liste des éléments du groupe G, par itération de la ligne de commandes précédente autant de
fois que nécessaire. À l’aide de la commande time, comparer sur des exemples les
temps de calcul entre cette procédure naïve et la procédure elements de Maple
dont l’implémentation est passée sous silence : conclusion ?
5. Soit G(n), pour n 3, le sous-groupe de S n engendré par :
– les cycles (1, 2, 3) et (3, . . . , n) si n est impair ;
– les permutations (1, 2, 3) et (1, 2)(3, . . . , n) si n est pair.
Que dire de la parité des éléments de G(n) ? Vérifier avec la commande parity
puis observer les cardinaux. Quelle conjecture cela suggère-t-il ? La démontrer
(indication : commencer par remarquer que (1, 2, i)(1, 2, j) −1 = (1, i)(1, j) et que
S n est engendré par les transpositions de la forme (1, i) ; en déduire que le groupe
alterné A n est, pour n 3, engendré par les 3-cycles (1, 2, i), i = 3, . . . , n). Écrire
enfin une procédure A:=proc(n) définissant A n sous Maple pour tout entier
n 2.
6. On sait que le centre de S n est trivial, sauf pour n = 2 où le groupe est abélien.
En testant avec Maple (commande center), faire une conjecture pour A n et la
démontrer.
Deux groupes de permutations de cardinal 8
☞ Quelques commandes Maple utiles : sort, Matrix.
Préliminaires : on rappelle que le type d’une permutation σ ∈ S n est la liste
[1, . . . , 1, n 1 , . . . , n r ], où les n i , rangés par ordre croissant, sont les longueurs des
cycles dans la décomposition canonique en produit de cycles disjoints, avec au
préalable autant de 1 que de points fixes : la somme des éléments de la liste vaut
donc n (en analyse combinatoire, on dit qu’une telle liste est une partition de n).
7. Écrire une procédure typ:=proc(g,n) renvoyant le type de la permutation
g ∈ S n . Tester avec les éléments (1, 2, 3) et (1, 2, 3)(4, 5) de S 6 . Comment trouver
35