ARÊTES ET TABLEAUX

par

Alain LASCOUX^{1} et Marcel-Paul SCHÜTZENBERGER^{2}

Que sont les tableaux :

∗ des idempotents dans l’algèbre du groupe symétrique, à la suite de Young ? [Young]

∗ des bases dans la représentation irréductible, dite semi-normale de Young, et la représentation orthogonale, toujours de Young, du groupe symétrique [Rutherford] ?

∗ des polynômes (produits de Vandermonde ∏(x_{i} − x_{j})), bases des modules de Specht [Specht], [Garnir] ?

∗ plus généralement, des mineurs d’une matrice quelconque (au lieu de la matrice de Vandermonde des puissances d’un ensemble de variables) ? Dans ce cas, on préfère les paires de tableaux [Turnbull], [Rota].

∗ des invariants susceptibles de redressement (straightening), ou bien encore des éléments de l’algèbre lettre/place (letter/place algebra) [Doubilet-Rota-Stein] ?

∗ géométriquement, des coordonnées de Plücker pour la Grassmannienne ou la variété de drapeaux [Hodge et Pedoe] ?

∗ des bases-de-sections-de-fibrés-inversibles-au-dessus-des-sous-variétés-de-Schubert-de-la-variété-de-drapeaux (i.e. des postulations) [Hodge], [Lakshmibai-Musili-Seshadri] ?

∗ des composantes irréductibles de la variété des drapeaux fixés par un unipotent [Steinberg] [Spaltenstein] ?

∗ des coefficients de décomposition de représentations du groupe linéaire [Littlewood-Richardson] ?

∗ des monômes dans le développement d’une fonction de Schur [Littlewood] ?

∗ des poids dans la formule des caractères de [Demazure] ?

∗ des chemins de branchement des représentations des groupes symétriques [Young] ou linéaires/unitaires [Gelfand-Cetlin] ? Dans ce dernier cas, ils se transforment en pyramides pointant vers le bas et portent le nom de Gelfand-Cetlin Patterns.

Respectivement supportés par :

1le C.N.R.S., le Programme de Recherches (coordonnées) en Informatique, le Programme d’échanges européen PROCOPE;

2lui-même.

∗ des partitions planes [MacMahon] [Gordon] [Hillman-Grassl] ?

∗ des objets décrivant les sous-suites monotones d’une suite d’entiers [Schensted], [Greene] ?

∗ des chaînes dans le treillis des partitions [Kreweras] ?

∗ des ensembles de chemins non coupants dans ℤ × ℤ [Gessel-Viennot] ?

∗ des mots [Barthes] donnant naissance au monoïde plaxique [Lascoux et Schützenberger] ?

∗ des cellules gauches [Kazhdan-Lusztig] ?

∗ des décompositions réduites des éléments du groupe symétrique : monoïde nilplaxique [Lascoux et Schützenberger], balanced tableaux [Edelman et Greene] ? ? ?

Ne serait ce donc que par le nombre de leurs avatars (et encore avons nous totalement ignoré les travaux de l’ecole californienne de combinatoire), les tableaux mériteraient une place exceptionelle dans la mythologie mathématique.

Nous inspirant d’Ehresmann qui avait défini à l’aide de tableaux l’ordre que l’on appelle soit fort (strong), soit de Bruhat (Bruhat’s) sur le groupe symétrique, nous entendons mettre en avant une autre de leurs vertus, celle de fournir une structure d’ordre Eulérienne sur les permutations.

Tout d’abord, les tableaux sont des produits de colonnes :

Soit 𝔸 = {a_{1} < a_{2} < ⋯ } un alphabet, ℤ⟨𝔸⟩ son algèbre libre. Un mot v = x_{1} … x_{r} est une colonnes de degré r (= |v|) ssi x_{1} > ⋯ > x_{r}, x_{i} ∈ 𝔸. On munit l’ensemble des colonnes de l’ordre ≫ : une colonne v = x_{1} … x_{r} domine une autre w = y_{1} … y_{p} (v ≫ w) ssi il existe une fonction surjective croissante de l’ensemble des lettres de v dans celui de w, c’est-à-dire s’il existe un sous-mot v′ de v et une bijection croissante des lettres de v′ sur celle de w. En d’autres termes,

