Treillis et bases des groupes de Coxeter

Alain Lascoux(*) et Marcel-Paul Schützenberger

A Dominique Foata, pionnier de la combinatoire

à qui elle doit tant

1. Introduction. — Le présent travail est une contribution à l’étude de l’ordre fort ( dit aussi de Bruhat) dans un groupe de Coxeter fini W.

Les définitions et propriétés relatives aux treillis, aux ensembles ordonnés, aux bases et aux treillis enveloppants, &c. sont rassemblées de manière minimale dans la section 2, les preuves et quelques exemples étant présentés en annexe, également de façon minimale.

La base B d’un ensemble ordonné fini (X, ≤) est le plus petit sousensemble tel que la comparaison de deux éléments pour l’ordre ≤ soit donné par l’ordre d’inclusion des projections (dans 2^{B}) de ces éléments sur la base. La section 3 décrit les rapports entre les ordres faibles et fort sur les groupes de Coxeter, en les reliant à diverses algèbres de Hecke dégénérées. La base (pour l’ordre fort) est contenue dans l’ensemble de ce que nous appelons les bigrassmanniennes ( éléments w ∈ W tels qu’il existe une seule paire de générateurs σ, σ′ tels que ℓ(σμ) < ℓ(μ), ℓ(μσ′) < ℓ(μ)).

La section 4 détaille le cas du groupe symétrique, pour lequel l’ordre fort a été décrit par Ehresmann en termes d’objets combinatoires que nous appelons clefs. La base est exactement l’ensemble des bigrassmanniennes. Ces dernières dépendent de 4 paramètres (en incluant l’ordre n du groupe), et leur nombre est \binom{n+1}{3}. Nous montrons que le treillis enveloppant est distributif, en application d’un énoncé plus général sur les propriétés de clivage des treillis enveloppants.

Dans la section suivante, nous identifions les éléments du treillis enveloppant à des objets combinatoires très intéressants, les triangles, qui ont déjà été rencontrés dans un autre contexte, celui des matrices alternantes. Nous montrons que les permutations vexillaires se caractérisent de façon simple en terme de leur projection sur la base.

La section 6 utilise la même notion de clivage pour découper de façon itérée le groupe symétrique en intervalles remarquables, isomorphes aux intervalles inférieurs des bigrassmanniennes. Nous donnons les polynômes de Poincaré de ces intervalles.

La section 7 étend les résultats des sections 4 et 5 aux groupes de type B_{n}. Cette fois-ci, la base ne contient pas toutes les bigrassmanniennes,

(*) Soutenu par le PRC Math-Info et la bourse CEE n^{0} ERBCHRXCT930400 mais le treillis enveloppant reste distributif. Le treillis de B_{n} est en fait un sous-treillis du treillis enveloppant de 𝔖(2n).

Les bases de tous les groupes de Coxeter finis viennent d’être obtenues dans un article récent de M. Geck et S. Kim [G-Ki].

2. Treillis enveloppant. — Renvoyant les preuves à une annexe, nous nous limitons ici à énoncer les propriétés des treillis dont nous aurons besoin. La plupart de celles ci sont bien connues et nous faisons référence au grand traité de G.Birkhoff [Bi] ( et spécialement aux chapitres III et IX ) pour une théorie plus complète ainsi que pour les attributions de priorité.

Si (X, ≤) est un ensemble ordonné et x ∈ X, nous notons [x ≤] l’intervalle supérieur {y ∈ X : x ≤ y} et symétriquement, [≤ x] := {y ∈ X : y ≤ x]}. L’infimum ∧Y = Inf(Y) d’une partie Y de X est l’unique élément x ∈ X tel que

[≤ x] = ∩{[≤ y] : y ∈ Y }

s’il en existe un, et ∧Y = ∅ sinon. Symétriquement, le supremum ∨Y = Sup(Y) est l’unique x′ ∈ X tel que

[x′ ≤] = ∩{[y ≤] : y ∈ Y }

s’il en existe un, ∅ sinon.

Un ensemble ordonné (X, ≤) est un treillis (sous-entendu complet) ssi toute partie Y non vide admet un Inf ( et donc ausi un Sup, ainsi qu’on le voit facilement, en prenant le Inf de l’ensemble des z tels que Y ⊂ [≤ z] ).

C’est un théorème classique dû à Mac Neille qu’il existe un treillis minimal unique (T, ≤) et un isomorphisme d’ordre X → T commutant avec les opérations ∧ et ∨ quand leur valeur est un élément de X.

Ce treillis (T, ⊂) est la plus petite famille de parties de X qui contienne X, tous les intervalles supérieurs [x ≤], x ∈ X, et qui soit fermée par l’intersection ensembliste ∩. L’injection naturelle x ⟶ [x ≤] de (X, ≤) dans (T, ⊂) fait donc correspondre à l’opération Sup de (X, ≤) l’opération ∩ de (2^{X}, ⊂) qui est l’opération Inf de (T, ⊂); l’opération Inf de (X, ≤) correspond quant à elle au Sup de (T, ⊂), où cette dernière opération est définie de façon indirecte, ainsi que nous l’avons indiqué plus haut.

Nous appelerons T le treillis enveloppant de (X, ≤) bien que l’usage soit d’appeler T la “complétion de (X, ≤))”, parce que cette construction, qui ne fait appel à aucune hypothèse de finitude, constitue une généralisation naturelle de la construction de Dedekind (correspondant elle-même au cas où l’ordre sur X est un ordre total).

On sait que de façon équivalente dans le cas fini, un treillis fini est un monoide commutatif idempotent finiment engendré (pour l’une quelconque des deux opérations), la relation d’ordre et la seconde opération étant alors canoniquement construites en terme de la première opération.

L’apport de la théorie des treillis au présent travail consiste essentiellement en les deux définitions suivantes et la proposition 2.5 : Définition 2.1. — Une relation basique est un relation R entre deux ensembles B̄ et B telle que, en considérant R ∈ B̄ ×B comme une matrice booléenne, aucune ligne de R ne soit l’intersection de lignes, que la ligne composée entièrement de 1 n’appartienne pas à R, et que les conditions symétriques soient satisfaites par les colonnes de R. Définition 2.2. — La base B (resp. la cobase B̄ ) de (X, ≤) est l’ensemble des x ∈ X \∧X (resp. x ∈ X \∨X) tels que x ne puisse être obtenu comme le Sup (resp. le Inf) d’autres éléments, c’est-à-dire x ∈ B (resp. x ∈ B̄) si pour toute partie Y,

x ∉ Y ⇒ x ≠ Sup(Y) ( resp. x ≠ Inf(Y) ) .

Nous supposerons désormais que tous les ensembles considérés sont finis.

Nous utiliserons la caractérisation suivante de la base, qui permet le calcul de cette dernière par simple inspection des triples d’éléments de X, puisque l’assertion que x est minimal dans X \ [≤ z] pour un z ∉ [x ≤] équivaut à [< x] \ [≤ z] = ∅.

LEMME 2.3. — Un élément x ≠ ∧X appartient à la base B ssi il est un élément minimal de X \ [≤ z] pour au moins un z ∈ X.

Dans le cas particulier où (X, ≤) est un treillis, on a que x ∈ B ssi x couvre un et un seul élément de X, c’est-à-dire ssi x est un ∨-générateur.

La base satisfait de plus une propriété de minimalité :

PROPOSITION 2.4. — La projection β : X ∋ x → B ∩ [≤ x] ∈ (2^{B}, ⊂) est un isomorphisme d’ordre et l’on a B ⊂ C pour toute partie C de X ayant la même propriété.

Ceci permet de coder chaque élément x par l’ensemble des élements maximaux de x β, c’est à dire par ce que nous appelerons ses rectrices.

On a de même la projection β̄ de chaque élément de X sur la cobase. Soit R′ ⊂ B̄ ×B la relation définie par (b̄, b) ∈ R′ ssi b̄ ≥ b, c’est-à-dire,

de façon équivalente, ssi b ∈ b̄β ou b̄ ∈ bβ̄.

PROPOSITION 2.5. — La relation R′ est une relation basique.

Nous appelerons désormais la relation R′ précédente la relation basique de l’ensemble ordonné (X, ≤).

TH^{}ÉOR^{}ÈME 2.6. — Chaque ensemble ordonné a même relation basique que son treillis enveloppant.

Nous introduisons encore la Définition 2.7. — La paire d’éléments (x̄, x) de l’ensemble ordonné (X, ≤) clive X ssi X est l’union disjointe de [≤ x̄] et [x ≤].

Les clivages de X sont en bijection avec ceux de son treilis enveloppant, et les paires clivantes (x̄, x)sont nécessairement des éléments de B̄ × B, ce qui permet d’énoncer un résultat classique de Birkhoff sous la forme modifiée suivante:

TH^{}ÉOR^{}ÈME 2.8. — Une condition nécessaire et suffisante pour que le treillis enveloppant d’un ensemble ordonné (X, ≤) soit distributif est qu’il existe un isomorphisme d’ordre bijectif entre sa base et sa cobase tel que chaque paire d’éléments associés donne un clivage.

Comme il est bien connu, il y a bijection, pour un treillis distributif, entre les antichaînes de la restriction de la relation d’ordre à la base et les éléments du treillis: c’est un cas particulier de la correspondance entre les éléments et leurs rectrices.

3. Ordres sur les groupes de Coxeter et algèbres de Iwahori-Hecke dégénérées. — Soit (W, S) un groupe de Coxeter fini, S un système de générateurs. L’algèbre d’ Iwahori-Hecke H(W, p, q) est l’algèbre engendrée par des éléments T_{s} vérifiant les relations de Coxeter, plus les relations de Hecke (homogénéisées)

T_{s}^{2} = (p + q)T_{s} − pq ,

où p, q sont deux constantes commutant avec les T_{s}. Pour le groupe symétrique, nous nous sommes attachés à développer les cas T_{s}^{2} = 0 (différences divisées), T_{s}^{2} = T_{s} (différences divisées isobares), T_{s}^{2} = −T_{s}, sans oublier l’algèbre du groupe ( T_{s}^{2} = 1) , cf. [L-S 1], [L-S 2], et aussi [Ch] pour ce qui concerne les algèbres de Hecke affines.

Employons des notations différentes pour distinguer les quatre cas spéciaux ci-dessus (pour les valeurs des paramètres p, q respectivement égales à (0, 0), (0, 1), (0, −1) et (1, −1) ):

∂_{s} , π_{s} , π̄_{s} , s

vérifiant respectivement

∂_{s}^{2} = 0 , π_{s}^{2} = π_{s} , π̄_{s}^{2} = −π̄_{s} , s^{2} = 1 .

Pour chacune de ces algèbres, nous considérerons aussi le monoide engendré par les générateurs T_{i}.

L’algèbre d’ Iwahori-Hecke admet une base linéaire {T_{w}}_{w∈W}, en bijection avec les éléments du groupe, que nous noterons respectivement {∂_{w}}, {π_{w}}, {π̄_{w}} et {w} dans les cas spéciaux, l’algèbre étant elle-même H^{∂}, H^{π}, Hπ̄ et H^{s} respectivement.

Les ∂_{w} permettent de définir la longueur des éléments de W, les décompositions réduites et l’ordre faible droit ou gauche sur W. Définitions. — Etant donné w ∈ W, la longueur maximum d’une factorisation dans le monoide des ∂_{i}: ∂_{w} = ∂^{1}∂^{2} ⋯ ∂^{k} (en facteurs ≠ 1) est dite longueur de w et notée ℓ(w). Une factorisation de longueur maximum est telle que les facteurs ∂^{1}, …, ∂^{k} sont des générateurs. La factorisation correspondante dans W : w = s^{1} ⋯ s^{k} est une décomposition réduite de w.

