L'algorithme de Todd Coxeter

sujet proposé par Dominique Perrin

perrin@univ-mlv.fr

L'algorithme de Todd Coxeter est une méthode classique de l'algèbre effective. Il permet de calculer un groupe donné par générateurs et relations. Son implémentation est simple dans le principe mais délicate dans l'application à des exemples concrets. C'est un exemple de programme facile à réaliser mais qui peut être amélioré sans limites. Il existe comme une fonction standard dans un système de calcul algébrique comme Cayley [1].

1   Introduction

Nous présentons d'abord les éléments d'algèbre nécessaires pour la suite. Pour une présentation plus complète, voir [3] ou [2].

Soit G un groupe et A une partie de G. Un relateur sur G est un mot r, sur l'ensemble AÈ A-1 des symboles aÎ A et de leurs inverses, tel que r=1 dans G. Une relation sur G est un couple (r,s) de mots sur AÈ A-1 tel que r=s dans G. On dit que le couple á A| Rñ est une présentation de G si A engendre G et que toute relation sur G est une conséquence des relations r=1 pour rÎ R.

On démontre qu'il existe, à un isomorphisme près, un groupe et un seul qui a une présentation donnée. Par contre, un groupe donné admet une infinité de présentations différentes.
Exemple 1  Le groupe G=á a| a2ñ est le groupe cyclique à deux éléments Z/2Z.
Exemple 2  Soit
G=á a,b| a2,b2,(ab)2ñ
Le groupe G est le groupe commutatif à quatre éléments Z/2× Z/2 aussi connu comme le groupe de Klein et noté V4. On trouvera plus bas (Exemple 4) une représentation de G en fonction de a et b.
Exemple 3  Le groupe G=á a,b| a2,b2,(ab)3ñ est le groupe symétrique S3 qui a six éléments. En remplaçant b par c=ab, on obtient la présentation G=á a,c| a2,c3,(ac)2ñ.

2   L'algorithme de Todd Coxeter

L'algorithme de Todd Coxeter permet de calculer la représentation de permutation d'un groupe défini par générateurs et relations. Si G=á A| Rñ, l'algorithme calcule le graphe de Cayley de G relatif à A.

C'est un graphe dont les flèches sont étiquetées par les symboles de A. L'ensemble des sommets est G et les flèches sont les triplets (p,a,q) tels que pa=q dans le groupe G.

Exemple 4  Soit
G=á a,b| a2,b2,(ab)2ñ
le groupe de Klein de l'Exemple 2. Son graphe de Cayley est représenté sur la Figure 1.



Figure 1: Le groupe de Klein V4


Exemple 5  Pour l'exemple du groupe symétrique S3 (Exemple 2), on obtient le graphe de la Figure 2.




Figure 2: Le graphe de Cayley de S3


Pour réduire la taille du graphe de Cayley, on peut se donner, en plus de l'ensemble des symboles A et de l'ensemble des relateurs R, un ensemble X de mots sur AÈ A-1 et calculer la représentation de G par permutations sur les classes latérales du sous groupe H=á Xñ engendré par X.

Rappelons que les classes latérales de H dans G sont les classes de l'équivalence définie par
xº y Û x-1yÎ HÛ xÎ HyÛ yÎ HxÛ Hx=Hy

La représentation de G sur les classes latérales de H est le graphe dont les sommets sont les classes latérales Hg du sous-groupe H et les flèches sont les triplets (Hg,a,Hk) tels que Hga=Hk.

Exemple 6  Soit
G=á a,b| a2,b2,(ab)3ñ
Le groupe G est le groupe S3 de l'exemple 3. Si on prend H=á a ñ, on obtient la représentation donnée sur la Figure 3.



Figure 3: Le groupe symétrique S3


Exemple 7  Soit
G=á a,b,c | a2,b2,c2,(ab)3,(bc)3,(ac)2ñ
Le groupe G est le groupe symétrique S4. Si on prend H=á b,c ñ, on obtient la représentation donnée sur la Figure 4.




Figure 4: Le groupe S4



3   Principe de l'algorithme

Le principe de l'algorithme est de créer pour chaque relateur un cycle dans le graphe et de réduire progressivement le graphe pour tenir compte des lois de groupe.

La réduction consiste à fusionner itérativement les sommets p,q tels qu'il existe ou bien simultanément des flèches (r,a,p) et (r,a,q) ou bien simultanément des flèches (p,a,r) et (q,a,r).

L'algorithme de Todd-Coxeter est le suivant. On se donne un ensemble A de symboles (générateurs de G), un ensemble X de mots sur AÈ A-1 (générateurs du sous-groupe H) et un autre ensemble R de mots sur AÈ A-1 (les relateurs). On part du graphe ayant un seul sommet noté 1 et sans flèches.







L'algorithme s'arrête lorsque le graphe est complet, c'est à dire que pour tout sommet s et tout relateur r, il existe un cycle d'étiquette r autour de s.

Pour l'Exemple 4 du groupe de Klein, on obtient la suite de transformations donnée sur la Figure 5. Les états completés sont indiqués en grisé.



