Pour le monoïde plaxique

Marcel-Paul Schützenberger

I.B.P. - L.I.T.P.

Ce texte est une brève réponse à une question posée il y a bien longtemps par mon ami André Lentin et plus récemment par Gian-Carlo Rota :

“Quelles raisons as-tu de considérer le monoïde plaxique comme un des monoïdes fondamentaux de l’algèbre ? ”

Les origines et les propriétés de ce monoïde étant la théorie des permutations, sous divers aspects plantés ou cultivés dans le département où s’accomplit la part la plus universitaire de ta multiple carrière, je m’enhardis à te faire un hommage de ma réponse.

Trois sont les raisons de la faiblesse que j’ai pour le monoïde plaxique.

D’abord quelques notations ou conventions de style.

Soient

• 𝔸^{∗}= le monoïde libre engendré par l’alphabet totalement ordonné 𝔸 = {a_{1} < a_{2} < …} ( ou plus commodément, 𝔸 = {… a < … < b < … < c < …} );

• ℤ(𝔸^{∗}), son algèbre et Ev, le morphisme canonique ( l’évaluation) de ℤ(𝔸^{∗}) sur l’algèbre usuelle Pol(𝔸) des polynômes commutatifs en les variables de 𝔸.

Un mot w = w_{1} ⋯ w_{n}, ( w_{i} ∈ 𝔸) est une colonne ssi w_{1} > w_{2} > ⋯ > w_{n} et une ligne ssi w_{1} ≤ w_{2} ≤ ⋯ ≤ w_{n}.

Les lignes (resp. colonnes) sont en bijection avec la base de Pol(𝔸), c’est-à-dire les monômes (resp. avec l’algèbre distributive libre, c’est-à-dire les parties de 𝔸).

La congruence plaxique ≡ est définie par les relations suivantes dont le mérite de la découverte revient à D.Knuth:

Pour tout a, b, c ∈ 𝔸 a < b ≤ c ⇒ bca ≡ bac
a ≤ b < c ⇒ acb ≡ cab

De façon équivalente, d’après Kazhdan et Lusztig, si w est un mot de longueur 3, on a w ≡ w′ où w′ = w si w est une ligne ou une colonne, et où, dans le cas contraire, w′ est l’unique mot ayant cette même propriété qui se déduise de w par permutation de deux lettres adjacentes.

L’algorithme de Schensted est une application directe des relations précédentes. P. Moszkowski en a donné une présentation originale qui rend extrèmement faciles les calculs à la main (un hommage à André Lentin !).

Première raison

Soit, dans ℤ(𝔸^{∗}), Λ_{k} la somme des colonnes de longueur k (= 1, 2, …, card(𝔸)). Les images dans Pol(𝔸) des Λ_{k} sont les fonctions symétriques élémentaires des lettres de 𝔸 et forment donc un ensemble minimal de générateurs de la sous-algèbre Sym(𝔸) des polynômes symétriques.

Par conséquent, si ∼ est une congruence sur 𝔸^{∗} commutant avec l’évaluation telle que les images des Λ_{k} dans ℤ(𝔸^{∗}/ ∼) commutent deux à deux, la sous-algèbre de ℤ(𝔸^{∗}/ ∼) qu’elles engendrent est isomorphe à Sym(𝔸).

Or cette condition sur ∼ admet deux solutions extrémales:

l’une est la congruence plaxique;

l’autre peut être récusée pour mille excellentes raisons, la plus simple étant peut être que le nombre de ses classes croît (avec la longueur des mots) beaucoup moins vîte que pour la congruence plaxique. La valeur de cette première raison est appuyée par le fait qu’une

variante des calculs précédents s’applique utilemement à certaines algèbres de Hecke (je fais ici allusion au monoide nilplaxique dont les relations de définition sont à peu près les mêmes que les relations plaxiques).

Un autre argument en faveur de la congruence plaxique est la propriété suivante, conséquence triviale de la définition, mais exceptionnelle parmi les monoïdes présentés. Notons v ∩ 𝔹^{∗} la restriction du mot v au sousalphabet 𝔹 (c’est-à-dire le sous-mot de v obtenu en y effaçant les lettres qui n’appartiennent pas à 𝔹). Dans le monoïde plaxique on a identiquement

w ≡ w′ ⇒ w ∩ 𝔹^{∗} ≡ w′ ∩ 𝔹^{∗}

pour chaque sous-intervalle 𝔹 de l’alphabet 𝔸.

Deuxième raison

Grâce à la théorie de Curtis Greene, nous savons associer à chaque mot w ∈ 𝔸^{∗} une partition p_{k} ≤ p_{k−1} ≤ ⋯ ≤ p_{1} de sa longueur n par la condition que p_{k} + p_{k−1} + ⋯ p_{i+1} soit le maximum de la longueur des sous-mots de w qui peuvent être obtenus en effaçant dans w i sous-mots qui sont des colonnes (i = 1, 2, …).

