Lattice paths and Kazhdan-Lusztig polynomials ^{1}

Francesco Brenti^{2}

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., [17], Chap. 7). These polynomials are intimately related to the Bruhat order of W and to the geometry of Schubert varieties, and have proven to be of fundamental importance in representation theory.

The purpose of this paper is to present a new non-recursive combinatorial formula for these polynomials. More precisely, we show that each directed path in the Bruhat graph of W has a naturally associated set of lattice paths with the property that the Kazhdan-Lusztig polynomial of u, v is the sum, over all the lattice paths associated to all the paths going from u to v, of (−1)^{Γ_{≥0}+d_{+}(Γ)}q^{(l(v)−l(u)+Γ(l(Γ)))/2} where Γ_{≥0}, d_{+}(Γ), and Γ(l(Γ)) are three natural statistics on the lattice path. We believe that this formula is the most explicit non-recursive formula known for the Kazhdan-Lusztig polynomials which holds in complete generality.

The organization of the paper is as follows. In section 3 we define and study the R-polynomial of a chain. This polynomial reduces to the usual R-polynomial for a chain of length one and is fundamental in all that follows. In section 4 we show that the antisymmetrization of the Kazhdan-Lusztig polynomial of two elements u, v of W equals the alternating sum, over all the chains going from u to v, of the corresponding Rpolynomials. In section 5 we derive some consequences of this result which, although not needed in what follows, are of independent interest. More precisely, we derive explicit formulas for each coefficient of any Kazhdan-Lusztig polynomial, and comparing these to known formulas we obtain some new identities for the R-polynomials. In section 6 we introduce and study a family of polynomials, indexed by sequences of positive integers, which is needed in the proof of our main result. These polynomials are independent of W, are easily computable by simple recursions, and can be interpreted as counting certain lattice paths. In section 7 we prove our main theorem, which is obtained by combining the results in sections 4 and 6. This expresses the Kazhdan-Lusztig polynomial of two elements u, v in W as the sum, over a certain multiset of lattice paths, of (−1)^{Γ_{≥0}+d_{+}(Γ)} q^{\frac{l(v)−l(u)+Γ(l(Γ))}{2}} where Γ_{≥0}, d_{+}(Γ), and Γ(l(Γ)) are three simple statistics on the lattice path Γ. In section 8, as an application of our main result, we obtain a generalization of Theorem 6.3 of [6] and a connection between the Kazhdan-Lusztig polynomials and the Bayer-Billera relations arising in the theory of Eulerian posets and convex polytopes. Finally, in section 9, we briefly sketch how one can obtain analogues of the results in this work for the inverse Kazhdan-Lusztig polynomials.

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

2Part 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 and EC grant No. CHRX-CT93-0400.

Some of the results of this paper and [6] can be extended with little or no change in argument to more general classes of kernels (in the sense of [23]) in place of the Kazhdan-Lusztig kernel R. For instance, Theorems 4.1 and 4.2 (and also Theorem 4.1 of [6]) extend easily to arbitrary kernels.

2 Notation, definitions, and preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of this work. We let P =^{def} {1, 2, 3, …} , N=^{def}P ∪{0}, Z be the ring of integers, Q be the field of rational numbers, 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], and we define similarly (n, m], (n, m), and [n, m). Given A ⊆ P we may clearly write, in a unique way, A = ⨄_{i=1}^{s}[α_{i}, ω_{i}] so that α_{i} ≤ ω_{i} ≤ α_{i+1} − 2 for i = 1, …, s (where α_{s+1} =^{def} ω_{s} + 2), we then call [α_{1}, ω_{1}], …, [α_{s}, ω_{s}] the connected components of A. For S ⊆ Q we write S = {a_{1}, …, a_{r}}_{<} to mean that S = {a_{1}, …, a_{r}} and a_{1} < … < a_{r}. The cardinality of a set A will be denoted by |A|, for r ∈ N we let (\begin{matrix}A \\ r \end{matrix}) =^{def} \{S ⊆ A : |S| = r\}. For S ⊆ P and j ∈ P we let S_{j} be the j-th smallest element of S, (so S = {S_{1}, …, S_{|S|}}_{<}). Given a polynomial P (q), and i ∈ Z, we denote by [q^{i}](P (q)) the coefficient of q^{i} in P (q). For a ∈ Q we let ⌊a⌋ (respectively, ⌈a⌉) denote the largest integer ≤ a (respectively, smallest integer ≥ a). Given n ∈ P we let S_{n} be the set of all bijections π : [n] → [n]. If σ ∈ S_{n} then we write σ = σ_{1} … σ_{n} to mean that σ(i) = σ_{i}, for i = 1, …, n.

A polynomial ∑_{i=0}^{d} a_{i}x^{i} ∈ R[x] is called log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for i = 1, …, d−1. It is said to be unimodal if there exists an index 0 ≤ j ≤ d such that a_{i} ≤ a_{i+1} for i = 0, …, j − 1 and a_{i} ≥ a_{i+1} for i = j, …, d − 1. It is said to have no internal zeros if there are not three indices 0 ≤ i < j < k ≤ d such that a_{i}, a_{k} ≠ 0 and a_{j} = 0. It is well known that the product of two polynomials with real nonnegative coefficients which are log-concave and have no internal zeros has again these properties (see, e.g., [22], Proposition 2, p. 503).

Recall that a composition (respectively, weak composition) of n (n ∈ P) is a sequence (α_{1}, …, α_{s}) (for some s ∈ P) of positive (respectively, nonnegative) integers such that α_{1} + … + α_{s} = n (see, e.g., [20], p. 14). When writing compositions we will sometimes omit to write the parentheses (i.e., we will write α_{1}, …, α_{s} instead of (α_{1}, …, α_{s})). Thus if α = (α_{1}, …, α_{s}) and β = (β_{1}, …, β_{t}) are compositions then α, β is to be interpreted as the composition (α_{1}, …, α_{s}, β_{1}, …, β_{t}). For n ∈ P we let C_{n} be the set of all compositions of n and C =^{def} ⋃_{n≥1} C_{n}. Given β ∈ C we denote by l(β) the number of parts of β, by β_{i}, for i = 1, …, l(β), the i-th part of β (so that β = (β_{1}, β_{2}, …, β_{l(β)})), and we let

|β| =^{def} ∑_{i=1}^{l(β)} β_{i}, \overline{β} =^{def} (β_{2}, β_{3}, …, β_{l(β)}) (if l(β) ≥ 2), β^{(1)} =^{def} (β_{1} − 1, β_{2}, …, β_{l(β)}) (where

β^{(1)} =^{def} \overline{β} if β_{1} = 1), β^{∗} =^{def} (β_{l(β)}, …, β_{2}, β_{1}), T (β) =^{def} \{β_{r}, β_{r} + β_{r−1}, …, β_{r} + … + β_{2}\}

where r =^{def} l(β), and β̃ be the complementary composition of β (i.e., the unique β̃ ∈ C such that |β̃| = |β| and T (β̃) = [|β| − 1] \ T (β)). Given (α_{1}, ..., α_{s}), (β_{1}, ..., β_{t}) ∈ C_{n} we say that (α_{1}, ..., α_{s}) refines (β_{1}, ..., β_{t}) if there exist 1 ≤ i_{1} < i_{2} < … < i_{t−1} ≤ s such that ∑_{j=i_{k−1}+1}^{i_{k}} α_{j} = β_{k} for k = 1, …, t (where i_{0} =^{def} 0 , i_{t} =^{def} s). We then write (α_{1}, ..., α_{s}) ⪯ (β_{1}, ..., β_{t}). It is well known, and easy to see, that the map α ↦ T (α) is an isomorphism from (C_{n}, ⪯) to the Boolean algebra B_{n−1} of subsets of [n − 1], ordered by reverse inclusion (see, e.g., [20], p.14).

For j ∈ Q we define operators U_{j}, D_{j} : R[x] → R[x] by letting

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

D_{j} (∑_{i≥0} a_{i}q^{i}) =^{def} ∑_{i=0}^{j} a_{i}q^{i}.

Note that U_{j} and D_{j} are linear and idempotent, and that D_{j} = D_{⌊j⌋} and U_{j} = U_{⌈j⌉}, for all j ∈ Q.

We follow [20], Chap. 3, for notation and terminology concerning partially ordered sets. In particular, given a finite graded poset P and S ⊆ N we let P_{S} =^{def} {x ∈ P : ρ(x) ∈ S}, where ρ : P → N is the rank function of P, α(P; S) be the number of maximal chains of P_{S}, and

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

