Upper and Lower Bounds for Kazhdan-Lusztig polynomials

Francesco Brenti^{1}

Abstract

We give upper and lower bounds for the Kazhdan-Lusztig polynomials of any Coxeter group W. If W is finite we prove that, for any k ≥ 0, the k-th coefficient of the Kazhdan-Lusztig polynomial of two elements u, v of W is bounded from above by a polynomial (which depends only on k) in l(v)−l(u). In particular, this implies the validity of Lascoux-Schutzenberger’s conjecture for all sufficiently long intervals, and gives supporting evidence in favor of the Dyer-Lusztig conjecture.

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., [13], 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 aim in this paper is to give upper and lower bounds for the coefficients of any Kazhdan-Lusztig (and inverse Kazhdan-Lusztig) polynomial of any Coxeter group and to study some consequences of these bounds. Our motivation for doing this comes from two conjectures of Kazhdan-Lusztig and Lascoux-Schutzenberger which assert, respectively, that these coefficients are always nonnegative (see, e.g., [14], p. 166) and that, if the polynomials have the maximum possible degree, then they are bounded from above by appropriate Eulerian numbers (see, [17], p. 249, or §2 for the precise statement of this conjecture). Our main result is that, if the group W is finite, then there exists a sequence of polynomials {s_{k}(q)}_{k∈N} ⊆ Z[q] (independent of W) such that the coefficient of q^{k} in the Kazhdan-Lusztig polynomial of a pair of elements u, v ∈ W is bounded in absolute value by s_{k}(l(v) − l(u)) (see Theorem 3.9). As a consequence of this result, we prove that Lascoux-Schutzenberger’s conjecture holds for all sufficiently long intervals (see Corollary 3.10), and we give supporting evidence in favor of the Dyer-Lusztig conjecture (see Corollary 3.11 and the comments following it, and §2 for the precise statement of this conjecture).

1Part of this work was carried out while the author was a member of the Institute for Advanced Study in Princeton, New Jersey, U.S.A., and was partially supported by NSF grant DMS 9304580 and by EC grant No. CHRX-CT93-0400.

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 sequel. In section 3 we prove our main results. In particular, we verify the conjecture of Lascoux-Schutzenberger for all sufficiently long intervals. In section 4 we briefly sketch how it is possible to obtain analogues of the results in section 3 for the inverse Kazhdan-Lusztig polynomials. Finally, in section 5, we discuss some conjectures and open problems that arise naturally from the present work.

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]. 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\}, and P(A) be the power set of A. 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 ∈ Q 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., [19], 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 [19], 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. 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.

We will follow [13] 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., [13], §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]. We call the elements of [u, v] at distance one from u (respectively, v) the atoms (respectively, coatoms) of [u, v], and we denote by a(u, v) and c(u, v) their number. So a(u, v) = |[u, v]_{1}| and c(u, v) = |[u, v]_{l(v)−l(u)−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}.

We denote by H(W) the Hecke algebra associated to W. Recall (see, e.g., [13], 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}  (1)

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, [13], 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 (1) and Proposition 2.1 (see [13], §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}(q), & if s ∉ D(u). \end{matrix}  (2)

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 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}} ) .  (3)

There is one other 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.4 Let u, v ∈ W. Then

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

A proof of the preceding result can be found, e.g., in [13], §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 [21], Corollary 6.7 and Example 6.9) and a proof can be found, e.g., in [13], §§7.9-11, or [14], §2.2.

Theorem 2.5 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. Note that parts iii) and iv) of Theorem 2.5 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.

There is a non-recursive way to express the Kazhdan-Lusztig polynomials in terms of the R-polynomials which is the fundamental tool that we will use in this paper. The following result first appeared in [6] (see Theorem 5.2) and we refer the reader to [6] for its proof.

Theorem 2.6 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)) (6)

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.

We will find it convenient to recall also the following two consequences of Theorem 2.6 (see [6], Corollaries 5.3 and 5.4, for their proofs). Given a poset P we denote by P^{∗} the order dual of P.

Corollary 2.7 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].

Corollary 2.8 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}^{∗}|

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

where α([u, v]^{∗}; {1, 3}) denotes the number of maximal chains of [u, v]_{{1,3}}^{∗}.

We illustrate Corollary 2.8 with an example. Let W = S_{5}, u = 14325, and v = 45312. Then l(v) − l(u) = 5, [u, v]_{1}^{∗} = {45132, 35412, 43512, 45213}, |[u, v]_{2}^{∗}| = 10, [u, v]_{3}^{∗} = {15342, 14532, 41523, 34152, 41352, 43125, 42315, 34215, 35124, 24513, 15423, 25314}, and R_{u,v}(q) = q^{5}−4q^{4}+7q^{3}−7q^{2}+4q−1. Therefore α([u, v]^{∗}; {1, 3}) = 32, ∑_{a∈[u,v]_{1}^{∗}}[q](R_{u,a}) = (−4)+(−4)+(−4)+(−4), ∑_{b∈[u,v]_{3}^{∗}}[q](R_{b,v}) = 2+3+3+3+2+3+2+3+3+3+3+2, and hence [q^{2}](P_{u,v}) = 7 + (−16) + 10 − 32 + 32 = 1.

