Combinatorial Properties of the Kazhdan-Lusztig R-polynomials for S_{n}

Francesco Brenti^{1} Dipartimento di Matematica Universitá degli Studi di Perugia Via Vanvitelli 1 I-06123 Perugia, Italy

Abstract

We point out a deep and surprising connection between the Kazhdan-Lusztig R-polynomials for S_{n} and the enumeration and combinatorics of increasing subsequences in permutations. This leads to a simple combinatorial recurrence and to several new closed formulas for these polynomials.

1 Introduction

In their fundamental paper [18] Kazhdan and Lusztig defined, for every Coxeter group W, a family of polynomials, indexed by pairs of elements of W, which have become known as the Kazhdan-Lusztig polynomials of W (see, e.g., [16], Chap. 7). These polynomials are intimately related to the Bruhat order of W and to the algebraic geometry of Schubert varieties, and have proven to be of fundamental importance in representation theory.

In order to prove the existence of these polynomials Kazhdan and Lusztig defined another family of polynomials (see [18], §2) which are intimately related to the multiplicative structure of the Hecke algebra associated to W. These polynomials are now known as the R-polynomials of W (see, e.g., [16], §7.5) and their importance stems mainly from the fact that their knowledge is equivalent to that of the Kazhdan-Lusztig polynomials.

Our aim in this work is to study some combinatorial properties of the R-polynomials of symmetric groups. More precisely, we point out a surprising connection between them and the enumeration and combinatorics of increasing subsequences in permutations. This leads to a simple combinatorial recurrence for computing these polynomials which in turn yields some new formulas for them. As a consequence of this recurrence, for example, we obtain a simple poset-theoretic condition on the interval determined by two elements in Bruhat order which insures that their R-polynomial is a power of q − 1. This, in turn, implies an interesting connection between the Kazhdan-Lusztig polynomials of these intervals and generalized h-vectors.

1This work was carried out while the author was a member of the Institute Mittag-Leffler in Djursholm, Sweden.

The organization of the paper is as follows. In the next section we recall some basic definitions, notation, and results, both of an algebraic and combinatorial nature, that will be used in the rest of this work. In section 3 we prove our main result (Corollary 3.9). This gives a simple combinatorial recurrence, defined in terms of increasing subsequences of permutations, for computing the R-polynomials of symmetric groups. Finally, in section 4, we apply our main result to the explicit computation of Kazhdan-Lusztig and R-polynomials. More precisely, we derive a combinatorial formula for the R-polynomials (Theorem 4.1) and we single out some families of pairs of elements of S_{n} for which the corresponding R-polynomial has a simple closed form (Theorems 4.6 and 4.9). As a special case, we obtain the result that if the interval between two permutations in Bruhat order is a lattice then the corresponding R-polynomial is just a power of q − 1 (Corollary 4.10), and the corresponding Kazhdan-Lusztig polynomial is the g-polynomial of the dual interval (Theorem 4.11). We also obtain sufficient conditions on two permutations so that their Kazhdan-Lusztig and R-polynomial factor (Theorem 4.4) and obtain as a consequence the result that Kazhdan-Lusztig and R-polynomials of symmetric groups are closed under products (Corollary 4.5).

The way in which our main result was discovered deserves a few words of comment. In October of 1991 Boris Shapiro attracted the author’s attention to some polynomials arising from the computation of Euler characteristics of links of Schubert cells in the flags manifold (see [22]). These polynomials are naturally indexed by permutations and the main result of [22] is a combinatorial rule for computing them. Later Anders Björner suggested (and Boris Shapiro proved using topological arguments, see [23]) that these polynomials are the R-polynomials corresponding to upper intervals of the Bruhat order of S_{n}. Spurred by this I tried to generalize the combinatorial rule appearing in [22] and was thus led to the definition of the R̃-polynomials (see (19) ) and then to the proof of the equivalence of these and the R-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}, and Z be the set of integers; for a ∈N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). Given n, m ∈ P, n ≤ m, we let [n, m] =^{def} [m] \ [n − 1]. We write S = {a_{1}, …, a_{r}}_{<} to mean that S = {a_{1}, …, a_{r}} and a_{1} < … < a_{r}. The cardinality of a set A will be denoted by |A|. Given a polynomial P (q), and i ∈ N, we will denote by [q^{i}](P (q)) the coefficient of q^{i} in P (q).

Given a set T we will let S(T) be the set of all bijections π : T → T, and

S_{n} =^{def} S([n]). If σ ∈ S(T) and T =^{def} {t_{1}, …, t_{r}}_{<} ⊆ P then we write σ = σ_{1} … σ_{r}

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

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

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

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

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

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

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

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

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

We will follow [16] 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

d(σ) = |D(σ)| .

We call D(σ) the descent set of σ and say that σ has d(σ) descents. We denote by e the identity of W, and we let T =^{def} {σsσ^{−1} : σ ∈ W, s ∈ S}. If A ⊆ W and x ∈ W we let A x =^{def} {wx : w ∈ A}. We will always assume that W is partially ordered by (strong) Bruhat order. Recall (see, e.g., [16], §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. It is well known (see, e.g., [3], 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., [16], Chap.

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

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

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

Proposition 2.1 Let y ∈ W. Then

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

where R_{x,y}(q) ∈ Z[q].

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

Theorem 2.2 Let x, y ∈ W and s ∈ D(y). Then

R_{x,y}(q) = \{ \begin{matrix}R_{xs,ys}(q), & if s ∈ D(x), \\ qR_{xs,ys}(q) + (q − 1)R_{x,ys}, & if s ∉ D(x). \end{matrix}  (4)

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

Even though our interest in this work is mainly in the R-polynomials, some of our results have consequences also for the Kazhdan-Lusztig polynomials, which we now define. The following result is not hard to prove (and, in fact, holds in much greater generality, see [27], Corollary 6.7 and Example 6.9) and a proof can be found, e.g., in [16], §§7.9-11, or [18], §2.2.

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

i) P_{x,y}(q) = 0 if x ≰ y;

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

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

iv)

q^{l(y)−l(x)} P_{x,y} (\frac{1}{q}) = ∑_{x≤z≤y} R_{x,z}(q) P_{z,y}(q) ,  (5)
if x ≤ y.

The polynomials P_{x,y}(q) defined by the preceding theorem are called the Kazhdan-Lusztig polynomials of W. Note that parts iii) and iv) of Theorem 2.3 actually yield an inductive procedure to compute the polynomials P_{x,y}(q) for all x, y ∈ W, taking parts i) and ii) as initial conditions. The polynomials P_{x,y}(q) have been the subject of considerable study, and we refer the reader to, e.g., [16], Chapter 7, for further information about them.

The object of this work is to study some combinatorial properties of the Rpolynomials for the symmetric groups. Therefore, from now on we will let W = S_{n} and S = {s_{1}, …, s_{n−1}} where s_{i} =^{def} (i, i + 1), for i = 1, …, n − 1, and we will say that p(q) ∈ Z[q] is an R-polynomial (respectively, a Kazhdan-Lusztig polynomial) if there are n ∈ P and σ, τ ∈ S_{n} such that p(q) = R_{σ,τ}(q) (respectively, P_{σ,τ}(q)). We will often find it convenient to identify S(T) with S_{|T |} for T ⊆ P. We will do this by identifying t_{i} with i, for i = 1, …, r, if {t_{1}, …, t_{r}}_{<} =^{def} T. So, for example,

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

It is clear from (3), Proposition 2.1, and Theorem 2.2 that the R-polynomials depend heavily on the Bruhat order, the length function, and descent sets. Therefore, we will find it useful to have combinatorial descriptions of these objects for S_{n}. The following result is well known and a proof can be found, e.g., in [21], Chapter 1.

Proposition 2.4 Let σ ∈ S_{n}, and i ∈ [n − 1]. Then:

i) l(σ) = |{(a, b) ∈ [n] × [n] : a < b, σ(a) > σ(b)}|;

ii) s_{i} ∈ D(σ) if and only if σ(i) > σ(i + 1).

For example, if σ = 615243 then l(σ) = 9 and D(σ) = {(1, 2), (3, 4), (5, 6)}. The following characterization of the Bruhat order of S_{n} is also well known, and will be used repeatedly in this work. We refer the reader to, e.g., [21], Chapter 1, for a proof. For σ ∈ S_{n}, and i ∈ [n], let

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

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

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

3 R-polynomials and increasing subsequences

In this section we derive our main result. This gives a simple combinatorial recurrence for the R-polynomials in terms of increasing subsequences of permutations.

We start by studying some basic combinatorics of increasing subsequences in a permutation. These results will be useful later on in our study of the R-polynomials. Let σ ∈ S_{n}, and s ∈ S. For a, b, i, j ∈ [n] we let

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

C_{i,j}(σ; s) =^{def} {w ∈ C_{i,j}(σ) : s ∈ D(wσ)} ,

C(σ) =^{def} ⋃_{1≤i<j≤n} C_{i,j}(σ) ,

and

T_{σ}[i, j; a, b] =^{def} {r ∈ [n] : i < r < j, a < σ(r) < b} .

Given w = (σ(i_{k}), …, σ(i_{1})) ∈ C_{i,j}(σ) we let

n(w, σ) =^{def} ∑_{r=1}^{k−1} |T_{σ}[i_{r}, i_{r+1}; σ(i_{r}), σ(j)]| ,  (7)
m(w, σ) =^{def} ∑_{r=1}^{k−1} |T_{σ}[i_{r}, i_{r+1} ; σ(i_{r+1}), σ(j)]| ,  (8)

and

p(w, σ) =^{def} ∑_{r=1}^{k−1}(k − 1 − r)|T_{σ}[i_{r}, i_{r+1}; σ(i_{r+1}), σ(j)]| .  (9)

