Parabolic Kazhdan-Lusztig R-polynomials for tight quotients of the symmetric groups ^{1}

Francesco Brenti^{2} Dipartimento di Matematica Universitá di Roma “Tor Vergata” Via della Ricerca Scientifica, 1 00133 Roma, Italy brenti@mat.uniroma2.it

Abstract

We give explicit closed combinatorial formulas for the parabolic Kazhdan-Lusztig R-polynomials of the tight quotients of the symmetric groups. We give two formulations of our result, one in terms of permutations and one in terms of Motzkin paths. As an application of our results we obtain explicit closed combinatorial formulas for certain sums and alternating sums of ordinary Kazhdan-Lusztig R-polynomials.

1 Introduction

In their fundamental paper [11] Kazhdan and Lusztig defined, for any 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., [9, Chap.7] or [2, Chap.5]). These polynomials play an important role in several areas of mathematics, including the algebraic geometry and topology of Schubert varieties and representation theory (see, e.g., [2, Chap.5], and the references cited there). In order to prove the existence of these polynomials Kazhdan and Lusztig introduced another family of polynomials, usually called the R-polynomials, whose knowledge is equivalent to that of the Kazhdan-Lusztig polynomials.

In 1987 Deodhar ([5]) introduced parabolic analogues of all these polynomials. These parabolic Kazhdan-Lusztig and R-polynomials reduce to the ordinary ones for the trivial parabolic subgroup of W and are also related to them in other ways (see, e.g., Proposition 2.2 below). Besides these connections the parabolic polynomials also play a direct role in several areas including the theories of generalized Verma modules ([4]), tilting modules ([13], [14]), quantized Schur algebras ([17]), Macdonald polynomials ([8], [7]), Schubert varieties in partial flag manifolds ([10]), and in the representation theory of the Lie algebra gl_{n} ([12]).

12000 Mathematics Subject Classification: Primary 20F55; Secondary 05E99.

2Partially supported by MIUR.

The purpose of this work is to study the parabolic Kazhdan-Lusztig R-polynomials for the tight quotients of the symmetric groups. These quotients were first introduced and studied by Stembridge in [16], who classified them for the finite Coxeter groups. For the symmetric groups S_{n}, the tight quotients are the ones obtained by deleting either a single node (maximal quotients) or two adjacent nodes in the Dynkin diagram of S_{n}. The parabolic Kazhdan-Lusztig R-polynomials for the maximal quotients of the symmetric groups have been computed in [3], here we complete the computation of the parabolic R-polynomials of the tight quotients of the symmetric groups by dealing with the other ones. More precisely, we obtain explicit combinatorial product formulas for these polynomials. We give two formulations of our result, one in terms of permutations and one in terms of Motzkin paths. As an application of our results, we obtain combinatorial closed product formulas for certain sums and alternating sums of ordinary Kazhdan-Lusztig R-polynomials.

The organization of the paper is as follows. In the next section we recall definitions, notation and results that are used in the rest of this work. In §3 we prove our main result, and derive some consequences of it.

2 Preliminaries

In this section we collect some definitions, notation and results that are used in the rest of this paper. We let P =^{def} {1, 2, 3, …} and N=^{def}P ∪{0}. For m, n ∈ N, m ≥ n, we let [n, m] =^{def} {n, n + 1, …, m − 1, m} and [n] =^{def} [1, n] (where [0] =^{def} ∅). The cardinality of a set A will be denoted by |A|. For S ⊆ N we write S = {s_{1}, …, s_{k}}_{<} to mean that S = {s_{1}, …, s_{k}} and s_{1} < s_{2} < ⋯ < s_{k}. If P is a statement then we let χ(P) =^{def} 1 if P is true and χ(P) =^{def} 0 if P is false. For i, j ∈ N we let δ_{i,j} be the Kronecker delta.

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 σ = a_{1} ⋯ a_{n} to mean that σ(i) = a_{i} for all i ∈ [n]. We also write σ in disjoint cycle form (see, e.g., [15], p.17) and we usually omit writing the 1-cycles of σ. So, for example, if σ = (9, 7, 1, 3, 5)(2, 6) then σ(1) = 3, σ(2) = 6, σ(3) = 5, σ(4) = 4, etc... Given σ, τ ∈ S_{n} we let στ =^{def} σ ∘ τ (composition of functions) so that, for example, (1, 2)(2, 3) = (1, 2, 3).

Let n ∈ P. By a Motzkin path of length n we mean a function M : [0, n] → Z such that M(0) = 0 and M(j) − M(j − 1) ∈ {0, 1, −1} for all j ∈ [n]. If j ∈ [n] then we call M(j) − M(j − 1) the j-th step of M and say that such a step is up (respectively, horizontal, down) if M(j) − M(j − 1) = 1 (respectively, 0, −1). We will usually depict a Motzkin path by its diagram. So, for example, the Motzkin path depicted in Figure 1 is the Motzkin path M : [0, 9] → Z such that (M(1), …, M(9)) = (1, 0, −1, −1, 0, 0, −1, −2, −1).

[figure]

Figure 1.

We follow [9] and [2] for general Coxeter groups notation and terminology. In particular, given a Coxeter system (W, S) and u ∈ W we denote by ℓ(u) the length of u in W, with respect to S, and we let D(u) =^{def} {s ∈ S : ℓ(us) < ℓ(u)} and ε_{u} =^{def} (−1)^{ℓ(u)}. For u, v ∈ W we let ℓ(u, v) =^{def} ℓ(v) − ℓ(u). We denote by e the identity of W, and we let T =^{def} {usu^{−1} : u ∈ W, s ∈ S} be the set of reflections of W. Given J ⊆ S we let W_{J} be the parabolic subgroup generated by J and

W^{J} =^{def} {u ∈ W : ℓ(su) > ℓ(u) for all s ∈ J}.  (1)

Note that W^{∅} = W. We always assume that W^{J} is partially ordered by Bruhat order. Recall 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 ℓ(t_{i} ⋯ t_{1} x) > ℓ(t_{i−1} ⋯ t_{1}x) for i = 1, …, r.

The following result is due to Deodhar, and we refer the reader to [5, §§2-3] for its proof.