Our aim in this work is to obtain upper and lower bounds for the coefficients of the Kazhdan-Lusztig polynomials of a Coxeter system. As mentioned in the Introduction, the motivation for doing this comes from the following two conjectures.

Conjecture 2.9 Let (W, S) be a Coxeter system and u, v ∈ W. Then [q^{k}](P_{u,v}) ≥ 0 for all k ∈ N.

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

Here A(n, k) (n, k ∈ N) denotes an Eulerian number (i.e., A(n, k) =^{def} |{σ ∈ S_{n} : |D(σ)| = k}|, for 0 ≤ k ≤ n−1 and n ∈ P, see, e.g, [7], §6.5, for further information about Eulerian numbers). For example, if we let A_{n}(q) =^{def} ∑_{k=0}^{n−1} A(n, k) q^{k} for n ∈ P, then we have that A_{1}(q) = 1, A_{2}(q) = 1 + q, A_{3}(q) = 1 + 4q + q^{2}, A_{4}(q) = 1 + 11q + 11q^{2} + q^{3}, A_{5}(q) = 1 + 26q + 66q^{2} + 26q^{3} + q^{4}, and A_{6}(q) = 1 + 57q + 302q^{2} + 302q^{3} + 57q^{4} + q^{5}. Note that equality can be achieved in Conjecture 2.10. For example, one can check from [12] that P_{1324,3412}(q) = A_{2}(q) and P_{145236,456123}(q) = A_{3}(q). It turns out that our main result also has applications to the following (apparently unrelated) conjecture.

Conjecture 2.11 Let (W_{1}, S_{1}) and (W_{2}, S_{2}) be two Coxeter systems and u, v ∈ W_{1}, z, w ∈ W_{2} be such that [u, v] ≅ [z, w] (as posets). Then P_{u,v}(q) = P_{z,w}(q).

Conjectures 2.9 and 2.10 first appeared in [14], p. 166, and [17], p. 249, respectively, while Conjecture 2.11 was made by Lusztig around 1979 ([18]) and by Dyer (see [13], §8.6, p.177). Conjecture 2.9 is currently known to be true in several important cases (see, e.g., [13], §7.12, p.164), as well as for k = 1 (see [22], and [11], p. 114). No partial results are known on Conjecture 2.10,while Conjecture 2.11 is known to be true if l(v) − l(u) ≤ 3 or if [u, v] is a lattice (see [6], Lemma 6.2 and Theorem 6.3). Our results give supporting evidence in favor of Conjecture 2.11 and of the fact that Conjecture 2.10 may actually hold for any finite Coxeter system, and suggest that Conjecture 2.9 is the hardest of the three.

Throughout this work (W, S) denotes a Coxeter system.

3 The main results

In this section we prove our main results. Namely, we give upper and lower bounds for the coefficients of Kazhdan-Lusztig polynomials. Since the notation involved in the derivation of these bounds is rather complicated, we treat in detail only the upper and lower bounds for the coefficients of q and q^{2}. This will make the main ideas of the argument stand out more clearly, and enable the interested reader to easily derive the corresponding bounds for the higher powers of q.

Our first step, by Corollaries 2.7 and 2.8, is to obtain bounds for the coefficients of q and q^{2} in the R-polynomials. However, in this case, it turns out to be no extra work to obtain bounds for the other coefficients as well.

To this end we define two functions F, G : N × N → Z inductively as follows. We let

F (k, n) =^{def} F (k, n − 1) + F (k − 1, n − 1) − min {0, G(k − 1, n − 2)} , (7)
G(k, n) =^{def} G(k, n − 1) + G(k − 1, n − 1) − max {0, F (k − 1, n − 2)} , (8)

if (k, n) ∈ N × N \ {(0, 0)}, (where G(k, n) =^{def} F (k, n) =^{def} 0 if k < 0 or n < 0), and

F (0, 0) =^{def} G(0, 0) =^{def} 1.  (9)

Proposition 3.1 Let (W, S) be a Coxeter system. Then

G(k, l(v) − l(u)) ≤ (−1)^{k}ε_{u}ε_{v}[q^{k}](R_{u,v}) ≤ F (k, l(v) − l(u)) ,  (10)

for all k ∈ N, and all u, v ∈ W such that u ≤ v.

