Ordonner le Groupe Symétrique:

Pourquoi Utiliser l’Algèbre de Iwahori-Hecke ?

Alain Lascoux(*)

Abstract. The Bruhat order on the symmetric group is defined by means of subwords of reduced decompositions of permutations as products of simple transpositions. Ehresmann gave a different description by considering any permutation as a chain of sets and comparing componentwise the chains. A third method reduces the Bruhat order to the inclusion order on sets, by associating to any permutation a set of bigrassmannian permutations. This amounts to embed the symmetric group into a lattice which is distributive. The last manner to understand the Bruhat order is to use a distinguished linear basis of the Iwahori-Hecke algebra of the symmetric group, and this involves computing polynomials due to Kazhdan & Lusztig; we explicit these polynomials in the case of vexillary permutations.

1991 Mathematics Subject Classification: 05E10, 20C30 Keywords and Phrases: Symmetric group, Bruhat Order, Kazhdan-Lusztig Polynomials

1. Ordre par les sous-mots En tant que groupe de Coxeter, le groupe symétrique 𝔖(n) est engendré par les transpositions simples σ_{i}, i = 1 … n − 1, qui vérifient les relations de tresse

σ_{i}σ_{i+1}σ_{i} = σ_{i+1}σ_{i}σ_{i+1} et σ_{i}σ_{j} = σ_{j}σ_{i} , |i − j| > 1  (1.1)

ainsi que σ_{i}^{2} = 1.

Une décomposition réduite d’une permutation μ est un mot w^{ij...h} = σ_{i}σ_{j} ⋯ σ_{h}, dont le produit, de longueur minimale, est égal à μ (cette longueur est dite longueur ℓ(μ) de μ). Par définition (cf. [Hu]), l’ordre de Bruhat est l’ordre induit par les sous-mots :

ν ≤ μ ⇔ ∃w^{ij...h} = μ, w^{ij...h} réduit , ∃ ϵ, …, ϵ′′ ∈ {0, 1}, ν = σ_{i}^{ϵ} σ_{j}^{ϵ′} ⋯ σ_{h}^{ϵ′′} (1.2)

Soit σ une transposition simple telle que ℓ(μσ) > ℓ(μ). Alors on a la “propriété d’échange” :

[1, μ] = A ∪ B et [1, μσ] = A ∪ B ∪ Bσ  (1.3)

(*) C.N.R.S. où [1, μ] := {ν ∈ 𝔖(n), ν ≤ μ}, A := {ν : ν ≤ μ, νσ ≤ μ} et B := [1, μ] \ A.

Documenta Mathematica · Extra Volume ICM 1998 · III · 355–364

On définit, sur l’algèbre du groupe symétrique 𝔖(n), des opérateurs de réordonnement π_{1}, …, π_{n−1}, notés à droite