Theorem 2.1 Let (W, S) be a Coxeter system, and J ⊆ S. Then, for each x ∈ {−1, q}, there is a unique family of polynomials {R_{u,v}^{J,x}(q)}_{u,v∈W^{J}} ⊆ Z[q] such that, for all u, v ∈ W^{J}:

i) R_{u,v}^{J,x}(q) = 0 if u ≰ v;

ii) R_{u,u}^{J,x}(q) = 1; iii) if u < v and s ∈ D(v) then

R_{u,v}^{J,x}(q) = \{ \begin{matrix}R_{us,vs}^{J,x}(q), & if us < u, \\ (q − 1)R_{u,vs}^{J,x}(q) + qR_{us,vs}^{J,x}(q), & if u < us ∈ W^{J}, \\ (q − 1 − x)R_{u,vs}^{J,x}(q), & if u < us ∉ W^{J}. \end{matrix}

The polynomials R_{u,v}^{J,x}(q), whose existence is guaranteed by the previous theorem, are called the parabolic R-polynomials of W^{J} of type x. It follows immediately from Theorem 2.1 and from well known facts (see, e.g., [9, §7.5]) that R_{u,v}^{∅,−1}(q) (= R_{u,v}^{∅,q}(q)) are the (ordinary) R-polynomials of W which we will denote simply by R_{u,v}(q), as customary. The parabolic R-polynomials can then be used to define and compute the parabolic Kazhdan-Lusztig polynomials of W^{J} of type x (see [5, Proposition 3.1]).

The parabolic R-polynomials are related to their ordinary counterparts also in the following way.

Proposition 2.2 Let (W, S) be a Coxeter system, J ⊆ S, and u, v ∈ W^{J}. Then

R_{u,v}^{J,x}(q) = ∑_{w∈W_{J}}(−x)^{ℓ(w)}R_{wu,v}(q),

for all x ∈ {−1, q}.

A proof of this result can be found in [5, Proposition 2.12].

There is one more property of the parabolic R-polynomials that we will use and that we recall for the reader’s convenience. A proof of it can be found in [6, Corollary 2.2].

Proposition 2.3 Let (W, S) be a Coxeter system, and J ⊆ S. Then

q^{ℓ(u,v)}R_{u,v}^{J,q} (\frac{1}{q}) = (−1)^{ℓ(u,v)}R_{u,v}^{J,−1}(q)

for all u, v ∈ W^{J}.

It is well known (see, e.g., [2, Chap. 1]) that the symmetric group S_{n} is a Coxeter group with respect to the generating set S = {s_{1}, …, s_{n−1}} where s_{i} = (i, i + 1) for all i ∈ [n − 1]. The following result is also well known (see, e.g., [2, §1.5]).

Proposition 2.4 Let v ∈ S_{n}. Then

ℓ(v) = |{(i, j) ∈ [n]^{2} : i < j, v(i) > v(j)}|

and

D(v) = {(i, i + 1) ∈ S : v(i) > v(i + 1)}.

For k ∈ [n] and U, T ⊆ [n] such that |U| = |T | = k let U ⪯ T if and only if

u_{i} ≤ t_{i} for all i ∈ [k] where {u_{1}, …, u_{k}}_{<} =^{def} U and {t_{1}, …, t_{k}}_{<} =^{def} T. Note that

U ⪯ T if and only if

|{j ≥ r : j ∈ T }| ≥ |{j ≥ r : j ∈ U}|  (2)

for all r ∈ [n]. The following result is well known (see, e.g., [2, Theorem 2.6.3]).

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

i) u ≤ v;

ii) u([j]) ⪯ v([j]) for all j ∈ [n − 1];

iii) u([j]) ⪯ v([j]) for all j such that s_{j} ∈ D(u).

Our purpose in this work is to study the parabolic R-polynomials of the tight quotients of the symmetric groups. These quotients were first introduced and studied by Stembridge in [16], who classified them for the finite Coxeter groups. For the symmetric groups S_{n}, the tight quotients are the ones obtained by deleting either a single node (maximal quotients) or two adjacent nodes in the Dynkin diagram of S_{n}. The parabolic R-polynomials for the maximal quotients have been computed in [3], in this work we complete the computation of the parabolic R-polynomials of the tight quotients by dealing with the other ones.

Let n ∈ P and 2 ≤ i ≤ n − 1. For simplicity, we let S_{n}^{(i)} =^{def} (S_{n})^{J_{i}} where J_{i} =^{def} {s_{1}, s_{2}, …, s_{i−2}, s_{i+1}, …, s_{n−1}}. It follows immediately from (1), Proposition 2.4 and well known facts (see, e.g., [2, Proposition 1.4.2]) that

S_{n}^{(i)} = {v ∈ S_{n} : v^{−1}(1) < ⋯ < v^{−1}(i − 1), v^{−1}(i + 1) < ⋯ < v^{−1}(n)}. (3)

For u, v ∈ S_{n}^{(i)} and r ∈ [n] we let

a_{r}(u, v) =^{def} |{j ≥ r : j ∈ v^{−1}([i − 1])}| − |{j ≥ r : j ∈ u^{−1}([i − 1])}|  (4)

and

ã_{r}(u, v) =^{def} |{j ≥ r : j ∈ v^{−1}([i])}| − |{j ≥ r : j ∈ u^{−1}([i])}|.  (5)

So, for example, if n = 9, i = 5, u = 1 6 2 3 5 7 4 8 9 and v = 6 5 7 1 8 2 3 9 4 then (a_{1}(u, v), …, a_{9}(u, v)) = (0, 1, 1, 2, 2, 2, 1, 1, 1) and (ã_{1}(u, v), …, ã_{9}(u, v)) = (0, 1, 0, 1, 1, 2, 1, 1, 1). Note that