Proof. We proceed by induction on l(v), (10) being clearly true for all k ∈ N and u ≤ v if l(v) = 0. So assume that l(v) > 0 and let u ∈ W be such that u ≤ v, and s ∈ D(v). If s ∈ D(u) then it follows from our induction hypotheses that

G(k, l(v) − l(u)) = G(k, l(vs) − l(us)) ≤ (−1)^{k}ε_{us}ε_{vs}[q^{k}](R_{us,vs})
≤ F (k, l(vs) − l(us)) = F (k, l(v) − l(u)),

for all k ∈ N, and the thesis follows from (2). If s ∉ D(u) then it follows again from our induction hypotheses that, by (7) and (8)

G(k, l(v) − l(u)) = G(k − 1, l(vs) − l(u)) + G(k, l(vs) − l(u))
−max {0, F (k − 1, l(vs) − l(us))}
≤ (−1)^{k}ε_{u}ε_{v}([q^{k−1}](R_{u,vs}) − [q^{k}](R_{u,vs}) + [q^{k−1}](R_{us,vs}))
≤ F (k − 1, l(vs) − l(u)) + F (k, l(vs) − l(u))
−min {0, G(k − 1, l(vs) − l(us))}
= F (k, l(v) − l(u)) ,

so the thesis follows from (2). □

An immediate consequence of the preceding result is the following.

Corollary 3.2 Let u, v ∈ W, u ≤ v. Then

1 ≤ (−1)^{l(v)−l(u)+1}[q](R_{u,v}) ≤ l(v) − l(u) ,  (11)

and

− (\begin{matrix}l(v)−l(u) \\ 2 \end{matrix}) ≤ (−1)^{l(v)−l(u)}[q^{2}](R_{u,v}) ≤ (\begin{matrix}l(v)−l(u) \\ 2 \end{matrix}) .  (12)

Proof. It is easily verified from the definitions (7), (8), and (9), by induction on k + n ∈ N, that G(1, n) = 1, F (1, n) = n, G(2, n) ≥ − (\begin{matrix}n \\ 2 \end{matrix}), and F (2, n) = (\begin{matrix}n \\ 2 \end{matrix}) for all n ≥ 1, so the result follows from Proposition 3.1. □

It is easy to see that both bounds on the RHS of (11) and (12) are best possible (take, e.g., W = S_{n}, u = e, and v = (1, 2, …, n), for n ≥ 2, or use Theorem 6.3 of [6]).

The preceding result, together with Corollaries 2.7 and 2.8 (and the observation that 2 ≤ [q](R_{u,v}) if u ≤ v and l(v) − l(u) = 3), implies the following bounds.

Corollary 3.3 Let u, v ∈ W, u ≤ v. Then

c(u, v) − l(v) + l(u) ≤ [q](P_{u,v}) ≤ c(u, v) − 1 ,  (13)

and

− (\begin{matrix}l(v)−l(u) \\ 2 \end{matrix}) − (l(v) − l(u) − 1) c(u, v) − |[u, v]_{3}^{∗}| ≤

≤ [q^{2}](P_{u,v}) − |[u, v]_{2}^{∗}| + 2|[u, v]_{3}^{∗}| − α([u, v]^{∗}; {1, 3}) ≤

≤ (\begin{matrix}l(v)−l(u) \\ 2 \end{matrix}) − c(u, v) .□  (14)

Taking u, v ∈ W, u ≤ v, be such that [u, v] does not contain any subinterval isomorphic (as a poset) to S_{3} shows (by Theorem 6.3 of [6]) that the bound on the LHS of (13) is best possible. However, we have been unable to find similar examples for the other bounds.

One problem with the preceding result is that the bounds that we have obtained can sometimes be hard to evaluate. In particular, it is difficult to compare these bounds with the conjectured ones. In order to do this it is necessary to obtain more explicit bounds. We have been able to do this only for finite Coxeter systems, thanks to the following result.

Proposition 3.4 Let (W, S) be a finite Coxeter system, and u, v ∈ W, u ≤ v. Then

c(u, v) ≤ 2|S|^{2} .  (15)

Proof. Assume first that (W, S) is irreducible. If |S| = 2 then (W, S) is dihedral and hence

c(u, v) ≤ 2 ,

which implies (15). If (W, S) is of type H_{4} then one can compute directly (using a computer) that

c(u, v) ≤ 12 ,

which again implies (15). If |S| ≥ 3 and (W, S) is not of type H_{4} then, by the classification of irreducible finite Coxeter systems (see, e.g., [3], or [13], Chapter 2 and §6.4), we conclude easily that

|T | ≤ 2|S|^{2}  (16)

where T is the set of reflections of (W, S). But it follows immediately from the definition of Bruhat order that

c(u, v) ≤ |T | ,  (17)

and hence (15) follows from (17) and (16).

