A Combinatorial Formula for Kazhdan-Lusztig polynomials

Francesco Brenti^{1}

1 Introduction

In their fundamental paper [14] 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., [12], 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.

Our aim in this work is to give a simple, nonrecursive, combinatorial formula for any Kazhdan-Lusztig polynomial of any Coxeter group (Theorem 4.1) , and to study some consequences of it. The main idea involved in the proof and statement of this formula is that of extending the concept of the R-polynomial (see, e.g., [12], §7.5) to any (finite) multichain of W (so that, for multichains of length 1, one obtains, apart from sign, the usual R-polynomials). Once this has been done, then the Kazhdan-Lusztig polynomial of a pair u, v turns out to be just the sum, over all multichains from u to v, of the corresponding (generalized) R-polynomials. The Rpolynomial of a multichain can be readily defined, and computed, from the ordinary R-polynomials (see (9), (10), and (11)). Since several combinatorial formulas and interpretations are known for these polynomials (see, e.g., [5], [10], and, for the case of symmetric groups, [3]) and simple recurrences exist for them, we feel that this formula is a significant step forward in the understanding of the Kazhdan-Lusztig polynomials. Though combinatorial formulas for Kazhdan-Lusztig polynomials have appeared before in the literature (see, e.g., [16], [21], [8], [6]), none of them hold in complete generality.

The organization of the paper is as follows. In the next section we recall some basic definitions, notation, and results, both of an algebraic and combinatorial nature, that will be used in the rest of this work. In section 3 we introduce and study the crucial concept of this paper, namely the R-polynomial of a multichain. In section 4 we prove our main result (Theorem 4.1). This expresses the Kazhdan-Lusztig polynomial of any Bruhat interval as the sum of the R-polynomials of its multichains. In section 5 we use this result to obtain combinatorial formulas for each coefficient of any Kazhdan-Lusztig polynomial. Even in their simplest special cases these formulas are new (see Corollaries 5.3 and 5.4) and have interesting and nontrivial consequences. In section 6 we use one of these special cases to characterize those Bruhat intervals whose Kazhdan-Lusztig polynomial equals the g-polynomial (as defined in [18]) of the dual interval (Theorem 6.3). Our characterization is purely combinatorial and depends only on the isomorphism type of the interval as a poset. As a consequence of it we obtain explicit formulas for the Kazhdan-Lusztig polynomials of intervals which are lattices (Theorem 6.4) as well as for several other classes of intervals. Finally, in section 7, we briefly sketch how it is possible to obtain analogues of all the results in the previous sections for inverse Kazhdan-Lusztig polynomials.

1A mia moglie, Annamaria.

2 Notation and Preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of this work. We let P =^{def} {1, 2, 3, …} , N=^{def}P ∪{0}, Z be the ring of integers, and Q be the field of rational numbers; 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|, for r ∈ N we let (\begin{matrix}A \\ r \end{matrix}) =^{def} \{S ⊆ A : |S| = r\}. For S ⊆ P and j ∈ P we let S_{j} be the j-th largest element of S, and S_{j} =^{def} 0 if j > |S|, (so S = {S_{|S|}, …, S_{1}}_{<}). Given a polynomial P (q), and i ∈ Z, we will denote by [q^{i}](P (q)) the coefficient of q^{i} in P (q). For a ∈ R we let ⌊a⌋ (respectively, ⌈a⌉) denote the largest integer ≤ a (respectively, smallest integer ≥ a).

Given a set T we let S(T) be the set of all bijections π : T → T, and S_{n} =^{def} S([n]). If σ ∈ S_{n} then we write σ = σ_{1} … σ_{n} to mean that σ(i) = σ_{i}, for i = 1, …, n. We will also write σ in disjoint cycle form (see, e.g., [17], 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 [17], Chap. 3, for notation and terminology concerning partially ordered sets. In particular, given a finite graded poset P and S ⊆ N we let P_{S} =^{def} {x ∈ P : ρ(x) ∈ S}, where ρ : P → N is the rank function of P, and α(P; S) be the number of maximal chains of P_{S}. We also let P_{i} =^{def} P_{{i}} if i ∈ N, and G_{P} (q) =^{def} ∑_{i≥0} P_{i}q^{i}. We call G_{P} (q) the rank generating function (or growth function) of P. We say that a finite graded poset P as above is Eulerian if P has a ˆ0 and ˆ1 and μ(x, y) = (−1)^{ρ(y)−ρ(x)} for all x, y ∈ P, x ≤ y. Recall (see, e.g., [17], §3.14, p. 138, or [18], §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 [18] and are two very subtle invariants of the Eulerian poset P (see [17], §3.14, and [18], §§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.

We will follow [12] for general Coxeter groups notation and terminology. Given a Coxeter system (W, S) and σ ∈ W we denote by l(σ) the length of σ in W, with respect to S, and we let

D(σ) =^{def} {s ∈ S : l(σ s) < l(σ)} ,

and

ε_{σ} =^{def} (−1)^{l(σ)}.

We call D(σ) the descent set of σ. We denote by e the identity of W, and we let T =^{def} {σsσ^{−1} : σ ∈ W, s ∈ S} be the set of reflections of W. We will always assume that W is partially ordered by (strong) Bruhat order. Recall (see, e.g., [12], §5.9) that this means that x ≤ y if and only if there exist r ∈ N and t_{1}, …, t_{r} ∈ T such that t_{r} … t_{1} x = y and l(t_{i} … t_{1} x) > l(t_{i−1} … t_{1}x) for i = 1, …, r. For example, the Hasse diagram of the Bruhat order on S_{3} is shown in Figure 1. Given u, v ∈ W we let [u, v] =^{def} {x ∈ W : u ≤ x ≤ v}. We consider [u, v] as a poset with the partial ordering induced by W. In particular, we will often use notation such as [u, v]_{S} or [u, v]_{i} (S ⊆ N, i ∈ N) to denote the rank-selected subposets of [u, v]. For simplicity we let c(u, v) =^{def} |[u, v]_{l(v)−l(u)−1}| and a(u, v) =^{def} |[u, v]_{1}|. It is well known (see, e.g., [2], Corollary 1) that intervals of W (and their duals) are Eulerian posets.

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

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

Recall (see, [12], §8.6, or, [9]) that the Bruhat graph of a Coxeter system (W, S) is the directed graph B(W, S) obtained by taking W as vertex set and putting a directed edge from x to y if and only if yx^{−1} ∈ T and l(x) < l(y). For example, the Bruhat graph of S_{3} is depicted in Figure 2. It follows immediately from the definitions that B(W, S) contains the Hasse diagram of the Bruhat order of W (considered as a directed graph in the obvious way) as a directed subgraph.

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

Figure 2: The Bruhat graph of S_{3}.

We denote by H(W) the Hecke algebra associated to W. Recall (see, e.g., [12], Chap.

7) that this is the free Z[q, q^{−1}]-module having the set {T_{w} : w ∈ W } as a basis and multiplication such that

T_{w}T_{s} = \{ \begin{matrix}T_{ws}, & if l(ws) > l(w), \\ qT_{ws} + (q − 1)T_{w}, & if l(ws) < l(w), \end{matrix}  (3)

for all w ∈ W and s ∈ S. It is well known that this is an associative algebra having T_{e} as unity and that each basis element is invertible in H(W). More precisely, we have the following result (see, [12], Proposition 7.4).

Proposition 2.1 Let v ∈ W. Then

(T_{v^{−1}})^{−1} = q^{−l(v)} ∑_{u≤v}(−1)^{l(v)−l(u)} R_{u,v}(q) T_{u} ,

where R_{u,v}(q) ∈ Z[q].

The polynomials R_{u,v} defined by the previous proposition are called the R-polynomials of W. It is easy to see that deg(R_{u,v}) = l(v) − l(u), and that R_{u,u}(q) = 1, for all u, v ∈ W, u ≤ v. It is customary to let R_{u,v}(q) =^{def} 0 if u ≰ v. We then have the following fundamental result that follows from (3) and Proposition 2.1 (see [12], §7.5).

Theorem 2.2 Let u, v ∈ W and s ∈ D(v). Then

R_{u,v}(q) = \{ \begin{matrix}R_{us,vs}(q), & if s ∈ D(u), \\ qR_{us,vs}(q) + (q − 1)R_{u,vs}, & if s ∉ D(u). \end{matrix}  (4)

Note that the preceding theorem can be used to inductively compute the R-polynomials since l(vs) < l(v). Therefore, one could take Theorem 2.2 as the definition of the Rpolynomials, together with the initial conditions that R_{u,u}(q) = 1 and R_{u,v}(q) = 0, for all u, v ∈ W, u ≰ v.

Theorem 2.2 has also the following simple but important consequence.

Proposition 2.3 Let u, v ∈ W. Then there exists a (necessarily unique) polynomial R̃_{u,v}(q) ∈ N[q] such that

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

Combinatorial interpretations of the coefficients of R̃_{u,v}(q) have been given by V. Deodhar (see [5], Theorem 1.3) and by M. Dyer (see [7], and [10]). In particular, Dyer’s interpretation implies the following result (we refer the reader to [10], §§2, 3, for its proof, see also [9], §(3.5)), which can also be proved directly, by induction on l(v), from (4) and (5).

Proposition 2.4 Let u, v ∈ W, and k ∈ N. Then [q^{k}](R̃_{u,v}(q)) ≠ 0 if and only if there is a directed path in B(W, S) from u to v of length k.

Note that it follows easily from Theorem 2.2 and Proposition 2.3 that, for any u, v ∈ W, there exists a unique polynomial Q_{u,v}(q) such that

R̃_{u,v}(q) = \{ \begin{matrix}qQ_{u,v}(q^{2}), & if l(v) − l(u) ≡ 1 (2), \\ Q_{u,v}(q^{2}), & if l(v) − l(u) ≡ 0 (2). \end{matrix}  (6)

There is one more property of the R-polynomials that we will use quite often in this work (and, sometimes, without explicit mention). We recall it here for the reader’s convenience.

Proposition 2.5 Let u, v ∈ W. Then

(−q)^{l(v)−l(u)}R_{u,v} (\frac{1}{q}) = R_{u,v}(q) .  (7)

A proof of the preceding result can be found, e.g., in [12], §7.8.

The R-polynomials can be used to define the Kazhdan-Lusztig polynomials. The following result is not hard to prove (and, in fact, holds in much greater generality, see [19], Corollary 6.7 and Example 6.9) and a proof can be found, e.g., in [12], §§7.9-11, or [14], §2.2.

Theorem 2.6 There is a unique family of polynomials {P_{u,v}(q)}_{u,v∈W} ⊆ Z[q], such that, for all u, v ∈ W:

i) P_{u,v}(q) = 0 if u ≰ v;

ii) P_{u,u}(q) = 1;

iii) deg(P_{u,v}(q)) ≤ ⌊\frac{1}{2} (l(v) − l(u) − 1)⌋, if u < v;

iv)

q^{l(v)−l(u)} P_{u,v} (\frac{1}{q}) = ∑_{u≤z≤v} R_{u,z}(q) P_{z,v}(q) ,  (8)
if u ≤ v.

The polynomials P_{u,v}(q) defined by the preceding theorem are called the Kazhdan-Lusztig polynomials of W. Note that parts iii) and iv) of Theorem 2.6 actually yield an inductive procedure to compute the polynomials P_{u,v}(q) for all u, v ∈ W, taking parts i) and ii) as initial conditions.

