Combinatorial Expansions of Kazhdan-Lusztig polynomials

Francesco Brenti^{1}

Abstract

We introduce two, related, families of polynomials, easily computable by simple recursions into which any Kazhdan-Lusztig (and inverse Kazhdan-Lusztig) polynomial of any Coxeter group can be expanded linearly, and we give combinatorial interpretations to the coefficients in these expansions. This yields a combinatorial rule for computing the Kazhdan-Lusztig polynomials in terms of paths in a directed graph, and a completely combinatorial reformulation of the nonnegativity conjecture ([15], p. 166).

1 Introduction

In their fundamental paper [15] 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., [14], Chap. 7). These polynomials are intimately related to the Bruhat order of W and to the algebraic geometry of Schubert varieties, and are of fundamental importance in representation theory.

Our goal in this paper is to introduce two families of polynomials into which any Kazhdan-Lusztig polynomial can be expanded linearly and to give a combinatorial interpretation to the coefficients in these expansions. Our families are independent of the Coxeter group and can be computed (and/or defined) through simple recurrence relations. As a consequence of our results we obtain a combinatorial rule for computing the Kazhdan-Lusztig polynomials of any Coxeter group in terms of paths in a labeled directed graph. Also, since all the polynomials in our families have alternating coefficients (see Theorems 3.10, and 3.14), we obtain a completely combinatorial reformulation (see Theorem 4.8) of the nonnegativity conjecture for Kazhdan-Lusztig polynomials (see, e.g., [14], §7.9, p. 159). Though combinatorial formulas for Kazhdan-Lusztig polynomials have appeared before in the literature (see, e.g., [5], [9], [10], [17], [22]) none of them are as general and/or explicit as the ones presented here.

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

Part of this work was carried out while the author was visiting the Institute of Mathematics, Royal Institute of Technology, Stockholm, Sweden.

The organization of the paper is as follows. In the next section we collect several notation, definition, and results, that will be used in the rest of this work. In section 3 we define the families of polynomials that we need for our main result, we derive simple recursions for them (see Propositions 3.2 and 3.5, and Theorem 3.4) and prove some of their fundamental properties (see Theorems 3.7, 3.10, 3.14, and 3.15). In section 4 we prove our main result (Theorem 4.5) and give some applications of it. Namely, we express any Kazhdan-Lusztig polynomial of any Coxeter group as a linear combination of the polynomials introduced in section 3, and give a combinatorial interpretation to the coefficients in these linear expansions. We then derive a combinatorial rule to compute any Kazhdan-Lusztig polynomial (see Corollary 4.6), and we obtain a completely combinatorial reformulation of the nonnegativity conjecture for Kazhdan-Lusztig polynomials (see, e.g., [14], §7.9, p.

159) in terms of the enumeration of paths in a certain labeled directed graph (see Theorem 4.8). In section 5 we study the coefficients that appear in the linear expansions obtained in section 4. Our main result is an inequality for them (Theorem 5.7) which is equivalent to a “monotonicity” property for the R̃-polynomials (see Proposition 2.4 and Theorem 5.4) that is interesting in its own right. Finally, in section 6, we briefly sketch how it is possible to obtain analogues of our main results for the inverse Kazhdan-Lusztig polynomials.

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}, 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], and we define similarly (n, m], and [n, m). For S ⊆ Q 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|, and we let P(A) be the power set of A. Given a polynomial P (q), and i ∈ Z, we denote by [q^{i}](P (q)) the coefficient of q^{i} in P (q). For a ∈ Q we let ⌊a⌋ (respectively, ⌈a⌉) denote the largest integer ≤ a (respectively, smallest integer ≥ a).

A sequence {a_{0}, a_{1}, …, a_{d}} (of real numbers) is called log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for i = 1, …, d − 1. It is said to be unimodal if there exists an index 0 ≤ j ≤ d such that a_{i} ≤ a_{i+1} for i = 0, …, j −1 and a_{i} ≥ a_{i+1} for i = j, …, d−1. It is said to have no internal zeros if there are not three indices 0 ≤ i < j < k ≤ d such that a_{i}, a_{k} ≠ 0 and a_{j} = 0. It is said to be symmetric if a_{i} = a_{d−i} for i = 0, …, ⌊\frac{d}{2}⌋. We say that a polynomial ∑_{i=0}^{d} a_{i} x^{i} is log-concave (respectively, unimodal, with no internal zeros, symmetric) if the sequence {a_{0}, a_{1}, …, a_{d}} has the corresponding property. It is well known that if ∑_{i=0}^{d} a_{i} t^{i} is a polynomial with nonnegative coefficients and with only real zeros, then the sequence {a_{0}, a_{1}, …, a_{d}} is log-concave and unimodal, with no internal zeros (see, e.g., [6], Thm. B, p.270). If p(x) is a symmetric unimodal polynomial then there is a unique n ∈ N such that x^{n} p (\frac{1}{x}) = p (x). We call the number \frac{n}{2} the center of symmetry of p (x) (or of the corresponding sequence). We denote by P F_{2} the class of all polynomials with real nonnegative coefficients that are log-concave and have no internal zeros (we refer the reader to [4], Proposition 2.5.1, p. 21, for the reason behind this apparently strange notation).

Recall that a composition of n (n ∈ P) is a sequence (α_{1}, …, α_{s}) (for some s ∈ P) of positive integers such that α_{1} + … + α_{s} = n (see, e.g., [18], p. 14). When writing compositions we will sometimes omit to write the parentheses (i.e., we will write α_{1}, …, α_{s} instead of (α_{1}, …, α_{s})). Thus if α = (α_{1}, …, α_{s}) and β = (β_{1}, …, β_{t}) are compositions then α, β is to be interpreted as the composition (α_{1}, …, α_{s}, β_{1}, …, β_{t}). For n ∈ P we let C_{n} be the set of all compositions of n and

C =^{def} ⋃_{n≥1} C_{n}. Given (α_{1}, ..., α_{s}), (β_{1}, ..., β_{t}) ∈ C_{n} we say that (α_{1}, ..., α_{s}) refines

(β_{1}, ..., β_{t}) if there exist 1 ≤ i_{1} < i_{2} < … < i_{t−1} ≤ s such that ∑_{j=i_{k−1}+1}^{i_{k}} α_{j} = β_{k} for k = 1, …, t (where i_{0} =^{def} 0 , i_{t} =^{def} s). We then write (α_{1}, ..., α_{s}) ⪯ (β_{1}, ..., β_{t}). It is well known, and easy to see, that the map (α_{1}, …, α_{s}) ↦ {α_{1}, α_{1} + α_{2}, …, α_{1} + α_{2} + … + α_{s−1}} is an isomorphism from (C_{n}, ≤) to the Boolean algebra B_{n−1} of subsets of [n − 1], ordered by reverse inclusion (see, e.g., [18], p.14), and we will use this identification freely in what follows. Given β ∈ C we denote by l(β) the number of parts of β, by β_{i}, for i = 1, …, l(β), the i-th part of β, (so that

β = (β_{1}, β_{2}, …, β_{l(β)})), and we let |β| =^{def} ∑_{i=1}^{l(β)} β_{i}, and \overline{β} =^{def} (β_{2}, β_{3}, …, β_{l(β)}) (if

l(β) ≥ 2). Given i ∈ P such that i ≤ β_{1} we let β^{(i)} =^{def} (β_{1} − i, β_{2}, …, β_{l(β)}) (where

β^{(i)} =^{def} \overline{β} if β_{1} = i).

We let L be the real vector space of all Laurent polynomials in q with real coefficients. For j ∈ Q and k ∈ Z we define operators E, U_{j}, D_{j}, J_{k} : L → L as follows

E(∑_{i∈Z} a_{i}q^{i}) =^{def} ∑_{i∈Z} a_{i}q^{i+1},

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

D_{j}(∑_{i∈Z} a_{i}q^{i}) =^{def} ∑_{i≤j} a_{i}q^{i},

J_{k}(∑_{i∈Z} a_{i}q^{i}) =^{def} ∑_{i∈Z} a_{i}q^{k−i}.

Note that E, U_{j}, D_{j}, J_{k} are linear, that U_{j} and D_{j} are idempotent, that J_{k} is an involution, and that D_{j} = D_{⌊j⌋} and U_{j} = U_{⌈j⌉}, for all j ∈ Q and k ∈ Z. Since we will use these operators very often, it is useful to know what relations hold among them. The following result (whose verification is left to the reader) lists some of the most important ones. We denote by 0 and I the zero and identity operators, respectively, on L. Proposition 2.1 Let i, j ∈ Q and k ∈ Z. Then we have that:

i) U_{i}D_{j} = D_{j}U_{i} = 0 if i > j; ii) U_{i}J_{k} = J_{k}D_{k−i}; iii) J_{k}U_{i} = D_{k−i}J_{k}; iv) J_{k}E = J_{k−1};

v) EJ_{k} = J_{k+1}; vi) EU_{j} = U_{j+1}E; vii) ED_{j} = D_{j+1}E. □

We will follow [18], 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, α(P; S) be the number of maximal chains of P_{S}, and

β(P; S) =^{def} ∑_{T ⊆S}(−1)^{|S\T |}α(P; T) .  (1)

We also let P_{i} =^{def} P_{{i}} if i ∈ N.

We will follow [14] 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 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., [14], §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 use notation such as [u, v]_{S} or [u, v]_{i} (S ⊆ N, i ∈ N) to denote the rank-selected subposets of [u, v].

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

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

Recall (see, [14], §8.6, or, [12]) 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., [14], 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}  (2)

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, [14], Proposition 7.4).

Proposition 2.2 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 (2) and Proposition 2.2 (see [14], §7.5).

Theorem 2.3 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}(q), & if s ∉ D(u). \end{matrix}  (3)

Theorem 2.3 has also the following simple consequence.

Proposition 2.4 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}} ) .  (4)

Several combinatorial interpretations are known for the polynomials R̃_{u,v}(q) (see [7], and [13]). We now recall the one that we will use in this work.