Assume now that (W, S) is reducible. It is then well known (see, e.g., [13], Proposition 6.1, p. 129) that there exist irreducible (finite) Coxeter systems (W_{1}, S_{1}), …, (W_{r}, S_{r}) such that

W ≅ W_{1} × … × W_{r} ,

(as groups). In this case, it follows easily from the definition of Bruhat order that there exist u_{i}, v_{i} ∈ W_{i}, u_{i} ≤ v_{i}, for i = 1, …, r, such that

[u, v] ≅ [u_{1}, v_{1}] × … × [u_{r}, v_{r}],

(as posets). Therefore

c(u, v) = ∑_{i=1}^{r} c(u_{i}, v_{i}) .

Since (W_{i}, S_{i}) is irreducible there follows from what we have already proved that

c(u_{i}, v_{i}) ≤ 2|S_{i}|^{2} ,

for i = 1, …, r. Hence

c(u, v) ≤ ∑_{i=1}^{r} 2|S_{i}|^{2} ≤ 2 (∑_{i=1}^{r} |S_{i}|)^{2} = 2|S|^{2} ,

as desired. □

Note that the preceding result does not hold, in general, for infinite Coxeter systems. For example, if (W, {a, b, c}) is a universal Coxeter system (as defined, e.g., in [13]. §5.1, p. 106) and v_{n} =^{def} \underbrace{abcabc … abc}_{3n}, then c(e, v_{n}) = 3n, for all n ≥ 1.

We should mention that we believe that the bound given in Proposition 3.4 can be improved. For example, if one could somehow verify, or compute, that max{c(u, v) : u, v ∈ W } ≤ 9, 16, 49, 64 when W is of type H_{3}, F_{4}, E_{7}, and E_{8}, respectively, then the proof that we have given would imply a bound of |S|^{2} on the RHS of (15) in Proposition 3.4. However, (15) is enough to allow us to verify that Lascoux-Schutzenberger’s conjectured bounds hold, for the coefficients of q and q^{2}, (for any finite Coxeter group) except possibly in a few special cases. Before we can do this we need the following technical consequence of the preceding result. Given n, i ∈ N we let (n)_{i} =^{def} n(n − 1) … (n − i + 1), and (n)_{0} =^{def} 1.

Proposition 3.5 Let (W, S) be a finite Coxeter system and u, v ∈ W, u ≤ v. Then

|[u, v]_{i}^{∗}| ≤ 2^{i}((l(v) − l(u))_{i})^{2} ,  (18)

for all i ∈ N.

Proof. If i = 0 then (18) is clear. Now note that if (18) holds for i = 1 then it holds for all i ≥ 1 since

|[u, v]_{i}^{∗}| ≤ ∑_{a∈[u,v]_{i−1}^{∗}} c(u, a) ≤ ∑_{a∈[u,v]_{i−1}^{∗}} 2(l(a) − l(u)))^{2}
= 2(l(v) − l(u) − i + 1)^{2} |[u, v]_{i−1}^{∗}| .

To prove that (18) holds if i = 1 note that by Proposition 2.1 of [10] there exists a finite Coxeter system (W′, S′) and u′, v′ ∈ W′ such that [u′, v′] ≅ [u, v] (as posets) and |S′| ≤ l(v) − l(u). Therefore, by Proposition 3.4,

c(u, v) = c(u′, v′) ≤ 2|S′|^{2} ≤ 2(l(v) − l(u))^{2} ,

as desired. □

Note that, for i = 1, the degree of the polynomial in l(v) − l(u) on the RHS of (18) is best possible. For example, if u = 1 n + 1 … 2n − 1 2 3 … n 2n and v = n + 1 n + 2 … 2n 1 2 … n then l(v) − l(u) = n^{2} − (n − 1)^{2} = 2n − 1, but |[u, v]_{1}^{∗}| = n^{2}, as it is easy to check.

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

Theorem 3.6 Let (W, S) be a finite Coxeter system and u, v ∈ W, u ≤ v. Then

[q](P_{u,v}(q)) ≤ 2d^{2} − 1 ,  (19)

and

[q^{2}](P_{u,v}) ≤ (\begin{matrix}d \\ 2 \end{matrix}) + 4((d)_{2})^{2} + 2^{4}2^{3}((d)_{3})^{2},  (20)

where d =^{def} l(v) − l(u). In particular: i) l(v) − l(u) > 18 ⇒ [q](P_{u,v}) ≤ A (⌊\frac{1}{2} (l(v) − l(u) + 1)⌋; 1);

ii) l(v) − l(u) > 50 ⇒ [q^{2}](P_{u,v}) ≤ A (⌊\frac{1}{2} (l(v) − l(u) + 1)⌋; 2).

Proof. Both inequalities in (19) and (20) follow immediately from Corollary 3.3, Proposition 3.5, and the fact that

