ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

13. Combinatorics

1991 MS Classification: 05 E 15 Lascoux, Alain, CNRS, Université de Marne La Vallée, France Ordering the symmetric group: Why use Iwahori-Hecke algebras?

As a Coxeter group, the symmetric group is generated by simple transpositions σ_{i} := (i, i + 1). Taking subwords of reduced products of σ_{i} induces an order on permutations, the Bruhat order. Instead of enumerating all subwords, one can replace decompositions σ_{i}σ_{j} ⋯ σ_{h} by products (1 + π_{i})(1 + π_{j}) ⋯ (1 + π_{h}) and expand them in the 0-Hecke algebra (whose generators π_{i} satisfy the braid relations, and π_{i}^{2} = −π_{i}). One then obtains the sum of all permutations below a given one. Another method consists in taking left factors of permutations (as words in {1, 2, … }), sorting them and comparing them componentwise. This amounts to associating to a permutation, a Young tableau encoding all the cosets μP, where μ ∈ S_{n} and where the P ’s are all the maximal parabolic subgroups. One can instead use double cosets P μ P′ and associate to a permutation the minimum representatives β of all the double cosets, such that β is below μ in the Bruhat order: S_{n} ∋ μ ↦ B(μ) := {β : β ≤ μ}. The order becomes inclusion of sets :

μ ≤ ζ ⇔ B(μ) ⊆ B(ζ) .

This furnishes an embedding of the symmetric group, as an ordered set, into the (distributive) lattice of alternating sign matrices. However, being able to compare permutations does not provide a way to describe intervals for the Bruhat order. For example, since the symmetric group is a rank-poset, combinatorists would like to describe the Poincaré polynomial of an initial interval [1, μ] (for geometers this polynomial is equal to the number of points of a Schubert variety over the finite field F_{q}). For some permutations (which correspond to non-singular Schubert varieties) this polynomial is known to be symmetric and to factor into q-integers 1 + q + ⋯ + q^{k}. One can lift such a factorization, not to the group algebra of S_{n}, but to the Iwahori-Hecke algebra (the generators T_{i} satisfy the braid relations, and (T_{i} + 1)(T_{i} − q) = 0). For example the element

c_{μ} := ∑_{μ≤[4312]}(−q)^{ℓ(μ)}T_{μ} = (T_{3}−q)(T_{2}− \frac{q^{2}}{1 + q})(T_{1}− \frac{q^{2}}{1 + q})(T_{3}−q)(T_{2}−q)

becomes, under the specialization T_{1} = T_{2} = T_{3} = −1, equal to −(1+q)(1+ q + q^{2})^{2}. This special element c_{μ} belongs in fact to the Kazhdan-Lusztig basis which is a distinguished linear basis of the Hecke algebra of fundamental importance in representation theory and in geometry. The coefficients of the matrix expressing the Kazhdan-Lusztig basis into the standard basis T_{μ} are called Kazhdan-Lusztig polynomials. These are polynomials in q with (small) integral positive coefficients, that are, unfortunately, hard to obtain, despite their elementary recursions. It is still a challenge to provide a combinatorial description of these polynomials. Such a description would have applications to properties of the Bruhat order, to desingularizations of Schubert varieties, multiplicities of Verma modules, &c. In the case of the minimum representatives β which code the order (and correspond to determinantal varieties, i. e. varieties defined by the vanishing of minors of a given order of a generic matrix) the Kazhdan-Lusztig polynomials are just Gauss polynomials, also called q-binomial coefficients. We shall show that the above stated embedding of the symmetric group into a lattice furnishes an explicit combinatorial description of Kazhdan-Lusztig polynomials in the case of “3412-avoiding” permutations. References: D. Kazhdan, G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165–184. A. Lascoux, M. P. Schützenberger, Treillis et Bases des Groupes de Coxeter, Electronic J. of Combinatorics 3 (1996)