Kazhdan-Lusztig and R-polynomials from a combinatorial point of view

Francesco Brenti^{1}

In onore di Adriano M. Garsia

1 Introduction

In their fundamental paper [18] Kazhdan and Lusztig defined, for every Coxeter group W, a family of polynomials, indexed by pairs of elements of W, which have become known as the Kazhdan-Lusztig polynomials of W (see, e.g., [17], Chap. 7). These polynomials are intimately related to the Bruhat order of W and to the algebraic geometry of Schubert varieties, and have proven to be of fundamental importance in representation theory. In order to prove the existence of these polynomials Kazhdan and Lusztig defined another family of polynomials (see [18], §2) which are intimately related to the multiplicative structure of the Hecke algebra associated to W. These polynomials are now known as the R-polynomials of W (see, e.g., [17], §7.5) and their importance stems mainly from the fact that their knowledge is equivalent to that of the Kazhdan-Lusztig polynomials.

While Kazhdan-Lusztig and R-polynomials are usually defined algebraically in terms of Hecke algebras (see, e.g., [17]), or through complicated combinatorial recursions (see, e.g., [18], §2.2), in recent years simpler combinatorial rules to compute them have been found. These rules not only make these objects more concrete, and accessible to a wider audience, but also make it easier to apply combinatorial reasoning and techniques to them. Since these polynomials are still not very well understood, (see, e.g., [10], p. 95) and several conjectures and open problems exist about them, many of a combinatorial nature, we feel that these combinatorial rules are worthy of further investigation. Unfortunately, while the rules themselves are purely combinatorial, the proofs of their correctness are not and are usually very technical.

In this paper we survey and illustrate two of these rules, and we present some intriguing conjectures and open problems on the polynomials (some old and some new) together with the evidence that exists for them. To help the reader get a better feeling for these conjectures and problems we have included two sections which survey the main combinatorial properties which are known for the Kazhdan-Lusztig and R-polynomials. Our goal is to make the material more easily accessible and understandable by stripping it of all the technical details that the original papers contain and by illustrating it with several examples, while at the same time providing references for further reading for the interested reader. We only treat the symmetric groups since the material is particularly interesting, especially from a combinatorial point of view, in this case. Our hope is that this paper will stimulate combinatorial research on these polynomials for the symmetric groups, since we firmly believe that they hide a wealth of beautiful and deep combinatorial results.

1Partially supported by NSF grant DMS 9304580 and by EC grant No. CHRX-CT93-0400.

The organization of the paper is very simple and is as follows. In the next section we collect some notation, definitions, and results, that will be needed in the rest of the paper. In section 3 we describe in detail a combinatorial rule for the computation of the R-polynomials of the symmetric groups. In section 4 we survey some of the main combinatorial properties that are known for these R-polynomials. In section 5 we describe in detail a combinatorial rule for the computation of the Kazhdan-Lusztig polynomials of the symmetric groups, and in section 6 we survey some of the main combinatorial properties that are known for them. Finally, in section 7, we discuss several conjectures and open problems on the Kazhdan-Lusztig and Rpolynomials, together with the evidence that exists in their support. It should be noted that, because of their importance in so many different fields of mathematics, it is almost impossible to survey all of the combinatorial properties that are known for the Kazhdan-Lusztig and R-polynomials of the symmetric groups. While we have tried to be as comprehensive as possible in sections 4 and 6, we make no claims in this direction.

2 Notation and Preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of this paper. We let P =^{def} {1, 2, 3, …} , N=^{def}P ∪{0}, and Z be the set of integers; for a ∈N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). Given n, m ∈ P, n ≤ m, we let [n, m] =^{def} [m] \ [n − 1]. We write S = {a_{1}, …, a_{r}}_{<} to mean that S = {a_{1}, …, a_{r}} and a_{1} < … < a_{r}. The cardinality of a set A will be denoted by |A|. Given a polynomial P (q), and i ∈ N, we will denote by [q^{i}](P (q)) the coefficient of q^{i} in P (q).

Given a set T we let S(T) be the set of all bijections π : T → T, and S_{n} =^{def} S([n]). If σ ∈ S(T) and T =^{def} {t_{1}, …, t_{r}}_{<} ⊆ P then we write σ = σ_{1} … σ_{r} to mean that σ(t_{i}) = σ_{i}, for i = 1, …, r. If σ ∈ S_{n} then we also write σ in disjoint cycle form (see, e.g., [25], p.17) and we will usually omit to write the 1-cycles of σ. For example, if σ = 365492187 then we also write σ = (9, 7, 1, 3, 5)(2, 6). Given σ, τ ∈ S_{n} we let στ =^{def} σ ∘ τ (composition of functions) so that, for example, (1, 2)(2, 3) = (1, 2, 3).

We will follow [25], Chap. 3, for notation and terminology concerning partially ordered sets. In particular, we say that a finite graded poset P with ˆ0 and ˆ1 is Eulerian if μ(x, y) = (−1)^{ρ(y)−ρ(x)} for all x, y ∈ P, x ≤ y, where ρ : P → N is the rank function of P. Recall (see, e.g., [25], §3.14, p. 138, or [26], §2, p. 190) that to any Eulerian poset P as above there are associated two polynomials, denoted f(P; q) and g(P; q), defined inductively as follows:

i) if |P | = 1 then f(P; q) =^{def} g(P; q) =^{def} 1;

ii) if P has rank n + 1 ≥ 1 and f(P; q) = ∑_{i≥0} k_{i}q^{i} then

g(P; q) =^{def} ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(k_{i} − k_{i−1})q^{i} ,  (1)

(where k_{−1} =^{def} 0);

iii) if P has rank n + 1 ≥ 1 then

f(P; q) =^{def} ∑_{a∈P \{ˆ1}} g([ˆ0, a]; q) (q − 1)^{n−ρ(a)} .  (2)

The polynomials f(P; q) and g(P; q) were introduced in [26] and are two very subtle invariants of the Eulerian poset P (see [25], §3.14, and [26], §§2,3, for further information). We call g(P; q) the g-polynomial of P, and (h_{0}, …, h_{n}), where h_{i} =^{def} [q^{n−i}](f(P; q)), for i = 0, …, n, the h-vector of P.

Given σ ∈ S_{n} we let

D(σ) =^{def} {i ∈ [n − 1] : σ(i) > σ(i + 1)} ,

d(σ) = |D(σ)| ,

and

l(σ) =^{def} inv(σ) =^{def} |{(a, b) ∈ [n] × [n] : a < b, σ(a) > σ(b)}|

For example, if σ = 615243 then l(σ) = 9 and D(σ) = {(1, 3, 5)}. We call D(σ) the descent set of σ and say that σ has d(σ) descents. We denote by e the identity of S_{n}. We will always assume that S_{n} is partially ordered by (strong) Bruhat order. Recall (see, e.g., [23], Chapter 1) that this means that x ≤ y if and only if there exist r ∈ N and a_{1}, b_{1}, …, a_{r}, b_{r} ∈ [n] such that (a_{r}, b_{r}) … (a_{1}, b_{1})x = y and l((a_{i}, b_{i}) … (a_{1}, b_{1})x) > l((a_{i−1}, b_{i−1}) … (a_{1}, b_{1})x) for i = 1, …, r. For example, the Hasse diagram of the Bruhat order on S_{3} is shown in Figure 1. It is well known (see, e.g., [1], Corollary 1) that intervals of S_{n} (and their duals) are Eulerian posets.

[figure: 123; 321; 213; 312; 132; 231]

Figure 1: The Bruhat order on S_{3}.

The following characterization of the Bruhat order of S_{n} is well known, and will be used often in this work. We refer the reader to, e.g., [23], Chapter 1, for a proof. For σ ∈ S_{n}, and i ∈ [n], let

{σ^{i,1}, …, σ^{i,i}}_{<} =^{def} {σ(1), …, σ(i)} .  (3)