α([u, v]^{∗}; {1, 3}) = ∑_{a∈[u,v]_{3}^{∗}} c(a, v) ≤ ∑_{a∈[u,v]_{3}^{∗}} 2(l(v) − l(a))^{2} = 18|[u, v]_{3}^{∗}| ,

and

∑_{a∈[u,v]_{3}^{∗}} c(a, v) ≥ 2|[u, v]_{3}^{∗}|,

(by [2], (4.7)).

Now, it is well known (see, e.g., [7], Theorem C, §6.5), and easy to see, that A(n, 1) = 2^{n} − n − 1, and A(n, 2) = 3^{n} − 2^{n}(n + 1) + (\begin{matrix}n+1 \\ 2 \end{matrix}), for all n ∈ P, and the other two statements follow. □

Note that the inequality on the RHS of (19) fails if W is infinite. For example, if (W, {a, b, c}) is a universal Coxeter system (as defined, e.g., in [13], §5.1, p. 106) and u =^{def} abc abc … abc, v =^{def} uabc, then l(v) − l(u) = 3 but it is easy to verify that P_{u,v}(q) = 1 + l(v)q. Also note that the inequalities at the end of Theorem 3.6 fail in general. For example, if W = S_{5} and u = 14235, v = 45123, then l(v)−l(u) = 4 but P_{u,v}(q) = 1 + 2q, while if W = S_{6} and u = 154236, v = 564123, then l(v) − l(u) = 6 but P_{u,v}(q) = 1 + 2q^{2}.

It is clear that the same method that we have used so far extends to higher powers of q. However, the bounds that one obtains get more and more complicated as the powers get higher, and for this reason, as noted at the beginning of this section, we have decided to treat in detail only the cases of q and q^{2}. Nonetheless, it is easy to obtain qualitative results for the higher powers of q which are still good enough to imply the validity of Lascoux-Schutzenberger’s conjecture for all sufficiently long intervals, as we now show.

Define a sequence of polynomials \{\overline{R}_{k}(q)\}_{k∈N} ⊆ Z[q] inductively as follows. We let

\overline{R}_{0}(q) =^{def} 1,  \overline{R}_{1}(q) =^{def} q ,  (21)

and

(Δ\overline{R}_{k})(q) =^{def} \overline{R}_{k−1}(q) + \overline{R}_{k−1}(q − 1) ,  (22)
\overline{R}_{k}(0) =^{def} 0 ,  (23)

if k ≥ 2, where Δ is the (first) difference operator, (Δf)(q) =^{def} f(q + 1) − f(q) (see, e.g., [19], p. 36). So, for example, \overline{R}_{2}(q) = q^{2} − 2q, \overline{R}_{3}(q) = (2q^{3} − 12q^{2} + 19q)/3, and \overline{R}_{4}(q) = (q^{4} − 12q^{3} + 50q^{2} − 72q)/3. It is well known (see, e.g., [19], Proposition 1.4.2, p. 38), and also easy to see, that conditions (21), (22) and (23) uniquely define the polynomials \overline{R}_{k}(q) for all k ∈ N.

Proposition 3.7 Let (W, S) be a Coxeter system. Then

|[q^{k}](R_{u,v})| ≤ \overline{R}_{k}(l(v) − l(u))  (24)

for all u, v ∈ W, u ≤ v, and k ∈ N.

Proof. It is easily verified by induction on k + n ∈ N, using the definitions (7), (8), (22), and (23), that

−\overline{R}_{k}(n) ≤ G(k, n) ≤ F (k, n) ≤ \overline{R}_{k}(n)

for all k, n ∈ N, and the thesis follows from Proposition 3.1. □

Now let G =^{def} {(S, I) ∈ P(N) × P(N) : |S| = |I|, and S_{r+1} ≤ I_{r} − S_{r} ≤ S_{r} − 1,

for r = 1, …, |S|}, and, for k ∈ N, G_{k} =^{def} {(S, I) ∈ G : S ⊆ [k]}. We define a function C : G → N by letting

C(S, I) =^{def} ∏_{r=1}^{|S|} \overline{R}_{S_{r}+S_{r+1}−I_{r+1}}(I_{r} − I_{r+1}) ,

for (S, I) ∈ G. A consequence of Proposition 3.7, and of Theorem 2.6, is the following.

Theorem 3.8 Let (W, S) be a Coxeter system, and k ∈ N. Then

|[q^{k}](P_{u,v})| ≤ ∑_{(S,I)∈G_{k}} C(S, I)α([u, v]^{∗}; I)\overline{R}_{k−S_{1}}(l(v) − l(u) − I_{1})

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

Proof. By iii) of Theorem 2.5 the result clearly holds if l(v) − l(u) < 2k − 1. For S ⊆ [k] let G(S) =^{def} {I ∈ P(N) : (S, I) ∈ G}. Then, if 2k − 1 ≤ l(v) − l(u), we have from Theorem 2.6 and Proposition 3.7 that