Deux éléments sont comparables pour l’ordre faible droit : v ≤_{R} w ssi ∂_{v} est facteur gauche de ∂_{w}, i.e. s’il existe u ∈ W tel que

∂_{v} ∂_{u} = ∂_{w} .

Symétriquement, v ≤_{L} w ssi ∂_{v} est facteur droit de ∂_{w}.

Etant donnés deux éléments w, w′ de W, il existe un plus petit v ∈ W (pour l’ordre droit) tel que ∂_{v} ait pour facteur gauche ∂_{w} et ∂_{w′}. En d’autres termes, l’intersection des idéaux ∂_{w}H^{∂} et ∂_{w′}H^{∂} est un idéal principal ( = ∂_{v}H^{∂} ).

Similairement, il existe un plus grand facteur gauche ∂_{v} de ∂_{w} et ∂_{w′}. L’existence d’un plus grand facteur gauche et d’un plus petit commun

multiple signifie que W, muni de l’ordre <_{R}, est un treillis. Cette propriété a été montré par Guilbaud & Rosensthiel [G-R] pour le groupe symétrique, et est due à Björner pour les autres groupes de Coxeter finis [Bj].

Symétriquement, l’ordre faible gauche donne une deuxième structure de treillis, image de la précédente par inversion des permutations.

A chacune des deux structures de treillis correspond une base. Définitions. — Pour w ∈ W, l’ensemble des descentes (resp reculs) de w est le sous-ensemble des générateurs de W tels que ∂_{w}∂_{s} = 0 (resp.

∂_{s}∂_{w} = 0). Un élément est dit grassmannien s’il n’a qu’une descente. Une bigrassmannienne est un élément de W ayant une seule descente et un seul recul.

La base de W, muni de l’ordre <_{R}, est constituée des éléments grassmanniens, puisque ceux-ci sont exactement les w ∈ W ayant un et un seul successeur.

Soit s un générateur du groupe de Coxeter (W, S). Le sous-ensemble des éléments grassmanniens ayant s pour descente, auquel on adjoint l’identité, est un treillis pour l’ordre <_{L} (cf. [B-W]). Cet ensemble est usuellement noté W^{s}; ses éléments sont les représentants de longueur minimum des classes W / W (S\s), où W (S\s) est le parabolique engendré par tous les générateurs sauf s.

Le morphisme p_{s} : W → W^{s} qui à chaque élément de W associe l’élément de longueur minimum de sa classe modulo W (S \ s) est défini par

p_{s}(w) = g ⇔ ∂_{g} est le plus grand facteur gauche de w, g ∈ W^{s}

Il est équivalent de rechercher les décompositions ∂_{w} = ∂_{g} ∂_{v}, v ∈ W (S \s), telles que ∂_{v} soit de longueur maximale parmi les facteurs droits de ∂_{w} appartenant à W (S \ s).

On peut aussi munir W du plus petit ordre ( ordre bifaible ) contenant <_{L} et <_{R} et étudier les propriétés des facteurs des ∂_{w}.

La considération des sous-mots conduit, quant à elle, à définir un ordre dit fort ou de Bruhat que nous noterons désormais ≤ . Définitions. — On a a v ≤ w ssi ∂_{v} est un sous-mot de ∂_{w}, i.e. s’il existe deux factorisations

∂_{v} = ∂_{v_{1}} ∂_{v_{2}} ⋯ ∂_{v_{k}} et ∂_{w} = ∂_{w′} ∂_{v_{1}} ∂_{w′′} ∂_{v_{2}} ∂_{w′′′} ⋯ ∂_{v_{k}} ∂_{w′′′′}.

Il suffit en fait de ne considérer que les sous-mots d’une seule décomposition réduite arbitraire de w pour obtenir tous les éléments v ≤ w (cf. [Bo]).

Les idéaux d’ordre pour l’ordre fort se décrivent aisément dans l’algèbre Hπ̄. On a en effet la récurrence suivante ([Vr]):

LEMME 3.1. — Soient w ∈ W, s ∈ S, tels que ℓ(w) < ℓ(ws). Alors l’intervalle inférieur [≤ w] se décompose en deux sous-ensembles {v : v < w, vs < w} et {u : u ≤ w, us ≮ w}, et l’intervalle [≤ ws] est égal à

[≤ w] ∪ {us : u ≤ w, us ≮ w} .

COROLLAIRE 3.2. — Pour tout w,

π_{w} = ∑_{v≤w} π̄_{v}

et

π̄_{w} = ∑_{v≤w} (−1)^{ℓ(w)−ℓ(v)} π_{v} .

En effet, soient v et s tels que ℓ(v) < ℓ(vs). Alors (π̄_{v}+π̄_{vs})π_{s} = π̄_{v}+π̄_{vs}, π̄_{v}π_{s} = π̄_{v} + π̄_{vs}; (π_{vs} − π_{v})π̄_{s} = −π_{vs} + π_{v}, π_{v}π̄_{s} = π_{vs} − π_{v}

Ce corollaire est utilisé de manière essentielle par Fokko du Cloux [Fo] pour implémenter l’ordre fort sur les groupes de Coxeter.

L’ordre fort peut s’obtenir à partir de la restriction de l’ordre aux sousensembles W^{s}, s ∈ S, ainsi que l’établit le lemme suivant dû à Deodhar [De], qui généralise la définition géométrique de l’ordre fort donnée par Ehresmann [Eh] pour le groupe symétrique.

LEMME 3.3. — Soient v, w ∈ W. Alors w ≥ v ssi pour tout s ∈ S, p_{s}(w) ≥ p_{s}(v).

Comme les morphismes p_{s} sont des morphismes d’ordre, on peut écrire la propriété précédente

(3.4)  w ≥ v ⇔ ∀s ∈ S, w ≥ p_{s}(v)

Plus symétriquement en la droite et la gauche, soient deux générateurs r, s ∈ S et^{r}W^{s} l’ensemble des bigrassmanniennes ayant recul r, descente s, ensemble auquel on adjoint l’identité. Cet ensemble est formé des éléments minimaux des classes W (S\r) \ W / W (S\s).

On dispose d’une projection p_{r,s} : W → ^{r}W^{s} telle que

p_{r,s}(w) = g ⇔ ∂_{w} = ∂_{w′}∂_{g}∂_{w′′} ,

où ∂_{g} est un facteur de ∂_{w} de plus grande longueur parmi les g ∈ ^{r}W^{s}.

L’unicité d’un tel facteur provient de ce que les deux projections W → W / (S\s) et W → W (S\r) \ W commutent.

La propriété (3.4) implique

(3.5)  w ≥ v ⇔ ∀r, ∀s ∈ S, w ≥ p_{r,s}(v) .

A tout élément w ∈ W, on associe l’élément

p_{G}(w) := {g ∈ G, g ≤ w} ⊆ 2^{G} ,

où G est l’ensemble des bigrassmanniennes.

TH^{}ÉOR^{}ÉME 3.6. — Soit (W, S) un groupe de Coxeter fini. Alors la base B de W, en tant qu’ensemble muni de l’ordre fort, est contenue dans l’ensemble G des bigrassmanniennes.

Une bigrassmannienne b ayant recul r et descente s appartient à la base ssi elle n’est pas le supremum d’un sous-ensemble de bigrassamnniennes (≠ b) de mêmes descente et recul.

Preuve. — La propriété (3.5) implique que p_{G} soit un morphisme d’ordre. En outre p_{G} est injectif, car chaque élément w est déterminé par l’ensemble des p_{r,s}(w) , r, s ∈ S, qui est un sous-ensemble de p_{G}(w). La caractérisation par minimalité de la base donnée en (2.4) implique que G contienne la base.

Les éléments de l’ensemble W \B sont les éléments de W dont l’ensemble des rectrices est de cardinal ≠ 1. Soit g une bigrassmanienne de descente s et recul r, et soit {b_{1}, …, b_{k}} l’ensemble de ses rectrices. Supposons que k > 1. Alors tous les b_{i}, i = 1 … k, ont mêmes descente et recul que g . En effet, s’il existe i tel que b_{i} ait descente s′ ≠ s, alors b_{i} > b_{i}s′ et w < ws′. Soient b_{k+1}, …, b_{h} les rectrices de b_{i}s′. La condition w ≥ b_{i} est équivalente à w ≥ b_{i}s′, elle même équivalente à w ≥ b_{k+1}, …, w ≥ b_{h}. L’élément w est donc le supremum de l’ensemble {b_{1}, …, b_{i−1}, b_{i+1}, …, b_{h}}, ce qui est impossible puisque cet ensemble ne contient pas la rectrice b_{i}.

Réciproquement, si une bigrassmannienne dans ^{r}W^{s} est le supremum de {g_{1}, …, g_{k}} ⊆ ^{r}W^{s}, k > 1, alors elle est le supremum de leurs rectrices qui appartiennent toutes à ^{r}W^{s}. Ainsi donc une bigrassmannienne de descente s et recul r n’appartient pas à la base ssi elle est le supremum d’un ensemble de cardinal > 1 de bigrassmanniennes dans ^{r}W^{s} deux à deux incomparables

Nous détaillons par la suite les bases des groupes classiques de type A_{n} et B_{n}.

4. Ehresmannoedre. — L’ordre fort, dit aussi de Bruhat, sur le groupe symétrique est usuellement défini comme la clôture transitive des relations de consécutivité

{ν → μ} ⇔ {∃τ : μ = ντ , ℓ(μ) = ℓ(ν) + 1} ,

où ν, μ sont deux permutations et τ une transposition, plutôt que par sous-mots des décompositions réduites comme au paragraphe 2.

Le groupe symétrique, muni de cet ordre, est dit Ehresmannoedre. Nous allons voir que sa base consiste en l’ensemble des bigrassmanniennes. La base est donc exactement l’intersection des bases pour les ordres faibles droit et gauche.

La définition originelle d’Ehresmann [Eh] de l’ordre sur le groupe symétrique repose quant à elle sur la comparaison des ensembles.

Deux sous-ensembles A et B d’un ensemble totalement ordonné sont comparables : A ≤ B ssi il existe un morphisme injectif de A dans B. Une suite d’ensembles se représente planairement par une suite de colonnes décroissantes justifiée par le haut, ces colonnes étant les ensembles réordonnés composant la suite. La suite d’ensembles est une chaîne (i.e. est croissante) si l’objet planaire est un contretableau, i.e. si les colonnes sont de longueurs croissantes, et si toutes les lignes sont croissantes de gauche à droite.

Etant donnés deux contretableaux t et t′ de même forme, on dit que t ≤ t′ ssi chaque composante de t est inférieure à la composante de t′ situéee au même endroit. On notera que la restriction de l’ordre au sousensemble des colonnes coïncide bien avec l’ordre sur les ensembles sousjacents.

Les facteurs gauches successifs d’une permutation μ sont une suite d’ ensembles emboîtés (un drapeau ). Le contretableau associé est dit clef(μ).

Ainsi μ = 2413 a pour clef

2 4 4 4 2 2 3 1 2 1

Le lemme suivant montre que l’ordre fort coïncide avec la comparaison des clefs, qui est la définition choisie par Ehresmann.

LEMME 4.1. — μ ≤ ν ssi clef(μ) ≤ clef(ν)

Chaque colonne de la clef d’une permutation détermine une permutation grassmannienne. Ansi la clef de μ = 2413 correspond-elle à la suite des grassmanniennes 2 143, 24 13, 124 3, 1234. La comparaison de deux clefs correspond donc à la comparaison de grassmanniennes ayant même descentes. C’est aussi la comparaison des partitions obtenues en soustrayant 1, 2 … aux colonnes de la clef.

