Monoïdes
Un monoïde est un ensemble M muni d’une multiplication et d’un élément neutre ; c’est-à-dire un groupe mais sans l’axiome d’inversibilité. Cette structure algébrique peut encoder naturellement la composition des opérations élémentaires d’un algorithme sur une structure de données. L’exemple fondamental est peut-être la théorie des langages, l’ensemble des mots sur un alphabet A muni de la concaténation constitue un monoïde. Plus algorithmique, considérons le tri à bulles qui trie un tableau de nombres en effectuant des transpositions élémentaires de gauche à droite jusqu’à obtenir une liste triée.
Théorie des représentations
Naturellement, le monoïde précédemment défini agit sur les tableaux de longueur n. On peut poursuivre l’abstraction du problème : la valeur des éléments de la liste n’a pas vraiment d’importance, l’algorithme ne dépend que de la position de chaque case dans la liste, donc toutes les permutations de longueur n représentent une exécution différente de l’algorithme. On peut alors regarder l’action de Hn(0) sur l’espace vectoriel Cn! , dont la base est indexée par les permutations et qui représente toutes les entrées possibles de l’algorithme du tri à bulles. Se ramener à l’algèbre linéaire permet d’utiliser des processus d’élimination de type pivot de Gauss, afin de décomposer le problème en blocs plus simples. L’étude de Hn(0) va ainsi passer par exemple par la décomposition de l’espace vectoriel en somme directe d’espaces invariants, l’étude de leurs dimensions, le calcul des valeurs propres des actions, etc. Plus généralement, le plongement de M dans un espace de matrices par une application M → Mn(k) est appelé une représentation, et l’étude de ces morphismes (évidemment non uniques) est appelée théorie des représentations.
Dans le cadre des groupes finis, c’est un axe majeur de recherche depuis plus d’un siècle : une représentation d’un groupe G est un plongement G → GLn(k). Ces morphismes sont caractérisés par la donnée d’un nombre fini de représentations irréductibles, et la décomposition d’une représentation quelconque en représentations irréductibles est unique (c’est une somme directe) : c’est le théorème de Maschke qui affirme qu’une algèbre de groupe sur un corps de caractéristique 0 est semi-simple [Mas98]. Les représentations de groupes ont été introduites par Frobenius et les premiers résultats spectaculaires extérieurs à la théorie ont été obtenus par Burnside au début du XXème siècle .
La théorie des représentations joue un rôle de premier plan dans la plupart des mathématiques modernes comme l’analyse harmonique, la géométrie différentielle, la théorie des nombres ou la théorie de la complexité géométrique. On retrouve également la théorie des représentations en physique, en particulier en physique quantique où les symétries sont d’une importance capitale. Le cas des semigroupes et des monoïdes en particulier est étudié depuis les années 1960 [Sch58], [CP61], [LP69]. Classiquement, le point de vue fait intervenir très explicitement le monoïde des matrices de rang fini sur un corps. Plus récemment, de nombreuses connexions ont été faites avec d’autres domaines comme par exemple les chaînes de Markov ce qui a donné une nouvelle impulsion aux représentations de semigroupes [Put96], [Bro00]. Le point de vue est aujourd’hui très algébrique et utilise la généralité de la théorie des modules : une représentation d’un monoïde M sur un k-espace vectoriel est exactement un kM module. Les résultats des dernières décennies en représentation de monoïdes donnent un contrôle assez fin sur les représentations des monoïdes, permettant de se ramener à la théorie des représentations des groupes et à de la combinatoire sur des préordres.
Mais la situation pour les monoïdes finis n’est pas aussi idyllique que pour les groupes finis : les kM-modules ne sont pas semi-simples en général. Ils s’obtiennent bien comme extensions successives de modules irréductibles mais ceux-ci ne sont pas en somme directe en général. On peut cependant décomposer un kM-module finiment engendré comme un quotient d’une somme directe de modules projectifs indécomposables. L’une des motivation principale de l’étude des représentations des monoïdes est la dualité entre modules projectifs indécomposables et modules simples, dualité qui est triviale dans le cas des groupes.
Tours de monoïdes
Si nous reprenons notre premier exemple d’algorithme de tri à bulles, on remarque qu’augmenter la taille de la liste initiale augmente par la même le monoïde des différentes exécutions. Aussi, les sousmonoïdes Hi(0) de Hn(0) pour i < n contiennent une grande partie de l’information. On peut, à partir d’une représentation de Hn(0), restreindre cette représentation à Hi(0). Réciproquement on peut construire une représentation de Hn(0) à partir d’une représentation de Hi(0) de manière universelle via un processus qu’on appelle induction. Vu que l’on dispose ici d’une famille de monoïdes (Hn(0))n de même nature, il est naturel de considérer la tour (Hn(0))n ainsi que les foncteurs de restriction et d’induction afin d’en étudier les représentations.
|
Table des matières
1 Introduction
2 Combinatoire algébrique
2.1 Mots et permutations
2.2 Partitions
2.2.1 Partition d’un entier
2.2.2 Compositions d’un entier
2.2.3 Partitions d’ensembles
2.2.4 Partitions ordonnées d’ensemble
2.3 Chemins de Dyck
2.4 Monoïdes
2.4.1 Relations de Green
2.4.2 Monoïdes K-triviaux
2.4.3 Quelques exemples
2.4.4 Structure des J -classes
2.5 Modules et algèbres de dimensions finie
2.5.1 Produit tensoriel
2.5.2 Induction et restriction des modules
2.5.3 Séries de composition
2.5.4 Produits tensoriels d’algèbres
2.5.5 Décomposition par blocs
2.5.6 Algèbres semi-simples
2.5.7 Modules projectifs
2.6 Groupes de Grothendieck
2.7 Algèbres de Hopf
2.7.1 Exemples classiques d’algèbres de Hopf
2.7.2 Fonctions symétriques
2.7.3 Fonctions quasi-symétriques libres
2.7.4 Fonctions symétriques non-commutatives
2.7.5 Algèbre de Hopf de Loday et Ronco
3 Représentations des monoïdes finis
3.1 Équivalence avec la théorie des modules
3.2 Représentations des groupes finis
3.3 Représentations des groupes symétriques
3.4 Théorie des espèces
3.4.1 Définition
3.4.2 Fonction génératrice et arithmétique des espèces
3.4.3 Série indicatrice des cycles
3.5 Construction de Clifford – Munn – Ponizovskiĭ des modules simples
3.6 Modules de Schützenberger
3.7 Représentations des monoïdes J -triviaux
4 Tours de monoïdes et catégorification
4.1 Tours d’algèbres et de monoïdes
4.2 Induction et restriction des représentations
4.3 Tours de monoïdes J -triviaux
4.3.1 Induction des modules simples
4.3.2 Restriction des modules simples
4.4 Anneaux de Grothendieck
4.5 Catégorification
4.6 Tours d’algèbres au sens de Bergeron et Li
4.7 Tours de semi-treillis
4.7.1 Tour des permutoèdres
4.7.2 Tour des treillis de Tamari
4.7.3 Tour des treillis booléens
4.8 Tours d’algèbres basiques
4.9 Non catégorification de PBT
4.9.1 Énoncé
4.9.2 J -trivialité pour n ď 5
4.9.3 Exploration informatique
4.10 Catégorifications de NCSF{QSym
4.10.1 Énoncé
4.10.2 Démonstration
4.10.3 Mn contient un quotient de Hnp0q
5 Fonctions de parking
6 Conclusion