|[q^{k}](P_{u,v})| ≤ ∑_{S⊆[k]} ∑_{I∈G(S)} ∑_{(a_{|S|},...,a_{1})∈M(([u,v]^{∗})_{I})} |∏_{r=0}^{|S|}[q^{S_{r}+S_{r+1}−I_{r+1}}](R_{a_{r},a_{r+1}})|
≤ ∑_{S⊆[k]} ∑_{I∈G(S)} ∑_{(a_{|S|},...,a_{1})∈M(([u,v]^{∗})_{I})} C(S, I)|[q^{I_{0}−S_{0}−S_{1}}](R_{a_{0},a_{1}})|
= ∑_{S⊆[k]} ∑_{I∈G(S)} α([u, v]^{∗}; I)\overline{R}_{I_{0}−S_{0}−S_{1}}(l(v) − l(u) − I_{1}) C(S, I)

where a_{0} =^{def} u, a_{|S|+1} =^{def} v, S_{0} =^{def} l(v) − l(u) − k, I_{0} =^{def} l(v) − l(a_{0}), and M(([u, v]^{∗})_{I}) denotes the set of all maximal chains in ([u, v]^{∗})_{I}, and the thesis follows. □

The preceding result, and Proposition 3.5, immediately imply the following one.

Theorem 3.9 There exists a sequence of polynomials {s_{i}(q)}_{i∈N} ⊆ Z[q] such that

|[q^{k}](P_{u,v})| ≤ s_{k}(l(v) − l(u))

for all k ∈ N, u, v ∈ W such that u ≤ v, and all finite Coxeter systems (W, S).

Proof. Fix k ∈ N. Then, since (W, S) is finite, we conclude from Proposition 3.5 that

α([u, v]^{∗}; I) ≤ ∏_{r=1}^{|I|} |[u, v]_{I_{r}}^{∗}| ≤ ∏_{r=1}^{|I|} 2^{I_{r}}((l(v) − l(u))_{I_{r}})^{2}

for any I ⊆ [l(v) − l(u)] ∪ {0}, and the thesis follows from Theorem 3.8. □

We can now prove that Lascoux-Schutzenberger’s conjecture holds (for any finite Coxeter system) for all sufficiently long intervals.

Corollary 3.10 There exists a sequence of constants {c_{i}}_{i∈N} ⊆ N such that

|[q^{k}](P_{u,v})| ≤ A(⌊\frac{1}{2}(l(v) − l(u) + 1)⌋; k)  (25)

for all finite Coxeter systems (W, S) and all k ∈ N, u, v ∈ W, such that l(v)−l(u) > c_{k}.

Proof. Fix k ∈ P. From Theorem 3.9 we know that

|[q^{k}](P_{u,v})| ≤ s_{k}(l(v) − l(u))  (26)

for all u, v ∈ W, u ≤ v. Now, it is well known (see, e.g., [7], Theorem B, §6.5, and Exercise 3, p. 292) that Eulerian polynomials are symmetric and unimodal. Hence

A (⌊\frac{1}{2} (l(v) − l(u) + 1)⌋; k) ≥ A (⌊\frac{1}{2} (l(v) − l(u) + 1)⌋; 1)  (27)

if 1 ≤ k ≤ ⌊\frac{1}{2} (l(v) − l(u) − 3)⌋. But it is also well known (see, e.g., [7], Theorem C, §6.5), and easy to see, that

A(n; 1) = 2^{n} − n − 1  (28)

if n ≥ 1. Hence (25) follows from (26), (27), and (28), and the fact that s_{k}(l(v)−l(u)) is a polynomial function of l(v) − l(u). □

Note that the above corollary is always “non-empty” since the constant c_{k} appearing in its statement depends only on k and not on the Coxeter system (W, S). Hence, for any given k ∈ N, there are infinitely many intervals that satisfy the hypotheses of Corollary 3.10.

We close this section by noting the following immediate consequence of Theorem 3.9 and part iii) of Theorem 2.5.

Corollary 3.11 There are only a finite number of Kazhdan-Lusztig polynomials of intervals of a given length of finite Coxeter systems. □

Note that the preceding corollary gives evidence in favor of Conjecture 2.11 since it is known (see [10], Corollary 2.2, and also [13], Theorem 8.6, p.177) that only finitely many posets (up to isomorphism) can occur as intervals of a given length in finite Coxeter systems (under Bruhat order). Hence Corollary 3.11 is a consequence of Conjecture 2.11.

4 Inverse Kazhdan-Lusztig polynomials

In this section we show how one can obtain analogues of the results in the previous section for the inverse Kazhdan-Lusztig polynomials. Recall (see, e.g., [13], §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}  (29)

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