Theorem 2.1 Let σ, τ ∈ S_{n}. Then σ ≤ τ if and only if σ^{i,j} ≤ τ^{i,j} for all 1 ≤ j ≤ i ≤ n − 1.

For example, if σ = 4123 and τ = 2431 then (σ^{1,1}, σ^{2,1}, σ^{2,2}, …, σ^{3,3}) = (4, 1, 4, 1, 2, 4) and (τ^{1,1}, τ^{2,1}, τ^{2,2}, …, τ^{3,3}) = (2, 2, 4, 2, 3, 4) and hence σ and τ are incomparable in Bruhat order.

As stated in section 1, the object of this paper is to describe two combinatorial rules for the computation of the Kazhdan-Lusztig and R-polynomials of the symmetric groups and to survey the main combinatorial facts and open problems about them. Since these combinatorial rules can be taken as definitions of these polynomials, we won’t define them here, but refer the interested reader to [17], Chapter 7, for their (usual) defintion. For the moment, we only say that the Kazhdan-Lusztig and R-polynomials are two families of polynomials (in one variable) indexed by pairs of permutations, which we will denote (as customary) by {P_{σ,τ}(q)}_{σ,τ∈S_{n}} and {R_{σ,τ}(q)}_{σ,τ∈S_{n}}, respectively. Thus we will write, for example, R_{1243,4231}(q) and P_{e,(1,n)}(q). We say that p(q) ∈ Z[q] is an R-polynomial (respectively, a Kazhdan-Lusztig polynomial) if there are n ∈ P and σ, τ ∈ S_{n} such that p(q) = R_{σ,τ}(q) (respectively, P_{σ,τ}(q)). We will often find it convenient to identify S(T) with S_{|T |} for T ⊆ P. We will do this by identifying t_{i} with i, for i = 1, …, r, if {t_{1}, …, t_{r}}_{<} =^{def} T.

So, for example, R_{5294,4592}(q) =^{def} R_{3142,2341}(q).

3 The R-polynomials

In this section we describe a combinatorial rule for the computation of the Rpolynomials of S_{n}. Other combinatorial rules for the computation of the R-polynomials appear in [13] and [9]. We have chosen this particular one because it requires a minimal amount of background. Before stating the rule rigorously and in full generality we prefer to illustrate it on an example, as we believe that this will make the general definition more easily understandable (and maybe even superfluous).

Let u = 2147563, and v = 6157243. We compute a polynomial R̃_{u,v}(q) as follows. We first check (e.g., using Theorem 2.1) that u < v (if u ≰ v then R̃_{u,v}(q) =^{def} 0, if u = v then R̃_{u,v}(q) =^{def} 1, and we are done). If u < v then we locate the largest integer that does not occupy the same position in both u and v. In this case this is 6 since 7 does occupy the same position (namely, the fourth) in both u and v. We now look at the positions that this integer (in our case, 6) occupies in u and v. In our case these are the sixth and first positions (it can be proved from Theorem 2.1 (see, [4], Proposition 3.4) that the position in u is always to the right of the one in v because u < v). Next we find all the increasing subsequences in u that start at the first position and end at the sixth position. In our case there are four such subsequences, namely, 26, 246, 256, and 2456. We now “rotate” one step “to the right” each one of these subsequences in u to obtain 4 new permutations u^{(1)}, u^{(2)}, u^{(3)}, u^{(4)}. In our case we have u^{(1)} = \underline{6}1475\underline{2}3, u^{(2)} = \underline{6}1\underline{2}75\underline{4}3, u^{(3)} = \underline{6}147\underline{2}\underline{5}3, and u^{(4)} = \underline{6}1\underline{2}7\underline{4}\underline{5}3 (where we have underlined, for emphasis, the elements that we have “rotated” in each case). Then the polynomial R̃_{u,v}(q) is given by

R̃_{u,v}(q) = qR̃_{u^{(1)},v}(q) + q^{2}R̃_{u^{(2)},v}(q) + q^{2}R̃_{u^{(3)},v}(q) + q^{3}R̃_{u^{(4)},v}(q) ,  (4)

(where the exponent of the power of q that multiplies R̃_{u^{(i)},v}(q) is the number of elements that have been “rotated” to obtain u^{(i)}, minus one). It is not hard to see that this algorithm will eventually stop.

We now describe the algorithm rigorously. Given u, v ∈ S_{n} and i, j ∈ [n] we let

d(u, v) =^{def} max{i ∈ [n] : u^{−1}(i) ≠ v^{−1}(i)},  (5)

C_{i,j}(u) =^{def} {(u(i_{1}), …, u(i_{k})) : k ∈ [n], i = i_{1} < … < i_{k} = j and u(i_{1}) < … < u(i_{k})},

(6)

and k(u) be the length of the largest cycle of u. Then our algorithm can be stated as follows.

Definition 3.1 Let u, v ∈ S_{n}. Then

R̃_{u,v}(q) =^{def} \{ \begin{matrix}0, & if u ≰ v, \\ ∑_{w∈C_{v^{−1}(d),u^{−1}(d)}(u)}q^{k(w)−1}R̃_{wu,v}(q), & if u < v, \\ 1, & if u = v, \end{matrix}  (7)

where d =^{def} d(u, v).

We say that p(q) ∈ Z[q] is an R̃-polynomial if there are n ∈ P and u, v ∈ S_{n} such that p(q) = R̃_{u,v}(q).

Once the polynomial R̃_{u,v}(q) has been computed it is a simple matter to compute the polynomial R_{u,v}(q), thanks to the following result.

Theorem 3.2 Let u, v ∈ S_{n}, then

R_{u,v}(q) = q^{\frac{l(v)−l(u)}{2}} R̃_{u,v}(q^{\frac{1}{2}} − q^{− \frac{1}{2}} ) .

The preceding theorem is proved in [4], Corollary 3.8. Because of this result we will usually translate freely between the R-polynomials and the R̃-polynomials without further comment.

To illustrate the algorithm again we finish the computation of R̃_{2147563,6157243}(q) that we have started at the beginning of this section. We compute first R̃_{u^{(1)},v}(q). Since u^{(1)} ≰ v we have

R̃_{u^{(1)},v}(q) = 0 .  (8)

To compute R̃_{u^{(2)},v}(q) note that, using the notations (5) and (6), we have d = 5, (u^{(2)})^{−1}(d) = 5, v^{−1}(d) = 3, and C_{3,5}(6127543) = {(2, 5)}. Hence

R̃_{u^{(2)},v}(q) = qR̃_{6157243,6157243}(q).  (9)

For R̃_{u^{(3)},v}(q) we have d = 5, (u^{(3)})^{−1}(d) = 6, v^{−1}(d) = 3, and C_{3,6}(6147253) = {(4, 5)}. Hence

R̃_{u^{(3)},v}(q) = qR̃_{6157243,6157243}(q).  (10)

Finally, for R̃_{u^{(4)},v}(q) we have that d = 5, (u^{(4)})^{−1}(d) = 6, v^{−1}(d) = 3, and C_{3,6}(6127453) = {(2, 5), (2, 4, 5)}. Hence

R̃_{u^{(4)},v}(q) = qR̃_{6157423,6157243}(q) + q^{2}R̃_{6157243,6157243}(q).  (11)

Putting (4), (8), (9), (10), and (11) together we therefore obtain that

R̃_{u,v}(q) = (2q^{3} + q^{5})R̃_{6157243,6157243}(q) + q^{4}R̃_{6157423,6157243}(q).  (12)

But 6157423 ≰ 6157243, hence from (12) and Definition 3.1 we obtain our final result,

R̃_{2147563,6157243}(q) = q^{5} + 2q^{3}.  (13)

As an exercise the reader may want to compute R̃_{5213674,6725134}(q) (the result is q^{7} + 2q^{5}).

The algorithm illustrated in this section can be easily implemented on a computer, and a Maple version of it is available from the author upon request.

4 Combinatorial properties of the R-polynomials

In this section we survey some of the main combinatorial properties that are known for the R-polynomials of the symmetric groups.

We begin with the following fundamental property of the R̃-polynomials.

Theorem 4.1 Let u, v ∈ S_{n}, and i ∈ [n − 1] be such that v(i) > v(i + 1). Then

R̃_{u,v}(q) = \{ \begin{matrix}R̃_{u(i,i+1),v(i,i+1)}(q), & if u(i) > u(i + 1), \\ R̃_{u(i,i+1),v(i,i+1)}(q) + qR̃_{u,v(i,i+1)}(q), & if u(i) < u(i + 1). \end{matrix}  (14)

The above result follows easily from (and, in fact, is equivalent to) Theorem 3.2 using well known properties of the Hecke algebra (see, e.g., [17], §7.5). It can also be proved combinatorially from Definition 3.1 (see, [4], Theorem 3.7). Note that, since inv(v(i, i+1)) = inv(v)−1 (as v(i) > v(i+1)) one can use (14) as an inductive procedure to compute R̃_{u,v}(q). However, the reader can easily convince herself of the advantages of (7) over (14) by computing (13) using Theorem 4.1. Note that Theorem 4.1 shows that it is enough to compute the R̃-polynomials R̃_{u,v}(q) for pairs u, v such that D(u) ∩ D(v) = ∅.

From (14) it is easy to deduce the fundamental facts that R̃_{u,v}(q) is a monic polynomial of degree inv(v)− inv(u) and that

[q^{k}](R̃_{u,v}(q)) = 0

unless k ≡ inv(v)− inv(u) (mod 2). Thus there exist (necessarily unique) polynomials Q_{u,v}(q) ∈ N[q] such that

R̃_{u,v}(q) = \{ \begin{matrix}Q_{u,v}(q^{2}), & if inv(v)− inv(u) ≡ 0 (mod 2), \\ qQ_{u,v}(q^{2}), & otherwise. \end{matrix}  (15)

On these latter polynomials the following can be proved from (14) (see, [5], Proposition 6.1, or [9], Proposition 5.3).

Proposition 4.2 Let u, v ∈ S_{n}. Then Q_{u,v}(q) has no internal zeros.

There are four more general facts on the R̃-polynomials which we wish to mention.

Theorem 4.3 Let u, v ∈ S_{n}. Then the following are equivalent:

i) R̃_{u,v}(q) = q^{inv(v)−inv(u)};

ii) [u, v] does not contain any interval isomorphic to S_{3}.

The implication ii) ⇒ i) of the above result was first proved in [4], Theorem 4.8, while the converse was proved by Haiman and Kalai [15]. Theorem 4.3 was later generalized in [5], Theorem 6.3.

