Université de Rouen UFR Sciences & Techniques Rapport de stage de master Maître de stage : Florent Hivert Tuteur universitaire : Jean-Philippe Dubernard Alge`bres de Hopf et mono¨ıdes plaxiques ge´ne´ralise´s Jean-Baptiste PRIEZ Orsay, le  septembre  Table des matières Introduction  Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  Sujet et problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  Organisation du rapport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   Notions mathématiques et combinatoire  . Monoïde et base d’algèbre . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Monoïde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Groupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Corps et anneau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Anneau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Espace vectoriel et module . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Espace vectoriel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Propriétés sur ces espaces . . . . . . . . . . . . . . . . . . . . . . . .  . Algèbre, cogèbre, bigèbre et algèbre de Hopf . . . . . . . . . . . . . . . . . .  .. Algèbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Cogèbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Bigèbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Algèbre de Hopf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Introduction à la combinatoire . . . . . . . . . . . . . . . . . . . . . .  .. Algèbre de Hopf combinatoire . . . . . . . . . . . . . . . . . . . . . .  . Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Base Duale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Crochet de dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Relation d’ordre et treillis . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Relation d’ordre et poset . . . . . . . . . . . . . . . . . . . . . . . . .  .. Treillis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    Techniques de constructions et algèbres de Hopf principales  . Réalisations polynomiales d’algèbres de Hopf . . . . . . . . . . . . . . . . . .  .. Algèbres de polynômes non-commutatifs et réalisations . . . . . . . .  .. Réalisation polynomiale d’algèbre . . . . . . . . . . . . . . . . . . . .  .. Doublement d’alphabet . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Réalisation polynomiale de cogèbre . . . . . . . . . . . . . . . . . . .  .. Réalisation polynomiale de Hopf . . . . . . . . . . . . . . . . . . . . .  . Restrictions aux positions et aux intervalles . . . . . . . . . . . . . . . . . .  .. Restrictions aux positions . . . . . . . . . . . . . . . . . . . . . . . .  .. Restrictions aux intervalles . . . . . . . . . . . . . . . . . . . . . . . .  . L’algèbre de Hopf : FQSym . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Classe combinatoire des permutations . . . . . . . . . . . . . . . . . .  .. Bijection avec les mots standards . . . . . . . . . . . . . . . . . . . .  .. Module combinatoire et réalisation polynomiale . . . . . . . . . . . .  .. Algèbre combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Cogèbre combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Algèbre de Hopf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Algèbre de Hopf duale . . . . . . . . . . . . . . . . . . . . . . . . . .  . L’algèbre de Hopf : WQSym . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Classe combinatoire des partitions d’ensembles ordonnés . . . . . . .  .. Bijection avec les mots tassés . . . . . . . . . . . . . . . . . . . . . .  .. Module combinatoire et réalisation polynomiale . . . . . . . . . . . .  .. Algèbre combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Cogèbre combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Algèbre duale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . L’algèbre de Hopf : PQSym . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Algorithme de parkisation . . . . . . . . . . . . . . . . . . . . . . . .  .. Algèbre et duale de Hopf . . . . . . . . . . . . . . . . . . . . . . . . .   Monoïdes et algèbres de Hopf  . Monoïde plaxique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Description par relations . . . . . . . . . . . . . . . . . . . . . . . . .  .. Description algorithmique . . . . . . . . . . . . . . . . . . . . . . . .  .. Formule des équerres . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Compatibilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Bons monoïdes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Définition et propriétés . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Opérations sur les bons monoïdes . . . . . . . . . . . . . . . . . . . .  .. Passage aux algèbres de Hopf . . . . . . . . . . . . . . . . . . . . . .  . Monoïde sylvestre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Description par relations . . . . . . . . . . . . . . . . . . . . . . . . .  .. Description algorithmique . . . . . . . . . . . . . . . . . . . . . . . .   .. Formule des équerres . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Treillis de Tamari . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Monoïde stalacticte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Description par relations . . . . . . . . . . . . . . . . . . . . . . . . .  .. Description algorithmique . . . . . . . . . . . . . . . . . . . . . . . .  .. Treillis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Monoïde taïga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Description par relations et algorithmes . . . . . . . . . . . . . . . . .  .. Formule des équerres . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Treillis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . Classes combinatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Stalactites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. Arbres binaires à multiplicités . . . . . . . . . . . . . . . . . . . . . .  . Algèbres de Hopf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. PBT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. PBTm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  Conclusion  Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  Références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   Introduction Contexte Danscerapport,voustrouverezmontravaileffectuédurantlestagederecherchedumaster IGIS spécialité ITA (Informatique Théorique et Applications) au sein du LRI (Laboratoire de Recherche en Informatique) sur le campus d’Orsay, Université Paris-Sud. Mon travail a été encadré par Florent Hivert† et Nicolas M. Thiéry‡ sur le thème du monoïde plaxique généralisé. “Quelles raison as-tu de considérer le monoïde plaxique comme un des monoïdes fondamentaux de l’algèbre?" André Lentin [Sch] Il existe un grand nombre de monoïde, quotient du monoïde libre, dont les éléments et les algorithmes sous-jacents possèdent des propriétés combinatoires intéressantes (les mo- noïdesplaxique,sylvestre,baxter[Gira],hypoplaxique[Nov],stalactites[HNT],...).L’étude des monoïdes de type plaxique se base sur le monoïde fondamental le monoïde plaxique [LS, Lot] définit par les relations de D. Knuth [Knu]. Ce monoïde intervient dans bon nombre de démonstration de la règle de Littlewood-Richardson [LR] (qui calculeles cœf- ficients apparaissant lors d’une multiplication de fonctions de Schur [Mac]). Il est aussi utilisé pour généraliser l’algèbre des fonctions symétriques [PR]. Parmi les nombreux monoïdes introduits dans la littérature, nous nous intéresserons parti- culièrement au monoïde sylvestre [HNT, HNT] ainsi qu’au monoïde stalactite [HNT]. Ces deux monoïdes sont des analogues au monoïde plaxique, ils sont ainsi qualifiés de bons monoïdes [Hiv, HN]. L’étudedesbons monoïdes permetlaconstructionquasi-automatiqued’algèbres de Hopf combinatoire [Hiv, Foi]. En , Hivert-Novelli-Thibon ont montré un lien fort entre les objets algorithmiques combinatoires sous-jacents à ces monoïdes (partitions d’entiers, d’en- sembles,arbresbinaires,graphes,...), et les algèbres de Hopf. Ce lien donne un angle d’attaque privilégié pour l’analyse d’algorithme raffinant la notion de série génératrice pour enregistrer plus d’information. Sujet et problématique L’objectif durant mon stage, fût de généraliser la construction des algèbres de Hopf utili- sant la démarche (figure ) de Hivert-Nzeutchap. Cette démarche part d’un algorithme . IGIS:masterenInformatique,Géniedel’InformationetdesSystèmesproposéàl’UniversitédeRouen. La spécialité ITA est une des trois spécialités proposées dans la formation Informatique. †. fl[email protected] (Pr. Univ. Paris-Sud) ‡. [email protected] (Pr. Univ. Paris-Sud)  Algèbre c ostma pn adtairbidliistaétio n Algorithme : – Schensted Associativité sous (co-)alg. Monoïde Alg. Hopf – arbre binaire FQSym de recherche – ... co restmr.pinatteibrvilaitléles Cogèbre Figure  – Schéma de la construction d’une algèbre de Hopf combinatoire proposé par Hivert-Nzeutchap [HN] à partir d’un algorithme associatif. associatif manipulant des objets combinatoires (au sein d’un monoïde); et en imposant deux contraintes : compatibilités à la standardisation et à la restriction aux intervalles, on obtient une structure de sous-algèbre de Hopf de l’algèbre des permutations FQSym [DHT]. Cette technique de construction permet notamment de recontruire l’algèbre PBT [LR] à partir de l’algorithme d’insertion dans un arbre binaire de recherche manipulant les arbres binaires du monoïde sylvestre [HNT, HNT]. Mon stage s’est donc fixé autour des objectifs suivants : – La compréhension de la notion mathématique d’une algèbre de Hopf et particulièrement de sa structure combinatoire. À cela s’ajoute l’assimilation de quelques techniques ré- currentes et très efficaces pour obtenir ces dernières : les réalisations polynomiales qui permettent de construire des sous-algèbres de l’algèbre libre; le doublement d’alphabet utilisé pour montrer que le définition d’un coproduit  est un morphisme d’algèbre à partir d’une réalisation polynomiale, et ainsi d’obtenir une structure de bigèbre. – L’étude de différentes algèbres de Hopf. Ce rapport s’intéresse particulièrement à deux algèbres : FQSym, l’algèbre des permutations [DHT], et WQSym, l’algèbre des par- titions ordonnées [Hiv, NT, BZ]. L’algèbre FQSym est l’algèbre pour laquelle on utilise la fonction de standardisation. Cette fonction permet d’exprimer un élément de FQSym dans l’algèbre libre par l’in- termédiaire d’une réalisation polynomiale qu’elle définit. La notion de standardisation est intéressante pour ce rapport car elle est un point essentiel de la définition d’un bon monoïde au sens de Hivert-Nzeutchap. . Un coproduit est une opération duale au produit. Elle consiste à désassembler un élément alors que le produit permet d’assembler.  L’algèbre WQSym contient la sous-algèbre FQSym, laquelle utilise la fonction de tas- sement au même titre que précédemment. C’est en étudiant en particulier cette dernière qu’on a cherché à étendre la définition de bon monoïde. Nous verrons que la définition s’étend aussi naturellement grâce à la fonction de parki- sation qui apparait dans l’algèbre PQSym [NT], l’algèbre des fonctions de parking. – La généralisation de la définition de bon monoïde. L’idée proposée par Florent Hivert a été d’étudié un monoïde issu des définitions du monoïde sylvestre [HNT, HNT] et du monoïde stalactite [HNT] : un monoïde que nous avons choisi d’appelé monoïde taïga pour faire le lien entre les arbres et les stalactites (deglaces). Ce monoïde, comme le monoïde stalactite, présente une compatibilité au tassement. Nous verrons que cette com- patibilité permet de donner une nouvelle définition de bon monoïde que nous pourrons même étendre à la parkisation. – L’implantation sur la plateforme Sage-combinat des différents outils utilisés pendant mon stage. Sage est une plateforme open-source de mathématiques proposant une alter- native viable à Magma, Maple, ... Les sources de mon travail sont disponibles sur un serveur de version à l’adresse http://code.google.com/p/sage-hopf-algebra/. Organisation du rapport Ce rapport se découpe en trois parties principales : une première partie mathématiques, une seconde sur les techniques de constructions d’algèbres de Hopf avec la description de certaines algèbres, et enfin une troisième présentant quelques résultats obtenus. Dans la partie mathématiques se trouve une description complète de la structure d’algèbre de Hopf,endétaillantungrandenombredestructuresimbriquées:monoïde, groupe, module, anneau, algèbre, cogèbre, bigèbre. Nous trouverons aussi quelques définitions combinatoires, un rapide aperçu de la notion de dualité ainsi que quelques propriétés sur les treillis. Dans la seconde partie, nous introduisons les techniques de réalisations polynomiales, de doublement d’alphabet ainsi que certaines restrictions. Cette partie bibliographique se com- plète d’une présentation (non exhaustive aux vues des nombreuses publications y attrayant) des algèbres FQSym, WQSym et PQSym. Enfin, dans un dernier temps, nous présentons quelques résultats encourageants sur la généralisation de la définition de bon monoïde. Cette généralisation sera notamment usitée sur un monoïde particulier (le monoïde taïga) pour le quel les compatibilités permettent d’obtenir une sous-algèbre de WQSym en généralisant PBT. Les deux dernières parties sont complétées d’exemples automatisés par l’implantation des différentes algèbres sur Sage. J’ai eu l’occasion d’implanter en partie FQSym, totalement WQSym, PBT et PBTm (l’algèbre résultante des compatibilités du monoïde taïga).  Chapitre  Notions mathématiques et combinatoire . Monoïde et base d’algèbre Cechapitrevaintroduirelesbasesd’algèbresquivontpermettredeprésenterlesstructures d’algèbre, cogèbre, bigèbre, et enfin algèbre de Hopf. Ces bases sont les structures classiques de monoïde et de groupe. Par ailleurs, la notion de monoïde est importante. Elle va être réutilisée pour définir certaines sous-algèbres de Hopf d’algèbres classiques. .. Monoïde Avant toute chose, nous introduisons une des structures les plus simples en algèbre : la structuredemonoïde.Celle-civatrèsimportantetoutaulongdecerapport,ellevapermettre introduire les notions d’anneaux, d’algèbre d’anneaux qui vont être nécessaire pour définir une algèbre de Hopf ; en plus, cette structure va être une des premières étapes à l’analyse d’algorithme que nous allons présenter. Définition .. (Monoïde) Soient M un ensemble, et ⊕ une loi de composition interne associative sur M. Le magma associatif (M,⊕) forme un monoïde s’il existe e ∈ M qui soit un élément neutre. Autrement dit, un monoïde est un semi-groupe ayant un élément neutre, ou encore un magma dont la loi de composition interne est associative pour lequel il existe un élément neutre.  ⊕×Id A×A×A A×A Id×⊕ ⊕ ⊕ A×A A Figure . – Ce schéma représente l’associativité de l’opérateur ⊕ dans la définition d’un monoïde (définition ..); et où Id est la fonction identité. Id×e e×Id A×A A A×A ⊕ ⊕ Figure.– Ceschémareprésentel’élémentneutreavecIdl’applicationidentité,etoùId× e (respectivement e×Id) associe à un élément a ∈ A le couple (a,e) ∈ A×A (respectivement (e,a)). Exemple .. Soit N l’ensemble des entiers naturels, et + l’opération d’addition usuelle. Le couple (N,+) forme un magma : ∀a,b ∈ N, a+b ∈ N. Ce magma est un semi-groupe : ∀a,b,c ∈ N, (a+b)+c = a+(b+c). Ce semi-groupe est est un monoïde : ∀a ∈ N, a+0 = 0+a = a. Afindesimplifierlacompréhensiondesprochainesstructures,nousprésentonslesnotations par diagrammes. Un monoïde se simplifie par les schémas figures . et .. On dit que le monoïde est un monoïde commutatif lorsque la loi de composition interne est commutative. Pour N un sous-ensemble du monoïde M, on dit que M est engendré par N si pour tout x ∈ M il existe n ∈ N et (a ) ∈ Nn tel que x = a ⊕...⊕a . On parle alors de N une i i∈[1,n] 1 n famille génératrice du monoïde M. 