𝔖(n) ∋ μ ⟶^{π_{i}} \{ \begin{matrix}μ + μσ_{i} & si μ_{i} < μ_{i+1} \\ 0 & autrement \end{matrix}

Il est aisé de voir que pour toute décomposition réduite de μ, l’image de 1 par un produit de π_{i} est la somme des éléments de l’intervalle [1, μ] :

μ = σ_{i}σ_{j} ⋯ σ_{h} réduit ⇒ 1π_{i}π_{j} ⋯ π_{h} = ∑_{ν≤μ} ν  (1.4)

Deux décompositions réduites de la même permutation vont donner en général des ensembles de sous-mots différents et donc ces ensembles ne sont pas des invariants de la permutation.

Une autre manière que (1.4) de corriger cette non-canonicité est de pondérer les sous-mots. Etant données n variables x_{1}, …, x_{n}, on définit, à la suite de Yang [Ya],[Ch], une base linéaire Y_{μ}, μ ∈ 𝔖(n), de l’algèbre du groupe symétrique à coefficients rationnels en les x_{i}, par

ℓ(μσ_{i}) > ℓ(μ) ⇒ Y_{μσ_{i}} = Y_{μ} (σ_{i} + \frac{1}{x_{μ_{i+1}} − x_{μ_{i}}} ) .  (1.5)

Toute décomposition réduite w^{i...h} de μ fournit une factorisation de Y_{μ}, dont le développement est une somme impliquant tous les sous-mots de w^{i...h}. On vérifie de plus que le coefficient de ν dans Y_{μ} est non nul ssi ν ≤ μ.

En fait, les coefficients sont des spécialisations de polynômes en deux ensembles de variables ([LLT2], [F-K]). On peut les obtenir en définissant des opérateurs sur l’anneau des polynômes vérifiant les relations de tresse [L-S4], [L-S5]. Ces opérateurs fournissent à leur tour des bases distinguées de l’anneau des polynômes en tant que module libre sur l’anneau des polynômes symétriques [BGG] et l’ordre de Bruhat joue un rôle essentiel [L-S3] (les programmes sont disponibles comme librairie Maple [Ve]). On trouvera dans [L-P] l’étude analogue de l’anneau des polynômes comme module libre sur l’anneau des polynômes symétriques en les carrés des variables, qui correspond aux groupes hyperoctahedraux.

2. Ordre par projection Il existe un ordre naturel sur les sous-ensembles de {1, …, n} :

u, v ⊆ {1, …, n}, u ≤ v ⇔ ∃ une injection croissante de u dans v

Cet ordre permet de définir les tableaux de Young comme étant les chaînes croissantes d’ensembles d’entiers.

Ehresmann [Eh] induit à partir de cet ordre sur les ensembles, un ordre sur les cellules de Schubert de la variété de drapeaux pour le groupe linéaire (lesquelles sont en bijection avec les permutations) :

ν, μ ∈ 𝔖(n), ν ≤ μ ⇔ ∀i : 1 ≤ i ≤ n, {ν_{1}, …, ν_{i}} ≤ {μ_{1}, …, μ_{i}}  (2.1)

On peut disposer les ensembles {μ_{1}, …, μ_{i}} dans un tableau, dit clef de la permutation, dont ils sont les colonnes (décroissantes). Alors deux permutations sont comparables ssi leurs clefs le sont, composante à composante. De fait, on vérifie aisément par récurrence sur la longueur que l’ordre d’Ehresmann coincïde avec l’ordre de Bruhat.

La restriction μ → {μ_{1}, …, μ_{i}} peut s’interpréter comme la projection de 𝔖(n) sur 𝔖(n)/𝔖(i) × 𝔖(n − i), où 𝔖(i) × 𝔖(n − i) est le sous-groupe de Young engendré par σ_{1}, …, σ_{i−1}, σ_{i+1}, …, σ_{n−1}. On peut identifier les éléments de 𝔖(n)/𝔖(i)×𝔖(n−i) aux permutations γ (dites grassmanniennes) : γ_{1} < ⋯ < γ_{i}; γ_{i+1} < ⋯ < γ_{n}, ayant une descente en i. La restriction de l’ordre de Bruhat à ces dernières est

γ ≤ γ′ ⇔ γ_{1} ≤ γ′_{1}, …, γ_{i} ≤ γ′_{i}

Deodhar [De] a étendu à tous les groupes de Coxeter W la définition de l’ordre de Bruhat par relèvement de l’ordre sur les W/P, P parabolique. Proctor [Pr] a généralisé aux types B, C, D la construction des clefs.

3. Ordre par sous-ensembles Au lieu de considérer toutes les projections 𝔖(n) ↦ 𝔖(i) × 𝔖(n − i), i = 1, …, n − 1, on peut associer à toute permutation μ l’ensemble G(μ) des permutations grassmanniennes γ telles que γ ≤ μ. Le critère (2.1) se formule alors

ν ≤ μ ⇔ G(ν) ⊆ G(μ)  (3.1)

Cette définition n’est pas invariante par l’involution μ ↦ μ^{−1}, contrairement à l’ordre de Bruhat. Pour corriger cette disymétrie, on définit les permutations bigrassmanniennes comme étant les permutations qui sont grassmanniennes, ainsi que leurs inverses. En d’autres termes

β bigrassmannienne ⇔ ∃!i, ∃!j : ℓ(σ_{i}μ) < ℓ(μ), ℓ(μσ_{j}) < ℓ(μ)

(i est dit recul de β, et j descente).

Soit B(μ) l’ensemble des permutations bigrassmanniennes β telles que β ≤ μ. Le critère (3.1) est équivalent à

ν ≤ μ ⇔ B(ν) ⊆ B(μ)  (3.2)

En fait, on peut montrer que l’ensemble des bigrassmanniennes est optimal pour obtenir l’ordre de Bruhat par inclusion. Plus précisément, soit C ⊆ 𝔖(n). Pour que le morphisme 𝔖(n) → 2^{C} : μ → C ∩ [1, μ] soit un morphisme d’ordre injectif, il faut et il suffit que C contienne l’ensemble des bigrassmanniennes (cf. [L-S6]).

Pour les groupes de Coxeter finis, on trouvera dans [G-K] la détermination du sous-ensemble optimal codant l’ordre. Les élements de la “base de l’ordre” sont caractérisés par la propriété :

β appartient à la base ssi il existe un élément μ du groupe tel que β soit minimum dans le complémentaire de l’intervalle [1, μ] .

La même construction peut être étendue aux groupes de Coxeter affines (pour une description plus classique, voir [B-B] dans le cas du type A et [Er] plus généralement).

Toute permutation bigrassmannienne dans 𝔖(n) est une permutation du type [ 1, …, a, a + 1 + c, …, a + b + c, a + 1, …, a + c, a + b + c + 1, …, a + b + c + d] et donc définie par un vecteur [[a, b, c, d]] ∈ N^{4}, a, d ≥ 0, b, c ≥ 1, a + b + c + d = n.

La restriction de l’ordre de Bruhat aux bigrassmanniennes est

[[a, b, c, d]] ≤ [[a′, b′, c′, d′]] ⇔ a ≥ a′, d ≥ d′; b ≤ b′, c ≤ c′ .  (3.3)

Une permutation μ est supérieure à une bigrassmannienne β = [[a, b, c, d]] ssi l’ensemble {μ_{1}, …, μ_{a+b}} contient au moins b valeurs > a + c.

Le treillis engendré par les bigrassmanniennes (en tant que sup-irréductibles; de manière équivalente, on prend l’ensemble des unions quelconques de B(μ)) est dit treillis enveloppant du groupe symétrique, ou complétion de Mac Neille [Bi]. Les éléments de ce treillis sont par définition en correspondance bijective avec les antichaînes de bigrassmanniennes. Par exemple, pour 𝔖(4), il y a 10 bigrassmanniennes et 42 antichaînes, donc 42-24=18 éléments du treillis qui ne sont pas des permutations, l’ordre sur les bigrasmanniennes étant :

[[0, 3, 1, 0]] [[0, 2, 2, 0]] [[0, 1, 3, 0]] [[1, 2, 1, 0]] [[1, 1, 2, 0]] [[0, 2, 1, 1]] [[0, 1, 2, 1]] [[2, 1, 1, 0]] [[1, 1, 1, 1]] [[0, 1, 1, 2]]

Les éléments du treillis enveloppant peuvent aussi être identifiés aux supremums (composante à composante) d’une famille quelconque de clefs. Ces supremums sont des tableaux ayant des propriétés supplémentaires de croissances diagonales, que l’on appelle triangles monotones, et qui sont en bijection avec les matrices à signe alternant (alternating sign matrices), cf. [M-R-R], [An], [Zei].

Ainsi le supremum des bigrassmanniennes [[1, 2, 1, 0]], [[1, 1, 2, 0]], [[0, 2, 1, 1]], [[0, 1, 2, 1]] se représente par

( \begin{matrix}0 & 0 & 1 & 0 \\ 0 & 1 & −1 & 1 \\ 1 & −1 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} ) ↔ 3 4 4 4 2 3 3 1 2 1 = sup ( \begin{matrix}3 & 3 & 3 & 4 \\ & 2 & 2 & 3 \\ & & 1 & 2 \\ & & & 1 \end{matrix} et \begin{matrix}1 & 4 & 4 & 4 \\ & 1 & 3 & 3 \\ & & 1 & 2 \\ & & & 1 \end{matrix} )