Let A ⊆ T and W′ be the subgroup of W generated by A. Following [14], §8.2 we call W′ a reflection subgroup of W. It is then known (see [14], Theorem 8.2, or [11], or [8]) that (W′, S′) is again a Coxeter system where S′ =^{def} {t ∈ T : N(t) ∩ W′ = {t}}, and N(w) =^{def} {t ∈ T : l(wt) < l(w)}. We say that W′ is a dihedral reflection subgroup if |S′| = 2 (i.e., if (W′, S′) is a dihedral Coxeter system). Following [13] we say that a total ordering <_{T} of T is a reflection ordering if, for any dihedral reflection subgroup W′ of W, we have that either a <_{T} aba <_{T} ababa <_{T} … <_{T} babab <_{T} bab <_{T} b or b <_{T} bab <_{T} babab <_{T} … <_{T} ababa <_{T} aba <_{T} a where {a, b} =^{def} S′. The existence of reflection orderings (and many of their properties) is proved in [13], §2.

In the case of finite Coxeter systems there is a simple description of all the reflection orderings of T, given by the following result (we refer the reader to [13], Proposition (2.13), for its proof).

Theorem 2.5 Let (W, S) be a finite Coxeter system, w_{0} be its longest element, and s_{1} … s_{r} = w_{0} be a reduced expression of w_{0}. Then s_{r} <_{T} s_{r}s_{r−1}s_{r} <_{T} s_{r}s_{r−1}s_{r−2}s_{r−1}s_{r} <_{T} … <_{T} s_{r}s_{r−1} … s_{1} … s_{r−1}s_{r} is a reflection ordering and any reflection ordering arises in this way.

Given a path Γ = (a_{0}, a_{1}, …, a_{r}) in the Bruhat graph of W we define its descent set, with respect to <_{T}, to be

D(a_{0}, a_{1}, …, a_{r}) =^{def} {i ∈ [r − 1] : a_{i}(a_{i−1})^{−1} >_{T} a_{i+1}(a_{i})^{−1}} ,

and its length to be l(Γ) =^{def} r. Given u, v ∈ W we denote by B(u, v) the set of all directed paths in B(W, S) from u to v.

We then have the following result (we refer the reader to [13], Corollary 3.4 , for its proof).

Theorem 2.6 Let u, v ∈ W. Then

R̃_{u,v}(q) = ∑_{{Γ∈B(u,v): D(Γ)=∅}} q^{l(Γ)}.□

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 [20], Corollary 6.7 and Example 6.9) and a proof can be found, e.g., in [14], §§7.9-11, or [15], §2.2.

Theorem 2.7 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) ,  (5)
if u ≤ v.

The polynomials P_{u,v}(q) defined by the preceding theorem are called the Kazhdan-Lusztig polynomials of W.

There is one other way of computing the Kazhdan-Lusztig polynomials in terms of the R-polynomials, which we will use. Given a multichain a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} (r ∈ N) in W 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})) ,  (6)

(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)  (7)

if r = 0. The polynomial R_{a_{0},...,a_{r+1}}(q) thus defined is called the R-polynomial of the multichain a_{0} ≤ a_{1} ≤ … ≤ a_{r+1}. We then have the following result (we refer the reader to [5], Theorem 4.1, for its proof).

Theorem 2.8 Let u, v ∈ W. Then

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

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

Note that, although C(u, v) is an infinite set, the sum in (8) is actually finite since R_{C}(q) = 0 for almost all C ∈ C(u, v) (see [5], Proposition 3.5).

3 Weight polynomials

In this section we define and study the families of polynomials that we need for the statement and proof of our main result (Theorem 4.5). More precisely, we give simple recursions to compute these polynomials (see (9), (10), Propositions 3.2 and 3.5 and Theorem 3.4), we prove that their coefficients alternate in sign (see Theorems 3.7, 3.10, and 3.14), and we obtain some inequalities and combinatorial interpretations for them (see Theorems 3.13, 3.15, and 3.16).

For β ∈ C we define a polynomial γ_{β}(q) inductively as follows. We let

γ_{β} =^{def} (I + U_{\frac{|β|+1}{2}} J_{|β|})(E − I)(γ_{β^{(1)}}) ,  (9)

if β_{1} ≥ 2,

γ_{β} =^{def} (E − I)U_{\frac{|β|}{2}} J_{|β|−1}(γ\overline{β})  (10)

if β_{1} = 1 and l(β) ≥ 2, and

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

For n ∈ P and α ∈ C_{n} we then let

g_{α} =^{def} ∑_{{β∈C_{n}:β⪯α}}(−1)^{l(β)−l(α)}γ_{β} .  (12)

So, for example,

γ_{1,1} = (E − I)U_{1} J_{1}(γ_{1}) = −q^{2} + q ,
γ_{2,1} = (I + U_{2}J_{3})(E − I)(γ_{1,1})
= −(q − 1)^{2}q + U_{2}(−(1 − q)^{2})
= −q^{3} + q^{2} − q,

and

g_{3,2} = γ_{3,2} − γ_{2,1,2} − γ_{1,2,2} + γ_{1,1,1,2} − γ_{3,1,1} + γ_{2,1,1,1} + γ_{1,2,1,1} − γ_{1,1,1,1,1}
= q^{5} − 3q^{4} + 2q^{3} − q^{2}.

Note that from the Principle of Inclusion-Exclusion (see, e.g., [18], §2.1, p. 64) we obtain that (12) is equivalent to

γ_{β} = ∑_{{α∈C_{n}: α⪯β}} g_{α},  (13)

for all β ∈ C_{n}, n ∈ P.

There are two more families of polynomials (again indexed by compositions) that are closely related to the ones just introduced, and which are useful for the proof of our main result. For n ∈ P and α ∈ C_{n} we let

γ̂_{α} =^{def} (I − U_{\frac{n+1}{2}} J_{n})(γ_{α})  (14)

and

ĝ_{α} =^{def} (I − U_{\frac{n+1}{2}} J_{n})(g_{α}) .  (15)

Note that the relations (14) and (15) can be easily inverted.

Proposition 3.1 Let n ∈ P and α ∈ C_{n}. Then we have that

g_{α} = (I + U_{\frac{n+1}{2}} J_{n})(ĝ_{α}) ,  (16)

and

γ_{α} = (I + U_{\frac{n+1}{2}} J_{n})(γ̂_{α}) .  (17)

Proof. We have from Proposition 2.1 that

(I + U_{\frac{n+1}{2}} J_{n})(I − U_{\frac{n+1}{2}} J_{n}) = I − U_{\frac{n+1}{2}} J_{n}U_{\frac{n+1}{2}} J_{n}
= I − J_{n}D_{\frac{n−1}{2}} U_{\frac{n+1}{2}} J_{n}
= I ,  (18)

and the result follows from (14) and (15). □

Using (14), (15), (16), and (17) we can easily translate recurrence relations for the {γ_{α}}_{α∈C} (respectively, {g_{α}}_{α∈C}) into recurrence relations for the {γ̂_{α}}_{α∈C} (respectively, {ĝ_{α}}_{α∈C}), and conversely. We will often do this since the γ̂_{α}’ s and ĝ_{α}’ s are usually easier to handle.

Our goal now is to find simple recursions for the polynomials introduced so far in order to prove some of their fundamental properties, which we will need in the proof of our main results. We begin by “transferring” the recurrence relations (9), and (10), to the polynomials {γ̂_{α}}_{α∈C}.

Proposition 3.2 Let n ∈ P and β ∈ C_{n}. Then

γ̂_{β} = (q − 1)(U\frac{n}{2} J_{n−1} + I)(γ̂_{β^{(1)}})  (19)

if β_{1} ≥ 2, and

γ̂_{β} = (q − 1)U\frac{n}{2} J_{n−1}(γ̂\overline{β}),  (20)

if β_{1} = 1 and l(β) ≥ 2.

Proof. (19) follows easily from (9), (14), (17), and (18). To prove (20) note that it follows from (10) and (17) that, if β_{1} = 1 and l(β) ≥ 2,

γ_{β} = (E − I)U\frac{n}{2} J_{n−1}(I + U\frac{n}{2} J_{n−1})(γ̂\overline{β})
= (E − I)(U\frac{n}{2} J_{n−1} + J_{n−1}D_{\frac{n−2}{2}} U\frac{n}{2} J_{n−1})(γ̂\overline{β})
= (E − I)U\frac{n}{2} J_{n−1}(γ̂\overline{β}),  (21)

by i) and ii) of Proposition 2.1. But from (10) we conclude that, if β_{1} = 1 and l(β) ≥ 2, then

U_{\frac{n+1}{2}} J_{n}(γ_{β}) = U_{\frac{n+1}{2}} J_{n}(E − I)U\frac{n}{2} J_{n−1}(γ\overline{β}) = J_{n}D_{\frac{n−1}{2}} (E − I)U\frac{n}{2} J_{n−1}(γ\overline{β}) = 0,

again by Proposition 2.1. Hence, by (14),

γ̂_{β} = (I − U_{\frac{n+1}{2}} J_{n})(γ_{β}) = γ_{β} ,  (22)

if β_{1} = 1 and l(β) ≥ 2, and (20) follows from (21). □

The preceding result allows us to show that the polynomials {ĝ_{α}}_{α∈C} satisfy an extremely simple recurrence relation. Before we can do this, however, we need the following preliminary result.

Proposition 3.3 Let β ∈ C be such that |β| ≥ 2. Then

γ̂_{β} = ∑_{i=1}^{β_{1}}(E − I)^{i}U_{\frac{n−i+1}{2}} J_{n−i}(γ̂_{β^{(i)}}),  (23)

where n =^{def} |β|.

Proof. We proceed by induction on β_{1} ∈ P. If β_{1} = 1 then (23) reduces to (20). If β_{1} ≥ 2 then we conclude from (19) of Proposition 3.2 and our induction hypothesis that

γ̂_{β} = (E − I)(I + U\frac{n}{2} J_{n−1})(γ̂_{β^{(1)}})
= (E − I)U\frac{n}{2} J_{n−1}(γ̂_{β^{(1)}}) + (E − I) ∑_{i=1}^{β_{1}−1}(E − I)^{i}U_{\frac{n−i}{2}} J_{n−1−i}(γ̂_{β^{(i+1)}})

and (23) follows. □

We can now prove one of the main results of this section.

Theorem 3.4 Let α ∈ C. Then we have that

ĝ_{α} = (q − 1)^{α_{1}} U_{\frac{|\overline{α}|+1}{2}} J_{|\overline{α}|}(ĝ\overline{α})  (24)

if l(α) ≥ 2, and

ĝ_{α} = (q − 1)^{α_{1}}  (25)

if l(α) = 1.