We also let P_{i} =^{def} P_{{i}} if i ∈ N. We say that a finite graded poset P as above is Eulerian if P has a ˆ0 and ˆ1 and μ(x, y) = (−1)^{ρ(y)−ρ(x)} for all x, y ∈ P, x ≤ y. Recall (see, e.g., [20], §3.14, p. 138, or [21], §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 then

g(P; q) =^{def} D\frac{n}{2} ((1 − q)f(P; q));  (2)

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

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

The polynomials f(P; q) and g(P; q) were introduced in [21] and are two very subtle invariants of the Eulerian poset P (see [20], §3.14, and [21], §§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.

Let a, b ∈ Z, a ≤ b. By a lattice path on [a, b] we mean a function Γ : [a, b] → Z such that Γ(a) = 0 and

|Γ(i + 1) − Γ(i)| = 1

for all i ∈ [a, b − 1]. Given such a lattice path Γ we let

N(Γ) =^{def} {i ∈ [a + 1, b − 1] : Γ(i) < 0},

d_{+}(Γ) =^{def} |{i ∈ [a, b − 1] : Γ(i + 1) − Γ(i) = 1}|,

l(Γ) =^{def} b − a, and Γ_{≥0} =^{def} l(Γ) − 1 − |N(Γ)|. We call N(Γ) the negative set of Γ, and l(Γ) the length of Γ. Note that b ∉ N(Γ) and that

d_{+}(Γ) = \frac{Γ(b) + b − a}{2}.  (4)

For example, if Γ is the lattice path illustrated in Figure 1 then N(Γ) = {3, 4, 5}, d_{+}(Γ) = 2, l(Γ) = 6, and Γ_{≥0} = 2. For n ∈ P we denote by D(n) the set of all the lattice paths on [0, n].

[figure]

Figure 1.

We follow [17] 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 ε_{σ} =^{def} (−1)^{l(σ)}. We denote by e the identity of W, and we let T =^{def} {σsσ^{−1} : σ ∈ W, s ∈ S} be the set of reflections of W. We will always assume that W is partially ordered by Bruhat order. Recall (see, e.g., [17], §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 2. Given u, v ∈ W we let [u, v] =^{def} {x ∈ W : u ≤ x ≤ v}. We consider [u, v] as a poset with the partial ordering induced by W. In particular, we will often use notation such as [u, v]_{S} or [u, v]_{i} (S ⊆ N, i ∈ N) to denote the rank-selected subposets of [u, v]. It is well known (see, e.g., [5], Corollary 1) that intervals of W (and their duals) are Eulerian posets.

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

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

Recall (see [17], §8.6, or [13]) that the Bruhat graph of a Coxeter system (W, S) is the directed graph B(W, S) obtained by taking W as vertex set and putting a directed edge from x to y if and only if yx^{−1} ∈ T and l(x) < l(y). For example, the Bruhat graph of S_{3} is depicted in Figure 3. It follows immediately from the definitions that B(W, S) contains the Hasse diagram of the Bruhat order of W (considered as a directed graph in the obvious way) as a directed subgraph.

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

Figure 3: The Bruhat graph of S_{3}.

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

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

Proposition 2.1 Let v ∈ W. Then

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

where R_{u,v}(q) ∈ Z[q].

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

Theorem 2.2 Let u, v ∈ W and s ∈ S be such that l(vs) < l(v). Then

R_{u,v}(q) = \{ \begin{matrix}R_{us,vs}(q), & if l(us) < l(u), \\ qR_{us,vs}(q) + (q − 1)R_{u,vs}, & if l(us) > l(u). \end{matrix}  (6)

Note that the preceding theorem can be used to inductively compute the R-polynomials. Theorem 2.2 has also the following simple but important consequence.

Proposition 2.3 Let u, v ∈ W. Then there exists a (necessarily unique) polynomial R̃_{u,v}(q) ∈ N[q] such that

R_{u,v}(q) = q^{\frac{1}{2} (l(v)−l(u))} R̃_{u,v} (q^{\frac{1}{2}} − q^{− \frac{1}{2}} ) .  (7)

Combinatorial interpretations of the coefficients of R̃_{u,v}(q) have been given by V. Deodhar (see [11], Theorem 1.3) and by M. Dyer (see [12], and [14]). In particular, Dyer’s interpretation implies the following result (we refer the reader to [14], §§2, 3, for its proof, see also [13], §(3.5)).

Proposition 2.4 Let u, v ∈ W, and k ∈ N. Then [q^{k}](R̃_{u,v}(q)) ≠ 0 if and only if there is a directed path in B(W, S) from u to v of length k.

There is one more property of the R-polynomials that we will use quite often in this work. We recall it here for the reader’s convenience.

Proposition 2.5 Let u, v ∈ W. Then

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

A proof of the preceding result can be found, e.g., in [17], §7.8.

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

b <_{T} bab <_{T} babab <_{T} … <_{T} ababa <_{T} aba <_{T} a where {a, b} =^{def} S′. The existence of

reflection orderings (and many of their properties) is proved in [14], §2. Throughout this work we will always assume that we have fixed (once and for all) a reflection ordering <_{T} of T. Given a path Δ = (a_{0}, a_{1}, …, a_{r}) in the Bruhat graph of W we define its length to be l(Δ) =^{def} r, its descent set, with respect to <_{T}, to be

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

and its descent composition to be the unique composition D(Δ) ∈ C such that |D(Δ)| = l(Δ) and

T (D(Δ)^{∗}) = D(Δ).

Given u, v ∈ W, and k ∈ N, we denote by B_{k}(u, v) the set of all directed paths in B(W, S) from u to v of length k, and we let B(u, v) =^{def} ⋃_{k≥0} B_{k}(u, v). For u, v ∈ W, and α ∈ C, we let

c_{α}(u, v) =^{def} |{Δ ∈ B_{|α|}(u, v) : D(Δ) ⪰ α}|,  (9)

and

b_{α}(u, v) =^{def} |{Δ ∈ B_{|α|}(u, v) : D(Δ) = α}|.  (10)

Note that these definitions imply that

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

for all u, v ∈ W and α ∈ C_{n} (n ∈ P). The following result appears in [7], Proposition 4.4.

Proposition 2.6 Let u, v ∈ W, u ≤ v, and α ∈ C. Then

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

where C_{r}(u, v) denotes the set of all chains of length r from u to v, and r =^{def} l(α).

The R-polynomials can be used to define the Kazhdan-Lusztig polynomials. The following result is not hard to prove (and, in fact, holds in much greater generality, see [23], Corollary 6.7 and Example 6.9) and a proof can be found, e.g., in [17], §§7.9-11, or [18], §2.2.

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

i) P_{u,v}(q) = 0 if u ≰ v;

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

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

iv)

q^{l(v)−l(u)} P_{u,v} (\frac{1}{q}) = ∑_{u≤z≤v} R_{u,z}(q) P_{z,v}(q) ,  (12)
if u ≤ v.

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

Throughout this work (unless otherwise explicitly stated) (W, S) denotes a fixed (but arbitrary) Coxeter system.

3 The R-polynomial of a chain

In this section we define and study the R-polynomial of a chain. This polynomial reduces to the usual R-polynomial for chains of length one, and is fundamental in all that follows.

Given a chain a_{0} < a_{1} < … < a_{i} in W we define

R_{a_{0},...,a_{i}}(q) =^{def} R_{a_{0},a_{1}}(q)D_{\frac{d−1}{2}} (R_{a_{1},...,a_{i}}(q))  (13)

(where d =^{def} l(a_{i}) − l(a_{1})) if i ≥ 2, and

R_{a_{0},...,a_{i}}(q) =^{def} R_{a_{0},a_{1}}(q)  (14)

if i = 1. For example, in W = S_{4} we have that

R_{2134,2431,4321}(q) = R_{2134,2431}(q) D_{\frac{2−1}{2}} (R_{2431,4321}(q))
= (q^{3} − 2q^{2} + 2q − 1) D_{\frac{1}{2}} ((q − 1)^{2})
= q^{3} − 2q^{2} + 2q − 1,

and hence

R_{1234,2134,2431,4321}(q) = R_{1234,2134}(q) D_{\frac{5−1}{2}} (R_{2134,2431,4321}(q))
= (q − 1) D_{2}(q^{3} − 2q^{2} + 2q − 1)
= −2q^{3} + 4q^{2} − 3q + 1.

The next result is a straightforward consequence of our definitions, but nonetheless deserves to be mentioned.

Proposition 3.1 Let a_{0} < a_{1} < … < a_{i} be a chain in W. Then:

i) deg(R_{a_{0},a_{1},...,a_{i}}) ≤ max (0, ⌊\frac{l(a_{i})−l(a_{1})−1}{2}⌋) + l(a_{1}) − l(a_{0});

ii) R_{a_{0},a_{1},...,a_{i}}(0) = ε_{a_{0}}ε_{a_{i}}.

Proof. i) is immediate from (13). ii) follows immediately from (13) and (14) by induction on i ∈ P, noting that d ≥ 1 in (13). □ We conjecture that equality always holds in part i) of the above proposition.

We now derive several formulas for the coefficients of the R-polynomial of a chain in terms of coefficients of ordinary R-polynomials.

Proposition 3.2 Let k ∈ Z and a_{0} < a_{1} < … < a_{i} be a chain in W. Then

[q^{k}](R_{a_{0},...,a_{i}}) = ∑_{α} ∏_{r=1}^{i}[q^{α_{r}}](R_{a_{r−1},a_{r}})  (15)

where α = (α_{1}, …, α_{i}) ∈ N^{i} runs over all weak compositions of k into i parts such that α_{r} ≤ ρ(a_{r−1})−ρ(a_{r}) for r = 1, …, i, and α_{r+1}+…+α_{i} ≤ \frac{1}{2}(ρ(a_{r})−1) for r = 1, …, i−1, and ρ : [a_{0}, a_{i}] → N is the rank function of [a_{0}, a_{i}]^{∗}.

Proof. The result is clear if i = 1 so we may assume that i ≥ 2. We prove first that

[q^{k}](R_{a_{0},...,a_{i}}) = ∑_{j_{1}=0}^{⌊ \frac{ρ(a_{1})−1}{2} ⌋} … ∑_{j_{i−1}=0}^{⌊ \frac{ρ(a_{i−1})−1}{2} ⌋} ∏_{r=1}^{i}[q^{j_{r−1}−j_{r}}](R_{a_{r−1},a_{r}})  (16)

where j_{0} =^{def} k, and j_{i} =^{def} 0. In fact, from (13) we conclude that

[q^{k}](R_{a_{0},...,a_{i}}) = ∑_{j=0}^{⌊ \frac{d−1}{2} ⌋}[q^{k−j}](R_{a_{0},a_{1}})[q^{j}](R_{a_{1},...,a_{i}})  (17)

where d = l(a_{i}) − l(a_{1}). We now prove (16) by induction on i ≥ 2. If i = 2 then (16) reduces to (17). If i ≥ 3 then from (17) and our induction hypothesis we conclude that

[q^{k}](R_{a_{0},...,a_{i}}) = ∑_{j=0}^{⌊ \frac{ρ(a_{1})−1}{2} ⌋}[q^{k−j}](R_{a_{0},a_{1}}) ∑_{j_{2}=0}^{⌊ \frac{ρ(a_{2})−1}{2} ⌋} … ∑_{j_{i−1}=0}^{⌊ \frac{ρ(a_{i−1})−1}{2} ⌋} ∏_{r=2}^{i}[q^{j_{r−1}−j_{r}}](R_{a_{r−1},a_{r}})

where j_{1} =^{def} j, and (16) follows. Now note that

∏_{r=1}^{i}[q^{j_{r−1}−j_{r}}](R_{a_{r−1},a_{r}}) ≠ 0

only if 0 ≤ j_{r−1} − j_{r} ≤ l(a_{r}) − l(a_{r−1}) for r = 1, … i. Furthermore, given (j_{1}, …, j_{i−1}) ∈ N^{i−1} such that k ≥ j_{1} ≥ j_{2} ≥ … ≥ j_{i−1} ≥ 0, j_{r} ≤ \frac{1}{2}(ρ(a_{r}) − 1) for r = 1, …, i − 1, and j_{r−1} − j_{r} ≤ l(a_{r}) − l(a_{r−1}) for r = 1, …, i then (k − j_{1}, j_{1} − j_{2}, …, j_{i−2} − j_{i−1}, j_{i−1}) is a weak composition of k into i parts satisfying the conditions of the proposition, and this is a bijection. □ Note that Proposition 3.2 implies Proposition 3.1.

Using the fact that [q^{0}](R_{x,y}) = ε_{x}ε_{y} for all x, y ∈ W, x ≤ y, we can obtain the following more compact (though less elegant) formulation of the preceding proposition.

Proposition 3.3 Let a_{0} < a_{1} < … < a_{i} be a chain in W, and k ∈ Z \ {0}. Then

[q^{k}](R_{a_{0},...,a_{i}}) = ε_{a_{0}}ε_{a_{i}} ∑_{α∈C_{k}} ∑_{S} ∏_{j=1}^{l(α)} ε_{a_{S_{j} −1}}ε_{a_{S_{j}}} [q^{α_{j}}](R_{a_{S_{j} −1},a_{S_{j}}})

where S = \{S_{1}, …, S_{l}\}_{<} runs over all subsets of [i] of size l(α) such that \frac{1}{2}(ρ(a_{S_{j}−1})−1) ≥ α_{j} + … + α_{l} for j = 2, …, l, and \frac{1}{2}(ρ(a_{S_{1}−1}) − 1) ≥ k if S_{1} > 1.

Proof. If α ∈ N^{i} is a weak composition of k into i parts then α = (0, …, 0, α_{s_{1}}, 0, …, 0, α_{s_{2}}, 0, …, 0, α_{s_{l}}, 0, …, 0) for some (unique) l, s_{1}, …, s_{l} such that α_{s_{1}}, …, α_{s_{l}} > 0, 1 ≤ s_{1} < s_{2} < … < s_{l} ≤ i and l ∈ [i], and this is a bijection between the weak compositions of k into i parts and pairs (β, S) where β ∈ C_{k}, and S ∈ \binom{[i]}{l(β)}. Furthermore, if α and (β, \{S_{1}, …, S_{l}\}_{<}) correspond under this bijection then α_{r+1} + … + α_{i} ≤ \frac{1}{2}(ρ(a_{r}) − 1) for r = 1, …, i − 1 if and only if β_{j} + … + β_{l} ≤ \frac{1}{2}(ρ(a_{S_{j}−1}) − 1) for j = 2, …, l and β_{1} + … + β_{l} ≤ \frac{1}{2}(ρ(a_{S_{1}−1}) − 1) if S_{1} > 1. Since [q^{α_{r}}](R_{a_{r−1},a_{r}}) = 0 if α_{r} > ρ(a_{r−1}) − ρ(a_{r}) and [q^{α_{r}}](R_{a_{r−1},a_{r}}) = ε_{a_{r−1}}ε_{a_{r}} if α_{r} = 0 the thesis follows from Proposition 3.2. □

Note that if k ≤ \frac{1}{2}(l(a_{i}) − l(a_{0}) − 1) then the conditions on the subset S in Proposition 3.3 may be stated simply as “\frac{1}{2}(ρ(a_{S_{j}−1}) − 1) ≥ α_{j} + … + α_{l} for j = 1, …, l”.

Using Proposition 2.5 we can obtain the following “dual” expression for the coefficient of q^{k} of the R-polynomial of a chain. This formulation is simpler than the one in Proposition 3.2 if k > \frac{1}{2}(l(a_{i}) − l(a_{0})) and will be used in section 5.

Proposition 3.4 Let a_{0} < a_{1} < … < a_{i} be a chain in W and k ∈ Z. Then

[q^{k}](R_{a_{0},...,a_{i}}) = ∑_{α} ∏_{r=1}^{i}[q^{α_{r}}](R_{a_{r−1},a_{r}})ε_{a_{r−1}}ε_{a_{r}}  (18)

where α = (α_{1}, …, α_{i}) ∈ N^{i} runs over all weak compositions of ρ(a_{0}) − k into i parts such that α_{r} ≤ ρ(a_{r−1}) − ρ(a_{r}) for r = 1, …, i, and α_{r+1} + … + α_{i} ≥ \frac{1}{2}(ρ(a_{r}) + 1) for r = 1, …, i − 1, and ρ has the same meaning as in Proposition 3.2.