et c’est de plus le supremum des deux permutations [3, 2, 1, 4] et [1, 4, 3, 2] dont nous avons donné les clefs à droite.

La lecture par colonnes, de gauche à droite, des tableaux ou des matrices donne la même suite d’ensembles : 1 ou -1 en ligne i signifie que la lettre i apparaît ou disparaît. Ainsi la matrice ci-dessus se lit : ” 3 apparaît; 2 et 4 apparaîssent, 3 disparaît; 1 et 3 apparaîssent, 2 disparaît; 2 revient enfin”.

On montre en outre que le treillis enveloppant du groupe symétrique est distributif [L-S6]. En d’autres termes, pour toute bigrassmannienne β, il existe une permutation η telle que 𝔖(n) est l’union disjointe des deux intervalles [1, η] et [β, ω], où ω est l’élément maximum de 𝔖(n). Par exemple, une permutation de 𝔖(4) est soit au dessus de β = [1, 4, 2, 3] = [[1, 1, 2, 0]], soit en dessous de [3, 2, 4, 1].

Codant chaque permutation par B(μ), ou par le vecteur booléen [v_{β}(μ)]_{β∈B} : v_{β}(μ) = 1 ou 0 selon que β ≤ μ ou non, on dispose ainsi d’un outil purement algébrique de calcul sur les intervalles pour l’ordre de Bruhat.

4. Algèbre de Hecke Au lieu d’énumérer, on peut se proposer au contraire de chercher à caractériser la fonction génératrice ∑_{ν≤μ}(−q)^{ℓ(μ)−ℓ(ν)} ν des éléments de l’intervalle [1, μ].