Throughout this work (unless otherwise explicitly stated) (W, S) denotes a fixed (but arbitrary) Coxeter system.

3 The R-polynomial of a multichain

In this section we define and study the crucial concept of this work, namely the R-polynomial of a multichain. This is a polynomial which can be associated to any (finite) multichain of W and which reduces (essentially, see (11)) to the ordinary Rpolynomial if the multichain has length one. The importance of this concept lies in the fact that it plays a fundamental role in the computation of the Kazhdan-Lusztig polynomials of a Coxeter group, as will be seen in the next section (see Theorem 4.1). In this section we define the R-polynomial of a multichain and derive some of its basic properties.

Given a polynomial p(x) =^{def} ∑_{i=0}^{d} a_{i}x^{i} (with coefficients in some ring) and j ∈ Z we let

U_{j}(p) =^{def} ∑_{i=j}^{d} a_{i}x^{i} .  (9)

So, for example, U_{2}(x − 3x^{2} + 2x^{3}) = −3x^{2} + 2x^{3}, and U_{j}(p) = p, for any polynomial p, if j < 0. Note that the operators U_{j} are linear and idempotent.

Given a multichain a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} (r ∈ N) in W we define a polynomial R_{a_{0},a_{1},...,a_{r+1}}(q) inductively as follows,

R_{a_{0},a_{1},...,a_{r+1}}(q) =^{def} R_{a_{0},a_{1}}(q)U_{⌈ \frac{d+1}{2} ⌉} (q^{d}R_{a_{1},...,a_{r+1}} (\frac{1}{q})) ,  (10)

(where d =^{def} l(a_{r+1}) − l(a_{1})) if r ∈ P, and

R_{a_{0},a_{1},...,a_{r+1}}(q) =^{def} (−1)^{l(a_{1})−l(a_{0})}R_{a_{0},a_{1}}(q)  (11)

if r = 0. We call R_{a_{0},a_{1},...,a_{r+1}}(q) the R-polynomial of the multichain a_{0} ≤ a_{1} ≤ … ≤ a_{r+1}. For example, in W = S_{4} we have that

R_{2134,2314,2413}(q) = R_{2134,2314}(q) U_{1} (qR_{2314,2413} (\frac{1}{q}))
= −R_{2134,2314}(q) U_{1} (−qR_{2314,2413} (\frac{1}{q}))
= (1 − q) U_{1}(q − 1) = q − q^{2} ,

and

R_{1234,2134,2314,2413}(q) = R_{1234,2134}(q) U_{2} (q^{2}R_{2134,2314,2413} (\frac{1}{q}))
= −R_{1234,2134}(q) U_{2}(q − 1) = 0 .

We begin our study of the R-polynomial of a multichain by considering its degree. Given a multichain a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} in W (r ∈ N) we denote by m(a_{0}, …, a_{r+1}) the maximum power of q that divides R_{a_{0},...,a_{r+1}}(q).

Proposition 3.1 Let r ∈ P and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} be a multichain in W such that R_{a_{0},...,a_{r+1}} ≠ 0. Then

deg(R_{a_{0},...,a_{r+1}}) = l(a_{r+1}) − l(a_{0}) − m(a_{1}, …, a_{r+1}) ,  (12)

and

m(a_{0}, …, a_{r+1}) ≥ ⌈\frac{1}{2} (l(a_{r+1}) − l(a_{1}) + 1)⌉ .  (13)

In particular,

deg(R_{a_{0},...,a_{r+1}}) ≤ l(a_{2}) − l(a_{0}) + ⌊\frac{1}{2} (l(a_{r+1}) − l(a_{2}) − 1)⌋ .  (14)

Proof. Let, for brevity, d =^{def} l(a_{r+1}) − l(a_{1}). Then, by (10), we have that

deg(R_{a_{0},...,a_{r+1}}) = deg(R_{a_{0},a_{1}}) + deg (U_{⌈ \frac{d+1}{2} ⌉} (q^{d}R_{a_{1},...,a_{r+1}} (\frac{1}{q})))
= l(a_{1}) − l(a_{0}) + deg (q^{d}R_{a_{1},...,a_{r+1}} (\frac{1}{q}))
= l(a_{1}) − l(a_{0}) + d − m(a_{1}, …, a_{r+1}),

and (12) follows. Now (13) is immediate from (10), and (14) follows from (12) and (13). □

It is easy to construct examples which show that the bound given in (13) is best possible. In fact, we believe that equality always holds in (13) (and hence in (14)).

The preceding result has the following consequence.

Corollary 3.2 Let r ∈ P, and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} be a multichain in W. Then the number of non-zero coefficients in R_{a_{0},...,a_{r+1}} is at most

\frac{1}{2} (l(a_{1}) + l(a_{2})) − l(a_{0}).□

We note the following simple observation which will be used in the proof of Theorem 4.1.