Proof. We define a family of polynomials {k_{α}(q)}_{α∈C} by letting

k_{α} =^{def} (q − 1)^{α_{1}} U_{\frac{|\overline{α}|+1}{2}} J_{|\overline{α}|}(k\overline{α})  (26)

if l(α) ≥ 2, and

k_{α} = (q − 1)^{α_{1}}  (27)

if l(α) = 1. Then we have from (26) and (27) that

∑_{{α∈C_{n}:α⪯β}} k_{α} = ∑_{i=1}^{β_{1}} ∑_{{α∈C_{n−i}:α⪯β^{(i)}}} k_{i,α}
= ∑_{i=1}^{β_{1}} ∑_{\{α∈C_{n−i}:α⪯β^{(i)}\}}(q − 1)^{i}U_{\frac{|α|+1}{2}} J_{|α|}(k_{α})
= ∑_{i=1}^{β_{1}}(q − 1)^{i}U_{\frac{n−i+1}{2}} J_{n−i} (  ∑_{\{α∈C_{n−i}: α⪯β^{(i)}\}} k_{α}) ,  (28)

for all β ∈ C such that |β| ≥ 2. Since, by (11), (14), and (27), ∑_{α⪯(1)} k_{α} = k_{1} = (q − 1) = γ̂_{1}, we conclude from (28) and Proposition 3.3 that

∑_{{α∈C_{n}: α⪯β}} k_{α} = γ̂_{β}

for all β ∈ C_{n}, n ∈ P. This, by (13), (14), and (15), and the Principle of Inclusion-Exclusion, implies that k_{α} = ĝ_{α} for all α ∈ C, and the result follows from (26) and (27). □

Note that the preceding result allows us to define ĝ_{α_{1},...,α_{s}}(q) for any α_{1}, …, α_{s} ∈ N. We will use this fact freely in what follows.

The results presented so far are already enough to allow us to prove our main theorem in the next section. However, because of the fundamental role that the polynomials {g_{α}}_{α∈C} and {γ_{α}}_{α∈C} play in the computation of the Kazhdan-Lusztig polynomials (see Theorem 4.5), we feel that it is both desirable and natural to study them further. In fact, we believe that the meaning and interest of our main result would be considerably diminished if one could not show that the polynomials {g_{α}}_{α∈C} and {γ_{α}}_{α∈C} have nice properties, and can be efficiently computed.

We begin by deducing, from (16) and Theorem 3.4, a simple recursive way to compute the polynomials {g_{α}}_{α∈C}.

Proposition 3.5 Let α ∈ C. Then we have that

g_{α} = [(E − I)^{α_{1}}J_{|\overline{α}|} + U_{\frac{|α|+1}{2}} (I − E)^{α_{1}}]D_{\frac{|\overline{α}|−1}{2}} (g\overline{α}),  (29)

if l(α) ≥ 2, and

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

if l(α) = 1.

Proof. Note that (16) implies (30) as well as that

D_{\frac{|α|−1}{2}} (g_{α}) = D_{\frac{|α|−1}{2}} (ĝ_{α}) .  (31)

Hence we conclude from (16) and (24) that, if l(α) ≥ 2,

g_{α} = (I + U_{\frac{|α|+1}{2}} J_{|α|})((E − I)^{α_{1}}J_{|\overline{α}|}D_{\frac{|\overline{α}|−1}{2}} )(ĝ\overline{α})
= [(E − I)^{α_{1}}J_{|\overline{α}|} + U_{\frac{|α|+1}{2}} (I − E)^{α_{1}}]D_{\frac{|\overline{α}|−1}{2}} (ĝ\overline{α})  (32)

(since J_{|α|}(E − I)^{α_{1}}J_{|\overline{α}|} = (I − E)^{α_{1}}, as it is easy to verify), and (29) follows from (31). □

Proposition 3.1 gives a way to compute the γ_{α}’s and g_{α}’s from the γ̂_{α}’s and ĝ_{α}’s, respectively. The next result gives an alternative way to do the same.

Corollary 3.6 Let β_{1}, …, β_{s} ∈ P (s ∈ P). Then we have that

γ_{β_{1},...,β_{s}}(q) = \frac{1}{q − 1} γ̂_{β_{1}+1,β_{2},...,β_{s}}(q) ,  (33)

and

g_{β_{1},...,β_{s}}(q) = ĝ_{β_{1},...,β_{s}}(q) + ĝ_{0,β_{1},...,β_{s}}(q) .  (34)

Proof. (33) is an immediate consequence of (9), (14), and (18), while (34) follows immediately from (16) and Theorem 3.4. □

Probably the most interesting (and remarkable) property of the polynomials {g_{α}}_{α∈C} and {γ_{α}}_{α∈C} is that their coefficients alternate in sign. In order to prove this we need several preliminary results, which are also of independent interest. For d_{1}, …, d_{r} ∈ N we let mĝ(d_{1}, …, d_{r}) be the largest power of q that divides ĝ_{d_{1},...,d_{r}}(q).

Theorem 3.7 Let r ∈ P, and d_{1}, …, d_{r} ∈ N. Then (−1)^{d′} ĝ_{d_{1},...,d_{r}}(−q) ∈ P F_{2} where d′ =^{def} d_{1} + d_{3} + . . .. Furthermore, if r ≥ 2, and ĝ_{d_{1},...,d_{r}}(q) ≠ 0, then:

i) deg(ĝ_{d_{1},...,d_{r}}) = d_{1} + d_{2} + max (0, ⌊\frac{1}{2}(d_{3} + … + d_{r} − 1)⌋);

ii) mĝ(d_{1}, …, d_{r}) = ⌈\frac{1}{2}(d_{2} + … + d_{r} + 1)⌉;

iii) d_{j} ≥ 2 for j = 2, …, r − 1, and d_{r} ≥ 1.

Proof. We prove first that (−1)^{d′} ĝ_{d_{1},...,d_{r}}(−q) ∈ P F_{2} by induction on r ∈ P, this being clearly true if r = 1. If r ≥ 2 then, by Theorem 3.4,

(−1)^{d′} ĝ_{d_{1},...,d_{r}}(−q) = (q + 1)^{d_{1}} U_{\frac{d+1}{2}} ((−1)^{d′′}q^{d} ĝ_{d_{2},...,d_{r}} (−\frac{1}{q})) ,  (35)

where d =^{def} d_{2} + … + d_{r}, and d′′ =^{def} d_{2} + d_{4} + . . .. Since, clearly, U_{j}(P F_{2}) ⊆ P F_{2} for all j ∈ Z the result follows from (35), the induction hypothesis, and the well known fact (see, e.g., [4], Theorem 2.2.2, p. 9) that the product of two polynomials in P F_{2} is again in P F_{2}.

To prove i), ii), and iii) we proceed by induction on r ≥ 2, i), ii), and iii) being clearly true if r = 2. Then, since ĝ_{d_{1},...,d_{r}} ≠ 0, and ĝ_{d_{2},...,d_{r}} does not have internal zeros, we have from (35) that

deg(ĝ_{d_{1},...,d_{r}}) = d_{1} + d − mĝ(d_{2}, …, d_{r}),  (36)
mĝ(d_{1}, …, d_{r}) = max (⌈\frac{d + 1}{2}⌉ , d − deg(ĝ_{d_{2},...,d_{r}})) ,  (37)

and

d − mĝ(d_{2}, …, d_{r}) ≥ ⌈\frac{d + 1}{2}⌉ .  (38)

Now i) and ii) follow by induction from (36) and (37) since deg(ĝ_{d_{2},...,d_{r}}) ≥ ⌊\frac{d−1}{2}⌋ (by i) of our induction hypotheses) while iii) follows by induction since d_{2} ≥ 2 (by (38) and ii) of our induction hypotheses). □

Note that the polynomials ĝ_{d_{1},...,d_{r}}(q) do not, in general, have only real zeros, (take, e.g., ĝ_{1,6,3}(q)). Also note that the conditions in part iii) of Theorem 3.7 are not sufficient to insure that ĝ_{d_{1},...,d_{r}}(q) ≠ 0. For example, ĝ_{2,2,2}(q) = 0.

The preceding result allows us to give sufficient conditions on β that insure that γ_{β} = g_{β} = 0.

Proposition 3.8 Let β ∈ C and suppose that there exists i ∈ [2, l(β) − 1] such that β_{i} = 1. Then γ_{β}(q) = γ̂_{β}(q) = g_{β}(q) = 0.

Proof. The statement for g_{β}(q) follows immediately from Proposition 3.1 and Theorem 3.7, while those for γ_{β}(q) and γ̂_{β}(q) follow from (13) and the corresponding statement for the g_{α}’ s, and from (14), respectively. □

Note that the converse of the above proposition does not hold. For example, γ_{2,2,2}(q) = 0.

The crucial step in the proof that the coefficients of the polynomials γ_{α}(q) alternate in sign is given by the next result.

Proposition 3.9 Let β ∈ C. Then

γ̂_{β}(q) = (q − 1)((q − 1)γ̂_{β^{(2)}}(q) − q^{⌈ \frac{n}{2} ⌉}[q^{⌈ \frac{n}{2} ⌉−1}](γ̂_{β^{(2)}}(q)))  (39)

if β_{1} ≥ 3, and

γ̂_{β}(q) = (q − 1)^{2}U\frac{n}{2} (q^{n−1}γ̂\overline{β} (\frac{1}{q})) ,

if β_{1} = 2 and l(β) ≥ 2, where n =^{def} |β| − 1.

Proof. Since β_{1} ≥ 3 we conclude, by (19) of Proposition 3.2, that

γ̂_{β} = (E − I)(I + U_{\frac{n+1}{2}} J_{n})(E − I)(I + U\frac{n}{2} J_{n−1})(γ̂_{β^{(2)}}).  (40)

Now note that, by i) and ii) of Proposition 2.1,

U_{\frac{n+1}{2}} J_{n}(E − I)U\frac{n}{2} = J_{n}D_{\frac{n−1}{2}} (E − I)U\frac{n}{2} = 0.  (41)

Hence, again by Proposition 2.1,