|v| ≥ |w|, i.e. r ≥ p (1) x_{r} ≤ y_{p}, x_{r−1} ≤ y_{p−1}, … (2)

Un produit t = v_{1}v_{2} … de colonnes est un tableau ssi v_{1} ≫ v_{2} ≫ v_{3} ≫ ⋯, c’est-à-dire ssi c’est une chaîne de colonnes. On appelle forme d’un tableau la suite I des degrés des colonnes de t : I = (I_{1}, I_{2}, …) = (|v_{1}|, |v_{2}|, |v_{3}|, …) ; c’est donc une partition, i.e. I_{1} ≥ I_{2} ≥ I_{3} ≥ · · ·.

Par exemple, le mot 521 43 3 6 (que nous avons décomposé en ses colonnes) est un tableau de forme 3, 2, 1, 1 ; on peut le représenter planairement par l’objet

5 2 4 1 3 3 6 . En d’autres termes, un mot est un tableau si et seulement si il provient de la lecture idoine (par colonnes) d’un tableau de Young. D’autres lectures sont possibles, par exemple la lecture par lignes ; on peut aussi prendre le tableau formé des complémentaires (dans l’alphabet) de chacune de ses colonnes ou pousser, jeu de taquin aidant, un tableau dans le cadran nord-est d’un rectangle le contenant : dans ce dernier cas, on obtient un contre-tableau, que l’on pourrait définir plus simplement comme une chaîne de colonnes pour l’ordre ≪ : v ≪ w ssi il existe une injection croissante de l’ensemble des lettres de v dans celui de w.

En fait, une partie des propriétés des tableaux provient de ces différentes involutions, ainsi que de leurs combinaisons avec d’autres moins immédiates, chacune pouvant jouer un rôle spécifique important dans un des différents avatars énumérés ci-dessus.

Une clef est un tableau tel que pour chaque entier k, la colonne w_{k+1} est un sous-mot de w_{k}. Les clefs jouent un rôle particulier en théorie p–groupes Abéliens et des polynômes de Hall-Littlewood : ce sont les tableaux de charge nulle (cf. [Macdonald, III.6]). Enfin, un mot (en particulier, un tableau) est standard si c’est une permutation de 1, 2, …, r.

Une application remarquable envoyant bijectivement les mots sur les paires de tableaux de même forme a été découverte par Schensted. Elle semble être restée presqu’ignorée jusqu’à ce qu’un article de Knuth ne lui confère le statut qu’elle mérite. Nous préférons mettre l’accent sur la structure de monoïde sousjacente à la contruction de Schensted.

On munit l’algèbre libre d’une congruence ≡ (dite plaxique), engendrée par les relations élementaires suivantes, relations isolées par Knuth et qui sont la formulation algèbrique de la construction de Schensted :

(3)  \begin{matrix}a_{k}a_{i}a_{j} ≡ a_{i}a_{k}a_{j} et a_{j}a_{i}a_{k} ≡ a_{j}a_{k}a_{i} \\ a_{j}a_{i}a_{j} ≡ a_{j}a_{j}a_{i} et a_{j}a_{i}a_{i} ≡ a_{i}a_{j}a_{i} \end{matrix} \} i < j < k .

Deux mots sont congrus ssi ils donnent par l’algorithme de Schensted le même tableau ; le deuxiéme tableau (dit tableau d’insertion ; c’est le Q–symbole de Schensted) associé à un mot v = x_{1}x_{2} … est celui qui décrit la suite des formes des tableaux congrus aux facteurs gauches successifs de v, i.e. aux mots x_{1}, x_{1}x_{2}, x_{1}x_{2}x_{3}, …

On parcourt la classe de congruence d’un mot v en faisant varier le tableau d’insertion QQ(v) : l’application v → Q(v) est une bijection de la classe de v sur l’ensemble des tableaux standards de même forme que le tableau congru à v. Ainsi donc, toute condition déterminant le tableau d’insertion fournit par là même un mot unique dans sa classe. Nous n’aurons besoin ici que du cas particulier suivant :