Proof. Let α = (α_{1}, …, α_{i}) ∈ N^{i} be a weak composition satisfying the conditions in the proposition. Then β =^{def} (ρ(a_{0}) − ρ(a_{1}) − α_{1}, …, ρ(a_{i−1}) − ρ(a_{i}) − α_{i}) ∈ N^{i} is a weak composition of k into i parts such that β_{r} ≤ ρ(a_{r−1}) − ρ(a_{r}) for r = 1, …, i and β_{r+1} + … + β_{i} = ρ(a_{r}) − ρ(a_{i}) − (α_{r+1} + … + α_{i}) ≤ ρ(a_{r}) − ρ(a_{i}) − \frac{1}{2}(ρ(a_{r}) + 1) = \frac{1}{2}(ρ(a_{r}) − 1) for r = 1, …, i − 1. It is clear that this correspondence is a bijection between the summation sets in the right hand sides of (18) and (15). Furthermore, if α and β correspond under this bijection then

∏_{r=1}^{i}[q^{α_{r}}](R_{a_{r−1},a_{r}})ε_{a_{r−1}}ε_{a_{r}} = ∏_{r=1}^{i}[q^{β_{r}}](R_{a_{r−1},a_{r}}),

by (8), and the result follows from Proposition 3.2. □

In the same way that Proposition 3.3 follows from Proposition 3.2 one can deduce from Proposition 3.4 the following result.

Proposition 3.5 Let a_{0} < a_{1} < … < a_{i} be a chain in W and k ∈ Z \ {0}. Then

[q^{ρ(a_{0})−k}](R_{a_{0},...,a_{i}}) = ∑_{α∈C_{k}} ∑_{S} ∏_{j=1}^{l(α)}[q^{α_{j}}](R_{a_{S_{j} −1},a_{S_{j}}})ε_{a_{S_{j} −1}}ε_{a_{S_{j}}} ,

where S = {S_{1}, …, S_{l}}_{<} runs over all subsets of [i] of size l(α) such that i ∈ S, α_{j+1} + … + α_{l} ≥ \frac{1}{2}(ρ(a_{S_{j}}) + 1) for j = 1, …, l − 1, and S_{1} = 1 if k < \frac{1}{2}(ρ(a_{1}) + 1).

Proof. The result is clear if i = 1 by (8), so we may assume that i ≥ 2. Note first that if α ∈ N^{i} appears in the sum on the RHS of (18) then necessarily α_{i} > 0 (since α_{i} ≥ \frac{1}{2}(ρ(a_{i−1}) + 1) ≥ 1). Now reasoning as in the proof of Proposition 3.3 we see that there is a bijection between weak compositions α ∈ N^{i} of k into i parts such that α_{i} > 0 and pairs (β, S) where β ∈ C_{k}, S ∈ \binom{[i]}{l(β)}, and i ∈ S. Furthermore, if α and (β, \{S_{1}, …, S_{l}\}_{<}) correspond under this bijection then α_{r+1} + … + α_{i} ≥ \frac{1}{2}(ρ(a_{r}) + 1) for r = 1, …, i − 1 if and only if β_{j+1} + … + β_{l} ≥ \frac{1}{2}(ρ(a_{S_{j}}) + 1) for j = 1, …, l − 1, and β_{1} + … + β_{l} ≥ \frac{1}{2}(ρ(a_{1}) + 1) if S_{1} > 1. Since [q^{α_{r}}](R_{a_{r−1},a_{r}}) = 0 if α_{r} > ρ(a_{r−1}) − ρ(a_{r}) and [q^{α_{r}}](R_{a_{r−1},a_{r}}) = ε_{a_{r−1}}ε_{a_{r}} if α_{r} = 0 the thesis follows from Proposition 3.4. □ Note that the preceding proposition also holds for k = 0 as long as i ≥ 2.

Given the similarity of the definition of the R-polynomial of a chain with that of the R-polynomial of a multichain given in §3 of [6] it is natural to ask whether there are any connections between the two concepts. Indeed, it follows easily from Proposition 3.7 of [6] and from Proposition 3.5 that if a_{0} < a_{1} < … < a_{i} (i ≥ 2) is a chain in W then

[q^{k}](R_{a_{0},...,a_{i}}) = (−1)^{k}[q^{l(a_{i})−l(a_{0})−k}](R_{a_{0},...,a_{i}})  (19)

for k = 0, 1. However, (19) fails for k ≥ 2. For example, if C is the chain 1234 < 3142 < 3421 < 4321 in S_{4} then R_{C}(q) = −q^{5} + 3q^{4} − 3q^{3} + q^{2} but R_{C}(q) = 1 − 5q + 9q^{2} − 7q^{3} + 2q^{4}. Also, it is not hard to verify that

ε_{a_{1}}ε_{a_{2}}R_{a_{0},a_{1},a_{2}}(q) = q^{l(a_{2})−l(a_{0})}R_{a_{0},a_{1},a_{2}} (\frac{1}{q})

for any chain a_{0} < a_{1} < a_{2} in W. However, in general, the R-polynomial of a chain does not determine its R-polynomial as a multichain, and conversely. For example, R_{123,213,321}(q) = R_{123,213,312,321}(q) but R_{123,213,321}(q) ≠ R_{123,213,312,321}(q), while R_{1234,2134,3412,3421}(q) = R_{1234,2134,2431,3421}(q) but R_{1234,2134,3412,3421}(q) ≠ R_{1234,2134,2431,3421}(q).

4 A non-recursive formula

In this section we prove a non-recursive formula for the Kazhdan-Lusztig polynomial of any two elements of any Coxeter group, which is needed in the proof of our main result. This formula is analogous to, but different from, the one obtained in Theorem 4.1 of [6]. In fact, comparison of the two formulas yields some interesting new identities, as will be shown in section 5.

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

P_{u,v}(q) = D_{⌊ \frac{l(v)−l(u)−1}{2} ⌋} ( ∑_{C∈C(u,v)}(−1)^{l(C)}R_{C}(q))

where C(u, v) is the set of all chains from u to v.

Proof. We prove the result by induction on l(v) − l(u). If l(v) − l(u) = 1 then

D_{⌊ \frac{l(v)−l(u)−1}{2} ⌋} ( ∑_{C∈C(u,v)}(−1)^{l(C)}R_{C}(q)) = D_{0}(−R_{u,v}(q)) = D_{0}(−(q − 1)) = 1 = P_{u,v}(q).

Now let u < v be such that l(v) − l(u) ≥ 2. Then from Theorem 2.7, our definitions (13) and (14), and our induction hypothesis, we have that

q^{l(v)−l(u)}P_{u,v} (\frac{1}{q}) − P_{u,v}(q) = R_{u,v}(q) + ∑_{u<a<v} R_{u,a}(q)D_{⌊ \frac{l(v)−l(a)−1}{2} ⌋} ( ∑_{C∈C(a,v)}(−1)^{l(C)}R_{C}(q))
= R_{u,v}(q) + ∑_{u<a<v} ∑_{C∈C(a,v)}(−1)^{l(C)}R_{u,a}(q)D_{⌊ \frac{l(v)−l(a)−1}{2} ⌋}(R_{C}(q))
= R_{u,v}(q) + ∑_{u<a<v} ∑_{C∈C(a,v)}(−1)^{l(C)}R_{u,C}(q)
= R_{u,v}(q) + ∑_{{C′∈C(u,v): l(C′)≥2}}(−1)^{l(C′)−1}R_{C′}(q)
= − ∑_{C′∈C(u,v)}(−1)^{l(C′)}R_{C′}(q).  (20)

But from part iii) of Theorem 2.7 we deduce that

D⌊_{\frac{l(v)−l(u)−1}{2}}⌋ (q^{l(v)−l(u)}P_{u,v} (\frac{1}{q}) − P_{u,v}(q)) = −P_{u,v}(q)

and the thesis follows from (20). □ Note that Corollaries 4.3 and 4.4 of [6] also follow from Theorem 4.1, with proofs analogous to those in [6].

The preceding result makes it natural to ask what is the polynomial ∑_{C∈C(u,v)}(−1)^{l(C)} R_{C}(q). The answer is already contained in the previous theorem and its proof, which imply the following.

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

P_{u,v}(q) − q^{l(v)−l(u)}P_{u,v} (\frac{1}{q}) = ∑_{C∈C(u,v)}(−1)^{l(C)}R_{C}(q).  (21)

In particular, the polynomial ∑_{C∈C(u,v)}(−1)^{l(C)}R_{C}(q) is antisymmetric with respect to l(v)− l(u). □

Note that it is not true that the polynomial ∑_{C∈C_{k}(u,v)}(−1)^{l(C)}R_{C}(q), where C_{k}(u, v) is the set of all chains from u to v of length k, is antisymmetric with respect to l(v) − l(u) (take, e.g., u = 123, v = 321, and k = 2 in W = S_{3}). In fact, the antisymmetry of the polynomial ∑_{C∈C(u,v)}(−1)^{l(C)}R_{C}(q) has some interesting and non-trivial consequences, as will be shown in the next section.

5 Coefficients of Kazhdan-Lusztig polynomials

In this section we derive some consequences of Theorem 4.2. More precisely, we prove two formulas for the coefficients of any Kazhdan-Lusztig polynomial in terms of coefficients of R-polynomials. These two formulas are different, and they also differ from the one given in Theorem 5.2 of [6]. The results in this section are not needed in the rest of this work.

The first formula is obtained by combining Proposition 3.3 and Theorem 4.2.

Theorem 5.1 Let u, v ∈ W, u ≤ v, and k ∈ P. Then

[q^{k}](P_{u,v}) = ∑_{α∈C_{k}}(−1)^{l(α)} ∑_{(a_{0},...,a_{2l+1})∈M_{α}(u,v)} ∏_{i=1}^{l(α)}[q^{α_{i}}](R_{a_{2i−1},a_{2i}})

where M_{α}(u, v) is the set of all multichains u = a_{0} ≤ a_{1} ≤ … ≤ a_{2l} ≤ a_{2l+1} = v of length 2l(α) + 1 from u to v such that l(v) − l(a_{2i−1}) ≥ 2(α_{i} + α_{i+1} + … + α_{l}) + 1, and a_{2i−1} < a_{2i} for i = 1, …, l.

Proof. Let ρ : [u, v] → N be the rank function of [u, v]^{∗}. The result clearly holds if 2k ≥ l(v) − l(u) by part iii) of Theorem 2.7, so we may assume that 2k + 1 ≤ l(v) − l(u).

Fix α ∈ C_{k}. Now let C = (b_{0}, …, b_{i}) ∈ C(u, v) and S = \{S_{1}, …, S_{l}\}_{<} ∈ \binom{[i]}{l(α)} be such that \frac{1}{2}(ρ(b_{S_{j}−1}) − 1) ≥ α_{j} + … + α_{l} for j = 1, …, l. Then (b_{0}, b_{S_{1}−1}, b_{S_{1}}, …, b_{S_{l}−1},

b_{S_{l}}, b_{i}) ∈ M_{α}(u, v), C_{0} =^{def} (b_{0}, b_{1}, …, b_{S_{1}−1}) ∈ C(b_{0}, b_{S_{1}−1}), C_{1} =^{def} (b_{S_{1}}, …, b_{S_{2}−1}) ∈

C(b_{S_{1}}, b_{S_{2}−1}), …, C_{l} =^{def} (b_{S_{l}}, …, b_{i}) ∈ C(b_{S_{l}}, b_{i}). Conversely, if (a_{0}, …, a_{2l+1}) ∈ M_{α}(u, v),

and C_{0} ∈ C(a_{0}, a_{1}), C_{1} ∈ C(a_{2}, a_{3}), …, C_{l} ∈ C(a_{2l}, a_{2l+1}), then C =^{def} (C_{0}, C_{1}, …, C_{l}) ∈

C(u, v), S =^{def} \{l(C_{0}) + 1, l(C_{0}) + l(C_{1}) + 2, …, l(C_{0}) + … + l(C_{l−1}) + l\}_{<} ∈ \binom{l(C)}{l}, and

\frac{1}{2}(ρ(b_{l(C_{0})+...+l(C_{j−1})+j−1}) − 1) ≥ α_{j} + … + α_{l} for j = 1, …, l, (where b_{n} denotes the (n + 1)- st element of C, from the bottom). Since this is a bijection we conclude from Theorem 4.2 and Proposition 3.3, that