We also let k(σ) be the length of the longest cycle of σ, and F (σ) be the set of fixed points of σ. For example, if σ = 215496378 then k(σ) = 5, F (σ) = {4, 6}, T_{σ}[2, 6; 4, 8] = {3}, C_{1,6}(σ) = {(6, 2), (6, 5, 2), (6, 4, 2)}, and if w = (8, 6, 4, 2) ∈ C_{1,9}(σ) then n(w, σ) = 1 + 0 + 1 = 2, m(w, σ) = 1 + 0 + 0 = 1, and p(w, σ) = 2 · 1 + 1 · 0 + 0 · 0 = 2. Note that C_{i,j}(σ) ≠ ∅ if and only if i ≤ j and σ(i) ≤ σ(j).

We begin by investigating some properties of the sets C_{i,j}(σ).

Proposition 3.1 Let σ ∈ S_{n}, and w ∈ C(σ). Then:

i) σ < w σ;

ii) l(w σ) − l(σ) = 2n(w, σ) + k(w) − 1.

Proof. Let w =^{def} (σ(i_{k}), …, σ(i_{1})) ∈ C(σ) and let, for convenience, t_{r} =^{def} (σ(i_{k}), σ(i_{r})) for r = 1, …, k − 1. Then, clearly,

w σ = t_{1} t_{2} … t_{k−1} σ  (10)

and since σ(i_{k}) > σ(i_{r}) and i_{r} < i_{k}, for r = 1, …, k − 1, we have that

l(t_{r} t_{r+1} … t_{k−1} σ) − l(t_{r+1} … t_{k−1} σ) = 2|T_{σ}[i_{r}, i_{r+1}; σ(i_{r}), σ(i_{k})]| + 1 ,  (11)

for r = 1, …, k − 1, and i) follows. Summing (11) for r = 1, …, k − 1 and using (7) and (10) yields ii), as desired. □

A little more involved is the next property, which will be used in the proof of Theorem 4.9.

Proposition 3.2 Let σ ∈ S_{n}, and i, j ∈ [n] be such that C_{i,j}(σ) ≠ ∅. Then there exists a unique w ∈ C_{i,j}(σ) such that n(w, σ) = 0.

Proof. We may assume that i < j and σ(i) < σ(j). Now let i_{1} =^{def} i and

i_{r+1} =^{def} \{ \begin{matrix}min (T_{σ}[i_{r}, j + 1; σ(i_{r}), σ(j) + 1]), & if i_{r} < j and σ(i_{r}) < σ(j), \\ j, & otherwise. \end{matrix} (12)

for r = 1, 2, . . .. Then, clearly

i = i_{1} < i_{2} < … < i_{k} = j ,  (13)

and

σ(i) = σ(i_{1}) < σ(i_{2}) < … < σ(i_{k}) = σ(j)  (14)

where k =^{def} min{r ∈ P : i_{r} = j}. Therefore w_{0} =^{def} (σ(i_{k}), …, σ(i_{1})) ∈ C_{i,j}(σ). Furthermore, for any r ∈ [k − 1] we have that

T_{σ}[i_{r}, i_{r+1}; σ(i_{r}), σ(j)] = ∅ ,

(for if s ∈ T_{σ}[i_{r}, i_{r+1} : σ(i_{r}), σ(j)] then s < i_{r+1} and s ∈ T_{σ}[i_{r}, j + 1; σ(i_{r}), σ(j) + 1], which contradicts (12)). Hence, by (7), n(w_{0}, σ) = 0.

Now let w =^{def} (σ(j_{m}), …, σ(j_{1})) be such that w ∈ C_{i,j}(σ) and n(w, σ) = 0. Then

i = j_{1} < j_{2} < … < j_{m} = j ,  (15)
σ(i) = σ(j_{1}) < σ(j_{2}) < … < σ(j_{m}) = σ(j) ,  (16)

and, by (7),

T_{σ}[j_{r}, j_{r+1}; σ(j_{r}), σ(j)] = ∅  (17)

for r = 1, …, m − 1. We now claim that i_{r} = j_{r} for r = 1, …, min (k, m). We will prove this by induction on r, the claim being clearly true if r = 1. So let t ∈ [min (k, m) − 1] and assume that i_{r} = j_{r} for r = 1, …, t. Then from (15) and (16) there follows that j_{t+1} ∈ T_{σ}[i_{t}, j + 1; σ(i_{t}), σ(j) + 1]. This, by (12), (13), and (14), implies that

i_{t+1} ≤ j_{t+1} .

Now, if i_{t+1} < j_{t+1}, then by (13), (14), and our induction hypothesis we have that

i_{t+1} ∈ T_{σ}[j_{t}, j_{t+1}; σ(j_{t}), σ(j)] ,

which contradicts (17). Therefore i_{t+1} = j_{t+1} and this concludes the induction step and proves our claim. In particular, this shows that i_{min(k,m)} = j_{min(k,m)} = j and hence, by (13) and (15), that k = m. Hence w = w_{0} and this completes the proof. □

We now define a distance on S_{n} which will play a crucial role in all that follows. For σ, τ ∈ S_{n} we let

d(σ, τ) =^{def} max {i ∈ [n] : σ^{−1}(i) ≠ τ^{−1}(i)} ,  (18)

(where max{∅} =^{def} 0). So, for example, d(198265374 , 298461357) = max {1, 2, 5, 7, 4} = 7, and d(σ, τ) ≠ 1 for all σ, τ ∈ S_{n}.

The next result shows that the function d : S_{n} × S_{n} → N just defined is indeed a distance on S_{n}, and that it is invariant under right translations.

Proposition 3.3 For all σ, τ, w ∈ S_{n} we have that:

i) d(σ, τ) = 0 if and only if σ = τ;

ii) d(σ, τ) = d(τ, σ);

iii) d(σ, τ) ≤ d(σ, w) + d(w, τ);

iv) d(σ w, τ w) = d(σ, τ).

Proof. i), ii), and iv) are clear. To prove iii) let j =^{def} d(σ, τ) and assume j > 0. Then σ^{−1}(j) ≠ τ^{−1}(j) and hence either σ^{−1}(j) ≠ w^{−1}(j) or w^{−1}(j) ≠ τ^{−1}(j). Therefore either d(σ, w) ≥ j or d(w, τ) ≥ j and hence

d(σ, τ) ≤ max {d(σ, w), d(w, τ)} ,

and iii) follows. □

The next result gives what are for us the crucial properties of the distance function. Proposition 3.4 Let σ, τ ∈ S_{n} be such that σ < τ. Then:

i) τ^{−1}(d(σ, τ)) < σ^{−1}(d(σ, τ));

ii) σ(τ^{−1}(d(σ, τ))) < d(σ, τ). Proof. By the definition of the Bruhat order it is clearly enough to prove i) when τ = (σ(i), σ(j))σ with i < j and σ(i) < σ(j). In this case

d(σ, τ) = max {σ(i), σ(j)} = σ(j) ,

and therefore

τ^{−1}(d(σ, τ)) = τ^{−1}(σ(j)) = σ^{−1}(σ(i)) = i < j = σ^{−1}(σ(j)) = σ^{−1}(d(σ, τ)) , as desired.

To prove ii) let k =^{def} σ(τ^{−1}(d(σ, τ))). Then σ^{−1}(k) = τ^{−1}(d(σ, τ)) and hence, by (18), k ≠ d(σ, τ). But if k > d(σ, τ) then, by (18), σ^{−1}(k) = τ^{−1}(k) and hence τ^{−1}(k) = τ^{−1}(d(σ, τ)) which is impossible since k ≠ d(σ, τ). Therefore k < d(σ, τ), as desired. □

We are now ready to define, in terms of increasing subsequences, some polynomials which will turn out to be, essentially, the R-polynomials for S_{n}. For σ, τ ∈ S_{n} we define a polynomial R̃_{σ,τ}(t) by the following recurrence:

R̃_{σ,τ}(t) =^{def} \{ \begin{matrix}0, & if σ ≰ τ, \\ ∑_{w∈C_{τ^{−1}(d),σ^{−1}(d)}(σ)}t^{k(w)−1} R̃_{w σ,τ}(t), & if σ < τ, \\ 1, & if σ = τ, \end{matrix}  (19)

where d =^{def} d(σ, τ). Note that, by Proposition 3.4, C_{τ^{−1}(d),σ^{−1}(d)}(σ) ≠ ∅ if σ < τ, and, by Proposition 3.1, l(τ) − l(w σ) < l(τ) − l(σ) for all w ∈ C_{τ^{−1}(d),σ^{−1}(d)}(σ), so that (19) inductively defines the polynomials R̃_{σ,τ}(t) for all σ, τ ∈ S_{n}.

We illustrate the definition with an example. Let σ = 1342 and τ = 4321, then applying (19) repeatedly we have that

R̃_{1342,4321}(t) = t R̃_{4312,4321}(t) + t^{2} R̃_{4132,4321}(t)
= t^{2} R̃_{4321,4321}(t) + t^{3} R̃_{4312,4321}(t)
= t^{2} + t^{4} R̃_{4321,4321}(t)
= t^{2} + t^{4} .

It is a general fact that the polynomials R̃_{σ,τ}(t) are, essentially, polynomials in t^{2}. More precisely, we have the following result.

Proposition 3.5 For σ, τ ∈ S_{n}, σ ≤ τ, there exists a unique polynomial Q_{σ,τ}(t) such that

R̃_{σ,τ}(t) = \{ \begin{matrix}Q_{σ,τ}(t^{2}), & if l(τ) − l(σ) is even, \\ t Q_{σ,τ}(t^{2}), & if l(τ) − l(σ) is odd. \end{matrix}

Proof. We proceed by induction on d(σ, τ), the thesis being clear if σ = τ. So let σ < τ, d =^{def} d(σ, τ), and suppose that l(τ) − l(σ) is even. Then, by Proposition 3.1, we have that

l(τ) − l(w σ) ≡ l(τ) − l(σ) − k(w) + 1 ≡ −k(w) + 1 (mod 2)

for any w ∈ C_{i,j}(σ) (where i =^{def} τ^{−1}(d), j =^{def} σ^{−1}(d)). Therefore we conclude from (19) and our induction hypotheses that

R̃_{σ,τ}(t) = ∑_{{w∈C_{i,j}(σ): k(w)≡1 (2)}} t^{k(w)−1} Q_{wσ,τ}(t^{2}) + ∑_{{w∈C_{i,j}(σ): k(w)≡0 (2)}} t^{k(w)} Q_{wσ,τ}(t^{2}),

which is clearly a polynomial in t^{2}. A similar argument is used if l(τ)−l(σ) is odd. □

We now wish to show that the polynomials R̃_{σ,τ}(t) are, up to a simple transformation, the R-polynomials for S_{n}. We will do this by showing that they satisfy an appropriate version of the basic recurrence (4). In order to do this, in view of our definition (19), it is necessary to investigate what happens to the sets C_{i,j}(σ) when an adjacent transposition is applied to σ. This requires a delicate combinatorial analysis whose result is given in the following lemma.

Lemma 3.6 Let π ∈ S_{n}, a, b, c ∈ [n] be such that a < b, π(a) < π(b), and π(c) < π(c + 1), and s =^{def} (c, c + 1), s̄ =^{def} (π(c), π(c + 1)). Then

C_{s(a),s(b)}(π s) = \{ \begin{matrix}C_{a,b}(π) \ C_{a,b}(π; s) s̄, & if a < c < b, and π(c), π(c + 1) ∈ [π(a), π(b)], \\ C_{a,b}(π) \ C_{a+1,b}(π) s̄, & if a = c, and π(c + 1) ∈ [π(a), π(b)], \\ C_{a,b}(π), & otherwise. \end{matrix}

Proof. Suppose first that a < c < b and π(a) < π(c) < π(c + 1) ≤ π(b). It is then clear that C_{s(a),s(b)}(π s) ⊆ C_{a,b}(π) and that if w ∈ C_{a,b}(π) \ C_{s(a),s(b)}(π s) then there exist p ∈ P, q ∈ N and indices i_{1}, …, i_{p}, j_{0}, …, j_{q} ∈ [n] such that

w = (π(j_{q}), …, π(j_{1}), π(c + 1), π(c), π(i_{p}), …, π(i_{1})) ,

a = i_{1} < … < i_{p} < c < c + 1 = j_{0} < j_{1} < … < j_{q} = b ,

and

π(i_{1}) < … < π(i_{p}) < π(c) < π(c + 1) < π(j_{1}) < … < π(j_{q}) .

Therefore

w s̄ = (π(j_{q}), …, π(j_{1}), π(c + 1), π(i_{p}), …, π(i_{1})) ,

and hence w s̄ ∈ C_{a,b}(π). Furthermore, (w s̄π)(c) = π(c) > π(i_{p}) = (w s̄π)(c + 1), so that s ∈ D(w s̄π).

Conversely, if u ∈ C_{a,b}(π) and s ∈ D(u π) then π(c + 1) ∉ F (u) and π(c) ∈ F (u) (for if π(c+1) ∈ F (u) then s ∉ D(u π)). Hence there exist p ∈ P, q ∈ N and indices i_{1}, …, i_{p}, j_{0}, …, j_{q} ∈ [n] such that

u = (π(j_{q}), …, π(j_{1}), π(c + 1), π(i_{p}), …, π(i_{1})) ,
a = i_{1} < … < i_{p} < c < c + 1 = j_{0} < j_{1} < … < j_{q} = b ,

and

π(i_{1}) < … < π(i_{p}) < π(c + 1) < π(j_{1}) < … < π(j_{q}) .

Furthermore, π(i_{p}) < π(c) (since s ∈ D(uπ)). Therefore

u s̄ = (π(j_{q}), …, π(j_{1}), π(c + 1), π(c), π(i_{p}), …, π(i_{1}))

and hence u s̄ ∈ C_{a,b}(π) \ C_{s(a),s(b)}(π s).

Suppose now that a = c and π(a) < π(a + 1) < π(b). Then it is clear that C_{s(a),s(b)}(π s) = C_{a+1,b}(π s) ⊆ C_{a,b}(π) and that, given w ∈ C_{a,b}(π), w ∉ C_{a+1,b}(π s) if and only if π(a + 1) ∉ F (w). But it is easy to see that

{w ∈ C_{a,b}(π) : π(a + 1) ∉ F (w)} s̄ = C_{a+1,b}(π) .

and the result follows.

Finally, if either c < a−1, or b < c, or π(c) ∉ [π(a), π(b)], or π(c+1) ∉ [π(a), π(b)] (note that this covers all the possible remaining cases since if c = b then, by our hypotheses, π(c+1) > π(c) = π(b) and hence π(c+1) ∉ [π(a), π(b)], while if c = a−1 then, similarly, π(c) < π(c + 1) = π(a) and hence π(c) ∉ [π(a), π(b)]) then it follows immediately from our definitions that C_{s(a),s(b)}(π s) = C_{a,b}(π), and this concludes the proof. □

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

Theorem 3.7 Let σ, τ ∈ S_{n} be such that σ ≤ τ. Then, for each s ∈ D(τ), we have that

R̃_{σ,τ}(t) = \{ \begin{matrix}R̃_{σs,τs}(t), & if s ∈ D(σ), \\ R̃_{σs,τs}(t) + t R̃_{σ,τs}(t), & if s ∉ D(σ). \end{matrix}

Proof. We proceed by induction on d(σ, τ), the thesis being clearly true if d(σ, τ) = 0. So let σ, τ ∈ S_{n} be such that d(σ, τ) > 0 and σ < τ. Fix s ∈ D(τ) and let, for convenience, s = (k, k + 1), d =^{def} d(σ, τ) and s̄ =^{def} (σ(k), σ(k + 1)) (so that s̄ = σ s σ^{−1}). Applying (19) we get that

R̃_{σ,τ}(t) = ∑_{w∈C_{i,j}(σ)} t^{k(w)−1} R̃_{wσ,τ}(t) ,  (20)

where i =^{def} τ^{−1}(d), and j =^{def} σ^{−1}(d). Also, since d(σs, τs) = d(σ, τ), we get from (19) that

R̃_{σs,τs}(t) = ∑_{w∈C_{s(i),s(j)}(σs)} t^{k(w)−1} R̃_{wσs,τs}(t) .  (21)

Finally, note that, if s ∉ D(σ) then σ(k), σ(k + 1) ≤ d(σ, τ) (for if σ(k + 1) > d then τ(k) > τ(k + 1) = σ(k + 1) > d and hence σ(k) = τ(k) > σ(k + 1), which is a contradiction) and hence d(σ, τs) = d(σ, τ), unless k = i = j − 1. Therefore we conclude from (19) that

R̃_{σ,τs}(t) = ∑_{w∈C_{s(i),j}(σ)} t^{k(w)−1} R̃_{wσ,τs}(t) ,  (22)

whenever s ∉ D(σ). Now, from (20) and our induction hypotheses (which can be applied since d(wσ, τ) < d(σ, τ) for all w ∈ C_{i,j}(σ)) we get that

R̃_{σ,τ}(t) = ∑_{w∈C_{i,j}(σ;s)} t^{k(w)−1} R̃_{wσs,τs}(t)
+ ∑_{{w∈C_{i,j}(σ): s∉D(wσ)}} t^{k(w)−1} (R̃_{wσs,τs}(t) + t R̃_{wσ,τs}(t))
= ∑_{w∈C_{i,j}(σ)} t^{k(w)−1} R̃_{wσs,τs}(t) + ∑_{{w∈C_{i,j}(σ): s∉D(wσ)}} t^{k(w)} R̃_{wσ,τs}(t) . (23)

There are now several cases to consider:

i) i + 1 ≤ k ≤ j, and σ(i) ≤ σ(k + 1) < σ(k) ≤ σ(j) .

Then applying Lemma 3.6 (with π = σs, a = s(i), b = s(j), and c = k) yields that C_{s(i),s(j)}(σs) = C_{i,j}(σ) ⨄ C_{s(i),s(j)}(σs; s) s̄, but it is easy to see that

C_{s(i),s(j)}(σs; s) = {w ∈ C_{i,j}(σ) : s ∉ D(wσ)} .

Therefore, we conclude from (23) that

R̃_{σ,τ}(t) = ∑_{w∈C_{i,j}(σ)} t^{k(w)−1} R̃_{wσs,τs}(t) + ∑_{w∈{w∈C_{i,j}(σ): s∉D(wσ)}s̄}t^{k(ws̄)}R̃_{ws̄σ,τs}(t)
= ∑_{w∈C_{i,j}(σ)} t^{k(w)−1} R̃_{wσs,τs}(t) + ∑_{w∈{w∈C_{i,j}(σ): s∉D(wσ)}s̄}t^{k(w)−1}R̃_{wσs,τs}(t)
= R̃_{σs,τs}(t) ,  (24)

by (21).

ii) i + 1 ≤ k ≤ j, and σ(i) ≤ σ(k) < σ(k + 1) ≤ σ(j) .

Then by Lemma 3.6 we have that C_{s(i),s(j)}(σs) = C_{i,j}(σ) \ C_{i,j}(σ; s)s̄. Therefore, we conclude from (23) that

R̃_{σ,τ}(t) = ∑_{w∈C_{i,j}(σ)} t^{k(w)−1} (R̃_{wσs,τs}(t) + t R̃_{wσ,τs}(t)) − ∑_{w∈C_{i,j}(σ;s)} t^{k(w)} R̃_{wσ,τs}(t)
= ∑_{w∈C_{i,j}(σ)} t^{k(w)−1} (R̃_{wσs,τs}(t) + t R̃_{wσ,τs}(t)) − ∑_{w∈C_{i,j}(σ;s)s̄}t^{k(ws̄)} R̃_{ws̄σ,τs}(t)
= ∑_{w∈C_{i,j}(σ)} t^{k(w)−1} (R̃_{wσs,τs}(t) + t R̃_{wσ,τs}(t)) − ∑_{w∈C_{i,j}(σ;s)s̄}t^{k(w)−1} R̃_{wσs,τs}(t)
= t R̃_{σ,τs}(t) + R̃_{σs,τs}(t) ,

by (21) and (22).

iii) either k ∉ [i − 1, j] or σ(k) ∉ [σ(i), σ(j)] or σ(k + 1) ∉ [σ(i), σ(j)].

Then by Lemma 3.6 we have that C_{s(i),s(j)}(σs) = C_{i,j}(σ). Now, if σ(k) > σ(k + 1) (i.e., if s ∈ D(σ)) then it is easy to check that s ∈ D(wσ) for all w ∈ C_{i,j}(σ) so that {w ∈ C_{i,j}(σ) : s ∉ D(wσ)} = ∅ and hence, by (21) and (23),

R̃_{σ,τ}(t) = R̃_{σs,τs}(t) .

On the other hand, if σ(k) < σ(k + 1) (i.e., if s ∉ D(σ)) then it is easy to check that s ∉ D(wσ) for all w ∈ C_{i,j}(σ) so that {w ∈ C_{i,j}(σ) : s ∉ D(wσ)} = C_{i,j}(σ). Furthermore, s(i) = i (for if k = i−1 then d = τ(k+1) < τ(k) = σ(k) < σ(k+1) ≤ d, and similarly if k = i then σ(i) < σ(k+1) and hence d = σ(j) < σ(k+1) = τ(k+1) < τ(k) = d). Therefore, by (21), (22), and (23),

R̃_{σ,τ}(t) = R̃_{σs,τs}(t) + t R̃_{σ,τs}(t) .

iv) k = i, and σ(i) < σ(i + 1) ≤ σ(j).