(I + U_{\frac{n+1}{2}} J_{n})(E − I)(I + U\frac{n}{2} J_{n−1}) = (E − I) + (U_{\frac{n+1}{2}} (I − E) + (E − I)U\frac{n}{2} )J_{n−1}
= (E − I) + ((U_{\frac{n+1}{2}} − U\frac{n}{2} ) + E(U\frac{n}{2} − U_{\frac{n−1}{2}} ))J_{n−1}
= (E − I) + E(U_{⌊ \frac{n+1}{2} ⌋} − U_{⌊ \frac{n−1}{2} ⌋}),

and (39) follows from (40). If β_{1} = 2 and l(β) ≥ 2 then we conclude from Propositions 3.2 and 2.1 that

γ̂_{β} = (E − I)(I + U_{\frac{n+1}{2}} J_{n})(E − I)U\frac{n}{2} J_{n−1}(γ̂\overline{β})
= (E − I)^{2}U\frac{n}{2} J_{n−1}(γ̂\overline{β}),

as desired. □

We can now prove that the coefficients of the polynomials γ̂_{β}(q) and γ_{β}(q) alternate in sign. For β ∈ C we denote by mγ̂(β) (respectively, m_{γ}(β)) the largest power of q that divides γ̂_{β}(q) (respectively, γ_{β}(q)).

Theorem 3.10 Let β ∈ C and β′ =^{def} β_{1} + β_{3} + . . .. Then (−1)^{β′}γ_{β}(−q) has nonnegative coefficients and no internal zeros. Furthermore, if l(β) ≥ 2, and γ_{β}(q) ≠ 0, then

deg(γ_{β}) = β_{1} + β_{2} + max (0, ⌊\frac{β_{3} + … + β_{s} − 1}{2}⌋)  (42)

and

m_{γ}(β) = ⌈\frac{|\overline{β}| + 1}{2}⌉ .  (43)

The above statements also hold when “γ” is substituted by “γ̂”.

Proof. We proceed by induction on |β| ∈ P. If |β| = 1 then the result clearly holds. If |β| ≥ 2 then we have from Propositions 3.2 and 3.9 and Corollary 3.6 that