[q^{k}](P_{u,v}) = ∑_{C∈C(u,v)}(−1)^{l(C)}[q^{k}](R_{C})
= ε_{u}ε_{v} ∑_{α∈C_{k}} ∑_{(a_{0},...,a_{2l+1})∈M_{α}(u,v)} ∑_{C_{0}∈C(a_{0},a_{1})} … ∑_{C_{l}∈C(a_{2l},a_{2l+1})}(−1)^{l(α)+∑_{i=0}^{l(α)} l(C_{i})}

∏_{j=1}^{l(α)} ε_{a_{2j−1}}ε_{a_{2j}}[q^{α_{j}}](R_{a_{2j−1},a_{2j}})

= ε_{u}ε_{v} ∑_{α∈C_{k}}(−1)^{l(α)} ∑_{(a_{0},...,a_{2l+1})∈M_{α}(u,v)} ∏_{j=1}^{l(α)} ε_{a_{2j−1}}ε_{a_{2j}}[q^{α_{j}}](R_{a_{2j−1},a_{2j}})

∑_{C_{0}∈C(a_{0},a_{1})}(−1)^{l(C_{0})} … ∑_{C_{l}∈C(a_{2l},a_{2l+1})}(−1)^{l(C_{l})},

and the result follows since intervals of W are Eulerian posets. □

Note that in the proof of Theorem 5.1 we have used only the “bottom half” of (21). If we use the “upper half” then we obtain a different formula for the coefficients of Kazhdan-Lusztig polynomials. Given u, v ∈ W with u ≤ v and i ∈ N we let