ã_{k}(u, v) = \{ \begin{matrix}a_{k}(u, v) + 1, & if u^{−1}(i) < k ≤ v^{−1}(i), \\ a_{k}(u, v) − 1, & if v^{−1}(i) < k ≤ u^{−1}(i), \\ a_{k}(u, v), & otherwise, \end{matrix}  (6)

for all k ∈ [n].

Proposition 2.6 Let u, v ∈ S_{n}^{(i)}. Then u ≤ v if and only if a_{r}(u, v) ≥ 0 and ã_{r}(u, v) ≥ 0 for all r ∈ [n].

Proof. It is well known (see, e.g., [2, Cor. 2.2.5]) that u ≤ v if and only if u^{−1} ≤ v^{−1}. Therefore we conclude from (3) and Theorem 2.5 that u ≤ v if and only if u^{−1}([i − 1]) ⪯ v^{−1}([i − 1]) and u^{−1}([i]) ⪯ v^{−1}([i]). The result then follows from (2), (4), and (5). □

3 Main result

In this section we prove our main result and derive some consequences of it. More precisely, we obtain explicit combinatorial product formulas for the parabolic Rpolynomials of S_{n}^{(i)}. As an application of our results, we derive explicit combinatorial formulas for certain sums and alternating sums of ordinary Kazhdan-Lusztig Rpolynomials.

For u, v ∈ S_{n}^{(i)} we define

D(u, v) =^{def} v^{−1}([i − 1]) \ u^{−1}([i − 1]),

and

D̃(u, v) =^{def} v^{−1}([i]) \ u^{−1}([i]).

So, for example, if n = 9, i = 5, v = 657182394, and u = 162375489, then D(u, v) = {6, 9} and D̃(u, v) = {2, 9}. Note that D(u, v) = D̃(u, v) if u^{−1}(i) = v^{−1}(i).

Theorem 3.1 Let u, v ∈ S_{n}^{(i)}, u ≤ v. Then

R_{u,v}^{J_{i},q} = \{ \begin{matrix}ε_{u}ε_{v} (1 − q + c q^{1+a_{u^{−1}(i)}(u,v)}) ∏_{k∈D(u,v)}(1 − q^{a_{k}(u,v)}), & if u^{−1}(i) ≤ v^{−1}(i), \\ ε_{u}ε_{v} (1 − q + c q^{1+ã_{u^{−1}(i)}(u,v)}) ∏_{k∈D̃(u,v)}(1 − q^{ã_{k}(u,v)}), & if u^{−1}(i) ≥ v^{−1}(i), \end{matrix}

where c =^{def} δ_{u^{−1}(i),v^{−1}(i)}.

Proof. We proceed by induction on ℓ(v) ≥ 0, the result being easy to check if ℓ(v) = 0. So assume ℓ(v) > 0. Let s ∈ D(v), say s = (j, j +1). Then v(j) > v(j +1) and hence, since v ∈ S_{n}^{(i)}, v(j) ≥ i ≥ v(j + 1). Note that it follows immediately from our definitions that

a_{k}(u, v) = a_{k}(u, vs) = a_{k}(us, vs)  (7)

and

ã_{k}(u, v) = ã_{k}(u, vs) = ã_{k}(us, vs)  (8)

for all k ∈ [n] \ {j + 1}. We will use these facts throughout the proof often without explicit mention. For simplicity, we write “R_{w,z}” rather than “R_{w,z}^{J_{i},q}” for all w, z ∈ S_{n}^{(i)}.

Assume first that u^{−1}(i) ≤ v^{−1}(i). There are two main cases to consider.

i) v(j + 1) < i.

There are then six cases to consider.

a) u(j) ≥ i > u(j + 1).

Then u > us, (us)^{−1}(i) ≤ (vs)^{−1}(i), D(u, v) = D(us, vs) ∌ j + 1, and δ_{(us)^{−1}(i),(vs)^{−1}(i)} = δ_{u^{−1}(i),v^{−1}(i)} so we have from Theorem 2.1 and our induction hypotheses that

R_{u,v} = R_{us,vs}
= ε_{us}ε_{vs}(1 − q + δ_{(us)^{−1}(i),(vs)^{−1}(i)} q^{a_{(us)^{−1}(i)}(us,vs)+1}) ∏_{k∈D(us,vs)}(1 − q^{a_{k}(us,vs)})
= ε_{u}ε_{v} (1 − q + δ_{u^{−1}(i),v^{−1}(i)} q^{a_{(us)^{−1}(i)}(us,vs)+1}) ∏_{k∈D(u,v)}(1 − q^{a_{k}(u,v)}),

and the result follows since a_{u^{−1}(i)}(u, v) = a_{(us)^{−1}(i)}(us, vs) if u^{−1}(i) = v^{−1}(i). b) u(j) > i = u(j + 1).

Then v(j) > i, u > us, (us)^{−1}(i) < (vs)^{−1}(i), D(us, vs) = (D(u, v)\{j +1})∪ {j}, so we have from Theorem 2.1 and our induction hypotheses that

R_{u,v} = R_{us,vs}
= ε_{us}ε_{vs} (1 − q) ∏_{k∈D_{(}us,vs)}(1 − q^{a_{k}(us,vs)})
= ε_{u}ε_{v} (1 − q) (1 − q^{a_{j}(us,vs)}) ∏_{k∈D(u,v)\{j+1}}(1 − q^{a_{k}(u,v)}),

and the result follows since a_{j}(us, vs) = a_{j+1}(u, v).

c) i < u(j) < u(j + 1). Then u < us ∉ S_{n}^{(i)}, u^{−1}(i) ≤ (vs)^{−1}(i), D(u, vs) = (D(u, v) \ {j + 1}) ∪ {j}, δ_{u^{−1}(i),(vs)^{−1}(i)} = δ_{u^{−1}(i),v^{−1}(i)}, so we have from Theorem 2.1 and our induction hypotheses that

R_{u,v} = −R_{u,vs}
= −ε_{u}ε_{vs} (1 − q + δ_{u^{−1}(i),(vs)^{−1}(i)} q^{a_{u^{−1}(i)}(u,vs)+1}) ∏_{k∈D(u,vs)}(1 − q^{a_{k}(u,vs)})
= ε_{u}ε_{v} (1 − q + δ_{u^{−1}(i),v^{−1}(i)} q^{a_{u^{−1}(i)}(u,vs)+1}) (1 − q^{a_{j}(u,vs)})

∏_{k∈D(u,v)\{j+1}}(1 − q^{a_{k}(u,v)}),

and the result follows since a_{j}(u, vs) = a_{j+1}(u, v) and u^{−1}(i) ≠ j + 1.