(−1)^{β′} γ̂_{β}(−q) = \{ \begin{matrix}(q + 1)(−1)^{β′−1}γ_{β^{(1)}}(−q), & if β_{1} ≥ 2, \\ (q + 1)U_{\frac{|β|}{2}} (q^{|β|−1}(−1)^{|β|+β′} γ̂\overline{β} (−\frac{1}{q})) , & if β_{1} = 1, \end{matrix}  (44)

and

(−1)^{β′}γ_{β}(−q) = \{ \begin{matrix}(q + 1)(−1)^{β′−1}γ̂_{β^{(1)}}(−q) − q^{⌈ \frac{|β|}{2} ⌉}[q^{⌊ \frac{|β|−1}{2} ⌋}]((−1)^{β′−1}γ̂_{β^{(1)}}(−q)), & if β_{1} ≥ 2, \\ (q + 1)U_{\frac{|β|}{2}} (q^{|β|−1}(−1)^{|β|+β′} γ̂\overline{β} (−\frac{1}{q})) , & if β_{1} = 1. \end{matrix}

(45)

This easily implies, by our induction hypotheses, that (−1)^{β′} γ̂_{β}(−q) and (−1)^{β′}γ_{β}(−q) both have nonnegative coefficients and no internal zeros. Furthermore, using the hypothesis that γ̂_{β}(q) ≠ 0, and the fact that γ̂\overline{β}(q) has no internal zeros, we conclude from (44) that

deg(γ̂_{β}) = \{ \begin{matrix}deg(γ_{β^{(1)}}) + 1, & if β_{1} ≥ 2, \\ |β| − 1 − mγ̂(\overline{β}) + 1, & if β_{1} = 1, \end{matrix}

and

mγ̂(β) = \{ \begin{matrix}m_{γ}(β^{(1)}), & if β_{1} ≥ 2, \\ max (⌈\frac{|β|}{2}⌉ , |β| − 1 − deg(γ̂\overline{β})) , & if β_{1} = 1, \end{matrix}

and the analogues of (42) and (43) for the γ̂_{β}’s follow by induction and the easily verified facts that mγ̂(β) = 0 and

deg(γ̂_{β}) = \{ \begin{matrix}|β|, & if |β| ≡ 0 (mod 2), \\ \frac{|β|−1}{2}, & if |β| ≡ 1 (mod 2), \end{matrix}  (46)

if l(β) = 1.

Now note that, if β_{1} ≥ 2 and γ_{β} ≠ 0, then (45) implies that deg(γ_{β}) = deg(γ̂_{β^{(1)}})+1 unless ⌈\frac{|β|}{2}⌉ = deg(γ̂_{β^{(1)}})+1 (= β_{1}+β_{2}+ max(0, ⌊\frac{1}{2}(β_{3} + … + β_{s} − 1)⌋), by induction). Since β_{1} ≥ 2, this can happen only if l(β) ≥ 3, β_{1} + β_{2} = 3, and β_{3} + … + β_{s} is even, which is impossible by Proposition 3.8. Therefore using the hypothesis that γ_{β}(q) ≠ 0, and the fact that γ̂\overline{β}(q) has no internal zeros, we conclude from (45) that

deg(γ_{β}) = \{ \begin{matrix}deg(γ̂_{β^{(1)}}) + 1, & if β_{1} ≥ 2, \\ |β| − 1 − mγ̂(\overline{β}) + 1, & if β_{1} = 1, \end{matrix}

and

m_{γ}(β) = \{ \begin{matrix}mγ̂(β^{(1)}), & if β_{1} ≥ 2, \\ max (⌈\frac{|β|}{2}⌉ , |β| − 1 − deg(γ̂\overline{β})) , & if β_{1} = 1, \end{matrix}

and (42) and (43) follow similarly by induction, using (46). This concludes the induction step and hence the proof. □

Note that the polynomials (−1)^{β′} γ̂_{β}(−q) and (−1)^{β′}γ_{β}(−q) are not, in general, even unimodal. For example, γ_{4}(q) = q^{4} − 3q^{3} + 2q^{2} − 3q + 1, and γ̂_{9}(q) = q^{9} − 8q^{8} + 27q^{7} − 48q^{6} + 42q^{5} − 42q^{4} + 48q^{3} − 27q^{2} + 8q − 1.

To prove the analogue of the previous result for the polynomials g_{α}’s one needs some further properties of the polynomials ĝ_{α}’s, which we now develop.

Lemma 3.11 Let i ∈ Z, r ∈ P, r ≥ 2, and d_{1}, …, d_{r} ∈ N. Then

∑_{j≥⌈ \frac{d+1}{2} ⌉}(−1)^{d_{1}−i+j} (\begin{matrix}d_{1} \\ i−j \end{matrix} ) [q^{d−j}](ĝ_{d_{2},...,d_{r}}) = [q^{i}](ĝ_{d_{1},...,d_{r}}),  (47)

(where d =^{def} d_{2} + … + d_{r}).

Proof. From Theorem 3.4 we obtain that

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

and (47) follows. □

The next result is an immediate consequence of the previous one, and its verification is left to the reader.

Proposition 3.12 Let r ∈ P, r ≥ 2, k ∈ Z, and d_{1}, …, d_{r} ∈ N. Then

[q^{k}](ĝ_{d_{1},...,d_{r}}) = (−1)^{k+d′} ∑_{j_{1}≥⌈ \frac{c_{1}+1}{2} ⌉} … ∑_{j_{r−1}≥⌈ \frac{c_{r−1}+1}{2} ⌉} ∏_{α=1}^{r} (\begin{matrix}d_{α} \\ c_{α−1}−j_{α−1}−j_{α} \end{matrix} )

where d′ =^{def} d_{1} + d_{3} + …, c_{α} =^{def} d_{α+1} + … + d_{r}, for α = 0, …, r − 1, j_{0} =^{def} c_{0} − k,

and j_{r} =^{def} 0. □

Theorem 3.13 Let r ∈ P, and d_{1}, …, d_{r} ∈ N. Then

|[q^{k}](ĝ_{d_{1},...,d_{r}})| ≤ |[q^{n−k}](ĝ_{d_{1},...,d_{r}})|  (48)

for all 0 ≤ k ≤ \frac{n}{2} (where n =^{def} d_{1} + … + d_{r}), and

|[q^{0}](ĝ_{d_{1},...,d_{r}})| ≤ |[q](ĝ_{d_{1},...,d_{r}})| ≤ … ≤ |[q^{⌊ \frac{n}{2} ⌋}](ĝ_{d_{1},...,d_{r}})|.  (49)

Proof. It is well known, and easy to see, (see, e.g., [19], p. 500, or [6], §7.1) that the sequence \{(\begin{matrix}d \\ i \end{matrix})\}_{i∈Z} is symmetric and unimodal with center of symmetry at \frac{d}{2}. Therefore

(\begin{matrix}d \\ \frac{a}{2} − \frac{b}{2} \end{matrix} ) ≤ (\begin{matrix}d \\ \frac{a}{2} + \frac{b}{2} \end{matrix} )

for all a, b ∈ Z such that a ≤ d and b ≥ 0 (where (\begin{matrix}d \\ i \end{matrix}) =^{def} 0 if i ∉ Z). Hence

(\begin{matrix}d_{1} \\ k−j \end{matrix} ) = (\begin{matrix}d_{1} \\ \frac{n}{2} −j−(\frac{n}{2} −k) \end{matrix}) ≤ (\begin{matrix}d_{1} \\ \frac{n}{2} −j+(\frac{n}{2} −k) \end{matrix}) = (\begin{matrix}d_{1} \\ n−j−k \end{matrix})

for all j ∈ Z such that j ≥ \frac{1}{2}(n − d_{1} + 1), and (48) follows from Proposition 3.12. To prove (49) assume that there exists 0 ≤ k ≤ ⌊\frac{n}{2}⌋ − 1 such that

|[q^{k}](ĝ_{d_{1},...,d_{r}})| > |[q^{k+1}](ĝ_{d_{1},...,d_{r}})|.  (50)

Since, by Theorem 3.7, the absolute values of the coefficients of ĝ_{d_{1},...,d_{r}}(q) form a unimodal sequence, (50) implies that |[q^{k}](ĝ_{d_{1},...,d_{r}})| > |[q^{n−k}](ĝ_{d_{1},...,d_{r}})|, which contradicts (48). □

We can now prove the analogue of Theorem 3.10 for the polynomials g_{α}’s. Given α ∈ C we denote by m_{g}(α) the largest power of q that divides g_{α}(q).

Theorem 3.14 Let α ∈ C, and α′ = α_{1} + α_{3} + . . .. Then (−1)^{α′}g_{α}(−q) ∈ N[q]. Furthermore, if g_{α} ≠ 0 and l(α) ≥ 2, then

deg(g_{α}) = α_{1} + α_{2} + max (0, ⌊\frac{1}{2}(α_{3} + … + α_{r} − 1)⌋) ,  (51)

and

m_{g}(α) = ⌈\frac{|\overline{α}| + 1}{2}⌉ .  (52)

Proof. From Proposition 3.1 we have that

(−1)^{α′}g_{α}(−q) = (−1)^{α′} ĝ_{α}(−q) + (−1)^{|α|}U_{\frac{|α|+1}{2}} ((−1)^{α′}q^{|α|}ĝ_{α} (−\frac{1}{q})) .

Therefore, by Theorem 3.7,

[q^{k}]((−1)^{α′}g_{α}(−q)) = \{ \begin{matrix}|[q^{k}](ĝ_{α}(q))|, & if k < ⌈\frac{|α|+1}{2}⌉, \\ |[q^{k}](ĝ_{α}(q))| + (−1)^{|α|}|[q^{|α|−k}](ĝ_{α}(q))|, & if k ≥ ⌈\frac{|α|+1}{2}⌉, \end{matrix}

and the first statement follows from (48) of Theorem 3.13.

To prove (51) and (52) note that since g_{α} ≠ 0 we conclude from (16) that ĝ_{α} ≠ 0. If ĝ_{0,α} = 0 then the result follows immediately from (34) and Theorem 3.7.

If ĝ_{0,α} ≠ 0 then, by part iii) of Theorem 3.7, α_{1} ≥ 2, and α_{2} ≥ 2 if l(α) ≥ 3, and hence we conclude from parts i) and ii) of Theorem 3.7 that deg(ĝ_{0,α}) < deg(ĝ_{α}) and mĝ(0, α) > mĝ(α) and the result again follows from (34) and Theorem 3.7. □

Theorem 3.13 has also the following interesting consequence.

Theorem 3.15 Let α ∈ C. Then

|[q^{0}](γ_{α})| ≤ |[q](γ_{α})| ≤ … ≤ |[q^{⌊ \frac{|α|}{2} ⌋}](γ_{α})|,  (53)

and

|[q^{0}](g_{α})| ≤ |[q](g_{α})| ≤ … ≤ |[q^{⌊ \frac{|α|}{2} ⌋}](g_{α})|,  (54)

Proof. From (13), (14), and (15) we conclude that

γ̂_{α} = ∑_{{β∈C_{n}:β⪯α}} ĝ_{β}

where n =^{def} |α|, so (49) implies that

|[q^{0}](γ̂_{α})| ≤ |[q](γ̂_{α})| ≤ … ≤ |[q^{⌊ \frac{|α|}{2} ⌋}](γ̂_{α})|.  (55)

Now (53) and (54) are just a restatement of (55) and (49), because, by Proposition 3.1, D_{\frac{|α|}{2}} (ĝ_{α}) = D_{\frac{|α|}{2}} (g_{α}) and

D_{\frac{|α|}{2}} (γ̂_{α}) = D_{\frac{|α|}{2}} (γ_{α}) .□  (56)

We conclude this section by giving a combinatorial interpretation of the polynomials (−1)^{α′} ĝ_{α}(−q). Let a, b ∈ P, a ≤ b, and T = {t_{1}, …, t_{r−1}}_{<} be a subset of [a, b − 1]. We say that a subset S ⊆ [a, b] is T -balanced if

|S ∩ (t_{2i}, b]| ≤ ⌊\frac{|(t_{2i}, b]| − 1}{2}⌋ ,

and

|S ∩ (t_{2i−1}, b]| ≥ ⌈\frac{|(t_{2i−1}, b]| + 1}{2}⌉ ,

for all i = 1, …, ⌊\frac{r−1}{2}⌋. For example, if a = 1 and b = 5, then \{3, 4\} is \{2, 4\}- balanced, but not {1, 4}-balanced. Given T ⊆ [a, b − 1] we let

G_{a,b}(T) =^{def} {S ∈ P([a, b]) : S is T -balanced}.  (57)

If a = 1 we will simply write G_{b}(T) instead of G_{1,b}(T).

Theorem 3.16 Let α ∈ C, and α′ =^{def} α_{1} + α_{3} + . . .. Then

(−1)^{α′} ĝ_{α}(−q) = ∑_{S∈G_{|α|}(T)} q^{|S|} ,  (58)

where T =^{def} {α_{1}, α_{1} + α_{2}, …, α_{1} + α_{2} + … + α_{r−1}} and r =^{def} l(α).

Proof. Note first that any S ∈ G_{|α|}(T) can be written uniquely as S = S′⊎S′′ where S′ ⊆ [α_{1}], S′′ ⊆ (α_{1}, |α|], (α_{1}, |α|] \ S′′ ∈ G_{α_{1}+1,|α|}(T \ \{α_{1}\}), and |S′′| ≥ ⌈\frac{|\overline{α}|+1}{2}⌉. Therefore,

∑_{S∈G_{|α|}(T)} q^{|S|} = (1 + q)^{α_{1}}U_{\frac{|\overline{α}|+1}{2}} (q^{|\overline{α}|} ∑_{S∈G_{α_{1}+1,|α|}(T \\{α_{1}\})} (\frac{1}{q})^{|S|}) .  (59)

We now proceed by induction on r ∈ P, (58) being clearly true if r = 1. Since there is an obvious size preserving bijection between G_{α_{1}+1,|α|}(T \\{α_{1}\}) and G_{|\overline{α}|}(\{α_{2}, α_{2} + α_{3}, …, α_{2} + α_{3} + … + α_{r−1}}), using (59) and our induction hypothesis we conclude that

∑_{S∈G_{|α|}(T)} q^{|S|} = (1 + q)^{α_{1}}U_{\frac{|\overline{α}|+1}{2}} (q^{|\overline{α}|}(−1)^{|α|−α′} ĝ\overline{α} (−\frac{1}{q}))
= (1 + q)^{α_{1}}(−1)^{α′−α_{1}}U_{\frac{|\overline{α}|+1}{2}} ((−q)^{|\overline{α}|}ĝ\overline{α} (−\frac{1}{q}))
= (−1)^{α′} ĝ_{α}(−q),

by Theorem 3.4, as desired. □

We illustrate the preceding theorem with an example. Suppose α = (2, 2, 3). Then G_{7}({2, 4}) = ⋃_{i=5}^{7}{{3, 4, i}, {2, 3, 4, i}, {1, 3, 4, i}, {1, 2, 3, 4, i}} and hence (−1)^{5} ĝ_{2,2,3}(−q) = 3q^{3} + 6q^{4} + 3q^{5}. We have been unable to find combinatorial interpretations for the polynomials (−1)^{α′}g_{α}(−q), (−1)^{α′}γ_{α}(−q), and (−1)^{α′} γ̂_{α}(−q).

4 Main Results

In this section we prove our main result (Theorem 4.5). This expresses any Kazhdan-Lusztig polynomial as a linear combination of the polynomials {γ_{β}}_{β∈C} and {g_{α}}_{α∈C}, introduced and studied in the previous section, and gives a combinatorial interpretation to the coefficients in these expansions in terms of certain directed paths in the Bruhat graph of W. As a consequence of our main result we obtain a combinatorial rule to compute any Kazhdan-Lusztig polynomial (Corollary 4.6), and a completely combinatorial reformulation of the nonnegativity conjecture (Theorem 4.8).

Our first step is that of expressing the R-polynomial of a multichain in terms of the polynomials ĝ_{d_{1},...,d_{r}}(q).

Theorem 4.1 Let a_{0} ≤ a_{1} ≤ … ≤ a_{r} be a multichain in W. Then

R_{a_{0},a_{1},...a_{r}}(q) = ε_{a_{0}}ε_{a_{r}} ∑_{α_{1}≥0} … ∑_{α_{r}≥0} q^{\frac{l(ar)−l(a_{0})−α}{2}} ĝ_{α_{1},...,α_{r}}(q) ∏_{j=1}^{r}[q^{α_{j}}](R̃_{a_{j−1},a_{j}}) , (60)

where α =^{def} α_{1} + … + α_{r}.

Proof. We proceed by induction on r ∈ P. If r = 1 then (60) follows immediately from (7), (25), and (4) of Proposition 2.4. If r > 1 then we have from (6) and our induction hypothesis that

R_{a_{0},a_{1},...,a_{r}}(q) = R_{a_{0},a_{1}}(q)U_{\frac{d+1}{2}} (q^{d}R_{a_{1},...,a_{r}} (\frac{1}{q}))
= U_{\frac{d+1}{2}} (q^{d}ε_{a_{1}} ε_{a_{r}} ∑_{α_{2}≥0} … ∑_{α_{r}≥0} q^{\frac{α_{2}+...+αr−d}{2}} ĝ_{α_{2},...,α_{r}} (\frac{1}{q}) ∏_{j=2}^{r}[q^{α_{j}}](R̃_{a_{j−1},a_{j}})))

ε_{a_{0}}ε_{a_{1}} ∑_{α_{1}≥0}(q − 1)^{α_{1}}q^{\frac{l(a_{1})−l(a_{0})−α_{1}}{2}} [q^{α_{1}}](R̃_{a_{0},a_{1}})

= ε_{a_{0}}ε_{a_{r}} ∑_{α_{1}≥0} … ∑_{α_{r}≥0} U_{\frac{d+1}{2}} (q^{\frac{d+α−α_{1}}{2}} ĝ_{α_{2},...,α_{r}} (\frac{1}{q}))

q^{\frac{l(a_{1})−l(a_{0})−α_{1}}{2}} ĝ_{α_{1}}(q) ∏_{j=1}^{r}[q^{α_{j}}](R̃_{a_{j−1},a_{j}})

= ε_{a_{0}}ε_{a_{r}} ∑_{α_{1}≥0} … ∑_{α_{r}≥0} q^{\frac{d−α+α_{1}}{2}} U_{\frac{d+1}{2} − \frac{d−α+α_{1}}{2}} (q^{α−α_{1}} ĝ_{α_{2},...,α_{r}} (\frac{1}{q}))

q^{\frac{l(a_{1})−l(a_{0})−α_{1}}{2}} ĝ_{α_{1}}(q) ∏_{j=1}^{r}[q^{α_{j}}](R̃_{a_{j−1},a_{j}})

= ε_{a_{0}}ε_{a_{r}} ∑_{α_{1}≥0} … ∑_{α_{r}≥0} q^{\frac{l(ar)−l(a_{0})−α}{2}} U_{\frac{α−α_{1}+1}{2}} (q^{α−α_{1}} ĝ_{α_{2},...,α_{r}} (\frac{1}{q}))

ĝ_{α_{1}}(q) ∏_{j=1}^{r}[q^{α_{j}}](R̃_{a_{j−1},a_{j}}),

(where d =^{def} l(a_{r}) − l(a_{1})) and the thesis follows from Theorem 3.4. □

We note the following special case of the above result.

Corollary 4.2 Let a_{0} ≤ a_{1} ≤ … ≤ a_{r} be a multichain in W and suppose that [a_{0}, a_{r}] does not contain any subinterval isomorphic to S_{3}. Then

R_{a_{0},...,a_{r}}(q) = (−1)^{l(a_{r})−l(a_{0})}ĝ_{d_{1},...,d_{r}}(q)  (61)

where d_{j} =^{def} l(a_{j}) − l(a_{j−1}), for j = 1, …, r.

Proof. Since [a_{0}, a_{r}] does not contain any subinterval isomorphic to S_{3} we have from (4) and Theorem 6.3 of [5] that R̃_{a_{j−1},a_{j}}(q) = q^{l(a_{j})−l(a_{j}−1)} for j = 1, …, r, and the result follows from Theorem 4.1. □

Now fix a reflection ordering <_{T} of T in W (as defined in section 2). Recall that given u, v ∈ W we denote by B(u, v) the set of all directed paths in B(W, S) from u to v. For u, v ∈ W, and α_{1}, …, α_{r} ∈ N, we let

c_{α_{1},...,α_{r}}(u, v) =^{def} |{(a_{0}, …, a_{α}) ∈ B(u, v) : D(a_{0}, …, a_{α}) ⊆ {β_{1}, …, β_{r−1}}}|, (62)

and

b_{α_{1},...,α_{r}}(u, v) =^{def} |{(a_{0}, …, a_{α}) ∈ B(u, v) : D(a_{0}, …, a_{α}) = {β_{1}, …, β_{r−1}}}| (63)

where β_{i} =^{def} α_{1} + … + α_{i}, for i = 1, …, r, and α =^{def} β_{r}. Note that these definitions imply that

c_{α}(u, v) = ∑_{{β∈C_{n}:β⪰α}} b_{β}(u, v)  (64)

for all u, v ∈ W and α ∈ C_{n} (n ∈ P).

We note first the following elementary property of the coefficients c_{α_{1},...,α_{r}}(u, v).

Proposition 4.3 Let u, v ∈ W, u ≤ v, and α_{1}, …, α_{r} ∈ N (r ∈ P), r ≥ 2. Then

c_{α_{1},...,α_{r}}(u, v) = ∑_{u≤a≤v} c_{α_{1},...,α_{r−1}}(u, a)c_{α_{r}}(a, v) .

Proof. Let C =^{def} (a_{0}, …, a_{α}) ∈ B(u, v) be such that D(C) ⊆ {β_{1}, …, β_{r−1}},

where β_{i} =^{def} α_{1} + … + α_{i}, for i = 1, …, r. Then, clearly, u ≤ a_{β_{r−1}} ≤ v,

C′ =^{def} (a_{0}, …, a_{β_{r−1}}) ∈ B(u, a_{β_{r−1}}), C′′ =^{def} (a_{β_{r−1}}, …, a_{α}) ∈ B(a_{β_{r−1}}, v), D(C′) ⊆

{β_{1}, …, β_{r−2}}, and D(C′′) = ∅. It is easy to see that this correspondence C ↔ (C′, C′′) is a bijection, and the result follows from (62). □

The following result is crucial for the proof of our main theorem.

Proposition 4.4 Let u, v ∈ W, u ≤ v, and α_{1}, …, α_{r} ∈ N (r ∈ P). Then

c_{α_{1},...,α_{r}}(u, v) = ∑_{(a_{0},...,a_{r})∈C_{r}(u,v)} ∏_{j=1}^{r}[q^{α_{j}}](R̃_{a_{j−1},a_{j}})

where C_{r}(u, v) denotes the set of all multichains of length r from u to v.

Proof. We proceed by induction on r ∈ P. If r = 1 then, by (62) and Theorem 2.6, we have that

c_{α_{1}}(u, v) = |{(a_{0}, …, a_{α_{1}}) ∈ B(u, v) : D(a_{0}, …, a_{α_{1}}) = ∅}| = [q^{α_{1}}](R̃_{u,v}), (65)

as desired. If r ≥ 2 then we have from Proposition 4.3, (65), and our induction hypothesis that

c_{α_{1},...,α_{r}}(u, v) = ∑_{u≤a≤v} c_{α_{r}}(a, v)c_{α_{1},...,α_{r−1}}(u, a)
= ∑_{u≤a≤v}[q^{α_{r}}](R̃_{a,v}) ∑_{(a_{0},...,a_{r−1})∈C_{r−1}(u,a)} ∏_{j=1}^{r−1}[q^{α_{j}}](R̃_{a_{j−1},a_{j}})
= ∑_{u≤a≤v} ∑_{(a_{0},...,a_{r−1})∈C_{r−1}(u,a)}[q^{α_{r}}](R̃_{a,v}) ∏_{j=1}^{r−1}[q^{α_{j}}](R̃_{a_{j−1},a_{j}}),

and the result follows. □

We can now prove the main result of this work. This gives two combinatorial expansions of the Kazhdan-Lusztig polynomial of two elements u, v ∈ W in terms of the polynomials g_{α}(q) and γ_{β}(q).

Theorem 4.5 Let u, v ∈ W, u < v. Then

P_{u,v}(q) = ε_{u}ε_{v} ∑_{α∈C} q^{\frac{1}{2} (l(v)−l(u)−|α|)}c_{α}(u, v) g_{α}(q) ,  (66)

and

P_{u,v}(q) = ε_{u}ε_{v} ∑_{β∈C} q^{\frac{1}{2} (l(v)−l(u)−|β|)}b_{β}(u, v) γ_{β}(q) .  (67)

Proof. It follows immediately from Theorems 2.8, 4.1 and Proposition 4.4 that

P_{u,v}(q) = ε_{u}ε_{v} ∑_{r≥1} ( ∑_{α_{1}≥0} … ∑_{α_{r}≥0} q^{\frac{1}{2} (l(v)−l(u)−α)}c_{α_{1},...,α_{r}}(u, v)ĝ_{α_{1},...,α_{r}}(q)) ,  (68)

where α =^{def} α_{1} + … + α_{r}, and (66) follows from part iii) of Theorem 3.7, Corollary 3.6, and the observation that c_{0,α_{1},...,α_{r}}(u, v) = c_{α_{1},...,α_{r}}(u, v) for all α_{1}, …, α_{r} ∈ P, and c_{0}(u, v) = 0 if u < v.

To prove (67) note that

∑_{α∈C} q^{− \frac{|α|}{2}} c_{α}(u, v)g_{α}(q) = ∑_{n=0}^{l(v)−l(u)} q^{− \frac{n}{2}} ∑_{α∈C_{n}} c_{α}(u, v)g_{α}(q)
= ∑_{n=0}^{l(v)−l(u)} q^{− \frac{n}{2}} ∑_{α∈C_{n}} ∑_{\{β∈C_{n}: β⪰α\}} b_{β}(u, v) g_{α}(q)

= ∑_{n=0}^{l(v)−l(u)} q^{− \frac{n}{2}} ∑_{β∈C_{n}} b_{β}(u, v) ∑_{\{α∈C_{n}: α⪯β\}} g_{α}(q)
= ∑_{n=0}^{l(v)−l(u)} q^{− \frac{n}{2}} ∑_{β∈C_{n}} b_{β}(u, v) γ_{β}(q),

by (64) and (13), and (67) follows from (66). □

We note the following particularly elegant way of restating Theorem 4.5. Given a directed path Γ ∈ B(W, S) of length k we denote by D(Γ) the composition of k corresponding to D(Γ) under the identification of C_{k} with B_{k−1} described in section 2.

Corollary 4.6 Let u, v ∈ W, u < v. Then

P_{u,v}(q) = ε_{u}ε_{v} ∑_{Γ∈B(u,v)} q^{\frac{1}{2} (l(v)−l(u)−l(Γ))}γ_{D(Γ)}(q).  (69)

Proof. We have that

∑_{Γ∈B(u,v)} q^{\frac{1}{2} (l(v)−l(u)−l(Γ))}γ_{D(Γ)}(q) = ∑_{β∈C} ∑_{\{Γ∈B(u,v):D(Γ)=β\}} q^{\frac{1}{2} (l(v)−l(u)−l(Γ))}γ_{D(Γ)}(q)

and (69) follows from (67), (63), and the fact that l(Γ) = |D(Γ)| for all Γ ∈ B(u, v). □

The preceding corollary is especially interesting as it yields a rather explicit algorithm for the computation of any Kazhdan-Lusztig polynomial. Namely, given u, v ∈ W, one should construct all possible directed paths Γ from u to v in B(W, S) and then, using a given reflection ordering, compute D(Γ) and sum up q^{\frac{1}{2} (l(v)−l(u)−l(Γ))}γ_{D(Γ)} for all such paths Γ. Furthermore, note that, by Proposition 3.8, γ_{D(Γ)} = 0 if Γ has two consecutive descents. Hence not all the paths Γ will be necessary in the computation. It should be noted that this algorithm has two crucial advantages over the one obtained from Theorem 2.8. First, the summation set is smaller. In fact, every directed path in B(W, S) is a chain, but not conversely, and the summation on the RHS of (8) is over all multichains from u to v (even though R_{C} = 0 for almost all multichains (see [5], Proposition 3.5), it is usually the case that R_{C} ≠ 0 if C is a chain). Second, the computation of the polynomials γ_{β} does not depend on the knowledge of the R-polynomials, while that of R_{C} does.

Since the computation of the polynomials {ĝ_{α}}_{α∈C} is simpler than that of {g_{α}}_{α∈C} (cfr. Theorem 3.4 and Proposition 3.5) it is natural to wonder whether one can compute the Kazhdan-Lusztig polynomials directly in terms of the former ones. This is indeed possible if we disregard higher degree terms.

Corollary 4.7 Let u, v ∈ W, u < v. Then

P_{u,v}(q) = ε_{u}ε_{v} ∑_{α∈C} q^{\frac{1}{2} (l(v)−l(u)−|α|)}c_{α}(u, v)D_{\frac{|α|−1}{2}} (ĝ_{α}) ,  (70)

and

P_{u,v}(q) = ε_{u}ε_{v} ∑_{α∈C} q^{\frac{1}{2} (l(v)−l(u)−|α|)}b_{α}(u, v)D_{\frac{|α|−1}{2}} (γ̂_{α}) .  (71)

Proof. This follows immediately by applying D_{\frac{l(v)−l(u)−1}{2}} to both sides of (66) and (67), and using iii) of Theorem 2.7, vii) of Proposition 2.1, (31) and (56). □

Note that, by Theorems 3.7 and 3.10, D_{\frac{|α|−1}{2}} (ĝ_{α}) and D_{\frac{|α|−1}{2}} (γ̂_{α}) both have strictly smaller degree than ĝ_{α} and γ̂_{α}. However, we have been unable to find recursion relations for the D_{\frac{|α|−1}{2}} (ĝ_{α})’s and the D_{\frac{|α|−1}{2}} (γ̂_{α})’s themselves. Thus, it seems that one still has to compute the ĝ_{α}’s and γ̂_{α}’s even though one is then only interested in their first ⌊\frac{|α|−1}{2}⌋ coefficients.

As stated in section 3, one of the most important properties of the polynomials {g_{α}}_{α∈C} and {γ_{β}}_{β∈C} is that their coefficients alternate in sign. This is important as it allows us to separate the positive and negative terms in the summations (66) and (67) (something which would be impossible to do from Theorem 2.8, since the signs of the coefficients of R_{C}(q) are not known, even in the case l(C) = 2, cfr., e.g., [2]), and thus obtain a completely combinatorial reformulation of the nonnegativity conjecture for Kazhdan-Lusztig polynomials (see, e.g., [15], p. 166, or [14], §7.9, p. 159).

Theorem 4.8 Let (W, S) be a Coxeter system. Then the nonnegativity conjecture fro Kazhdan-Lusztig polynomials holds for W if and only if

∑_{α∈C_{+}(j,u,v)} c_{α}(u, v)|\{S ∈ G_{|α|}(T (α)) : |S| = j − \frac{1}{2}(l(v) − l(u) − |α|)\}| ≥

∑_{α∈C_{−}(j,u,v)} c_{α}(u, v)|\{S ∈ G_{|α|}(T (α)) : |S| = j − \frac{1}{2}(l(v) − l(u) − |α|)\}|  (72)

for all u, v ∈ W, u < v, and j ∈ [0, \frac{1}{2}(l(v) − l(u) − 1)], where C_{+}(j, u, v) =^{def} \{α ∈ C : α_{2} + α_{4} + … ≡ j + \frac{1}{2}(l(v) − l(u) − |α|) (mod 2)\}, C_{−}(j, u, v) = C \ C_{+}(j, u, v), and

T (α) =^{def} {α_{1}, α_{1} + α_{2}, …, α_{1} + … + α_{l(α)−1}}.

Proof. This is an immediate consequence of (70) and Theorem 3.16. □

Note that both sides of (72) are nonnegative integers with a well defined combinatorial interpretation (see definitions (62) and (57)). Therefore it is quite possible that an injection can be found that would prove (72) combinatorially. Note that, by Proposition 3.12, the inequality (72) can be reformulated using binomial coefficients rather than balanced subsets. Also, an analogous result can be formulated using (71) instead of (70) in the proof of Theorem 4.8. We omit to state this since we don’t know any combinatorial interpretation or formula for the coefficients of the polynomials γ̂_{α}’s.

To give the reader a feeling for the inequalities (72) we illustrate them in detail for j = 1. Now, it follows from (57) that

|\{S ∈ G_{|α|}(T (α)) : |S| = 1\}| = \{ \begin{matrix}|α|, & if l(α) = 1, \\ 1, & if l(α) = 2 and α_{2} = 1, \\ 0, & otherwise, \end{matrix}  (73)

and

|\{S ∈ G_{|α|}(T (α)) : |S| = 0\}| = \{ \begin{matrix}1, & if l(α) = 1, \\ 0, & otherwise. \end{matrix}  (74)

Furthermore, it follows from (62) or Proposition 4.4 that c_{α}(u, v) = 0 unless |α| ≤ l(v) − l(u) and |α| ≡ l(v) − l(u) (mod 2). Therefore the only compositions that give non-zero contributions to the sums in (72) are (l(v) − l(u)), (l(v) − l(u) − 1, 1), and (l(v) − l(u) − 2). Of these three only (l(v) − l(u)) is in C_{−}(1, u, v), hence we obtain from (73), and (74) that the inequality (72) becomes, when j = 1,

c_{d−2}(u, v) + c_{d−1,1}(u, v) ≥ d  (75)

where d =^{def} l(v) − l(u). Note that c_{d−1,1}(u, v) equals the number of coatoms in [u, v] (i.e., |{x ∈ [u, v] : l(v)−l(x) = 1}|), as can be seen from Proposition 5.1 in the next section. We know from the proof of Theorem 4.8 that the inequality (75) holds if and only if [q](P_{u,v}) ≥ 0. This last inequality has been recently proved by Tagawa [21], and, independently, by Dyer ([13], p. 115).

5 Weight coefficients

Our main results show that further understanding of the Kazhdan-Lusztig polynomials can be achieved through further understanding of the polynomials {g_{α}}_{α∈C}, {γ_{α}}_{α∈C}, {ĝ_{α}}_{α∈C}, and {γ̂_{α}}_{α∈C}, and of the coefficients c_{α}(u, v) and b_{α}(u, v). We have studied the polynomials in section 3. In this section we study the coefficients c_{α}(u, v) and b_{α}(u, v). Our main result is a remarkable inequality satisfied by the c_{α}(u, v)’s (Theorem 5.7), which is interesting in its own right (Theorem 5.4).

We begin by noting the following easy consequence of Proposition 4.4.

Proposition 5.1 Let u, v ∈ W and (d_{1}, …, d_{r}) ∈ C_{l(v)−l(u)} (r ∈ P). Then

c_{d_{1},...,d_{r}}(u, v) = α([u, v]; {d_{1}, d_{1} + d_{2}, …, d_{1} + d_{2} + … + d_{r−1}})  (76)

and

b_{d_{1},...,d_{r}}(u, v) = β([u, v]; {d_{1}, d_{1} + d_{2}, …, d_{1} + d_{2} + … + d_{r−1}}).  (77)

Proof. (76) follows immediately from Proposition 4.4 and the fact that, by (3) and (4), R̃_{x,y}(q) is a monic polynomial of degree l(y) − l(x), for all x, y ∈ W. Now (77) follows from (76), (64), (1), and the Principle of Inclusion-Exclusion. □

The preceding result shows that the numbers c_{α}(u, v) and b_{α}(u, v) include as special cases the α and β rank-selected invariants of [u, v]. These invariants have been widely studied (see, e.g., [18], §3.12, and the references cited there).

There is one further simple but important property of the numbers b_{α}(u, v) and c_{α}(u, v). Recall that our definitions (62) and (63) assume that we are given a (fixed) reflection ordering <_{T} of T. However, Proposition 4.4 shows that c_{α}(u, v) (and hence b_{α}(u, v)) are in fact independent of the reflection ordering chosen to define them. This allows us to deduce the following result. Given a composition α ∈ C_{n} we denote by α̃ the complement of α in C_{n} (where we identify C_{n} with B_{n−1}, as indicated in section 2).

Proposition 5.2 Let (W, S) be a Coxeter system, u, v ∈ W, and α ∈ C. Then

b_{α}(u, v) = bα̃(u, v).  (78)

Proof. It is clear from the definition (see also, [13], Remark (2.4)(i)) that the reverse of a reflection ordering is again a reflection ordering. So (78) follows from the definition (63) and the fact that this definition is independent of the reflection ordering chosen. □

The preceding result implies, of course, corresponding identities for the c_{α}(u, v), which are obtained from (78) and (64) by Inclusion-Exclusion. For example, the fact that b_{3}(u, v) = b_{1,1,1}(u, v) is equivalent to the identity c_{1,1,1}(u, v) = c_{2,1}(u, v) + c_{1,2}(u, v), while the equality b_{2,1}(u, v) = b_{1,2}(u, v), is equivalent to c_{2,1}(u, v) = c_{1,2}(u, v). Even in these simple special cases these identities are absolutely non trivial from the point of view of Proposition 4.4.

We now start the proof of the main result of this section. We begin with the following simple remark on reflection orderings.

Lemma 5.3 Let (W, S) be a Coxeter system and s ∈ S. Then there is a reflection ordering ≤_{T} of T such that t ≤_{T} s for all t ∈ T.

Proof. Let I = {s}. Then T ∩ W_{I} = {s} while T \ W_{I} = T \ {s}. Applying Proposition 2.3 of [13] to I and J = ∅ we obtain that there exists a reflection ordering on T in which s comes first. But, as observed in the proof of Proposition 5.2, the reverse of a reflection ordering is again a reflection ordering and the result follows. □

Let y < z be an edge in the Hasse diagram of the Bruhat order of W. Then for every reduced expression ρ = (s_{i_{1}}, …, s_{i_{n}}) of z (so n = l(z)) there exists a unique j_{ρ} ∈ [n] such that (s_{i_{1}}, …, s_{i_{jρ−1}}, s_{i_{jρ+1}}, s_{i_{n}}) is a reduced expression of y (see, e.g., [14], Theorem 5.8, p.117). We let

τ(y, z) =^{def} l(z) − max{j_{ρ} : ρ ∈ R(z)}

and call τ(y, z) the type of the edge y < z (where we denote by R(z) the set of all reduced expressions of z). Note that τ(y, z) = 0 if and only if y^{−1}z ∈ S (i.e., if and only if y < z in the (right) weak order (see, e.g., [14], §5.9, p. 119)). For example, the types of the edges in the Hasse diagram of S_{3} are shown in Figure 3.

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

Figure 3.

Theorem 5.4 Let (W, S) be a Coxeter system, and x, y, z ∈ W be such that x ≤ y ≤ z. Then

q^{l(z)−l(y)}R̃_{x,y}(q) ≤ R̃_{x,z}(q),  (79)

(coefficientwise).

Proof. Since Bruhat order is graded (see, e.g., [14], Proposition 5.11, p. 122), the result will follow immediately if we can prove that

qR̃_{x,y}(q) ≤ R̃_{x,z}(q)  (80)

(coefficientwise), for all x, y, z ∈ W such that x ≤ y < z.

We will prove (80) by induction on τ(y, z). If τ(y, z) = 0 then y^{−1}z ∈ S. Let s =^{def} y^{−1}z, and choose a reflection ordering on T, <_{T}, such that s is last (this is possible by the previous lemma). Then, by Theorem 2.6, [q^{k}](R̃_{x,y}) equals the number of paths Γ ∈ B(x, y), of length k, such that D(Γ) = ∅. For each such path Γ = (x, x_{1}, …, x_{k−1}, y) the path (x, x_{1}, …, x_{k−1}, y, ys) has again empty descent set (since s comes last in our reflection ordering and x_{k} ≠ x_{k−1}s since x_{k−1} < x_{k}), has length k + 1, and goes from x to ys. Since this is clearly an injection there follows from Theorem 2.6 that [q^{k}](R̃_{x,y}) ≤ [q^{k+1}](R̃_{x,ys}), as desired.

Now let p =^{def} τ(y, z) and assume that p ≥ 1. Then there exists a reduced expres-

sion (s_{i_{1}}, …, s_{i_{n}}) of z (where n =^{def} l(z)) such that (s_{i_{1}}, …, s_{i_{n−p−1}}, s_{i_{n−p+1}}, …, s_{i_{n}}) is

a reduced expression of y. Let s =^{def} s_{i_{n}}, for brevity. Then s ∈ D(z), s ∈ D(y) (since p ≥ 1), and ys < zs. Furthermore, (s_{i_{1}}, …, s_{i_{n−1}}) is a reduced expression of zs, and (s_{i_{1}}, …, s_{i_{n−p−1}}, s_{i_{n−p+1}}, …, s_{i_{n−1}}) is a reduced expression of ys. Therefore

τ(ys, zs) ≤ l(zs) − (n − p) = τ(y, z) − 1.

There are now two cases to consider.

a) s ∈ D(x).

Then, by Theorem 2.3 and Proposition 2.4,

R̃_{x,z}(q) = R̃_{xs,zs}(q),  (81)
R̃_{x,y}(q) = R̃_{xs,ys}(q),  (82)

and xs ≤ ys < zs. But, by our induction hypothesis,

q R̃_{xs,ys}(q) ≤ R̃_{xs,zs}(q)  (83)

(coefficientwise), so (80) follows from (81), (82), and (83).

b) s ∉ D(x).

Then, by Theorem 2.3 and Proposition 2.4,

R̃_{x,z}(q) = R̃_{xs,zs}(q) + q R̃_{x,zs}(q),  (84)

R̃_{x,y}(q) = R̃_{xs,ys}(q) + q R̃_{x,ys}(q),  (85)

and x ≤ ys < zs. Also we have from our induction hypotheses that

q R̃_{x,ys}(q) ≤ R̃_{x,zs}(q)  (86)

(coefficientwise). If xs ≰ ys then R̃_{xs,ys}(q) = 0 and hence we conclude from (84), (85), and (86) that

qR̃_{x,y}(q) = q^{2}R̃_{x,ys}(q) ≤ q R̃_{x,zs}(q) ≤ R̃_{xs,zs}(q) + q R̃_{x,zs}(q) = R̃_{x,z}(q),

(all inequalities are coefficientwise), as desired. If xs ≤ ys then we conclude from our induction hypotheses that

q R̃_{xs,ys}(q) ≤ R̃_{xs,zs}(q) ,  (87)

and (80) follows from (84), (85), (86), and (87).

This concludes the induction step and hence the proof. □

Corollary 5.5 Let (W, S) be a finite Coxeter system, and x, y, u, v ∈ W be such that x ≤ u ≤ v ≤ y. Then

q^{l(y)−l(v)+l(u)−l(x)}R̃_{u,v}(q) ≤ R̃_{x,y}(q),  (88)

(coefficientwise).

Proof. Since x ≤ u ≤ y, and W is finite, there follows that w_{0}y ≤ w_{0}u ≤ w_{0}x (see, e.g., [14], §5.9, Ex. 3), where w_{0} denotes the longest element of W. By (4), Theorem 5.4 and Proposition 7.6 of [14] we therefore conclude that

q^{l(u)−l(x)}R̃_{u,y}(q) = q^{l(w_{0}x)−l(w_{0}u)}R̃_{w_{0}y,w_{0}u}(q) ≤ R̃_{w_{0}y,w_{0}x}(q) = R̃_{x,y}(q), (89)

and (88) follows from (89) and Theorem 5.4. □

It would be interesting to know if the preceding corollary holds also for infinite Coxeter groups. In this respect we should mention the following result, which is proved in an analogous way (choosing a reflection ordering in which the given s ∈ S comes first), to the base of the induction in the proof of Theorem 5.4.

Theorem 5.6 Let (W, S) be a Coxeter system, and x, y, z ∈ W be such that y ≤ z (in Bruhat order), and x ≤ y (in (right, say) weak order). Then

q^{l(y)−l(x)}R̃_{y,z}(q) ≤ R̃_{x,z}(q)

(coefficientwise). □

From Theorem 5.4 and Corollary 5.5 we deduce the main result of this section.

Theorem 5.7 Let (W, S) be a Coxeter system, x, y, u, v ∈ W be such that x ≤ u ≤ v ≤ y, and α_{1}, …, α_{r} ∈ N (r ∈ P). Then

c_{α_{1},...,α_{r}}(u, v) ≤ c_{α_{1},...,α_{r−1},α_{r}+l(y)−l(v)}(u, y).

Furthermore, if W is finite, then

c_{α_{1},...,α_{r}}(u, v) ≤ c_{α_{1}+l(u)−l(x),α_{2},...,α_{r−1},α_{r}+l(y)−l(v)}(x, y).

Proof. The two statements follow immediately from Theorem 5.4 and Corollary 5.5, respectively, using Propositions 4.3 and 4.4, and induction on r ∈ P. □

It would be interesting to know if the preceding result holds also for the b_{α}’s.

6 Inverse Kazhdan-Lusztig polynomials

In this section we briefly sketch how it is possible to obtain analogues of the results in §4 for the inverse Kazhdan-Lusztig polynomials. Recall (see, e.g., [14], §7.13, or [16], 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}  (90)

for all u, v ∈ W, u ≤ v.

There is an analogue of Theorem 2.8 for the inverse Kazhdan-Lusztig polynomials, which is obtained as follows. For any multichain a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} (r ∈ N) of W define a polynomial R_{a_{0},...,a_{r+1}}^{∗}(q) by letting

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)  (91)