E_{i}(u, v) =^{def} \{ \begin{matrix}∑_{\{x∈[u,v]: l(x)≥i\}}(−1)^{l(x)}, & if u < v, \\ −ε_{u}, & if u = v. \end{matrix}

Theorem 5.2 Let u, v ∈ W, u ≤ v, and k ∈ [1, ⌊\frac{1}{2}(l(v) − l(u) − 1)⌋]. Then

[q^{k}](P_{u,v}) = ε_{v} ∑_{α∈C_{k}}(−1)^{l(α)} ∑_{(a_{0},...,a_{2l})∈N_{α}(u,v)} E_{l(v)−2k+1}(u, a_{1}) ∏_{i=1}^{l(α)}[q^{α_{i}}](R_{a_{2i−1},a_{2i}})

where N_{α}(u, v) is the set of all multichains u = a_{0} ≤ a_{1} ≤ … ≤ a_{2l} = v of length 2l(α) from u to v such that l(v) − l(a_{2i}) ≤ 2(α_{i+1} + … + α_{l}) − 1 for i = 1, …, l − 1, and a_{2i−1} < a_{2i} for i = 1, …, l.

Proof. Let ρ : [u, v] → N be the rank function of [u, v]^{∗}. Fix α ∈ C_{k}. Now let C = (b_{0}, …, b_{i}) ∈ C(u, v) and S = \{S_{1}, …, S_{l}\}_{<} ∈ \binom{[i]}{l(α)} be such that i ∈ S, \frac{1}{2}(ρ(b_{S_{j}}) + 1) ≤ α_{j+1} + … + α_{l}, for j = 1, …, l − 1, and k ≥ \frac{1}{2}(ρ(b_{1}) + 1) if S_{1} > 1. Then

(b_{0}, b_{S_{1}−1}, b_{S_{1}}, …, b_{S_{l}−1}, b_{i}) ∈ N_{α}(u, v), C_{0} =^{def} (b_{0}, …, b_{S_{1}−1}) ∈ C′(b_{0}, b_{S_{1}−1}), C_{1} =^{def} (b_{S_{1}}, …,

b_{S_{2}−1}) ∈ C(b_{S_{1}}, b_{S_{2}−1}), …, C_{l−1} =^{def} (b_{S_{l−1}}, …, b_{S_{l}−1}) ∈ C(b_{S_{l−1}}, b_{i−1}), where

C′(x, y) =^{def} {(a_{0}, a_{1}, …) ∈ C(x, y) : ρ(a_{1}) ≤ 2k − 1}

for x, y ∈ W, x ≤ y (so C′(x, y) = C(x, y) if x = y). Conversely, if (a_{0}, …, a_{2l}) ∈ N_{α}(u, v),

and C_{1} ∈ C′(a_{0}, a_{1}), C_{2} ∈ C(a_{2}, a_{3}), …, C_{l} ∈ C(a_{2l−2}, a_{2l−1}), then C =^{def} (C_{1}, C_{2}, …, C_{l}, v) ∈

C(u, v), S =^{def} \{l(C_{1}) + 1, l(C_{1}) + l(C_{2}) + 2, …, l(C_{1}) + … + l(C_{l}) + l\} ∈ \binom{[l(C)]}{l}, l(C) ∈ S,

\frac{1}{2}(ρ(b_{l(C_{1})+...+l(C_{j})+j}) + 1) ≤ α_{j+1} + … + α_{l} for j = 1, …, l − 1 (where b_{n} denotes the (n + 1)-st element of C, from the bottom), and k ≥ \frac{1}{2}(ρ(b_{1}) + 1) if l(C_{1}) > 0. Since this is a bijection then from Theorem 4.2 and Proposition 3.5 we deduce that

−[q^{k}](P_{u,v}) = ∑_{C∈C(u,v)}(−1)^{l(C)}[q^{ρ(u)−k}](R_{C})
= ∑_{α∈C_{k}} ∑_{(a_{0},...,a_{2l})∈N_{α}(u,v)} ∑_{C_{1}∈C′(a_{0},a_{1})} … ∑_{C_{l}∈C(a_{2l−2},a_{2l−1})}(−1)^{l(α)+∑_{i=1}^{l(α)} l(C_{i})}

∏_{j=1}^{l(α)}[q^{α_{j}}](R_{a_{2j−1},a_{2j}})ε_{a_{2j−1}}ε_{a_{2j}},

and the result follows as in the proof of Theorem 5.1 since

∑_{C∈C′(a_{0},a_{1})}(−1)^{l(C)} = ∑_{{x∈(a_{0},a_{1}]: ρ(x)≤2k−1}} ∑_{C∈C(x,a_{1})}(−1)^{l(C)+1}
= ∑_{{x∈(a_{0},a_{1}]: ρ(x)≤2k−1}} −ε_{x}ε_{a_{1}}
= −ε_{a_{1}} E_{l(v)−2k+1}(a_{0}, a_{1})

(since 2k − 1 < ρ(u) = ρ(a_{0})) if a_{0} < a_{1}, while

∑_{C∈C′(a_{0},a_{1})}(−1)^{l(C)} = ∑_{C∈C(a_{0},a_{0})}(−1)^{l(C)} = (−1)^{0} = −ε_{a_{1}} E_{l(v)−2k+1}(a_{0}, a_{1}),

if a_{0} = a_{1}. □

Note that, if u < v, E_{i}(u, v) = 0 unless l(u) + 1 ≤ i ≤ l(v). Also, we have the following result.

Proposition 5.3 Let u, v ∈ W, u < v, and i ∈ [l(u)+1, l(v)]. Then −ε_{v}E_{i}(u, v) equals the value of the Möbius function of the rank-selected subposet [u, v]_{{0}∪[i−l(u),l(v)−l(u)]} evaluated at (u, v). In particular, (−1)^{i}E_{i}(u, v) ≥ 0.

Proof. Let, for brevity, P =^{def} [u, v]_{{0}∪[i−l(u),l(v)−l(u)]}. Note that by the definition of the Möbius function of a poset (see, e.g., [20], §3.7) we have that

μ_{P} (a, v) = μ_{[u,v]}(a, v)

for all a ∈ P \ {u}. Therefore, again by the definition of the Möbius function

μ_{P} (u, v) = − ∑_{a∈P \{u}} μ_{P} (a, v)
= − ∑_{a∈P \{u}}(−1)^{l(v)−l(a)}
= − ∑_{{a∈[u,v]: l(a)≥i}}(−1)^{l(v)−l(a)}
= −ε_{v} E_{i}(u, v)  (22)

where we have used the fact that the intervals of W are Eulerian posets. Now, it is well known (see, e.g., [4], Theorem 5.5) that intervals of W are Cohen-Macaulay (see, e.g. [3], for the definition of, and further information about, Cohen-Macaulay posets) hence by Theorem 5.2 of [3], P is a Cohen-Macaulay poset, and this, by (22) and Proposition 3.8.11 of [20] implies that (−1)^{i}E_{i}(u, v) ≥ 0. □

We don’t know any direct proof of the equivalence of Theorems 5.1 and 5.2, nor of the equivalence of these results with Theorem 5.2 of [6], even for k = 3. For k = 1 it is easy to see that Theorem 5.2 reduces to Corollary 5.3 of [6] while Theorem 5.1 yields the following result.

Corollary 5.4 Let u, v ∈ W. Then

[q](P_{u,v}) = − ∑_{{x,y∈[u,v]: ρ(x)≥3}}[q](R_{x,y}),

where ρ : [u, v] → N is the rank function of [u, v]^{∗}. □

Comparison of Corollary 5.4 with Corollary 5.3 of [6] yields the following curious identity, which proves a special case of Conjecture 7.2 of [8].

Corollary 5.5 Let u, v ∈ W. Then

[q] ( ∑_{x,y∈[u,v]} R_{x,y}) = −ε_{u}ε_{v}[q](R_{u,v}).  (23)

In particular, [q](∑_{x,y∈[u,v]} R_{x,y}) ≥ 0.

Proof. Comparing Corollary 5.4 with Corollary 5.3 of [6] we obtain that

− ∑_{{x,y∈[u,v]: ρ(x)≥3}}[q](R_{x,y}) = ε_{u}ε_{v}[q](R_{u,v}) + |[u, v]_{1}^{∗}|,  (24)

where ρ : [u, v] → N is the rank function of [u, v]^{∗}. Now note that

|[u, v]_{1}^{∗}| = ∑_{{x,y∈[u,v]: ρ(x)=1}}[q](R_{x,y}),

and

∑_{{x,y∈[u,v]: ρ(x)=2}}[q](R_{x,y}) = ∑_{x∈[u,v]_{2}^{∗}} ∑_{y∈[u,v]}[q](R_{x,y}) = ∑_{x∈[u,v]_{2}^{∗}}(1 + 1 − 2) = 0,

since W is Eulerian, and (23) follows from (24). The second statement follows easily from (23) and (6). □

For k = 2 it is not hard to see that Theorem 5.2 is equivalent to Corollary 5.4 of [6], while Theorem 5.1 implies the following result.

Corollary 5.6 Let u, v ∈ W. Then

[q^{2}](P_{u,v}) = − ∑_{{x,y∈[u,v]: ρ(x)≥5}}([q^{2}](R_{x,y}) + [q](R_{x,y})[q](P_{y,v})),

where ρ has the same meaning as in Corollary 5.4.

Proof. From Theorem 5.1 we deduce that

[q^{2}](P_{u,v}) = − ∑_{{u≤x<y≤v: ρ(x)≥5}}[q^{2}](R_{x,y}) + ∑_{{u≤x<y≤z<w≤v: ρ(x)≥5, ρ(z)≥3}}[q](R_{x,y})[q](R_{z,w}),

(25)

and the result follows from Corollary 5.4. □

Comparing (25) with Corollary 5.4 of [6] yields an identity for the R-polynomials which, however, we have been unable to state in a simple way analogous to that of Corollary 5.5.

It should be noted that the antisymmetry of the polynomial on the RHS of (21) (which, of course, implies the equivalence of Theorems 5.1 and 5.2) is not trivial even for the coefficients of q^{0} and q^{l(v)−l(u)}, as the next result shows.

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

∑_{i≥1}(−1)^{i}c_{i} = (−1)^{l(v)−l(u)},  (26)

where c_{i} is the number of chains of length i from u to v, for i ∈ P.

Proof. By Proposition 3.1 we have that

[q^{0}] ( ∑_{C∈C(u,v)}(−1)^{l(C)}R_{C}) = ∑_{C∈C(u,v)}(−1)^{l(C)}R_{C}(0) = ε_{u}ε_{v} ∑_{C∈C(u,v)}(−1)^{l(C)},

and that

[q^{l(v)−l(u)}] ( ∑_{C∈C(u,v)}(−1)^{l(C)}R_{C}) = ∑_{C∈C(u,v)}(−1)^{l(C)}[q^{l(v)−l(u)}](R_{C})
= −[q^{l(v)−l(u)}](R_{u,v}) = −1,

and the result follows from Theorem 4.2. □

By P. Hall’s Theorem (see, e.g., [20], Proposition 3.8.5) Corollary 5.7 is equivalent to the well known (but non-trivial, see, e.g., [24], [10], [4]) result that μ(u, v) = (−1)^{l(v)−l(u)} for all u, v ∈ W, u ≤ v, where μ denotes the Möbius function of W (as a poset). Hence Corollary 5.7 is equivalent to the fact that intervals of W are Eulerian posets.

6 Lattice paths

In this section we define and study a family of polynomials, indexed by sequences of positive integers, which plays a fundamental role in the proof of our main result. These polynomials are independent of W, and are related to the combinatorics of lattice paths.

For α ∈ C we define a polynomial Ψ_{α}(q) ∈ Z[q] inductively as follows,

Ψ_{α}(q) =^{def} (q − 1)^{α_{1}}D_{\frac{|\overline{α}|−1}{2}} (Ψ\overline{α}(q))  (27)

if l(α) ≥ 2, and

Ψ_{α}(q) =^{def} (q − 1)^{|α|},  (28)

if l(α) = 1. For n ∈ P and β ∈ C_{n} we then let

Υ_{β}(q) =^{def} ∑_{{α∈C_{n}: α⪯β}}(−1)^{l(α)}Ψ_{α}(q).  (29)

For example,

Ψ_{1,5}(q) = (q − 1) D_{\frac{5−1}{2}} (Ψ_{5}(q)) = (q − 1)D_{2}((q − 1)^{5}) = −10q^{3} + 15q^{2} − 6q + 1,

and

Υ_{2,3}(q) = Ψ_{2,3}(q) − Ψ_{1,1,3}(q) − Ψ_{2,2,1}(q) + Ψ_{1,1,2,1}(q) − Ψ_{2,1,2}(q) + Ψ_{1,1,1,2}(q)
+Ψ_{2,1,1,1}(q) − Ψ_{1,1,1,1,1}(q) = q^{3} − q^{2}.

We begin by giving a combinatorial interpretation to the polynomials Ψ_{α}(q) and Υ_{α}(q), α ∈ C. For n ∈ P and S ⊆ [n − 1] we let

H(S, n) =^{def} {Γ ∈ D(n) : N(Γ) ⊇ S},  (30)

and

E(S, n) =^{def} {Γ ∈ D(n) : N(Γ) = S}.  (31)

For example, the four lattice paths in E({5}, 6) are illustrated in Figure 4. Recall that

for β ∈ C we let T (β) =^{def} {β_{r}, β_{r} + β_{r−1}, …, β_{r} + … + β_{2}} where r =^{def} l(β).

Theorem 6.1 Let α ∈ C. Then

(−1)^{|α|}Ψ_{α}(−q) = ∑_{Γ∈H(T (α),|α|)} q^{d_{+}(Γ)},  (32)

and

(−1)^{|α|−l(α)}Υ_{α}(−q) = ∑_{Γ∈E(T (α),|α|)} q^{d_{+}(Γ)}.  (33)

Proof.We prove (32) first. Let Γ ∈ H(T (α), |α|). Then Γ_{|_{[0,|\overline{α}|]}} ∈ H(T (\overline{α}), |\overline{α}|) and Γ(|\overline{α}|) < 0. Conversely, if Γ′ ∈ H(T (\overline{α}), |\overline{α}|) and Γ′(|\overline{α}|) < 0 then extending Γ′ to [0, |α|] by adding any α_{1} steps yields 2^{α_{1}} different lattice paths in H(T (α), |α|). Therefore

∑_{Γ∈H(T (α),|α|)} q^{d_{+}(Γ)} = (1 + q)^{α_{1}} ∑_{\{Γ′∈H(T (\overline{α}),|\overline{α}|): Γ′(|\overline{α}|)<0\}} q^{d_{+}(Γ′)}
= (1 + q)^{α_{1}}D_{\frac{|\overline{α}|−1}{2}} (  ∑_{Γ∈H(T (\overline{α}),|\overline{α}|)} q^{d_{+}(Γ)}) ,  (34)

by (4), and (32) follows easily from (34), (27), and (28) by induction on l(α). To prove (33) note that it is clear from our definitions (30) and (31) that

∑_{S⊆A⊆[|α|−1]} ( ∑_{Γ∈E(A,|α|)} q^{d_{+}(Γ)}) = ∑_{Γ∈H(S,|α|)} q^{d_{+}(Γ)}

for all S ⊆ [|α| − 1]. Therefore, by the principle of Inclusion-Exclusion, and (32), we conclude that

∑_{Γ∈E(T (α),|α|)} q^{d_{+}(Γ)} = ∑_{T (α)⊆S⊆[|α|−1]}(−1)^{|S\T (α)|} ( ∑_{Γ∈H(S,|α|)} q^{d_{+}(Γ)})
= ∑_{{β∈C_{|α|}: T (α)⊆T (β)}}(−1)^{|T (β)\T (α)|+|β|}Ψ_{β}(−q)
= (−1)^{|α|} ∑_{{β∈C_{|α|}:β⪯α}}(−1)^{l(β)−l(α)}Ψ_{β}(−q)

and (33) follows from (29). □

We illustrate the preceding theorem with an example. Let α = (1, 5), then E({5}, 6) consists of the 4 lattice paths illustrated in Figure 4 and hence Υ_{1,5}(−q) = 2q^{2} + 2q^{3}.

[figure]

Figure 4: The 4 lattice paths in E({5}, 6).

There is a geometric reformulation of Theorem 6.1 which we feel is worth noting explicitly. Let q be a prime power and k =^{def} F_{q} be the finite field on q elements. Let n ∈ P, and (e_{1}, …, e_{n}) be an ordered basis of F_{q}^{n}. Given a subspace V ⊆ F_{q}^{n} we let

D(V) =^{def} \{i ∈ [n − 1] : dim_{k}(V ∩ E_{i}) ≤ \frac{i − 1}{2}\} ,

where E_{j} =^{def} ⟨e_{1}, …, e_{j}⟩, for j = 1, …, n. We say that a subspace V ⊆ F_{q}^{n} is a coordinate subspace if V = ⟨e_{i_{1}}, …, e_{i_{r}}⟩ for some {i_{1}, …, i_{r}} ⊆ [n] (0 ≤ r ≤ n). Given S ⊆ [n − 1] we denote by E_{S,n} (respectively, H_{S,n}) the set of all coordinate subspaces V of F_{q}^{n} such that D(V) = S (respectively, D(V) ⊇ S). It is then clear that there is a bijection between E_{S,n} and E(S, n) (and hence, since H_{S,n} = ⊎_{A⊇S}E_{A,n}, also between H_{S,n} and H(S, n)). Namely, if V ∈ E_{S,n} then the lattice path Γ_{V} : [0, n] → Z defined by

Γ_{V} (i) − Γ_{V} (i − 1) = 1

if and only if e_{i} ∈ V, is in E(S, n) (since dim_{k}(V ∩ E_{i}) = |{j ∈ [i] : e_{j} ∈ V }| = d_{+}((Γ_{V})|_{[0,i]}) = \frac{Γ_{V} (i)+i}{2}, for i ∈ [n]). Conversely, if Γ ∈ E(S, n) then ⟨\{e_{i} : i ∈ [n], Γ(i) − Γ(i − 1) = 1}⟩ ∈ E_{S,n} and this is a bijection. We can therefore restate Theorem 6.1 in geometric language as follows.

Theorem 6.2 Let β ∈ C, and q be a prime power. Then

(−1)^{|β|−l(β)}Υ_{β}(−q) = ∑_{V ∈E_{T (β),|β|}} |V |,

and

(−1)^{|β|}Ψ_{β}(−q) = ∑_{V ∈H_{T (β),|β|}} |V |.

Proof. From Theorem 6.1, and the above comments, we have that

(−1)^{|β|−l(β)}Υ_{β}(−q) = ∑_{Γ∈E(T (β),|β|)} q^{d_{+}(Γ)}
= ∑_{V ∈E_{T (β),|β|}} q^{dim_{k}(V)}
= ∑_{V ∈E_{T (β),|β|}} |F_{q}|^{dim_{k}(V)}
= ∑_{V ∈E_{T (β),|β|}} |V |,

and similarly for (−1)^{|β|}Ψ_{β}(−q). □

It would be interesting to know if the preceding result can be interpreted in terms of intersection homology.

Theorem 6.1 enables us to give a simple inductive procedure to compute the polynomials Υ_{β}(q), analogous to the definition of the polynomials Ψ_{α}(q).

Theorem 6.3 Let β ∈ C. Then

Υ_{β}(q) = (q − 1)U_{\frac{|β|−1}{2}} (Υ_{β^{(1)}}(q)),  (35)

if β_{1} ≥ 2,

Υ_{β}(q) = (1 − q)D_{\frac{|β|−2}{2}} (Υ\overline{β}(q)),  (36)

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

Υ_{1}(q) = 1 − q.

Proof. Suppose first that β_{1} ≥ 2. Then |β^{(1)}| ∉ T (β) and T (β) = T (β^{(1)}). Hence if Γ ∈ E(T (β), |β|) then Γ(|β^{(1)}|) ≥ 0, and Γ_{|_{[0,|β^{(1)}|]}} ∈ E(T (β^{(1)}), |β^{(1)}|). Conversely, if Γ′ ∈ E(T (β^{(1)}), |β^{(1)}|) and Γ′(|β^{(1)}|) ≥ 0 then extending Γ′ to all of [0, |β|] by adding any one step yields two lattice paths in E(T (β), |β|). Therefore

∑_{Γ∈E(T (β),|β|)} q^{d_{+}(Γ)} = (1 + q) ∑_{{Γ′∈E(T (β^{(1)}),|β^{(1)}|): Γ′(|β^{(1)}|)≥0}} q^{d_{+}(Γ′)}
= (1 + q)U_{\frac{|β|−1}{2}} (  ∑_{Γ∈E(T (β^{(1)}),|β^{(1)}|)} q^{d_{+}(Γ)}) ,

by (4), and (35) follows from (33).

Similarly, if β_{1} = 1 then |β| − 1 ∈ T (β) and T (\overline{β}) = T (β) \ \{|β| − 1\}. Hence if Γ ∈ E(T (β), |β|) then Γ(|β| − 1) < 0 and Γ_{|_{[0,|\overline{β}|]}} ∈ E(T (\overline{β}), |\overline{β}|). Conversely, if Γ′ ∈ E(T (\overline{β}), |\overline{β}|) and Γ′(|β| − 1) < 0 then extending Γ′ to all of [0, |β|] by adding any one step yields two lattice paths in E(T (β), |β|). Therefore

∑_{Γ∈E(T (β),|β|)} q^{d_{+}(Γ)} = (1 + q) ∑_{\{Γ′∈E(T (\overline{β}),|\overline{β}|): Γ′(|\overline{β}|)<0\}} q^{d_{+}(Γ′)}

= (1 + q)D_{\frac{|β|−2}{2}} (  ∑_{Γ∈E(T (\overline{β}),|\overline{β}|)} q^{d_{+}(Γ)}) ,

again by (4), and (36) follows from (33). □

There are a number of symmetries that act on lattice paths. One of these yields (by Theorem 6.1) a corresponding symmetry for the Υ-polynomials. Recall that for β ∈ C we let β̃ ∈ C be the complementary composition of β.

Proposition 6.4 Let β ∈ C. Then

−q^{|β|}Υ_{β} (\frac{1}{q}) = Υ_{(β̃,1)}(q).

In particular, −q^{n}Υ_{n}(1/q) = Υ_{(1^{n+1})}(q) for n ∈ P.

Proof. For Γ ∈ E(T (β), |β|) let Γ′ : [0, |β| + 1] → Z be defined by

Γ′(i) =^{def} \{ \begin{matrix}0, & if i = 0, \\ −Γ(i − 1) − 1, & if i ∈ [|β| + 1]. \end{matrix}

Then Γ′ is clearly a lattice path and Γ′ ∈ E(T (β̃, 1), |β| + 1) since

T (β̃, 1) = {1} ∪ (1 + T (β̃)) = {1} ∪ ([2, |β|] \ (1 + T (β))) = [|β|] \ (1 + T (β)), (37)

and N(Γ′) = [|β|] \ (1 + N(Γ)).

Conversely, if Γ′ ∈ E(T (β̃, 1), |β| + 1) then Γ : [0, |β|] → Z defined by

Γ(i) = −Γ′(i + 1) − 1

for i ∈ [0, |β|] is again a lattice path and Γ ∈ E(T (β), |β|) (note that Γ′(1) = −1). It is clear that this correspondence Γ ↔ Γ′ is a bijection between E(T (β), |β|) and E(T (β̃, 1), |β| + 1), and that d_{+}(Γ) = |β| − d_{+}(Γ′), hence

∑_{Γ∈E(T (β),|β|)} q^{d_{+}(Γ)} = ∑_{Γ′∈E(T (β̃,1),|β|+1)} q^{|β|−d_{+}(Γ′)},

and the thesis follows from (33) since l(β) + l(β̃) = (|T (β)| + 1) + (|T (β̃)| + 1) = |β| + 1. □

Theorem 6.1 and Proposition 6.4 enable us to prove the fundamental fact that any polynomial Υ_{β}(q) is easily expressible in terms of two very special kinds of Υ-polynomials. For n ∈ N we denote by C(n) the n-th Catalan number (see, e.g., [9], §1.15, p. 53) so that C(n) = \frac{1}{n+1} \binom{2n}{n} if n ∈ P, and C(0) = 1.

Theorem 6.5 Let β ∈ C, l(β) ≥ 2, and [α_{1}, ω_{1}], …, [α_{s}, ω_{s}] be the connected components of T (β) (indexed so that 1 ≤ α_{1} < α_{2} < … < α_{s} ≤ |β| − 1). Then

Υ_{β}(q) = \{ \begin{matrix}(−1)^{l(β)+ \frac{|β|−β_{1}−1}{2}} K_{β} C (\frac{ω_{s}−α_{s}}{2} ) q^{\frac{|β|−β_{1}+1}{2}} Υ_{β_{1}−1}(q), & if β_{1} ≥ 2, \\ (−1)^{l(β̃)+ \frac{|β|−β̃_{1}}{2} −1}K_{β} q^{\frac{|β|−β̃_{1}}{2}} Υ_{(1β̃_{1})}(q), & if β_{1} = 1, \end{matrix}  (38)

where K_{β} =^{def} C (\frac{α_{s}−ω_{s−1}−2}{2}) ∏_{j=1}^{s−1} (C (\frac{α_{j}−ω_{j−1}−2}{2}) C (\frac{ω_{j}−α_{j}}{2} )), ω_{0} =^{def} −1 , and C(n) =^{def} 0 if

n ∉ N.

Proof. Assume first that β_{1} ≥ 2. Note that if Γ ∈ E(T (β), |β|) then Γ(α_{j} − 1) ≥ 0, Γ(α_{j}) < 0, Γ(ω_{j}) < 0, and Γ(ω_{j} + 1) ≥ 0 for j ∈ [s]. Since Γ is a lattice path this implies that

Γ(α_{j} − 1) = Γ(α_{j}) + 1 = 0 ,  (39)

and

Γ(ω_{j} + 1) = Γ(ω_{j}) + 1 = 0  (40)

for j ∈ [s]. Now let, for Γ ∈ E(T (β), |β|), Γ_{j} =^{def} Γ_{|_{(ω_{j−1},α_{j})}}, and Γ′_{j} =^{def} −Γ_{|_{[α_{j} ,ω_{j}]}} − 1, for j ∈ [s]. Then it is clear from our definitions that N(Γ_{j}) = N(Γ′_{j}) = ∅ for j ∈ [s]. This, by (39) and (40), shows that Γ_{j} ∈ E_{(ω_{j−1},α_{j})}^{∗}, and Γ′_{j} ∈ E_{[α_{j},ω_{j}]}^{∗}, for j ∈ [s], where, for a, b ∈ Z, E_{[a,b]}^{∗} denotes the set of all the lattice paths Γ : [a, b] → Z such that N(Γ) = ∅ and Γ(b) = 0. We now construct a bijection

φ : E(T (β), |β|) → E(∅, |β| − ω_{s} − 1) × (×_{j=1}^{s} (E_{(ω_{j−1},α_{j})}^{∗} × E_{[α_{j},ω_{j}]}^{∗})) ,

that will prove (38) combinatorially. Given Γ ∈ E(T (β), |β|) we let φ(Γ) =^{def} (Γ_{0}, Γ_{1}, …, Γ_{s}, Γ′_{1}, …, Γ′_{s}) where

Γ_{0}(i) =^{def} Γ(i + ω_{s} + 1)  (41)

for i ∈ [0, |β| − ω_{s} − 1]. Note that, by (41) and our definitions, Γ_{0} ∈ E(∅, |β| − ω_{s} − 1).

Conversely, if Γ_{0} ∈ E(∅, |β| − ω_{s} − 1) and Γ_{j} ∈ E_{(ω_{j−1},α_{j})}^{∗}, Γ′_{j} ∈ E_{[α_{j},ω_{j}]}^{∗} for j ∈ [s] then Γ : [0, |β|] → Z defined by

Γ(i) =^{def} \{ \begin{matrix}Γ_{j}(i), & if i ∈ (ω_{j−1}, α_{j}), & for some j ∈ [s], \\ −Γ′_{j}(i) − 1, & if i ∈ [α_{j}, ω_{j}], & for some j ∈ [s], \\ Γ_{0}(i − ω_{s} − 1), & if i ∈ (ω_{s}, |β|], \end{matrix}

is clearly a lattice path and Γ ∈ E(T (β), |β|). This shows that φ is a bijection and furthermore we have that

d_{+}(Γ) = \frac{Γ(|β|) + |β|}{2} = \frac{Γ_{0}(|β| − ω_{s} − 1) + |β|}{2} = d_{+}(Γ_{0}) + \frac{ω_{s} + 1}{2}.

Hence

∑_{Γ∈E(T (β),|β|)} q^{d_{+}(Γ)} = ∑_{Γ_{0}∈E(∅,|β|−ω_{s}−1)} ∑_{Γ_{1}∈E_{(ω_{0},α_{1})}^{∗}} ∑_{Γ′_{1}∈E_{[α_{1},ω_{1}]}^{∗}} … ∑_{Γ_{s}∈E_{(ω_{s−1},αs)}^{∗}} ∑_{Γ′_{s}∈E_{[αs,ωs]}^{∗}} q^{d_{+}(Γ_{0})+ \frac{ωs+1}{2}}
= q^{\frac{ωs+1}{2}} ∑_{Γ_{0}∈E(∅,|β|−ω_{s}−1)} q^{d_{+}(Γ_{0})} ∏_{j=1}^{s}(|E_{(ω_{j−1},α_{j})}^{∗}||E_{[α_{j},ω_{j}]}^{∗}|)
= q^{\frac{ωs+1}{2}} ∏_{j=1}^{s} (C (\frac{α_{j} − ω_{j−1} − 2}{2}) C (\frac{ω_{j} − α_{j}}{2} )) ∑_{Γ∈E(∅,|β|−ω_{s}−1)} q^{d_{+}(Γ)}

by a well known property of Catalan numbers (see, e.g., [9], Theorem B, p. 21) and the first part of (38) follows from (33).

Assume now that β_{1} = 1. Then ω_{s} = |β| − 1, and hence, by (37), [ω_{0} + 2, α_{1}], [ω_{1} + 2, α_{2}], …, [ω_{s−1} +2, α_{s}] are the connected components of T (β̃, 1). By Proposition 6.4, and what we have just proved (applied to (β̃, 1), since (β̃)_{1} ≥ 2 because β_{1} = 1) we then have that

Υ_{β}(q) = −q^{|β|}Υ_{(β̃,1)} (\frac{1}{q})
= (−1)^{l(β̃)+ \frac{|β|−β̃_{1}}{2}} K_{(β̃,1)}C (\frac{α_{s} − ω_{s−1} − 2}{2}) q^{|β|− \frac{|β|−β̃_{1}+2}{2}} Υ_{β̃_{1}−1} (\frac{1}{q})
= (−1)^{l(β̃)+1+ \frac{|β|−β̃_{1}}{2}} K_{(β̃,1)}C (\frac{α_{s} − ω_{s−1} − 2}{2}) q^{\frac{|β|−β̃_{1}}{2}} Υ_{(1β̃_{1})}(q)

and the result follows since it is easy to verify that K_{(β̃,1)}C (\frac{α_{s}−ω_{s−1}−2}{2}) = K_{β}. □

We illustrate the preceding theorem with some examples. Let β = (1, 1, 1, 4, 1, 1, 2, 4, 1, 1, 5). Then T (β) = {5, 6, 7, 11, 13, 14, 15, 19, 20, 21} = [5, 7]⊎[11, 11]⊎[13, 15]⊎[19, 21] and hence Υ_{β}(q) = C(2)C(1)C(1)C(0)C(0)C(1)C(1)q^{9}Υ_{(1^{4})}(q) = 2q^{9} Υ_{(1^{4})}(q). If β = (4, 1, 1, 6, 4, 1, 1, 7) then T (β) = {7, 8, 9, 13, 19, 20, 21} = [7, 9] ⊎ [13, 13] ⊎ [19, 21] and hence Υ_{β}(q) = C(3)C(1)C(1)C(0)C(2)C(1)q^{11}Υ_{3}(q) = 10q^{11}Υ_{3}(q).

Theorem 6.5 and Proposition 6.4 reduce the problem of computing any Υ-polynomial to that of computing Υ_{n}(q) for n ∈ P. These polynomials, in turn, can be computed in a completely explicit way. For n ∈ P let

B_{n}(q) =^{def} ∑_{i=0}^{n} (\begin{matrix}2n \\ n−i \end{matrix}) \frac{2i + 1}{1 + n + i}q^{n+i}.  (42)

The polynomials B_{n}(q) are closely related to ballot problems (see, e.g., [1], [15] §III.1, p. 21, [16] §5.3).

Proposition 6.6 Let n ∈ P. Then

Υ_{2n}(q) = −B_{n}(−q)  (43)

and

Υ_{2n+1}(q) = (1 − q)B_{n}(−q).  (44)

Proof. We prove (43) first. By Theorem 6.1 we have that

−Υ_{2n}(−q) = ∑_{Γ∈E(∅,2n)} q^{d_{+}(Γ)} = ∑_{\{Γ:Γ(i)≥0, i∈[2n]\}} q^{\frac{2n+Γ(2n)}{2}}
= ∑_{\{i∈[0,2n], i≡0 (2)\}} \frac{i + 1}{\frac{2n+i}{2} + 1} ( 2n_{\frac{2n−i}{2}} ) q^{\frac{2n+i}{2}}  (45)

where we have used a well known classical result on lattice paths (see, e.g., [9], Theorem B, p. 21). This proves (43). To prove (44) note that from Theorem 6.3 we have that

Υ_{2n+1}(q) = (q − 1)U_{n}(Υ_{2n}(q)),

and (44) follows from (43) and (42). □

An immediate consequence of Theorem 6.5 and Proposition 6.6 is a simple characterization of which Υ-polynomials are equal to zero.

Corollary 6.7 Let β ∈ C, and [α_{1}, ω_{1}], …, [α_{s}, ω_{s}] be the connected components of T (β) (indexed as in Theorem 6.5). Then the following are equivalent:

i) Υ_{β}(q) ≠ 0;

ii) α_{1}, …, α_{s}, ω_{1}, …, ω_{s−1} are odd, and ω_{s} is odd if ω_{s} < |β| − 1. □

Note that condition ii) in the above corollary is vacuously satisfied if l(β) = 1 (i.e., if T (β) = ∅), and is always satisfied if β = (1^{|β|}).

We conclude this section by collecting some more properties of the polynomials Υ_{β}(q). For β ∈ C we denote by m_{Υ}(β) the maximum power of q that divides Υ_{β}(q).

Proposition 6.8 Let β ∈ C be such that Υ_{β}(q) ≠ 0. Then:

i) (−1)^{|β|−l(β)} Υ_{β}(−q) is a log-concave polynomial with no internal zeros; ii) m_{Υ}(β) = ⌊\frac{|β|−β̃_{1}+1}{2}⌋;

