Publications du Laboratoire de Combinatoire et d’ Informatique Mathématique 8 Guy Melançon Réécritures dans I’algébre de Lie libre, le groupe libre et l’algèbre associative libre Département de mathématiques et d’informatique Université du Québec B Montréal “!Il Responsable de la collection: Sre&o Brlek LAC34 Université du Québec à MontrrZal C.P. 8888, SU~C. A Montr6al, Qc. canada H3c 3P8. e-mail: [email protected] Ce num6ro constitue la publication d’une th5se soutenue devant jury. pour l’obtention du Ph.D. Composition du Jury P.M.COHN University Colleege. London A. JOYAL UIZAM, P.LEROUX VQAMt c.IWJTENAUER UQAM,Directeur D. THÉRIEN Mc Gill University D@ôt Egal. deuxii?me semestre 199 1, BiblioWque nationale du Qu&e~. ISBN 2-89276-094-l LACIM Montréal 0 LACIM, Montr&tl, Septembre 1991. Laboratoire de combinatoire et d’informatique math6matique Département de math6matique.s et d’informatique Université du Québec à Montréal C.P. 8888, SU~C. A Montrt%l, Qc. canadaH3c3P8 UNIVERSITÉ DU QUÉBEC À MONTRÉAL THÈSE PRÉSENTÉE COMME EXIGENCE PARTIELLE DU DOCTORAT EN MATHÉMATIQUES PAR GUY MELANÇON RÉÉCRITURES DANS L’ALGÈBRE DE LIE LIBRE, DANS LE GROUPE LIBRE ET DANS L>ALGÈBRE ASSOCIATIVE LIBRE AVRIL 1001 Résumé On élabore des systèmes de réécriture et on les applique à la théorie et aux calculs effectifs dans certaines structures algébriques libres. Dans le monoide libre, on étudie une famille de factorisations complètes; les mots d’une telle factorisation sont appelés des ‘mots de Hall’. Le système de réécriture qu’on y développe permet d’effectuer le calcul de la factorisation (unique) en produit de mots de Hall des mots du monoïde libre. Nous l’utilisons aussi pour montrer d’importantes caractérisations des mots de Hall, qui n’étaient connues que dans le cas où la factorisation est ‘celle formée des ‘mots de Lyndon’. On fait ensuite l’étude détaillée, dans l’algèbre de Lie libre, du redressement des bases de Hall généralisées, à l’aide du système de réécriture développé dans le monoide libre. Une version adaptée de ce système de réécriture nous permet de faire un travail analogue dans le groupe libre. Dans ce contexte, on montre que les éléments du groupe libre s’écrivent de façon unique comme produit de certains commutateurs. On donne aussi des identités pour calculer les multiplicités de ces commutateurs dans la décomposition d’un élément du groupe libre. On met au point des algorithmes de calcul des bases standard des idéaux à droite dans l’anneau des polynômes non commutatifs. Une des principales applications de nos résultats est de rendre effectif le travail avec les idéaux et dans le quotient de l’anneau par un idéal. Les résultats sur les idéaux sont ensuite généralisés aux modules à droite sur l’anneau des polynômes non commutatifs. Remerciements Je tiens à remercier: Monsieur P. M. Cohn pour l’honneur et le plaisir qu’il me fait en acceptant de se joindre au jury de cette thèse. Mon directeur C. Reutenauer, qui m’a amené à la combinatoire des mots. Je lui suis reconnaissant pour tout le temps qu’il m’a dédié et pour ses encouragements constants durant les années d’étude et de recherche qui m’ont conduit à la rédaction de cette thèse. Messieurs A. Joyal, P. Leroux et D. Thérien de s’être intéressés à ce travail et d’avoir accepté de faire partie du jury. Je remercie aussi les membres de l’équipe du LaCIM de leur soutien et leurs encourage- ments tout au long de ce travail. Enfin, cette thèse n’aurait pas vu le jour si je n’avais été chaudement entouré des membres de ma famille: Milicska, Maya et Elie. Je dédie ce travail à mes parents. iV Table des matières Résumé ......................................................................... ..i i ... Remerciements .................................................................. ..n 1 Table des matières ................................................................. . Introduction ....................................................................... . 1. Réécritures dans le monoide libre et dans l’algèbre de Lie libre ................. .5 1.1 Introduction ............................................................... . 1.2 Arbres et mots de Hall: définitions et notations ............................ .7 1.3 Factorisations des facteurs de mots de Hall ................................ .9 1.4 Réécritures de suites standard de mots de Hall ............................ 13 1.5 Propriétés ‘à la Lyndon’ des mots de Hall ................................ .19 1.5.1 Conjugaison...........................................................l 9 1.5.2 Facteurs droits ..................................................... ..2 6 11.6 Réécritures dans l’algèbre de Lie libre .................................... .29 11.7 Base duale et algèbre de mélange ......................................... 37 2. Réécritures dans le groupe libre ................................................ .45 t2.I Introduction ............................................................ ..4 5 :2.2 Suites standard dans F(A) et système de réécriture ....................... .47 t2.3 Confluence ............................................................. ..5 5 :2.4 Unicité de la décomposition et calcul des exposants de Hall ............... .62 t2.5 Les identités de Thérien ................................................. .68 :2.6 Généralisation des identités de Thérien .................................... 71 2.6.1 Fonctions représentatives de F(A) .................................... 73 2.6.2 Topologie de Hall ..................................................... 77 3. Constructions des bases standard des K<A>-modules à droite ................ .81 3.1 Introduction ............................................................. .81 3.2 Recteurs des polynômes et s-dépendance à droite ........................ .82 3.3 Idéaux à droite dans ](<A>. ............................................. .88 Vi 3.4 Bases standard des idéaux à droite ....................................... .94 3.5 K<A>-modules à droite et I-dépendance à droite ....................... 100 Conclusion .................................................................... ..117 Bibliographie ................................................................... .119 Indexterminologique .......................................................... ..12 3 Indexdesnotations ............................................................ ..12 5 0 Introduction Dans un travail sur l’étude de certains p-groupes, P. Hall [HP 331 effectuait des calculs profonds sur les commutateurs itérés et sur la série centrale descendante du groupe libre. Cet article allait être suivi de plusieurs autres travaux d’importance dans la ‘théorie com- binatoire des groupes’. Parmi ceux-là, les travaux de Magnus [Ma 35, Ma 371 et de Witt [Wi 371 ont permis de lier le groupe libre à une autre structure algébrique fondamentale: l’algèbre de Lie libre. M. Hall a construit dans [HM SOa] une suite ordonnée de commu- tateurs dans le groupe libre (qu’il a appelé les ‘commutateurs basiques’), qui donnent une base de la série centrale descendante du groupe libre. Dans le même article, il a utilise les commutateurs basiques pour obtenir une base de l’algèbre de Lie libre qui, depuis, est appelée la ‘base de Hall’. Divers auteurs ont par la suite proposé des généralisations des commutateurs basiques (Meier-Wunderli [MW 521, Schützenberger [SC 581, $irSov [si 621, Gorcakov [Go 691, Ward [Wa 691). Peu de temps après M. Hall, Lyndon [Ly 54, CFL 581 construisait une autre base de la série centrale descendante, qui à l’origine semblait d’une nature différente de celle de la base de Hall. Les travaux de Viennot [Vi 761 ont réuni dans une même famille toutes les bases qui avaient alors été construites. Il a donné des conditions précises qui décrivent une large famille de bases de l’algèbre de Lie libre qui inclut la base classique de M. Hall et la base de Lyndon. Il a montré comment ces bases peuvent être obtenues à l’aide d’une gtinéralisation de la ‘méthode d’élimination de Lazard’. De plus, il ramenait l’étude des bises de l’algèbre de Lie libre à celle des factorisations du monoide libre. Ce sont les bases considérées par Viennot que nous appellerons les ‘bases de Hall ghhles’. Les factorisations qui leur correspondent dans le monoide libre sont appelées par Viennot ‘les factorisations de Lazard’; nous appellerons les’mots d’une telle factorisation, des ‘mots de Hall’. On peut construire, à l’aide d’une base de Hall générale, une base de l’algèbre enveloppante de l’algèbre de Lie libre, en vertu du théorème de Poincaré-Birkhoff-Witt (cf. [Hu 72, Ja 621). 0 n est donc amené à une autre structure algébrique libre. En effet, l’algèbre enveloppante de l’algèbre de Lie libre est précisément l’algèbre associative libre (cf. [Ja 62, Lo 821). Cette algèbre est celle des polynômes en variables non commutatives; elle est aussi le module libre engendré par les mots du monoide libre. Dans [MR 891, Mielançon et Reutenauer présentaient un système de réécriture qui permet de calculer les mots dans la base de Poincaré-Birkhoff-Witt associée à la base de Lyndon de l’algèbre 2 de Lie libre. C’est ce système de réécriture qui est ici généralisé pour travailler avec les basesd e Hall générales, dans l’algèbre de Lie et son algèbre enveloppante. Nous démontrons aussi certains résultats sur la factorisation des mots, de façon complète- ment combinatoire, en utilisant les propriétés du système de réécriture. Dans son travail, Lyndon [CFL 58) d onne quatre caractérisations des mots de Lyndon. Un paragraphe entier de [Lo 821 est consacré à l’étude des propriétés très fines de ces mots, par rapport à l’ordre lexicographique sur les mots. Nous montrons dans ce travail que plusieurs des propriétés des mots de Lyndon sont aussi partagées par les mots de Hall, par rapport à un ordre qui généralise l’ordre lexicographique. Ces calculs dans l’algèbre de Lie libre et dans le monoide libre trouvent leurs analogues dans le groupe libre. En effet, Magnus [Ma 35, Ma 371a donné un plongement du groupe libre dans l’algèbre des séries formelles en variables non commutatives. Il met ainsi la filtration naturelle de l’algèbre associative libre en correspondancea vec la suite centrale descendante du groupe libre. Aux bases de Hall générales de l’algèbre de Lie libre, il correspond des familles de commutateurs basiques,q ue nous appelonsd es ‘commutateurs de Hall’. Il nous a semblén aturel de chercher dans quelle mesuren os méthodes pouvaient être utilisées pour retrouver les résultats dans le groupe libre. On y développe un système de réécriture qui permet de calculer la décomposition des éléments du groupe libre en produit de commutateurs de Hall. Cependant, on n’a plus dans le groupe libre toute la rigidité d’une structure de monoide et par conséquent, le système de réécriture ne suffit plus à lui seul pour montrer l’unicité de cette décomposition. Pour y arriver, nous avons développé un argument algébrique, comme l’ont fait entre autres M. Hall [HM 5Oa] et Lyndon [CFL 581. N os calculs montrent que les fonctions qui calculent l’exposant d’un wnmutateur de Hall, dans la décomposition des éléments du groupe libre, sont dans l’algèbre des fonctions sous-mot. Ce résultat permet d’étendre au groupe libre tout entier des identités qui avaient été montrées par Thérien [Th 831 pour le monoïde libre. On en tire de nouvelles démonstrations de deux importants théorèmes. L’un de Magnus [Ma 371 qui caractérise les éléments du némcg roupe de la série centrale decendante du groupe libre; et l’autre de P. Hall [HP 33) qui donne une expression polynomiale pour l’exposant d’un commutateur de Hall, dans la décomposition d’une puissance d’un élément du groupe libre. Ce théorème lui avait permis de montrer plusieurs résultats importants de la théorie des p-groupes. Le calcul avec les sous-algèbresd e Lie de l’algèbre de Lie libre est lié aux calculs avec les idéaux à droite dans l’algèbre associative libre. En effet, une sous-algèbred e Lie de l’algèbre de Lie libre est exactement égale à la partie de l’idéal à droite qu’elle engendre (dans l’algèbre associative libre), et qui se trouve dans l’algèbre de Lie libre (cf. [Di 741 et [Reu 901). C’est ce résultat qui motive l’étude que nous faisonsd es idéaux à droite de l’anneau des polynômes non commutatifs. Il est connu depuis P. M. Cohn (CO 61, CO 691 que les idéaux à droite de cet anneau sont des modules libres (sur l’anneau). Notre point de départ est un théorème de Berstel et Reutenauer [BR 881, qui affirme l’existence