Then by Lemma 3.6 we have that C_{s(i),s(j)}(σs) = C_{i,j}(σ) \ C_{i+1,j}(σ)\overline{s}. Now, it is easy to see that, since k = i, {w ∈ C_{i,j}(σ) : s ∉ D(wσ)} = ∅. Therefore, we conclude from (23), and (21), that

R̃_{σ,τ}(t) = ∑_{w∈C_{s(i),s(j)}(σs)} t^{k(w)−1} R̃_{wσs,τs}(t) + ∑_{w∈C_{i+1,j}(σ) s̄}t^{k(w)−1} R̃_{wσs,τs}(t)
= R̃_{σs,τs}(t) + ∑_{w∈C_{i+1,j}(σ)} t^{k(ws̄)−1} R̃_{ws̄σs,τs}(t)
= R̃_{σs,τs}(t) + ∑_{w∈C_{s(i),j}(σ)} t^{k(w)} R̃_{wσ,τs}(t)
= R̃_{σs,τs}(t) + t R̃_{σ,τs}(t) ,

by (22).

v) k = i − 1, and σ(i) < σ(i − 1) < σ(j).

This case can never happen because, since s ∈ D(τ) we have that τ(k) > τ(k + 1) and therefore τ(i−1) > τ(i). But τ(i) = τ(τ^{−1}(d)) = d. Hence τ(i−1) > d, but, by the definition of d =^{def} d(τ, σ), this implies that τ(i − 1) = σ(i − 1). Hence σ(i − 1) > d = σ(j), which is a contradiction since we are assuming that σ(i − 1) < σ(j).

This concludes the proof. □

We can now state the precise relationship between the polynomials defined by (19) and the R-polynomials of S_{n}.

Corollary 3.8 Let σ, τ ∈ S_{n}, then

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

Proof. This follows immediately from Theorems 2.2 and 3.7. □

As an immediate consequence of the preceding result, of Proposition 3.1, and of the definition (19) we obtain the following recurrence for R-polynomials.

Corollary 3.9 Let σ, τ ∈ S_{n} be such that σ < τ. Then

R_{σ,τ}(q) = ∑_{w∈C_{τ^{−1}(d),σ^{−1}(d)}(σ)} q^{n(w,σ)} (q − 1)^{k(w)−1} R_{wσ,τ}(q) ,  (25)

where d =^{def} d(σ, τ). □

The preceding recurrence has several advantages over the one given by (4), both of a theoretical as well as practical nature. The main one is that (25) does not “branch off” into two cases as (4) does. This allows one to use (25) repeatedly and thus explicitly solve the recurrence, as will be done in the next section. While this is theoretically possible also with (4), the details are much simpler using (25). The second one is that the recurrence (25) does not change the second permutation. This is extremely useful in induction arguments, as will be seen in the proofs of Theorems 4.4 and 4.6 in the next section. The third one is that the recurrence (25) is much faster from a computational point of view. Already computing R_{1342,4321}(q) by hand, using (4), and comparing with the example computed before Proposition 3.5, should convince the reader of this. However, we have implemented both recursions (4) and (25) on a computer (using MAPLE) and have been able to verify this directly. For example, computing the R-polynomial of any pair of permutations in S_{8} takes (running MAPLE V on a Sun SparcStation SLC) less than 65 seconds using (25) while it takes more than 5 minutes to compute R_{12...8,8...21}(q) using (4). These MAPLE programs (which will run also on older versions of MAPLE) are available from the author upon request.

4 Applications

In this section we apply our main result to the explicit computation of R-polynomials and Kazhdan-Lusztig polynomials. We begin by “solving” the recurrence relation (25). Let σ, τ ∈ S_{n}, σ ≤ τ. An R-chain from σ to τ is a chain σ = σ_{0} < σ_{1} < … < σ_{r} = τ such that:

i) d(σ_{i}, τ) < d(σ_{i−1}, τ);

ii) (σ_{i})(σ_{i−1})^{−1} ∈ C(σ_{i−1});

for all i = 1, …, r. We denote by R(σ, τ) the set of all R-chains from σ to τ. Given any chain C = (σ_{0} < σ_{1} < … < σ_{r}) in S_{n} we define its R-length to be

l_{R}(C) =^{def} ∑_{i=1}^{r}(k((σ_{i})(σ_{i−1})^{−1}) − 1) .

For example, C = (1234 < 4132 < 4312 < 4321) is an R-chain from 1234 to 4321 and its R-length is l_{R}(C) = 2 + 1 + 1 = 4.

Theorem 4.1 Let σ, τ ∈ S_{n}, σ ≤ τ. Then

R_{σ,τ}(q) = ∑_{C∈R(σ,τ)} q^{\frac{l(τ)−l(σ)−l_{R}(C)}{2}} (q − 1)^{l_{R}(C)} .  (26)

Proof. We will prove that

R̃_{σ,τ}(t) = ∑_{C∈R(σ,τ)} t^{l_{R}(C)} ,  (27)

and the thesis will then follow from Corollary 3.8. We proceed by induction on d(σ, τ), (27) being true by definition if σ = τ. So let σ, τ ∈ S_{n} be such that σ < τ. By (19) and our induction hypothesis we have that

R̃_{σ,τ}(t) = ∑_{w∈C_{i,j}(σ)} t^{k(w)−1} ∑_{C∈R(wσ,τ)} t^{l_{R}(C)} ,  (28)

where i =^{def} τ^{−1}(d), j =^{def} σ^{−1}(d), and d =^{def} d(σ, τ). Now, if C = (σ_{0} < … < σ_{r}) ∈

R(wσ, τ) and w ∈ C_{i,j}(σ) then clearly C_{w} =^{def} (σ < wσ < σ_{1} < … < σ_{r−1} < τ) ∈

R(σ, τ) and

l_{R}(C_{w}) = k(w) − 1 + l_{R}(C) .

Conversely, if C′ = (σ_{0} < σ_{1} < … < σ_{r}) ∈ R(σ, τ) then it follows from our definitions that there exists w =^{def} (σ(i_{k}), …, σ(i_{1})) ∈ C(σ) (where i_{1} < … < i_{k} and

σ(i_{1}) < … < σ(i_{k})) such that σ_{1} = wσ and C′′ =^{def} (σ_{1} < … < σ_{r}) ∈ R(wσ, τ).

Furthermore, since d(σ_{1}, τ) < d(σ_{0}, τ) = d, we have that

σ^{−1}(d) ≠ τ^{−1}(d) = (σ_{1})^{−1}(d) = (wσ)^{−1}(d) = σ^{−1}(w^{−1}(d)) ,  (29)

and

σ^{−1}(h) = τ^{−1}(h) = (σ_{1})^{−1}(h) = (wσ)^{−1}(h) = σ^{−1}(w^{−1}(h))

if h > d. Hence d ∉ F (w) but h ∈ F (w) if h > d, and this implies that σ(i_{k}) = d and hence that i_{k} = j. Furthermore, it follows from this and (29) that i = τ^{−1}(d) = σ^{−1}(w^{−1}(d)) = σ^{−1}(w^{−1}(σ(i_{k}))) = σ^{−1}(σ(i_{1})) = i_{1}. Hence w ∈ C_{i,j}(σ) and it is clear that l_{R}(C′) = l_{R}(C′′) + k − 1. This shows that we have a bijection φ : ⋃_{w∈C_{i,j}(σ)} R(wσ, τ) → R(σ, τ) such that l_{R}(φ(C)) = k(w) − 1 + l_{R}(C) for any C ∈ R(wσ, τ) and w ∈ C_{i,j}(σ), and so (27) follows from (28), as desired. □