iii) deg(Υ_{β}) = β_{1}+ max(⌊\frac{|\overline{β}|−1}{2}⌋ , 0).

Proof. i) is an immediate consequence of Theorem 6.3. To prove ii) and iii) assume first that l(β) = 1. It then follows from Proposition 6.6 that

deg(Υ_{n}) = n , m_{Υ}(n) = ⌊\frac{n}{2}⌋  (46)

for n ∈ P, and hence ii) and iii) hold in this case. Furthermore, it follows from (46) and Proposition 6.4 that

deg(Υ_{(1^{n+1})}) = ⌊\frac{n + 1}{2}⌋ , m_{Υ}((1^{n+1})) = 0  (47)

for n ∈ P, so that ii) and iii) also hold if l(β̃) = 1. In the other cases ii) and iii) follow from Theorem 6.5, using (46) and (47). □

Proposition 6.9 Let β ∈ C be such that l(β), l(β̃) ≥ 2, and Υ_{β} ≠ 0. Then Υβ̃ = 0.

Proof. Since l(β), l(β̃) ≥ 2 we have that T (β), T (β̃) ≠ ∅. Therefore either α_{1} > 1 or ω_{1} < |β| − 1 but this means that either [1, α_{1} − 1] or [ω_{1} + 1, α_{2} − 1] is the first (i.e., leftmost) connected component of T (β̃), and the thesis follows from Corollary 6.7. □