Notons ||w|| cette partition et appelons la forme plaxique de w. L’application w ⟶ ||w|| est une norme, en ce sens que l’on a identiquement

||ww′|| ≤ ||w|| ⊕ ||w′||

où ⊕ est l’addition des partitions au sens de Philipp Hall. C. Greene a observé que

w ≡ w′ ⇒ ||w|| = ||w′|| .

Mais réciproquement, on peut caractériser la congruence plaxique par la propriété d’être la congruence syntaxique de la norme ∥ ∥, c’est-à-dire d’être la congruence extrémale sur 𝔸^{∗} telle que deux éléments de chacune de ses classes aient même forme plaxique.

J’intercale ici une digression. Le produit ww′ de deux mots est franc ssi ∥ww′∥ = ∥w∥ ⊕ ∥w′∥ . Un contretableau (resp. tableau) est un mot qui est un produit franc de colonnes de longueurs non décroissantes (resp. non croissantes). La construction de Schensted montre que chaque classe plaxique contient un et un seul contretableau (et un et un seul tableau). Enfin l’ensemble des colonnes est un treillis distributif pour l’ordre v ⪯ v′ défini par v ⪯ v′ ssi il existe une injection non décroissante des lettres de v dans celles de v′.

Avec ces notations, un contretableau est simplement un produit v_{1}v_{2} ⋯ v_{k} de colonnes telles que v_{1} ⪯ v_{2} ⪯ ⋯ ⪯ v_{k}.

Comme on peut le penser, l’opération de shuffle sur les mots joue un grand rôle dans la théorie du monïde plaxique. Elle a permis à A. Lascoux de donner une version non commutative (dans ℤ(𝔸^{∗})) des fonctions symétriques, avec comme conséquence une compréhension meilleure de la structure de leur algèbre.

Troisième raison

Un quotient extrémalement voisin de Pol(𝔸) de l’algèbre ℤ(𝔸^{∗}) est obtenu en posant u ≈ u′ pour u, u′ ∈ ℤ(𝔸^{∗}) ssi uμ et u′μ coïncident en degré ≤ 2, où l’homomorphisme de Magnus μ consiste à remplacer chaque variable a ∈ 𝔸 par aμ = 1 + a. De façon équivalente, ℤ(𝔸^{∗}/ ≈) est isomorphe à l’algèbre de Lie libre nilpotente de classe 2, c’est-à-dire au quotient de ℤ(𝔸^{∗}) par l’idéal qui définit la condition que tous les commutants [b, a](= ba − ab) sont dans le centre.

La fonction génératrice de l’une des bases de ℤ(𝔸^{∗}/ ≈) est le produit de Cauchy

P = ∏_{a_{i}∈𝔸}(1 − a_{i})^{−1} ∏_{{a_{i}<a_{j} \atop a_{i},a_{j}∈𝔸}}(1 − a_{i}a_{j})^{−1}

(calculé dans l’algèbre commutative).

Comme P est la somme des fonctions de Schur sur 𝔸, cest-à-dire la somme des images commutatives des ”tableaux”, et comme ces derniers forment une section (= ensemble minnimal des représentants des classes) de la congruence plaxique ≡, on voit que 𝔸^{∗}/ ≡ admet P comme fonction génératrice (commutative). Les autres quotients de 𝔸^{∗} ayant la même propriété sont maintenant le domaine de Daniel Krob. Le monoïde plaxique est caractérisé parmi eux par la seule condition supplémentaire que, pour chaque mot w = a_{1}^{m_{1}}a_{2}^{m_{2}} ⋯ a_{h}^{m_{h}} ∈ 𝔸^{∗}, où l’un au moins des m_{i} est ≥ 2, il n’y ait qu’un seul mot qui soit seul dans sa classe de congruence parmi tous les mots ayant même évaluation (=image commutative) que w.

Une caractérisation dont la vérification est moins fastidieuse est que la congruence plaxique est la seule dont une section soit l’ensemble des tableaux.

Il y a certainement de meilleurs énoncés, mais les autres objets découverts par D.Krob sont fort hétéroclites et encore mal connus.

Telles étaient mes trois raisons pour affirmer la nécessité d’installer le monoïde plaxique parmi les structures remarquables. Il y en a une autre plus ténébreuse.

Il existe un monoïde présenté très évident dont les propriétés ne sont jamais données qu’à titre d’exercices mineurs. Il s’agit du monoïde cycliste B engendré par deux lettres a et b que relie la seule identité

ba = 1 .

Autrement dit, b est l’inverse à gauche de a.

Une section de B est formée des mots a^{n}b^{m} (n, m ∈ ℕ). Ses deux propriétés fondamentales sont:

– Tout quotient de B est isomorphe à ℤ (par a^{n}b^{m} ⟶ n − m) ou à un quotient de ℤ à travers le quotient précédent;