Note that, by Proposition 3.1 and our definitions, l(τ) − l(σ) − l_{R}(C) is even for any σ, τ ∈ S_{n} and C ∈ R(σ, τ), so that (26) does not involve q^{\frac{1}{2}} . It would be interesting to find a direct connection between (26) and Deodhar’s formula (see, e.g., [8], Theorem 1.3, or [16], p. 154). This should involve some bijection between R-chains and “distinguished subexpressions” (as defined in [8], Definition 2.3 or [16], p. 154). We should also note that a formula closely related to (27) was obtained (independently) by Dyer in [11].

We now concentrate on specific types of intervals in S_{n} for which the R-polynomial can be evaluated in closed form. Corollary 3.9 shows that the process of going from σ to wσ, where w ∈ C(σ), is the “basic step” in the computation of R-polynomials. This suggests that the R-polynomial of intervals of the form [σ, wσ], where w ∈ C(σ), might be particularly simple. This is indeed the case (see Theorem 4.6) though the proof of this fact is by no means easy. We begin by establishing some preliminary facts about the Bruhat order of S_{n} which will be needed in the proof. Throughout the rest of this section we will use the characterization of Bruhat order given by Theorem 2.5 without explicit mention.

First, we need to define some refinements of the distance function on S_{n} which was introduced in §3. Let σ, τ ∈ S_{n}. For i ∈ [n] let

d_{i}(σ, τ) =^{def} max {j ∈ [n] : σ^{−1}(j) ≠ τ^{−1}(j), σ^{−1}(j) ∈ [i]} ,  (30)

(where max {∅} =^{def} 0). For example, if σ = 198265374 and τ = 298461357 then (d_{1}(σ, τ), …, d_{9}(σ, τ)) = (1, 1, 1, 2, 2, 5, 5, 7, 7) and (d_{1}(τ, σ), …, d_{9}(τ, σ)) = (2, 2, 2, 4, 4, 4, 4, 5, 7). Note that 0 ≤ d_{1}(σ, τ) ≤ d_{2}(σ, τ) ≤ … ≤ d_{n}(σ, τ) = d(σ, τ) and that, in general, d_{i}(σ, τ) ≠ d_{i}(τ, σ) unless i = n. In relation to Bruhat order the functions d_{i} : S_{n} × S_{n} → N have the following important property.

Proposition 4.2 Let σ, τ ∈ S_{n} be such that σ ≤ τ. Then

d_{i}(σ, τ) ≤ d_{i}(τ, σ)

for i = 1, …, n.

Proof. Fix i ∈ [n]. Let {a_{1}, …, a_{i}}_{<} =^{def} {σ(1), …, σ(i)},

{b_{1}, …, b_{i}}_{<} =^{def} {τ(1), …, τ(i)} ,  (31)

and j, k ∈ [i] be such that a_{j} = d_{i}(σ, τ), b_{k} = d_{i}(τ, σ). Note that, since σ ≤ τ, we have that

a_{r} ≤ b_{r}  (32)

for all r = 1, …, i. In particular this implies that if a_{m} = b_{n} for some m, n ∈ [i] then m ≥ n (for if m < n then b_{n} = a_{m} < a_{n} ≤ b_{n} by (32)). Furthermore, the definition of d_{i}(τ, σ) implies that

σ^{−1}(b_{r}) = τ^{−1}(b_{r})  (33)

for all k + 1 ≤ r ≤ i. In particular this implies that b_{r} ∈ {σ(1), …, σ(i)}, for all k+1 ≤ r ≤ i (since b_{r} = σ(τ^{−1}(b_{r})) and τ^{−1}(b_{r}) ∈ [i] by (31)). But then a_{i} = b_{i} (for if b_{i} = a_{r} for some r < i, then b_{i} = a_{r} < a_{i} ≤ b_{i}). Similarly a_{i−1} = b_{i−1} (for if b_{i−1} = a_{r} for some r < i − 1, then b_{i−1} = a_{r} < a_{i−1} ≤ b_{i−1}), and a_{i−2} = b_{i−2}, …, a_{k+1} = b_{k+1}. But then d_{i}(σ, τ) ∉ {a_{k+1}, …, a_{i}} (otherwise d_{i}(σ, τ) ∈ {b_{k+1}, …, b_{i}} and hence σ^{−1}(d_{i}(σ, τ)) = τ^{−1}(d_{i}(σ, τ)) by (33), which contradicts the definition of d_{i}(σ, τ)). Therefore a_{j} ∉ {a_{k+1}, …, a_{i}}, hence j ≤ k which implies that

d_{i}(σ, τ) = a_{j} ≤ a_{k} ≤ b_{k} = d_{i}(τ, σ) ,

as desired. □

Note that the converse of the above proposition does not hold. For example, if σ = 312 and τ = 231 then (d_{1}(σ, τ), …, d_{3}(σ, τ)) = (3, 3, 3) and (d_{1}(τ, σ), …, d_{3}(τ, σ)) = (2, 3, 3).

We now need to prove some preliminary results about R̃ and R-polynomials.

Lemma 4.3 Let σ ∈ S_{n}, i, j ∈ [n], and w ∈ C_{i,j}(σ). Then there exists v ∈ S_{n} such that:

i) R̃_{σ,wσ}(t) = R̃_{σv,wσv}(t);

ii) w ∈ C_{i,j}(σv);

iii) m(w, σv) = 0.

Proof. We proceed by induction on p(w, σ). If p(w, σ) = 0 then m(w, σ) = 0 and there is nothing to prove. So assume that p(w, σ) ≥ 1, and let k =^{def} k(w), for brevity, and

w =^{def} (σ(i_{k}), … σ(i_{1})) ,

where i = i_{1} < … < i_{k} = j, and σ(i_{1}) < … < σ(i_{k}). Since p(w, σ) ≥ 1 we have that m(w, σ) ≥ 1 and hence there exists 2 ≤ a ≤ k −1 such that T_{σ}[i_{a−1}, i_{a}; σ(i_{a}), σ(j)] ≠ ∅. So let b ∈ T_{σ}[i_{a−1}, i_{a}; σ(i_{a}), σ(j)], and u =^{def} (b, b + 1, b + 2, …, i_{a}), so that u = s_{b} s_{b+1} s_{b+2} … s_{i_{a}−1}. Since every element of [n] \ {σ(i_{1}), …, σ(i_{k})} is fixed by w we have that s_{c} ∈ D(σ s_{b} s_{b+1} … s_{c−1}) if and only if s_{c} ∈ D(wσs_{b} s_{b+1} … s_{c−1}), for all b ≤ c < i_{a} − 1. Furthermore, since σ(b) > σ(i_{a}) > σ(i_{a−1}) = (wσ)(i_{a}) we also have that s_{i_{a}−1} ∈ D(σ s_{b} s_{b+1} … s_{i_{a}−2}) ∩ D(wσs_{b}s_{b+1} … s_{i_{a}−2}). Using Theorem 3.7 repeatedly we conclude from this that

R̃_{σ,wσ}(t) = R̃_{σs_{b}s_{b+1}...s_{ia−1},wσs_{b}s_{b+1}...s_{ia−1}}(t) = R̃_{σu,wσu}(t) .

Furthermore, it is clear that w ∈ C_{i,j}(σw) (since u(i) = i, u(j) = j, and w = (σ(i_{k}), …, σ(i_{1})) = ((σu)(i_{k}), …, (σu)(i_{a} − 1), …, (σu)(i_{1}))) and that p(w, σu) ≤ p(w, σ) − 1. Hence, by our induction hypotheses, there exists v ∈ S_{n} such that

R̃_{σu,wσu}(t) = R̃_{σuv,wσuv}(t) ,

w ∈ C_{i,j}(σuv), and m(w, σuv) = 0, and the thesis follows. □

Our next preliminary result is also of independent interest. It gives sufficient conditions on two permutations so that their R-polynomial and Kazhdan-Lusztig polynomial factor. Let σ ∈ S_{n}, and i, j ∈ [n], i ≤ j. We define the restriction of σ to [i, j] to be the unique permutation σ_{[i,j]} ∈ S([i, j]) such that

σ^{−1}(σ_{[i,j]}(i)) < σ^{−1}(σ_{[i,j]}(i + 1)) < … < σ^{−1}(σ_{[i,j]}(j)) .

For example, if σ = 7251634 then σ_{[3,5]} = 534 (i.e, σ_{[3,5]}(3) = 5, σ_{[3,5]}(4) = 3, σ_{[3,5]}(5) = 4). Note that σ_{[i,j]} =Id([i, j]) if and only if σ^{−1}(i) < σ^{−1}(i + 1) < … < σ^{−1}(j), and that if σ([i, j]) = [i, j] then σ_{[i,j]} = σ|_{[i,j]}.

Theorem 4.4 Let σ, τ ∈ S_{n}, σ ≤ τ. Suppose that there exist 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ n such that σ^{−1}((i_{j}, i_{j+1}]) = τ^{−1}((i_{j}, i_{j+1}]) for all j = 0, …, k (where i_{0} =^{def} 0,

i_{k+1} =^{def} n). Then

R_{σ,τ}(q) = ∏_{j=0}^{k} R_{σ_{(i_{j} ,i_{j+1}]},τ_{(i_{j} ,i_{j+1}]}}(q) ,  (34)

and

P_{σ,τ}(q) = ∏_{j=0}^{k} P_{σ_{(i_{j} ,i_{j+1}]},τ_{(i_{j} ,i_{j+1}]}}(q) .  (35)

Proof. We will prove first that

R̃_{σ,τ}(t) = ∏_{j=0}^{k} R̃_{σ_{(i_{j} ,i_{j+1}]},τ_{(i_{j} ,i_{j+1}]}}(t) ,  (36)