Note that the converse of the above result does not hold. For example, Υ_{1,3,1,1} = Υ_{2,1,3} = 0.

7 The main result

In this section we prove the main result of this work (Theorem 7.3). We begin by expressing the R-polynomial of a chain in terms of the polynomials Ψ_{α}(q).

Proposition 7.1 Let a_{0} < a_{1} < … < a_{i} be a chain in W. Then

R_{a_{0},...,a_{i}}(q) = ∑_{α∈P^{i}} q^{\frac{l(a_{i})−l(a_{0})−|α|}{2}} Ψ_{α}(q) ∏_{r=1}^{i}[q^{α_{r}}](R̃_{a_{r−1},a_{r}}).  (48)

Proof. If i = 1 then (48) follows immediately from (28), (14), and (7). We now proceed by induction on i ∈ P. Since i ≥ 2 we have from (13) and our induction hypothesis that

R_{a_{0},...,a_{i}}(q) = R_{a_{0},a_{1}}(q)D_{\frac{d−1}{2}} ( ∑_{α∈P^{i−1}} q^{\frac{l(a_{i})−l(a_{1})−|α|}{2}} Ψ_{α}(q) ∏_{r=1}^{i−1}[q^{α_{r}}](R̃_{a_{r},a_{r+1}}))
= ∑_{α_{0}>0} q^{\frac{l(a_{1})−l(a_{0})−α_{0}}{2}} Ψ_{α_{0}}(q) [q^{α_{0}}](R̃_{a_{0},a_{1}})D_{\frac{d−1}{2}} ( ∑_{α∈P^{i−1}} q^{\frac{l(a_{i})−l(a_{1})−|α|}{2}}

Ψ_{α}(q) ∏_{r=1}^{i−1}[q^{α_{r}}](R̃_{a_{r},a_{r+1}}))

= ∑_{α_{0}>0} ∑_{α∈P^{i−1}} q^{\frac{l(a_{1})−l(a_{0})−α_{0}}{2}} ∏_{r=0}^{i−1}[q^{α_{r}}](R̃_{a_{r},a_{r+1}})Ψ_{α_{0}}(q)D_{\frac{d−1}{2}} (q^{\frac{d−|α|}{2}} Ψ_{α}(q))
= ∑_{α_{0}>0} ∑_{α∈P^{i−1}} q^{\frac{l(a_{1})−l(a_{0})−α_{0}}{2} + \frac{d−|α|}{2}} ∏_{r=0}^{i−1}[q^{α_{r}}](R̃_{a_{r},a_{r+1}})Ψ_{α_{0}}(q)D_{\frac{d−1}{2} − \frac{d−|α|}{2}} (Ψ_{α}(q))
= ∑_{α_{0}>0} ∑_{α∈P^{i−1}} q^{\frac{l(a_{i})−l(a_{0})−α_{0}−|α|}{2}} ∏_{r=1}^{i}[q^{α_{r−1}}](R̃_{a_{r−1},a_{r}})Ψ_{α_{0}}(q)D_{\frac{|α|−1}{2}} (Ψ_{α}(q)),

where d =^{def} l(a_{i}) − l(a_{1}), and (48) follows from (27) and (28). □

The preceding result, together with (29) and Theorem 4.2, yields the following elegant expression for the Kazhdan-Lusztig polynomials in terms of the polynomials Υ_{β}(q).

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

P_{u,v}(q) − q^{l(v)−l(u)} P_{u,v} (\frac{1}{q}) = ∑_{Δ∈B(u,v)} q^{\frac{l(v)−l(u)−l(Δ)}{2}} Υ_{D(Δ)}(q),  (49)

where B(u, v) is the set of all Bruhat paths from u to v.

Proof. From Theorem 4.2 and Proposition 7.1 we have that

P_{u,v}(q) − q^{l(v)−l(u)}P_{u,v} (\frac{1}{q}) = ∑_{C∈C(u,v)}(−1)^{l(C)}R_{C}(q)
= ∑_{i≥1}(−1)^{i} ∑_{α∈P^{i}} q^{\frac{l(v)−l(u)−|α|}{2}} Ψ_{α}(q) ∑_{(a_{0},...,a_{i})} ∏_{r=1}^{i}[q^{α_{r}}](R̃_{a_{r−1},a_{r}})
= ∑_{α∈C}(−1)^{l(α)} q^{\frac{l(v)−l(u)−|α|}{2}} Ψ_{α}(q) c_{α}(u, v),  (50)

by Proposition 2.6 (where (a_{0}, …, a_{i}) runs over all the chains of length i from u to v). On the other hand, from (11) and (29) we have that

∑_{α∈C_{n}}(−1)^{l(α)} Ψ_{α}(q) c_{α}(u, v) = ∑_{α∈C_{n}}(−1)^{l(α)} Ψ_{α}(q) ∑_{{β∈C_{n}: β⪰α}} b_{β}(u, v)
= ∑_{β∈C_{n}} b_{β}(u, v) ∑_{{α∈C_{n}: α⪯β}}(−1)^{l(α)}Ψ_{α}(q)
= ∑_{β∈C_{n}} b_{β}(u, v) Υ_{β}(q),  (51)

for all n ∈ P. Therefore we conclude from (50) that

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

which, by (10), is equivalent to (49). □

We can now prove the main result of this work. Given n ∈ Z and A ⊆ Z we let

n − A =^{def} {n − a : a ∈ A}.

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

P_{u,v}(q) = ∑_{(Γ,Δ)}(−1)^{Γ_{≥0}+d_{+}(Γ)} q^{\frac{l(v)−l(u)+Γ(l(Γ))}{2}}

where the sum is over all pairs (Γ, Δ) such that Γ is a lattice path, Δ is a Bruhat path from u to v, l(Γ) = l(Δ), N(Γ) = l(Δ) − D(Δ), and Γ(l(Γ)) < 0.

Proof. Note first that if Γ is a lattice path and β ∈ C is such that Γ ∈ E(T (β), |β|) then T (β) = N(Γ) and |β| = l(Γ). Hence, in particular,

l(β) = |T (β)| + 1 = |β| − Γ_{≥0}.

Therefore we conclude from Theorems 7.2 and 6.1 that

P_{u,v}(q) − q^{l(v)−l(u)}P_{u,v} (\frac{1}{q}) = ∑_{Δ∈B(u,v)} q^{\frac{l(v)−l(u)−l(Δ)}{2}} Υ_{D(Δ)}(q)
= ∑_{Δ∈B(u,v)} q^{\frac{l(v)−l(u)−l(Δ)}{2}} (−1)^{|D(Δ)|−l(D(Δ))} ∑_{Γ∈E(T (D(Δ)),|D(Δ)|)}(−q)^{d_{+}(Γ)}
= ∑_{Δ∈B(u,v)} ∑_{Γ∈E(l(Δ)−D(Δ),l(Δ))} q^{\frac{l(v)−l(u)−l(Γ)}{2} +d_{+}(Γ)}(−1)^{Γ_{≥0}+d_{+}(Γ)},

and the result follows from (4) and part iii) of Theorem 2.7. □

8 Kazhdan-Lusztig polynomials and generalized hvectors

In this section we obtain, as an application of our main result, a generalization of Theorem 6.3 of [6] and a connection between Kazhdan-Lusztig polynomials and the so-called “Bayer-Billera relations” arising in the theory of convex polytopes and Eulerian posets.

The following definition is naturally suggested by Theorem 7.2. For u, v ∈ W, u < v, and i ∈ Z let

P_{u,v,l(v)−l(u)−i}(q) =^{def} ∑_{Δ∈B_{i}(u,v)} q^{\frac{l(v)−l(u)−i}{2}} Υ_{D(Δ)}(q),  (53)

where B_{i}(u, v) is the set of all Bruhat paths from u to v of length i. Note that P_{u,v,i}(q) = 0 unless i ∈ [0, l(v)−l(u)−1] and i ≡ 0 (mod 2) and that Theorem 7.2 can then be rewritten as

P_{u,v}(q) − q^{l(v)−l(u)}P_{u,v} (\frac{1}{q}) = ∑_{i≥0} P_{u,v,i}(q)  (54)

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

Proposition 8.1 Let u, v ∈ W, u < v, and i ∈ N be such that P_{u,v,i}(q) = 0. Then P_{u,v,i+2}(q) = 0.

Proof. We may clearly assume that i ≡ 0 (mod 2). From part ii) of Proposition 6.8 and from our definition (53) we have that

0 = [q^{\frac{i}{2}} ](P_{u,v,i}(q))
= b_{(1^{l(v)−l(u)−i})}(u, v) Υ_{(1^{l(v)−l(u)−i})}(0)
= b_{(1^{l(v)−l(u)−i})}(u, v)
= b_{l(v)−l(u)−i}(u, v)
= [q^{l(v)−l(u)−i}](R̃_{u,v}(q)),  (55)

where we have used Proposition 5.2 of [7], (11), and Proposition 2.6. This, by Proposition 6.1 of [6], implies that [q^{l(v)−l(u)−i−2}](R̃_{u,v}(q)) = 0 and this, by Proposition 2.4, implies that B_{l(v)−l(u)−i−2}(u, v) = ∅ which by (53) implies the result. □

The preceding proposition seems to suggest that P_{u,v,i+2}(q) is “smaller” than P_{u,v,i}(q), and implies that P_{u,v,0}(q) ≠ 0 for all u, v ∈ W, u < v. The next result shows that, in fact, P_{u,v,0}(q) is an important combinatorial invariant of the poset [u, v]. Given a chain C = (a_{0} < a_{1} < … < a_{i}) in W we define

α(C) =^{def} (l(a_{1}) − l(a_{0}), l(a_{2}) − l(a_{1}), …, l(a_{i}) − l(a_{i−1})).  (56)

Proposition 8.2 Let u, v ∈ W, u < v. Then

P_{u,v,0}(q) = (1 − q) f([u, v]^{∗}; q)  (57)

and

D_{\frac{l(v)−l(u)−1}{2}} (P_{u,v,0}(q)) = g([u, v]^{∗}; q).  (58)

Proof. Note first that by Proposition 5.1 of [7], our definition (53), and (51) we have that

P_{u,v,0}(q) = ∑_{β∈C_{l(v)−l(u)}}(−1)^{l(β)}c_{β}(u, v)Ψ_{β}(q)
= ∑_{β∈C_{l(v)−l(u)}}(−1)^{l(β)} α([u, v]; T (β^{∗}))Ψ_{β}(q)
= ∑_{C∈C(u,v)}(−1)^{l(C)} Ψ_{α(C)}(q)  (59)

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

We now prove the result by induction on l(v) − l(u). If l(v) − l(u) = 1 then

P_{u,v,0}(q) = Υ_{1}(q) = 1 − q

and the result holds by (2) and (3). Now let u < v be such that l(v) − l(u) ≥ 2. Then we have from (3), (59), and our induction hypothesis that

(q − 1)f([u, v]^{∗}; q) = (q − 1) ∑_{u<a≤v} g([a, v]^{∗}; q)(q − 1)^{l(v)−l(u)−1−(l(v)−l(a))}

= ∑_{u<a≤v} g([a, v]^{∗}; q)(q − 1)^{l(a)−l(u)}
= ∑_{u<a<v}(q − 1)^{l(a)−l(u)}D_{\frac{l(v)−l(a)−1}{2}} ( ∑_{C∈C(a,v)}(−1)^{l(C)}Ψ_{α(C)}(q)) + (q − 1)^{l(v)−l(u)}
= (q − 1)^{l(v)−l(u)} + ∑_{u<a<v}(q − 1)^{l(a)−l(u)} ∑_{C∈C(a,v)}(−1)^{l(C)}D_{\frac{l(v)−l(a)−1}{2}} (Ψ_{α(C)}(q))
= (q − 1)^{l(v)−l(u)} + ∑_{u<a<v} ∑_{C∈C(a,v)}(−1)^{l(C)}Ψ_{l(a)−l(u),α(C)}(q)
= (q − 1)^{l(v)−l(u)} + ∑_{{C′∈C(u,v): l(C′)≥2}}(−1)^{l(C′)−1} Ψ_{α(C′)}(q)
= − ∑_{C∈C(u,v)}(−1)^{l(C)}Ψ_{α(C)}(q),