Proposition 3.3 Let r ∈ N and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} be a multichain in W. Then

R_{a_{0},...,a_{r+1}}(0) = \{ \begin{matrix}1, & if r = 0, \\ 0, & otherwise. □ \end{matrix}

Since we are unable to decide whether equality always holds in (14) it is natural to try to obtain lower bounds on the degree of the R-polynomial of a multichain.

Proposition 3.4 Let r ∈ P and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} be a multichain in W such that R_{a_{0},...,a_{r+1}} ≠ 0. Then

deg(R_{a_{0},...,a_{r+1}}) ≥ l(a_{1}) − l(a_{0}) + ⌈\frac{1}{2} (l(a_{r+1}) − l(a_{1}) + 1)⌉ .

Proof. Let, for brevity, d =^{def} l(a_{r+1}) − l(a_{1}). Then, since R_{a_{0},...,a_{r+1}}(q) ≠ 0, we conclude from (10) that

deg(R_{a_{0},...,a_{r+1}}) = deg(R_{a_{0},a_{1}}) + deg (U_{⌈ \frac{d+1}{2} ⌉} (q^{d}R_{a_{1},...,a_{r+1}} (\frac{1}{q})))
≥ l(a_{1}) − l(a_{0}) + m(a_{0}, …, a_{r+1}),

by Proposition 3.3, and the thesis follows from (13). □

We now investigate the problem of characterizing those multichains whose Rpolynomial is identically zero.

Proposition 3.5 Let r ∈ P and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} be a multichain in W such that R_{a_{0},...,a_{r+1}} ≠ 0. Then l(a_{r+1}) − l(a_{r}) ≥ 1, and l(a_{i+1}) − l(a_{i}) ≥ 2 for i = 1, …, r − 1. In particular l(a_{r+1}) − l(a_{1}) ≥ 2r − 1.

Proof. We proceed by induction on r ∈ P. It is clear from (10) that R_{a_{0},a_{1},a_{2}}(q) ≠ 0 if and only if l(a_{2}) − l(a_{1}) ≥ 1. So fix r ≥ 2 and assume that the proposition holds for all multichains of length ≤ r. Since R_{a_{0},...,a_{r+1}}(q) ≠ 0 then, by (10),

U_{⌈ \frac{d+1}{2} ⌉}(q^{d}R_{a_{1},...,a_{r+1}}(\frac{1}{q})) ≠ 0 (where d =^{def} l(a_{r+1}) − l(a_{1})), and hence R_{a_{1},...,a_{r+1}}(q) ≠ 0

and

deg (q^{d}R_{a_{1},...,a_{r+1}} (\frac{1}{q})) ≥ ⌈\frac{1}{2} (l(a_{r+1}) − l(a_{1}) + 1)⌉ .  (15)

By our induction hypothesis this implies that l(a_{r+1})−l(a_{r}) ≥ 1, and l(a_{i+1})−l(a_{i}) ≥ 2 for i = 2, …, r − 1. Also, by Proposition 3.1 we have that

m(a_{1}, …, a_{r+1}) ≥ ⌈\frac{1}{2} (l(a_{r+1}) − l(a_{2}) + 1)⌉ .  (16)

Comparing (15), and (16) yields that

⌈\frac{1}{2} (l(a_{r+1}) − l(a_{2}) + 1)⌉ ≤ d − ⌈\frac{1}{2} (l(a_{r+1}) − l(a_{1}) + 1)⌉

which implies that l(a_{2}) − l(a_{1}) ≥ 2, as desired. □

It would be interesting to know if the converse of the preceding proposition holds. We conclude this section with the following two technical results which are easy

consequences of the definitions (9), and (10), and which will be used in sections 4 and 5.

Lemma 3.6 Let i ∈ Z, r ∈ P and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} be a multichain in W. Then

∑_{j≥⌈ \frac{ρ(a_{1})+1}{2} ⌉}[q^{i−j}](R_{a_{0},a_{1}})[q^{ρ(a_{1})−j}](R_{a_{1},...,a_{r+1}}) = [q^{i}](R_{a_{0},a_{1},...,a_{r+1}}),  (17)

where ρ : [a_{0}, a_{r+1}] → N is the rank function of [a_{0}, a_{r+1}]^{∗}.

Proof. From the definition (10) we obtain that

[q^{i}](R_{a_{0},...,a_{r+1}}) = ∑_{j=0}^{i}[q^{i−j}](R_{a_{0},a_{1}})[q^{j}] (U_{⌈ \frac{ρ(a_{1})+1}{2} ⌉} (q^{ρ(a_{1})}R_{a_{1},...,a_{r+1}} (\frac{1}{q})))

and (17) follows. □

The next result is a straightforward consequence of the preceding lemma and its proof is omitted.

Proposition 3.7 Let r ∈ P, k ∈ Z, and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} be a multichain in W. Then

[q^{k}](R_{a_{0},a_{1},...,a_{r+1}}) = ∑_{j_{1}≥⌈ \frac{ρ(a_{1})+1}{2} ⌉} … ∑_{j_{r}≥⌈ \frac{ρ(ar)+1}{2} ⌉} ∏_{i=0}^{r}[q^{ρ(a_{i})−j_{i}−j_{i+1}}](R_{a_{i},a_{i+1}})  (18)

where ρ : [a_{0}, a_{r+1}] → N is the rank function of [a_{0}, a_{r+1}]^{∗}, j_{r+1} =^{def} 0, and j_{0} =^{def} ρ(a_{0}) − k. □

4 The main result

In this section we prove the main result of this work (Theorem 4.1), and give some applications of it.

Theorem 4.1 Let u, v ∈ W. Then

P_{u,v}(q) = ∑_{C∈C(u,v)} R_{C}(q)  (19)

where C(u, v) denotes the set of all multichains from u to v.

Proof. Note first that, by Proposition 3.5, the sum on the RHS of (19) is finite. We will show by induction on i ∈ N that

[q^{i}](P_{u,v}(q)) = [q^{i}]( ∑_{C∈C(u,v)} R_{C}(q))  (20)

for all u, v ∈ W, u ≤ v. If i = 0 then, by Proposition 3.3,

[q^{0}]( ∑_{C∈C(u,v)} R_{C}(q)) = ∑_{C∈C(u,v)} R_{C}(0) = R_{u,v}(0) = 1 = [q^{0}](P_{u,v}).

Now fix k ∈ P and assume that (20) holds for all i ≤ k − 1 and all u, v ∈ W, u ≤ v. Then substituting q with q^{−1} in part iv) of Theorem 2.6 we get that

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

Using (11), and Proposition 2.5, we may rewrite (21) as

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

Extracting the coefficient of q^{k} on both sides of (22) we obtain that

[q^{k}](P_{u,v}) − [q^{k}](R_{u,v}) = ∑_{u≤a<v} ∑_{i=0}^{k}[q^{k−i}](R_{u,a})[q^{ρ(a)−i}](P_{a,v}) ,  (23)

where ρ : [u, v] → N is the rank function of [u, v]^{∗}. Now note that, by part iii) of Theorem 2.6, the coefficient of q^{ρ(a)−i} in P_{a,v}(q) is zero if i < ⌈\frac{1}{2}(ρ(a)+1)⌉. Therefore we may rewrite (23) as

[q^{k}](P_{u,v}) − [q^{k}](R_{u,v}) = ∑_{a∈[u,v)} ∑_{i=⌈\frac{ρ(a)+1}{2}⌉}^{k}[q^{k−i}](R_{u,a})[q^{ρ(a)−i}](P_{a,v}) .  (24)

But for any a ∈ [u, v) and i ∈ [⌈\frac{ρ(a)+1}{2}⌉, k] we have that ρ(a) − i ≤ i − 1 ≤ k − 1. Therefore, using Lemma 3.6, and our induction hypotheses, we conclude from (24) that