De manière symétrique, la comparaison des inverses des permutations peut se décrire en coupant l’alphabet {1, …, n} en deux intervalles. Soit en effet {x < y} un alphabet à deux lettres, et p_{h} la projection de 𝔖(n) (considéré comme un ensemble de mots en 1, …, n) sur le monoïde {x, y}^{∗} induite par le morphisme

i → x si i ≤ h , i → y si i > h .

L’ordre sur les mots en {x, y} se définit en comparant les degrés en y des facteurs gauches respectifs de même longueur des deux mots :

v ≤ w si {v = v′v′′, w = w′w′′, |v′| = |w′|} ⇒ |v′|_{y} = |w′|_{y} .

On a alors

LEMME 4.2. — μ ≤ ν ssi pour tout h, tout k,

| p_{h}(μ_{1} ⋯ μ_{k}) |_{y} ≤ | p_{h}(ν_{1} ⋯ ν_{k} |_{y} .

Ainsi 2143 ≤ 4132, car, écrivant {1 … i|i + 1 … n} pour la projection 1, …, i → x, i + 1, …, n → y, on a : pour {1 | 234}, yxyy ≤ yxyy; pour {12 | 34}, xxyy ≤ yxyx; pour {123 | 4}, xxyx ≤ yxxx.

Le lemme 4.2 n’est autre que l’explicitation des projections p_{hk} (vues en 3.5) de 𝔖(n) sur l’ensemble des éléments de longueur minimum des classes 𝔖(h) × 𝔖(n − h) \ 𝔖(n) / 𝔖(k) × 𝔖(n − k).

On peut maintenant rétablir la symétrie (pour l’inversion des permutations) de l’Ehresmannoedre, qu’avait mise à mal la comparaison des clefs de μ et ν.

Voyons tout d’abord la comparaison d’une permutation et d’une bigrassmannienne. Comme une bigrassmannienne b de 𝔖(n) est une permutation qui a pour code un rectangle 0^{r_{0}}r_{2}^{r_{1}}0^{r_{3}}, avec r_{0} + r_{1} + r_{2} + r_{3} = n, r_{1} ≥ 1, r_{2} ≥ 1, on la désignera plutôt par le symbole b = [r_{0}, r_{1}, r_{2}, r_{3}]. Alors

LEMME 4.3. — Une permutation μ est supérieure à une bigrassmannienne b = [r_{0}, r_{1}, r_{2}, r_{3}] ssi il y a au moins r_{1} valeurs > r_{0} + r_{2} dans le facteur gauche de longueur r_{0} + r_{1} de μ.

Preuve. — On utilise le critère 4.2. Pour la coupure de l’alphabet {1 ⋯ r_{0}+ r_{2} | r_{0} + r_{2} + 1 ⋯ n}, le mot x^{r_{0}}y^{r_{1}}x^{r_{2}}y^{r_{3}} = p_{r_{0}+r_{2}}(b) est clairement le minimum des p_{r_{0}+r_{2}}(μ), pour μ ≥ b.

On peut tout autant optimiser la négation NEG de la condition μ ≥ b ( nous prions le lecteur de se reporter à la dernière partie de l’annexe où est traitée la notion de clivage). En effet, le mot y^{r_{1}−1}x^{r_{0}+1}y^{r_{3}+1}x^{r_{2}−1} est le maximum des p_{r_{0}+r_{2}}(ζ), ζ ≱ b, et a pour maximum dans sa fibre la permutation c_{[r_{0}r_{1}r_{2}r_{3}]} = n ⋯ (n−r_{1} +2)(r_{0} +r_{2}) ⋯ r_{2}(r_{0} +r_{2} +r_{3} +1) ⋯ (r_{0} +r_{2} +1)(r_{2} −1) ⋯ 1.

Ainsi donc les bigrasmanniennes constituent la base de l’Ehresmannoedre, car à chaque bigrassmannienne b correspond bijectivement une cobigrassmannienne qui est le Sup du complémentaire de l’intervalle supérieur [b ≤]. En d’autres termes, on a le théorème suivant.

TH^{}ÉOR^{}ÈME 4.4. — Le treillis enveloppant du groupe symétrique est distributif et a pour générateur les bigrassmanniennes.

Plus précisément, soit [r_{0}, r_{1}, r_{2}, r_{3}] ∈ ℕ^{4}, r_{1}, r_{2} ≥ 1, r_{0} +r_{1} +r_{2} +r_{3} = n. Alors le groupe symétrique 𝔖(n) clive en les deux intervalles [b ≤] et [≤ c], où b et c sont les bigrassmannienne et cobigrassmannienne codées par [r_{0}, r_{1}, r_{2}, r_{3}].

Une permutation μ appartient à l’un ou l’autre de ces deux intervalles selon que la composante de sa clef de coordonnées r_{0} + r_{1}, r_{1} ( pour les axes ↓^{→}) est strictement supérieure à r_{0} + r_{2} ou non.

Pour 𝔖(4), l’ensemble B des bigrassmanniennes est :

{2134, 1324, 1243, 1342, 1423, 2314, 3124, 2341, 4123, 3412}

La restriction de la relation d’incidence à 𝔖(4) × B, dont les lignes sont les projections par β des éléments sur la base B est représentée par la matrice:

4321 : 1 1 1 1 1 1 1 1 1 1
4312 : 1 1 1 0 1 1 1 1 1 1
4231 : 1 0 1 1 1 1 1 1 1 1
4213 : 1 0 1 0 1 1 1 0 1 1
4132 : 1 0 1 0 0 1 1 1 1 1
4123 : 1 0 1 0 0 1 1 0 1 1
3421 : 0 1 1 1 1 1 1 1 1 1
3412 : 0 1 1 0 1 1 1 1 1 1
3241 : 0 0 1 1 1 1 0 1 1 1
3214 : 0 0 1 0 1 1 0 0 1 0
3142 : 0 0 1 0 0 1 0 1 1 1
3124 : 0 0 1 0 0 1 0 0 1 0
2431 : 0 0 0 1 1 1 1 1 1 1
2413 : 0 0 0 0 1 1 1 0 1 1
2341 : 0 0 0 1 1 1 0 1 1 1
2314 : 0 0 0 0 1 1 0 0 1 0
2143 : 0 0 0 0 0 1 0 0 0 1
2134 : 0 0 0 0 0 1 0 0 0 0
1432 : 0 0 0 0 0 0 1 1 1 1
1423 : 0 0 0 0 0 0 1 0 1 1
1342 : 0 0 0 0 0 0 0 1 1 1
1324 : 0 0 0 0 0 0 0 0 1 0
1243 : 0 0 0 0 0 0 0 0 0 1
1234 : 0 0 0 0 0 0 0 0 0 0

Enfin, les dix clivages correspondant aux bigrassmanniennes sont :

𝔖(4) = [2134 ≤] ∪ [≤ 1432] = [1324 ≤] ∪ [≤ 2143] = [1243 ≤] ∪ [≤ 3214]
= [1342 ≤] ∪ [≤ 4213] = [1423 ≤] ∪ [≤ 3241] = [2314 ≤] ∪ [≤ 4132]
= [3124 ≤] ∪ [≤ 2431] = [2341 ≤] ∪ [≤ 4312] = [4123 ≤] ∪ [≤ 3421]
= [3412 ≤] ∪ [≤ 4231]

Par ailleurs, les bigrassmanniennes étant codées bijectivement par les vecteurs [r_{0}, r_{1}, r_{2}, r_{3}] ∈ ℕ^{4}, r_{1}, r_{2} ≥ 1, la fonction génératrice du nombre de bigrassmanniennes, pour n variable, est

∑_{n≥2} z^{n−2}card(Base(𝔖(n))) = (1 − z)^{−4}

L’image d’une permutation par la projection p_{ij} vue en 3.5 est soit l’identité, soit une bigrassmannienne b ayant recul i et descente j (i.e. b a le sous-mot i+1… i et b_{j} > b_{j+1}). En outre, si b est une bigrassmannienne de recul i et descente j, alors b ≤ μ ⇒ b ≤ p_{ij}(μ). Les rectrices d’une permutation μ sont donc les éléments maximaux de l’ensemble {p_{ij}(μ)}_{1≤i,j≤n−1}. Il existe un algorithme pour déterminer ces rectrices, sans calculer l’ensemble précédent, qui repose sur le lemme suivant:

LEMME 4.5. — Il y a bijection entre les rectrices d’une permutation μ et les triples d’entiers i ≤ j < j + 1 ≤ k tels que

μ_{j+1} ≤ μ_{k} < μ_{i} = 1 + μ_{k} ≤ μ_{j} .

A un tel triple correspond la rectrice b = [r_{0}, r_{1}, r_{2}, r_{3}], où r_{0} = card{h < j : μ_{h} < μ_{k}}, r_{1} = j − r_{0}, r_{2} = μ_{k} − r_{0}.

Nous laissons au lecteur le soin de vérifier que la bigrassmannienne associée au couple : descente (μ_{j} > μ_{j+1}), recul (μ_{k} + 1 … μ_{k}) est bien maximale sous les hypothèses du lemme 4.5.

Graphiquement, une rectrice b correspond à une configuration

nord

⋮ ⋮ ⋮ ⋮  ⋮ ⋮ ⋮ ⋮
⋯ μ_{j}  ⋯
⋮ ⋮ ⋮ ⋮  ⋮ ⋮ ⋮ ⋮
· μ_{i} · ·  ⋯
ouest ⋯ b  · · μ_{k} · est
⋮ ⋮ ⋮ ⋮  ⋮ ⋮ ⋮ ⋮
⋯ μ_{j+1} ⋯
⋮ ⋮ ⋮ ⋮  ⋮ ⋮ ⋮ ⋮
places · i · j j + 1 · k ·

pour les axes de coordonnées cartésiens ↑_{→}, le couple (μ_{k}, j) étant dit les coordonnées de la rectrice.

Outre l’ordre de Bruhat, on peut lire certaines propriétés des permutations sur l’ensemble de leurs rectrices. Par exemple, la proposition suivante décrit l’appartenance à un sous-groupe de Young, sous des conditions que l’on peut qualifier de géographiques car elles ne font intervenir que les coordonnées r_{0} + r_{1}, r_{0} + r_{2} des rectrices.

PROPOSITION 4.6. — Soit μ une permutation, R = R′ ⊎ R′′ une décomposition de l’ensemble de ses rectrices ( R′, R′′ ≠ ∅).

Soient n_{1}, n_{2} deux entiers tels que

\begin{aligned}r_{0} + r_{1} & ≤ n_{1} & & & r_{0} + r_{2} & ≤ n_{2} & si [r_{0}, r_{1}, r_{2}, r_{3}] ∈ R′ \\ & > n_{1} & & & > n_{2} & sinon \end{aligned}

Alors il existe un entier n_{3} tel que l’on ait les mêmes relations en remplaçant (n_{1}, n_{2}) par (n_{3}, n_{3}), et μ appartient au sous-groupe 𝔖(n_{3}) × 𝔖(n − n_{3}).

Preuve. — Soient n_{4} et n_{5} les deux entiers : n_{4} = Max({μ_{j} : il existe une rectrice de μ dans R′ avec r_{0} + r_{1} = j}) ; n_{5} = Max({kj: il existe une rectrice de μ dans R′ avec r_{0} + r_{2} = μ_{k}}) .

Par maximalité de n_{4} = μ_{j}, on a μ_{j} > μ_{j+1}. D’après le lemme 4.5 et l’hypothèse 4.6, on a μ_{j+1} < n_{2}. Pour les mêmes raisons, on a aussi μ_{k} > n_{4} pour tout h > n_{1}, ce qui entraine que les zones ⋆ ne contiennent pas de point (i, μ_{i}):

⋆ ⋆ ⋆ ⋆ · · · · ·
⋆ ⋆ ⋆ ⋆ · · · · ·
⋆ ⋆ ⋆ ⋆ · · · · ·
n_{4} ⋯ ⋆ ⋆ ⋆ ⋆ ⋆
n_{2} ⋯ ⋆ ⋆ ⋆ ⋆ ⋆
· · · · · · · · ·
· · · · · · · · ·
· · · · · · · · ·
· · · · · · · · ·
j n_{1}

Le même argument s’applique à n_{5} grâce à la symétrie μ → μ^{−1}. Le domaine permis pour les points (i, μ_{i}) est donc finalement (zone “·”) :

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ · ·
⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ · ·
⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ · ·
n_{4} ⋯ ⋆ ⋆ ⋆ ⋆ ⋆
n_{2} ⋯ ⋆ ⋆ ⋆ ⋆ ⋆
· · · · · · · ⋆ ⋆
· · · · · · · ⋆ ⋆
· · · · · · · ⋆ ⋆
· · · · · · · ⋆ ⋆
j n_{1}  n_{5}

Ceci montre que n_{3} = Max(n_{4}, n_{5}) satisfait l’énoncé 4.6, et que i ≤ n_{3} ⇒ μ_{i} ≤ n_{3}

5. Triangles. — On peut identifier chaque permutation μ à sa clef K(μ). La comparaison d’une permutation μ et d’une bigrassmannienne b = [r0, r_{1}, r_{2}, r_{3}] se réduit à tester une seule composante de K(μ), d’après le théorème 4.4 :

(5.1)  μ ≥ b ssi K(μ)_{r0+r1,r_{1}} > r_{0} + r_{2} .

Le Sup ou l’ Inf, dans le treillis enveloppant, d’une famille {μ} de permutations se calcule aisément, étant le Sup ou l’Inf composante à composante des {K(μ)}.

Plus précisément, un contretableau t de forme 12 ⋯ n est le sup de la famille {μ} ssi

∀i, j : 1 ≤ i ≤ j ≤ n, t_{ij} = Sup_{μ}{K(μ)_{ij}} .

Il est aisé de contrôler qu’un tel contre-tableau vérifie, pour chaque soustriangle élémentaire ( i.e. triple de composantes adjacentes de coordonnées respectives (i, j), (i, j + 1) et (i + 1, j + 1) pour les axes ↓^{→}) les inégalités suivantes

(5.2)  _{x}^{yz} ⇒ {x < z & x ≤ y & y ≤ z} .

Réciproquement, tout contre-tableau de forme 12 ⋯ n vérifiant les conditions 5.2 ( que l’on appelera triangle) est le Sup de la famille de bigrassmanniennes déterminée par chacune de ses composantes :

(5.3)  t_{ij} → b = [j − i, i, t_{ij} + i − j − 1, n − t_{ij} − i + 1]

On a donc

LEMME 5.4. — Le treillis enveloppant du groupe symétrique 𝔖(n) est isomorphe au treillis des triangles de forme 12 ⋯ n, remplis avec des lettres dans {1, 2, …, n}.

D’après les travaux de Mills, Robbins & Rumsey [MRR] les triangles (qu’ils appellent triangles monotones) sont en bijection avec les matrices alternantes, dont le cardinal, pour l’ordre n, est

∏_{0}^{n−1}(3k + 1)! / (n + k)!

Cette formule, qu’ils conjecturaient, a depuis été prouvée.

Pour 𝔖(3), le treillis enveloppant comprend un seul élément qui n’est pas une permutation : c’est le Sup de 213 ↔ _{1}^{22} et 132 ↔ _{1}^{13}, ainsi que l’Inf de 231 ↔ _{2}^{23} et 312 ↔ _{1}^{33}. C’est donc _{1}^{23} qui correspond à la seule matrice

alternante d’ordre trois qui ne soit pas une permutation : \begin{matrix}0 & 1 & 0 \\ 1 & −1 & 1 \\ 0 & 1 & 0 \end{matrix} .

Le treillis enveloppant de 𝔖(4) est constitué de 42 triangles, dont nous énumérons les 18 qui ne sont pas des clefs:

2 3 3 1 2 1 1 3 4 1 2 1 2 3 4 1 2 1 2 3 4 2 2 1 3 3 4 1 2 1 2 3 4 1 3 1 3 3 4 2 2 1 2 3 4 2 3 1 3 3 4 2 3 1

2 4 4 1 2 1 3 4 4 1 2 1 2 4 4 1 3 1 3 4 4 2 2 1 2 4 4 2 3 1 3 4 4 1 3 1 3 4 4 2 3 1 3 4 4 2 3 2 4 4 4 2 3 1

L’application 5.3 décrit, pour un contre-tableau t, une famille de bigrassmanniennes dont t est le Sup. Les éléments maximaux de cet ensemble de bigrassmanniennes, c’est-à-dire les rectrices du triangle, correspondent bijectivement aux composantes t_{ij} telles que l’image de t par t_{ij} → t_{ij} − 1 soit encore un triangle.

Ces composantes seront appelées points essentiels du triangle; un triangle est donc le Sup des bigrassmanniennes correspondant à ses points essentiels et tout ensemble de composantes dont le triangle est le Sup contient les points essentiels. Dans le cas où t est la clef d’une permutation μ, les points essentiels ont été définis par Fulton [Fu] ( en terme de la fonction de rang de la matrice représentant la permutation).

Un triangle sera dit vexillaire ssi l’ensemble de ses points essentiels E vérifie la condition suivante (qui est géographique au sens donné plus haut à ce terme):

(5.5)  ∀(i, j) ∈ E ⇒ {(i′, j′) : i′ ≤ i, j′ > j} ∩ E = ∅ .

En d’autres termes, il n’y a pas de point essentiel dans le cadran nord-est d’un point essentiel (le domaine d’exclusion comprend le demi axe-est).

Dans le cas d’une permutation vexillaire μ, cette définition, appliquée à la clef de μ, correspond à l’une des nombreuses caractérisations des permutations vexillaires (cf. [Fu]).

6. Pavés. — On a remarqué que le clivage associé à une transposition simple σ induit le clivage de tout intervalle [≤ μ]. Cet idéal se décompose en un idéal [≤ ν] (où ν est la permutation maximum ν ≤ μ dont aucune décomposition réduite ne contient σ) et son complémentaire [≤ μ] ∩ [σ ≤].

Nous donnons dans ce paragraphe une décomposition du groupe symétrique transversale au clivage précédent.

Pour ce faire, considérons l’algèbre des différences divisées isobares. A tout ensemble J ⊂ {1, …, n − 1} correspond le groupe parabolique

P_{J} engendré par les transpositions simples {σ_{i}|i ∈ {1 … n − 1} \ J }, ainsi que la projection p_{J} du monoide engendré par les π_{i} , i ∈ {1 … n − 1} sur le monoide engendré par les π_{i} , i ∉ J déterminée par π_{j} → 1 pour tous les j ∈ J.

Cette projection est clairement compatible aux relations de Coxeter, ainsi qu’aux relations π_{i}^{2} = π_{i} et donc l’image des π_{μ} est bien définie. Définition. — Soit k un entier, 1 ≤ k ≤ n − 1. Un k-pavé est une classe d’équivalence pour la relation

μ ∼_{k} ν ⇔ p_{k}(π_{μ}) = p_{k}(π_{ν}) .

Deux permutations μ, ν appartiennent au même k-pavé ssi, pour deux décompositions réduites quelconques μ = σ_{i}σ_{j} ⋯ σ_{h} et ν = σ_{l} ⋯ σ_{m}, on a

p_{k}(π_{i}π_{j} ⋯ μ_{h}) = p_{k}(π_{l} ⋯ π_{m}) .

Par exemple, le groupe 𝔖(4) se décompose en six 1-pavés : [1432, 4321], [1342, 3241], [1423, 4213], [1324, 3214], [1243, 2143], [1234, 2134], qui sont des intervalles booléens de cardinaux respectifs 8,4,4,4,2,2 .

Des pavés plus généraux apparaissent pour k ≠ 1, n − 1.

Définition. — Soit μ une permutation et k ≤ n − 1. Les places ksaillantes gauches de μ sont les indices 1 ≤ i ≤ k pour lesquels μ_{i} = max({μ_{i}, …, μ_{k}}); les places k-saillantes droites de μ sont les indices k < j ≤ n pour lesquels μ_{j} = min({μ_{k+1}, …, μ_{j}}).

PROPOSITION 6.1. — Soit k un entier ≤ n − 1, ν une permutation dans P_{k} = 𝔖(k) × 𝔖(n − k). Soit ζ la permutation obtenue à partir de ν en permutant circulairement les points saillants de ν de sorte à en faire une suite décroissante.

Alors le k-pavé contenant ν est égal à l’intervalle [ν, ζ] et est isomorphe à l’idéal de la bigrassmannienne [0, r, p, 0] de 𝔖(p + r), où p est le nombre de points saillants gauches de ν, r le nombre de points saillants droits.

Une permutation μ appartient au pavé de ν ssi ζ_{i} = ν_{i} ⇒ μ_{i} = ν_{i} et l’image de μ par la projection de 𝔖(n) sur 𝔖(p + r) qui consiste en l’effacement des valeurs communes à ν et ζ, est supérieure (pour l’ordre de Bruhat) à l’image de ν.

Ainsi, pour k = 5 et

\begin{matrix}ν & = & 5 & 3 & 4 & 1 & 2 & 11 & 9 & 12 & 7 & 8 & 6 & 10 \\ places & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \end{matrix}

( les point saillants sont en gras) , le maximum du pavé est

ζ = 11 3 9 1 7 6 5 12 4 8 2 10 .

Une permutation μ appartient au pavé ssi μ_{2} = 3, μ_{4} = 1, μ_{8} = 12, μ_{12} = 10 et (μ_{1}, μ_{3}, μ_{5}, μ_{6}, μ_{7}, μ_{9}, μ_{11}) ≥ (5, 4, 2, 11, 9, 7, 6). Preuve. — La permutation ν est le produit direct des deux permutations ν′ = ν_{1} … ν_{k} k + 1 … n et ν′′ = 1 … k ν_{k+1} … ν_{n}. Une permutation μ est dans la fibre de ν ssi p_{k...n−1}(μ) = ν′ et p_{1...k}(μ) = ν′′. Or le code de p_{k...n−1}(μ) est l’inf du code de μ et du vecteur [k − 1, …, 1, 0, …, 0], ainsi qu’on le voit en considérant le décomposition réduite de μ associée au code (i.e. le code considéré est le vecteur [inf(c_{1}, k − 1), …, inf(c_{k}, 0), …, 0], où [c_{1}, …, c_{n}] est le code de μ ).

Il s’ensuit que la condition nécessaire et suffisante que μ soit dans la fibre de ν est que

• l’inf du code de μ et [k − 1 … 0 … 0] est égal au code de ν′

• l’inf du code de ωμω et [n − k − 1 … 0 … 0] est égal au code de ων′′ω.

Il n’est pas difficile de vérifier que ζ satisfait à ces deux conditions. Comme les morphismes de spécialisation p_{J} sont des morphismes

d’ordre (i.e. μ ≤ η ⇒ p_{J} (μ) ≤ p_{J} (η)), on en déduit que l’intervalle [ν, ζ] est contenu tout entier dans une seule fibre.

Nous épargnerons au lecteur la vérification que toute permutation appartient à un et un seul de ces intervalles.

Par ailleurs, l’intervalle [ν, ζ] a pour image dans 𝔖(p + r), après effacement des points fixes et retour à l’alphabet {1, 2, …, p+r} l’intervalle [(p … 1) , (p + r … p + 1)]. L’image de cet intervalle, par multiplication à gauche par ω, est l’intervalle [(1 … p) , (p + 1 … p + r)] qui n’est autre que l’intervalle inférieur de la bigrassmannienne [0, r, p, 0]

L’énumération des pavés isomorphes à l’idéal de la bigrassmannienne [0, r, p, 0] ( disons de type [0, r, p, 0] ) est donné par le lemme suivant, en désignant par Λ^{i}(k) le nombre de Stirling égal à la i−ème fonction élémentaire des entiers 0, 1, …, k − 1.

LEMME 6.2. — Le nombre de k−pavés de type [0, r, p, 0] est égal au produit des nombres de Stirling Λ^{k−p}(k) Λ^{n−k−r}(n − k)

Preuve. — Soit n(k, r, p) le nombre de pavés de type [0, r, p, 0]. La projection ”effacement de la lettre 1” :

𝔖(n) ∋ μ → μ\1 ∈ 𝔖(n − 1)

donne une récurrence sur le nombre de pavés.

En effet, soit ν le minimum d’un k−pavé. Si ν_{k} = 1, alors le pavé est de type [0, r, p, 0] ssi le pavé contenant ν\1 est de type [0, r, p − 1, 0].

Si ν_{k} ≠ 1, l’effacement de 1 donne un pavé isomorphe. Comme il y a k − 1 permutations μ qui se projettent sur ν\1, et telles que ν_{k} ≠ 1, on a la récurrence n(k, r, p) = (k − 1)n(k − 1, r, p) + n(k − 1, r, p − 1) Exemple. — Les fibres de la projection p_{3} : 𝔖(7) → 𝔖(3) × 𝔖(4) sont les bigrassmanniennes suivantes. On regroupe les pavés de type [0, r, p, 0] et [0, p, r, 0] qui sont isomorphes, et on écrit Λ^{ij} pour Λ^{i}(3)Λ^{j}(4) :

[p, r] [11]  [12]  [13]  [14] [22]  [23]  [24] [33] [34]
card 12  40  18  2 33  29  3  6  1
= Λ^{23} Λ^{22} + Λ^{13} Λ^{21} + Λ^{03} Λ^{20} Λ^{12} Λ^{02} + Λ^{11} Λ^{10} Λ^{01} Λ^{00}

Molev [Mo] a utilisé une décomposition du groupe symétrique en intervalles booléens pour développer le déterminant de Sklyanin et décrire le centre de l’algèbre enveloppante dans le cas des groupes orthogonaux et symplectiques. Quoique le nombre des pavés soit encore un nombre de Stirling, cette décomposition est différente de celle que nous venons d’exposer.

Ayant décomposé le groupe symétrique en pavés, il nous reste à décrire ceux-ci en tant qu’intervalles pour l’ordre de Bruhat. Nous nous contenterons de donner la fonction génératrice du nombre d’éléments dans l’intervalle, classés par nombre d’inversions, autrement dit le Polynôme de Poincaré de l’intervalle.

Soit une bigrassmannienne b = [0, r, p, 0]. Notons G(r, p) le polynôme de Poincaré := ∑_{μ≤b} z^{ℓ(μ)} de b.

Nous voulons décrire l’intervalle inférieur de b. Celle dernière a une décomposition réduite canonique que l’on peut écrire planairement dans un rectangle (lisant par colonnes, de gauche à droite):

σ_{p} σ_{p+1} ⋯ σ_{p+r−1}
⋮  ⋮  ⋮
σ_{1} σ_{2} ⋯  σ_{r}

Comme l’intervalle se calcule à l’aide de (3.2), c’est-à-dire de la décomposition des produits de π_{i} dans la base des π̄_{μ}, le polynôme de Poincaré G(r, p) est obtenu par récurrence à partir du lemme suivant.

LEMME 6.3. — Soient p et r deux entiers. Alors on a l’identité

\begin{matrix}π_{p} & π_{p+1} & ⋯ & π_{p+r−1} & · \\ π_{p−1} & π_{p} & ⋯ & π_{p+r−2} & π̄_{p+r−1} \\ ⋮ & ⋮ & & ⋮ & ⋮ \\ π_{1} & π_{2} & ⋯ & π_{r} & π̄_{r+1} \end{matrix} = \begin{matrix}π̄_{p−1} & π̄_{p} & ⋯ & π̄_{p+r−1} \\ ⋮ & ⋮ & & ⋮ \\ π̄_{1} & π̄_{2} & ⋯ & π̄_{r+1} \\ · & π_{1} & ⋯ & π_{r} \end{matrix}

Preuve. — Ecrivons i pour π_{i}, i′ pour π̄_{i}. On a, pour deux entiers consécutifs quelconques,

434′ = 43′4′ = 3′4′3 ,

et donc, pour deux lignes,

\begin{matrix}2 & 3 & 4 & · \\ 1 & 2 & 3 & 4′ \end{matrix} = \begin{aligned}2 & 3 \\ 1 & 2 & 3′ & 4′ \\ & & & 3 \end{aligned} = \begin{aligned}2 \\ 1 & 2′ & 3′ & 4′ \\ & & 2 & 3 \end{aligned} = \begin{aligned}1′ & 2′ & 3′ & 4′ \\ & 1 & 2 & 3 \end{aligned}

Finalement, pour un nombre quelconque de lignes,

\begin{matrix}3 & 4 & 5 & · \\ 2 & 3 & 4 & 5′ \\ 1 & 2 & 3 & 4′ \end{matrix} = \begin{matrix}2′ & 3′ & 4′ & 5′ & · \\ · & 2 & 3 & 4 & · \\ · & 1 & 2 & 3 & 4′ \end{matrix} = \begin{matrix}2′ & 3′ & 4′ & 5′ \\ 1′ & 2′ & 3′ & 4′ \\ · & 1 & 2 & 3 \end{matrix} ,

ce qui est bien le lemme

On intialise la récurrence sur les polynômes de Poincaré en écrivant que la dernière colonne de l’expression planaire de π_{b}, disons π_{6}π_{5}π_{4}π_{3} est égale à

π_{6}π_{5}π_{4}π_{3} = (1 + \overline{π_{6}})(1 + \overline{π_{5}})(1 + \overline{π_{4}})(1 + \overline{π_{3}})

Par application répétée de 6.3, en regroupant les termes et en employant les notations des λ-anneaux ( les fonctions S^{i}(r + x) sont les coefficients de la série en z 1/(1 − zx)(1 − z)^{r}, i.e. 1/(1 − zx)(1 − z)^{r} = S^{0}(r + x) + zS^{1}(r + x) + z^{2}S^{2}(r + x) + …), on obtient

PROPOSITION 6.4. — Soient r, p des entiers ≥ 1 et Z = z^{r+1}. Alors G(r + 1, p) = (S^{p−1}(1 + z) + z^{p})G(r, p) + ZS^{p−2}(2 + z)G(r, p − 1) +

Z^{2}S^{p−3}((3 + z)G(r, p − 2) + ⋯ + Z^{p−2}S^{1}(p − 1 + z)G(r, 2) + Z^{p−1}S^{0}(r, 1)

Le cas initial G(r, 1), c’est à dire de l’idéal d’un cycle b = (2, …, r+1, 1) est donné par la spécialisation π_{i} = 1 + z ∀i. En effet, π_{b} = (1 + \overline{π_{1}}) ⋯ (1 + \overline{π_{r}}) = ∑_{μ≤b} \overline{π_{μ}} est une expression dont le développement ne fait apparaître aucun carré \overline{π_{i}}^{2}. Les éléments de l’intervalle [≤ b] sont en correspondance bijective avec les sous-mots de la décomposition réduite b = σ_{1}σ_{2} ⋯ σ_{r}. Cet intervalle est booléen et l’on a G(r, 1) = (1 + z)^{r}, ce qui résulte aussi du fait bien connu que l’idéal d’un cycle b est un intervalle booléen.

Comme exemple de la proposition, on a G(7, 4) = (1 + z + z^{2} + z^{3} + z^{4})G(6, 4) + z^{7}(3 + 2z + z^{2})G(6, 3) + z^{14}(3 + z)G(6, 2)+z^{21}G(6, 1) = 1+10z +54z^{2} +209z^{3} +…+252z^{26} +28z^{27} +z^{28} est le polynôme de Poincaré d’un pavé de cardinal 1315666 de 𝔖(11) que nous nous dispenserons d’énumérer.

Table des coefficients des G(r, p), pour 4 ≥ r ≥ p ≥ 2

card
G(2, 2) 1 3 5 4 1  14
G(3, 2) 1 4 9 13 12 6  1  46
G(3, 3) 1 5 14 29 45 53 46 27  9  1  230
G(4, 2) 1 5 14 26 35 34 22 8  1  146
G(4, 3) 1 6 20 49 95 150 195 206 173 110 48 12 1 1066
G(4, 4) 1 7 27 76 174 337 562 815 1029 1125 1052 823 521
252 84 16 1 6902

7. Groupe B_{n}. — Le goupe B_{n} est engendré par n générateurs s_{1}, …, s_{n} qui satisfont aux mêmes relations que les générateurs du groupe symétrique, mis à part le remplacement de (s_{1}s_{2})^{3} = 1 par

(s_{1}s_{2})^{4} = 1

Chaque élément peut être décrit par sa décomposition réduite lexicographiquement minimale ( drlm ). Ecrivant i pour s_{i}, celle-ci est un sous-mot de la décomposition de l’élément maximal :

(1) (212) (32123) ⋯ (n … 212 … n)

qui est formé de facteurs gauches de chacun des blocs indiqués entre parenthèses.

On peut donc coder bijectivement un élément de B_{n} par la suite des longueurs des facteurs successifs de sa drlm ; les éléments de B_{n} sont en bijection avec les vecteurs c dans ℕ^{n}, c ≤ [1, 3, 5, …, 2n + 1] que nous appelerons codes.

Les éléments de B_{n} peuvent aussi être représentés par les permutations signées de {1, …, n}, en interprétant s_{1} comme le morphisme de ℤ^{n} :

u = [u_{1}, …, u_{n}] → us_{1} = [−u_{1}, u_{2}, …, u_{n}]

et s_{i}, i = 2, …, n, comme la transposition simple échangeant les composantes u_{i−1} et u_{i}.

Une deuxième représentation est le plongement dans 𝔖(2n) défini par

s_{1} → σ_{n}, s_{2} → σ_{n−1}σ_{n+1}, …, s_{n} → σ_{1}σ_{2n−1} ,

où les σ_{i} sont les transpositions simples de 𝔖(2n). L’image de B_{n} est alors l’ensemble des permutations μ palindromes, i.e. telles que μ_{i} + μ_{2n−i} = 2n + 1, i = 1, …, n.

Le passage du code à chacune de ces deux représentations est immédiat et correspond à compter les inversions. Ainsi le code [1, 0, 5, 2] correspond à la décomposition réduite (1)()(32123)(43), à la permutation signée [−1, 4, 2, −3] et au palindrome 73154862. En effet, c_{4} = 2 indique la place de 4 (à partir de la droite) dans la permutation signée et la place de 8 dans le palindrome; c_{3} = 5 donne la place de -3 dans [−1, 2, −3], le signe - impliquant que l’on compte la place à partir de la gauche en ajoutant l’ordre (=3), ainsi que la place de 7 dans le palindrome 735462.

On passe de la permutation signéee au palindrome par duplication et retour à l’alphabet {1, 2, …, 2n} par translation de n:

[−1, 4, 2, −3] → [3, −2, −4, 1] , [−1, 4, 2, −3] ∼ 73154862

Le générateur s_{1} joue un rôle particulier, ce qui conduit à distinguer deux types de facteurs v d’une drlm :

• colonne si s_{1} ∉ v (i.e. v = s_{k} ⋯ s_{k−i}, i < k − 1)

• équerre sinon. Le produit d’une colonne ou d’une équerre par un générateur s_{i} est

instantané et permet ainsi de d’expliciter l’action, à gauche ou à droite, de B_{n} sur les codes.

Soit un élément de B_{n} dont le code n’a que deux composantes non nulles. Cet élément n’est une bigrassmannienne que dans les seuls cas suivants:

(cc) c_{1} = 0 = c_{k−1}; c_{k} = c_{k+1} < k; c_{k+2} = 0 = ⋯ = c_{n} (ee) c_{1} = 0 = c_{k−1}; = c_{k+1} = c_{k} + 1 ≥ k + 1 < k; c_{k+2} = 0 = ⋯ = c_{n} (ec) c_{1} = 0 = c_{k−1}; c_{k} ≥ k, c_{k+1} = 2k + 1 − c_{k}; c_{k+2} = 0 = ⋯ = c_{n} Les facteurs correspondants de la drlm sont respectivement (colonne,

colonne); (équerre, équerre); (équerre, colonne).

Par exemple, pour k = 5, avec i au lieu de s_{i}, les drlm suivantes illustrent ces trois types :

(cc) (543) (654) (ee) (5432123) (65432123) (ec) (5432123) (654) Par récurrence sur le nombre de facteurs, on en déduit la caractérisation

des codes des bigrassmanniennes de B_{n} :

LEMME 7.1. — Un vecteur c dans ℕ^{n} est le code d’une bigrassmannienne de B_{n} ssi

i) c ≤ [1, 3, …, 2n + 1]; ses composantes non nulles sont consécutives et constituent une suite d’équerres suivie par une suite de colonnes (l’une de ces deux suites peut être vide)

ii) chaque paire de composantes adjacentes non nulles vérifie la condition cc), ee) ou ec) indiquée par son type.