Lemme 4. Soit t un tableau de forme I = (I_{1}, I_{2}, …, I_{r}) ; alors pour toute permutation J = (J_{1}, …, J_{r}) de I, il existe dans la classe de congruence de t un et un seul mot v = v_{1} … v_{r}, produit de colonnes de degrés respectifs J_{1}, …, J_{r}. Si H est une autre permutation de J et w = w_{1} … w_{r} let mot associé, alors H_{r} ≥ J_{r} implique que v_{r} est un sous-mot de w_{r}.

Exemple 5. Le tableau t = 531 62 4 a trois colonnes de longueurs différentes, et donc il y a 6 permutations de sa forme auxquelles correspondent les mots (lire verticalement !) :

/ \begin{matrix}5 \\ 1 \end{matrix} · 6 3 2 4 ———— 5 1 3 · \begin{matrix}6 \\ 4 \\ 2 \end{matrix} \

5 3 6 1 2 4  1 5 6 3 4 2

\ \begin{matrix}5 \\ 3 \\ 1 & 2 \end{matrix} · {6 \atop 4} ———— 1 · \begin{matrix}5 \\ 3 & 6 \\ 2 & 4 \end{matrix} /

et donc la clef gauche 5 3 5 1 1 1 et la clef droite 6 4 6 2 4 4 .

En particulier, lorsque t est une clef, ses colonnes commutent deux à deux (dans le monoide plaxique) et réciproquement, cette propriété de commutation caractérise les clefs. Pour un tableau général, avec les notations du lemme 4, on dit que v_{1} (resp. v_{r}) est le facteur gauche (resp. droit) du couple (J, t). Pour chaque part I_{k} de I, on a donc obtenu, par la gauche, une colonne et une seule de degré I_{k}. D’aprés le lemme 4, ces colonnes sont des sous-mots les unes des autres. En d’autres termes, le produit des facteurs gauches de degré respectifs I_{1}, I_{2}, … est une clef dite clef gauche de t et notée K_{−}(t). On définit similairement la clef droite K_{+}(t) de t.

Par exemple, le tableau 541 62 75 6 7 est congru aux mots

51 642 75 6 7, 1 542 65 76 7, 1 542 65 7 76, 51 64 5 7 762,

ce que l’on peut écrire planairement si l’on préfère :

5 4 6 7 1 2 5 6 7 ≡ {5 \atop 1} · 6 4 7 2 5 6 7 ≡ ^{1} · 5 4 6 7 2 5 6 7 ≡ ^{1} · 5 4 6 2 5 7 · {7 \atop 6} ≡ _{1 4 5 7}^{5 6} · 7 6 2 .

Avec les facteurs gauches que l’on répète le nombre de fois qu’il faut pour

remplir le diagramme 3 2 2 1 1, on obtient la clef gauche 5 4 5 5 1 1 1 1 1 , tandis que

la clef droite est égale quant à elle à 7 6 7 7 2 6 6 7 7 .

Les clef d’un tableau jouent un rôle décisif en maint probléme. Ainsi, la base standard de Lakshmibai-Musili-Seshadri, pour un poids I et une varieté de Schubert S_{μ}, est l’ensemble des tableaux de forme I, de clef droite K(μ, I), cf. [L&S2]. En outre, pour ce qui est de la structure multiplicative de ces bases, le produit de deux tableaux t, t′ de forme I, est congru à un tableau de forme I ∪I (i.e. à la partition I_{1}I_{1}I_{2}I_{2}I_{3}I_{3} …) ssi K_{+}(t) ≤ K_{−}(t′) [L&S2]. Par ailleurs, les clefs donnent la décomposition d’un polynôme de Schubert X_{μ} en fonction des caractéres de Demazure et des décompositions réduites de la permutation μ, cf. [L&S1].

Venons en au groupe symétrique : à toute permutation μ de 𝔖(n) et toute partition I, on associe une clef, notée K(μ, I), en prenant la suite des facteurs gauches (réordonnés) de longueurs respectives I_{1}, I_{2}, … Ainsi, le couple μ = 582491736, I = 7, 5, 4, 2 donne la clef 9875421 98542 8542 85.