d) u(j) = i < u(j + 1) Then u < us ∈ S_{n}^{(i)}, u^{−1}(i) + 1 = (us)^{−1}(i) ≤ (vs)^{−1}(i), D(u, vs) = (D(u, v) \ {j + 1}) ∪ {j} = D(us, vs), δ_{u^{−1}(i),v^{−1}(i)} = δ_{(us)^{−1}(i),(vs)^{−1}(i)}. Furthermore, a_{j+1}(us, vs) = a_{j+2}(u, v) so, by (6), (7), (8) and Proposition 2.6, us ≤ vs. Hence we have from Theorem 2.4 and our induction hypotheses that

R_{u,v} = qR_{us,vs} + (q − 1)R_{u,vs}
= (1 − q)^{2}(−ε_{u}ε_{vs}) ∏_{k∈D(u,vs)}(1 − q^{a_{k}(u,vs)})
+ q ε_{us}ε_{vs} (1 − q + δ_{(us)^{−1}(i),(vs)^{−1}(i)} q^{a_{(us)^{−1}(i)}(us,vs)+1})

∏_{k∈D(us,vs)}(1 − q^{a_{k}(us,vs)})

= ε_{u}ε_{v} ((1 − q)^{2} + q(1 − q + δ_{u^{−1}(i),v^{−1}(i)} q^{a_{j+1}(us,vs)+1})

(1 − q^{a_{j}(u,v)}) ∏_{k∈D(u,v)\{j+1}}(1 − q^{a_{k}(u,v)}),

and the result follows since a_{j+1}(us, vs) + 1 = a_{j}(u, v) = a_{j+1}(u, v).

e) u(j) < u(j + 1) < i. Then u < us ∉ S_{n}^{(i)}, u^{−1}(i) ≤ (vs)^{−1}(i), D(u, vs) = D(u, v) ∌ j + 1, δ_{u^{−1}(i),v^{−1}(i)} = δ_{u^{−1}(i),(vs)^{−1}(i)} and we have from Theorem 2.1 and our induction hypotheses that

R_{u,v} = −R_{u,vs}
= −ε_{u}ε_{vs} (1 − q + δ_{u^{−1}(i),(vs)^{−1}(i)} q^{a_{u^{−1}(i)}(u,vs)+1}) ∏_{k∈D(u,vs)}(1 − q^{a_{k}(u,vs)})
= ε_{u}ε_{v} (1 − q + δ_{u^{−1}(i),v^{−1}(i)} q^{a_{u^{−1}(i)}(u,v)+1}) ∏_{k∈D(u,v)}(1 − q^{a_{k}(u,v)}),

as desired.

f) u(j) < i ≤ u(j + 1). Then u < us ∈ S_{n}^{(i)}, (us)^{−1}(i) ≤ u^{−1}(i) ≤ v^{−1}(i) ≤ (vs)^{−1}(i), D(u, vs) = D(u, v) \ {j + 1}, D(us, vs) = (D(u, v) \ {j + 1}) ∪ {j}, and δ_{u^{−1}(i),v^{−1}(i)} = δ_{(us)^{−1}(i),(vs)^{−1}(i)} = δ_{u^{−1}(i),(vs)^{−1}(i)}. Then from Theorem 2.1 and our induction hypotheses we have that

R_{u,v} = q R_{us,vs} + (q − 1)R_{u,vs}
= (q − 1)ε_{u}ε_{vs}(1 − q + δ_{u^{−1}(i),(vs)^{−1}(i)} q^{a_{u^{−1}(i)}(u,vs)+1})

∏_{k∈D(u,vs)}(1 − q^{a_{k}(u,vs)}) + χ(us ≤ vs) qε_{us}ε_{vs}

(1 − q + δ_{(us)^{−1}(i),(vs)^{−1}(i)} q^{a_{(us)^{−1}(i)}(us,vs)+1}) ∏_{k∈D(us,vs)}(1 − q^{a_{k}(us,vs)})

= ε_{u}ε_{v} ((1 − q) + χ(us ≤ vs) q(1 − q^{a_{j}(us,vs)}))

(1 − q + δ_{u^{−1}(i),v^{−1}(i)} q^{a_{u^{−1}(i)}(u,v)+1}) ∏_{k∈D(u,v)\{j+1}}(1 − q^{a_{k}(u,v)})

where we have used the fact that, if δ_{u^{−1}(i),v^{−1}(i)} = 1, then u^{−1}(i) = (us)^{−1}(i) ≠ j + 1, and the result follows if us ≤ vs since a_{j}(us, vs) + 1 = a_{j+1}(u, v). If us ≰ vs then, by (6) and Proposition 2.6, a_{j+1}(us, vs) < 0. But a_{j+1}(us, vs) + 1 = a_{j+1}(u, v) − 1 = a_{j+2}(u, v) so a_{j+1}(u, v) = 1 and the result again follows. ii) v(j + 1) = i. There are then seven cases to consider.

a) u(j) > i ≥ u(j + 1). Then we conclude as in case i)a) above.

b) u(j) = i > u(j + 1) Then u > us, (us)^{−1}(i) > (vs)^{−1}(i), D̃(us, vs) = D(u, v) ∌ j + 1 so we have from Theorem 2.1 that

R_{u,v} = R_{us,vs} = ε_{us}ε_{vs}(1 − q) ∏_{k∈D̃(us,vs)}(1 − q^{ã_{k}(us,vs)})
= ε_{u}ε_{v} (1 − q) ∏_{k∈D(u,v)}(1 − q^{a_{k}(u,v)}),

as desired.

c) i < u(j) < u(j + 1). Then u < us ∉ S_{n}^{(i)}, u^{−1}(i) < (vs)^{−1}(i), D(u, vs) = D(u, v) ∌ j + 1, and the result follows from Theorem 2.1 and our induction hypothesis.

d) u(j) = i < u(j + 1). Then u < us ∈ S_{n}^{(i)}, u^{−1}(i) = (vs)^{−1}(i) < (us)^{−1}(i), D(u, vs) = D(u, v) ∌ j + 1, D̃(us, vs) = D(u, v) ∪ {j}. Then by Theorem 2.1 and our induction hypothesis we have that