– B n’a pas d’idéaux stricts (c’est-à-dire 1 ∈ B x B) pour tout x ∈ B bien qu’il ne puisse pas être injecté dans un groupe, et tout monoïde sans idéaux stricts qui n’est pas un groupe contient au moins une copie de B. Cette deuxième propriété implique qu’aucun monoïde compact ne

contient une copie de B, donc que B n’admet aucune représentation linéaire de dimension finie.

Pour l’anecdote, je rappelle que B peut être défini comme le monoïde syntaxique du sous-ensemble des mots de {a, b}^{∗} dont tous les facteurs gauches contiennent au moins autant de b que de a.

Pour remonter B en un quotient de {a, b}^{∗} compatible avec le morphisme d’évaluation, on remplace la relation ba = 1 par les deux relations

(∗)  baa ≡ aba & bba ≡ bab

exprimant que ba commute avec a et b. Or ces nouvelles relations ne sont autres que celles définissant le monoïde plaxxique sur deux lettres aet b > a (dont une section est d’ailleurs l’ensemble des tableaux (ba)^{p}a^{n}b^{m}, (n, m, p ∈ ℤ) ).

Revenons au cas général de 𝔸 = {a_{1} < a_{2} < ⋯ < a_{n}}. Tenant compte de la propriété rappelée à la fin de la première raison, on définit une congruence ∼ sur 𝔸^{∗} par le morphisme envoyant chaque mot sur le produit direct de l’image dans le monoïde plaxique {a_{i}, a_{i+1}}^{∗}/ ≡ de sa restriction w ∩ {a_{i}, a_{i+1}}^{∗} (i = 1, 2, …). Le monoïde 𝔸^{∗}/ ∼ est le quotient cycliste du monoïde plaxique 𝔸^{∗}/ ≡. Il a été utilisé avec succès par A.Lascoux, B.Leclerc et J-Y.Thibon pour certains problèmes de représentations modulaires.

Reste à justifier les relations plaxiques élémentaires sur trois lettres, c’est-à-dire à retrouver ≡ parmi les congruences contenues dans ∼.

La seule manière que je connaisse est d’utiliser le fait que pour tout sous-alphabet 𝔹 ⊂ 𝔸, la colonne v_{𝔹} contenant toutes les lettres de 𝔹 engendre le centre du monoïde plaxique 𝔹^{∗}/ ≡.

J’aimerais beaucoup mieux une caractérisation du monoïde plaxique employant les prédicats utilisés pour énoncer les propriétés fondamentales du monoïde cycliste. Mais je ne sais pas le faire, bien que le quotient du monoïde plaxique par son centre n’ait pas d’idéaux propres.

Peut-être pourrait-on faire jouer le fait que pour chaque lettre c de 𝔸, chaque classe plaxique admet un unique facteur gauche de longueur maximale dont toutes les lettres sont ≥ c ?

Et demain?

En des lieux divers (le Japon, Strasbourg, le M.I.T., Marne La Vallée), les mathématiciens qui développent la théorie des groupes quantiques ont retrouvé le monoïde plaxique ou l’un de ses quotients comme cas particulier de leurs constructions : quand, dans leur poétique, ils font tendre la température q vers zéro pour les cristalliser.

J-Y. Thibon et B. Leclerc remontent les grands fleuves de ce continent qu’ils sont en train de découvrir. A. Lascoux organise l’expédition que je regarde partir de mon hamac, entre deux palétuviers dans l’estuaire.

Références

C.Greene: An extension of Schensted’s theorem, Advances in Math. 14 (1974) 254–265. C.Greene: Some partitions associated with a partially ordered set, J. Comb. Th. A 20 (1976) 69–79. D.Kazdhan, G.Lusztig: Representations of Coxeter groups and Hecke algebras, Inv. Math. 53 (1979) 165–184. D.Knuth: The Art of Computer Programming, Vol.3, Sorting and Searching, Addison-Wesley (1973). D.Krob, J-Y.Thibon: Representations of the Hecke algebra of type A and corepresentations of the quantum group A_{q}(n) at q = 0, and the hypoplactic algebra, prépublication L.I.T.P. (1995).

A.Lascoux, B.Leclerc, J-Y.Thibon: Crystal Graphs and q-analogues of weight multiplicities for the root system A_{n}, Letters in Math. Phys. 35(1995) 359-374. A.Lascoux, M.P.Schützeznberger: Le monoïde plaxique, Non commutative structures in Algebra and Combinatorics , Quaderni della Ricerca Scientifica del CNR, Roma (1981). P.Moszkowski: A bijection betwwen trees and factorizations of cyclic permutations, Europ. J. Combinatorics 10 (1989) 13–16. C.Schensted: Longest increasing and decreasing subsequences, Canadian J. Math. 13 (1961) 179–191.