L’ordre lettre-à-lettre sur les mots (i.e. x_{1}x_{2} … ≤ y_{1}y_{2} … ssi x_{1} ≤ y_{1}, x_{2} ≤ y_{2}, …) induit un ordre sur les clefs de même forme. D’aprés Ehresmann, une permutation μ de 𝔖(n) est inférieure à une autre ζ ssi la clef K(μ, n … 21) est inférieure à K(ζ, n … 21).

Le groupe symétrique est ainsi muni d’une structure d’ordre gradué (rank poset), le grade étant le nombre d’inversions (il est dit aussi, plus majoritairement et maladroitement, longueur d’une permutation μ, alors que c’est la longueur d’un mot réduit (en les transpositions simples) égal à la permutation). A titre transitoire, nous adopterons le mot hauteur et noterons |μ|.

L’ordre d’Ehresmann a de multiples propriétés, en particulier des propriétés de dualité qui sont dites d’Eulérianité (Eulerian poset).

L’exemple classique d’une telle structure est celui de l’ensemble des faces d’un polytope convexe (cf. [Grünbaum] et surtout [Macdonald] pour les résultats fondamentaux concernant les polynômes associés).

Soit A une algèbre munie d’un automorphisme involutif σ. Un élément 𝔼 de A est Eulérien ssi il est inversible et 𝔼^{−1} = 𝔼^{σ}. Donc si 𝔽 est un autre élément Eulérien, il en est encore de même de 𝔼𝔽𝔼 puisque (𝔼𝔽𝔼)^{−1} = 𝔼^{−1}𝔽^{−1}𝔼^{−1} = (𝔼𝔽𝔼)^{σ}, bien que 𝔼𝔽 ne soit Eulérien que si 𝔽 commute avec 𝔼.

Dans le cas particulier d’une algèbre graduée A = ⨁_{i≥0} A_{i}, A_{i}A_{j} ⊆ A_{i+j}, soit σ l’automorphisme envoyant ∑ 𝔼_{i} (avec 𝔼_{i} ∈ A_{i}) sur ∑(−1)^{i}𝔼_{i}. Soit de façon encore plus particulière 𝔼 = ∑ 𝔼_{k} la matrice d’incidence d’une relation d’ordre graduée, où E_{k}, k ≥ 0, est la sous-matrice représentant les arêtes de longueur k. La condition d’Eulérianité se réduit aux conditions

(6)  pour tout entier k pair, 𝔼_{k}𝔼_{0} − 𝔼_{k−1}𝔼_{1} + 𝔼_{k−2}𝔼_{2} − ⋯ = 0 ,

Elle équivaut en ce cas à l’hypothèse que la fonction de Möbius de la relation d’ordre ne prend que les valeurs ±1 suivant la parité de la hauteur, ou encore que chaque intervalle (non réduit à un élèment) contient autant d’éléments en hauteur paire qu’en hauteur impaire (cf. les exercices de Stanley [S2]). C’est le cas de l’ordre d’Ehresmann sur le groupe symétrique, ainsi que l’a montré Verma [V] :

Lemme 7. La relation d’ordre d’Ehresmann sur le groupe symétrique est Eulérienne.

Nous présentons une autre structure Eulérienne sur 𝔖(n), étendant la structure d’Ehresmann, en interprétant les tableaux de forme une partition fixe I comme des arêtes :

Définition 8. Le I-tableautoëdre (I-tableautoedron) est le graphe ordonné dont les sommets sont les permutations de 𝔖(n) et les arêtes, les tableaux sur l’alphabet {1, …, n} de forme I : un tableau t est une arête entre ν et μ ssi la clef gauche de t est K(ν, I) et sa clef droite est K(μ, I).

Soit Γ la matrice (graduée) des arêtes du I-tableautoëdre, 𝔼 la matrice de l’ordre d’Ehresmann. On notera que 𝔼 ne fait intervenir que des tableaux bien particuliers, les clefs, alors que Γ met en jeu tous les tableaux d’une forme donnée, les clefs étant alors des boucles. Comme il ne peut y avoir d’arêtes entre ν et μ que si ν ≤ μ pour l’ordre d’Ehresmann, la nullité 𝔼_{νμ} = 0 implique Γ_{νμ} = 0. Par réference à la géométrie, disons que I est très ample si tous les entiers 1, 2, …, n − 1 sont des parts de I (il est équivalent d’imposer que la partition conjuguée de I, J = J_{1} … J_{n}, a toutes ses parts différentes ; en particulier, la part 0 ne peut figurer qu’une fois au plus dans J).