L’algèbre appropriée est cette fois-ci l’algèbre de Iwahori-Hecke H_{n} du groupe symétrique 𝔖(n), définie comme l’algèbre, à coefficients dans ℤ[q, 1/q], engendrée par les T_{1}, …, T_{n−1} satisfaisant les relations de tresse

T_{i}T_{i+1}T_{i} = T_{i+1}T_{i}T_{i+1} et T_{i}T_{j} = T_{j}T_{i} , |i − j| > 1  (4.2)

ainsi que la relation de Hecke

(T_{i} − q)(T_{i} + 1/q) = 0 , i = 1, …, n − 1 .  (4.3)

Une base linéaire de H_{n} consiste en les {T_{μ}, μ ∈ 𝔖(n)}, définies par produits réduits de T_{i}. Sur H_{n}, on a une involution T_{μ} ↦ (T_{μ^{−1}})^{−1}, q ↦ 1/q. Soit L le sous-module ⊕_{μ∈𝔖(n)}ℤ[q]T_{μ} et θ la projection L ↦ L/qL. Kazhdan & Lusztig (cf. [KL1], [Lu]) ont montré que pour chaque μ ∈ 𝔖(n), il existe un élément unique c_{μ} ∈ L qui soit invariant par l’involution et tel que θ(c_{μ}) = θ(T_{μ}). Les élements c_{μ}, μ ∈ 𝔖(n) constituent donc une base linéaire de H_{n}, et l’on a de plus

c_{μ} = ∑_{ν≤μ}(−q)^{ℓ(μ)−ℓ(ν)} P_{ν,μ}(q^{−2}) T_{ν} ,  (4.4)

les P_{ν,μ} étant des polynômes à coefficients entiers positifs, dits Polynômes de Kazhdan & Lusztig , qui interviennent dans de nombreuses théories [KL2], [Br].

Il est clair que { 1, T_{1} − q } est la base de Kazhdan & Lusztig de H_{2}. Plus généralement, posons c_{i} := T_{i} − q.

Tout produit c_{μ} c_{i} est invariant par l’involution, a pour terme dominant T_{μσ_{i}} si ℓ(μ σ_{i}) > ℓ(μ), et peut donc être considéré comme une approximation de c_{μσ_{i}}. On obtient c_{μσ_{i}} en soustrayant récursivement les multiples appropriés des c_{ν} pour les ν tels que le coefficient de T_{ν} comporte un terme constant.

Par exemple, c_{2,3,1} · c_{1} = (q^{2} + 1)T_{2,1,3} + T_{3,2,1} − qT_{3,1,2} − qT_{2,3,1} + q^{2}T_{1,3,2} − (q^{3} + q)T_{1,2,3} et c_{3,2,1} = c_{2,3,1}c_{1} − c_{2,1,3} = T_{3,2,1} − qT_{3,1,2} − qT_{2,3,1} + q^{2}T_{1,3,2} + q^{2}T_{3,1,2} − q^{3}T_{1,2,3}.

Cette récurrence élémentaire peut difficilement être mise en oeuvre dès n > 8 et il faut donc trouver des méthodes plus économiques qui n’imposent pas d’énumérer les éléments d’un intervalle.

En fait, pour tout i tel que ℓ(μ σ_{i}) < ℓ(μ), alors P_{ν,μ} = P_{νσ_{i},μ} , ∀ν ∈ 𝔖(n), et donc, comme l’indiquent [KL1], les polynômes P_{ν,μ} sont constants dans toute double classe 𝔖(I)\𝔖(n)/𝔖(J), où 𝔖(I), 𝔖(J) sont deux sous-groupes de Young déterminés par μ (𝔖(I) est le sous groupe engendré par les σ_{i}, i recul, et 𝔖(J) est engendré par les descentes).

L’invariance par rapport à deux sous-groupes de Young permet d’utiliser des propriétés de factorisation.

Soit ω = [n, …, 1], et pour 1 ≤ i < j ≤ n, ω[i, j] = [1, …, i − 1, j, …, i, j + 1, …, n]; posons pour tout entier positif [r] := (q^{r} − q^{−r})/(q − q^{−1}). Alors [DKLLST]

c_{ω} = ∑_{ν∈𝔖(n)}(−q)^{ℓ(ω)−ℓ(ν)} T_{ν} = c_{ω[1,n−1]} (T_{n−1} − \frac{q^{n−1}}{[n−1]}) ⋯ (T_{2} − \frac{q^{2}}{[2]})(T_{1} − \frac{q^{1}}{[1]})
= (T_{1} − \frac{q^{1}}{[1]}) ⋯ (T_{n−1} − \frac{q^{n−1}}{[n−1]}) c_{ω[2,n]}  (4.5)

Proposition Soit μ ∈ 𝔖(n); soient k l’entier tel que μ_{k} = n et ν ∈ 𝔖(n − 1) obtenue par effacement de n dans μ (ν est notée μ\n).