[q^{k}](P_{u,v}) − [q^{k}](R_{u,v}) = ∑_{a∈[u,v)} ∑_{i≥⌈ \frac{ρ(a)+1}{2} ⌉}[q^{k−i}](R_{u,a})[q^{ρ(a)−i}]( ∑_{C∈C(a,v)} R_{C})
= ∑_{a∈[u,v)} ∑_{C∈C(a,v)} ∑_{i≥⌈\frac{ρ(a)+1}{2}⌉}[q^{k−i}](R_{u,a})[q^{ρ(a)−i}](R_{C})
= ∑_{a∈[u,v)} ∑_{C∈C(a,v)}[q^{k}](R_{u,C})
= ∑_{C∈C(u,v)}[q^{k}](R_{C}) − [q^{k}](R_{u,v})
= [q^{k}]( ∑_{C∈C(u,v)} R_{C}) − [q^{k}](R_{u,v}).□

Recall (see, e.g., [17], p. 100) that the length of a multichain a_{0} ≤ a_{1} ≤ … ≤ a_{r} is r. Given u, v ∈ W, and k ∈ N, we denote by C_{k}(u, v) the set of all multichains from u to v of length ≤ k + 1.

Corollary 4.2 Let u, v ∈ W. Then

P_{u,v}(q) = ∑_{C∈C_{⌊ \frac{1}{2} (l(v)−l(u)+1)⌋}(u,v)} R_{C}(q) .

Proof. Proposition 3.5 implies that R_{C}(q) = 0 if C ∈ C(u, v) \ C_{⌊ \frac{1}{2} (l(v)−l(u)+1)⌋}(u, v), so the thesis follows from Theorem 4.1. □

Given a finite Coxeter system (W, S) we denote by ω_{0} the longest element of W.

Corollary 4.3 Let (W, S) be a finite Coxeter system, and u, v ∈ W. Then

P_{u,v}(q) = P_{ω_{0}uω_{0},ω_{0}vω_{0}}(q) .

Proof. It is well known (see, e.g., [12], Proposition 7.6) that

R_{u,v}(q) = R_{ω_{0}uω_{0},ω_{0}vω_{0}}(q),

for all u, v ∈ W. Using this, and the definitions (10) and (11) we conclude easily that

R_{a_{0},a_{1},...,a_{r+1}}(q) = R_{ω_{0}a_{0}ω_{0},...,ω_{0}a_{r+1}ω_{0}}(q)  (25)

for all multichains a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} of W. But it is easy to see (see also [12], §5.9, Example 3), that the map Ω : W → W defined by Ω(x) =^{def} ω_{0}xω_{0} is a poset isomorphism of W. Therefore we conclude from (25) and Theorem 4.1 that

P_{u,v}(q) = ∑_{C∈C(u,v)} R_{Ω(C)}(q) = ∑_{C′∈C(ω_{0}uω_{0},ω_{0}vω_{0})} R_{C′}(q) = P_{ω_{0}uω_{0},ω_{0}vω_{0}}(q) ,

as desired. □

In a completely analogous way one can prove the following result which, although known (see, e.g., [8], p. 356), is made particularly transparent by Theorem 4.1.

Corollary 4.4 Let u, v ∈ W. Then

P_{u,v}(q) = P_{u^{−1},v^{−1}}(q) .□

5 Coefficients of Kazhdan-Lusztig polynomials

In this section we use Theorem 4.1 to obtain explicit formulas for the coefficients of Kazhdan-Lusztig polynomials.

Our first result shows that the summation set on the RHS of (19) becomes smaller when we extract the coefficient of q^{k}.

Theorem 5.1 Let u, v ∈ W, and k ∈ N. Then

[q^{k}](P_{u,v}(q)) = [q^{k}]( ∑_{C∈C_{k}(u,v)} R_{C}(q)) ,  (26)

where C_{k}(u, v) denotes the set of all multichains from u to v of length ≤ k + 1.

Proof. By Theorem 4.1 we only have to show that

[q^{k}](R_{C}(q)) = 0  (27)

if C ∈ C(u, v) \ C_{k}(u, v). So let a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} be a multichain from u to v in W such that r > k and R_{a_{0},...,a_{r+1}}(q) ≠ 0. Then from Proposition 3.5 we have that

l(a_{r+1}) − l(a_{1}) ≥ 2r − 1 .  (28)

Hence we conclude from (28) and Proposition 3.1 that

m(a_{0}, …, a_{r+1}) ≥ ⌈\frac{1}{2} (l(a_{r+1}) − l(a_{1}) + 1)⌉ ≥ r > k ,

which proves (27). □

Note that the terms in the summation on the RHS of (26) are not all of the same sign. Therefore (26) does not shed light on the conjectured nonnegativity (see [14], p. 166) of the coefficients of Kazhdan-Lusztig polynomials.

Using (11) and Proposition 3.7 it is possible to express the coefficients of Kazhdan-Lusztig polynomials solely in terms of coefficients of (ordinary) R-polynomials.

Theorem 5.2 Let u, v ∈ W, and k ∈ N. Then

[q^{k}](P_{u,v}(q)) = ∑_{S⊆[k]} ∑_{(a_{0},...,a_{|S|+1})∈C_{S}(u,v)} ∏_{r=0}^{|S|}[q^{l(a_{r+1})−l(v)+S_{r}+S_{r+1}}](R_{a_{r},a_{r+1}}(q)) (29)

where C_{S}(u, v) is the set of all multichains a_{0} ≤ a_{1} ≤ … ≤ a_{|S|+1} from u to v such that S_{r+1} ≤ l(v) − l(a_{r}) − S_{r} ≤ S_{r} − 1, for r = 1, …, |S|, and where S_{0} =^{def} l(v) − l(u) − k.

Proof. From Theorem 5.1 and Proposition 3.7 we obtain that

[q^{k}](P_{u,v}) = ∑_{C∈C_{k}(u,v)}[q^{k}](R_{C})  (30)
= ∑_{(a_{0},...,a_{r+1})∈C_{k}(u,v)} ∑_{j_{1}≥⌈ \frac{ρ(a_{1})+1}{2} ⌉} … ∑_{j_{r}≥⌈ \frac{ρ(ar)+1}{2} ⌉} ∏_{i=0}^{r}[q^{ρ(a_{i})−j_{i}−j_{i+1}}](R_{a_{i},a_{i+1}})

where ρ : [u, v] → N is the rank function of [u, v]^{∗}, j_{0} =^{def} ρ(a_{0}) − k, and j_{r+1} =^{def} 0. Now note that if (j_{1}, …, j_{r}) ∈ N^{r} is such that j_{i} ≥ ⌈\frac{ρ(a_{i})+1}{2}⌉ for i = 1, …, r and ∏_{i=0}^{r}[q^{ρ(a_{i})−j_{i}−j_{i+1}}](R_{a_{i},a_{i+1}}) ≠ 0 then necessarily ρ(a_{i})−j_{i}−j_{i+1} ≥ 0, for i = 0, …, r, and therefore k ≥ j_{1} > j_{2} > … > j_{r} > 0. Hence

∑_{j_{1}≥⌈ \frac{ρ(a_{1})+1}{2} ⌉} … ∑_{j_{r}≥⌈ \frac{ρ(ar)+1}{2} ⌉} ∏_{i=0}^{r}[q^{ρ(a_{i})−j_{i}−j_{i+1}}](R_{a_{i},a_{i+1}}) =

∑_{S∈F_{k}(ρ(a_{1}),...,ρ(a_{r}))} ∏_{i=0}^{r}[q^{ρ(a_{i})−S_{i}−S_{i+1}}](R_{a_{i},a_{i+1}}) ,  (31)

where F_{k}(n_{1}, …, n_{r}) =^{def} \{S ∈ \binom{[k]}{r} : S_{i+1} ≤ n_{i} − S_{i} ≤ S_{i} − 1, i = 1, …, r\}, for

n_{1}, …, n_{r} ∈ N. Therefore, by (30) and (31),

[q^{k}](P_{u,v}) = ∑_{(a_{0},...,a_{r+1})∈C_{k}(u,v)} ∑_{S∈F_{k}(ρ(a_{1}),...,ρ(a_{r}))} ∏_{i=0}^{r}[q^{ρ(a_{i})−S_{i}−S_{i+1}}](R_{a_{i},a_{i+1}}) . (32)

Inverting the order of summation in the RHS of (32), and using (11) and (7), yields (29), as desired. □