which proves (57). Now (58) follows from (57) and (2). □

Theorem 8.3 Let u, v ∈ W, u < v, and j ∈ N, j ≡ 0 (mod 2). Then the following are equivalent:

i) P_{u,v}(q) = ∑_{i=0}^{j} D_{\frac{l(v)−l(u)−1}{2}} (P_{u,v,i}(q));

ii) [q^{l(v)−l(u)−j−2}](R̃_{u,v}(q)) = 0.

Proof. The result is trivial if l(v) − l(u) − j − 2 ≤ 0 so we may assume that j + 2 ≤ l(v) − l(u) − 1. Suppose that i) holds. Then, by (54),

∑_{i>j} D_{\frac{l(v)−l(u)−1}{2}} (P_{u,v,i}(q)) = 0.

Therefore

0 = [q^{\frac{j+2}{2}} ] (∑_{i>j} D_{\frac{l(v)−l(u)−1}{2}} (P_{u,v,i}(q)))
= ∑_{i>j}[q^{\frac{j+2}{2}} ](P_{u,v,i}(q))
= [q^{\frac{j+2}{2}} ](P_{u,v,j+2}(q))
= [q^{l(v)−l(u)−j−2}](R̃_{u,v}(q))

by (53) and (55). Conversely, if ii) holds then, by Proposition 2.4, B_{l(v)−l(u)−j−2}(u, v) = ∅ and hence P_{u,v,j+2}(q) = 0, and i) follows from (54) and Proposition 8.1. □

Note that, by (7) and Proposition 8.2, the preceding result reduces to Theorem 6.3 of [6] when j = 0.

We conclude this section by observing that the coefficients c_{α}(u, v) appearing in (50) satisfy the so-called “Bayer-Billera relations” arising in the theory of Eulerian posets and convex polytopes (see [2], Theorem 2.1).

Theorem 8.4 Let u, v ∈ W, u < v, α ∈ C, and t ∈ [l(α)] be such that α_{t} ≥ 2. Then

∑_{i=1}^{α_{t}−1}(−1)^{i−1} c_{α_{1},...,α_{t−1},i,α_{t}−i,α_{t+1},...,α_{r}}(u, v) = (1 + (−1)^{α_{t}})c_{α_{1},...,α_{r}}(u, v)  (60)

where r =^{def} l(α).

Proof. Since u < v, it follows from (7) and Proposition 7.8(c) of [17] that

∑_{a∈[u,v]} ε_{u}ε_{a}R̃_{u,a}(q^{\frac{1}{2}} − q^{− \frac{1}{2}} ) R̃_{a,v}(q^{\frac{1}{2}} − q^{− \frac{1}{2}} ) = 0,  (61)

for all q ∈ R\\{0\}. Since lim_{q→+∞} (q^{\frac{1}{2}} − q^{− \frac{1}{2}} ) = +∞ and q^{\frac{1}{2}} −q^{− \frac{1}{2}} is a continuos function for q > 0 we deduce from (61) that

∑_{a∈[u,v]} ε_{u}ε_{a}R̃_{u,a}(q)R̃_{a,v}(q) = 0  (62)

in Z[q]. Extracting the coefficient of q^{α_{1}} on both sides of (62) therefore yields that

0 = ∑_{i=0}^{α_{1}} ∑_{a∈[u,v]} ε_{u}ε_{a}[q^{i}](R̃_{u,a})[q^{α_{1}−i}](R̃_{a,v})
= [q^{α_{1}}](R̃_{u,v}) + ε_{u}ε_{v}[q^{α_{1}}](R̃_{u,v}) + ∑_{i=1}^{α_{1}−1} ∑_{a∈[u,v]}(−1)^{i}[q^{i}](R̃_{u,a})[q^{α_{1}−i}](R̃_{a,v})
= (1 + (−1)^{α_{1}})c_{α_{1}}(u, v) + ∑_{i=1}^{α_{1}−1}(−1)^{i}c_{i,α_{1}−i}(u, v)  (63)

by Proposition 2.6, where we have used the fact that [q^{i}](R̃_{u,a}) = 0 unless i ≡ l(a) − l(u) (mod 2). This proves the result if l(α) = 1. In general, it follows from (63) and Proposition 2.6 that

(1 + (−1)^{α_{t}})c_{α_{1},...,α_{r}}(u, v) = ∑_{u≤a≤b≤v} c_{α_{1},...,α_{t−1}}(u, a)(1 + (−1)^{α_{t}})c_{α_{t}}(a, b)c_{α_{t+1},...,α_{r}}(b, v)
= ∑_{u≤a≤b≤v} c_{α_{1},...,α_{t−1}}(u, a) ( ∑_{i=1}^{α_{t}−1}(−1)^{i−1}c_{i,α_{t}−i}(a, b)) c_{α_{t+1},...,α_{r}}(b, v)
= ∑_{i=1}^{α_{t}−1}(−1)^{i−1} ∑_{u≤a≤b≤v} c_{α_{1},...,α_{t−1}}(u, a)c_{i,α_{t}−i}(a, b)c_{α_{t+1},...,α_{r}}(b, v)
= ∑_{i=1}^{α_{t}−1}(−1)^{i−1}c_{α_{1},...,α_{t−1},i,α_{t}−i,α_{t+1},...,α_{r}}(u, v),

as desired. □

9 Inverse Kazhdan-Lusztig polynomials

In this section we briefly outline how to obtain analogues of the results in this work for the inverse Kazhdan-Lusztig polynomials. Recall (see, e.g., [17], §7.13, or [19], p.190) that these are the polynomials {P_{u,v}^{∗}(q)}_{u,v∈W} uniquely defined by the condition that

∑_{u≤a≤v}(−1)^{l(a)−l(u)} P_{u,a}(q) P_{a,v}^{∗}(q) = δ_{u,v}  (64)

for all u, v ∈ W, u ≤ v. The next (well known) result follows easily from (64), (8), and Theorem 2.7.

Theorem 9.1 For u, v ∈ W we have that:

i) P_{u,u}^{∗}(q) = 1;

ii) deg (P_{u,v}^{∗}(q)) ≤ ⌊\frac{1}{2}(l(v) − l(u) − 1)⌋ if u < v;

iii)

q^{l(v)−l(u)}P_{u,v}^{∗} (\frac{1}{q}) = ∑_{u≤a≤v} P_{u,a}^{∗}(q)R_{a,v}(q)

if u ≤ v. □

For any chain a_{0} < a_{1} < … < a_{i} in W we define a polynomial R_{a_{0},...,a_{i}}^{∗}(q) inductively as follows,

R_{a_{0},...,a_{i}}^{∗}(q) =^{def} D_{\frac{d−1}{2}} (R_{a_{0},...,a_{i−1}}^{∗}(q)) R_{a_{i−1},a_{i}}(q)  (65)

(where d =^{def} l(a_{i−1}) − l(a_{0})) if i ≥ 2, and

R_{a_{0},...,a_{i}}^{∗}(q) = R_{a_{0},a_{1}}(q),  (66)

if i = 1. We call R_{a_{0},...,a_{i}}^{∗}(q) the dual R-polynomial of the chain a_{0} < a_{1} < … < a_{i}. Note that if W is finite then we have the following result, whose proof follows easily from (13), (14), (65), (66), and Proposition 7.6 of [17].

Proposition 9.2 Let (W, S) be a finite Coxeter system and a_{0} < a_{1} < … < a_{i} be a chain in W. Then

R_{a_{0},...,a_{i}}^{∗}(q) = R_{ω_{0}a_{i},...,ω_{0}a_{0}}(q),

where ω_{0} denotes the longest element of W. □

The reader can check that all of the results in sections 3, 4, 5, 7, and 8 have analogues for the inverse Kazhdan-Lusztig polynomials and for the dual R-polynomials of a chain. For example, the analogues of Theorems 4.2, 5.1, 7.2, and 7.3 are the following.

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

P_{u,v}^{∗}(q) − q^{l(v)−l(u)} P_{u,v}^{∗} (\frac{1}{q}) = ∑_{C∈C(u,v)}(−1)^{l(C)}R_{C}^{∗}(q).□

Theorem 9.4 Let u, v ∈ W, u < v, and k ∈ P. Then

[q^{k}](P_{u,v}^{∗}) = ∑_{α∈C_{k}}(−1)^{l(α)} ∑_{(a_{0},...,a_{2l+1})∈M_{α}^{∗}(u,v)} ∏_{j=1}^{l(α)}[q^{α_{j}}](R_{a_{2j−1},a_{2j}})

where M_{α}^{∗}(u, v) is the set of all multichains u = a_{0} ≤ a_{1} ≤ … ≤ a_{2l+1} = v from u to v of length 2l(α) + 1 such that \frac{1}{2}(l(a_{2i}) − l(u) − 1) ≥ α_{1} + … + α_{i} and a_{2i−1} < a_{2i} for i = 1, …, l. □

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

P_{u,v}^{∗}(q) − q^{l(v)−l(u)} P_{u,v}^{∗} (\frac{1}{q}) = ∑_{Δ∈B(u,v)} q^{\frac{l(v)−l(u)−l(Δ)}{2}} Υ_{D(Δ)^{∗}}(q).□

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

P_{u,v}^{∗}(q) = ∑_{(Γ,Δ)}(−1)^{Γ_{≥0}+d_{+}(Γ)}q^{\frac{l(v)−l(u)+Γ(l(Γ))}{2}}

where the sum is over all pairs (Γ, Δ) such that Γ is a lattice path, Δ is a Bruhat path from u to v, l(Γ) = l(Δ), N(Γ) = D(Δ), and Γ(l(Γ)) < 0. □

For u, v ∈ W, u < v, and i ∈ Z let

P_{u,v,l(v)−l(u)−i}^{∗}(q) =^{def} ∑_{Δ∈B_{i}(u,v)} q^{\frac{l(v)−l(u)−i}{2}} Υ_{D(Δ)^{∗}}(q).

Then the analogues of Proposition 8.2 and of Theorem 8.3 are the following.

Proposition 9.7 Let u, v ∈ W, u < v. Then

P_{u,v,0}^{∗}(q) = (1 − q) f([u, v]; q),

and

D_{\frac{l(v)−l(u)−1}{2}} (P_{u,v,0}^{∗}(q)) = g([u, v]; q).□

Theorem 9.8 Let u, v ∈ W, u < v, and j ∈ N, j ≡ 0 (mod 2). Then the following are equivalent:

i) P_{u,v}^{∗}(q) = ∑_{i=0}^{j} D_{\frac{l(v)−l(u)−1}{2}} (P_{u,v,i}^{∗}(q));

ii) [q^{l(v)−l(u)−j−2}](R̃_{u,v}(q)) = 0. □

Acknowledgements. I would like to thank Mark Goresky and Robert MacPherson for many useful discussions and conversations.

References

[1] D. André, Solution directe du probléme résolu par M. Bertrand, C. R. Acad. Sci. Paris 105 (1887), 436-437.

[2] M. M. Bayer, L. J. Billera, Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets, Invent. Math., 79 (1985), 143-157.

[3] A. Björner, A. Garsia, and R. Stanley, An introduction to Cohen-Macaulay partially ordered sets, in Ordered Sets (I. Rival, Editor), Reidal, Dordrecht/Boston, 1982, 583-615.

[4] A. Björner, M. Wachs, Bruhat order of Coxeter groups and shellability, Adv. in Math. 43 (1982), 87-100.

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

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

[7] F. Brenti, Combinatorial expansions of Kazhdan-Lusztig polynomials, J. London Math. Soc., to appear.

[8] F. Brenti, Kazhdan-Lusztig and R-polynomials from a combinatorial point of view, Discrete Math., to appear.

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

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

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

[12] M. Dyer, Hecke algebras and reflections in Coxeter groups, Ph. D. Thesis, University of Sydney, 1987.

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

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

[15] W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, Wiley, New York, 1950.

[16] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley-Interscience, New York, 1983.

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

[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] R. P. Stanley, Enumerative Combinatorics , vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

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

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

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

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

Dipartimento di Matematica Universitá di Roma “Tor Vergata” Via della Ricerca Scientifica I-00133 Roma, Italy