Par exemple, l’ensemble des codes des bigrassmanniennes de B_{3} est {[0, 3, 4]; [1, 2, 3]; [0, 0, 5], [0, 2, 3], [1, 2, 2]; [0, 0, 4], [0, 3, 1], [0, 2, 2]; [0, 0, 3], [0, 3, 0], [1, 2, 0], [1, 1, 1]; [0, 0, 2], [0, 1, 1], [0, 2, 0], [1, 1, 0]; [0, 0, 1], [0, 1, 0], [1, 0, 0]}

Du lemme précédent, on déduit la fonction génératrice du nombre des bigrassmanniennes :

LEMME 7.2. — La fonction ∑_{n=1}^{∞} z^{n−1}card({bigr(B_{n})}) est égale à

(1 − z)^{−5} + z(1 − z)^{−4} = 1 + 6z + 19z^{2} + 45z^{3} + 90z^{4} + …

Nous allons voir que l’ensemble des bigrassmanniennes contient strictement la base de B_{n}, pour n ≥ 4.

Comme l’ordre de Bruhat sur B_{n} coïncide avec la restriction de l’ordre de Bruhat sur 𝔖(2n) au sous-ensemble des permutations palindromes [Lak], [Pr], on peut décrire l’ordre de B_{n} en utilisant les bigrassamnniennes de 𝔖(2n).