R_{u,v} = q R_{us,vs} + (q − 1)R_{u,vs}
= (q − 1) ε_{u}ε_{vs}(1 − q + q^{a_{j}(u,vs)+1}) ∏_{k∈D(u,vs)}(1 − q^{a_{k}(u,vs)})

+q χ(us ≤ vs)ε_{us}ε_{vs} (1 − q) ∏_{k∈D̃(us,vs)}(1 − q^{ã_{k}(us,vs)})

= ε_{u}ε_{v} (1 − q) ∏_{k∈D(u,v)}(1 − q^{a_{k}(u,v)})

(1 − q + q^{a_{j}(u,vs)+1} + q χ(us ≤ vs)(1 − q^{ã_{j}(us,vs)})),

and the result follows if us ≤ vs since a_{j}(u, vs) = ã_{j}(us, vs). If us ≰ vs then, by (6) and Proposition 2.6, ã_{j+1}(us, vs) < 0. But ã_{j+1}(us, vs) = a_{j}(u, vs) − 1 so, by Proposition 2.6, a_{j}(u, vs) = 0 and the result again follows. e) u(j) < u(j + 1) < i

Then we conclude as in case i)e) above, except that δ_{u^{−1}(i),v^{−1}(i)} = δ_{u^{−1}(i),(vs)^{−1}(i)} = 0 in this case.

f) u(j) < i < u(j + 1).

Then u < us ∈ S_{n}^{(i)}, (us)^{−1}(i) = u^{−1}(i) < (vs)^{−1}(i), D(u, vs) = D(u, v) = D(us, vs) ∌ j + 1. Furthermore, ã_{j+1}(us, vs) = a_{j+1}(us, vs) = a_{j}(u, v) so, by Proposition 2.6, us ≤ vs and we have from Theorem 2.1 and our induction hypotheses that

R_{u,v} = q R_{us,vs} + (q − 1) R_{u,vs}
= (−ε_{u}ε_{vs})(1 − q)^{2} ∏_{k∈D(u,vs)}(1 − q^{a_{k}(u,vs)})

+ε_{us}ε_{vs} q (1 − q) ∏_{k∈D(us,vs)}(1 − q^{a_{k}(us,vs)})

= ε_{u}ε_{v} (1 − q) ∏_{k∈D(u,v)}(1 − q^{a_{k}(u,v)}),

as desired.

g) u(j) < i = u(j + 1).

Then u < us ∈ S_{n}^{(i)}, (us)^{−1}(i) = (vs)^{−1}(i) < u^{−1}(i), D(us, vs) = D(u, v) ∌ j + 1, D̃(u, vs) = D(u, v). Furthermore, ã_{j+1}(us, vs) = a_{j+1}(us, vs) = a_{j}(u, v) so, by Proposition 2.6, us ≤ vs and we have from Theorem 2.1 and our induction hypotheses that

R_{u,v} = qR_{us,vs} + (q − 1)R_{u,vs}
= (−ε_{u} ε_{vs})(1 − q)^{2} ∏_{k∈D̃(u,vs)}(1 − q^{ã_{k}(u,vs)})

+q ε_{us}ε_{vs}(1 − q + q^{a_{j}(us,vs)+1}) ∏_{k∈D(us,vs)}(1 − q^{a_{k}(us,vs)})

= ε_{u}ε_{v}((1 − q)^{2} + q(1 − q + q^{a_{j}(us,vs)+1})) ∏_{k∈D(u,v)}(1 − q^{a_{k}(u,v)}),

and the result follows since a_{j}(us, vs) + 1 = a_{j+1}(u, v).

Assume now that u^{−1}(i) > v^{−1}(i). There are again two main cases to consider.

i) v(j) > i.

There are then five cases to consider.

a) u(j) > u(j + 1).

Then u > us, u(j + 1) ≤ i, (us)^{−1}(i) > (vs)^{−1}(i), D̃(us, vs) = D̃(u, v) ∌ j + 1, so by Theorem 2.1 and our induction hypotheses we have that

R_{u,v} = R_{us,vs} = ε_{us}ε_{vs} (1 − q) ∏_{k∈D̃(us,vs)}(1 − q^{ã_{k}(us,vs)}).

and the result follows.

b) i < u(j) < u(j + 1).

Then u < us ∉ S_{n}^{(i)}, u^{−1}(i) > (vs)^{−1}(i), D̃(u, vs) = (D̃(u, v) \ {j + 1}) ∪ {j}, so by Theorem 2.1 and our induction hypotheses we have that

R_{u,v} = −R_{u,vs} = −ε_{u}ε_{vs} (1 − q) ∏_{k∈D̃(u,vs)}(1 − q^{ã_{k}(u,vs)})
= ε_{u}ε_{v} (1 − q) (1 − q^{ã_{j}(u,vs)}) ∏_{k∈D̃(u,v)\{j+1}}(1 − q^{ã_{k}(u,v)})

and the result follows since ã_{j}(u, vs) = ã_{j+1}(u, v).

c) u(j) ≤ i < u(j + 1).

Then u < us ∈ S_{n}^{(i)}, (us)^{−1}(i) ≥ u^{−1}(i) > v^{−1}(i) ≥ (vs)^{−1}(i), D̃(u, vs) = D̃(u, v) \ {j + 1}, D̃(us, vs) = (D̃(u, v) \ {j + 1}) ∪ {j}. Hence, by induction and Theorem 2.1 we conclude that

R_{u,v} = (q − 1)R_{u,vs} + q R_{us,vs}
= (−ε_{u}ε_{vs})(1 − q)^{2} ∏_{k∈D̃(u,vs)}(1 − q^{ã_{k}(u,vs)})

+ε_{us}ε_{vs}χ(us ≤ vs)(1 − q) q ∏_{k∈D̃(us,vs)}(1 − q^{ã_{k}(us,vs)})

= ε_{u}ε_{v}(1 − q) ∏_{k∈D̃(u,v)\{j+1}}(1 − q^{ã_{k}(u,v)})

(1 − q + q χ(us ≤ vs)(1 − q^{ã_{j}(us,vs)}))