Proposition 9. La matrice Γ des arêtes d’un I-tableautoëdre, I partition très ample, est Eulérienne.

Preuve. Appelons chaîne toute suite des tableaux t_{1}, t_{2}, t_{3}, …, t_{r} telle que K_{+}(t_{1}) ≤ K_{−}(t_{2}); K_{+}(t_{2}) ≤ K_{−}(t_{3}), … et identifions la au mot t_{1}t_{2}t_{3} ⋯ t_{r} dans l’algèbre libre.

Soit, pour toute permutation μ, F_{μI}(z) la fonction génératrice des chaînes inférieures à μ, i.e. la fonction ∑ z^{r} t_{1} ⋯ t_{r}, somme sur toutes les chaînes telles que K_{+}(t_{r}) ≤ K(μ, I). Dans le cas spécial de la partition E = n … 2 1, on montre algèbriquement dans [L-S] que l’image commutative (i.e. dans ℤ[𝔸, z]) de F_{μE}(z) est invariante par l’involution 𝔸 → 𝔸^{−1} = {1/a_{1}, 1/a_{2}, … } & z → 1/z. Identifiant les termes correspondants dans F et son image, on obtient les relations

(10) ∀ν, μ : ν < μ, ∑(−1)^{r}t_{1} ⋯ t_{r+1} / K_{1} ⋯ K_{r}

= ∑ K(ν, E) K(μ, E) / t dans ℤ[𝔸],

la première somme étant sur toutes les chaînes du E-tableautoëdre joignant ν à μ, en notant K_{1} = K_{+}(t_{1}) = K_{−}(t_{2}); …; K_{r} = K_{+}(t_{r}) = K_{−}(t_{r+1}); la deuxiéme somme étant sur les arêtes de ν à μ, i.e. sur les t tels que K(ν, E) = K_{−}(t) et K_{+}(t) = K(μ, E).

En fait, la propriété que 𝔼 soit Eulérienne entraine l’élimination des chaînes telles qu’un des t_{1} soit une clef. La somme (10) se restreint donc aux chaînes sans boucles, i.e. telles que K(ν, E) = K_{−}(t_{1}) < K_{+}(t_{1}) = K_{1} = K_{−}(t_{2}) < K_{+}(t_{2}) … K_{r} = K_{−}(t_{r+1}) < K_{+}(t_{r+1}) = K(μ, E).

Utilisant les relations (10) pour les sous-chaînes ayant au moins deux maillons, on transforme (10) en les relations

(11)  ∀ν, μ : ν < μ, ∑(−1)^{h}t_{1}/t_{2} = 0 dans ℤ[𝔸],

somme sur toutes les paires de tableaux : K_{−}(t_{1}) = K(ν, E); K_{+}(t_{1}) = K_{−}(t_{2}); K_{+}(t_{2}) = K(μ, E), h étant la hauteur de la permutation de clef K_{+}(t_{1}).

Il convient de noter que la relation (11) est plus symétrique que (10) : ses termes extrémes sont en effet (−1)^{|ν|}K(ν, E) ∑ 1/t et (−1)^{|μ|} ∑ t/K(μ, E), somme sur toutes les arêtes t de ν à μ.

La spécialisation 𝔸 → {1, …, 1} de la relation (11) donne très exactement l’entrée d’indice ν, μ de la matrice Γ_{h} − Γ_{h−1}Γ_{1} + Γ_{h−2}Γ_{2} − ⋯ et donc la matrice Γ est Eulérienne, dans le cas de la partition E = n … 21.

On passe du cas de E à celui d’une partition très ample générale à l’aide de techniques sans mystères et sans relations avec l’Eulérianité, que l’on ne trouvera pas ici. □

Exemple 12. L’intervalle [ν = 1324, μ = 2413] comprend quatre éléments dont

4 2 4 1 2 2

