Explicit formulae for some Kazhdan-Lusztig polynomials

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

Rodica Simion^{2} Department of Mathematics The George Washington University Washington, DC 20052, U.S.A. simion@gwu.edu

Abstract

We consider the Kazhdan-Lusztig polynomials P_{u,v}(q) indexed by permutations u, v having particular forms with regard to their monotonicity patterns. The main results are the following. First we obtain a simplified recurrence relation satisfied by P_{u,v}(q) when the maximum value of v ∈ S_{n} occurs in position n − 2 or n − 1. As a corollary we obtain the explicit expression for P_{e,3 4 ... n 1 2}(q) (where e denotes the identity permutation), as a q-analogue of the Fibonacci number. This establishes a conjecture due to M. Haiman. Second, we obtain an explicit expression for P_{e,3 4 ... (n−2) n (n−1) 1 2}(q). Our proofs rely on the recurrence relation satisfied by the Kazhdan-Lusztig polynomials when the indexing permutations are of the form under consideration, and on the fact that these classes of permutations lend themselves to the use of induction. We present several conjectures regarding the expression for P_{u,v}(q) under hypotheses similar to those of the main results.

1Part of this work was carried out while the author was a member of the Mathematical Sciences Research Institute in Berkeley, California, U.S.A., and was partially supported by NSF grant No.

DMS 9022140

2This work was carried out in part during the author’s visit at MSRI on the occasion of the Special Year Program in Combinatorics. The MSRI support is gratefully acknowledged.

Keywords: Kazhdan-Lusztig polynomial, q-Fibonacci number, Bruhat order

1 Introduction

In their seminal 1979 paper [8], D. Kazhdan and G. Lusztig introduced a family of polynomials, P_{u,v}(q), indexed by pairs of elements u, v of a Coxeter group. In the case when u and v are permutations, the polynomials have become known as the Kazhdan-Lusztig polynomials for the symmetric group. The interest in these polynomials and the broader circle of ideas of Kazhdan-Lusztig Theory to which they belong, is multifold. From the beginning of their study, the Kazhdan-Lusztig polynomials were shown to be related to Lie theory, and a significant body of literature treats their relation to the geometry of Schubert varieties, representation theory, and the (strong) Bruhat order of the symmetric group. The latter and a variety of properties of and conjectures concerning the Kazhdan-Lusztig polynomials make them interesting and challenging objects of study from the point of view of combinatorics. Developments along these lines include combinatorial derivations for the Kazhdan-Lusztig polynomials (see, e.g., the account in [7], section 7.12, [5], [1], and [4]) as well as explicit formulas for Kazhdan-Lusztig polynomials for particular classes of permutations (see, e.g., [14], [9], [10], [12]).

The present paper contributes results in the direction of explicit formulae for the Kazhdan-Lusztig polynomials of the symmetric group when the indexing permutations are of particular forms. The main results, appearing in Section 3, are as follows. First we obtain a simplified recurrence relation satisfied by P_{u,v}(q) for u, v ∈ S_{n}, when the maximum value of v occurs in position n − 2 or n − 1 (Theorem 3.1). As a corollary (Corollary 3.2), we obtain the explicit expression for P_{e,3 4 ... n 1 2}(q) (where e denotes the identity permutation), as a q-analogue of the Fibonacci number. This establishes a conjecture due to M. Haiman (see [3, Conjecture 7.18]). Second, we obtain an explicit expression for P_{e,3 4 ... (n−2) n (n−1) 1 2}(q) (Theorem 3.3). Our proofs rely on the recurrence relation satisfied by the Kazhdan-Lusztig polynomials when the indexing permutations are of the form under consideration, and on the fact that these classes of permutations lend themselves to the use of induction. Section 4 presents several conjectures regarding the expression for P_{u,v}(q) under hypotheses similar to those of the main results.

As a starting point, in the next section we fix the notation and provide the necessary preliminaries concerning the Bruhat order. We also include a subset of facts about the Kazhdan-Lusztig polynomials which are used in proving the results of this paper.

2 Definitions, 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, and R be the field of real 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|. 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 ∈ R, we denote by ⌊a⌋ the largest integer ≤ a.

