Travaux pratiques
Tester cette commande avec G = D 5 et les sous-groupes K = a et L = b.
Sont-ils distingués dans D 5 ? Vérifier avec la commande isnormal. Calculer
leurs ordres (noter que pour appliquer la commande grouporder à un sousgroupe, il faut d’abord en calculer une présentation via la commande pres).
Sachant que l’ordre de x ∈ X est égal à l’ordre du sous-groupe qu’il engendre,
écrire une procédure ordre:=proc(x,G) renvoyant l’ordre d’un mot x en les
générateurs du groupe G. Tester en calculant les ordres des éléments de C 10 .
Conclusion ?
Il semble que la commande pres de Maple soit buguée (à moins que le problème n’ait été corrigé depuis...) : pres(subgrel({x=[a,a]},Cyclique(10))
donne un résultat aberrant. On évitera, autant que possible, d’utiliser par la
suite cette commande (dont on ne connaît d’ailleurs pas les algorithmes sousjacents, à la différence de grouporder, bâtie sur l’algorithme de Todd-Coxeter
que nous détaillerons plus loin).
4. La commande cosets renvoit une liste de représentants des classes modulo
un sous-groupe défini avec une commande subgrel (qui fait donc référence au
groupe dont il est issu). Tester avec L ⊂ D 5 : s’agit-il des classes à droite ou
à gauche ? Tester également avec a ⊂ S 4 . C’est a priori un choix arbitraire
historique dans la littérature sur le sujet.
Comment obtenir les éléments de G en utilisant la commande cosets ? Écrire
une fonction elements1 renvoyant, en fonction du groupe G (défini comme
toujours par une commande grelgroup), la liste de ses éléments. Tester sur
les exemples précédents (C 10 , D 5 , S 4 ).
L’algorithme de Todd-Coxeter
On se donne un groupe G défini par un ensemble X = {g 1 , . . . , g m } de générateurs vérifiant un ensemble R = {r j = 1 G } 1jk de relations. D’autre part, soit
H un sous-groupe de G engendré par Y = {h 1 , . . . , h s }. Les r j et h j sont exprimés
comme des mots en les éléments de X ∪ X −1 .
L’algorithme de Todd et Coxeter permet d’énumérer les différentes classes à
droite, i.e. les éléments de (G/H) d , en faisant agir G sur (G/H) d par translation
à doite : Hx · g = H(xg). Au final, on obtient l’indice n de H dans G, des
éléments g i ∈ G tels que (G/H) d = {Hg 1 , . . . , Hg n } (i.e. des représentants des
classes) et la description explicite du morphisme ρ : G → S((G/H) d ) = S n (après
numérotation des classes), c’est-à-dire l’expression des ρ(g i ) en tant qu’éléments
de S n .
101
Tester cette commande avec G = D 5 et les sous-groupes K = a et L = b.
Sont-ils distingués dans D 5 ? Vérifier avec la commande isnormal. Calculer
leurs ordres (noter que pour appliquer la commande grouporder à un sousgroupe, il faut d’abord en calculer une présentation via la commande pres).
Sachant que l’ordre de x ∈ X est égal à l’ordre du sous-groupe qu’il engendre,
écrire une procédure ordre:=proc(x,G) renvoyant l’ordre d’un mot x en les
générateurs du groupe G. Tester en calculant les ordres des éléments de C 10 .
Conclusion ?
Il semble que la commande pres de Maple soit buguée (à moins que le problème n’ait été corrigé depuis...) : pres(subgrel({x=[a,a]},Cyclique(10))
donne un résultat aberrant. On évitera, autant que possible, d’utiliser par la
suite cette commande (dont on ne connaît d’ailleurs pas les algorithmes sousjacents, à la différence de grouporder, bâtie sur l’algorithme de Todd-Coxeter
que nous détaillerons plus loin).
4. La commande cosets renvoit une liste de représentants des classes modulo
un sous-groupe défini avec une commande subgrel (qui fait donc référence au
groupe dont il est issu). Tester avec L ⊂ D 5 : s’agit-il des classes à droite ou
à gauche ? Tester également avec a ⊂ S 4 . C’est a priori un choix arbitraire
historique dans la littérature sur le sujet.
Comment obtenir les éléments de G en utilisant la commande cosets ? Écrire
une fonction elements1 renvoyant, en fonction du groupe G (défini comme
toujours par une commande grelgroup), la liste de ses éléments. Tester sur
les exemples précédents (C 10 , D 5 , S 4 ).
L’algorithme de Todd-Coxeter
On se donne un groupe G défini par un ensemble X = {g 1 , . . . , g m } de générateurs vérifiant un ensemble R = {r j = 1 G } 1jk de relations. D’autre part, soit
H un sous-groupe de G engendré par Y = {h 1 , . . . , h s }. Les r j et h j sont exprimés
comme des mots en les éléments de X ∪ X −1 .
L’algorithme de Todd et Coxeter permet d’énumérer les différentes classes à
droite, i.e. les éléments de (G/H) d , en faisant agir G sur (G/H) d par translation
à doite : Hx · g = H(xg). Au final, on obtient l’indice n de H dans G, des
éléments g i ∈ G tels que (G/H) d = {Hg 1 , . . . , Hg n } (i.e. des représentants des
classes) et la description explicite du morphisme ρ : G → S((G/H) d ) = S n (après
numérotation des classes), c’est-à-dire l’expression des ρ(g i ) en tant qu’éléments
de S n .
101