For small values of k the formula in Theorem 5.2 yields very explicit information on [q^{k}](P_{u,v}). In the rest of this section we analyze in some detail the two smallest non-trivial cases, namely k = 1 and k = 2. Even in these two simple special cases the resulting formulas are new and, as will be seen in this and the following section, have non-trivial consequences.

Corollary 5.3 Let u, v ∈ W. Then

[q](P_{u,v}(q)) = (−1)^{l(v)−l(u)} [q](R_{u,v}(q)) + c(u, v)

where c(u, v) is the number of coatoms in [u, v].

Proof. We obtain from Theorem 5.2 that

[q](P_{u,v}) = [q^{S_{0}}](R_{u,v}) + ∑_{a∈[u,v]_{1}^{∗}}[q^{l(a)−l(v)+S_{0}+1}](R_{u,a}) [q](R_{a,v})  (33)

where S_{0} has the same meaning as in the statement of Theorem 5.2, and the thesis follows. □

A result similar to the preceding one appears (for Weyl groups) in [4].

Corollary 5.4 Let u, v ∈ W. Then

[q^{2}](P_{u,v}(q)) = (−1)^{l(v)−l(u)}[q^{2}](R_{u,v}(q)) + ∑_{a∈[u,v]_{1}^{∗}}(−1)^{l(v)−l(u)−1}[q](R_{u,a}(q)) + |[u, v]_{2}^{∗}|

− ∑_{a∈[u,v]_{3}^{∗}}[q](R_{a,v}(q)) + α([u, v]^{∗} , {1, 3}) .

Proof. We obtain from (7) and Theorem 5.2 that

(−1)^{l(v)−l(u)}[q^{2}](P_{u,v}) = [q^{2}](R_{u,v}) + ∑_{a∈[u,v]_{1}^{∗}}[q](R_{u,a})[q^{0}](R_{a,v})

+ ∑_{a∈[u,v]_{2}^{∗}}[q^{0}](R_{u,a}) [q^{0}](R_{a,v}) + ∑_{a∈[u,v]_{3}^{∗}}[q^{0}](R_{u,a})[q](R_{a,v})

+ ∑_{(a_{0},...,a_{3})∈C_{{2,1}}(u,v)}[q^{0}](R_{u,a_{1}}) [q^{0}](R_{a_{1},a_{2}}) [q^{0}](R_{a_{2},v}) ,

and the thesis follows since |C_{[2]}(u, v)| = α([u, v]^{∗}; {1, 3}). □

There is an equivalent way of stating Corollaries 5.3 and 5.4 which suggests some possible lines of further investigation. For this we will find it convenient to let, for u, v ∈ W,

G̃_{[u,v]}(q) =^{def} ε_{u}ε_{v}G_{[u,v]}(−q) ,

so that

[q^{i}](G̃_{[u,v]}(q)) = (−1)^{l(v)−l(u)+i} |[u, v]_{i}|  (34)

for i ∈ Z.

Corollary 5.5 Let u, v ∈ W. Then

[q](P_{u,v}(q)) = [q^{l(v)−l(u)−1}](R_{u,v}(q) − G̃_{[u,v]}(q))  (35)

and

[q^{2}](P_{u,v}(q)) = ∑_{a∈[u,v]_{{0,1}}^{∗}}[q^{l(v)−l(u)−2}](R_{u,a}(q)−G̃_{[u,a]}(q))+ ∑_{a∈[u,v]_{3}^{∗}}[q^{2}](R_{a,v}(q)−G̃_{[a,v]}(q)) .

(36)

Proof. (35) follows immediately from (7), (34), and Corollary 5.3. To prove (36) note that it follows from (34) that

∑_{a∈[u,v]_{1}^{∗}}[q^{l(v)−l(u)−2}](G̃_{[u,a]}(q)) = −α([u, v]^{∗}, {1, 2})  (37)

and

∑_{a∈[u,v]_{3}^{∗}}[q^{2}](G̃_{[a,v]}(q)) = −α([u, v]^{∗}, {1, 3}) .  (38)

But it is well known (see, e.g., [2]) that every interval of W of length 2 is isomorphic to a Boolean algebra (as a poset). Hence

α([u, v]^{∗}, {1, 2}) = 2|[u, v]_{2}^{∗}|,

and (36) follows from (37), (38), (7), and Corollary 5.4. □

In view of the conjectured nonnegativity of the coefficients of Kazhdan-Lusztig polynomials (see [14], p. 166, and also [12], §7.9, p. 159) the formulas (35) and (36) naturally suggest the question of whether R_{u,v}(q) − G̃_{[u,v]}(q) is a polynomial with nonnegative coefficients. This is easily seen to be false. For example, in W = S_{4} we have that

R_{1234,4321}(q) − G̃_{S_{4}}(q) = −q^{2} + 2q^{3} − q^{4}.  (39)

However, it would be interesting to know if G_{[u,v]}(q) − ε_{u}ε_{v}R_{u,v}(−q) has always nonnegative coefficients. Or, in other words, if R_{u,v}(q) − G̃_{[u,v]}(q) has alternating coefficients for all u, v ∈ W.

Corollary 5.5 also suggests that the Kazhdan-Lusztig polynomials somehow “measure” the difference between the R-polynomials and the rank generating functions. While we have been unable to find analogues of (35) and (36) for [q^{k}](P_{u,v}) when k ≥ 3, we can prove the following result which strengthens the feeling just mentioned.

Proposition 5.6 Let u, v ∈ W, u ≤ v. Then the following are equivalent:

i) P_{x,y}(q) = 1 for all u ≤ x ≤ y ≤ v;

ii) R_{x,y}(q) = G̃_{[x,y]}(q) for all u ≤ x ≤ y ≤ v.

Proof. Assume first that ii) holds. Then we have that, for all u ≤ x ≤ y ≤ v,

∑_{x≤b≤y} R_{x,b}(q) = ∑_{x≤b≤y} ε_{b}ε_{x} ∑_{x≤a≤b}(−q)^{l(a)−l(x)}
= ∑_{x≤a≤b≤y} ε_{b}ε_{a}q^{l(a)−l(x)}
= ∑_{x≤a≤y} q^{l(a)−l(x)} ∑_{a≤b≤y} ε_{b}ε_{a}
= ∑_{x≤a≤y} q^{l(a)−l(x)}δ_{a,y} = q^{l(y)−l(x)} ,

where we have used a well known property of Bruhat order (see, e.g., [12], Corollary 7.13), and i) follows from Lemma 2.6 of [14].

Conversely, assume that i) holds. We will prove ii) by induction on l(z) − l(w). Then from i), (8), and our induction hypothesis we obtain that

R_{x,y}(q) = q^{l(y)−l(x)} − ∑_{x≤a<y} G̃_{[x,a]}(q)
= q^{l(y)−l(x)} − ∑_{x≤b≤a<y} ε_{a}ε_{x}(−q)^{l(b)−l(x)}
= q^{l(y)−l(x)} − ∑_{x≤b<y} q^{l(b)−l(x)} ∑_{b≤a<y} ε_{a}ε_{b}
= q^{l(y)−l(x)} + ∑_{x≤b<y} q^{l(b)−l(x)} ε_{b}ε_{y}
= G̃_{[x,y]}(q),

as desired. □

It would be interesting to know how much the preceding result can be refined or “localized”. While it is clearly false that P_{u,v}(q) = 1 is equivalent to R_{u,v}(q) = G̃_{[u,v]}(q) (for example, P_{1234,4321}(q) = 1 but R_{1234,4321}(q) ≠ G̃_{S_{4}}(q), as seen in (39)), it is conceivable that some refinements of Proposition 5.6 hold.

We now derive some consequences of Corollary 5.3.

Corollary 5.7 Let σ ∈ S_{n}, and t ∈ T. Then

[q](P_{σ,σt}(q)) = c(σ, σt) − \frac{1}{2}(l(σt) − l(σ) + 1) .

Proof. It follows from Theorem 4.6 of [3] that

R_{σ,σt}(q) = (q − 1)(q^{2} − q + 1)^{\frac{1}{2} (l(σt)−l(σ)−1)} ,

and the thesis follows from Corollary 5.3. □