and the result follows if us ≤ vs since ã_{j}(us, vs) + 1 = ã_{j+1}(u, v). If us ≰ vs then, by (6) and Proposition 2.6, ã_{j+1}(us, vs) < 0. But ã_{j+1}(us, vs) = ã_{j+1}(u, v) − 2 = ã_{j+1}(u, vs) − 1, so we conclude from Proposition 2.6 that ã_{j+1}(u, v) = 1 and the result again follows. d) u(j) < u(j + 1) < i Then u < us ∉ S_{n}^{(i)}, u^{−1}(i) > (vs)^{−1}(i), D̃(u, vs) = D̃(u, v) ∌ j + 1, so the result follows from Theorem 2.1 and our induction hypotheses.

e) u(j) < u(j + 1) = i Then u < us ∈ S_{n}^{(i)}, v(j+1) < i, u^{−1}(i) > (us)^{−1}(i) > v^{−1}(i) = (vs)^{−1}(i), D̃(u, vs) = D̃(u, v) = D̃(us, vs) ∌ j + 1. Furthermore, a_{j+1}(us, vs) = ã_{j+1}(us, vs) = ã_{j}(u, v) so, by Proposition 2.6, us ≤ vs. Hence by Theorem 2.1 and our induction hypotheses we have that

R_{u,v} = q R_{us,vs} + (q − 1) R_{u,vs}
= (−ε_{u}ε_{vs}) (1 − q)^{2} ∏_{k∈D̃(u,vs)}(1 − q^{ã_{k}(u,vs)})

+ε_{us}ε_{vs}q(1 − q) ∏_{k∈D̃(us,vs)}(1 − q^{ã_{k}(us,vs)})

= ε_{u}ε_{v} (1 − q) ∏_{k∈D̃(u,v)}(1 − q^{ã_{k}(u,v)})

and the result follows. ii) v(j) = i. Then u(j) ≠ i and there are six cases to consider.

a) u(j) > i > u(j + 1). Then u > us, (us)^{−1}(i) > (vs)^{−1}(i), D̃(us, vs) = (D̃(u, v) \ {j}) ∪ {j + 1}, so by Theorem 2.1 and our induction hypotheses we have that

R_{u,v} = R_{us,vs} = ε_{us}ε_{vs} (1 − q) ∏_{k∈D̃(us,vs)}(1 − q^{ã_{k}(us,vs)})
= ε_{u}ε_{v} (1 − q)(1 − q^{ã_{j+1}(us,vs)}) ∏_{k∈D̃(u,v)\{j}}(1 − q^{ã_{k}(u,v)}),

and the result follows since ã_{j+1}(us, vs) = ã_{j}(u, v).

b) u(j) > u(j + 1) = i.

Then u > us, (us)^{−1}(i) < (vs)^{−1}(i), D(us, vs) = D̃(u, v) ∌ j + 1, so by Theorem 2.1 and our induction hypotheses we have that

R_{u,v} = R_{us,vs} = ε_{us}ε_{vs} (1 − q) ∏_{k∈D(us,vs)}(1 − q^{a_{k}(us,vs)})
= ε_{u}ε_{v} (1 − q) ∏_{k∈D̃(u,v)}(1 − q^{ã_{k}(u,v)})

as desired.

c) i < u(j) < u(j + 1). Then u < us ∉ S_{n}^{(i)}, u^{−1}(i) > (vs)^{−1}(i), D̃(u, vs) = D̃(u, v) ∋ j + 1, so by Theorem 2.1 and our induction hypotheses we have that

R_{u,v} = −R_{u,vs} = −ε_{u}ε_{vs} (1 − q) ∏_{k∈D̃(u,vs)}(1 − q^{ã_{k}(u,vs)})
= ε_{us}ε_{v} (1 − q) (1 − q^{ã_{j+1}(u,vs)}) ∏_{k∈D̃(u,v)\{j+1}}(1 − q^{ã_{k}(u,v)}),

and the result follows since ã_{j+1}(u, vs) = ã_{j+1}(u, v).

d) u(j) < u(j + 1) < i. Then u < us ∉ S_{n}^{(i)}, u^{−1}(i) > (vs)^{−1}(i), D̃(u, vs) = D̃(u, v) ∌ j + 1, so by Theorem 2.1 and our induction hypotheses we have that

R_{u,v} = −R_{u,vs} = −ε_{u}ε_{vs} (1 − q) ∏_{k∈D̃(u,vs)}(1 − q^{ã_{k}(u,vs)})

and the result follows.

e) u(j) < u(j + 1) = i. Then u < us ∈ S_{n}^{(i)}, (us)^{−1}(i) = v^{−1}(i) < (vs)^{−1}(i) = u^{−1}(i), D(u, vs) = D̃(u, v) ∌ j + 1, D(us, vs) = D̃(u, v) ∪ {j} so by Theorem 2.1 and our induction hypotheses we have that

R_{u,v} = q R_{us,vs} + (q − 1) R_{u,vs}
= −ε_{u}ε_{vs} (1 − q) (q^{a_{j+1}(u,vs)+1} − q + 1) ∏_{k∈D(u,vs)}(1 − q^{a_{k}(u,vs)})

+q χ(us ≤ vs)ε_{us}ε_{vs} (1 − q) ∏_{k∈D(us,vs)}(1 − q^{a_{k}(us,vs)})

= ε_{u}ε_{v} (1 − q) ∏_{k∈D̃(u,v)}(1 − q^{ã_{k}(u,v)})

(q^{a_{j+1}(u,vs)+1} − q + 1 + q χ(us ≤ vs)(1 − q^{a_{j}(us,vs)})) and the result follows if us ≤ vs since a_{j}(us, vs) = a_{j+1}(u, vs). If us ≰ vs then, by (6) and Proposition 2.6, a_{j+1}(us, vs) < 0. But a_{j+1}(us, vs) = a_{j+1}(u, vs) − 1, so we conclude from Proposition 2.6 that a_{j+1}(u, vs) = 0 and the result again follows.

f) u(j) < i < u(j + 1)

Then u < us ∈ S_{n}^{(i)}, (vs)^{−1}(i) < u^{−1}(i) = (us)^{−1}(i), D̃(u, vs) = D̃(u, v) ∋ j + 1, D̃(us, vs) = (D̃(u, v) \ {j + 1}) ∪ {j}. Furthermore, ã_{j+1}(us, vs) = ã_{j+2}(u, v) so, by (6) and Proposition 2.6, us ≤ vs. Then by Theorem 2.1 and our induction hypotheses we have that