les clefs sont 4 2 4 1 1 1  3 2 3 1 2 2 et les arêtes autres que les boucles,

3 2 3 1 1 1

[figure: ∘ ; ∥]

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

∘[figure] [figure]  3 2 4 1 1 2  [figure] [figure] ∘
3 2 4 1 1 1  3 2 3 1 1 2

[figure: ∥ ; ∘]

La relation (11) est dans ce cas, en écrivant n pour a_{n} :

323111/324112 − 324111/424112 − 323112/324122 + 324112/424122 = 0.

La nullité de la somme (11) cache, ainsi qu’il est fréquent en théorie des tableaux, une propriété plus forte d’annulation (suite exacte d’annulation) : tout terme (−1)^{h}t_{1}/t_{2} s’élimine avec un terme (−1)^{h+1}t′_{1}/t′_{2} ou bien un terme (−1)^{h−1}t′_{1}/t′_{2}.

Les fonctions intéressantes en géométrie sont les quatre séries formelles ∑ z^{r}(𝔼Γ)^{r}𝔼 = H̄_{≤≤} ; ∑ z^{r}(Γ𝔼)^{r}Γ = H̄_{==} ; ∑ z^{r}(Γ𝔼)^{r} = H̄_{=≤} et ∑ z^{r}(𝔼Γ)^{r} = H̄_{≤=} .

L’entrée H̄_{∗∗}(ν, μ) de chacune de ces matrices est la spécialisation en 𝔸 → {1, …, 1} de la fonction génératrice H_{∗∗}(ν, μ) des chaînes t_{1} ⋯ t_{r} telles que

K_{+}(t_{1}) ≤ K_{−}(t_{2}); K_{+}(t_{2}) ≤ K_{−}(t_{3}); …; K_{+}(t_{r−1}) ≤ K_{−}(t_{r})

vérifiant de plus les conditions aux bords respectives suivantes

K(ν, I) ≤ K_{−}(t_{1}) & K_{+}(t_{r}) ≤ K(μ, I) pour H_{≤≤}(ν, μ),
K(ν, I) = K_{−}(t_{1}) & K_{+}(t_{r}) = K(μ, I) pour H_{==}(ν, μ),
K(ν, I) = K_{−}(t_{1}) & K_{+}(t_{r}) ≤ K(μ, I) pour H_{=≤}(ν, μ),
K(ν, I) ≤ K_{−}(t_{1}) & K_{+}(t_{r}) = K(μ, I) pour H_{≤=}(ν, μ).

On sait que, 𝔼 et Γ étant Eulériennes, chacune des séries (∑ z^{r}𝔼^{r})_{νμ} et (∑ z^{r}Γ^{r})_{νμ} est invariante (au signe près) par l’échange r → −r.

La spécialisation en 𝔸 → {1, …, 1} de chacune des fonctions H_{∗∗}(ν, μ) est une fraction rationnelle

P_{∗∗}(ν, μ; z)/(1 − z)^{|μ|−|ν|}.

La possibilité de composer les structures Eulériennes, ainsi qu’on l’a mentionné ci-dessus, permet d’obtenir les réciprocités suivantes que l’on appelerait Formules de Réciprocité si l’on ne reculait, aprés d’autres auteurs, devant l’abus monstrueux de ce terme (cf. [S1] ).

Lemme 13. P_{≤≤}(ν, μ; z) est réciproque de P_{==}(ν, μ; z), i.e est égal á z^{∗}P_{==}(ν, μ; 1/z). De même, P_{=≤}(ν, μ; z) est réciproque de P_{≤=}(νμ; z).

Traitons, par exemple, de manière détaillée le cas de hauteur 2 (|μ|−|ν| = 2), avec les arêtes :

∑ β [figure]  [figure]_{∑ β′}  K′
∑ γ et l’ordre sur les clefs k[figure] [figure] [figure] [figure] k′
∑ α [figure]  [figure]^{∑ α′}  K

Les fonctions en cause sont, au facteur 1/(1−zK)(1−zK′) près, en décomposant les chaînes en familles suivant les tableaux non clefs qu’elles comportent :