It would be interesting to know if the preceding result holds for any Coxeter group.

Another consequence of Corollary 5.3 is the following result which was conjectured by G. Kalai, [13].

Corollary 5.8 Let u, v ∈ W be such that P_{u,v}(q) = 1. Then

l(v) − l(u) ≥ c(u, v) .

Proof. It follows easily from (4) that

R_{u,v}(q) = ∑_{i=0}^{⌊ \frac{d}{2} ⌋} a_{i}(q − 1)^{d−2i} q^{i}

where d =^{def} l(v) − l(u), a_{0} = 1, and a_{i} ∈ N, for i = 1, …, ⌊\frac{d}{2}⌋. Therefore

(−1)^{d} [q](R_{u,v}(q)) = a_{1} − d ≥ −d

and the thesis follows from our hypotheses and Corollary 5.3 .□

A further application of Corollary 5.3 is the following result which was first proved by Dyer (see [7]). Corollary 5.9 Let v ∈ W. Then

[q](P_{e,v}(q)) = c(e, v) − a(e, v) .  (40)

Proof. We will show that

[q](R_{e,v}(q)) = (−1)^{l(v)−1} a(e, v) ,  (41)

for all v ∈ W, and the thesis will then follow from Corollary 5.3. We prove (41) by induction on l(v), the case v = e being clear. So assume that l(v) ≥ 1 and fix a reduced decomposition s_{i_{1}} … s_{i_{r}} of v. Let s =^{def} s_{i_{r}} so that s_{i_{1}} … s_{i_{r−1}} is a reduced decomposition of v s. From the subword property (see, e.g., [12], Theorem 5.10, p.120) we deduce that

a(e, v) = |{s ∈ S : s = s_{i_{j}} for some j ∈ [r]}|

and

a(e, v s) = |{s ∈ S : s = s_{i_{j}} for some j ∈ [r − 1]}| .

Therefore, again by the subword property, we have that

a(e, v) = \{ \begin{matrix}a(e, v s), & if s ≤ v s, \\ a(e, v s) + 1, & otherwise. \end{matrix}

Hence, using our induction hypothesis, we conclude that

a(e, v) = a(e, v s) + 1 + ε_{vs} [q^{0}](R_{s,v s}(q))
= −ε_{vs}([q](R_{e,v s}(q)) − [q^{0}](R_{s,v s}(q)) − [q^{0}](R_{e,v s}(q)))
= −ε_{v}[q](R_{e,v}(q)) ,

by (4), and this concludes the induction step and hence the proof. □

Note that (40) does not hold in general. For example, if W = S_{4}, u = 2143, and v = 4231 then [q](P_{u,v}) = 1 but c(u, v) = 4 and a(u, v) = 4.

6 Kazhdan-Lusztig polynomials and generalized

h-vectors

In this section we use Corollary 5.3 to characterize those pairs of elements u, v ∈ W such that P_{u,v}(q) equals the g-polynomial of [u, v]^{∗}. Our characterization is purely combinatorial and depends only on the isomorphism type of the poset [u, v]. As a consequence of this characterization, and of Theorem 5.2, we obtain an explicit combinatorial formula expressing the Kazhdan-Lusztig polynomial of any interval which is a lattice solely in terms of its combinatorial structure.

One of the crucial ingredients in our proof is the following simple result about the polynomials Q_{u,v}(q), defined by (6). The result follows also from Proposition 5.3 of [5], however, since our proof is simpler, we present it here for the reader’s convenience. We say that a polynomial ∑_{i≥0} a_{i}q^{i} has no internal zeros if there are not three indices i < j < k such that a_{i}, a_{k} ≠ 0 and a_{j} = 0.

Proposition 6.1 Let u, v ∈ W. Then the polynomial Q_{u,v}(q) has no internal zeros.

Proof. We may clearly assume that u ≤ v. We proceed by induction on l(v), the thesis being clear if l(v) = 0. So assume that l(v) ≥ 1 and let s ∈ D(v). From (4) and (5) we then conclude that

R̃_{u,v}(q) = \{ \begin{matrix}R̃_{us,vs}(q), & if s ∈ D(u), \\ R̃_{us,vs}(q) + qR̃_{u,vs}(q), & if s ∉ D(u). \end{matrix}

This, in turn, by (6) implies that

Q_{u,v}(q) = \{ \begin{matrix}Q_{us,vs}(q), & if s ∈ D(u), \\ Q_{us,vs}(q) + q Q_{u,vs}(q), & if s ∉ D(u), and l(u) ≡ l(v) (2), \\ Q_{us,vs}(q) + Q_{u,vs}(q), & otherwise. \end{matrix}  (42)

By our induction hypotheses both Q_{us,vs}(q) and Q_{u,vs}(q) have no internal zeros, so the thesis follows from (42) and the fact that deg(Q_{u,v}(q)) = ⌊\frac{1}{2}(l(v)−l(u))⌋ if u ≤ v while Q_{u,v}(q) = 0 if u ≰ v. □

The next result follows easily from (the proof of) Proposition 3.3 of [9] and the fact (see, e.g., [2], (4.7)) that every interval of length 3 of a Coxeter system is isomorphic to either S_{3}, or C_{n} for some n ≥ 3 (where C_{n} denotes the lattice of faces of an n-gon), and its proof is omitted. Note that (as pointed out to me by M. Dyer) the word “finite” should be erased from p. 185, l.-3, of [9].

Lemma 6.2 Let u, v ∈ W, u ≤ v, be such that l(v) − l(u) = 3. Then the following are equivalent:

i) [u, v] ≅ S_{3};

ii) vu^{−1} ∈ T. □

We can now prove the main result of this section, which greatly generalizes Theorem 4.8 of [3].

Theorem 6.3 Let u, v ∈ W, u ≤ v. Then the following are equivalent:

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

ii) R_{u,v}(q) = (q − 1)^{l(v)−l(u)};

iii) [q](R_{u,v}(q)) = (−1)^{l(v)−l(u)}(l(u) − l(v));

iv) [q](P_{u,v}(q)) = c(u, v) − l(v) + l(u);

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

Proof. We will prove first that i) ⇔ ii) and then use this fact to show that v) ⇒ iv) ⇒ iii) ⇒ ii) ⇒ v). Let d =^{def} l(v) − l(u), for brevity.

i) ⇔ ii). Assume first that ii) does not hold. Then there exists m ∈ [d − 1] such that [q^{m}](R̃_{u,v}(q)) > 0. Therefore m < d − 1 and hence, by Proposition 6.1, [q^{d−2}](R̃_{u,v}(q)) > 0. By Proposition 2.4 this implies that there is a directed path (u = a_{0} → a_{1} → … → a_{d−2} = v) in B(W, S) from u to v of length d − 2. Since l(a_{i}) − l(a_{i−1}) is odd for all i = 1, …, d − 2 we conclude that there exists j ∈ [d − 2] such that l(a_{j}) − l(a_{j−1}) = 3. By the definition of B(W, S) and Lemma 6.2 this implies that [a_{j−1}, a_{j}] ≅ S_{3}, which contradicts i).

Conversely, assume that i) does not hold. Then there exist x, y ∈ [u, v] such that [x, y] ≅ S_{3}. By Lemma 6.2 this implies that x → y in B(W, S). On the other hand, since u ≤ x < y ≤ v, there exist directed paths in B(W, S) from u to x and from y to v of lengths l(x) − l(u) and l(v) − l(y), respectively. Hence there is a directed path in B(W, S) from u to v of length l(x) − l(u) + 1 + l(v) − l(y) = d − 2 and this, by Proposition 2.4, implies that [q^{d−2}](R̃_{u,v}(q)) > 0 and hence that ii) does not hold.

v) ⇒ iv). This follows immediately from (1), (2) and the generalized Dehn-Sommerville equations (see, e.g., [18], Theorem 2.4, or [17], Theorem 3.14.9, p. 139). iv) ⇒ iii). This follows immediately from Corollary 5.3. iii) ⇒ ii). It follows from (5) and (6) that

(−1)^{l(v)−l(u)}[q](R_{u,v}(q)) = [q^{l(v)−l(u)−2}](R̃_{u,v}(q)) − l(v) + l(u) .