Given a set T we let S(T) be the set of all bijections π : T → T. In particular, S_{n} =^{def} S([n]) is the symmetric group on n elements. We denote by e the identity of S_{n}. If T = {t_{1}, …, t_{r}}_{<} ⊆ P and σ ∈ S(T), then we write σ = σ_{1} … σ_{r} to mean that σ(t_{i}) = σ_{i}, for i = 1, …, r. If σ ∈ S_{n} then we also write σ in disjoint cycle form (see, e.g., [13], p.17) and we will usually omit the 1-cycles of σ. For example, σ = 365492187 ∈ S_{9} can be written alternatively as σ = (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). Given σ ∈ S_{n}, the descent set of σ is

D(σ) =^{def} {i ∈ [n − 1] : σ(i) > σ(i + 1)} ,

the number of descents of σ is

d(σ) = |D(σ)| ,

and the length of σ is defined by the number of inversions:

l(σ) =^{def} inv(σ) =^{def} |{(a, b) ∈ [n] × [n] : a < b, σ(a) > σ(b)}|.

For example, if σ = 615243 then D(σ) = {1, 3, 5} and l(σ) = 9.

Throughout this paper we view S_{n} as a partially ordered set ordered by the (strong) Bruhat order. Recall (see, e.g., [11], Chapter 1) that this means that σ ≤ τ if and only if there exist r ∈ N and a_{1}, b_{1}, …, a_{r}, b_{r} ∈ [n] such that (a_{r}, b_{r}) … (a_{1}, b_{1})σ = τ and l((a_{i}, b_{i}) … (a_{1}, b_{1})σ) > l((a_{i−1}, b_{i−1}) … (a_{1}, b_{1})σ) for each i = 1, …, r. For example, the Hasse diagram of the Bruhat order on S_{3} is shown in Figure 1.

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

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

The following characterization of the Bruhat order of S_{n} is due to Ehresmann [6], and will be used often in this work. We refer the reader to, e.g., [11], Chapter 1, for a proof. For σ ∈ S_{n}, and j ∈ [n], let

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

Theorem 2.1 Let σ, τ ∈ S_{n}. Then σ ≤ τ if and only if σ^{j,i} ≤ τ^{j,i} for all 1 ≤ i ≤ j ≤ 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.

The following result is fundamental in the theory of Kazhdan and Lusztig and is presented, e.g., in [7], §7.11, eq. (23). Here it will serve as the definition of the Kazhdan-Lusztig polynomials P_{u,v}(q) of S_{n}. It is interesting to note that no combinatorial proof of Theorem 2.2 is known.

Theorem 2.2 There exists a unique family of polynomials {P_{u,v}(q)}_{u,v∈S_{n}} ⊆ Z[q] such that: i) P_{u,v}(q) = 0 if u ≰ v;

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

iii) if u ≤ v and i ∈ D(v) then

P_{u,v}(q) = q^{1−c}P_{u(i,i+1),v(i,i+1)}(q)+q^{c}P_{u,v(i,i+1)}(q)− ∑_{\{z: i∈D(z)\}} q^{\frac{l(v)−l(z)}{2}} μ(z, v(i, i+1))P_{u,z}(q)

where for u, w ∈ S_{n},