We will use the following analogue of Theorem 2.6 for the inverse Kazhdan-Lusztig polynomials, (see [6], Theorem 7.6).

Theorem 4.1 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_{0} ≥ a_{1} ≥ … ≥ a_{|S|+1} from v to u 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. □

Again, it is convenient to write down explicitly the following two consequences of the preceding result (see also [6], Corollary 7.7).

Corollary 4.2 Let u, v ∈ W. Then

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

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

Corollary 4.3 Let u, v ∈ W. Then

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

Using these two results, and Corollary 3.2, we deduce the following analogue of Corollary 3.3 for the inverse Kazhdan-Lusztig polynomials.

Corollary 4.4 Let u, v ∈ W, u ≤ v. Then

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

and

− (\begin{matrix}l(v)−l(u) \\ 2 \end{matrix}) − (l(v) − l(u) − 1)a(u, v) − |[u, v]_{3}| ≤

≤ [q^{2}](P_{u,v}^{∗}) − |[u, v]_{2}| + 2|[u, v]_{3}| − α([u, v]; {1, 3}) ≤

≤ (\begin{matrix}l(v)−l(u) \\ 2 \end{matrix}) − a(u, v).□

Again, taking u, v ∈ W, u ≤ v, be such that [u, v] does not contain any subinterval isomorphic to S_{3} shows (by Theorem 7.8 of [6]) that the bound on the LHS of (30) is best possible.

Reasoning as in the proof of Theorem 3.8, but using Theorem 4.1 and the well known fact (see, e.g., [6], Theorem 7.1) that deg(P_{u,v}^{∗}) ≤ \frac{1}{2}(l(v) − l(u) − 1) for u, v ∈ W, u < v, instead of Theorems 2.6 and 2.5, yields the following analogue of Theorem 3.8 (we omit the details).

Theorem 4.5 Let (W, S) be a Coxeter system, and k ∈ N. Then

|[q^{k}](P_{u,v}^{∗})| ≤ ∑_{(S,I)∈G_{k}} C(S, I) α([u, v]; I)\overline{R}_{k−S_{1}}(l(v) − l(u) − I_{1})

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

It is of course possible to deduce also, in a similar way, analogues of Theorems 3.6 and 3.9 and Corollary 3.10. This, however, turns out to be a fruitless endeavor. In fact, all these results hold for finite Coxeter groups and the reader can check that the analogues that one would obtain coincide with the results themselves using the well known facts (see, e.g., [13], Proposition 7.13, and §5.9) that P_{u,v}^{∗}(q) = P_{w_{0}v,w_{0}u}(q) and [u, v]^{∗} ≅ [w_{0}v, w_{0}u] (as posets) for all u, v ∈ W, if W is finite with longest element w_{0}.

5 Open Problems

In this section we discuss some open problems that arise naturally from the present work. The approach that we have used in this paper is to obtain upper and lower bounds for the R-polynomials and then to use Theorems 2.6 and 4.1 to “transfer” these bounds to the Kazhdan-Lusztig polynomials and their inverses. This naturally raises the question of obtaining sharp upper and lower bounds for the R-polynomials. Despite the fact that these polynomials satisfy simple recursions (see (2)) and that several combinatorial descriptions are known for them (see, e.g., [8], [10], and, for the case of symmetric groups, [5]), this does not seem to be an easy goal to attain. In particular, we have been unable to decide the following problems, which we believe to be of some interest and rather natural.

Problem 5.1 Let (W, S) be a Coxeter system. Is it true that

|[u, v]_{i}^{∗}| ≥ ε_{u}ε_{v}(−1)^{i}[q^{i}](R_{u,v})  (31)

for all u, v ∈ W, and i = 0, …, l(v) − l(u)?

Problem 5.2 Let (W, S) be a Coxeter system. Is it true that

ε_{u}ε_{v}(−1)^{i}[q^{i}](R_{u,v}) ≤ (\begin{matrix}l(v)−l(u) \\ i \end{matrix})  (32)

for all u, v ∈ W, and i = 0, …, l(v) − l(u)?

Problem 5.1 has been already mentioned in [6] (see eq.(39) and the comments following it). Note that, by Corollary 2.7, Problem 5.1 for i = 1 is equivalent to Conjecture 2.9 for k = 1. Therefore, the answer to Problem 5.1 is yes in this case by recent results of Tagawa and Dyer (see [22], and [11], p. 114). Problem 5.2 is naturally suggested by Corollary 3.2. Note that if [u, v] does not contain any subinterval isomorphic to S_{3} then, by Theorem 6.3 of [6], equality holds in (32) for all i = 0, …, l(v) − l(u). Therefore the bound given in (32) is best possible if it does hold.