R_{u,v} = (q − 1) R_{u,vs} + q R_{us,vs}
= −ε_{u}ε_{vs} (1 − q)^{2} ∏_{k∈D̃(u,vs)}(1 − q^{ã_{k}(u,vs)})

+qε_{us}ε_{vs} (1 − q) ∏_{k∈D̃(us,vs)}(1 − q^{ã_{k}(us,vs)})

= ε_{u}ε_{v} (1 − q) ∏_{k∈D̃(u,v)\{j+1}}(1 − q^{ã_{k}(u,v)})

((1 − q) (1 − q^{ã_{j+1}(u,vs)}) + q (1 − q^{ã_{j}(us,vs)}))

and the result follows since ã_{j+1}(u, vs) = ã_{j}(us, vs) = ã_{j+1}(u, v).

This concludes the induction step and hence the proof. □

We illustrate the preceding theorem with two examples. Suppose n = 9, i = 5, u = 162578349 and v = 657819234. Then u^{−1}(5) = 4 > 2 = v^{−1}(5), D̃(u, v) = {2, 5, 9}, (ã_{2}(u, v), ã_{5}(u, v), ã_{9}(u, v)) = (1, 2, 1) so by Theorem 3.1 we have that R_{u,v}^{J_{5},q} = (1 − q)^{3}(1 − q^{2}). On the other hand, if u = 123567489 and v = 617582394 then u^{−1}(5) = 4 = v^{−1}(5), D(u, v) = {6, 9}, (a_{4}(u, v), a_{6}(u, v), a_{9}(u, v)) = (2, 2, 1) so by Theorem 3.1 R_{u,v}^{J_{5},q} = −(1 − q + q^{3})(1 − q)(1 − q^{2}).

From Proposition 2.3 we obtain the following “dual” version of Theorem 3.1.

Corollary 3.2 Let u, v ∈ S_{n}^{(i)}, u ≤ v. Then