H_{≤≤} = \frac{1−z^{2}kk′}{(1−zk)(1−zk′)} + z ∑ γ + ^{\frac{z ∑ α+z ∑ β+z^{2} ∑ αβ}{1−zk}}

+ \frac{z ∑ α′ + z ∑ β′ + z^{2} ∑ α′β′}{1 − zk′} ,

H_{==} = z^{2}KK′ \frac{1−z^{2}kk′}{(1−zk)(1−zk′)} + z ∑ γ + z^{2}^{\frac{∑ αK+K ∑ β+∑ αβ}{1−zk}}

+ z^{2} \frac{∑ α′K + K ∑ β′ + ∑ α′β′}{1 − zk′} ,

H_{=≤} = zK\frac{1−z^{2}kk′}{(1−zk)(1−zk′)} + z ∑ γ + ^{\frac{z ∑ α+z^{2}K ∑ β+z^{2} ∑ αβ}{1−zk}}

+ \frac{z ∑ α′ + z^{2}K ∑ β′ + z^{2} ∑ α′β′}{1 − zk′} ,

H_{≤=} = zK′ \frac{1−z^{2}kk′}{(1−zk)(1−zk′)} + z ∑ γ + ^{\frac{z^{2} ∑ αK′+z ∑ β+z^{2} ∑ αβ}{1−zk}}

+ \frac{z^{2} ∑ α′K′ + z ∑ β′ + z^{2} ∑ α′β′}{1 − zk′} .

On a donc les expressions suivantes des polynômes P_{∗∗}, en notant |α| le cardinal de l’ensemble des arêtes α,

P_{≤≤} = 1 + z + (z − z^{2})|γ| + z(|α| + |β| + |α′| + |β′|) + z^{2}(|αβ| + |α′β′|),
P_{==} = z^{2} + z^{3} + (z − z^{2})|γ| + z^{2}(|α| + |β| + |α′| + |β′| + |αβ| + |α′β′|),
P_{=≤} = z + z^{2} + (z − z^{2})|γ| + z(|α| + |α′|) + z^{2}(|β| + |β′| + |αβ| + |α′β′|),
P_{≤=} = z + z^{2} + (z − z^{2})|γ| + z(|β| + |β′|) + z^{2}(|α| + |α′| + |αβ| + |α′β′|).

Sur ces expressions explicites, on voit sans conteste que les propriétés de réciprocité annoncées résultent de la spécialisation 𝔸 → {1, …, 1} de la relation (11), i.e. de la relation d’Eulérianité

|γ| − |α||β| − |α′||β′| + |γ| = 0.

References

[G] B. Grünbaum, Convex polytopes, Interscience Pub., 1967. [L&S1] A. Lascoux & M. P. Schützenberger, Noncommutative Schubert polynomials (en

Russie) (version précédente : Caractéres libres), Funktsional. Anal. i Prilozhen. 23 (1989), 63–64, traduction anglaise: Funct. Anal. Appl. 23 (1989), 223–225.

[L&S2] A. Lascoux & M. P. Schützenberger, Keys and Standard Bases, Invariant theory and tableaux (Minneapolis, MN, 1988), IMA Vol. Math. Appl., 19, Springer, New York-Berlin, 1990, pp. 125–144.

[L-S] A. Lascoux, Anneau de Grothendieck de la variété de drapeaux, The Grothendieck Festschrift, Vol. III, Progr. Math., 88, Birkhäuser, Boston, 1990, pp. 1–34.

[M1] I. G. Macdonald, The volume of a lattice polyhedron, Proc. Camb. Phil. Soc. 59 (1963), 719-726.

[M1] I. G. Macdonald, Polynomials associated with finite cell-complexes, J. Lond. Math. Soc. (2) 4 (1971), 181-192.

[S1] R. Stanley, Combinatorial Reciprocity Theorems, Adv. in Math. 14 (1974), 194-253.

[S2] R. Stanley, Enumerative Combinatorics, Wadsworth, Pacific Grove, California, 1986.

[V] D.-N. Verma, Möbius inversion for the Bruhat ordering on a Weyl group, Ann. Scient. E.N.S. 4 (1971), 393-398.

L.I.T.P., Université Paris 7, 2 Place Jussieu, 75251 PARIS Ced 05