(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),  (92)

if r = 0. The polynomial R_{a_{0},...,a_{r+1}}^{∗}(q) is called the dual R-polynomial of the multichain a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} (see [5], p. 392). Then the analogue of Theorem 2.8 is the following (see [5], Theorem 7.5).

Theorem 6.1 Let u, v ∈ W. Then

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

Using Theorem 3.4 and proceeding exactly as in the proof of Theorem 4.1 we then obtain the following analogue of it for the dual R-polynomial of a multichain.

Theorem 6.2 Let a_{0} ≤ a_{1} ≤ … ≤ a_{r} be a multichain in W. Then

R_{a_{0},a_{1},...,a_{r}}^{∗}(q) = ε_{a_{0}}ε_{a_{r}} ∑_{α_{1}≥0} … ∑_{α_{r}≥0} q^{\frac{l(ar)−l(a_{0})−α}{2}} ĝ_{α_{r},...,α_{1}}(q) ∏_{j=1}^{r}[q^{α_{j}}](R̃_{a_{j−1},a_{j}}) ,

where α =^{def} α_{1} + … + α_{r}. □

In other words, the preceding result says that the dual R-polynomial of a multichain is computed exactly as the R-polynomial of the same multichain but using ĝ_{α_{r},...,α_{1}}(q) instead of ĝ_{α_{1},...,α_{r}}(q).