Theorem 4.4 Let u, v, σ, τ ∈ S_{n} be such that u ≤ σ ≤ τ ≤ v. Then

R̃_{u,v}(q) − q^{inv(v)−inv(τ)+inv(σ)−inv(u)}R̃_{σ,τ}(q) ∈ N[q].  (16)

The above result appears in [7], Corollary 5.5.

Proposition 4.5 Let u, v ∈ S_{n}. Then

R̃_{u,v}(q) = R̃_{u^{−1},v^{−1}}(q) = R̃_{n+1−v(1)...n+1−v(n),n+1−u(1)...n+1−u(n)}(q)
= R̃_{v(n)...v(1),u(n)...u(1)}(q).  (17)

The above result can be proved easily using properties of the Hecke algebra (see [17], Proposition 7.6) and also from (14).

The following fact is easy to prove algebraically (see, [17], Proposition 7.8(c)), and a combinatorial proof of it would undoubtedly be very interesting.

Proposition 4.6 Let σ, τ ∈ S_{n}, σ < τ. Then

∑_{a∈[σ,τ]}(−1)^{inv(a)}R̃_{σ,a}(q) R̃_{a,τ}(q) = 0.  (18)

Aside from establishing general properties of them, one is of course interested in the explicit computation of the R̃-polynomials. Simple examples show that R̃- polynomials do not, in general, factor, so a general closed formula for them does not exist. For example R̃_{12345,54321}(q) = q^{2}(1+5q^{2}+10q^{4}+6q^{6}+q^{8}), and R̃_{123456,654321}(q) = q^{3}(1+9q^{2} +39q^{4} +57q^{6} +36q^{8} +10q^{10} +q^{12}), and these factors are irreducible over Q. Nonetheless, there are several general classes of permutations in S_{n} for which explicit simple formulas exist. We now survey the main results known in this direction.

Theorem 4.7 Let σ ∈ S_{n} and w ∈ C_{i,j}(σ) for some i, j ∈ [n]. Then

R̃_{σ,wσ}(q) = q^{k(w)−1}(q^{2} + 1)^{\frac{1}{2} (d−k(w)+1)} ,

where d =^{def} inv(wσ)−inv(σ).

The proof of the above result (which is based on (7) and (14)) can be found in [4], Theorem 4.6. So Theorem 4.7 allows us to conclude “by inspection” that, for example,

R̃_{e,n 2...n−1 1}(q) = q(q^{2} + 1)^{n−2}.  (19)

One other result of a similar nature that can be proved using Definition 3.1 and Theorem 4.1 is the following.

Theorem 4.8 Let u, v ∈ S_{n}, u ≤ v, be such that D(u), D(v) ⊇ [2, n − 2]. Then