and (34) will then follow from Corollary 3.8 and the easily established fact that

l(τ) − l(σ) = ∑_{j=0}^{k}(l(τ_{(i_{j},i_{j+1}]}) − l(σ_{(i_{j},i_{j+1}]})) ,  (37)

in the hypotheses of the theorem. We proceed by induction on d(σ, τ), (36) being trivially true if d(σ, τ) = 0. So let σ, τ, and i_{0}, …, i_{k+1} be as in the statement of the theorem, with σ < τ, and let, for brevity, I_{j} =^{def} (i_{j}, i_{j+1}], for j = 0, …, k. By (19) we have that

R̃_{σ,τ}(t) = ∑_{w∈C_{i,j}(σ)} t^{k(w)−1} R̃_{wσ,τ}(t)  (38)

where i =^{def} τ^{−1}(d), j =^{def} σ^{−1}(d), and d =^{def} d(σ, τ). Let r ∈ [k] be such that d ∈ I_{r}. Then τ(i) ∈ I_{r}, and hence, by our hypotheses, i ∈ σ^{−1}(I_{r}) so that σ(i) ∈ I_{r}. Therefore σ(i), σ(j) ∈ I_{r} and this shows that, for any w ∈ C_{i,j}(σ), all elements of [n] which are not fixed by w are in I_{r}. Therefore w^{−1}(I_{j}) = I_{j} for all j = 0, …, k and hence

(wσ)^{−1}(I_{j}) = τ^{−1}(I_{j})

for j = 0, …, k. By our induction hypotheses we then have that

R̃_{wσ,τ}(t) = ∏_{j=0}^{k} R̃_{(wσ)_{I_{j}} ,τ_{I_{j}}} (t) .  (39)

But, since every element of I_{j}, for 0 ≤ j ≤ k, j ≠ r, is fixed by w, we have that (wσ)_{I_{j}} = σ_{I_{j}}, for j = 0, …, k, j ≠ r. Hence we conclude from (39) that

R̃_{wσ,τ}(t) = R̃_{(wσ)_{Ir} ,τ_{Ir}} (t) ∏_{j≠r} R̃_{σ_{I_{j}} ,τ_{I_{j}}} (t).

Substituting this in (38) we obtain that

R̃_{σ,τ}(t) = ∏_{j≠r} R̃_{σ_{I_{j}} ,τ_{I_{j}}} (t) ∑_{w∈C_{i,j}(σ)} t^{k(w)−1}R̃_{(wσ)_{Ir} ,τ_{Ir}} (t) .  (40)

Now it is clear that d(σ_{I_{r}}, τ_{I_{r}}) = d(σ, τ)−i_{r} (recall that we identify S(I_{r}) with S_{|I_{r}|}), that restriction to I_{r} gives a bijection from C_{i,j}(σ) to C_{(τ_{Ir})^{−1}(d−i_{r}),(σ_{Ir})^{−1}(d−i_{r})}(σ_{I_{r}}) and that, since w fixes all elements not in I_{r}, (wσ)_{I_{r}} = w_{I_{r}}σ_{I_{r}}. Hence

∑_{w∈C_{i,j}(σ)} t^{k(w)−1} R̃_{(wσ)_{Ir} ,τ_{Ir}} (t) = ∑_{w_{Ir} ∈C_{i′,j′}(σ_{Ir})} t^{k(w_{Ir})−1} R̃_{w_{Ir} σ_{Ir} ,τ_{Ir}} (t)
= R̃_{σ_{Ir} ,τ_{Ir}} (t) ,

by (19), where i′ =^{def} (τ_{I_{r}})^{−1}(d−i_{r}) and j′ =^{def} (σ_{I_{r}})^{−1}(d−i_{r}), and (36) follows from (40).

We now prove (35) by induction on l(τ) − l(σ), (35) being clearly true if σ = τ. Note first that it follows easily from our hypotheses, and Theorem 2.5, that the map a ↦ (a_{I_{0}}, …, a_{I_{k}}) is a poset isomorphism from [σ, τ] to [σ_{I_{0}}, τ_{I_{0}}] × … × [σ_{I_{k}}, τ_{I_{k}}]. Therefore we conclude from (34), (5), and our induction hypotheses that

q^{l(τ)−l(σ)}P_{σ,τ} (\frac{1}{q}) − P_{σ,τ}(q) = ∑_{σ<a≤τ} R_{σ,a}(q) P_{a,τ}(q)
= ∏_{j=0}^{k} ∑_{a_{j}∈[σ_{I_{j}} ,τ_{I_{j}}]} R_{σ_{I_{j}} ,a_{j}}(q) P_{a_{j},τ_{I_{j}}} (q) − ∏_{j=0}^{k} P_{σ_{I_{j}} ,τ_{I_{j}}} (q)

= ∏_{j=0}^{k} q^{l(τ_{I_{j}})−l(σ_{I_{j}})} P_{σ_{I_{j}} ,τ_{I_{j}}} (\frac{1}{q}) − ∏_{j=0}^{k} P_{σ_{I_{j}} ,τ_{I_{j}}} (q)
= q^{l(τ)−l(σ)} ∏_{j=0}^{k} P_{σ_{I_{j}} ,τ_{I_{j}}} (\frac{1}{q}) − ∏_{j=0}^{k} P_{σ_{I_{j}} ,τ_{I_{j}}} (q) . (41)

Now, from (37) and part iii) of Theorem 2.3 we conclude that

deg (∏_{j=0}^{k} P_{σ_{I_{j}} ,τ_{I_{j}}} (q)) ≤ ∑_{j=0}^{k} ⌊\frac{l(τ_{I_{j}}) − l(σ_{I_{j}}) − 1}{2}⌋ ≤ ⌊\frac{l(τ) − l(σ) − 1}{2}⌋ .

Hence equating the coefficients of q^{i}, for i = 0, …, ⌊\frac{l(τ)−l(σ)−1}{2}⌋, on both sides of (41) yields (35), as desired. □

We illustrate the preceding theorem with an example. Let σ = 16573824, and τ = 47583612. Then σ^{−1}([1, 4]) = {1, 5, 7, 8} = τ^{−1}([1, 4]) and σ^{−1}([5, 8]) = {2, 3, 4, 6} = τ^{−1}([5, 8]), hence R_{16573824,47583612}(q) = R_{σ_{[1,4]},τ_{[1,4]}}(q) R_{σ_{[5,8]},τ_{[5,8]}}(q) = R_{1324,4312}(q) R_{6578,7586}(q) = R_{1324,4312}(q) R_{2134,3142}(q) = (q(q − 1)^{2} + (q − 1)^{4})(q − 1)^{2} = (q − 1)^{4}(q^{2} − q + 1), and P_{16573824,47583612}(q) = P_{σ_{[1,4]},τ_{[1,4]}}(q) P_{σ_{[5,8]},τ_{[5,8]}}(q) = P_{1324,4312}(q) P_{6578,7586}(q) = P_{1324,4312}(q) P_{2134,3142}(q) = 1 · 1 = 1.

We note the following interesting consequence of Theorem 4.4.

Corollary 4.5 The product of two R-polynomials (respectively, Kazhdan-Lusztig polynomials) is again an R-polynomial (respectively a Kazhdan-Lusztig polynomial). □

For example, R_{1324,3412}(q) R_{123,321}(q) = R_{1324567,3412765}(q) = R_{5671324,7653412}(q) = R_{5136274,7346152}(q), P_{1234,3412}(q) P_{13425,34512}(q) = P_{123457869,341278956}(q) = P_{152378649,374189526}(q) = P_{571823694,783941562}(q), etc... .

We now come to the second main result of this section.

Theorem 4.6 Let σ ∈ S_{n} and w ∈ C(σ). Then

R_{σ,wσ}(q) = (q − 1)^{k(w)−1}(q^{2} − q + 1)^{n(w,σ)} .

Proof. We will prove that

R̃_{σ,wσ}(t) = t^{k(w)−1} (t^{2} + 1)^{n(w,σ)} ,  (42)

and the thesis will then follow from Corollary 3.8 and Proposition 3.1. We proceed by induction on n(w, σ) + k(w) − 1, (42) being clearly true if n(w, σ) + k(w) = 2 (i.e., if n(w, σ) = 0 and k(w) = 2). So let i, j ∈ [n], i < j, be such that w ∈ C_{i,j}(σ) and let k =^{def} k(w), for brevity, and

w =^{def} (σ(i_{k}), …, σ(i_{1})) ,

where i = i_{1} < … < i_{k} = j, and σ(i_{1}) < … < σ(i_{k}). By Lemma 4.3 we may assume that m(w, σ) = 0, (i.e., that T_{σ}[i_{r}, i_{r+1}; σ(i_{s}), σ(i_{s+1})] = ∅ for all 1 ≤ r < s ≤ k − 1). So let

{i_{r,1}, …, i_{r,n_{r}}}_{<} =^{def} T_{σ}[i_{r}, i_{r+1}; σ(i_{r}), σ(i_{r+1})] ,

for r = 1, …, k − 1. Note that this implies that

∑_{r=1}^{k−1} n_{r} = n(w, σ) .  (43)

Now, since every element of [n] \ {σ(i_{1}), …, σ(i_{k})} is fixed by w, we have that s_{b} ∈ D(σs_{a_{1}} … s_{a_{p}}) if and only if s_{b} ∈ D(wσs_{a_{1}} … s_{a_{p}}) whenever b, a_{1}, …, a_{p} ∈ ⋃_{j=1}^{k+1}(i_{j−1}, i_{j} − 1) (where i_{0} =^{def} 0, i_{k+1} =^{def} n + 2). Using Theorem 3.7 we therefore conclude that

R̃_{σ,wσ}(t) = R̃_{σs_{a_{1}}...s_{ap},wσs_{a_{1}}...s_{ap}}(t)