Si n = μ_{k} > μ_{k+1} > ⋯ > μ_{n}, alors

c_{μ} = c_{μ\n} (T_{n−1} − \frac{q^{n−k}}{[n−k]}) ⋯ (T_{k+1} − \frac{q^{2}}{[2]}) (T_{k} − \frac{q^{1}}{[1]})  (4.6)

Preuve L’élément de droite a pour terme dominant T_{μ}, et est invariant par l’involution. Par ailleurs, c_{ω[k,n−1]}(T_{n−1} − \frac{q^{n−k}}{[n−k]}) ⋯ (T_{1} − \frac{q^{1}}{[1]}) = c_{ω[k,n]} = c_{ω[k,n−1]}(T_{(n,k)}−qT_{(n,k+1)}+⋯+(−q)^{n−1−k}T_{(n,n−1)}+(−q)^{n−k}), somme sur toutes les transpositions de n avec i, i ≥ k. Le produit se développe en une somme où l’on retrouve comme coefficients les polynômes de Kazhdan-Lusztig pour ν; il est donc bien égal à c_{μ}

La proposition précédente, combinée aux involutions μ ↦ μ^{−1} et μ ↦ ωμω, permet de factoriser totalement certains c_{μ}. En particulier, une permutation μ est dite non singulière si μ ou μ^{−1} a la propriété qu’il existe k : μ_{k} = n > μ_{k+1} > ⋯ > μ_{n}, et μ\n est non singulière ([1] ∈ 𝔖(1) est décrétée non singulière).

Dans le premier cas, c_{μ} = c_{μ\n}(T_{n−1} − \frac{q^{n−k}}{[n−k]}) ⋯ (T_{k} − \frac{q^{1}}{[1]}). Dans le deuxième,

c_{μ} = (T_{k} − \frac{q^{1}}{[1]}) ⋯ (T_{n−1} − \frac{q^{n−k}}{[n−k]}) c_{[μ^{−1}\n]^{−1}}. Corollaire Si μ est une permutation non singulière, alors c_{μ} = ∑_{ν≤μ}(−q)^{ℓ(μ)−ℓ(ν)} T_{ν} et c_{μ} factorise en un produit de facteurs (T_{i} − \frac{q^{j}}{[j]}). Le polynôme de Poincaré de l’intervalle [1, μ] s’obtient, à une puissance de q près, en spécialisant T_{i} ↦ −1/q dans chaque facteur.

Par exemple, μ = [4, 1, 6, 5, 3, 2] est non singulière; écrivant k, k^{+}, k^{++} pour T_{k} − \frac{q^{1}}{[1]}, T_{k} − \frac{q^{2}}{[2]}, T_{k} − \frac{q^{3}}{[3]} respectivement, on obtient la suite d’égalités

c_{312} = 21 ↦ c_{4132} = 23^{+}(21) ↦ c_{41532} = (23^{+}21)4^{+}3 ↦ c_{416532} = (23^{+}214^{+}3)5^{++}4^{+}3

et le polynôme de Poincaré de l’intervalle [1, μ], en la variable q^{2}, est égal à

−q^{9} [2] \frac{[3]}{[2]} [2] [2] \frac{[3]}{[2]} [2] \frac{[4]}{[3]} \frac{[3]}{[2]} [2] = (1 + q^{2})^{2} (1 + q^{2} + q^{4})^{2} (1 + q^{2} + q^{4} + q^{6})

Par contre, c_{461532} = c_{416532} c_{2}, mais le polynôme de Poincaré de l’intervalle [123456, 461532] ne s’obtient pas en spécialisant T_{i} en −1/q, car [4, 6, 1, 5, 3, 2] est singulière.

La factorisation du polynôme de Poincaré, dans le cas non singulier, est due à Carrell et Peterson [Ca]. La caractérisation des variétés de Schubert non singulières est donnée par Lakshmibai et Seshadri [La-Se].

La densité du nombre de permutations non singulières tend vers 0 lorsque n tend vers l’infini. En fait, [La-Sa] ont montré que Proposition Dans 𝔖(4), seules [3, 4, 1, 2] et [4, 2, 3, 1] sont singulières et μ ∈ 𝔖(n) est non-singulière ssi l’image de μ par toute projection 𝔖(n) → 𝔖(4) est différente de ces deux permutations.

En d’autres termes, il y a deux types élémentaires de singularités. Dans ce qui suit, nous montrons que les constructions du paragraphe 3 permettent d’expliciter les polynômes P_{ν,μ} pour toutes les permutations évitant le motif [3, 4, 1, 2] (i.e. celles qui n’ont jamais [3, 4, 1, 2] comme image par projection).