R̃_{u,v}(q) = \{ \begin{matrix}q^{a}(q^{2} + 1)^{\frac{1}{2} (d−a)}, & if [n + 1 − u(n), v(1)] ∩ [v(n), n + 1 − u(1)] ≠ ∅ \\ & and v(n) + u(1) < n + 1 < v(1) + u(n), \\ q^{d}, & otherwise, \end{matrix}

where a =^{def} |u(1) + v(1) − n − 1| + |u(n) + v(n) − n − 1| − 1, and d =^{def} inv(v)− inv(u).

The above result appears in [24], Theorem 3.

5 The Kazhdan-Lusztig polynomials

In this section we describe and illustrate a combinatorial rule for the computation of the Kazhdan-Lusztig polynomials of S_{n}. Another combinatorial rule for the computation of these Kazhdan-Lusztig polynomials appears in [10]. As in section 3, we have chosen to present the one that requires the minimum amount of background.

Let L be the real vector space of all Laurent polynomials in q with real coefficients. For j ∈ Q define an operator U_{j} : L → L by letting

U_{j}(∑_{i∈Z} a_{i}q^{i}) =^{def} ∑_{i≥j} a_{i}q^{i}.

Note that U_{j} is linear and idempotent and that U_{j} = U_{⌈j⌉}, for all j ∈ Q. Given β_{1}, …, β_{s} ∈ P we define a polynomial γ_{β_{1},...,β_{s}}(q) inductively as follows,

γ_{β_{1},...,β_{s}}(q) =^{def} (q − 1)γ_{β_{1}−1,β_{2},...,β_{s}}(q) + U_{\frac{n+1}{2}} (q^{n−1}(1 − q)γ_{β_{1}−1,β_{2},...,β_{s}} (\frac{1}{q}))

if β_{1} ≥ 2 (where n =^{def} β_{1} + … + β_{s}),

γ_{β_{1},...,β_{s}}(q) =^{def} (q − 1)U\frac{n}{2} (q^{n−1}γ_{β_{2},...,β_{s}} (\frac{1}{q}))

if β_{1} = 1 and s ≥ 2,

γ_{1}(q) =^{def} −1.

So, for example,

γ_{1,1}(q) = (q − 1)U_{1} (qγ_{1} (\frac{1}{q})) = (q − 1)U_{1}(−q) = −q^{2} + q

and hence

γ_{2,1}(q) = −q^{3} + 2q^{2} − q + U_{2} (q^{2}(1 − q) (−\frac{1}{q^{2}} + \frac{1}{q}))
= −q^{3} + 2q^{2} − q + U_{2}(−q^{2} + 2q − 1)
= −q^{3} + q^{2} − q.

The polynomials γ_{β_{1},...,β_{s}}(q) are the basic ingredients for the computation of the Kazhdan-Lusztig polynomials. As done in section 3, we prefer to illustrate the algorithm on a specific example before stating it rigorously in general.

Let u = 2147563, v = 6157243. We check first that u < v (otherwise the algorithm stops, and P_{u,v}(q) = 0 if u ≰ v, P_{u,v}(q) = 1 if u = v). We then construct a labeled directed graph B(u, v) by taking {σ ∈ S_{n} : u ≤ σ ≤ v} as vertex set and putting a directed edge from σ to τ labeled λ(σ, τ) =^{def} ∑_{k=1}^{i−1}(n − k) + (j − i) if and only if τ = σ(i, j) for some 1 ≤ i < j ≤ n such that u(i) < u(j). In our case we obtain the labeled directed graph depicted in Figure 2. Now, to each directed path (a_{0}, a_{1}, …, a_{k}) in B(u, v) from u to v we associate a sequence of positive integers (β_{1}, …, β_{s}) by “cutting” the path at vertex a_{i} if and only if λ(a_{i−1}, a_{i}) > λ(a_{i}, a_{i+1}) and counting the lengths of the “pieces” thus obtained, along the direction of the path. For example, for the path (2147563, 2147653, 6147253, 6157243) we obtain the pieces (2147563, 2147653) and (2147653, 6147253, 6157243) and hence β_{1} = 1, β_{2} = 2. Doing this for all the directed paths from 2147563 to 6157243 in Figure 2 (there are 62 such paths) we obtain the following multiset of compositions M = {(3)^{2}, (2, 1)^{3}, (1, 2)^{3}, (1, 1, 1)^{2}, (5)^{1}, (4, 1)^{2}, (3, 2)^{4}, (2, 3)^{4}, (1, 4)^{2}, (3, 1, 1)^{3}, (1, 3, 1)^{4}, (1, 1, 3)^{3}, (2, 2, 1)^{6}, (2, 1, 2)^{4}, (1, 2, 2)^{6}, (2, 1, 1, 1)^{2}, (1, 2, 1, 1)^{4}, (1, 1, 2, 1)^{4}, (1, 1, 1, 2)^{2}, (1, 1, 1, 1, 1)^{1}}. (where we use multiset notation as in [25], p. 15). Then the polynomial P_{u,v}(q) is given by

P_{u,v}(q) = − ∑_{β∈M} q^{\frac{1}{2} (inv(v)−inv(u)−|β|)}γ_{β}(q) .

In our case one obtains that P_{2147563,6157243}(q) = −q(2γ_{3} + 3γ_{2,1} + 3γ_{1,2} + 2γ_{1,1,1}) − q^{0}(γ_{5} + 2γ_{4,1} + 4γ_{3,2} + 4γ_{2,3} + 2γ_{1,4} + 3γ_{3,1,1} + 4γ_{1,3,1} +3γ_{1,1,3} + 6γ_{2,2,1} + 4γ_{2,1,2} + 6γ_{1,2,2} + 2γ_{2,1,1,1} +4γ_{1,2,1,1} + 4γ_{1,1,2,1} + 2γ_{1,1,1,2}) = −q(2(2q − 1) + 3(−q^{3} + q^{2} − q) + 3(q^{3} − q^{2}) + 2(0)) −q^{0}[(−5q^{2} + 4q − 1) +2(−q^{5} + 3q^{4} − 2q^{3} + 3q^{2} − q) + 4(q^{5} − 3q^{4}+ 2q^{3} − q^{2}) + 4(−q^{5} + 4q^{4} − 3q^{3} + 2q^{2}) + 2(q^{5} − 4q^{4} + 3q^{3}) + 3(0) +4(q^{4} − q^{3}) + 3(0) + 6(−q^{4} + q^{3} − q^{2}) + 4(0) + 6(0) + 2(0) + 4(0) + 4(0) + 2(0)] = 1.

In general, given u, v ∈ S_{n} we construct B(u, v) exactly as above. Then for any directed path Γ = (a_{0}, …, a_{k}) in B(u, v) we let

D(Γ) =^{def} (β_{1}, …, β_{s})

where s, β_{1}, …, β_{s} ∈ P are such that β_{1} + … + β_{s} = k and λ(a_{i−1}, a_{i}) > λ(a_{i}, a_{i+1}) if and only if i = β_{1} + … + β_{j} for some 1 ≤ j ≤ s − 1. Then the above algorithm is expressed by the following result.

. 12 Theorem 5.1 Let u, v ∈ S_{n}, u < v. Then

P_{u,v}(q) = (−1)^{inv(v)−inv(u)} ∑_{Γ} q^{\frac{1}{2} (inv(v)−inv(u)−l(Γ))}γ_{D(Γ)}(q) ,

where Γ runs over all directed paths in B(u, v) from u to v.

The proof of the preceding theorem is rather involved and appears in [7], Corollary 4.6 (where B(u, v) is used with a slightly different meaning than here).

It is worth noting that once the directed graph B(u, v) is constructed then one obtains also P_{σ,τ}(q), for any σ, τ ∈ [u, v], at almost no extra “cost”. We invite the reader to compute, using Figure 2 and the previous example as a “table” of the polynomials γ_{β_{1},...,β_{s}} for β_{1} + … + β_{s} ≤ 5, P_{4127563,6157243}(q) (the answer is 1). The reader may also want to check her understanding of the algorithm described in this section by computing P_{14325,45312}(q) (there are 136 paths in this case and the answer is 1 + q^{2}).

The algorithm illustrated in this section can be easily implemented on a computer, and a Maple version of it is available from the author upon request.

6 Combinatorial properties of the Kazhdan-Lusztig

polynomials

In this section we survey some of the main combinatorial properties that are known for the Kazhdan-Lusztig polynomials of the symmetric groups. Because of their importance in the representation theory of Hecke algebras, and in the algebraic geometry and topology of Schubert varieties, Kazhdan-Lusztig polynomials have been widely studied (see, e.g., [11]) and many properties of them are known. However, almost all these properties are proved either geometrically or algebraically. For most of them we believe that a combinatorial proof using Theorem 5.1 would be very interesting and illuminating.

We begin with the following fact which is usually taken as part of the definition of Kazhdan-Lusztig polynomials (see, e.g., [17], Theorem 7.9, or [18], §2.2) but which is quite mysterious from the point of view of Theorem 5.1.

Proposition 6.1 Let u, v ∈ S_{n}, u < v. Then deg(P_{u,v}(q)) ≤ \frac{1}{2}(inv(v)−inv(u) − 1).

We mentioned in section 1 that the Kazhdan-Lusztig and R-polynomials are very closely related. The next result makes this precise.

Theorem 6.2 Let u, v ∈ S_{n}, u ≤ v. Then

q^{inv(v)−inv(u)}P_{u,v} (\frac{1}{q}) = ∑_{u≤a≤v} R_{u,a}(q)P_{a,v}(q) .  (20)

The preceding theorem can be either taken as part of a possible definition of the Kazhdan-Lusztig polynomials (see, e.g., [18], §2.2, or [27], Corollary 6.7, and Example 6.9), or proved algebraically (see, e.g., [17], §7.10, eq.(21)). Note that the last two results can be used to compute P_{u,v}(q) inductively (by induction on inv(v)−inv(u)), using the facts that P_{u,v}(q) = 0 if u ≰ v, and P_{u,v}(q) = 1 if u = v, as initial conditions. The reader can easily convince herself that this method is usually not as efficient as that described in the previous section by computing P_{2147563,6157243}(q) in this second way.

There is one other recurrence relation for Kazhdan-Lusztig polynomials which is sometimes useful. For u, v ∈ S_{n} let

μ(u, v) =^{def} \{ \begin{matrix}[q^{\frac{1}{2} (inv(v)−inv(u)−1)}](P_{u,v}(q)), & if u < v, \\ 0, & otherwise. \end{matrix}

Theorem 6.3 Let u, v ∈ S_{n}, u ≤ v, and i ∈ [n − 1] be such that v(i) > v(i + 1). Then

P_{u,v}(q) = q^{1−c}P_{u(i,i+1),v(i,i+1)}(q)+q^{c}P_{u,v(i,i+1)}(q)− ∑_{\{z: z(i)>z(i+1)\}} μ(z, v(i, i+1))q^{\frac{1}{2} (l(v)−l(z))}P_{u,z}(q)

where c =^{def} 1 if u(i) > u(i + 1), and c =^{def} 0 otherwise.

A proof of the preceding result can be found, e.g., in [17], §7.11, eq. (23).

An important immediate consequence of Theorem 6.3 is the following.

Corollary 6.4 Let u, v ∈ S_{n}, u ≤ v, and i ∈ [n − 1] be such that v(i) > v(i + 1). Then

P_{u,v}(q) = P_{u(i,i+1),v}(q).

So, for example, P_{2147563,6157243}(q) = P_{1245736,6157243}(q), and

P_{u,n n−1...3 2 1}(q) = 1,  (21)

for all u ∈ S_{n}. Thus Corollary 6.4 shows that it is enough to compute Kazhdan-Lusztig polynomials P_{u,v}(q) for pairs u, v ∈ S_{n} such that D(v) ⊆ D(u) (say).

The following partial analogue of Proposition 4.5 holds for Kazhdan-Lusztig polynomials.

Proposition 6.5 Let u, v ∈ S_{n}. Then

P_{u,v}(q) = P_{u^{−1},v^{−1}}(q) = P_{n+1−u(n)...n+1−u(1),n+1−v(n)...n+1−v(1)}(q).  (22)

Proofs of the equalities in (22) appear in [5], Corollaries 4.3 and 4.4. Note that the other equalities in Proposition 4.5 fail for Kazhdan-Lusztig polynomials. For example, P_{1234,4231}(q) = 1 + q but P_{1324,4321}(q) = 1.

Recently, the following extraordinary analogue of Theorem 4.4 for Kazhdan-Lusztig polynomials has been proved by Braden and MacPherson ([3]).

Theorem 6.6 Let u, v, w ∈ S_{n} be such that u ≤ v ≤ w. Then

P_{u,w}(q) − P_{v,w}(q) ∈ N[q].

As an immediate consequence one obtains the following highly non-trivial result.

Corollary 6.7 Let u, v ∈ S_{n}. Then P_{u,v}(q) ∈ N[q].

The preceding result had been conjectured by Kazhdan and Lusztig in [18], p. 166, and first proved by them in [19].

There are two further general results on Kazhdan-Lusztig and R-polynomials which we wish to mention. Given u, v ∈ S_{n} let

G_{[u,v]}(q) =^{def} ∑_{u≤σ≤v} q^{inv(σ)−inv(u)}

(i.e., the rank generating function of [u, v], as a graded poset).

Proposition 6.8 Let u, v ∈ S_{n}, u ≤ v. Then the following are equivalent:

i) P_{σ,τ}(q) = 1 for all σ, τ ∈ [u, v];

ii) R_{σ,τ}(q) = (−1)^{inv(τ)−inv(σ)}G_{[σ,τ]}(−q) for all σ, τ ∈ [u, v].