Figure 5: L'algorithme de Todd Coxeter



Pour l'Exemple 7 du groupe S4, on obtient la suite de transformations donnée sur la Figure 6.



Figure 6: Le groupe S4


De l'étape (2) à l'étape (3), les états 3 et 4 ont été fusionnés (lors de la création de cycles b2 autour de 3 et 4) et un nouvel état 4 a été crée (pour réaliser un cycle c2 autour de 3).

L'algorithme ne termine que lorsque le groupe G est fini (il ne s'agit, au sens strict, que d'un semi-algorithme qui ne termine pas pour toute donnée). Le nombre de sommets créés peut excéder le nombre de sommets final. Ainsi, pour la présentation de S4 de l'Exemple 7, mais cette fois avec X=Ø, on obtient successivement des graphes à 11 puis 27 sommets avant de terminer avec les 24 sommets du graphe de Cayley de S4.
Exemple 8   Un exemple bien pire est celui du groupe ayant la présentation
G=á a,b| a8,b7,(ab)2,(a-1b)3ñ
avec X={a2,a-1b} comme ensemble de générateurs du sous-groupe. Il y a 448 états à la fin et il faut ruser pour ne pas rencontrer des graphes ayant des milliers de sommets au passage.
On peut montrer que, dans le déroulement de l'algorithme, deux sommets ayant déjà été complétés et réduits (les sommets grisés des exemples) ne seront pas fusionnés ensuite. Ceci fournit une borne inférieure du nombre de sommets final.

4   Travail demandé

On demande d'écrire une version de l'algorithme de Todd Coxeter qui prenne comme données A,X et R et donne comme résultat une représentation du groupe de permutations obtenu. On pourra par exemple donner le résultat sous forme des permutations réalisées par les générateurs. Ainsi, le résultat de l'Exemple 6 du groupe S3 sera donné sous la forme

  a b
1 1 2
2 3 1
3 2 3
ou encore
a=(23),     b=(12)
Pour obtenir un algorithme qui fonctionne efficacement, il faut être attentif à la fois au problème du temps de calcul et à celui de la place mémoire. Un algorithme mal programmé peine déjà sur l'exemple du groupe symétrique S4 avec X=Ø.

On pourra prendre comme objectif (difficile à atteindre) la présentation de l'Exemple 8.

5   Extensions possibles

Il y a beaucoup d'extensions et de variantes possibles de l'algorithme de Todd Coxeter. Citons les suivantes:
  1. Améliorer l'interface en incorporant la possibilité d'entrer un relateur comme a8 sous la forme a^8 plutôt que aaaaaaaa.
  2. Proposer plusieurs stratégies à l'utilisateur concernant l'ordre des complétions et des réductions.
  3. Proposer un mode trace qui présente les résultats intermédiaires , en mentionnant les états complets.
  4. Effectuer le calcul inverse de l'algorithme précédent en revenant des représentations par permutations aux présentations par générateurs et relations. Pour cela on pourra procéder de la façon suivante.

    Un système de Schreier est un ensemble S de mots sur AÈ A-1 tel que tout préfixe d'un mot de S est encore dans S.

    Si on part du graphe de la représentation d'un groupe G sur les classes latérales d'un sous-groupe H, on peut associer à tout sommet p un mot s tel que p=Hs dans G et de sorte que l'ensemble S des mots s choisis forme un système de Schreier. Il suffit pour cela de considérer un arbre recouvrant du graphe ayant comme racine le sommet 1 correspondant à la classe H. On associe ensuite à un sommet l'étiquette du chemin allant de la racine à ce sommet.

    Ayant ainsi étiqeté chaque sommet p par un mot s=e(p), on considère l'ensemble X des mots de la forme sat-1 construits pour chaque transition (p,a,q) avec s=e(p),t=e(q). On montre que X est un système de générateurs du sous-groupe H.

    Si on est parti du graphe de Cayley de G, on obtient ainsi une présentation de G puisque l'ensemble obtenu engendre le sous-groupe {1}.
    Exemple 9  On considère la représentation de S3 de l'Exemple 5. Un système de Schreier est représenté sur la Figure 7. Les mots de la forme sat-1 non vides sont
    a2,b2,ab2a-1,ba2b-1,bab(aba)-1,aba2(ab)-1,abab(ba)-1
    Un peu de nettoyage redonne l'ensemble R={a2,b2,(ab)3}.



    Figure 7: Un système de Schreier


  5. Ajouter un moyen de calculer une présentation du sous-groupe H. Une méthode consiste à utiliser un système de Schreier comme ci-dessus. D'autres méthodes sont possibles (voir [2]).

References

[Cayley]
Wieb Bosma and John Cannon, Handbook of Cayley Functions, Sydney, 1992.
[Coxeter]
Coxeter, H.S.M. and Moser W.O.J., Generators and Relations for Discrete Groups, Springer, 1984.
[Magnus]
Magnus, W. and Karras, A. and Solitar, S., Combinatorial Group Theory, Dover, 1966.

This document was translated from LATEX by HEVEA.