Il est commode de changer les conventions, et de noter, pour μ, ν ∈ 𝔖(n), P_{μ}(ν)(q) := P_{νω,μω}(1/q^{2}).

Lorsque μ est bigrassmannienne, alors la variété de Schubert correspondante est dite déterminantale, et la géométrie, ou le calcul direct, montrent que les polynômes P_{μ}(ν) sont des polynômes de Gauss. Plus précisément, Lemme Soit μ = [[a, b, c, d]] une bigrassmannienne, et β^{i} := [[a−i, b+i, c+i, d−i]], si 0 ≤ i ≤ min(a, d), β^{i} := ∞ sinon. Soit k = min(b, c). Pour tout ν ≥ μ, il existe un unique i, dit niveau par rapport à μ = β^{0}, tel que ν ≥ β^{i} et ν ≱ β^{i+1}, et alors P_{μ}(ν) = \left[{k+i \atop i}\right] = (1 − q^{k+i}) ⋯ (1 − q^{k+1})/(1 − q) ⋯ (1 − q^{i}).

Les polynômes de Gauss correspondent à des arbres linéaires, mais plus généralement, il est facile d’associer à toute permutation grassmanienne γ un arbre ainsi qu’il est expliqué en [L-S2]. Soit en effet i la descente de γ; alors (γ_{1} − 1, γ_{2} − 2, …, γ_{i} − i) est une partition λ (croissante), et la lecture de la frontière nord-est du diagramme de Ferrers de λ donne un mot en a, b (a= pas vertical, b = pas horizonal), dont on extrait un sous-mot maximal de lettres appariées par couples successifs ba (cette opération est utilisée pour définir une action du groupe symétrique sur les mots [L-S1], ainsi qu’en théorie des graphes cristallins [K-N], [LLT1]).

Ainsi, pour γ = [1, 2, 7, 12, 15, 16, 17, 3, 4, 5, 6, 8, 9, 10, 11, 13, 14], on a λ = (0, 0, 4, 8, 10, 10, 10). La frontière se lit a^{2}b^{4}ab^{4}ab^{2}a^{3}. Disposant ce mot planairement de sorte à faire apparaître les appariements dans les horizontales, les lettres non appariées (à éliminer) étant dans la ligne supérieure

a a b b b  b b
b  a
b  a
b a  b a  b a
sous−mot  b a  b b a b b a a a

Ce dernier mot (bab^{2}ab^{2}a^{3}) est le parcours d’un arbre Γ (b = s’éloigner de la racine, a = s’en rapprocher). Soient α_{1}, …, α_{r} les branches terminales de Γ.

L’arbre Γ définit une fonction f_{Γ} : ℕ^{r} → ℕ[q] comme suit : un étiquetage E de Γ est un morphisme croissant de l’ensemble des arêtes de Γ dans ℕ et son poids p(E) est la somme des étiquettes. Alors (voir un exemple à la fin)

f_{Γ}(i_{1}, …, i_{r}) := ∑_{E∈E(i_{1},...,i_{r})} q^{p(E)} ,  (4.7)

somme sur toutes les étiquetages de Γ tels que les étiquettes de α_{1}, …, α_{r} soient majorées respectivement par i_{1}, …, i_{r}. Le résultat essentiel de [L-S2] est Proposition Soient γ une permutation grassmannienne, Γ l’arbre associé et r son nombre de branches terminales. Alors pour toute permutation ν, il existe des entiers i_{1}, …, i_{r} tels que

P_{γ}(ν) = f_{Γ}(i_{1}, …, i_{r}) .  (4.8)

Zelevinsky [Zel] a donné une désingularisation explicite des variétés de Schubert indicées par des permutations grassmanniennes, qui relève la construction combinatoire précédente.

Le code d’une permutation μ ∈ 𝔖(n) est le vecteur [c_{1}, …, c_{n}] ∈ ℕ^{n} tel que c_{i} = card({j > i, μ_{j} < μ_{i}}). Réordonnant le code en une partition, on peut donc associer à toute permutation μ un arbre Γ(μ), comme on l’a fait plus haut.

Le théorème suivant ([La]) montre que cet arbre continue à fournir tous les polynômes de Kazhdan & Lusztig dans le cas où μ est vexillaire, i.e. lorsqu’aucune projection de μ dans S(4) n’est égale à [2, 1, 4, 3].

Théorème Soient μ une permutation vexillaire, Γ l’arbre associé et β_{1}, …, β_{r} les bigrassmanniennes maximales dans [1, μ]. Alors pour tout ν ≥ μ, le polynôme de Kazhdan & Lusztig est égal à

P_{μ}(ν) = f_{Γ}(i_{1}, …, i_{r}) ,  (4.9)