μ(u, w) =^{def} \{ \begin{matrix}[q^{\frac{1}{2} (l(w)−l(u)−1)}](P_{u,w}(q)), & if u < w, \\ 0, & otherwise, \end{matrix}

c = 1 if i ∈ D(u), and c = 0 otherwise.

Two well-known simple but important consequences of Theorem 2.2 are the following (see, e.g., [7, Theorem 7.9, part (b), and Corollary 7.14]).

Proposition 2.3 Let u, v ∈ S_{n} such that u < v. Then deg(P_{u,v}(q)) ≤ \frac{1}{2}(l(v) − l(u) − 1).

Proposition 2.4 Let u, v ∈ S_{n} such that u < v. If i ∈ D(v), then

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

So, for example, P_{2 1 4 7 5 6 3, 6 1 5 7 2 4 3}(q) = P_{1 2 4 5 7 3 6, 6 1 5 7 2 4 3}(q), and

P_{u, n n−1...3 2 1}(q) = 1,  (2)

for all u ∈ S_{n}. Thus Proposition 2.4 shows that it is enough to compute Kazhdan-Lusztig polynomials P_{u,v}(q) for pairs u, v ∈ S_{n} such that D(v) ⊆ D(u) (say).

The following result is an immediate consequence of Propositions 2.3 and 2.4.

Proposition 2.5 Let z, w ∈ S_{n}, z ≤ w, be such that μ(z, w) ≠ 0 and l(w)−l(z) > 1. Then D(z) ⊇ D(w). □

The preceding proposition motivates the following definition. For w ∈ S_{n} and i ∈ [n] we let

E(w, i) =^{def} {z ∈ S_{n} : z ≤ w, D(z) ⊇ D(w) ∪ {i}, l(w) − l(z) > 1}
∪{z ∈ S_{n} : z < w, D(z) ∋ i},  (3)

where the notation z < w means that z is covered by w, that is, z < w and if z ≤ t ≤ w then z = t or t = w.

Then by Proposition 2.5 we deduce from Theorem 2.2 the following result.

Corollary 2.6 Let u, v ∈ S_{n}, u ≤ v, and i ∈ D(v). Then

P_{u,v}(q) = q^{1−c}P_{u(i,i+1),v(i,i+1)}(q)+q^{c}P_{u,v(i,i+1)}(q)− ∑_{z∈E(v(i,i+1),i)} μ(z, v(i, i+1))q^{\frac{1}{2} (l(v)−l(z))}P_{u,z}(q),

where c = 1 if i ∈ D(u), and c = 0 otherwise. □

Two other properties of the Kazhdan-Lusztig polynomials that we will use are the following.

Proposition 2.7 Let u, v ∈ S_{n}. Then

P_{u,v}(q) = P_{u^{−1},v^{−1}}(q) = P_{n+1−u(n)...n+1−u(1),n+1−v(n)...n+1−v(1)}(q).  (4)

The final result of this section will be applied repeatedly in the sequel, in a special case: if u < v are permutations in S_{n} and n occurs in the same position in both u and v, then P_{u,v}(q) = P_{u′,v′}(q), where u′, v′ are obtained from u, v, respectively, by suppressing the value n.

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]} is the identity permutation in S([i, j]) if and only if σ^{−1}(i) < σ^{−1}(i + 1) < … < σ^{−1}(j).

Theorem 2.8 Let u, v ∈ S_{n}, u ≤ v. Suppose that there exist i ∈ [n] such that u^{−1}([i]) = v^{−1}([i]). Then

P_{u,v}(q) = P_{u_{[i]},v_{[i]}}(q)P_{u_{[i+1,n]},v_{[i+1,n]}}(q) .  (5)

Proofs of the equalities in (4) and (5) appear in [1, Corollaries 4.3 and 4.4], and in [2, Theorem 4.4], respectively.

3 Main Results

Theorem 3.1 Let u, v ∈ S_{n}, u ≤ v, be such that v^{−1}(n) ∈ {n − 2, n − 1}. Then