R_{u,v}^{J_{i},−1} = \{ \begin{matrix}q^{ℓ(u,v)} (1 − q^{−1} + cq^{−a_{u^{−1}(i)}(u,v)−1}) ∏_{k∈D(u,v)}(1 − q^{−a_{k}(u,v)}), & if u^{−1}(i) ≤ v^{−1}(i), \\ q^{ℓ(u,v)} (1 − q^{−1} + cq^{−ã_{u^{−1}(i)}(u,v)−1}) ∏_{k∈D̃(u,v)}(1 − q^{−ã_{k}(u,v)}), & if u^{−1}(i) ≥ v^{−1}(i), \end{matrix}

where c =^{def} δ_{u^{−1}(i),v^{−1}(i)}. □

If the first element is the identity, only one of the integers appearing in Theorem 3.1 is sufficient to determine the corresponding polynomial.

Corollary 3.3 Let v ∈ S_{n}^{(i)}. Then

R_{e,v}^{J_{i},q} = ε_{v}(1 − q + δ_{v^{−1}(i),i} q^{k+1}) ∏_{j=1}^{k}(1 − q^{j})

and

R_{e,v}^{J_{i},−1} = q^{ℓ(v)}(1 − q^{−1} + δ_{v^{−1}(i),i} q^{−k−1}) ∏_{j=1}^{k}(1 − q^{−j}),

where k =^{def} a_{i}(e, v) if i ≤ v^{−1}(i) and k =^{def} ã_{i+1}(e, v) if i ≥ v^{−1}(i).

Proof. We have that D(e, v) = {j ≥ i : v(j) < i} and hence that |D(e, v)| = a_{i}(e, v). But, for all r ∈ D(e, v), a_{r}(e, v) = |{j ≥ r : v(j) < i}| = |D(e, v) ∩ [r, n]|, so the result follows from Theorem 3.1 if i ≤ v^{−1}(i). Similarly, D̃(e, v) = {j > i : v(j) ≤ i} so |D̃(e, v)| = ã_{i+1}(e, v). But, for all r ∈ D̃(e, v), ã_{r}(e, v) = |{j ≥ r : v(j) ≤ i}| = |D̃(e, v) ∩ [r, n]|, and the result again follows since ã_{i+1}(e, v) = ã_{i}(e, v) if i = v^{−1}(i). □

It is an open problem, in the theory of the (ordinary) R-polynomials, to know if given u, v ∈ W there exists w ∈ W such that R_{u,v}(q) = R_{e,w}(q) ([1]). The last three results (and simple examples) show that, in general, this is false for the parabolic R-polynomials of S_{n}^{(i)}.

As a further consequence of our main result we obtain combinatorial closed product formulas for certain sums and alternating sums of ordinary R-polynomials.

Corollary 3.4 Let u, v ∈ S_{n}^{(i)}, u < v, and x ∈ {−1, q}. Then

∑_{w∈(S_{n})_{J_{i}}}(−x)^{ℓ(w)}R_{wu,v} =

\{ \begin{matrix}(q − x − 1)^{ℓ(u,v)} (1 − \frac{x^{2}}{q} + c (\frac{x^{2}}{q} )^{a_{u^{−1}(i)}(u,v)+1}) ∏_{r∈D(u,v)} (1 − (\frac{x^{2}}{q} )^{a_{r}(u,v)}) , & if u^{−1}(i) ≤ v^{−1}(i), \\ (q − x − 1)^{ℓ(u,v)} (1 − \frac{x^{2}}{q} + c (\frac{x^{2}}{q} )^{ã_{u^{−1}(i)}(u,v)+1}) ∏_{r∈D̃(u,v)} (1 − (\frac{x^{2}}{q} )^{ã_{r}(u,v)}) , & if u^{−1}(i) ≥ v^{−1}(i), \end{matrix}

where c =^{def} δ_{u^{−1}(i),v^{−1}(i)}.

Proof. This follows immediately from Theorem 3.1, Corollary 3.2 and Proposition 2.2. □

We conclude by giving a geometric interpretation of our main result. Given u ∈ S_{n}^{(i)} we associate to u a Motzkin path, which we denote by M_{u}, with n − i up, i − 1 down, and 1 horizontal steps, in the following way. For 1 ≤ j ≤ n the j-th step of M_{u} is down (respectively, horizontal, up) if and only if u(j) < i (resp., = i, > i). So, for example, if n = 9, i = 5, u = 123657489 then M_{u} is the Motzkin path depicted in Figure 2. Note that, if u, v ∈ S_{n}^{(i)}, then D(u, v) (resp., D̃(u, v)) is the set of all j ∈ [n] such that the j-th step of M_{v} (resp., M_{u}) is down (resp., up) and the j-th step of M_{u} (resp., M_{v}) is not.

[figure]

Figure 2.

Proposition 3.5 Let u, v ∈ S_{n}^{(i)}. Then

⌊\frac{M_{v}(j − 1) − M_{u}(j − 1)}{2}⌋ = \{ \begin{matrix}a_{j}(u, v), & if u^{−1}(i) ≤ v^{−1}(i), \\ ã_{j}(u, v), & if u^{−1}(i) ≥ v^{−1}(i), \end{matrix}  (9)

for j ∈ [n]. In particular, u ≤ v if and only if M_{v}(j) ≥ M_{u}(j) for all j ∈ [n].

Proof. Let j ∈ [n]. Clearly, M_{v}(j − 1) equals the difference between the number of up steps and down steps among the first j − 1 steps of M_{v}. Therefore, by our definitions

M_{v}(j − 1) = |{r ∈ [j − 1] : v(r) > i}| − |{r ∈ [j − 1] : v(r) < i}|
= n − 2i + 1 − |{r ∈ [j, n] : v(r) > i}| + |{r ∈ [j, n] : v(r) < i}|)
= j − 2i + 2 + |{r ∈ [j, n] : v(r) < i}| + |{r ∈ [j, n] : v(r) ≤ i}|.

Hence, by (4), (5), and (6)

M_{v}(j − 1) − M_{u}(j − 1) = a_{j}(u, v) + ã_{j}(u, v)
= \{ \begin{matrix}2 a_{j}(u, v) + 1, & if u^{−1}(i) < j ≤ v^{−1}(i), \\ 2 ã_{j}(u, v) + 1, & if v^{−1}(i) < j ≤ u^{−1}(i), \\ ã_{j}(u, v) + a_{j}(u, v), & otherwise, \end{matrix}

and (9) follows since a_{j}(u, v) = ã_{j}(u, v) if either j ≤ u^{−1}(i), v^{−1}(i) or u^{−1}(i), v^{−1}(i) < j. The second statement follows immediately from (9), (6), and Proposition 2.6. □

We can now give the following geometric reformulation of Theorem 3.1.

[figure]

Figure 3.

Corollary 3.6 Let u, v ∈ S_{n}^{(i)}, u ≤ v. Then

R_{u,v}^{J_{i},q} = ε_{u}ε_{v} (1 − q + cq^{⌊^{\frac{Mv(v^{−1}(i)−1)−Mu(u^{−1}(i)−1)}{2}}⌋+1}) ∏_{j∈D(u,v)} (1 − q^{⌊^{\frac{Mv(j−1)−Mu(j−1)}{2}}⌋}) ,

where c =^{def} δ_{u^{−1}(i),v^{−1}(i)}, D(u, v) =^{def} D(u, v) if u^{−1}(i) ≤ v^{−1}(i) and D(u, v) =^{def} D̃(u, v)

if u^{−1}(i) ≥ v^{−1}(i).

Proof. This follows immediately from Theorem 3.1 and Proposition 3.5. □

So, for example, if n = 9, i = 5, u = 123657489 and v = 671829345 then the two Motzkin paths M_{u} and M_{v} are depicted in Figure 3, u^{−1}(5) < v^{−1}(5), D(u, v) = {5, 8}, M_{v}(4) − M_{u}(4) = 4 and M_{v}(7) − M_{u}(7) = 3 so we have from Corollary 3.6 that R_{u,v}^{J_{5},q} = −(1 − q)^{2}(1 − q^{2}).

Acknowledgments. I would like to thank John Stembridge for suggesting the tight quotients as a natural next step after the maximal quotients and for useful suggestions and conversations.

References

[1] A. Björner, private communication, March 1992.

[2] A. Björner, F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, 231, Springer-Verlag, New York, 2005.

[3] F. Brenti, Kazhdan-Lusztig and R-polynomials, Young’s lattice, and Dyck partitions, Pacific J. Math., 207 (2002), 257-286.

[4] L. Casian, D. Collingwood, The Kazhdan-Lusztig conjecture for generalized Verma modules, Math. Zeit., 195 (1987), 581-600.

[5] V. Deodhar, On some geometric aspects of Bruhat orderings. II. The parabolic analogue of Kazhdan-Lusztig polynomials, J. Algebra, 111 (1987), 483-506.

[6] V. Deodhar, Duality in parabolic setup for questions in Kazhdan-Lusztig theory, J. Algebra, 142 (1991), 201-209.

[7] J. Haglund, M. Haiman, N. Loehr, A combinatorial formula for Macdonald polynomials, J. Amer. Math. Soc., 18 (2005), 735-761.

[8] J. Haglund, M. Haiman, N. Loehr, J. Remmel, A. Ulyanov, A combinatorial formula for the character of the diagonal coinvariants, Duke Math. J., 126 (2005), 195-232.

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

[10] M. Kashiwara, T. Tanisaki, Parabolic Kazhdan-Lusztig polynomials and Schubert varieties, J. Algebra, 249 (2002), 306-325.

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

[12] B. Leclerc, J.-Y. Thibon, Littlewood-Richardson coefficients and Kazhdan-Lusztig polynomials, Adv. Studies Pure Math., 28 (2000), 155-220.

[13] W. Soergel, Kazhdan-Lusztig polynomials and a combinatoric for tilting modules, Represent. Theory, 1 (1997), 83-114.

[14] W. Soergel, Character formulas for tilting modules over Kac-Moody algebras, Represent. Theory, 1 (1997), 115-132.

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

[16] J. Stembridge,Tight quotients and double quotients in the Bruhat order, Electron. J. Combin., 11 (2005), R14, 41 pp.

[17] M. Varagnolo, E. Vasserot, On the decomposition matrices of the quantized Schur algebra, Duke Math. J., 100 (1999), 267-297.