où i_{1}, …, i_{r} sont les niveaux respectifs de ν par rapport à β_{1}, …, β_{r}.

En fait, dans le cas d’une permutation vexillaire, pour tout r-uple i_{1}, …, i_{r}, tel que β_{1}^{i_{1}}, …, β_{r}^{i_{r}} ≠ ∞, le supremum ζ^{I} de β_{1}^{i_{1}}, …, β_{r}^{i_{r}} (calculé dans le treillis enveloppant) est une permutation, d’après [L-S6]. Sous les hypothèses du théorème, on a alors P_{μ}(ν) = P_{μ}(ζ^{I}).

Par exemple, μ = [1, 5, 6, 2, 7, 3, 4, 8, 9] a pour code [033020000], qui se réordonne en la partition […, 0, 2, 3, 3]. La frontière de cette dernière se lit (⋯ aa) b b a b a a (bb ⋯) et le mot réduit bbabaa est le parcours de l’arbre

• ; | ; • ; ⋀ ; • •. Il y a deux bigrassmanniennes maximales en dessous de μ, qui sont

[1, 5, 6, 2, 3, 4, 7, 8, 9] = [[1, 2, 3, 3]] = β_{1} et [1, 2, 5, 6, 7, 3, 4, 8, 9] = [[2, 3, 2, 3]] = β_{2}. Le paramètre i_{1} ne peut prendre que les valeurs 0, 1, puisque β_{1}^{1} = [[0, 3, 4, 2]], β_{1}^{2} = ∞; par contre, i_{2} ∈ {0, 1, 2} puisque β_{2}^{1} = [[1, 4, 3, 1]], β_{2}^{2} = [[0, 5, 4, 0]], β_{2}^{3} = ∞.

Le supremum de β_{1}^{1} et β_{2}^{2} est ζ^{1,2} = β_{2}^{2} = [5, 6, 7, 8, 9, 1, 2, 3, 4]. Toute permutation ν au dessus de cette dernière va donner le même polynôme P_{μ}(ζ^{1,2}) = f_{Γ}(1, 2) = 1 + 2q + 2q^{2} + 2q^{3} + q^{4}, fourni par l’énumération

\begin{matrix}• \\ 0| \\ • \\ 0 & ⋀ & 0 \\ • • \\ q^{0} \end{matrix}  \begin{matrix}• \\ 0| \\ • \\ 0 & ⋀ & 1 \\ • • \\ q^{1} \end{matrix}  \begin{matrix}• \\ 0| \\ • \\ 1 & ⋀ & 0 \\ • • \\ q^{1} \end{matrix}  \begin{matrix}• \\ 0| \\ • \\ 0 & ⋀ & 2 \\ • • \\ q^{2} \end{matrix}  \begin{matrix}• \\ 0| \\ • \\ 1 & ⋀ & 1 \\ • • \\ q^{2} \end{matrix}  \begin{matrix}• \\ 0| \\ • \\ 1 & ⋀ & 2 \\ • • \\ q^{3} \end{matrix}  \begin{matrix}• \\ 1| \\ • \\ 1 & ⋀ & 1 \\ • • \\ q^{3} \end{matrix}  \begin{matrix}• \\ 1| \\ • \\ 1 & ⋀ & 2 \\ • • \\ q^{4} \end{matrix}

Bibliographie

[BGG] I.N. Bernstein, I.M. Gelfand, S.I. Gelfand, Schubert cells and the cohomology of the spaces G/P, Russian Math. Surveys 28 (1973), 1-26.

[Bi] G. Birkoff, Lattice theory, 3ème ed., Am. Math. Soc., Providence (1967). [B-B] A. Björner, F. Brenti, Affine permutations of type A, Electronic J. Comb. 3# R18 (1996).

[Br] F. Brenti, A combinatorial formula for Kazhdan-Lusztig polynomials, Invent. M. 118 (1994) 371-394.

[Ca] J. Carrell, The Bruhat graph of a Coxeter group, a conjecture of Deodhar, and rational smoothness of Schubert varieties, Proc. Symp. Pure M. 56 (1994)53–61.

[Ch] I.V. Cherednik, Quantum groups as hidden symmetries of classic representation theory, in Differential geometric methods in theoretical physics (A.I. Solomon ed.), World Scientific, Singapore, 1989, 47–54.

[De] V.V. Deodhar, Some characterizations of Bruhat ordering on a Coxeter group, Invent. Math. 39 (1977) 187–198.

[DKLLST] G. Duchamp, D. Krob, A. Lascoux, B. Leclerc, T. Scharf, J.-Y. Thibon, Euler-Poincaré characteristic and polynomial representations of Iwahori-Hecke algebras, Publ. RIMS Kyoto 31 (1995), 179–201.