Tout d’abord, on remarque que pour les permutations palindromes

μ ≥ bigr[r_{0}, r_{1}, r_{2}, r_{3}] ⇔ μ ≥ bigr[r_{3}, r_{2}, r_{1}, r_{0}] .

Appelons couple miroir un tel couple de bigrassmanniennes, invariant par le retournement [r_{0}, r_{1}, r_{2}, r_{3}] → [r_{3}, r_{2}, r_{1}, r_{0}].

En particulier, l’ensemble des rectrices d’une permutation palindrome est formé de couples miroirs dont il suffit de se donner un seul des deux éléments. Définition. — Les rectrices d’un élément de B_{n} sont les rectrices [r_{0}, r_{1}, r_{2}, r_{3}] de son image palindrome qui sont telles que {r_{0} < r_{3}} ou {r_{0} = r_{3} & r_{1} ≤ r_{2}}.

Les éléments de B_{n} sont déterminés par leurs rectrices, puisque les éléments de 𝔖(2n) le sont. L’ordre de Bruhat sur les éléments de B_{n} est induit par l’ordre sur les bigrassmanniennes de 𝔖(2n). Plus explicitement, tenant compte de ce que l’on n’a pris que la moitié des rectrices des palindromes par raison de symétrie, on a

[r_{0}, r_{1}, r_{2}, r_{3}] ≤_{B_{n}} [p_{0}, p_{1}, p_{2}, p_{3}]