whenever a_{1}, …, a_{p} ∈ ⋃_{j=1}^{k+1}(i_{j−1}, i_{j} − 1). This shows that we may assume without loss of generality that

σ(i_{r,1}) > … > σ(i_{r,n_{r}})  (44)

for all 1 ≤ r ≤ k − 1. Now, by (19), we have that

R̃_{σ,wσ}(t) = ∑_{v∈C_{i,j}(σ)} t^{k(v)−1} R̃_{vσ,wσ}(t) .  (45)

We now claim that if v ∈ C_{i,j}(σ) and σ(i_{a}) ∈ F (v) for some 2 ≤ a ≤ k − 1 then vσ ≰ wσ (and hence, in particular, R̃_{vσ,wσ}(t) = 0). In fact, let v ∈ C_{i,j}(σ) and 2 ≤ a ≤ k − 1 be such that σ(i_{a}) ∈ F (v). Note that if b ∈ [n] is such that (vσ)^{−1}(b) ≠ (wσ)^{−1}(b) then i_{1} ≤ σ^{−1}(b) ≤ i_{a} and b ≤ σ(i_{k}), and this, since m(w, σ) = 0, implies that b ≤ σ(i_{a}). Therefore, by (30),

d_{i_{a}}(vσ, wσ) ≤ σ(i_{a}) ,  (46)

and d_{i_{a}}(wσ, vσ) ≤ σ(i_{a}). Now, if σ(i_{a}) ∈ F (v) then (vσ)^{−1}(σ(i_{a})) = i_{a} and (wσ)^{−1}(σ(i_{a})) = σ^{−1}(w^{−1}(σ(i_{a}))) = σ^{−1}(σ(i_{a−1})) = i_{a−1} and this, by (30), shows that

d_{i_{a}}(vσ, wσ) = σ(i_{a}) .

On the other hand, since (wσ)^{−1}(σ(i_{a})) > i_{a}, it follows from (30) that d_{i_{a}}(wσ, vσ) < σ(i_{a}). Hence

d_{i_{a}}(wσ, vσ) < d_{i_{a}}(vσ, wσ) ,

and this, by Proposition 4.2 , implies that vσ ≰ wσ, as claimed.

It follows from the claim just proved and the inequalities (44) that if v ∈ C_{i,j}(σ) is such that R̃_{vσ,wσ}(t) ≠ 0 then there exist 0 ≤ s ≤ k−1, 1 ≤ r_{1} < r_{2} < … < r_{s} ≤ k−1, and j_{t} ∈ [n_{r_{t}}], for t = 1, …, s, such that

v = (σ(i_{k}), …, σ(i_{r_{s}+1}), σ(i_{r_{s},j_{s}}), σ(i_{r_{s}}), …, σ(i_{r_{1}+1}), σ(i_{r_{1},j_{1}}), σ(i_{r_{1}}), …, σ(i_{1})) ,

and conversely any such choice gives a v ∈ C_{i,j}(σ). In this case it is easy to see that

(vσ)^{−1}(σ(i_{r_{t}})) = i_{r_{t},j_{t}} = (wσ)^{−1}(σ(i_{r_{t},j_{t}})) ,  (47)

and

(vσ)^{−1}(σ(i_{r_{t},j_{t}})) = i_{r_{t}+1} = (wσ)^{−1}(σ(i_{r_{t}})) ,  (48)

for t = 1, …, s, while

(vσ)^{−1}(j) = (wσ)^{−1}(j)  (49)

if j ∉ {σ(i_{r_{1}}), …, σ(i_{r_{s}}), σ(i_{r_{1},j_{1}}), …, σ(i_{r_{s},j_{s}})}. Therefore

(vσ)^{−1}((σ(i_{r_{t},j_{t}}), σ(i_{r_{t+1},j_{t+1}})]) = (wσ)^{−1}((σ(i_{r_{t},j_{t}}), σ(i_{r_{t+1},j_{t+1}})])

for t = 0, …, s (where i_{r_{0},j_{0}} =^{def} 0, i_{r_{s+1},j_{s+1}} =^{def} n). Hence we conclude from Theorem 4.4 (or, equivalently, from (36)) that

R̃_{vσ,wσ}(t) = ∏_{p=0}^{s} R̃_{(vσ)_{Ip},(wσ)_{Ip}}(t)  (50)

where I_{p} =^{def} (σ(i_{r_{p},j_{p}}), σ(i_{r_{p+1},j_{p+1}})], for p = 0, …, s. But it follows from (47), (48), and (49) that (wσ)_{I_{p−1}} = (σ(i_{r_{p}}), σ(i_{r_{p},j_{p}}))(vσ)_{I_{p−1}} for p = 1, …, s, and (wσ)_{I_{s}} = (vσ)_{I_{s}}. Since n((σ(i_{r_{p}}), σ(i_{r_{p},j_{p}})), (vσ)_{I_{p−1}}) = n_{r_{p}} − j_{p} < n(w, σ), for p = 1, …, s, we conclude from our induction hypothesis that

R̃_{(vσ)_{I_{p−1}},(wσ)_{I_{p−1}}}(t) = t (t^{2} + 1)^{n_{rp}−j_{p}}  (51)

for p = 1, …, s. Hence we obtain from (50) and (51) that

R̃_{vσ,wσ}(t) = ∏_{p=1}^{s} t (t^{2} + 1)^{n_{rp}−j_{p}} .

Therefore we conclude from (45) that

R̃_{σ,wσ}(t) = ∑_{s=0}^{k−1} ∑_{1≤r_{1}<...<r_{s}≤k−1} ∑_{j_{1}=1}^{n_{r_{1}}} … ∑_{j_{s}=1}^{n_{rs}} t^{k+s−1} ∏_{p=1}^{s} t (t^{2} + 1)^{n_{rp}−j_{p}}

= ∑_{s=0}^{k−1} ∑_{1≤r_{1}<...<r_{s}≤k−1} t^{k+s−1} ∏_{p=1}^{s} ∑_{j_{p}=1}^{n_{rp}} t (t^{2} + 1)^{n_{rp}−j_{p}}
= ∑_{s=0}^{k−1} ∑_{1≤r_{1}<...<r_{s}≤k−1} t^{k+s−1} ∏_{p=1}^{s} t\frac{(t^{2} + 1)^{n_{rp}} − 1}{(t^{2} + 1) − 1}
= ∑_{s=0}^{k−1} ∑_{1≤r_{1}<...<r_{s}≤k−1} t^{k−1} ∏_{p=1}^{s}((t^{2} + 1)^{n_{rp}} − 1)
= t^{k−1} ∏_{r=1}^{k−1}(1 + ((t^{2} + 1)^{n_{r}} − 1))
= t^{k−1}(t^{2} + 1)^{n(w,σ)} ,

by (43), as desired. □

Theorems 4.1 and 4.6 enable us to characterize the R-polynomials of pairs of permutations that differ by a transposition.

Corollary 4.7 Let σ, τ ∈ S_{n}, σ ≤ τ. Then the following are equivalent:

i) R_{σ,τ}(q) has a simple zero at q = 1;

ii) τσ^{−1} ∈ T;

iii) R_{σ,τ}(q) = (q − 1)(q^{2} − q + 1)^{r} for some r ∈ N.

Proof. It is clear that iii) implies i) and that (by Theorem 4.6) ii) implies iii). Now, if i) holds then [t](R̃_{σ,τ}(t)) ≠ 0 (else t^{2}|R̃_{σ,τ}(t) and hence (q −1)^{2}|R_{σ,τ}(q) which contradicts i)). By Theorem 4.1 (or, equivalently, by (27)) this implies that there is at least one R-chain from σ to τ of R-length one. Hence this R-chain has length one and therefore τσ^{−1} ∈ C(σ) and k(τσ^{−1}) = 2, which implies ii), as desired. □

We now come to the third main result of this section. This gives a simple poset-theoretic condition on the interval [σ, τ] which insures that the corresponding R-polynomial is a power of (q − 1). Again, we need first a preliminary result on the Bruhat order of S_{n}.

Lemma 4.8 Let σ ∈ S_{n}, and s̄ ∈ T be such that l(s̄σ) − l(σ) > 1. Then [σ, s̄σ] contains an interval isomorphic to S_{3}.

Proof. Let i, j ∈ [n], i < j, be such that s̄ = (σ(i), σ(j)). Since l(s̄σ) > l(σ) + 1 this implies that σ(i) < σ(j) and that T_{σ}[i, j; σ(i), σ(j)] ≠ ∅. So let

{k_{1}, …, k_{r}}_{<} =^{def} T_{σ}[i, j; σ(i), σ(j)] .

We now proceed by induction on l(s̄σ)−l(σ). If l(s̄σ)−l(σ) = 3 (note that l(s̄σ)−l(σ) is always odd) then r = 1 and it is easy to see that [σ, s̄σ] ≅ S_{3} (as posets). So assume that l(s̄σ) − l(σ) ≥ 5, and let τ =^{def} (σ(k_{r}), σ(j))σ. Then it is easy to check that

σ < τ < s̄τ < s̄σ ,  (52)

and that l(s̄τ) = l(s̄σ) − 1, l(τ) = l(σ) + 1. Therefore

1 < l(s̄τ) − l(τ) < l(s̄σ) − l(σ) .

Hence, by the induction hypothesis, [τ, s̄τ] contains an interval isomorphic to S_{3} and hence (by (52)) [σ, s̄σ] also does, as desired. □

Theorem 4.9 Let σ, τ ∈ S_{n}, σ ≤ τ, be such that [σ, τ] does not contain an interval isomorphic to S_{3}. Then

R_{σ,τ}(q) = (q − 1)^{l(τ)−l(σ)} .  (53)