Theorem 6.9 Let u, v ∈ S_{n}, u ≤ v. Then the following are equivalent:

i) [u, v] does not contain any interval isomorphic to S_{3};

ii) P_{u,v}(q) = g([u, v]^{∗}; q).

The preceding results are proved in [5], see Proposition 5.6, and Theorem 6.3.

As for the R-polynomials, aside from establishing general properties of the Kazhdan-Lusztig polynomials there is also interest in their explicit computation for particular classes of permutations. We now survey what is known in this direction.

As observed after Corollary 6.4, it is enough to compute Kazhdan-Lusztig polynomials P_{u,v}(q) for pairs u, v ∈ S_{n} such that D(v) ⊆ D(u). This suggests that the “easier” Kazhdan-Lusztig polynomials to compute should be those where D(v) is “large”. This is indeed confirmed not only by (21), but also by most of the results that are actually known.

Let u ∈ S_{n} be such that |D(u)| = n − 1 (such a permutation is sometimes called a Grassmannian permutation). Then u(1) > … > u(i) < u(i + 1) for a unique i ∈ [n−1]. We associate to u a word ũ in the alphabet {(,)} by letting the j-th letter of ũ be an open parenthesis if and only if j = u(a) for some a ∈ [i]. For example, if u = 83276541 then i = 3 and ũ =)(())))(. We now associate to each word in {(,)} a tree by “matching the parentheses”. An example should illustrate the process more clearly than a description in words. Consider the word )((()((())(())))()) then we obtain the following “matching” of its parenteses

) \underbrace{(\underbrace{(\underbrace{()} \underbrace{(\underbrace{(\underbrace{()})} \underbrace{(\underbrace{()})})})} \underbrace{()})}  (23)

and this can clearly be encoded by the tree in Figure 3 (where each vertex, except the root, corresponds to a matching pair \underbrace{(…)} and a vertex is a descendant of another if and only if its pair is enclosed by the other pair).

[figure]

Figure 3: the tree associated to (23).

Note that the leaves of this tree are in bijection with the factors () of the word. Given a word in {(,)} we may also associate to it a path in Z × Z by interpreting each “)” as a (1, 1)-step and each “(” as a (1, −1)-step in Z × Z. For example, the path associated to (23) is depicted in Figure 4.

[figure]

Figure 4: the path associated to (23).

Now let u, v ∈ S_{n}, u ≤ v, be two Grassmannian permutations such that D(u) = D(v) and D(v^{−1}) ⊆ D(u^{−1}). It is then easy to see that u ≤ v if and only if the path associated to u lies entirely below the one associated to v. We now associate to each leaf of the tree associated to v the vertical distance (divided by 2, since it is always even) from the corresponding valley (recall that leafs correspond to factors () in the word and hence to valleys in the path) , in the path associated to v, to the path associated to u. We denote by T (u/v) the tree associated to v together with this labeling of its leaves, and by E(u/v) its edge set. A function f : E(u/v) → N is then called admissible for T (u/v) if:

i) f weakly increases along any path from the root;

ii) the value of f at the final edge of each path from the root does not exceed the label of the corresponding leaf.

We let |f| =^{def} ∑_{x∈E(u/v)} f(x). We then have the following result, whose proof appears in [21] (see also [28]).

Theorem 6.10 Let u, v ∈ S_{n} be such that |D(u)| = |D(v)| = n − 1, D(u) = D(v), D(v^{−1}) ⊆ D(u^{−1}), and u ≤ v. Then

P_{u,v}(q) = ∑_{f} q^{|f|}

where the sum is over all functions f : E(u/v) → N that are admissible for T (u/v).