Comparing this with iii) yields that

[q^{l(v)−l(u)−2}](R̃_{u,v}(q)) = 0 .

This, by (6) and Proposition 6.1, implies that [q^{m}](R̃_{u,v}(q)) = 0 for all m < d, and hence that R̃_{u,v}(q) = q^{l(v)−l(u)} which, by (5), implies ii). ii) ⇒ v). Since i) is equivalent with ii) we conclude from ii) that R_{x,y}(q) = (q − 1)^{l(y)−l(x)} for all u ≤ x ≤ y ≤ v. Now we proceed by induction on l(v) − l(u), the thesis being clearly true if v = u. Then, using part iv) of Theorem 2.6 and our induction hypothesis we obtain that

q^{d}P_{u,v} (\frac{1}{q}) − P_{u,v}(q) = ∑_{u<a≤v} R_{u,a}(q) P_{a,v}(q)
= ∑_{u<a≤v}(q − 1)^{l(a)−l(u)} g([a, v]^{∗}, q)
= (q − 1)f([u, v]^{∗}; q) ,  (43)

by (2). Since, by part iii) of Theorem 2.6, deg(P_{u,v}(q)) ≤ ⌊\frac{1}{2}(d − 1)⌋, equating the coefficients of q^{i}, for i = 0, …, ⌊\frac{1}{2}(d − 1)⌋, on both sides of (43) yields, by (1), that

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

as desired. □

The preceding theorem has many consequences. The main one is probably the following which is obtained by combining Theorems 6.3 and 5.2, and which gives, in particular, an explicit formula for the Kazhdan-Lusztig polynomial of any interval [u, v] which is a lattice.

Theorem 6.4 Let u, v ∈ W, u ≤ v, be such that [u, v] does not contain any interval isomorphic to S_{3}. Then

[q^{k}](P_{u,v}(q)) = ∑_{S⊆[k]}(−1)^{l(v)−|S|+k} ∑_{(a_{0},...,a_{|S|+1})∈C_{S}(u,v)}(−1)^{∑_{i=1}^{|S|} l(a_{i})} ∏_{r=0}^{|S|} (\begin{matrix}l(a_{r+1})−l(a_{r}) \\ l(v)−l(a_{r})−S_{r}−S_{r+1} \end{matrix} )

where C_{S}(u, v), and S_{0}, have the same meaning as in Theorem 5.2. □

Another consequence of Theorem 6.3 is the following result which was first proved, in the case of symmetric groups, by M. Haiman and G. Kalai ([11]). Corollary 6.5 Let u, v ∈ W, u ≤ v, be such that [u, v] is a lattice. Then R_{u,v}(q) = (q − 1)^{l(v)−l(u)}. □ Two further non-trivial consequences of Theorem 6.3 are the following. Corollary 6.6 Let u, v ∈ W, u ≤ v, be such that [q](R_{u,v}(q)) = (−1)^{l(v)−l(u)}(l(u) − l(v)). Then R_{x,y}(q) = (q − 1)^{l(y)−l(x)} for all u ≤ x ≤ y ≤ v. □

Corollary 6.7 Let u, v ∈ W, u ≤ v, be such that [q](P_{u,v}(q)) = c(u, v) − l(v) + l(u). Then P_{x,y}(q) = g([x, y]^{∗}; q) for all u ≤ x ≤ y ≤ v. □

Theorem 6.3 also enables us to use results from the theory of g-polynomials to compute explicitly the Kazhdan-Lusztig polynomials of some classes of intervals. For n ∈ N we denote by B_{n} and Q_{n} the Boolean algebra of rank n and the face lattice of an n-dimensional cube, respectively. Corollary 6.8 Let u, v ∈ W, u ≤ v, be such that [u, v] ≅ B_{l(v)−l(u)} (as posets). Then

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

Proof. This follows immediately from Theorem 6.3 and the well known fact that g(B_{d}; q) = 1 for all d ∈ N (see, e.g., [18], Proposition 2.1, or [17], Example 3.14.8). □ Corollary 6.9 Let u, v ∈ W, u ≤ v, 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} .  (44)

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}⌋. Proof. (44) follows immediately from Theorem 6.3 and Proposition 2.6 of [18] (see also [17], Chapter 3, Exercise 71(f)). The second statement was first proved by L. Shapiro (unpublished, see also [17], Chapter 3, Exercise 71(g)). □

Let k ∈ N. Recall (see, e.g., [18], p.191) that a finite graded poset P with ˆ0 is said to be k-simplicial if [ˆ0, x] is isomorphic to a Boolean algebra for all x ∈ P_{k}. It is well known (see, e.g., [2]) that intervals of W, and their duals, are 2-simplicial.

For brevity, we say that an interval [u, v] is S_{3}-free if it satisfies condition i) of Theorem 6.3.

Proposition 6.10 Let u, v ∈ W, u ≤ v, and k ∈ N. Suppose that [u, v]^{∗} is ksimplicial and S_{3}-free. Then

[q^{j}](P_{u,v}(q)) = ∑_{i=0}^{j}(−1)^{i−j} (\begin{matrix}l(v)−l(u)−i \\ l(v)−l(u)−j \end{matrix} ) |[u, v]_{i}^{∗}|

for j = 0, …, ⌊\frac{k+1}{2}⌋.

Proof. It is well known (see, e.g., [1], Corollary 5.2, or [20]) that intervals of W are Eulerian and that W^{∗} ≅ W (as posets). Therefore [u, v]^{∗} is an Eulerian poset. Since [u, v]^{∗} is k-simplicial this implies, by Corollary 2.3 of [18], that

[q^{j}](f([u, v]^{∗}, q)) = [q^{d−j}] (∑_{i=0}^{d} r_{i}(q − 1)^{d−i}) = ∑_{i=0}^{j} (\begin{matrix}d−i \\ d−j \end{matrix} ) (−1)^{j−i}r_{i}

for 0 ≤ j ≤ ⌊\frac{k+1}{2}⌋, where r_{i} =^{def} |[u, v]_{i}^{∗}| for i ∈ N, and d =^{def} l(v) − l(u) − 1. Therefore we conclude from (1) that

[q^{j}](g([u, v]^{∗}; q)) = [q^{j}](f([u, v]^{∗}; q)) − [q^{j−1}](f([u, v]^{∗}; q)
= ∑_{i=0}^{j}(−1)^{j−i}r_{i} ((\begin{matrix}d−i \\ d−j \end{matrix} ) + (\begin{matrix}d−i \\ d−j+1 \end{matrix}))
= ∑_{i=0}^{j}(−1)^{j−i}r_{i} (\begin{matrix}d−i+1 \\ d−j+1 \end{matrix})  (45)

for 0 ≤ j ≤ ⌊\frac{k+1}{2}⌋. Since, by our hypotheses, [u, v] does not contain any interval isomorphic to S_{3}, the thesis follows from (45) and Theorem 6.3. □

For k = 3 we can also prove the converse of Proposition 6.10.

Proposition 6.11 Let u, v ∈ W, u ≤ v. Then the following are equivalent:

i) [q^{j}](P_{u,v}(q)) = ∑_{i=0}^{j}(−1)^{i−j} (\begin{matrix}l(v)−l(u)−i \\ l(v)−l(u)−j \end{matrix} ) |[u, v]_{i}^{∗}|, for j ≤ 2;

ii) [u, v]^{∗} is S_{3}-free and 3-simplicial.

Proof. We have already proved that ii) implies i) (see Proposition 6.10). So suppose that i) holds and let, for brevity, d =^{def} l(v) − l(u). Then

[q^{2}](P_{u,v}(q)) = (\begin{matrix}d \\ 2 \end{matrix}) − |[u, v]_{1}^{∗}|(d − 1) + |[u, v]_{2}^{∗}|,  (46)

and, by Theorem 6.3, [u, v] is S_{3}-free. Now, by (1), (2) and the generalized Dehn-Sommerville equations (see, e.g., [18], Theorem 2.4, or [17], Theorem 3.14.9, p. 139) we have that