ssi

[r_{0}, r_{1}, r_{2}, r_{3}] ≤_{𝔖(2n)} [p_{0}, p_{1}, p_{2}, p_{3}] ou [r_{0}, r_{1}, r_{2}, r_{3}] ≤_{𝔖(2n)} [p_{3}, p_{2}, p_{1}, p_{0}]

LEMME 7.3. — Soit b = [r_{0}, r_{1}, r_{2}, r_{3}] une bigrassmannienne de 𝔖(2n). Alors l’ensemble des permutations palindromes ≥ b admet un élément inférieur, noté b_{+}. Symétriquement, l’ensemble des permutations palindromes inférieures à une cobigrassmannienne c de 𝔖(2n) a un supremum, noté c_{−}.

De plus l’élément correspondant à b_{+} (resp c_{−}) dans B_{n} est une bigrassmannienne (resp. cobigrassmannienne).

Preuve. — On peut supposer que b = [r_{0}, r_{1}, r_{2}, r_{3}] avec r_{0} < r_{3} ou r_{0} = r_{3} & r_{1} ≤ r_{2}. On a quatre cas possibles, suivant que r_{0} + r_{1} ≤ n ou non, et r_{0} + r_{2} ≤ n ou non.

Prenons par exemple r_{0} + r_{1} > n et r_{0} + r_{2} ≤ n. On cherche les palindromes tels que le facteur gauche de longueur r_{0} + r_{1} contienne au moins r_{1} valeurs > r_{0} + r_{2}. L’ensemble des valeurs {1, …, 2n} est coupé en trois intervalles X = {1, …, r_{0} + r_{2}}, Y′ = {r_{0} + r_{2} + 1, …, r_{1} + r_{3}}, Y′′ = {r_{1} + r_{3} + 1, …, 2n}.

De même, les permutations, considérées comme mots, sont coupées en trois segments de longueurs respectives r_{2}+r_{3}, r_{0}+r_{1}−r_{2}−r_{3}, r_{2}+r_{3}. Pour la projection p : X → x, Y′ → y′, Y′′ sur l’alphabet {x < y′ < y′′}, on a que μ ≥ b implique que le facteur gauche de longueur r_{0} + r_{1} contient au moins r_{1} valeurs dans Y′ ∪Y′′. Tenant compte de ce que μ est palindrome, cela implique que

μ ≥ [r_{0}, r_{1}, r_{2}, r_{3}] ⇔ p(μ) ≥ v := x^{r_{0}}y′^{α}y′′^{r_{2}}y′^{2β}x^{r_{2}}y′^{α}y′′^{r_{0}} ,

avec α = r_{3} − r_{0}, β = r_{0} + r_{1} − n.

Ce mot est l’inf des palindromes d’évaluation x^{r_{0}+r_{2}}y′^{r_{1}+r_{3}−r_{0}−r_{2}}y′′^{r_{0}+r_{2}} qui soient plus grands que p(b). Le palindrome minimum qui se projette sur v est, en marquant les mêmes coupures que v, b_{+} := 1 … r_{0} | r_{0} + r_{2} + 1 …, r_{2} + r_{3} | r_{1} + r_{3} + 1 … r_{1} + r_{2} + r_{3} | r_{2} + r_{3} + 1 … r_{0} + r_{1} | r_{0} … r_{0} + r_{2} | r_{0} + r_{1} + 1 … r_{1} + r_{3} | 2n − r_{0} + 1 … 2n.

Comme dans le cas du groupe symétrique, on termine l’analyse en vérifiant que p(b_{+}) reste bien minimum lorsque l’on fait varier la projection d’alphabet p : {1 … 2n} → {x, y}.

Les trois autres cas se traitent explicitement de la même manière.

Etant donnée une bigrassmannienne b = [r_{0}, r_{1}, r_{2}, r_{3}] de 𝔖(2n), la cobigrassmannienne qui clive avec elle est c = ωb′, avec b′ = [r_{1} − 1, r_{0} + 1, r_{3}+1, r_{2}−1]. De l’existence de b′_{+}, on déduit donc par multiplication par ω l’existence d’une permutation palindrome maximale dans l’idéal [≤ c] complémentaire de [b ≤], qui n’est autre que ωb′_{+}.

Enfin, on voit, sur son expression explicite, que b_{+} a deux descentes, lesquelles sont à des places symétriques, de même que son inverse. En d’autres termes, l’élément correspondant de B_{n} est une bigrassmannienne

TH^{}ÉOR^{}ÈME 7.4. — L’image de la base de B_{n} dans 𝔖(2n) est l’ensemble des palindromes {b_{+}} qui sont les Sup respectifs des couples miroirs de bigrassmanniennes de 𝔖(2n), et en correspondance bijective avec ces derniers.

Le treillis enveloppant de B_{n} est distributif, i.e. chaque élément de la base clive B_{n} en une union disjointe de deux intervalles.

La base est un sous-ensemble strict de l’ensemble des bigrassmanniennes de B_{n}.

Remarque. — Le cardinal de la base de B_{n} est n(2n^{2} + 1)/3, et donc la fonction génératrice des cardinaux est

(1 + z)^{2}/(1 − z)^{4} = 1 + z + 19z^{2} + 44z^{3} + 85z^{4} + · · · .

Le rapport card(base(B_{n}))/card(Bigr(B_{n})) tend vers 0 comme 1/n lorsque n tend vers l’infini.

La seule bigrassmannienne de B_{4} qui n’appartient pas à la base a pour code [0042] et drlm s_{3}s_{2}s_{1}s_{2}s_{4}s_{3}; elle est le sup des deux éléments de la base [0050] = s_{3}s_{2}s_{1}s_{2}s_{3} et [0022] = s_{3}s_{2}s_{4}s_{3}. Les cinq bigrassmanniennes de B_{5} exclues de la base ont pour codes respectifs

[00053], [00420], [00062], [00422], [00453]

8. Annexe. — Commençons par rappeler brièvement la preuve classique du théorème de Mac Neille fournie par la méthode de O.Ore.

Soit donnée une relation R ⊂ X̄ × X entre deux ensembles X̄ et X. Pour chaque x ∈ X, nous posons xρ̄ = {x̄ ∈ X̄ : (x̄, x) ∈ R} et Y ρ̄ = ∩{yρ̄: y ∈ Y } pour chaque partie Y ≠ ∅, X de X. On convient de plus que ∅ρ̄ = X̄ et Xρ̄ = ∅.

On définit de même ρ en échangeant le rôle de X et de X̄, et tous les énoncés qui suivent restent valides par cet échange, un phénomène que nous nous dispenserons souvent de mentionner.

Il est clair que ρ̄: 2^{X} → 2X̄ est décroissante

(Y′ ⊂ Y ∈ 2^{X} ⇒ Y ρ̄ ⊂ Y′ρ̄)

et que ρ̄ρ : 2^{X} → 2^{X} est croissante ( Y ∈ 2^{X} ⇒ Y ⊂ Y ρ̄ρ).