We illustrate the preceding theorem with an example. Suppose u = 5437621, and v = 7536421. Then the associated words are ũ =))((()) and ṽ =))()()(. The tree associated to ṽ is therefore the one in Figure 5, the paths

Figure 5: The tree associated to ))()()(.

associated to ũ and ṽ are those in Figure 6 and hence the labels of the two leaves of the tree in Figure 5 are 0 and 1.

[figure]

Figure 6: The paths associated to ))((()) and ))()()(.

Thus there are only two functions f : E(u/v) → N admissible for T (u/v), illustrated in Figure 7, and hence

P_{5437621,7536421}(q) = 1 + q.  (24)

[figure: 0; 0; 0; 1]

Figure 7: The two T (u/v)-admissible maps from E(u/v) to N.

Note that the above theorem does indeed cover all the Kazhdan-Lusztig polynomials of two Grassmannian permutations. In fact, let v, σ ∈ S_{n} be such that σ ≤ v and |D(σ)| = |D(v)| = n − 1. Then by Corollary 6.4 there exists a unique τ ∈ S_{n} such that σ ≤ τ ≤ v, D(τ) = D(v), and

P_{σ,v}(q) = P_{τ,v}(q).  (25)

Similarly, by Corollary 6.4 there exists a unique u ∈ S_{n} such that τ^{−1} ≤ u^{−1} ≤ v^{−1}, D(v^{−1}) ⊆ D(u^{−1}), and

P_{τ^{−1},v^{−1}}(q) = P_{u^{−1},v^{−1}}(q)  (26)

(note that then necessarily D(u) = D(τ)). Hence, by (25), (26), and Proposition 6.5,

P_{σ,v}(q) = P_{u,v}(q)

and u, v ∈ S_{n} now satisfy all the hypotheses of Theorem 6.10. For example, if v = 7536421 and σ = 5421763, then τ = 5427631, hence τ^{−1} = 7362154 and since v^{−1} = 7635241 we conclude that u^{−1} = 7632154 and therefore that u = 5437621. Thus P_{5421763,7536421}(q) = P_{5427631,7536421}(q) = P_{7362154,7635241}(q) = P_{7632154,7635241}(q) = P_{5437621,7536421}(q) = 1 + q, by (24).

Theorem 6.11 Let u, v ∈ S_{n}, u ≤ v, be such that [2, n − 2] ⊆ D(v). Then

P_{u,v}(q) = \{ \begin{matrix}1, & if v(1) < v(n), or v(n) ≤ u(1), or v(1) ≥ u(n), \\ 1 + q^{v(1)−v(n)}, & otherwise. \end{matrix}

Theorem 6.12 Let u, v ∈ S_{n}, u ≤ v, be such that D(v) ⊆ {1, n − 1}. Then

P_{u,v}(q) = (1 + q)^{r}

where r =^{def} |\{z ∈ [v(n) + 1, v(1) − 2] : ∑_{i=1}^{z} u(i) = (\begin{matrix}z+1 \\ 2 \end{matrix})\}|.

The last two results appear in [24], Theorems 1 and 2. Theorem 6.12 implies, as a special case, a conjecture of M. Haiman ([16]).

Let τ ∈ S_{m} and σ ∈ S_{n} (n ≥ m). Recall that σ is said to be τ-avoiding if there are no 1 ≤ i_{1} < i_{2} < … < i_{m} ≤ n such that

σ(i_{τ(1)}) < σ(i_{τ(2)}) < … < σ(i_{τ(m)}).

Theorem 6.13 Let v ∈ S_{n}. Then the following are equivalent:

i) P_{e,v}(q) = 1;

ii) P_{u,v}(q) = 1 for all u ≤ v;

iii) v is 3412-avoiding and 4231-avoiding.

The equivalence of iii) and ii) is proved in [20], while the equivalence of i) and ii) is an immediate consequence of Theorem 6.6.

We conclude this section with two explicit formulas for Kazhdan-Lusztig polynomials that are obtained from Theorem 6.9 (see [5], Corollaries 6.8 and 6.9). We denote by B_{d} and Q_{d} the lattice of faces of a d-simplex (i.e., a Boolean algebra of rank d) and of a d-dimensional cube, respectively.

Corollary 6.14 Let u, v ∈ S_{n} be such that [u, v] ≅ B_{d} (as posets). Then P_{u,v}(q) = 1.

Corollary 6.15 Let u, v ∈ S_{n} be such that [u, v] ≅ Q_{d}^{∗} (as posets) where d =^{def} l(v) − l(u) − 1. Then

P_{u,v}(q) = ∑_{i=0}^{⌊ \frac{d}{2} ⌋} \frac{1}{d − i + 1} (\begin{matrix}d \\ i \end{matrix}) (\begin{matrix}2(d−i) \\ d \end{matrix}) (q − 1)^{i} .  (27)

Equivalently, [q^{i}](P_{u,v}(q)) is the number of plane trees with d + 1 vertices such that exactly i vertices have ≥ 2 sons, for all i ∈ N. In particular, deg(P_{u,v}(q)) = ⌊\frac{d}{2}⌋.

7 Conjectures and Open Problems

In this section we discuss several conjectures and open problems on the Kazhdan-Lusztig and R-polynomials of the symmetric groups, together with the evidence existing in their favor.

We begin by discussing the R-polynomials. The fundamental problem here (as with any other family of polynomials) is that of characterizing them. Proposition 4.2 gives a necessary condition for a polynomial to be an R̃-polynomial. Other necessary conditions can be derived from Definition 3.1. For example, it is not hard to show, using Definition3.1, and Theorem 4.1, that

[q](R̃_{σ,τ}) ≤ 1 ,

and

[q^{2}](R̃_{σ,τ}) ≤ 2 ,

for all σ, τ ∈ S_{n}. These properties, however, are far from being also sufficient, as simple examples show. In this respect, we feel that the following necessary condition holds.

Conjecture 7.1 Let u, v ∈ S_{n}. Then Q_{u,v}(q) is log-concave.

We have verified Conjecture 7.1 for n ≤ 6.

If one computes a few R-polynomials one is led to conjecture that (−1)^{inv(v)−inv(u)} R_{u,v}(−q) ∈ N[q], (in fact, a stronger conjecture had been made by Gabber and Joseph, see [2]). This, however, is false, as noted in [2]. For example, R_{124356,564312}(q) = 1−5q +11q^{2} −13q^{3} +8q^{4} −q^{5} −2q^{6} −q^{7} +8q^{8} −13q^{9} +11q^{10} −5q^{11} +q^{12}. Nonetheless, we feel that the following holds.

Conjecture 7.2 Let u, v ∈ S_{n}. Then

∑_{σ,τ∈[u,v]} R_{σ,τ}(q) ∈ N[q].  (28)

We have verified that Conjecture 7.2 holds for n ≤ 5.

Note that the coefficients of q^{inv(v)−inv(u)} and of q^{0} in ∑_{σ,τ∈[u,v]} R_{σ,τ}(q) are always nonnegative since R_{σ,τ}(q) is a monic polynomial of degree inv(τ)− inv(σ) and

∑_{σ,τ∈[u,v]} R_{σ,τ}(0) = ∑_{σ∈[u,v]} ∑_{τ∈[σ,v]}(−1)^{inv(τ)−inv(σ)}
= ∑_{σ∈[u,v]} δ_{σ,v}
= 1,

where we have used the fact that [u, v] is an Eulerian poset. Also, it can be proved ([8]) that the coefficient of q in ∑_{σ,τ∈[u,v]} R_{σ,τ}(q) is always nonnegative. Also note that, as it is easy to verify,

∑_{σ,τ∈[u,v]} R_{σ,τ}(1) = |[u, v]|

which suggests that, if Conjecture 7.2 holds, then (28) should enumerate the elements of [u, v] according to some statistics.

As partial evidence in favor of Conjecture 7.2 we mention the following results.

Proposition 7.3 Let u, v ∈ S_{n} be such that P_{u,v}(q) = 1. Then

∑_{σ,τ∈[u,v]} R_{σ,τ}(q) = G_{[u,v]^{∗}}(q).

Proof. From Theorem 6.6 and our hypothesis we conclude that P_{τ,v}(q) = 1 for all τ ∈ [u, v]. Hence from Theorem 6.2 we have that

∑_{σ,τ∈[u,v]} R_{σ,τ}(q) = ∑_{σ∈[u,v]} ∑_{τ∈[σ,v]} R_{σ,τ}(q)P_{τ,v}(q)
= ∑_{σ∈[u,v]} q^{inv(v)−inv(σ)}P_{σ,v} (\frac{1}{q})
= ∑_{σ∈[u,v]} q^{inv(v)−inv(σ)}.□

Thus Conjecture 7.2 holds, e.g., if v = n n − 1 … 3 2 1 (by (21)). If [u, v] does not contain any interval isomorphic to S_{3} then by Theorem 4.3 we have that

∑_{σ,τ∈[u,v]} R_{σ,τ}(q) = ∑_{σ∈[u,v]} ∑_{τ∈[σ,v]}(q − 1)^{inv(τ)−inv(σ)} = ∑_{u≤σ≤v} G_{[σ,v]}(q − 1).  (29)