[q^{2}](g([u, v]^{∗}; q)) = (\begin{matrix}d \\ 2 \end{matrix}) − (d − 1)|[u, v]_{1}^{∗}| + |[u, v]_{2}^{∗}| + ∑_{a∈[u,v]_{3}^{∗}}[q](g([a, v]^{∗}; q) . (47)

Comparing (46) and (47) yields, by Theorem 6.3, that

∑_{a∈[u,v]_{3}^{∗}}[q](g([a, v]^{∗}; q)) = 0 .  (48)

But it is known (see [2], (4.7)) that every interval of length 3 of a Coxeter group is isomorphic to either S_{3}, or C_{n} for some n ≥ 3. On the other hand, it is easy to see from the definitions (1), and (2), that g(C_{n}; q) = 1 + (n − 3)q, for n ≥ 3. Since [u, v] is S_{3}-free we conclude from (48) that every upper interval of length 3 in [u, v] is isomorphic to C_{3}, which proves ii). □

7 Inverse Kazhdan-Lusztig polynomials

In this section we briefly outline how to obtain analogues of all the results in this work for the inverse Kazhdan-Lusztig polynomials. Recall (see, e.g., [12], §7.13, or [15], p.190) that these are the polynomials {P_{u,v}^{∗}(q)}_{u,v∈W} uniquely defined by the condition that

∑_{u≤a≤v}(−1)^{l(a)−l(u)} P_{u,a}(q) P_{a,v}^{∗}(q) = δ_{u,v}  (49)

for all u, v ∈ W, u ≤ v. The next (well known) result follows easily from (49), (7), and Theorem 2.6.

Theorem 7.1 For u, v ∈ W we have that:

i) P_{u,u}^{∗} = 1;

ii) deg (P_{u,v}^{∗}(q)) ≤ ⌊\frac{1}{2}(l(v) − l(u) − 1)⌋ if u < v;

iii)

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

if u ≤ v. □

For any multichain a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} (r ∈ N) of W we define a polynomial R_{a_{0},...,a_{r+1}}^{∗}(q) as follows. We let

R_{a_{0},...,a_{r+1}}^{∗}(q) =^{def} U_{⌈ \frac{d+1}{2} ⌉} (q^{d}R_{a_{0},...,a_{r}}^{∗} (\frac{1}{q})) R_{a_{r},a_{r+1}}^{∗}(q)  (50)

(where d =^{def} l(a_{r}) − l(a_{0})), if r ∈ P, and

R_{a_{0},...,a_{r+1}}^{∗}(q) =^{def} (−1)^{l(a_{r+1})−l(a_{r})} R_{a_{r},a_{r+1}}(q),  (51)

if r = 0. We call the polynomial R_{a_{0},...,a_{r+1}}^{∗}(q) the dual R-polynomial of the multichain a_{0} ≤ a_{1} ≤ … ≤ a_{r+1}.

In the case that (W, S) is a finite Coxeter system there is a simple relation between R-polynomials and dual R-polynomials of multichains. The next result follows easily from the definitions (50), (51), (10), (11), and Proposition 7.6 of [12].

Proposition 7.2 Let (W, S) be a finite Coxeter system, and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} be a multichain in W. Then

R_{a_{0},...,a_{r+1}}^{∗}(q) = R_{ω_{0}a_{r+1},...,ω_{0}a_{0}}(q) .□

All of the results in section 3 are easily seen to have obvious analogues for the dual R-polynomials. We state here two such results as an example. Let m^{∗}(a_{0}, … a_{r+1}) denote the maximum power of q that divides R_{a_{0},...,a_{r+1}}^{∗}(q).

Proposition 7.3 Let r ∈ P and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} be a multichain in W such that R_{a_{0},...,a_{r+1}}^{∗} ≠ 0. Then

deg (R_{a_{0},...,a_{r+1}}^{∗}) = l(a_{r+1}) − l(a_{0}) − m^{∗}(a_{0}, …, a_{r}) ,

and

m^{∗}(a_{0}, … a_{r+1}) ≥ ⌈\frac{1}{2}(l(a_{r}) − l(a_{0}) + 1)⌉ .

In particular

deg (R_{a_{0},...,a_{r+1}}^{∗}) ≤ l(a_{r+1}) − l(a_{r−1}) + ⌊\frac{1}{2}(l(a_{r−1}) − l(a_{0}) − 1)⌋ .□

Proposition 7.4 Let r ∈ P and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} be a multichain in W such that R_{a_{0},...,a_{r+1}}^{∗} ≠ 0. Then l(a_{1})−l(a_{0}) ≥ 1, and l(a_{i+1})−l(a_{i}) ≥ 2 for i = 1, …, r−1. In particular l(a_{r}) − l(a_{0}) ≥ 2r − 1. □

All of the results in sections 4, 5, and 6 have obvious analogues for the inverse Kazhdan-Lusztig polynomials. We state below four of them as examples.

Theorem 7.5 Let u, v ∈ W. Then

P_{u,v}^{∗}(q) = ∑_{C∈C(u,v)} R_{C}^{∗}(q) .□

Theorem 7.6 Let u, v ∈ W, and k ∈ N. Then

[q^{k}](P_{u,v}^{∗}) = ∑_{S⊆[k]} ∑_{(a_{0},...,a_{|S|+1})∈C_{S}([u,v]^{∗})} ∏_{i=0}^{|S|}[q^{S_{i}+S_{i+1}−l(a_{i+1})+l(u)}](R_{a_{i+1},a_{i}})

where C_{S}([u, v]^{∗}) is the set of all multichains a_{|S|+1} ≤ a_{|S|} ≤ … ≤ a_{0} from u to v such that S_{r+1} ≤ l(a_{r}) − l(u) − S_{r} ≤ S_{r} − 1, for r = 1, …, |S|, and where

S_{0} =^{def} l(v) − l(u) − k. □

Corollary 7.7 Let u, v ∈ W. Then

[q](P_{u,v}^{∗}(q)) = (−1)^{l(v)−l(u)} [q](R_{u,v}) + a(u, v),

where a(u, v) is the number of atoms in [u, v]. □

Theorem 7.8 Let u, v ∈ W, u ≤ v. Then the following are equivalent:

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

ii) R_{u,v}(q) = (q − 1)^{l(v)−l(u)};

iii) [q](R_{u,v}(q)) = (−1)^{l(v)−l(u)}(l(u) − l(v));

iv) [q](P_{u,v}^{∗}(q)) = a(u, v) − l(v) + l(u);

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

Note that Theorems 4.1, 7.5, and Proposition 7.2 give a particularly transparent proof of the well known result (see, e.g., [12], Proposition 7.13) that, if (W, S) is a finite Coxeter system, then P_{u,v}^{∗}(q) = P_{ω_{0}v,ω_{0}u}(q) for all u, v ∈ W. Acknowledgements. I would like to thank Anders Björner, Matthew Dyer, Mark Haiman, and Gil Kalai for some useful suggestions and conversations. I would also like to thank the Institute of Mathematics of the Hebrew University of Jerusalem for hospitality and financial support during the preparation of part of this work.

References

[1] A. Björner, M. Wachs, Bruhat order of Coxeter groups and shellability, Adv. in Math. 43 (1982), 87-100.

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

[3] F. Brenti, Combinatorial properties of the Kazhdan-Lusztig R-polynomials for S_{n}, Adv. in Math., to appear.

[4] K. J. Carlin, Extensions of Verma modules, Ph. D. Thesis, Yale University, 1983.

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

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

[7] M. Dyer, Hecke algebras and reflections in Coxeter groups, Ph. D. Thesis, University of Sydney, 1987.

[8] M. Dyer, On some generalisations of the Kazhdan-Lusztig polynomials for “universal” Coxeter systems, J. Algebra, 116 (1988), 353-371.

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

[10] M. Dyer, Hecke algebras and shellings of Bruhat intervals, Comp. Math., to appear.

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

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

[13] G. Kalai, private communication, September 1992.

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

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

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

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

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

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

[20] D.-N. Verma, Möbius inversion for the Bruhat order on a Weyl group, Ann. Sci. École Norm. Sup. 4 (1971), 393-398.

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

Dipartimento di Matematica, Universitá di Perugia Via Vanvitelli 1, I-06123 Perugia, Italy