The analogue of our main theorem (Theorem 4.5) is then the following. Given

α =^{def} (α_{1}, …, α_{r}) ∈ C we let α^{∗} =^{def} (α_{r}, …, α_{1}).

Theorem 6.3 Let u, v ∈ W, u < v. Then

P_{u,v}^{∗}(q) = ε_{u}ε_{v} ∑_{α∈C} q^{\frac{1}{2} (l(v)−l(u)−|α|)}c_{α}(u, v) g_{α^{∗}}(q),  (93)

and

P_{u,v}^{∗}(q) = ε_{u}ε_{v} ∑_{α∈C} q^{\frac{1}{2} (l(v)−l(u)−|α|)}b_{α}(u, v) γ_{α^{∗}}(q).□  (94)

Similarly, one obtains analogues of Corollaries 4.6 and 4.7.

References

[1] I. N. Bernstein, I. M. Gelfand, S. I. Gelfand, Shubert cells and cohomology of the spaces G/P, Russian Math. Surveys 28 (1973), 1-26.

[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] N. Bourbaki, Groupes et algèbres de Lie, Ch. 4-6, Hermann, Paris, 1968; Masson, Paris, 1981.

[4] F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., no.413, 1989.

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

[6] L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974.

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

[8] V. V. Deodhar, A note on subgroups generated by reflections in Coxeter groups, Arch. Math., 53 (1989), 543-546.

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

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

[11] M. Dyer, Reflection subgroups of Coxeter systems, J. Algebra, 135 (1990), 57-73.

[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] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no.29, Cambridge Univ. Press, Cambridge, 1990.

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

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

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

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

[19] R. P. Stanley, Log-concave and unimodal sequences in Algebra, Combinatorics and Geometry, Annals of the New York Academy of Sciences, 576 (1989), 500-534.

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

[21] H. Tagawa, On the non-negativity of the first coefficient of Kazhdan-Lusztig polynomials, J. Algebra, to appear.

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

School of Mathematics Institute for Advanced Study Princeton, NJ, 08540 U.S.A.