This expression does not make it clear whether Conjecture 7.2 holds for these intervals [u, v] or not. However, it does imply Conjecture 7.2 in at least two cases.

Proposition 7.4 Let u, v ∈ S_{n} be such that [u, v] ≅ B_{d}. Then

∑_{σ,τ∈[u,v]} R_{σ,τ}(q) = (q + 1)^{d} .□

Proposition 7.5 Let u, v ∈ S_{n} be such that [u, v] ≅ Q_{d}^{∗}. Then

∑_{σ,τ∈[u,v]} R_{σ,τ}(q) = (2q + 1)^{d} + (q − 1)(q + 1)^{d} + 1.  (30)

Proof. Since [u, v] ≅ Q_{d}^{∗} there follows that [a, v]^{∗} ≅ Q_{l(v)−l(a)−1} for all a ∈ [u, v). Therefore

G_{[a,v]}(q − 1) = ∑_{x∈[a,v]}(q − 1)^{l(x)−l(a)}
= (q − 1)^{l(v)−l(a)} + ∑_{k=0}^{l(v)−l(a)−1} 2^{l(v)−l(a)−1−k} (\begin{matrix}l(v)−l(a)−1 \\ k \end{matrix}) (q − 1)^{l(v)−l(a)−1−k}
= (q − 1)^{l(v)−l(a)} + (2q − 1)^{l(v)−l(a)−1},

for all a ∈ [u, v), where we have used the well known (and easy to see) fact that a d-dimensional cube has 2^{d−k} (\begin{matrix}d \\ k \end{matrix}) faces of dimension k, for k = 0, …, d − 1. Hence we conclude from (29) that

∑_{σ,τ∈[u,v]} R_{σ,τ}(q) = ∑_{a∈[u,v]} G_{[a,v]}(q − 1)
= 1 + ∑_{a∈[u,v)}((q − 1)^{l(v)−l(a)} + (2q − 1)^{l(v)−l(a)−1})
= 1 + ∑_{k=0}^{d} 2^{d−k} (\begin{matrix}d \\ k \end{matrix}) [(q − 1)^{k+1} + (2q − 1)^{k}]
= 1 + (q − 1)(q − 1 + 2)^{d} + (2q − 1 + 2)^{d},

and (30) follows. □

Admittedly, Proposition 7.5 may be empty if d ≥ 4 (see Conjecture 7.14). However, all the results presented in support of Conjecture 7.2 actually hold for any Coxeter group, since they only use results which hold in general. Thus these results may be seen as evidence of the fact that Conjecture 7.2 may actually hold for any Coxeter group, and for this reason we have presented Proposition 7.5 also.

Probably the most remarkable conjecture on the R-polynomials is the following, which is a special case of a more general conjecture of Lusztig that he made in 1980 [22] and that has circulated informally since then (see also [12], and [17], §8.6).

Conjecture 7.6 Let u, v, σ, τ ∈ S_{n} be such that [u, v] ≅ [σ, τ] (as posets). Then R_{u,v}(q) = R_{σ,τ}(q).

For example, it is not hard to show, using (18) and Theorem 4.3, that, for u, v ∈ S_{n}, u ≤ v,

R̃_{u,v}(q) = q^{3} + B_{0}(u, v)q

if l(v) − l(u) = 3, and

R̃_{u,v}(q) = q^{4} + \frac{1}{2}(B_{0}(u, v) + B_{1}(u, v))q^{2}

if l(v) − l(u) = 4, where B_{i}(u, v) =^{def} |{(σ, τ) ∈ [u, v]^{2} : l(σ) − l(u) = i, [σ, τ] ≅ S_{3}}|

for i ∈ [0, l(v) − l(u) − 3]. Hence the conjecture holds if l(v) − l(u) ≤ 4 (it is open for l(v) − l(u) ≥ 5). Also, note that Conjecture 7.6 holds if [u, v] does not contain any interval isomorphic to S_{3}, by Theorem 4.3. Some more partial evidence in favor of Conjecture 7.6 is given in [6], Corollary 3.11. We should also mention that equivalent conjectures are obtained by substituting “R” with “P ” or with “Q” in Conjecture 7.6, as can be seen from (20), and (15). Finally, it is interesting to note, both in respect to the characterization problem as well as to Conjecture 7.6, that R̃-polynomials seem to be extremely “rigid”. For example, there are only 64 distinct polynomials Q_{u,v}(q) arising from the 518,400 pairs of elements of S_{6}. This (and Theorem 4.3) certainly gives evidence in favor of Conjecture 7.6.

We conclude this series of conjectures and problems on the R-polynomials by mentioning a conjectured closed formula for a large class of R-polynomials.

Conjecture 7.7 Let u, v ∈ S_{n} be such that u ≤ v ≤ (i, j) for some i, j ∈ [n], i ≠ j. Then

R̃_{u,v}(q) = q^{a}(q^{2} + 1)^{\frac{1}{2} (l(v)−l(u)−a)}

for some a ∈ N.

The above conjecture is based on numerical evidence and is known to be true if u = e ([8]).

We believe that many other classes of permutations exist for which the R̃- polynomials have either closed form or nice generating functions. We expect that finding them will depend mainly on computer explorations and on a better understanding of the algorithm given in section 3.

We now turn to the Kazhdan-Lusztig polynomials. In contrast with the situation for the R-polynomials, where most of the results presented in section 4 have a combinatorial proof based on the algorithm in section 3, almost all of the results in section 6 have only geometric or algebraic proofs. Thus a natural general problem is that of finding combinatorial proofs (i.e., based on the algorithm in section 5) for these results. In particular, we believe that Proposition 6.1 and Corollary 6.4 ought to have such proofs, and that these would yield considerable insight on the combinatorics of Kazhdan-Lusztig polynomials.

The algorithm described in section 5 depends on the polynomials γ_{β_{1},...,β_{s}}. Despite the fact that these polynomials have a rather simple definition, and can be easily computed, many of their properties are still not well understood. For example, it is proved in [7], Theorem 3.10, that (−1)^{β_{1}+β_{3}+...}γ_{β_{1},...,β_{s}}(−q) ∈ N[q], and this naturally leads to the following fundamental problem.

Problem 7.8 Find a combinatorial interpretation of (−1)^{β_{1}+β_{3}+...}γ_{β_{1},...,β_{s}}(−q), for any s, β_{1}, …, β_{s} ∈ P.

A combinatorial interpretation has been found for some alternating sums of the γ_{β_{1},...,β_{s}}(q)’s obtained by inclusion-exclusion (see [7], eq. (12) and Theorem 3.16), but Problem 7.8 remains open (cfr. the comments at the end of section 3 in [7]).

A similar, but certainly much more complicated, problem naturally suggested by Corollary 6.7 is the following.

Problem 7.9 Find a combinatorial interpretation of P_{u,v}(q) for any u, v ∈ S_{n}.

As shown by Theorems 6.10, 6.11, and 6.12, such a combinatorial interpretation is known only in very special cases. A more modest and preliminary goal is that of finding a combinatorial interpretation for P_{u,v}(1) (which is also a number of algebraic significance, see, e.g., [21], p. 249, and the references cited there). This, in turn, by Theorem 5.1, leads to the problem of finding a combinatorial interpretation for γ_{β_{1},...,β_{s}}(1). Even this problem is open at present. However, we feel that the following holds.

Conjecture 7.10 ^{2} Let n ∈ P. Then γ_{2n}(1) = γ_{2n+1}(1) = (−1)^{n+1}C_{n}, where C_{n} = \frac{1}{n+1} (\begin{matrix}2n \\ n \end{matrix}) is the n-th Catalan number.

For s ≥ 2 we have no explicit conjecture for γ_{β_{1},...,β_{s}}(1), however, numerical evidence suggests very strongly that the numbers γ_{β_{1},...,β_{s}}(1) always factor very nicely, so an explicit closed formula for them appears possible.

2This conjecture has recently been proved by D. Zeilberger, “Catalan strikes again, and again”, preprint, 1995.