P_{u,v}(q) = \{ \begin{matrix}q^{1−c}P_{u(i,i+1),v(i,i+1)}(q) + q^{c} P_{u,v(i,i+1)}(q) & if i + 1 ∉ D(v), \\ q^{1−c}P_{u(i,i+1),v(i,i+1)}(q) + q^{c} P_{u,v(i,i+1)}(q) − qP_{u,v(n,n−2,n−1)}(q), & if i + 1 ∈ D(v), \end{matrix}

where i =^{def} v^{−1}(n), c =^{def} 1 if i ∈ D(u), and c =^{def} 0 otherwise.

Proof. Let i = v^{−1}(n). Then i ∈ D(v) and Corollary 2.6 yields

P_{u,v}(q) = q^{1−c}P_{u(i,i+1),v(i,i+1)}(q) + q^{c}P_{u,v(i,i+1)}(q)
− ∑_{z∈E} μ(z, v(i, i + 1))q^{\frac{1}{2} (l(v)−l(z))}P_{u,z}(q),  (6)

where c = 1 if i ∈ D(u) and c = 0 otherwise, and E = E(v(i, i + 1), i) as defined in 3. In particular, z ∈ E satisfies z ≤ v(i, i + 1) and z(i) > z(i + 1).

Suppose first that i = n − 2. Then z ≤ v(n − 2, n − 1) and Theorem 2.1 imply z^{−1}(n) ∈ {n − 1, n}. Together with z(i) > z(i + 1), this forces z^{−1}(n) = n and therefore that n − 1 ∉ D(z). But n − 1 ∈ D(v(n − 2, n − 1)), so Proposition 2.5 implies that μ(z, v(n − 2, n − 1)) = 0 if l(v(n − 2, n − 1)) − l(z) > 1, and we can restrict our attention to z ∈ E such that z < v(n − 2, n − 1). Since z^{−1}(n) = n, the only candidate for z < v(n − 2, n − 1) which belongs to E is z = v(n, n − 2, n − 1). This is indeed in E if and only if n − 1 ∈ D(v). Therefore

∑_{z∈E} μ(z, v(n − 2, n − 1))q^{\frac{1}{2} (l(v)−l(z))}P_{u,z}(q) = \{ \begin{matrix}0, & if n − 1 ∉ D(v), \\ q P_{u,v(n,n−2,n−1)}(q), & if n − 1 ∈ D(v), \end{matrix}

and the desired result follows.

Suppose now that i = n − 1. As before, z ≤ v(n − 1, n) and Theorem 2.1 imply z^{−1}(n) = n, but now we have i = n − 1 ∉ D(z). Therefore E = ∅. Also, i + 1 = n ∉ D(v), by the definition of the descent set. So the result again follows. □

For n ∈ P consider the q-analogue F_{n}(q) of the Fibonacci number F_{n} defined by

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

where F_{n}(q) =^{def} 0 if n < 0 and F_{0}(q) =^{def} 1. It is an easy exercise to verify that for n ≥ 0,

F_{n}(q) = ∑_{i=0}^{⌊n/2⌋} \binom{n − i}{i}q^{i}.

Corollary 3.2 Let n ≥ 3. Then

P_{e, 3 4...n 1 2}(q) = F_{n−2}(q).

Proof. We proceed by induction on n ≥ 3, the result being easily verified for n = 3, 4. From Theorem 3.1 (the instance i = n − 2, c = 0, i + 1 ∉ D(v)) we obtain that

P_{e, 3 4...n 1 2}(q) = qP_{(n−2,n−1), 3 4...n−1 1 n 2}(q) + P_{e, 3 4...n−1 1 n 2}(q).

By applying Proposition 2.4 (in turn, with i = n−3 and i = n−1), then Theorem 2.8 (in turn, with i = n − 1, and with i = n − 2), and then the induction hypothesis, we have

P_{(n−2,n−1), 3 4...n−1 1 n 2}(q) = P_{1 2...n−4 n−1 n−3 n n−2, 3 4...n−1 1 n 2}(q)
= P_{1 2...n−3 n−2, 3 4...n−2 1 2}(q)
= F_{n−4}(q),

and similarly

P_{e, 3 4 ...n−1 1 n 2}(q) = P_{1 2...n−2 n n−1, 3 4...n−1 1 n 2}(q)
= P_{1 2...n−2 n−1, 3 4...n−1 1 2}(q)
= F_{n−3}(q)

and the result follows. □

So, for example, P_{1234567,3456712}(q) = 1 + 4q + 3q^{2}. Corollary 3.2, by Proposition 2.7, verifies a conjecture of M. Haiman ([3, Conjecture 7.18]).

It should be noted that the reasonings made to prove the last two results actually prove that

C_{34...n12} = C_{(2,3)}C_{(3,4)} ⋯ C_{(n−1,n)}C_{(1,2)}C_{(2,3)} ⋯ C_{(n−2,n−1)}

in the Hecke algebra H of S_{n}, where C_{σ} denotes the Kazhdan-Lusztig element of H corresponding to σ ∈ S_{n} ( see [7], Chap. 7, for the definitions, and further information about, these objects). This, in theory, should allow one to compute explicitly the Kazhdan-Lusztig polynomials P_{σ,34...n12} for all σ ∈ S_{n}. However, we have ben unable to carry this out because of the complicated nature of multiplication in the Hecke algebra H.

There are other pairs of permutations whose Kazhdan-Lusztig polynomials can be computed in a similar way.

Theorem 3.3 Let n ≥ 5. Then

P_{e, 3 4...n−2 n n−1 1 2}(q) = F_{n−3}(q).

Proof. By Corollary 2.6 with i = n − 2, we have

P_{e, 3 4...n−2 n n−1 1 2}(q) = qP_{(n−2,n−1), 3 4...n−2 n 1 n−1 2}(q)  (7)

+P_{e, 3 4...n−2 n 1 n−1 2}(q)

− ∑_{z∈E} q^{\frac{1}{2} (l(v)−l(z))}μ(z, 3 4 … n − 2 n 1 n − 1 2)P_{e,z}(q),

where E = E(3 4 … n−2 n 1 n−1 2, n − 2). We claim that E consists of only one permutation. To verify this claim, suppose z ∈ E. Thus, z < 3 4 … n−2 n 1 n−1 2. If l(z) < l(3 4 … n − 2 n 1 n − 1 2) − 1 then the condition on descents requires z(n − 3) > z(n − 2) > z(n − 1) > z(n). But together with Theorem 2.1, which implies z^{−1}(n) ≥ n − 3, this forces z^{−1}(n) = n − 3. Now, from Theorem 2.1 we obtain further that z^{−1}(n − 1) ≥ n − 1 which contradicts the condition on descents for z. Therefore if z ∈ E, then z < 3 4 … n − 2 n 1 n − 1 2. But then z is obtained from 3 4 … n − 2 n 1 n − 1 2 by transposing two elements and, since we need z(n − 2) > z(n − 1), we conclude that z = 3 4 … n − 2 1 n n − 1 2. Thus E is a singleton set as claimed and equation (7) can be rewritten explicitly as

P_{e, 3 4...n−2 n n−1 1 2}(q) = qP_{(n−2,n−1), 3 4...n−2 n 1 n−1 2}(q)
+P_{e, 3 4...n−2 n 1 n−1 2}(q)
−q P_{e, 3 4...n−2 1 n n−1 2}(q).  (8)

We now examine each of the terms on the right-hand-side of (8). Consider the Kazhdan-Lusztig polynomial from the first term, P_{(n−2,n−1), 3 4...n−2 n 1 n−1 2}(q), and apply to it Corollary 2.6 with i = n − 3. For simplicity of notation, let now E′: = E(3 4 … n−2 1 n n−1 2, n−3). We show that E′ = ∅. Suppose to the contrary that z ∈ E′. If l(z) < l(3 4 … n−2 1 n n−1 2)−1 then z(n−4) > … > z(n−1) > z(n) which implies that z^{−1}(n) ≤ n−4 and this, by Theorem 2.1, contradicts the fact that z ≤ 3 4 … n − 2 1 n n − 1 2. If z < 3 4 … n − 2 1 n n − 1 2 then z(n − 3) > z(n − 2) and this is again a contradiction. Therefore E′ = ∅ and Corollary 2.6 with i = n − 3 yields

P_{(n−2,n−1), 3 4...n−2 n 1 n−1 2}(q) = q P_{1...n−4 n−1 n−3 n−2 n, 3 4...n−2 1 n n−1 2}(q)
+P_{(n−2,n−1), 3 4...n−2 1 n n−1 2}(q).  (9)

Now note that by Theorem 2.2, the first term on the right-hand-side of (9) is null, since (using, e.g., Theorem 2.1) 1 … n−4 n−1 n−3 n−2 n ≰ 3 4 … n−2 1 n n−1 2. In turn, the second term on the right-hand-side of (9) can be evaluated explicitely:

P_{(n−2,n−1), 3 4...n−2 1 n n−1 2}(q) = P_{1...n−3 n n−1 n−2, 3 4...n−2 1 n n−1 2}(q)
= P_{1...n−3 n−2, 3 4...n−2 1 2}(q)
= F_{n−4}(q).  (10)

In (10), the first equality follows from Proposition 2.4 (applied with i = n − 1, and n − 2), the second one follows from Theorem 2.8 (suppressing n and n − 1), and the third from Corollary 3.2. Consequently, we have obtained that the first term on the right-hand-side of equation (8) is

q P_{(n−2,n−1), 3 4...n−2 n 1 n−1 2}(q) = qF_{n−4}(q).  (11)

Similarly, since E′ = ∅, the second term on the right-hand-side of (8) is

P_{e, 3 4...n−2 n 1 n−1 2}(q) = q P_{(n−3,n−2), 3 4...n−2 1 n n−1 2}(q)
+P_{e, 3 4...n−2 1 n n−1 2}(q).  (12)

In (12), the Kazhdan-Lusztig polynomial in the first term of the right-hand-side is

P_{(n−3,n−2), 3 4...n−2 1 n n−1 2}(q) = P_{1...n−4 n−2 n n−1 n−3, 3 4...n−2 1 n n−1 2}(q)
= P_{1...n−4 n−2 n−3, 3 4...n−2 1 2}(q),  (13)

by applying Proposition 2.4 and Theorem 2.8 (similarly to the situation in (10)). By Theorem 3.1,

P_{1...n−4 n−2 n−3, 3 4...n−2 1 2}(q) = q P_{1...n−5 n−2 n−4 n−3, 3 4...n−3 1 n−2 2}(q)
+P_{1...n−4 n−2 n−3, 3 4...n−3 1 n−2 2}(q).  (14)

Since 1 … n − 5 n − 2 n − 4 n − 3 ≰ 3 4 … n − 3 1 n − 2 2, the first term on the right-hand-side of (14) is null, and by Theorem 2.8, the second term is equal to P_{1...n−4 n−3, 3 4...n−3 1 2}(q). Also, this last polynomial is as in Corollary 3.2, so (14) becomes

P_{1...n−4 n−2 n−3, 3 4...n−2 1 2}(q) = F_{n−5}(q).  (15)

Combined with equation (13) this gives

P_{(n−3,n−2), 3 4...n−2 1 n n−1 2}(q) = F_{n−5}(q).  (16)

Finally, the second term on the right-hand-side of (12) can be computed similarly to the calculation in (10), and we obtain

P_{e, 3 4...n−2 1 n n−1 2}(q) = P_{1...n−3 n n−1 n−2, 3 4...n−2 1 n n−1 2}(q) = F_{n−4}(q).  (17)

Substituting (16) and (17) into (12) we obtain

P_{e, 3 4...n−2 n 1 n−1 2}(q) = q F_{n−5}(q) + F_{n−4}(q) = F_{n−3}(q).  (18)

Finally, the third term on the right-hand-side of (8) contains the same Kazhdan-Lusztig polynomial as in (17). By substituting (11), (18), and (17), into the initial equation (8) the proof is completed:

P_{e, 3 4...n−2 n n−1 1 2}(q) = q F_{n−4}(q) + F_{n−3}(q) − q F_{n−4}(q).□  (19)

4 Conjectures and Open Problems

In this section we collect a variety of conjectures concerning Kazhdan-Lusztig polynomials which we have obtained empirically. Although many of the permutations appearing in these conjectures are quite similar to the ones considered in this note, the resulting Kazhdan-Lusztig polynomials are rather different, and we have been unable to prove them.

Conjecture 4.1 Let i ∈ P. Then

P_{1 n−1 n−2...n−i 2 3...n−i−1 n, n−1 n n−2...n−i 1 2...n−i−1}(q) = 1 + (n − i − 2)q^{i}

for n ≥ i + 2.

Conjecture 4.2 Let n ≥ 6. Then

P_{e, n−2 n−1 n n−3...4 3 1 2}(q) = 1 + 2q^{n−4}.

Conjecture 4.3 Let n ≥ 6. Then

P_{e, n−2 n−1 n n−3...4 2 1 3}(q) = 1 + 2q^{n−5} + q^{n−4}.

The above conjectures have been verified for n ≤ 8. Note that Conjecture 4.1 generalizes both Conjectures 7.15 and 7.16 of [3].

Note added in proof: Conjecture 4.1 has been proved by P. Polo, Construction of arbitrary Kazhdan-Lusztig polynomials in symmetric groups, Representation Theory, 3 (1999), 90-104.

References

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

[2] F. Brenti, Combinatorial properties of the Kazhdan-Lusztig R-polynomials for S_{n}, Advances in Math., 126 (1997), 21-51.

[3] F. Brenti, Kazhdan-Lusztig and R-polynomials from a combinatorial point of view, Discrete Math., 193 (1998), 93-116.

[4] F. Brenti, Lattice paths and Kazhdan-Lusztig polynomials, J. Amer. Math. Soc., 11 (1998), 229-259.

[5] V.V. Deodhar, A combinatorial setting for questions in Kazhdan-Lusztig theory, Geom. Dedicata, 36 (1990), 95-119.

[6] C. Ehresmann, Sur la topologie de certains espaces homogènes, Ann. Math. 35 (1934), 396-443.

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

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

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

[10] A. Lascoux, Polynômes de Kazhdan-Lusztig pour les variétés de Schubert vexillaires, C. R. Acad. Sci. Paris, Ser. I, Math., 321 (1995), 667-670.

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

[12] B. Shapiro, M. Shapiro, A. Vainshtein, Kazhdan-Lusztig polynomials for certain varieties of incomplete flags, Discrete Math., 180 (1998), 345-355.

[13] R. P. Stanley, Enumerative Combinatorics , vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986; second printing, Cambridge University Press, Cambridge/New York, 1997.

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