TRAVAUX PRATIQUES
TP.IV.A. Générateurs et relations, autour de l’algorithme
de Todd-Coxeter
Les groupes définis par générateurs et relations constituent, avec les groupes
de permutations, les deux principaux types de groupes pour lesquels Maple offre
des commandes avancées dédiées à leur manipulation.
Si les groupes de permutations sont définis par des générateurs, les relations
sont entièrement régies par la multiplication des cycles ; de plus, l’unicité de la
décomposition en cycles définit un élément de façon univoque. Dans le cas des
groupes présentés par générateurs et relations, se posent des problèmes de « combinatoire des mots » : à supposer que le groupe soit fini, comment savoir si l’on a
écrit tous les mots (et être sûr que ces mots correspondent à des éléments distincts
modulo les relations) ?
Un des principaux algorithmes est dû à Todd et Coxeter : il permet, disposant
d’une présentation de G et d’un sous-groupe H d’indice fini n (défini par des
générateurs exprimés comme des mots en les générateurs de G), de donner un
système de représentants des classes modulo H.
Dans le cas où G est un groupe fini, en prenant H = {Id}, on obtient en
particulier les éléments de G.
De plus, l’algorithme nous fournit un morphisme ρ : G → Aut(G/H) S n
qui traduit l’action de G par translation sur les classes G/H. C’est d’ailleurs cette
action qui est à la base de l’algorithme, d’où le choix de différer ce TP en fin de
chapitre IV. On obtient ainsi, si ρ est injectif, une réalisation de G comme un
groupe de permutations.
Les objectifs de ce TP sont multiples : d’une part, on apprend à manipuler
les groupes définis par générateurs et relations (calcul du cardinal, du moins si ce
TP.IV.A. Générateurs et relations, autour de l’algorithme
de Todd-Coxeter
Les groupes définis par générateurs et relations constituent, avec les groupes
de permutations, les deux principaux types de groupes pour lesquels Maple offre
des commandes avancées dédiées à leur manipulation.
Si les groupes de permutations sont définis par des générateurs, les relations
sont entièrement régies par la multiplication des cycles ; de plus, l’unicité de la
décomposition en cycles définit un élément de façon univoque. Dans le cas des
groupes présentés par générateurs et relations, se posent des problèmes de « combinatoire des mots » : à supposer que le groupe soit fini, comment savoir si l’on a
écrit tous les mots (et être sûr que ces mots correspondent à des éléments distincts
modulo les relations) ?
Un des principaux algorithmes est dû à Todd et Coxeter : il permet, disposant
d’une présentation de G et d’un sous-groupe H d’indice fini n (défini par des
générateurs exprimés comme des mots en les générateurs de G), de donner un
système de représentants des classes modulo H.
Dans le cas où G est un groupe fini, en prenant H = {Id}, on obtient en
particulier les éléments de G.
De plus, l’algorithme nous fournit un morphisme ρ : G → Aut(G/H) S n
qui traduit l’action de G par translation sur les classes G/H. C’est d’ailleurs cette
action qui est à la base de l’algorithme, d’où le choix de différer ce TP en fin de
chapitre IV. On obtient ainsi, si ρ est injectif, une réalisation de G comme un
groupe de permutations.
Les objectifs de ce TP sont multiples : d’une part, on apprend à manipuler
les groupes définis par générateurs et relations (calcul du cardinal, du moins si ce