The problem of characterizing Kazhdan-Lusztig polynomials appears extremely hard, though it may very well have an extremely simple answer. In fact, it is possible that any polynomial with nonnegative integer coefficients and constant term equal to 1 is a Kazhdan-Lusztig polynomial. However, based on numerical evidence, we believe that this is not true. In fact, we conjecture the following.

Conjecture 7.11 1 + 5q + 2q^{2} is not a Kazhdan-Lusztig polynomial (i.e., there are no n ∈ P and u, v ∈ S_{n} such that P_{u,v}(q) = 1 + 5q + 2q^{2}).

We have verified the above conjecture for n ≤ 8.

Just as for the R̃-polynomials, there is interest in upper bounds for the coefficients of the Kazhdan-Lusztig polynomials. We present here three conjectures, in order of decreasing strength.

Conjecture 7.12 Let n ∈ P and u, v ∈ S_{n} be such that deg (P_{u,v}) = \frac{1}{2}(l(v) − l(u) − 1). Then [q^{k}](P_{u,v}) ≤ A(\frac{1}{2}(l(v) − l(u) + 1); k) for all k ∈ N.

Here A(n, k) (n, k ∈ N) denotes an Eulerian number (i.e., A(n, k) =^{def} |{σ ∈ S_{n} : d(σ) = k}|, for 0 ≤ k ≤ n − 1 and n ∈ P). This conjecture was motivated by (at the time rather scarce) numerical evidence. It is proved in [6] Corollary 3.10, that, for each k ∈ N, there exists a constant c_{k} such that Conjecture 7.12 holds for all permutations u, v such that inv(v)− inv(u) > c_{k}. Conjecture 7.12 implies, for k = \frac{1}{2}(inv(v) − inv(u) − 1), the following one.

Conjecture 7.13 Let u, v ∈ S_{n}. Then [q^{\frac{1}{2} (inv(v)−inv(u)−1)}](P_{u,v}) ≤ 1.

This conjecture has circulated informally for several years and is known as the (0, 1)- conjecture (see, e.g., [14]). The conjecture holds for n ≤ 8. Notice that Corollary 6.15 shows that [q^{\frac{1}{2} (inv(v)−inv(u)−1)}](P_{u,v}) > 1 if [u, v] ≅ Q_{4}^{∗} and d ≥ 4. Accordingly, Conjecture 7.13 implies the following one.

Conjecture 7.14 There are no n ∈ P and u, v ∈ S_{n} such that [u, v] ≅ Q_{4}^{∗}.

This conjecture has been verified for n ≤ 8.

We conclude with some conjectured explicit formulas for the Kazhdan-Lusztig polynomials of some particular classes of permutations.

Conjecture 7.15 Let n ∈ P, n ≥ 4. Then

P_{1 n−1 n−2 2 3...n−3 n,n−1 n n−2 1 2 3...n−3}(q) = 1 + (n − 4)q^{2} .  (31)

Conjecture 7.16 Let n ∈ P, n ≥ 5. Then

P_{1 n−1 n−2 n−3 2 3 ...n−4n,n−1 n n−2 n−3 1 2...n−4}(q) = 1 + (n − 5)q^{3}.  (32)

Both conjectures have been verified for n ≤ 8. It would be interesting to find a conjecture that would include both (31) and (32) as special cases.

Conjecture 7.17 Let n ∈ P, n ≥ 6. Then

P_{e,n−1 n n−2 n−3...4 3 1 2}(q) = 1 + q^{n−3} .

For n ∈ P let

F_{n}(q) =^{def} F_{n−1}(q) + qF_{n−2}(q),

where F_{n}(q) =^{def} 0 if n < 0 and F_{0}(q) =^{def} 1.

Conjecture 7.18 Let n ∈ P, n ≥ 4. Then

P_{e,n−1 n 1 2...n−2}(q) = F_{n−2}(q) .

Conjectures 7.17 and 7.18 have been verified for n ≤ 8 and are due to Haiman ([16]). Acknowledgements. The author would like to thank M. Haiman, R. MacPherson, and D. Zeilberger for some useful conversations. Some of the examples in this paper have been computed with the help of a Maple package for handling posets developed by J. Stembridge.

References

[1] A. Björner, Orderings of Coxeter groups, Combinatorics and Algebra, Contemporary Math. vol. 34, Amer. Math. Soc. 1984, 175-195.

[2] B. Boe, A counterexample to the Gabber-Joseph conjecture, Kazhdan-Lusztig theory and related topics, Contemporary Math. vol. 139, Amer. Math. Soc. 1992, 1-3.

[3] T. Braden, R. MacPherson, private communication, September 1994.

[4] F. Brenti, Combinatorial properties of the Kazhdan-Lusztig R-polynomials for S_{n}, Adv. in Math., 126 (1997), 21-51.

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

[6] F. Brenti, Upper and lower bounds for Kazhdan-Lusztig polynomials, Europ. J. Combinatorics, to appear.

[7] F. Brenti, Combinatorial expansions of Kazhdan-Lusztig polynomials, J. London Math. Soc., 55 (1997), 448-472.

[8] F. Brenti, in preparation.

[9] V. V. Deodhar, On some geometric aspects of Bruhat orderings. I. A finer decomposition of Bruhat cells, Invent. Math. 79 (1985), 499-511.

[10] V. V. Deodhar, A combinatorial setting for questions in Kazhdan-Lusztig Theory, Geom. Dedicata, 36 (1990), 95-120.

[11] V. V. Deodhar (Editor), Kazhdan-Lusztig theory and related topics, Contemporary Math. vol. 139, Amer. Math. Soc. 1992.

[12] M. Dyer, On the “Bruhat graph” of a Coxeter system, Comp. Math., 78 (1991), 185-191.

[13] M. Dyer, Hecke algebras and shellings of Bruhat intervals, Comp. Math., 89 (1993), 91-115.

[14] A. Garsia, T. McLarnan, Relations between Young’s natural and the Kazhdan-Lusztig representations of S_{n}, Adv. Math., 69 (1988), 32-92.

[15] M. Haiman, G. Kalai, private communication, April 1992.

[16] M. Haiman, private communication, September 1992.

[17] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no.29, Cambridge Univ. Press, Cambridge, 1990.

[18] D. Kazhdan, G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165-184.

[19] D. Kazhdan, G. Lusztig, Schubert varieties and Poincaré duality, Geometry of the Laplace operator, Proc. Sympos. Pure Math. 34, Amer. Math. Soc., Providence, RI, 1980, pp. 185-203.

[20] V. Lakshmibai, B. Sandhya, Criterion for smoothness of Schubert varieties in S_{l(n)/B}, Proc. Indian Acad. Sci. Math. Sci., 100 (1990), 45-52.

[21] A. Lascoux, M.-P. Schützenberger, Polynômes de Kazhdan & Lusztig pour les grassmanniennes, Young tableaux and Schur functions in algebra and geometry, Astérisque, 87-88 (1981), pp. 249-266.

[22] G. Lusztig, private communication, September 1993.

[23] I. G. Macdonald, Notes on Schubert Polynomials, Publ. LACIM, UQAM, Montreal, 1991.

[24] B. Shapiro, M. Shapiro, A. Vainshtein, Incomplete flag varieties and Kazhdan-Lusztig polynomials, Discrete Math., to appear.

[25] R. P. Stanley, Enumerative Combinatorics , vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[26] R. P. Stanley, Generalized h-vectors, intersection cohomology of toric varieties, and related results, Adv. Studies Pure Math., 11 (1987), 187-213.

[27] R. P. Stanley, Subdivisions and local h-vectors, J. Amer. Math. Soc., 5 (1992), 805-851.

[28] A. Zelevinski, Small resolutions of singularities of Schubert varieties, Funct. Anal. Appl., 17 (1983), 142-144.

Dipartimento di Matematica Universitá di Roma “Tor Vergata” Via della Ricerca Scientifica, 1 00133 Roma, Italy