On a donc ρ̄ρρ̄ = ρ̄ ( et ρρ̄ρ = ρ) puisque

Y ρ̄ ⊂ (Y ρ̄)ρρ̄ = Y ρ̄ρρ̄ = (Y ρ̄ρ)ρ̄ ⊂ Y ρ̄

identiquement.

Soit maintenant T̄ = \{Y ρ̄ : Y ∈ 2^{X}\} ∈ 2^{2\overline{X}}. D’après la définition de ρ̄: 2^{X} → 2\overline{X}, la famille (T̄, ⊂) de parties de X̄ munie de l’ordre d’inclusion, est un treillis dans lequel l’opération Inf est l’intersection ensembliste ∩. Plus précisément, (T̄, ⊂) est le plus petit treillis contenant tous les xρ̄ (x ∈ X).

Symétriquement, T = {Ȳ ρ : Ȳ ∈ 2X̄} ∈ 2^{2^{X}} est le treillis engendré par les x̄ρ (x̄ ∈ X̄). Si Y ∈ T, on a, par définition, Y ρ̄ ∈ T̄ et Y = Ȳ′ρ pour une certaine partie Ȳ′ de X̄. On a donc

Y ρ̄ρ = Ȳ′ρρ̄ρ = Ȳ′ρ = Y ,

ce qui montre que les restrictions ρ̄ : T → T̄ et ρ : T̄ → T sont deux antiisomorphismes (de la relation d’ordre ⊂) inverses l’un de l’autre.

Autrement dit, si {Y_{i} : i ∈ J } est une famille d’éléments de T, on a Inf{Y_{i} : i ∈ J } = ∩{Y_{i} : i ∈ J } ∈ T, cependant que Sup{Y_{i} : i ∈ J } = Z̄ρ, avec Z̄ = ∩{Y_{i}ρ̄: i ∈ J } ∈ T̄.

Nous appelerons T et T̄ le X-treillis et le X̄-treillis engendrés par R et nous utiliserons l’abréviation

Diag(R) = {(Ȳ , Y) ∈ 2X̄ × 2^{X} : Ȳ ρ = Y; Y ρ̄ = Ȳ } ⊂ T̄ × T .

En considérant, comme ci-dessus, R comme une matrice booléenne, une paire de parties (Ȳ , Y) sera appelé un rectangle (de 1 ) ssi Ȳ × Y est contenu dans R. Par construction, les paires (Ȳ × Y) ∈ Diag(R) sont les rectangles maximaux de R, en ce sens que, étant donné Y ⊂ X, Ȳ est la plus grande partie de X̄ telle que Ȳ ×Y soit un rectangle, et que l’on ait la condition symétrique sur Y par rapport à Ȳ. Par définition, les éléments de T̄ et T sont les projections de Diag(R) sur 2\overline{X} et 2^{X}.

Considérons deux parties X̄_{1} de X̄ et X_{2} de X.

Elles définissent par restriction trois autres relations

R_{1} = R ∩ (X̄_{1} × X) ; R_{2} = R ∩ (X̄ × X_{2}) ; R_{3} = R ∩ (X̄_{1} × X_{2})

engendrant les paires de treillis (T̄_{1}, T_{1}), (T̄_{2}, T_{2}), (T̄_{3}, T_{3}).

Par définition T_{1} (resp. T̄_{2}) est une famille de parties de X (resp. X̄) contenue dans T (resp. dans T̄) et l’injection naturelle T_{1} → T (resp. T̄_{2} → T̄) est un morphisme pour l’opération Inf puisque cette dernière n’est autre que l’opération ensembliste ∩.

On a de même des morphismes canoniques T̄_{3} → T̄_{1} et T_{3} → T_{2}.

LEMME 8.1. — Si X̄_{1} et X_{2} sont tels que T_{1} = T et T̄_{2} = T̄, on a

T_{3} = T et T̄_{3} = T̄ .

Preuve. — En posant X_{1} = X, X̄_{2} = X̄, X̄_{3} = X̄_{1} et X_{3} = X_{2}, les hypothèses et la conclusion peuvent s’écrire

Diag(R) = Diag(R) ∩ \{2\overline{X_{i}} × 2^{X_{i}}\} (= Diag(R_{i})) ,

respectivement pour i = 1, 2 et pour i = 3.

Supposons que (Ȳ , Y) soit un rectangle maximal dans X̄_{2} × X_{1}. On a d’une part Ȳ × Y ⊂ R_{3}, donc ⊂ R, et d’autre part que pour chaque z ∈ X_{1} \ Y, il y au moins un ȳ ∈ Ȳ pour lequel (y, z) ∉ R_{3}, donc ∉ R, et symétriquement pour chaque z ∈ X̄_{2} \ Ȳ. Ceci implique que (Ȳ , Y) est la restriction à X_{2} × Y du rectangle maximal (Y ρ̄, Ȳ ρ) ∈ Diag(R) et établit que

Diag(R_{3}) ⊂ Diag(R) ∩ (2\overline{X_{1}} × 2^{X_{2}}) .

Réciproquement, soit maintenant Ȳ × Y ∈ Diag(R). Sa restriction à X̄_{1} ×X_{2} est encore un rectangle dont il suffit de prouver qu’il est maximal pour chaque z ∈ X\Y. Or la maximalité de Ȳ ×Y implique l’existence d’au moins un ȳ ∈ Ȳ tel que (ȳ, z) ∉ R et l’hypothèse Diag(R_{1}) = Diag(R) implique que l’on puisse prendre un tel ȳ dans Ȳ ∩ X̄_{1}.

Un argument symétrique s’applique aux z̄ ∈ X̄ \ Ȳ, ce qui achève la preuve

Nous en venons maintenant à la preuve des résultats énoncés au paragraphe 2.

LEMME 2.3. — Soit (X, ≤) un ensemble ordonné. Un élément x ≠ ∧X appartient à la base B ssi il est un élément minimal de X \ [≤ z] pour au moins un z ∈ X.

Quand (X, ≤) est un treillis, cette condition est remplie ssi x couvre exactement un autre élément de X.

Preuve. — Soit x un élément de X \ ∧X. Par définition, il appartient au complément de X \ B de la base ssi il existe une partie Y ≠ ∅ de X telle que

(⋆)  x ∉ Y & [x ≤] = ∩{[y ≤] : y ∈ Y } .

On observe d’abord que cette relation est vraie pour un Y ≠ ∅ ssi elle est vraie pour le cas particulier de Y = [< x] (:= [x ≤]\x). En effet, si Y satisfait (⋆) on a y ∈ [< x] pour chaque y ∈ Y, et d’autre part Y ∪ {y} satisfait encore (⋆) pour chaque y ∈ [< x]. On a donc x ∈ X \ B ssi

[x ≤] = Z , où Z :== ∩{[y ≤] : y ∈ [< x]} .

Par construction Z \ [≤ x] est l’ensemble des z ∈ X tel que x soit un élément minimal de X \ [≤ z]. On a donc x ∈ X \ B ou x ∈ B selon que Z \ [≤ x] est vide ou non. Il est clair que x ∈ B quand x (≠ ∧X) est un élément minimal de X, car il suffit de prendre n’importe quel z ∈ X \[≤ x]. Il en est de même quand x couvre un seul élément, qui est alors Sup([< x]). Le cas particulier où (X, ≤) est un treillis est trivial puisque l’on a alors ∧X ≠ ∅ et pour tout x ∈ X \ ∧X, Sup([< x] ≠ ∅)

PROPOSITION 2.4. — La projection sur la base β : X ∋ x → B ∩[≤ x] ∈ (2^{B}, ⊂) est un isomorphisme d’ordre et l’on a B ⊂ C pour toute partie C de X ayant la même propriété.

Preuve. — Soient y, z ∈ X. Si Y := [≤ y] \ [< z] est vide, c’est-à-dire si y ≤ z on a yβ ⊂ zβ. Pour établir que β est isomorphisme il suffit donc de montrer que Y contient au moins un élément de la base quand Y ≠ ∅.

Or comme Y est fini, il contient au moins un élément minimal b. On a b ≠ ∧X puisque ∧X ∈ [≤ z] quand ∧X ≠ ∅, et donc b ∈ B d’après le lemme 2.3.

Soit maintenant C une partie de X telle que l’application γ : X ∋ x ⟶ xγ = C ∩ [≤ x] soit un isomorphisme. Supposons qu’il existe un b ∈ B \ C. D’après le lemme 2.3 il existe au moins un z ∈ X \ [b ≤] tel que [< b] ⊂ [≤ z]. On a alors bγ = C ∩ [< b] ⊂ zγ = C ∩ [≤ z], contredisant l’hypothèse que γ est un isomorphisme. Donc C contient B.

On définit de même l’application β̄ : X ∈ x ⟶ B̄ ∩ [x ≤], et l’on a pour β̄ des énoncés symétriques de ceux pour β. On notera que xβ = ∅ ssi x = ∧X, et xβ = X ssi x = ∨X.

Exemples. — Soit X = {1, 2, 3, 4} avec la relation d’ordre ≤ définie par {1, 2, 3} = [≤ 3] et {1, 2, 4} = [≤ 4]. Tous les éléments de X appartiennent à la base et à la cobase. La projection γ sur C = {1, 2, 3} est injective, mais elle n’est pas un isomorphisme puisque 4γ = {1, 2} ⊂ 3γ = {1, 2, 3} bien que 3 et 4 soient incomparables. Le treillis enveloppant de X est obtenu en ajoutant à X un plus petit et un plus grand élément, et aussi un élément t tel que

t = Sup({1, 2}) = Inf({3, 4}) .

Ce treillis est le treillis enveloppant de 𝔖(3) (muni de l’ordre fort) vu au 5.

La proposition 2.4 requiert une condition topologique quand X n’est pas fini. Ainsi elle n’est pas vraie quand (X, ≤) est un intervalle de la droite réelle ℝ puisque dans ce cas la base et la cobase sont des ensembles vides. Par contre elle est vraie pour (ℤ, ≤) qui est égal à sa base, puisque la condition des chaînes descendantes est vérifiée pour toute partie [≤ y]\[≤ z] non vide. Le treillis enveloppant est obtenu en ajoutant à ℤ un plus petit et un plus grand élément.

La proposition 2.4 est aussi vérifiée par le treillis distributif (2^{ℤ}, ⊂) dont les éléments sont les parties de ℤ.

Enfin soit X l’ensemble union de l’intervalle [0, 1] de ℝ, muni de son ordre naturel et d’un ensemble B = {b_{x} : x ∈ [0, 1]}, d’éléments incomparables. On ajoute les relations croisées 0 < b_{x} et b_{x} < x′ ssi x ≤ x′ ∈ [0, 1]. Alors B est à la fois la base et la cobase de X. L’application β : X ⟶ B est un isomorphisme d’ordre, ce qui n’est pas le cas de β̄ : X ⟶ B.

C’est un problème ouvert de trouver des catégories non triviales de treillis pour lesquelles la proposition 2.4 et sa symétrique sont vraies.

Soit R′ ⊂ B̄ ×B la relation définie par (b̄, b) ∈ R′ ssi b̄ ≥ b, c’est-à-dire, de façon équivalente, ssi b ∈ b̄β ou b̄ ∈ bβ̄.

PROPOSITION 2.5. — La relation R′ est une relation basique.

Preuve. — Comme X \ [≤ x] ≠ ∅, sauf si x = ∧X, la preuve précédente montre que b̄β ≠ B pour chaque b̄ ∈ B̄. Supposons qu’un élément b̄ ∈ B̄ et une partie C̄ de B̄ soient tels que b̄β = ∩{c̄β : c̄ ∈ C̄}. Comme β est un isomorphisme d’après (2.4), on a c̄ ∈ [b̄ ≤] pour tout c̄ ∈ C̄, et réciproquement b̄β ⊂ xβ pour tout x ∈ [b̄ ≤]; l’hypothèse implique que b̄β = ∩{xβ : x ∈ [b̄ ≤]} et enfin b̄ ∈ C̄ d’après la définition de B̄.