[Eh] C. Ehresmann, Sur la topologie de certains espaces homogènes, Ann. Math. 35 (1934) 396–443.

[Er] H. Eriksson, Computational and combinatorial aspects of Coxeter groups, thèse, KTH Stockholm (1994). [F-K] S. Fomin, A.N. Kirillov, The Yang-Baxter equation, symmetric functions and Schubert polynomials, Proc. FPSAC Firenze, 1993, Discr. Math. 153 (1996) 123–143. [G-K] M. Geck, S. Kim, Bases for the Bruhat-Chevalley order on all finite Coxeter groups, J. of Algebra 197 (1997) 278–310.

[Hu] J.E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Adv.Math. 29, Cambridge Univ. Press (1990). [K-L1] D. Kazhdan, G. Lusztig, Representations of Coxeter groups and Hecke algebras Invent. M. 53 (1979) 165–184. [K-L2] D. Kazhdan, G. Lusztig, Schubert varieties and Poincaré duality Proc. Symp. Pure M. 34, A.M.S. (1980) 185–203. [K-N] M. Kashiwara, T. Nakashima, Crystal graphs for representations of the q-analogue of classical Lie algebras, RIMS preprint 767 (1991). [La-Sa] V. Lakshmibai, B. Sandhya, Criterion for smoothness of Schubert varieties, Proc.Indian Acad. Sc. M. 100 (1990) 45–52.

[La-Se] V. Lakshmibai, C.S. Seshadri, Geometry of G/P. Singular locus of a Schubert variety, Bull. A.M.S. 2 (1984) 363–366.

[La] A. Lascoux, Polynômes de Kazdhan-Lusztig pour les variétés de Schubert vexillaires, C.R. Acad. Sci. Paris, 321 (1995) 667–670.

[LLT1] A. Lascoux, B. Leclerc et J.Y. Thibon, Crystal graphs and q-analogues of weight multiplicities for root systems of type A_{n}, Letters in Math. Physics, 35 (1995) 359–374.

[LLT2] A. Lascoux, B. Leclerc et J.Y. Thibon, Flag Varieties and the Yang-Baxter Equation, Letters in Math. Phys. 40 (1997) 75–90. [L-P] A. Lascoux, P. Pragacz, Operator calculus for Q-polynomials and Schubert polynomials, à paraître aux Adv. in Math. (1998). [L-S1] A. Lascoux, M.P. Schützenberger, Le monoïde plaxique, in Non Commutative Structures, Napoli 1978, Quaderni della Ricerca, Roma 109 (1981) 129–156. [L-S2] A. Lascoux, M.P. Schützenberger, Polynômes de Kazdhan-Lusztig pour les grassmanniennes, Astérisque 87-88 (1981) 249–266. [L-S3] A. Lascoux, M.P. Schützenberger, Symmetry and Flag manifolds, in Invariant Theory, Springer L.N. 996 (1983) 118–144. [L-S4] A. Lascoux, M.P. Schützenberger, Symmetrization operators on polynomial rings, Funk. Anal. 21 (1987) 77–78. [L-S5] A. Lascoux, M.P. Schützenberger, Algèbre des différences divisées, Discrete Maths 99 (1992) 165–179. [L-S6] A. Lascoux, M.P. Schützenberger, Treillis et bases des groupes de Coxeter, Electronic J. of Comb. 3 # R27 (1996).

[Lu] G. Lusztig, Intersection Cohomology Methods in Representation Theory, ICM Tokyo (1990) 155–174.

[MRR] W.H. Mills, D.P. Robbins, H. Rumsey, Alternating sign matrices and descending plane partitions, J. Comb. Th. A (1983) 340-359.

[Pr] R.A. Proctor, Classical Bruhat orders and lexicographic shellability, J. Alg. 77 (1982) 104–126.

[Ve] S. Veigneau, ACE, an algebraic environment for the computer algebra system

MAPLE, http://phalanstere.univ-mlv.fr/∼ ace (1998).

[Ya] C.N. Yang, Some exact results for the many-body problem in one dimension with repulsive delta-function interaction, Phys. Rev. Lett. 19 (1967), 1312–1315.

[Zei] D. Zeilberger, Proof of the alternating sign matrix conjecture, Electronic J. of Comb. 3 # R13 (1996).

[Zel] A. Zelevinsky, Small resolutions of singularities of Schubert varieties Funct. Anal. Pry. 17 (1983) 142–144.

Alain Lascoux

C.N.R.S., Institut Gaspard Monge Université de Marne-la-Vallée, 5 Bd Descartes, Champs sur Marne, 77454 Marne La Vallee Cedex 2 FRANCE