It is curious to note that, while it is difficult to obtain sharp upper bounds for the R-polynomials, this is very easy to do for the R̃-polynomials (see (3)). For n ∈ N define a polynomial F_{n}(q) inductively as follows. We let

F_{0}(q) =^{def} 1,  F_{1}(q) =^{def} q,  F_{2}(q) =^{def} q^{2}

and

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

if n ≥ 3. The polynomials F_{n}(q) are known as the q-Fibonacci numbers, and have been widely studied (see, e.g., [16], and the references cited there). We then have the following result. Proposition 5.3 Let (W, S) be a Coxeter system, and u, v ∈ W, u ≤ v. Then

R̃_{u,v}(q) ≤ F_{l(v)−l(u)}(q)  (33)

(coefficientwise), and this bound is best possible. Proof. We prove (33) by induction on l(v), (33) being clear if v = e. Let v ∈ W be such that l(v) ≥ 1 and s ∈ D(v). Then from (2), (3), and our induction hypothesis we conclude that

R̃_{u,v}(q) = R̃_{us,vs}(q) ≤ F_{l(vs)−l(us)}(q) = F_{l(v)−l(u)}(q)

if s ∈ D(u), and

R̃_{u,v}(q) = qR̃_{u,vs}(q) + R̃_{us,vs}(q)
≤ qF_{l(vs)−l(u)}(q) + F_{l(vs)−l(us)}(q)
= qF_{l(v)−l(u)−1}(q) + F_{l(v)−l(u)−2}(q)
= F_{l(v)−l(u)}(q),

if s ∉ D(u), and (33) holds.

To prove that the bound is sharp let (W, {a, b}) be a “universal” Coxeter system (as defined, e.g., in [9]). Then it is easy to see, by induction on l(v), that R̃_{u,v}(q) = F_{l(v)−l(u)}(q) for all u, v ∈ W, u ≤ v. □

Note that, by (3), any bounds on R̃_{u,v} yield corresponding bounds on R_{u,v}. For example, it is easy to verify (using Proposition 2.3) that the following holds.

Proposition 5.4 Let (W, S) be a Coxeter system and u, v ∈ W, u ≤ v. Then

− ∑_{i=0}^{⌊ \frac{m−1}{2} ⌋}[q^{d−4i−2}](R̃_{u,v}) (\begin{matrix}d−4i−2 \\ j−2i−1 \end{matrix}) ≤ ε_{u}ε_{v}(−1)^{j}[q^{j}](R_{u,v}) ≤ ∑_{i=0}^{⌊ \frac{m}{2} ⌋}[q^{d−4i}](R̃_{u,v}) (\begin{matrix}d−4i \\ j−2i \end{matrix})

(34)

where d =^{def} l(v) − l(u), and m =^{def} min{j, d − j}, for j = 0, …, d. □

However, the sharp bounds given by Proposition 5.3 do not yield, when substituted into (34), sharp bounds for the coefficients of the R-polynomials.

Note that while Proposition 5.3 gives a tight upper bound on the coefficients of R̃_{u,v}(q), it does not characterize the R̃-polynomials (and hence R-polynomials) of Bruhat intervals of a given length. For example, it is known (see, e.g., [8], Proposition 5.3, or [6], Proposition 6.1) that if [q^{l(v)−l(u)−2i}](R̃_{u,v}) ≠ 0 then [q^{l(v)−l(u)−2j}](R̃_{u,v}) ≠ 0 for all 0 ≤ j ≤ i. However, even this additional condition does not characterize R̃-polynomials. For example, 2q^{2} +q^{4} +q^{6} is not the R̃-polynomial of any Bruhat interval, as it is easy to verify. In this respect, we feel that the following holds. Recall that a polynomial P (q) =^{def} ∑_{i=0}^{d} a_{i}q^{i} ∈ R[q] is said to be log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for i = 1, …, d − 1 (we refer the reader to [4] or [20] for further information about log-concave polynomials).

Conjecture 5.5 Let (W, S) be a Coxeter system and u, v ∈ W. Then R̃_{u,v}(q) is log-concave.

Acknowledgements. I would like to thank Mark Van Leuween for carrying out the computer computation mentioned in the proof of Proposition 3.4.

References

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

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

[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, Combinatorial properties of the Kazhdan-Lusztig R-polynomials for S_{n}, Adv. in Math., to appear.

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

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

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

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

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

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

[12] M. Goresky, Kazhdan-Lusztig polynomials for classical groups, Northeastern University Mathematics Dept., [no date].

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

[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] S. T. Klein, Combinatorial representation of generalized Fibonacci numbers, Fibonacci Quart., 29 (1991), 124-131.

[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] G. Lusztig, private communication, September 1993.

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

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

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

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

Mathematical Sciences Research Institute 1000 Centennial Drive Berkeley, CA 94720-5070 U.S.A.