Proof. We proceed by induction on d(σ, τ), (53) being clearly true if d(σ, τ) = 0. So assume that σ < τ and let w ∈ C_{i,j}(σ) be such that wσ ≤ τ, (where i =^{def} τ^{−1}(d), j =^{def} σ^{−1}(d), d =^{def} d(σ, τ)). Then

w = (σ(i_{k}), σ(i_{k−1}), …, σ(i_{1}))

where i = i_{1} < i_{2} < … < i_{k} = j, and σ(i) = σ(i_{1}) < σ(i_{2}) < … < σ(i_{k}) = σ(j). We now claim that n(w, σ) = 0. In fact, if n(w, σ) ≥ 1, then, by definition, there is r ∈ [k − 1] and i_{r} < a < i_{r+1} such that

σ(i_{r}) < σ(a) < σ(j) .

But wσ = s̄_{1} … s̄_{k−1}σ, where s̄_{l} =^{def} (σ(i_{l}), σ(i_{k})), for l = 1, …, k − 1, hence

v =^{def} s̄_{r+1} … s̄_{k−1}σ

is such that l(s̄_{r}v) − l(v) > 1 and

σ ≤ v < s̄_{r}v ≤ wσ ≤ τ .  (54)

Therefore, by Lemma 4.8, [v, s̄_{r}v] contains an interval isomorphic to S_{3} and hence, by (54), [σ, τ] also does, which contradicts our hypothesis.

So n(w, σ) = 0 for any w ∈ C_{i,j}(σ) such that wσ ≤ τ. Since, by Proposition 3.2, there is a unique w_{0} ∈ C_{i,j}(σ) such that n(w_{0}, σ) = 0, we conclude that there is at most one w ∈ C_{i,j}(σ) such that wσ ≤ τ, namely w = w_{0}. Therefore, from (25) we have that

R_{σ,τ}(q) = (q − 1)^{k(w_{0})−1} R_{w_{0}σ,τ}(q) .  (55)

Since σ ≤ τ we know that R_{σ,τ}(q) ≠ 0, hence, by (55), R_{w_{0}σ,τ}(q) ≠ 0 and therefore w_{0}σ ≤ τ. Hence [w_{0}σ, τ]_{≠}^{⊂}[σ, τ] and therefore [w_{0}σ, τ] does not contain any interval isomorphic to S_{3}. Hence, by our induction hypotheses,

R_{w_{0}σ,τ}(q) = (q − 1)^{l(τ)−l(w_{0}σ)}

and this, by (55) and Proposition 3.1, implies (53), as desired. □

As an immediate consequence of the preceding theorem we obtain the following result, which was first observed by M. Haiman and G. Kalai (private communication).

Corollary 4.10 Let σ, τ ∈ S_{n}, σ ≤ τ, be such that [σ, τ] is a lattice. Then

R_{σ,τ}(q) = (q − 1)^{l(τ)−l(σ)} .□

Theorem 4.9 also has interesting and nontrivial consequences for Kazhdan-Lusztig polynomials. In fact, it implies the following result.

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

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

In particular,

P_{u,v}(q) = 1 + ∑_{i=1}^{⌊ \frac{d}{2} ⌋}(h_{i} − h_{i−1})q^{i}

where d =^{def} l(v) − l(u) − 1, and (h_{0}, h_{1}, …, h_{d}) is the h-vector of [u, v]^{∗}.

Proof. We proceed by induction on l(v)−l(u), the thesis being clearly true if u = v. Note that by Theorem 4.9 and our hypotheses we have that R_{u,x}(q) = (q − 1)^{l(x)−l(u)} for all x ∈ [u, v]. Therefore, using part iv) of Theorem 2.3 and our induction hypothesis we obtain that

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

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

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

as desired. The second statement then follows from (56) and the well known fact (see, e.g., [25], Theorem 3.14.9, or [26], Theorem 2.4) that the h-vector of an Eulerian poset is symmetric, so that h_{i} = h_{d−i} for i = 0, …, d. □

It had long been noticed (see, e.g., [5], §5.3, and [26], p. 200) that the gpolynomials of Eulerian posets have some striking similarities with Kazhdan-Lusztig polynomials. The preceding result is the first to establish a direct, precise connection, between the two. Note that equation (56) is in general false. For example, P_{123,321}(q) = 1 but g([123, 321]^{∗}; q) = 1 − q.

We can now use some standard results from the theory of g-polynomials to compute the Kazhdan-Lusztig polynomials of some classes of intervals. For n ∈ N we denote by B_{n} and C_{n} the Boolean algebra of rank n and the face lattice of an n-dimensional cube, respectively.

Corollary 4.12 Let u, v ∈ S_{n}, u ≤ v, be such that [u, v] ≅ B_{l(v)−l(u)} (as posets). Then

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

Proof. This follows immediately from Theorem 4.11 and the well known fact that g(B_{d}; q) = 1 for all d ∈ N (see, e.g., [26], Proposition 2.1, or [25], Example 3.14.8). □

Corollary 4.13 Let u, v ∈ S_{n}, u ≤ v, be such that [u, v] ≅ C_{d}^{∗} (as posets) where

d =^{def} l(v) − l(u) − 1. Then

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

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

Proof. (58) follows immediately from Theorem 4.11 and Proposition 2.6 of [26] (see also [25], Chapter 3, Exercise 71(f)). The second statement was first proved by L. Shapiro (unpublished, see also [25], Chapter 3, Exercise 71(g)). □

One other consequence of Theorem 4.11 is the following.

Proposition 4.14 Let u, v ∈ S_{n}, u ≤ v, be such that [u, v] does not contain an interval isomorphic to S_{3}. Then

[q](P_{u,v}(q)) = r_{1} − d − 1 ,

and

[q^{2}](P_{u,v}(q)) = (\begin{matrix}d+1 \\ 2 \end{matrix}) − d r_{1} + r_{2} + r_{3}^{c} ,

where d =^{def} l(v) − l(u) − 1, r_{i} =^{def} |{x ∈ [u, v] : l(v) − l(x) = i}|, for i = 0, …, d + 1,

and r_{3}^{c} =^{def} |{x ∈ [u, v] : [x, v] ≅ C_{2}}|.

Proof. Note first that it follows from Proposition 1 and Theorem 2 of [3], and from results of Jantzen (see [17], p.177) that every interval in S_{n} of length 2 or 3 is isomorphic to either B_{2}, B_{3}, S_{3}, or C_{2}. Since [u, v]^{∗} does not contain any interval isomorphic to S_{3} we obtain from (2) that

f([u, v]^{∗}; q) = (q − 1)^{d} + r_{1}(q − 1)^{d−1} g(B_{1}; q) + r_{2}(q − 1)^{d−2} g(B_{2}; q)
+ (q − 1)^{d−3}(r_{3}^{c} g(C_{2}; q) + (r_{3} − r_{3}^{c}) g(B_{3}; q)) + R(q)  (59)

where R(q) is a polynomial in q of degree ≤ d − 3.But it follows easily from the definitions that g(B_{1}; q) = g(B_{2}; q) = g(B_{3}; q) = 1 and g(C_{2}; q) = 1 + q, hence equating the coefficients of q^{d−i}, for i = 0, 1, 2, on both sides of (59), and using (1) and Theorem 4.11 yields the result. □ Acknowledgements. I would like to thank Adriano Garsia, Mark Haiman, Gil Kalai, and Anatoly Vershik for some useful conversations, Boris Shapiro for arousing my interest in the polynomials studied in [22], and Anders Björner for many useful suggestions and conversations. I would also like to thank the Institut Mittag-Leffler for hospitality, financial support, and for providing an ideal environment for research, during the preparation of this work.

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, M. Wachs, Bruhat order of Coxeter groups and shellability, Adv. in Math. 43 (1982), 87-100.

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

[4] A. Björner, Posets, regular CW complexes and Bruhat order, European J. Combin. 5 (1984), 7-16.

[5] A. Björner, Face numbers of complexes and polytopes, Proc. International Congress of Mathematicians, Berkeley, California, U.S.A., (1986), 1408-1418.

[6] N. Bourbaki, Groupes et algèbres de Lie, Ch. 4-6, Hermann, Paris, 1968; Masson, Paris, 1981.

[7] V. V. Deodhar, Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative Möbius function, Invent. Math. 39 (1977), 187-198.

[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] V. V. Deodhar, A combinatorial setting for questions in Kazhdan-Lusztig Theory, Geom. Dedicata, 36 (1990), 95-120.

[10] M. Dyer, On the “Bruhat graph” of a Coxeter system, preprint.

[11] M. Dyer, Hecke algebras and shellings of Bruhat intervals, preprint.

[12] M. Dyer, Hecke algebras and shellings of Bruhat intervals II: twisted Bruhat orders, preprint.

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

[14] H. L. Hiller, Combinatorics and intersections of Schubert varieties, Comment. Math. Helv. 57 (1982), 41-59.

[15] J. E. Humphreys, Introduction to Lie Algebras and Representation Theory, Springer, New York, 1972.

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

[17] J. Jantzen, Moduln mit einem höchsten Gewicht, Lecture Notes in Math., Vol. 750, Springer, Berlin, 1979.

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

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

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

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

[22] B. Z. Shapiro and A. D. Vainshtein, Euler characteristics for links of Schubert cells in the space of complete flags, Adv. Sov. Math., vol. 1, AMS, Providence, 1990, pp. 273-286.

[23] B. Z. Shapiro, M. Z. Shapiro, A. D. Vainshtein, On the geometrical meaning of the R-polynomials in the Kazhdan-Lustig theory, preprint.

[24] Shi Jian-yi, The Kazhdan-Lusztig cells in certain affine Weyl groups, Lect. Notes in Math., Vol. 1179, Springer, Berlin, 1986.

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

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

[27] R. P. Stanley, Subdivisions and local h-vectors, preprint.

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