Autrement dit, aucune ligne de R′ n’est l’intersection d’autres lignes. Ceci achève la preuve par symétrie entre B et B̄

Nous appelerons désormais la relation R′ précédente la relation basique de l’ensemble ordonné (X, ≤).

On voit facilement qu’un élément x ∈ X appartient à B̄ ∩B ssi xβ̄×xβ est un rectangle de 1 (au sens donné plus haut à ce terme) dans la relation basique.

Donnons maintenant à la preuve du théorème 2.6.

Prenant une copie X̄ de X et une bijection X ∋ x → x̄ ∈ X̄, nous associons à (X, ≤) sa matrice d’incidence, c’est-à-dire la relation R dans X̄ × X telle que (x̄_{1}, x_{2}) ∈ R ssi x_{1} ≥ x_{2}. La relation basique de (X, ≤) est simplement la restriction de R à B̄ × B.

Utilisant les conventions du début de cette annexe, on voit que pour chaque x ∈ X, on peut identifier la colonne xρ̄ à l’intervalle supérieur [x ≤] et la ligne x̄ρ à [≤ x̄]. Le treillis T et le treillis antiisomorphe T̄ de la construction de Ore sont donc respectivement le treillis enveloppant de (X, ≤) et celui de l’ensemble antiisomorphe (X̄, ≥).

Comme les applications β et β̄ sont injectives, les relations R∩(X̄ ×B) et R ∩ (B̄ × X) engendrent des paires de treillis isomorphes à T̄ × T. Les hypothèses du lemme 2.8 sont donc satisfaites, ce qui permet de conclure que la relation basique R ∩ (B̄ × B) de (X, ≤) est aussi celle du treillis T

Nous en venons maintenant au clivage.

Soit R ⊂ B̄ × B la relation basique d’une relation d’ordre (X, ≤). Le lemme 2.2 montre que deux éléments x̄, x ∈ X sont tels que X n’est

l’union disjointe de [≤ x̄] et [x ≤] que si (x̄, x) ∈ B̄ × B. En ce cas, x détermine x̄ et réciproquement.

Il est clair que si (b̄_{1}, b_{1}) et (b̄_{2}, b_{2}) sont deux paires clivantes, on a b_{1} ≤ b_{2} ssi b̄_{1} ≤ b̄_{2}. Ceci conduit à définir le morphisme partiel NEG de B dans B̄ en posant :

NEG(b) = b̄ s’il existe b̄ ∈ B̄ tel que (b̄, b) soit un clivage
= ∅ sinon

Nous supposons désormais que X est le treillis défini par R.

Soient b ∈ B, Y := X \ [b ≤] et s := Sup(Y). L’ensemble X est l’union de [≤ s] et de [b ≤], cette union étant disjointe ssi b ∉ [≤ s]. Donc NEG(b) = s ou ∅ selon que b ∉ [≤ s] ou non.

Considérons alors l’unique élément b_{−} couvert par b. Comme b_{−} ∈ Y, on a Inf(b_{−}, s) ∈ {b, b_{−}} et d’autre part Sup(Inf(b, y) : y ∈ Y) = b_{−}.

Par conséquent la relation de distributivité

Inf(b_{−}, Sup(Y)) = Sup({Inf(b_{−}, y) : y ∈ Y })

implique b ∉ [≤ s] et enfin NEG(b) = s ≠ ∅.

Compte tenu de la symétrie entre B et B̄, cette remarque établit la partie directe du théorème 2.8.

Revenant au cas général, nous isolons le

LEMME 8.5. — Pour chaque b ∈ B, on a NEG(b) ≠ ∅ ssi il existe un b̄ ∈ B̄ tel que b̄ β = B \ [b ≤].

Preuve. — Il suffit d’observer qu’avec les notations introduites plus haut, on a b ∉ [≤ s] ssi sβ = Y ∩ B

Comme B ∩ [b ≤] est l’ensemble des b′ ∈ B tels que b′β̄ ⊂ bβ̄, il en résulte que la fonction NEG se calcule directement à partir de la relation R et, de plus, que si NEG(b) ≠ ∅ pour chaque b ∈ B, la restriction de R à NEG(B) × B est déterminée par la seule donnée de la restriction de l’ordre ≤ à B.

Pour achever la preuve, nous supposons désormais R telle que NEG(b)≠ ∅ pour chaque b ∈ B.

Soit T ∈ 2^{2^{B}} le plus petit treillis pour les opérations ∪ et ∩ de (2^{B}, ⊂) qui contienne tous les sous-ensembles b_{0} := [b ≤] (b ∈ B) de B; il est classique que (T, ⊂) est un treillis distributif en tant que sous-treillis du treillis distributif (2^{B}, ⊂). En outre b ⟶ b_{0} est un isomorphisme (d’ordre) de B sur une partie B_{0} de T.

Posons aussi b^{0} := B \ [b ≤] ⊂ 2^{B} pour chaque b ∈ B. Cet ensemble appartient à T et il est l’union des b′_{0} ∈ B_{0} \ [b_{0} ⊂], ce qui montre que (b^{0}, b_{0}) est un clivage de T et que la base et la cobase de ce treillis sont B_{0} et B^{0} = {b^{0} : b ∈ B}.

D’après le lemme 8.5, la relation basique R_{0} ⊂ B^{0} × B_{0} de T est isomorphe à la restriction R′ de R à B̄′ × B où B̄′ = NEG(B) ⊂ B̄.

On vérifie maintenant que B̄′ = B̄. Soit b̄ un élément de la cobase B̄. Si b ∈ b̄β, on a b′ ∈ b̄β pour tout b′ ∈ B ∩ [≤ b] d’après la définition de ≤. Par conséquent, l’image de b̄β dans 2^{B} par l’isomorphisme b ⟶ b_{0} est un élément du treillis T. On a donc b̄ ∈ B̄′, montrant que B̄′ = B̄, c’est-à-dire que T est bien le treillis engendré par R

Les calculs dans le treillis distributif T sont facilités par l’identité de Morgan

tβ̄ = NEG(B \ tβ) (t ∈ T)

que l’on déduit immédiatement du lemme 8.5 en identifiant, par complémentation ensembliste, le treillis antiisomorphe T̄ ∈ 2^{2\overline{B}} à un sous treillis de (2^{B}, ⊂).

Il est curieux que l’égalité numérique card(B) = card(B̄) entre la base et la cobase reste vraie dans la variété des treillis modulaires dont les treillis distributifs sont une sous variété.

Pour avoir des exemples plus substantiels, nous considérons le treillis des partitions d’un entier n. Nous faisons référence à un article récent de C.Greene et Kleitman [G-K] dans lequel le lecteur trouvera exposés les principaux résultats sur l’ensemble des partitions en tant que treillis ( cf. aussi S.Kim dans un article à paraître).

Nous adoptons la notation exponentielle pour les partitions, et appelons équerre une partition du type 1^{k}c, i.e. une partition qui a au plus une part différente de 1.

PROPOSITION 8.6. — La base du treillis des partitions d’un entier fixé n est constituée des partitions, ayant trois parts différentes au plus, du type ab^{k}c, où k ≥ 2 et a < b < c, avec les cas dégénérés suivants : ab^{k}, b^{k}c, b^{k}, ( k ≥ 2), et bc.

La cobase est formée des partitions transposées des éléments de la base. L’intersection de la base et de la cobase est constituée par les équerres.

Pour que deux partitions g, ḡ, déterminent un clivage, il faut que l’une d’entre elles soit une équerre. Réciproquement, chaque équerre donne deux clivages, selon qu’elle est considérée comme un élément de la base ou de la cobase.

Preuve. — En effet, deux partitions sont consécutives dans le diagramme des partitions ssi l’on obtient le diagramme de l’une à partir de celui de l’autre en déplaçant de manière minimale une boîte. Si la partition a au moins quatre parts différentes, elle ne peut être irréductible pour ∨. On exclut ensuite les cas a^{h}b^{k}c^{l} où hl > 1. Les cas restants se vérifient sans difficulté.

Soit maintenant un clivage [g ≤], [≤ ḡ]. La partition g appartient à la base, supposons la du type g = ab^{k}c, a < b ≤ c où 2 ≤ k si b ≠ c et 1 ≤ k si b = c. Considérons h = 1^{n−c−1}c + 1. L’élément g ne vérifie pas g ≤ h, puisque a < a + 1. Or h est couverte par une seule partition, à savoir h_{+} := 1^{n−c−2}2 c et l’on a g ≤ h_{+}. Donc h est un élément maximal du complément de [g ≤]. Comme par hypothèse, ce complément est égal à [≤ ḡ], on doit avoir ḡ = h. De plus alors g = ac^{m}, où m est la partie entière de n/c et a le reste. Par conjugaison des partitions, on vérifie que symétriquement, le complément de [h ≤] est un intervalle inférieur

Par exemple, les rectrices de 1^{5}24^{2} sont 34^{3}, 13^{3}5, 12^{4}6 et 1^{7}8. Le lecteur pourra vérifier que le nombre des rectrices d’une partition est au plus égal à la valeur de sa deuxième plus grande part.

Bibliographie

[Bi] G. Birkoff, Lattice theory, 3ème ed., Am. Math. Soc., Providence (1967).

[Bj] A. Björner, Ordering of Coxeter groups, Contemp. Math. 34, A.M.S. (1984) 175-195. [B-W] A. Björner, M. Wachs, Generalized quotients in Coxeter groups, Trans. A.M.S. 308 (1988) 1-37.

[Bo] N. Bourbaki, Groupes et Algèbres de Lie, Fasc 34, Hermann, Paris (1968).

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

[Ch] I. Cherednik, A unification of Knizhnik-Zamolodchikov and Dunkle operators via affine Hecke algebras, Invent. Math. 106 (1991) 411-431.

[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).

[Fo] Fokko du Cloux, A transducer approach to Coxeter groups, prépublication (1995).

[Fu] W. Fulton, Flags, Schubert polynomials, degeneraci loci Duke Math. 65 (1992) 381-420. [G-Ki] M. Geck, S. Kim, On the Bruhat order of finite Coxeter groups, prépublication (1996). [G-K] C. Greene, D. Kleitman, Longest chains in the lattice of integer partitions ordered by majorization, Europ. J. Comb. 7 (1986) 1-10. [G-R] G. Guilbaud, P. Rosenstiehl, Analyse algébrique d’un scrutin, in Ordres totaux finis, Gauthiers-Villars, Paris (1971).

[Lak] V. Lakshmibai, Geometry of G/P. The symplectic group and the involution σ, J. Alg. 108 (1987) 403-434. [L-S 1] A. Lascoux, M.P. Schützenberger, Structure de Hopf de l’anneau de cohomologie de la variété de drapeaux, C.R. Acad. Sc. Paris 295 (1982) 629-633. [L-S 2] A. Lascoux, M.P. Schützenberger, Symmetrization operators on polynomial rings, Funk. Anal. 21 (1987) 77-78.

[Mo] A. Molev, On Stirling partitions of the symmetric group, prépublication, Australian National University (1995).

[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.

[Vr] D.N Verma, Möbius inversion for the Bruhat ordering on a Weyl group, Ann. Sc. Ec. Norm. Sup 4 (1971) 393-398.

the electronic journal of combinatorics 3 (1996), #R27 34 the electronic journal of combinatorics 3 (1996), #R27 35