QUASISYMMETRIC FUNCTIONS AND KAZHDAN-LUSZTIG POLYNOMIALS

LOUIS J. BILLERA AND FRANCESCO BRENTI

Abstract. We associate a quasisymmetric function to any Bruhat interval in a general Coxeter group. This association can be seen to be a morphism of Hopf algebras to the subalgebra of all peak functions, leading to an extension of the cd-index of convex polytopes. We show how the Kazhdan-Lusztig polynomial of the Bruhat interval can be expressed in terms of this complete cd-index and otherwise explicit combinatorially defined polynomials. In particular, we obtain the simplest closed formula for the Kazhdan-Lusztig polynomials that holds in complete generality.

Contents

1. Introduction 1 2. The R-quasisymmetric function of a Bruhat interval and the

complete cd-index 9 3. Kazhdan-Lusztig polynomials and the complete cd-index 15 4. Kazhdan-Lusztig polynomials and ballot polynomials 18 5. Other representations of the complete cd-index 22 6. A sign conjecture for the complete cd-index 24 References 25

1. Introduction

The Kazhdan-Lusztig polynomials of a Coxeter group are of fundamental importance in representation theory and in the geometry and topology of Schubert varieties. Defined by means of two separate recursions, they have proved difficult to unravel in any straightforward manner. Here, we reduce their computation to the computation of another invariant of Coxeter groups. This new invariant, a quasisymmetric function that can be

2000 Mathematics Subject Classification. Primary 20F55, 05E99; Secondary 05E15. Key words and phrases. Coxeter group, Kazhdan-Lusztig polynomial, cd-index, qua-

sisymmetric function.

The first author was supported in part by NSF grants DMS-0100323 and DMS-0555268. The second author was partially supported by EU grant CHRT-CT-2001-00272. This work was begun while both authors enjoyed the hospitality of the Mittag-Leffler Institute, Djursholm, Sweden.

encoded into a noncommutative polynomial in two variables that we call the complete cd-index, has interesting algebraic and combinatorial properties. We express the Kazhdan-Lusztig polynomial of any Bruhat interval in terms of its complete cd-index and otherwise explicit combinatorially defined polynomials. In particular, we obtain the simplest closed formula for the Kazhdan-Lusztig polynomials that holds in complete generality.

The complete cd-index is defined by means of a quasisysymmetric function F̃(u, v) associated to every Bruhat interval [u, v] in a Coxeter group W. The association [u, v] ↦ F̃(u, v) can be viewed as a morphism of Hopf algebras, suggesting the possibility of a filtered version of the theory of combinatorial Hopf algebras [1], which predicts the existence of graded maps to the quasisymmetric functions in general combinatorial settings.

The theory of Kazhdan-Lusztig polynomials of Weyl groups is analogous to that of the g-polynomials of rational convex polytopes in that they both compute the local intersection cohomology of certain varieties (Schubert and toric, respectively) associated to these objects [26], [29]. Also, the recursions that define them in a general Coxeter group (respectively, Eulerian partially ordered set) have the same form. The g-polynomial of an Eulerian partially ordered set is known to depend only on the number of chains of certain types. These flag numbers are most succintly represented by the cd-index. On the other hand, for the Kazhdan-Lusztig polynomials it is not even clear that there can be a completely combinatorial description (see, e.g., [7, §5.6]), so there is no straightforward way to generalize this combinatorial description of the g-polynomials to the Kazhdan-Lusztig polynomials. Yet, the quasisymmetric functions F̃(u, v) do seem to capture much of the spirit of the combinatorial setting of the g-polynomials, without themselves being obviously combinatorial.

In the remainder of this section we give the necessary background in Coxeter groups and Kazhdan-Lusztig polynomials and in the use of quasisymmetric functions in poset enumeration. In Section 2 we introduce the R-quasisymmetric function of a Bruhat interval, define from this the complete cd-index of the interval and give some of its algebraic properties. Section 3 gives an expression for the Kazhdan-Lusztig polynomials in terms of the complete cd-index and certain lattice path enumerators. Using this expression, we give in Section 4 the representation of the Kazhdan-Lusztig polynomials in terms of an explicit polynomial basis defined by means of the ballot polynomials. The coefficients of this representation are given as linear forms in the complete cd-index. In Section 5 we give a formula for computing the complete cd-index of any Bruhat interval in terms of explicit combinatorial quantities associated to the Bruhat interval. Finally, in Section 6 we conjecture nonnegativity of the complete cd-index and show that one consequence of this conjecture holds in the case of finite Coxeter and affine Weyl groups.

1.1. Coxeter groups and Kazhdan-Lusztig polynomials. We follow [23] for general Coxeter groups notation and terminology. In particular, given a Coxeter system (W, S) and u ∈ W we denote by l(u) the length of u in W, with respect to S. 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. We will always assume that W is partially ordered by Bruhat order. Recall (see, e.g., [23, §5.9]) that this means that x ≤ y if and only if there exist r ∈ ℕ 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. 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. It is well known (see, e.g., [7], Corollary 2.7.11) that intervals of W (and their duals) are Eulerian posets.

Recall (see [23], §8.6, or [17]) 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).

Let A ⊆ T and W′ be the subgroup of W generated by A. Following [23, §8.2], we call W′ a reflection subgroup of W. It is then known (see, e.g., [23], 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 [18] 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 [18, §2] (see also [7, §5.2]). Throughout this work we will always assume that we have fixed (once and for all) a reflection ordering <_{T} of T.

Recall that a composition of a positive integer n is a finite sequence of positive integers α = α_{1} ⋯ α_{k} such that ∑_{i} α_{i} = n. In this case we write α ⊧ n and we define l(α) = k, |α| = n, and α^{∗} = α_{k} ⋯ α_{1}. (There should be no confusion with our using the same notation l(·) for the lengths of compositions and elements of W.) Given two compositions α_{1} ⋯ α_{s}, β_{1} ⋯ β_{t} of 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}. We denote by C the set of all finite sequences of positive integers (i.e., the set of all compositions).

Given a path Δ = (a_{0}, a_{1}, …, a_{r}) in B(W, S) from a_{0} to a_{r}, 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(Δ) of r corresponding to D(Δ) under the usual bijection between compositions and sets β_{1}β_{2} ⋯ β_{k} ↦ {β_{1}, β_{1} + β_{2}, …, β_{1} + ⋯ + β_{k−1}}. We will denote the inverse of this bijection by co(·).

We denote by H(W) the Hecke algebra associated to W. Recall (see, e.g., [23, Chap. 7]) that this is the free ℤ[q, q^{−1}]-module having the set {T_{w} : w ∈ W } as a basis and multiplication such that

(1.1)  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}

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

Proposition 1.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) ∈ ℤ[q].

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

Theorem 1.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}(q), & if l(us) > l(u). \end{matrix}

Note that the preceding theorem can be used to inductively compute the R-polynomials. Theorem 1.2 has also the following simple but important consequence (see, for example, [7, Proposition 5.3.1]).

Proposition 1.3. Let u, v ∈ W. Then there exists a (necessarily unique) polynomial R̃_{u,v}(q) ∈ ℕ[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}} ) .

Combinatorial interpretations of the coefficients of R̃_{u,v}(q) have been given by V. Deodhar [16] and by M. Dyer [18] (see [7, Theorem 5.3.7] and [7, Theorem 5.3.4]).

Given u, v ∈ W, and k ∈ ℕ, 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, following [9],

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

and

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

Note that these definitions imply that

(1.4)  c_{α}(u, v) = ∑_{{β⊧n:β⪰α}} b_{β}(u, v)

for all u, v ∈ W and α ⊧ n (n ∈ ℙ).

The following result appears as [9, Proposition 4.4]. Given a polynomial P (q), and i ∈ ℤ, we denote by [q^{i}](P) the coefficient of q^{i} in P (q).

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

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

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

Proposition 1.4 shows, in particular, that c_{α}(u, v) (and hence b_{α}(u, v)) are independent of the total reflection ordering <_{T} used to define them.

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 [30, Corollary 6.7] and [30, Example 6.9]) and a proof can be found, e.g., in [23, §7.9–11] or [25, §2.2].

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

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

2. P_{u,u}(q) = 1;

3. deg(P_{u,v}(q)) < \frac{1}{2} (l(v) − l(u)), if u < v; 4.

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

if u ≤ v.

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

For j ∈ ℚ we define an operator D_{j} : ℝ[q] → ℝ[q] by letting

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

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

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

if l(α) ≥ 2, and

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

if l(α) = 1. Here α^{−} = α_{2} ⋯ α_{k} when α = α_{1} ⋯ α_{k}. For n ∈ ℙ and β ⊧ n we then let

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

We then have the following result, whose proof can be found in [7, Theorem 5.5.7].

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

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

Let (W_{1}, S_{1}) and (W_{2}, S_{2}) be two Coxeter systems. It is clear that the direct product W = W_{1} × W_{2} is again a Coxeter group with respect to the generating set S = S_{1} ⊔ S_{2} (disjoint union), having Dynkin diagram the disjoint union of the diagrams of (W_{1}, S_{1}) and (W_{2}, S_{2}). It then follows immediately from the subword property of Bruhat order (see, e.g., [7, Theorem 2.2.2]) that W, as a poset under Bruhat order, is isomorphic to the direct product of W_{1} and W_{2} as posets under Bruhat order. Thus (u_{1}, u_{2}) ≤ (v_{1}, v_{2}) in W if and only if u_{1} ≤ v_{1} in W_{1} and u_{2} ≤ v_{2} in W_{2}. Thus Theorems 1.2 and 1.5 imply the following multiplicative formulas. We include a proof for lack of an adequate reference.

Proposition 1.7. Let u_{1}, v_{1} ∈ W_{1} and u_{2}, v_{2} ∈ W_{2}. Then

(1.5)  R_{(u_{1},u_{2}),(v_{1},v_{2})} = R_{u_{1},v_{1}} · R_{u_{2},v_{2}}, and
(1.6)  P_{(u_{1},u_{2}),(v_{1},v_{2})} = P_{u_{1},v_{1}} · P_{u_{2},v_{2}}.

Proof. First note that by the comments preceding this proposition, (1.5) and (1.6) hold if (u_{1}, u_{2}) ≰ (v_{1}, v_{2}), so assume that (u_{1}, u_{2}) ≤ (v_{1}, v_{2}). We first prove (1.5) by induction on l(v_{2}).If v_{2} = e then u_{2} = e and (1.5) follows from Theorem 1.2 and the fact that D((u, e)) = {(s, e) : s ∈ D(u)} for all u ∈ W_{1}. (Note that l_{W} ((u_{1}, u_{2}), (v_{1}, v_{2})) = l_{W_{1}}(u_{1}, v_{1}) + l_{W_{2}}(u_{2}, v_{2}).) If v_{2} > e and s ∈ D(v_{2}), then (e, s) ∈ D((v_{1}, v_{2})) and therefore, by Theorem 1.2 and our induction hypothesis,

R_{(u_{1},u_{2}),(v_{1},v_{2})} = q R_{(u_{1},u_{2}s),(v_{1},v_{2}s)} + (q − 1) R_{(u_{1},u_{2}),(v_{1},v_{2}s)}
= R_{u_{1},v_{1}} (q R_{u_{2}s,v_{2}s} + (q − 1) R_{u_{2},v_{2}s})
= R_{u_{1},v_{1}} · R_{u_{2},v_{2}}

if s ∉ D(u_{2}) (so (e, s) ∉ D((u_{1}, u_{2}))), while

R_{(u_{1},u_{2}),(v_{1},v_{2})} = R_{(u_{1},u_{2}s),(v_{1},v_{2}s)} = R_{u_{1},v_{1}} R_{u_{2}s,v_{2}s}
= R_{u_{1},v_{1}}R_{u_{2},v_{2}}

if s ∈ D(u_{2}), as desired.

We conclude by proving (1.6) by induction on l_{W} ((u_{1}, u_{2}), (v_{1}, v_{2})). The result is clear if l_{W} ((u_{1}, u_{2}), (v_{1}, v_{2})) = 0. If l_{W} ((u_{1}, u_{2}), (v_{1}, v_{2})) > 0 then by Theorem 1.5, our induction hypothesis, (1.5) and the comments preceding this proposition, we have

q^{l((u_{1},u_{2}),(v_{1},v_{2}))} P_{(u_{1},u_{2}),(v_{1},v_{2})} (\frac{1}{q}) − P_{(u_{1},u_{2}),(v_{1},v_{2})}(q)

= ∑_{(u_{1},u_{2})<(x_{1},x_{2})≤(v_{1},v_{2})} R_{(u_{1},u_{2}),(x_{1},x_{2})}(q) P_{(x_{1},x_{2}),(v_{1},v_{2})}(q)

= ∑_{u_{1}≤x_{1}≤v_{1}} R_{u_{1},x_{1}}(q) P_{x_{1},v_{1}}(q) ∑_{u_{2}≤x_{2}≤v_{2}} R_{u_{2},x_{2}}(q) P_{x_{2},v_{2}}(q)

− P_{u_{1},v_{1}}(q) P_{u_{2},v_{2}}(q)

= q^{l(u_{1},v_{1})} P_{u_{1},v_{1}} (\frac{1}{q}) q^{l(u_{2},v_{2})} P_{u_{2},v_{2}} (\frac{1}{q}) − P_{u_{1},v_{1}}(q) P_{u_{2},v_{2}}(q),

and (1.6) follows. □

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

1.2. Quasisymmetric functions and poset enumeration. A quasisymmetric function is a formal power series in countably many variables that has bounded degree and whose coefficients are invariant under shifts of the variables that respect their order. We assume here that the reader is familiar with the basics of the theory of quasisymmetric functions, for example, as described in [32, §7.19]. We denote by QSym ⊂ ℚ[[x_{1}, x_{2}, …]] the algebra of all quasisymmetric functions (with rational coefficients). QSym is a graded algebra with the usual grading of power series; we denote by Q_{i} the i^{th} homogeneous part of QSym and so

QSym = Q_{0} ⊕ Q_{1} ⊕ · · · .

In particular, we will make use of the monomial basis {M_{α}}_{α∈C} and the fundamental basis {L_{α}}_{α∈C} for QSym, where for a composition α = α_{1}α_{2} ⋯ α_{k}, k > 0, α_{i} > 0,

M_{α} = ∑_{i_{1}<i_{2}<···<i_{k}} x_{i_{1}}^{α_{1}}x_{i_{2}}^{α_{2}} ⋯ x_{i_{k}}^{α_{k}}

and

(1.7)  L_{β} = ∑_{{α⊧|β|: α⪯β}} M_{α}.

We include as well the empty composition α = 0 (the case k = 0); here we set M_{0} = L_{0} = 1. Note that the degree of M_{α} and L_{α} is |α|. Occasionally, it will be useful to index these bases by subsets of [n−1] instead of compositions of n, using the standard bijection between compositions and subsets already mentioned. In this case, we write L_{T}^{(n)} to indicate its degree.

An interesting subalgebra of QSym is the subspace Π of peak functions, which can be defined as follows. Let c and d be noncommuting indeterminates of degree 1 and 2, respectively. We let w be an arbitrary word in the letters c and d. If

w = c^{n_{1}}dc^{n_{2}}d ⋯ c^{n_{k}}dc^{n_{0}},

(n_{0}, …, n_{k} ≥ 0) then let m_{j} = deg(c^{n_{1}}dc^{n_{2}}d ⋯ c^{n_{j}}d), j = 1, …, k. Define I^{w} to be the family consisting of the k 2-element subsets {m_{j} − 1, m_{j}}, j = 1, …, k, and

b[I^{w}] =^{def} {T ⊆ [n] : S ∩ T ≠ ∅, for all S ∈ I^{w}},

where n=deg(w). Finally, define

(1.8)  Θ_{w} =^{def} ∑_{T ∈B[I^{w}]} L_{T}^{(n+1)},

where B[I^{w}] =^{def} \{T ⊆ [n] : T, \overline{T} ∈ b[I^{w}]\}. Note that deg(Θ_{w}) = deg(w) + 1. Here, if w = 1, the empty cd-word, then Θ_{1} = L_{∅}^{(1)} = L_{1}. We can define Π to be the linear subspace of QSym spanned by 1 and all the Θ_{w}, as w ranges over all cd words. Again, Π is a graded algebra with the inherited grading; we denote by Π_{i} =^{def} Π ∩ Q_{i} its i^{th} homogeneous part. See [6] and [33] for details. There the basis element Θ_{w} in (1.8) is replaced by Θ_{w}^{(st)} = 2^{|w|_{d}+1}Θ_{w}, where we denote the degree of w by |w| and extend this notation to let |w|_{d} denote the number of d’s in w.

We summarize here the basics of the use of quasisymmetric functions in the theory of flag f-vectors of graded posets and, in particular, Eulerian posets. For a finite graded poset Q, with rank function ρ(·), we define the formal power series

(1.9)  F (Q) =^{def} ∑_{ˆ0=t_{0}≤···≤t_{k−1}<t_{k}=ˆ1} x_{1}^{ρ(t_{0},t_{1})}x_{2}^{ρ(t_{1},t_{2})} ⋯ x_{k}^{ρ(t_{k−1},t_{k})},

where the sum is over all multichains in Q whose last two elements are different and ρ(x, y) = ρ(y) − ρ(x). For general properties of F (Q), see [19] and [6]. In particular, we have the following

Proposition 1.8. For a graded poset Q, 1. F (Q) ∈ QSym and is homogeneous of degree ρ(Q),

2. F (Q_{1} × Q_{2}) = F (Q_{1})F (Q_{2}),

3. F (Q) = ∑_{α} f_{α}M_{α} = ∑_{α} h_{α}L_{α}, where f_{α} and h_{α} are the flag f and flag h-vectors, respectively, of Q, and

4. If Q is Eulerian, then F (Q) ∈ Π; in fact F (Q) = ∑_{w}[w]_{Q} Θ_{w}, where [w]_{Q} denotes the coefficient of w in the cd-index of Q.

The last statement of Proposition 1.8, which follows from Proposition 2.2 and Theorem 2.1 of [6], can be used as the definition of the cd-index for an Eulerian poset Q. Formally, the cd-index is the homogeneous noncommutative polynomial, ψ_{Q} = ψ_{Q}(c, d) = ∑_{w}[w]_{Q} w in c and d, where the sum is over all cd-words of degree ρ(Q) − 1; see [4].

2. The R-quasisymmetric function of a Bruhat interval and the complete cd-index

Since a Bruhat interval [u, v] is an Eulerian poset, it has a homogeneous cd-index ψ_{u,v} =^{def} ψ_{[u,v]} and quasisymmetric function F (u, v) =^{def} F ([u, v]) defined as above. The polynomial ψ_{u,v} has been studied explicitly by Reading [28]. In this section, we extend the definition of the cd-index for Bruhat intervals to get a nonhomogeneous polynomial, whose coefficients we later use to give a simple expression for Kazhdan-Lusztig polynomials.

2.1. The R-quasisymmetric function of a Bruhat interval. We define a quasisymmetric function, analogous to the power series (1.9), making use of the polynomials R̃_{u,v} defined in Proposition 1.3.

Given u, v ∈ W, u ≤ v, we define the R-quasisymmetric function F̃(u, v) by

(2.1)  F̃(u, v) =^{def} ∑_{u=t_{0}≤···≤t_{k−1}<t_{k}=v} R̃_{t_{0}t_{1}}(x_{1})R̃_{t_{1}t_{2}}(x_{2}) ⋯ R̃_{t_{k−1}t_{k}}(x_{k}),

where, again, the sum is over all multichains in [u, v] whose last two elements are different. Note that, by Proposition 1.3 and the comments following Proposition 1.1, the leading term of each summand on the right hand side of (2.1) is the corresponding monomial on the right hand side of (1.9).

An alternative description of F̃(u, v) in terms of chains is as follows. We omit the straightforward verification.

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

F̃(u, v) = ∑_{k≥1} ∑_{u=t_{0}<t_{1}<···<t_{k}=v} ∑_{1≤i_{1}<i_{2}<···<i_{k}} ∏_{j=1}^{k} R̃_{t_{j−1},t_{j}}(x_{i_{j}}).

We will see that F̃(u, v) shares many of the properties of F (Q) and will serve to define an extension of the cd-index for Bruhat intervals. In particular, we have the following

Theorem 2.2. For any u, v ∈ W, u ≤ v,

1. F̃(u, v) = ∑_{α} c_{α}(u, v) M_{α} = ∑_{α} b_{α}(u, v) L_{α}, and
2. F̃(u, v) ∈ Π, in fact
F̃(u, v) ∈ Π_{l(u,v)} ⊕ Π_{l(u,v)−2} ⊕ Π_{l(u,v)−4} ⊕ · · · .

Proof. To prove part 1, we have, using Proposition 1.4,

F̃(u, v) = ∑_{u=t_{0}≤···≤t_{k−1}<t_{k}=v} R̃_{t_{0}t_{1}}(x_{1})R̃_{t_{1}t_{2}}(x_{2}) ⋯ R̃_{t_{k−1}t_{k}}(x_{k})

= ∑_{u=t_{0}≤···≤t_{k−1}<t_{k}=v} ∏_{j=1}^{k} ∑_{α_{j}≥0} (x_{j}^{α_{j}} [q^{α_{j}}](R̃_{t_{j−1},t_{j}}))

= ∑_{u=t_{0}≤···≤t_{k−1}<t_{k}=v} ∑_{α∈ℕ^{k}} ∏_{j=1}^{k} (x_{j}^{α_{j}} [q^{α_{j}}](R̃_{t_{j−1},t_{j}}))

= ∑_{k≥1} ∑_{\{α∈ℕ^{k}:α_{k}>0\}}x_{1}^{α_{1}} ⋯ x_{k}^{α_{k}} ∑_{u=t_{0}≤···≤t_{k−1}<t_{k}=v} ∏_{j=1}^{k}[q^{α_{j}}] \binom{}{R_{t_{j−1},t_{j}}}

= ∑_{k≥1} ∑_{\{α∈ℕ^{k}:α_{k}>0\}}x_{1}^{α_{1}} ⋯ x_{k}^{α_{k}} ∑_{u=t_{0}<···<t_{l(α^{+})}=v} ∏_{j=1}^{l(α^{+})}[q^{α_{j}^{+}}] \binom{}{R_{t_{j−1},t_{j}}}

= ∑_{k≥1} ∑_{{α∈ℕ^{k}:α_{k}>0}}x_{1}^{α_{1}} ⋯ x_{k}^{α_{k}} c_{α^{+}}(u, v)

= ∑_{β∈C} c_{β}(u, v) M_{β},

where we have used the facts that [q^{0}](R̃_{x,y}) = δ_{x,y} for all x, y ∈ W, x ≤ y, and R̃_{x,x} = 1. Here α^{+} is the composition obtained by taking only positive entries of α in order. The second equality in part 1 follows from (1.4) and (1.7).

Part 2 now follows easily from [10, Theorem 8.4] and [6, Proposition 1.3]. The last assertion follows since the c_{α}(u, v) count certain directed paths from u to v of length |α| in the Bruhat graph B(W, S), and all of these must have length ≡ l(u, v)(mod 2). □

As a consequence of Theorem 2.2, we can express any F̃(u, v) in terms of the basis Θ_{w} for Π.

Corollary 2.3. For any u, v ∈ W, u ≤ v, we can write

F̃(u, v) = ∑_{w}[w]_{u,v} Θ_{w}.

Note that, by Theorem 2.2, the coefficients [w]_{u,v} can be nonzero only when deg(w) = l(u, v) − 1, l(u, v) − 3, …. We find it convenient to define, for any u, v ∈ W,

ψ̃_{u,v} = ψ̃_{u,v}(c, d) = ∑_{w}[w]_{u,v} w,

a nonhomogeneous, noncommutative polynomial in the variables c and d that will be called the complete cd-index of the Bruhat interval [u, v].

Example 2.4. Let W = S_{4}, u = 1234 and v = 4231. Choose the reflection ordering (1, 2) < (1, 3) < (1, 4) < (2, 3) < (2, 4) < (3, 4). Then there are 73 Bruhat paths from u to v and from (1.3) one can compute that

b_{5}(u, v) = b_{1,1,1,1,1}(u, v) = b_{1}(u, v) = 1, b_{3}(u, v) = b_{2,1}(u, v) = b_{1,2}(u, v) = b_{1,1,1}(u, v) = b_{1,4}(u, v) = b_{2,1,1,1}(u, v) = 2, b_{4,1}(u, v) = b_{3,1,1}(u, v) = b_{1,1,3}(u, v) = b_{1,1,1,2}(u, v) = 3, b_{2,3}(u, v) = b_{1,2,1,1}(u, v) = 4, b_{3,2}(u, v) = b_{1,1,2,1}(u, v) = 5, b_{1,3,1}(u, v) = b_{2,1,2}(u, v) = 6, and b_{2,2,1}(u, v) = b_{1,2,2}(u, v) = 8,

so by Theorem 2.2

F̃(1234, 4231) = L_{5} + 3L_{4,1} + 5L_{3,2} + 4L_{2,3} + 2L_{1,4}

+ 3L_{3,1,1} + 6L_{1,3,1} + 3L_{1,1,3} + 8L_{2,2,1} + 6L_{2,1,2} + 8L_{1,2,2}

+ 2L_{2,1,1,1} + 4L_{1,2,1,1} + 5L_{1,1,2,1} + 3L_{1,1,1,2} + L_{1,1,1,1,1}
+ 2L_{3} + 2L_{2,1} + 2L_{1,2} + 2L_{1,1,1} + L_{1}
= Θ_{c^{4}} + Θ_{dc^{2}} + 2Θ_{cdc} + 2Θ_{c^{2}d} + 2Θ_{d^{2}} + 2Θ_{c^{2}} + Θ_{1},

and so [dc^{2}]_{1234,4231} = 1, [cdc]_{1234,4231} = 2, etc. Thus we have

ψ̃_{1234,4231} = c^{4} + dc^{2} + 2cdc + 2c^{2}d + 2d^{2} + 2c^{2} + 1.

There is at least one case where (1.9) and (2.1) define the same element of QSym. For u, v ∈ W and i ∈ ℕ let F̃_{i}(u, v) be the homogeneous component of F̃(u, v) of degree i (so F̃_{i}(u, v) = 0 unless i ≡ l(u, v) (mod 2)).

Proposition 2.5. Let u, v ∈ W, u ≤ v. Then F̃_{l(u,v)}(u, v) = F (u, v) and so [w](ψ̃_{u,v}) = [w](ψ_{u,v}) when deg(w) = l(u, v) − 1. In particular, F̃(u, v) = F (u, v) and ψ̃_{u,v} = ψ_{u,v} whenever the Bruhat interval [u, v] is a lattice.

Proof. The first assertion follows immediately from (1.9), (2.1) and the comments following Proposition 1.1. The second one follows from (1.9), (2.1) and [8, Corollary 6.5]. □

2.2. Algebraic properties of F̃. We investigate some of the algebraic properties of the map [u, v] ↦ F̃(u, v). In [19, Proposition 4.4], the map on posets, P ↦ F (P), is shown to be a morphism of Hopf algebras. The same holds for the map defined by F̃. To see this, note that the coproduct on posets used in [19] restricts to one on Bruhat intervals:

(2.2)  Δ([u, v]) = ∑_{w∈[u,v]}[u, w] ⊗ [w, v].

On QSym, we take the usual coproduct defined by

(2.3)  Δ(M_{γ}) = ∑_{α·β=γ} M_{α} ⊗ M_{β},

where α · β denotes concatenation of compositions.

We begin with an analog of Proposition 1.8.2, which shows the map to be multiplicative with respect to direct product.

Proposition 2.6. Let W_{1}, W_{2} be two Coxeter groups, W_{1} × W_{2} be their direct product, and u_{1}, v_{1} ∈ W_{1}, u_{2}, v_{2} ∈ W_{2}. Then

F̃((u_{1}, u_{2}), (v_{1}, v_{2})) = F̃(u_{1}, v_{1}) F̃(u_{2}, v_{2}).

Proof. It follows from Proposition 1.7 and Proposition 1.3 that for u_{1} ≤ z_{1} ≤ z_{2} ≤ v_{1} and u_{2} ≤ w_{1} ≤ w_{2} ≤ v_{2}

(2.4)  R̃_{(z_{1},w_{1}),(z_{2},w_{2})} = R̃_{z_{1},z_{2}} R̃_{w_{1},w_{2}}.

The proof then follows by the same limiting argument used to prove multiplicativity of the map F [19, Proposition 4.4], with the change that we now use the maps κ̃_{i}(u, v) = R̃_{u,v}(x_{i}), which are multiplicative by (2.4). We omit the details. □

That F̃ is a coalgebra map is proved next.

Proposition 2.7. The map F̃ is a map of coalgebras, that is, for each u, v ∈ W, u ≤ v

((F̃ ⊗ F̃) ∘ Δ) ([u, v]) = Δ (F̃(u, v)) .

Proof. By Theorem 2.2.1 and (2.3), we can write

Δ (F̃(u, v)) = ∑_{γ} c_{γ}(u, v) ∑_{α·β=γ} M_{α} ⊗ M_{β}

= ∑_{α} ∑_{β} c_{α·β}(u, v) M_{α} ⊗ M_{β}.

Now, as an extension of [2, Proposition 5.5.4] (and with virtually the same proof), we have c_{α·β}(u, v) = ∑_{w∈[u,v]} c_{α}(u, w) c_{β}(w, v). Thus

Δ (F̃(u, v)) = ∑_{w∈[u,v]} ∑_{α} ∑_{β} c_{α}(u, w) c_{β}(w, v)M_{α} ⊗ M_{β}

= ∑_{w∈[u,v]} F̃(u, w) ⊗ F̃(w, v),

completing the proof. □

Remark 2.8. Formally, let C be the graded vector space, over a field k, spanned by 1 ∈ k and all isomorphism classes of Bruhat intervals [u, v], u < v, in all Coxeter groups, where the elements of k have degree 0 and deg([u, v]) = l(v) − l(u), and where [u, v] ≅ [w, z] if there exists a directed graph isomorphism f : [u, v] → [w, z] such that D(Δ) = D(f(Δ)) for all Bruhat paths Δ in [u, v]. C has multiplication defined via Cartesian product [u_{1}, v_{1}] × [u_{2}, v_{2}] = [(u_{1}, u_{2}), (v_{1}, v_{2})], and comultiplication defined by Δ([u, v]) = ∑_{w∈[u,v]}[u, w] ⊗ [w, v], where [u, u] is defined to be 1 ∈ k. We define a counit ϵ on C by ϵ([u, v]) = δ_{0,l(v)−l(u)} for u ≤ v. By [19, Lemma 2.1], this defines C as a graded Hopf algebra. Propositions 2.6 and 2.7 show that the linear map F̃ : C → QSym induced by F̃ is a morphism of graded Hopf algebras. (Compare [19, Proposition 4.4]; note that our F̃ should not be confused with the similarly named function in [19].)

2.3. Properties of ψ̃_{u,v}. Let a and b be two noncommuting indeterminates and ℤ⟨a, b⟩ be the ring of noncommutative polynomials in a and b with coefficients in ℤ. Given n ∈ ℙ and a subset T ⊆ [n] let m_{T}^{(n)} be the noncommutative monomial of degree n in a and b whose i-th letter (from the left) is a if i ∉ T and b if i ∈ T, for i = 1, …, n. Given a Bruhat path Γ = (u_{0}, u_{1}, ⋯, u_{k−1}, u_{k}) of length k we define its weight to be

w(Γ) =^{def} m_{D(Γ)}^{(k−1)}.

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

ψ̃_{u,v}(a + b, ab + ba) = ∑_{Γ} w(Γ)

where Γ runs over all the Bruhat paths from u to v.

Proof. Let w = c^{n_{1}} d c^{n_{2}} d ⋯ c^{n_{k}} d c^{n_{0}} be a cd-word (n_{0}, …, n_{k} ∈ ℕ, k ≥ 0). It then follows immediately from the definition of B[I^{w}] that

(2.5) (a + b)^{n_{1}} (ab + ba) ⋯ (a + b)^{n_{k}}(ab + ba)(a + b)^{n_{0}} = ∑_{T ∈B[I^{w}]} m_{T}^{(|w|)}.

On the other hand, by Theorem 2.2 and Corollary 2.3,

(2.6)  F̃(u, v) = ∑_{α} b_{α}(u, v) L_{α} = ∑_{w}[w]_{u,v} Θ_{w},

using (1.8) and equating coefficients of L_{T}^{(n+1)} in (2.6) we obtain that

(2.7)  b_{T}^{(n+1)}(u, v) = ∑_{{w: |w|=n, T ∈B[I^{w}]}}[w]_{u,v},

for all n ∈ ℕ and T ⊆ [n], where as in (1.3)

b_{T}^{(n+1)}(u, v) =^{def} |{Γ ∈ B_{n+1}(u, v) : D(Γ) = T }|.

Therefore, by (2.5) and (2.7),

ψ̃_{u,v}(a + b, ab + ba) = ∑_{w}[w]_{u,v} ∑_{T ∈B_{[}I^{w}]} m_{T}^{(|w|)}

= ∑_{n≥0} ∑_{T ⊆[n]} (  ∑_{{w: |w|=n, T ∈B[I^{w}]}}[w]_{u,v}) m_{T}^{(n)}

= ∑_{n≥0} ∑_{T ⊆[n]} b_{T}^{(n+1)}(u, v) m_{T}^{(n)}

= ∑_{Γ} w(Γ),

as desired. □

From this we see that we can obtain the polynomial R̃_{u,v} directly from ψ̃_{u,v}.

Corollary 2.10. For u < v, R̃_{u,v}(q) = q ψ̃_{u,v}(q, 0).

Proof. From (2.7), one obtains [c^{n}]_{u,v} = b_{∅}^{(n+1)}(u, v) for any n. Thus

q ψ̃_{u,v}(q, 0) = ∑_{n≥0} [c^{n}]_{u,v} q^{n+1}

= ∑_{Γ∈B(u,v):D(Γ)=∅} q^{l(Γ)} = R̃_{u,v}(q),

the last equality being [7, Theorem 5.3.4]. □

Thus, referring to Example 2.4, we have R̃_{1234,4231}(q) = q^{5} + 2q^{3} + q. As in [21], we note that ℤ⟨a, b⟩ has a comultiplication defined for mono-

mials by

(2.8)  Δ′(a_{1} ⋯ a_{n}) =^{def} ∑_{i=1}^{n} a_{1} ⋯ a_{i−1} ⊗ a_{i+1} ⋯ a_{n},

and extended linearly (where Δ′(1) =^{def} 0 ⊗ 0). Similarly, we can define a second coproduct on Bruhat intervals by

Δ′([u, v]) = ∑_{u<z<v}[u, z] ⊗ [z, v].

(Note that this is not the coproduct given in (2.2).) We define, for convenience,

ϕ̃_{u,v}(a, b) =^{def} ψ̃_{u,v}(a + b, ab + ba),

for all u, v ∈ W, u < v. Then with the coalgebra structures just defined on Bruhat intervals and ℤ⟨a, b⟩, we have that ϕ̃ is a map of coalgebras.

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

Δ′(ϕ̃_{u,v}) = ∑_{u<z<v} ϕ̃_{u,z} ⊗ ϕ̃_{z,v}.

Proof. Given a Bruhat path Γ = (u_{0}, u_{1}, …, u_{k}) we let Γ_{(i)} =^{def} (u_{0}, u_{1}, …, u_{i})

and Γ^{(i)} =^{def} (u_{i}, u_{i+1}, …, u_{k}), for i = 1, …, k − 1. By Proposition 2.9 and (2.8) we have that

Δ′(ϕ̃_{u,v}) = ∑_{Γ} Δ′(w(Γ))

= ∑_{Γ} ∑_{i=1}^{l(Γ)−1} w(Γ_{(i)}) ⊗ w(Γ^{(i)})
= ∑_{u<z<v} ∑_{Γ_{1}∈B(u,z)} ∑_{Γ_{2}∈B(z,v)} w(Γ_{1}) ⊗ w(Γ_{2})

= ∑_{u<z<v} ϕ̃_{u,z} ⊗ ϕ̃_{z,v},

as desired. □

If we let c = a+b and d = ab+ba, then as in [21], the subalgebra ℤ⟨c, d⟩ of ℤ⟨a, b⟩ is closed under Δ′, since Δ′(c) = 2(1⊗1) and Δ′(d) = c⊗1+1⊗c (Δ′ acts as a derivation on ℤ⟨a, b⟩). Thus ψ̃ is a map of coalgebras:

Δ′(ψ̃_{u,v}) = ∑_{u<z<v} ψ̃_{u,z} ⊗ ψ̃_{z,v}.

We note finally that the multiplicative structure used in [21], the poset join, does not carry over to Bruhat intervals. In most cases the join of two Bruhat intervals cannot be a Bruhat interval by [12, Theorem 3.2].

3. Kazhdan-Lusztig polynomials and the complete cd-index

In this section we show how one can compute easily and explicitly the Kazhdan-Lusztig polynomial of any Bruhat interval of any Coxeter group from its complete cd-index.

Recall the definition of the polynomials Ψ_{α} and Υ_{α} from §1.1. Consider

the map K : QSym → ℤ[q^{1/2}, q^{−1/2}] defined by K(M_{α}) =^{def} (−1)^{l(α)}q^{− \frac{|α|}{2}} Ψ_{α}

or, equivalently, K(L_{α}) =^{def} q^{− \frac{|α|}{2}} Υ_{α}. Then by Theorem 2.2 we may rephrase Theorem 1.6 in the following way.

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

(3.1)  K(F̃(u, v)) = q^{\frac{−l(u,v)}{2}} P_{u,v}(q) − q^{\frac{l(u,v)}{2}} P_{u,v} (\frac{1}{q}) .

If we define Ξ_{w} =^{def} K(Θ_{w}), then the following is immediate from Corollary 2.3 and Proposition 3.1.

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

q^{\frac{−l(u,v)}{2}} P_{u,v}(q) − q^{\frac{l(u,v)}{2}} P_{u,v}(1/q) = ∑_{w}[w]_{u,v} Ξ_{w}.

We next give an explicit description of Ξ_{w} in terms of w. Let C_{i} =^{def} \frac{1}{2i+1} \binom{2i+1}{i} for i ∈ ℕ be the i-th Catalan number, and set C_{i} = 0 if i ∉ ℕ. Let

(3.2)  B_{k}(q) =^{def} ∑_{i=0}^{⌊k/2⌋} \frac{k + 1 − 2i}{k + 1}\binom{k + 1}{i}q^{i}.

We call B_{k}(q) the k-th ballot polynomial since it is closely related to ballot problems (see, e.g., [22, §III.1, p. 73]).

Let a, b ∈ ℤ, a ≤ b. By a lattice path on [a, b] we mean a function Γ : [a, b] → ℤ 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 l(Γ) the length of Γ. Note that b ∉ N(Γ) and that

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

We denote by L(n) the set of all lattice paths on [0, n]. From [10, Theorem 6.1] we have that for a composition α,

(3.4)  Υ_{α}(q) = (−1)^{|α|−l(α)} ∑_{{Γ∈L(|α|): co(N(Γ))=α^{∗}}}(−q)^{d_{+}(Γ)}.

For a set T, we denote by T^{∗} the set for which co(T^{∗}) = co(T)^{∗}.

The next result, along with the previous one, shows how one can compute the Kazhdan-Lusztig polynomial of any pair of elements u, v ∈ W from the complete cd-index of the Bruhat interval [u, v].

Theorem 3.3. Let w = c^{n_{0}}dc^{n_{1}}d ⋯ dc^{n_{k}}, k ≥ 0, n_{0}, …, n_{k} ≥ 0. Then

Ξ_{w} = (−1)^{k+ \frac{|w|−n_{0}}{2}} (q^{− \frac{n_{0}+1}{2}} B_{n_{0}}(−q) − q^{\frac{n_{0}+1}{2}} B_{n_{0}} (\frac{−1}{q})) ∏_{j=1}^{k} C_{\frac{n_{j}}{2}} .

In particular, Ξ_{w} = 0 unless n_{1} ≡ n_{2} ≡ ⋯ ≡ n_{k} ≡ 0 (mod 2).

Proof. Let n = |w|, and for a cd-word w = w_{1} ⋯ w_{n}, let w^{∗} =^{def} w_{n} ⋯ w_{1}. Note that (I^{w})^{∗} = I^{w^{∗}}. Then, by (1.8) and (3.4) we have that

q^{\frac{n+1}{2}} Ξ_{w} = ∑_{T ∈B[I^{w}]} Υ_{co(T)}

= ∑_{T ∈B[I^{w}]} ∑_{{Γ∈L(n+1) : N(Γ)^{∗}=T }}(−1)^{n+1−|N(Γ)|−1}(−q)^{d_{+}(Γ)}

(3.5)  = ∑_{\{Γ∈L(n+1) , N(Γ),\overline{N(Γ)}∈b(I^{w^{∗}})\}}(−1)^{Γ_{≥0}} (−q)^{d_{+}(Γ)}.

Now, I^{w^{∗}} = {{p_{1}−1, p_{1}}, {p_{2}−1, p_{2}}, …, {p_{k} −1, p_{k}}} where p_{j} =^{def} n_{k+1−j} +

⋯ + n_{k} + 2j for j ∈ [k], and clearly \overline{N(Γ)} = \{i ∈ [n] : Γ(i) ≥ 0\}. Therefore Γ ∈ L(n+1) is such that N(Γ)∩\{p_{j} −1, p_{j}\} ≠ ∅ and \overline{N(Γ)}∩\{p_{j} −1, p_{j}\} ≠ ∅ for all j ∈ [k] if and only if either Γ(p_{j} − 1) = Γ(p_{j}) − 1 = −1 or Γ(p_{j} − 1) = Γ(p_{j}) + 1 = 0, for all j ∈ [k]. Since Γ is a lattice path this happens if and only if

(3.6)  Γ(p_{j} − 1) = \{ \begin{matrix}Γ(p_{j}) − 1 = −1, & if p_{j} ≡ 0 (mod 2), \\ Γ(p_{j}) + 1 = 0, & if p_{j} ≡ 1 (mod 2), \end{matrix}

for all j ∈ [k].

Let, for brevity, L_{w} be the set of all lattice paths Γ ∈ L(n+1) that satisfy condition (3.6) so, by (3.5),

(3.7)  q^{\frac{n+1}{2}} Ξ_{w} = ∑_{Γ∈L_{w}}(−1)^{Γ_{≥0}} (−q)^{d_{+}(Γ)}.

We claim that

(3.8)  q^{\frac{n+1}{2}} Ξ_{w} = ∑_{Γ∈L_{w}^{∗}}(−1)^{Γ_{≥0}} (−q)^{d+(Γ)}

where

(3.9)  L_{w}^{∗} =^{def} {Γ ∈ L_{w} : Γ(i) ≠ 0 if i ∈ [n + 1] \ {p_{1}, …, p_{k}}}.

In fact, let Γ ∈ L_{w} \ L_{w}^{∗} and let

i_{0} =^{def} min{i ∈ [n + 1] \ {p_{1}, …, p_{k}} : Γ(i) = 0}.

Note that i_{0} ≡ 0 (mod 2). Then p_{r} < i_{0} < p_{r+1} for some r ∈ [0, k] (where p_{0} =^{def} 0 and p_{k+1} =^{def} n+2). Since Γ ∈ L_{w} this implies that Γ(p_{r}) = 0 (else, by (3.6), Γ(p_{r} −1) = 0, contradicting the choice of i_{0}). Define Γ′ : [0, n+1] → ℤ by

Γ′(i) =^{def} \{ \begin{matrix}−Γ(i), & if p_{r} ≤ i ≤ i_{0}, \\ Γ(i), & otherwise, \end{matrix}

for i ∈ [0, n + 1]. Then Γ′ ∈ L_{w} \ L_{w}^{∗}, d_{+}(Γ′) = d_{+}(Γ) and (−1)^{Γ′_{≥0}} = −(−1)^{Γ_{≥0}}. It is clear that this map Γ ↦ Γ′ is an involution of L_{w} \ L_{w}^{∗} (since i_{0} = min{i ∈ [n + 1] \ {p_{1}, …, p_{k}} : Γ′(i) = 0}) and that it has no fixed points, so ∑_{Γ∈L_{w}\L_{w}^{∗}}(−1)^{Γ_{≥0}} (−q)^{d_{+}(Γ)} = 0 and (3.8) follows from (3.7).

Now let Γ ∈ L_{w}^{∗}. Then, by (3.9) and (3.6),

Γ(p_{j} − 1) = Γ(p_{j}) − 1 = −1

and p_{j} ≡ 0 (mod 2) for all j ∈ [k]. This, again by (3.9), implies that Γ(p_{j−1}+ 1) = −1 for all j ∈ [k] and that Γ(i) ≤ −1 for all i ∈ [p_{k}] \ {p_{1}, …, p_{k}}. Therefore, by (3.8),

q^{\frac{n+1}{2}} Ξ_{w} = ∑_{m=−n_{0}−1}^{n_{0}+1} ∑_{\{Γ∈L_{w}^{∗}: Γ(n+1)=m\}}(−1)^{Γ_{≥0}} (−q)^{d_{+}(Γ)}

= ∑_{\{m∈[n_{0}+1]: m≡n_{0}+1 (mod 2)\}} ∏_{j=1}^{k} C_{\frac{n_{j}}{2}} \frac{m}{n_{0} + 1}\binom{n_{0} + 1}{\frac{n_{0}+1−m}{2}}

((−1)^{k} ((−q)^{\frac{n+1+m}{2}} (−1)^{n_{0}} + (−q)^{\frac{n+1−m}{2}} ))

= ∑_{i=0}^{⌊ \frac{n_{0}}{2} ⌋}(−1)^{k} ∏_{j=1}^{k} C_{\frac{n_{j}}{2}} \frac{n_{0} + 1 − 2i}{n_{0} + 1}\binom{n_{0} + 1}{i}

((−q)^{\frac{n+1+n_{0}+1−2i}{2}} (−1)^{n_{0}} + (−q)^{\frac{n+1−n_{0}−1+2i}{2}} )

=(−1)^{k} ∏_{j=1}^{k} C_{\frac{n_{j}}{2}} (−q)^{\frac{n−n_{0}}{2}} ∑_{i=0}^{⌊ \frac{n_{0}}{2} ⌋} \frac{n_{0} + 1 − 2i}{n_{0} + 1}\binom{n_{0} + 1}{i}
((−q)^{n_{0}+1−i} (−1)^{n_{0}} + (−q)^{i})
=(−1)^{k} ∏_{j=1}^{k} C_{\frac{n_{j}}{2}} (−q)^{\frac{n−n_{0}}{2}} (B_{n_{0}}(−q) − q^{n_{0}+1} B_{n_{0}}(−1/q)) ,

where we have used (3.3) and well known results on lattice path enumeration (see, e.g., [32, Ex.6.20]). □

4. Kazhdan-Lusztig polynomials and ballot polynomials

Using the results in the previous section, we derive the expansion, in terms of the complete cd-index, of the Kazhdan-Lusztig polynomials with respect to a basis derived from the ballot polynomials (3.2). This basis and its relation to the Kazhdan-Lusztig polynomials was independently studied by Caselli [13], who also considered its relation to the R-polynomails.

In what follows, we will consider a fixed Bruhat interval [u, v]; the dependence on the pair u, v will often be omitted. We set n = l(u, v) − 1. For a cd-word w = c^{n_{0}}dc^{n_{1}}d ⋯ c^{n_{k−1}}dc^{n_{k}}, k ≥ 0, n_{0}, …, n_{k} ≥ 0, define C_{w} =^{def} ∏_{j=1}^{k} C_{\frac{n_{j}}{2}} . If w = c^{m}, we take C_{w} = 1. Note that since C_{i} = 0 when i ∉ ℕ, C_{w} = 0 unless w is an even cd-word, that is, unless n_{1}, …, n_{k} are all even.

It will be helpful to rework Corollary 3.2 to obtain an expression for the Kazhdan-Lusztig polynomial in terms of alternating shifted ballot polynomials q^{i}B_{n−2i}(−q). Note that q^{i}B_{n−2i}(−q) has degree ⌊n/2⌋ and lowest degree term q^{i} with coefficient 1. Thus the set of polynomials q^{i}B_{n−2i}(−q), 0 ≤ i ≤ ⌊\frac{n}{2}⌋, form a basis for the space of polynomials of degree ≤ ⌊n/2⌋. Depending on the parity of n, Caselli denoted this basis by O_{j} or E_{j} (see [13, Theorem 6.5]).

We begin by deriving the expression for P_{u,v} in terms of this basis as a function of the complete cd-index.

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

P_{u,v}(q) = ∑_{i=0}^{⌊n/2⌋} a_{i} q^{i} B_{n−2i}(−q),

where

a_{i} = a_{i}(u, v) = [c^{n−2i}]_{u,v} + ∑_{dw even}(−1)^{\frac{|w|}{2} +|w|_{d}}C_{dw}[c^{n−2i}dw]_{u,v}.

Proof. Since deg(P_{u,v}) ≤ ⌊n/2⌋, it follows from Corollary 3.2 that

(4.1)  P_{u,v} = ∑_{w}[w]_{u,v} D_{\frac{n}{2}} (q^{\frac{l(u,v)}{2}} Ξ_{w}) .

If w = c^{n_{0}}dc^{n_{1}}dc^{n_{2}} ⋯ dc^{n_{k}}, with |w| ≤ n = l(u, v) − 1, then by Theorem 3.3,

q^{\frac{l(u,v)}{2}} Ξ_{w} = (−1)^{k+ \frac{|w|−n_{0}}{2}} C_{w} [q^{\frac{n−n_{0}}{2}} B_{n_{0}}(−q) − q^{\frac{n+n_{0}}{2} +1} B_{n_{0}} (\frac{−1}{q})] .

Thus, if w is even and [w]_{u,v} ≠ 0, then n_{0} ≡ |w| ≡ n (mod 2) so

D_{\frac{n}{2}} (q^{\frac{l(u,v)}{2}} Ξ_{w}) = (−1)^{k+ \frac{|w|−n_{0}}{2}} C_{w} q^{\frac{n−n_{0}}{2}} B_{n_{0}}(−q),

and (4.1) becomes

(4.2)  P_{u,v} = ∑_{w even}(−1)^{|w|_{d}+ \frac{|w|−h(w)}{2}} C_{w} [w]_{u,v} q^{\frac{n−h(w)}{2}} B_{h(w)}(−q),

where h(c^{n_{0}}dc^{n_{1}}d ⋯ c^{n_{k−1}}dc^{n_{k}}) =^{def} n_{0} denotes the head of w.

Collecting the terms corresponding to cd words w with h(w) = n − 2i gives the statement of the theorem. □

Remark 4.2. Alternatively, we can write a_{i} as a sum over subsets of [i], namely

∑_{S={i_{1},...,i_{k}}_{<}^{S⊆[i]}}(−1)^{i_{k}−k} [c^{n−2i}dc^{2(i_{1}−1)}dc^{2(i_{2}−i_{1}−1)} ⋯

…dc^{2(i_{k}−i_{k−1}−1)}]_{u,v} ∏_{j=1}^{k} C_{i_{j}−i_{j−1}−1}.

Remark 4.3. We list the first few coefficients a_{i} as functions of the complete cd-index (recall n = l(u, v) − 1, and that we omit the dependence on u, v):

a_{0} = [c^{n}]
a_{1} = [c^{n−2}d] + [c^{n−2}]
a_{2} = [c^{n−4}d^{2}] − [c^{n−4}dc^{2}] + [c^{n−4}d] + [c^{n−4}]
a_{3} = [c^{n−6}d^{3}] − [c^{n−6}d^{2}c^{2}] − [c^{n−6}dc^{2}d] + 2[c^{n−6}dc^{4}]
+ [c^{n−6}d^{2}] − [c^{n−6}dc^{2}] + [c^{n−6}d] + [c^{n−6}].

(4.3)

Remark 4.4. By Proposition 2.5, the degree n terms of the complete cdindex of the Bruhat interval [u, v] correspond to the ordinary cd-index of the Eulerian poset [u, v]. Restricting the formulas for the a_{i} in Theorem 4.1 to only the degree n cd-coefficients yields the expression given by Bayer and Ehrenborg [3, Theorem 4.2] for the g-polynomial g([u, v]^{∗}, q) in terms of the cd-index of the dual interval [u, v]^{∗}. This can be checked by comparing formulas – for example the polynomial Q_{k+1}(x) of [3] is B_{k}(−x) – and recalling that [w]_{u,v} = [w^{∗}]_{[u,v]^{∗}}. One consequence is that the difference P_{u,v}(q) − g([u, v]^{∗}, q) is a function of the lower degree cd-coefficients only.

Example 4.5. Continuing with Example 2.4, we have

F̃(1234, 4231) = Θ_{c^{4}} + Θ_{dc^{2}} + 2Θ_{cdc} + 2Θ_{c^{2}d} + 2Θ_{d^{2}} + 2Θ_{c^{2}} + Θ_{1}

and so

P_{u,v}(q) = a_{0}q^{0}B_{4}(−q) + a_{1}q^{1}B_{2}(−q) + a_{2}q^{2}B_{0}(−q)
= [c^{4}] (1 − 3q + 2q^{2}) + ([c^{2}d] + [c^{2}]) q(1 − q)
+ ([d^{2}] − [dc^{2}] + [d] + [1]) q^{2}
= (1 − q + q^{2}) + (2q − q^{2}) = 1 + q

with g([u, v]^{∗}, q) = 1 − q + q^{2}.

Considering the dependence of the coefficients of the Kazhdan-Lusztig polynomials on these coefficients a_{i}, let P_{u,v} = p_{0} + p_{1}q + · · ·. The following is a direct consequence of the definition of the a_{i} as the coefficients of P_{u,v} in the basis q^{i} B_{n−2i}(−q). Propositions 4.6 and 4.7 as well as Corollary 4.8 are all implicit in [13, §6], so proofs will be omitted here.

Proposition 4.6. For j = 0, …, ⌊n/2⌋,

p_{j} = ∑_{i=0}^{j}(−1)^{j−i} \frac{n + 1 − 2j}{n + 1 − 2i} \binom{n + 1 − 2i}{j − i}a_{i}.

Theorem 4.1 and Proposition 4.6 allow us to derive the coefficients of the Kazhdan-Lusztig polynomial for any Bruhat interval as a function of its complete cd-index. For example, we can read from Proposition 4.6 and (4.3) that

\begin{matrix}p_{1} = [q](P_{u,v}) = & a_{1} − (n − 1)a_{0} \\ = & [c^{n−2}d] + [c^{n−2}] − (n − 1)[c^{n}]. \end{matrix} ; (4.4)

The relations given in Proposition 4.6 are unitriangular so invertible. The inverse relations have a particularly simple nonnegative form.

Proposition 4.7. For j = 0, …, ⌊n/2⌋,

a_{j} = ∑_{i=0}^{j} \binom{n − j − i}{n − 2j}p_{i}.

Corollary 4.8. Nonnegativity of a_{i}(u, v), i = 1, …, k is implied by the nonnegativity of [q^{i}](P_{u,v}), i = 1, …, k.

Remark 4.9. In fact, any nonnegative polynomial of degree ≤ ⌊\frac{n}{2}⌋ has a nonnegative representation in terms of the basis of alternating shifted ballot polynomials q^{i}B_{n−2i}(−q).

Given the conjectured nonnegativity of the coefficients of the Kazhdan-Lusztig polynomial P_{u,v} for any Bruhat interval [u, v] [25], Caselli made the following conjecture. Because of Theorem 4.1 (see also (4.3)), we can interpret it as a conjectured set of linear inequalities that must be satisfied by the complete cd-index.

Conjecture 4.10. [13, Conjecture 6.6] For each Bruhat interval [u, v] and for each i = 0, 1, …, ⌊n/2⌋, n = l(u, v) − 1, we have a_{i}(u, v) ≥ 0.

We conclude by noting the following consequence of Proposition 4.7.

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

a_{⌊ \frac{l(u,v)−1}{2} ⌋} = \begin{cases}P_{u,v}(1), & l(u, v) odd \\ \frac{d}{dq} (q^{\frac{l(u,v)}{2}} P_{u,v}(1/q)) |_{q=1}, & l(u, v) even. \end{cases}

Remark 4.12. An interesting question is whether, for all w, the quantities [w]_{u,v} are combinatorially invariant, that is, they depend only on the poset structure of the interval [u, v]. This is true for cd-words w of degree l(u, v)−1 by Proposition 2.5. By Theorem 4.1, combinatorial invariance of [w]_{u,v} for all w implies the conjectured combinatorial invariance of the Kazhdan-Lusztig polynomial P_{u,v}. But the converse is also true: if P_{u,v} is combinatorially invariant for all u < v, then so is [w]_{u,v} for all w and all u < v. This follows from Proposition 1.4 and Theorem 1.5 and the fact that [w]_{u,v} depends on the c_{α}, by (1.4) and Proposition 5.1. Combinatorial invariance of P_{u,v} is known to hold in the case u = e (see [27], [12] and [15]), and it follows that the same is true for all [w]_{e,v}.

5. Other representations of the complete cd-index

The formulas obtained in the previous sections for the Kazhdan-Lusztig polynomials assume knowledge of the complete cd-index. In this section we show how one can explicitly compute the complete cd-index of a Bruhat interval [u, v] in terms of the coefficients b_{α}(u, v) defined in §1.1.

Let u, v ∈ W, u < v, and n ∈ [l(u, v) − 1], n ≡ l(u, v) − 1 (mod 2). In this section it will be convenient to index the b_{α} by subsets instead of the corresponding compositions. Unless otherwise explicitly stated, all subsets are in [n]. We will omit to write the dependence on u, v throughout the section.

We start with a general expression for [w] in terms of sparse b_{S}, that is, those b_{S}, S ⊆ [n], where S has no two successive elements and n ∉ S. In terms of b_{α}, this means that α_{i} > 1 if i > 1. We use an expression for [w] in terms of the sparse k-vector, which is a reinversion of the sparse b_{S} defined by k_{S} = ∑_{T ⊆S}(−1)^{|S|−|T |}b_{T}. The following result is proved in exactly the same way as [5, Proposition 7.1].

Proposition 5.1. Let w = c^{n_{1}}dc^{n_{2}}d ⋯ c^{n_{k}}dc^{n_{0}} and define m_{0}, …, m_{k} by m_{0} = 1 and m_{i} = m_{i−1} + n_{i} + 2. Then

[w] = ∑_{i_{1},...,i_{k}}(−1)^{(m_{1}−i_{1})+(m_{2}−i_{2})+···+(m_{k}−i_{k})} k_{{i_{1}i_{2}···i_{k}}}, (5.1)

where the sum is over all k-tuples (i_{1}, i_{2}, …, i_{k}) such that m_{j−1} ≤ i_{j} ≤ m_{j} − 2.

The inversion of this relation, expressing k_{S} as a sum of distinct [w], is the same as [6, Proposition 2.3]. Using Proposition 5.1 one can obtain from (4.4) that the coefficient of the linear term of the Kazhdan-Lusztig polynomial P_{u,v} is

p_{1} = c_{n,1}(u, v) + c_{n−1}(u, v) − (n + 1)

(compare [8, Corollary 5.9]).

We will show that if [w] is expressed in terms of the sparse b_{S}, the coefficients are still ±1, leading to the possibility of a direct enumerative interpretation of [w]. Using the notation of Proposition 5.1, let

A_{j} = { i : m_{j−1} ≤ i ≤ m_{j} − 2}

be the range of i_{j} above, and let

T_{w} =^{def} {T ⊂ ∪_{i≤k}A_{i} : |T ∩ A_{j}| ≤ 1 ∀j}.

Then k_{S} appears in (5.1) if and only if S ∈ T_{w} and |S| = k , and by Proposition 5.1 and the definition of k_{S}, we see that [w] = ∑_{S∈T_{w}} d_{S} b_{S} for integers d_{S}. We now prove that these integers can only be ±1 or 0.

Proposition 5.2. If w = c^{n_{1}}d ⋯ c^{n_{k}}dc^{n_{0}}, then [w] = ∑_{S∈T_{w}} d_{S} b_{S}, where

d_{S} = \begin{cases}(−1)^{k−|S|} ∏_{j} ∏_{i∈S∩A_{j}}(−1)^{m_{j}−i}, & if |S ∩ A_{i}| = 1 for |A_{i}| even, \\ 0, & otherwise. \end{cases}

Proof. By (5.1) and the definition of k_{S} we have

\begin{aligned}d_{S} & = ∑_{S⊆\{i_{1},...,i_{k}\}∈T_{w}}(−1)^{k−|S|}(−1)^{(m_{1}−i_{1})+(m_{2}−i_{2})+···+(m_{k}−i_{k})} \\ & = (−1)^{k−|S|} [ ∏_{j:S∩A_{j}≠∅} ∏_{i∈S∩A_{j}}(−1)^{m_{j}−i}] [ ∏_{j:S∩A_{j}=∅} ( ∑_{i∈A_{j}}(−1)^{m_{j}−i})] . \end{aligned}

But the sums in the last expression are 0 or 1 depending on whether |A_{j}| are even or odd, so the result follows. □

For example, for w = cd^{2}, k = 2, n_{1} = 1, n_{2} = 0, n_{0} = 0, A_{1} = {1, 2}, A_{2} = {4} and so

[cd^{2}] = b_{{2,4}} − b_{{1,4}} − b_{{2}} + b_{{1}}.

Note that the same expression computes the coefficient [w] = [cd^{2}c^{m}] for any m ≥ 0, where the subscripts are understood to be subsets of {1, …, deg w}.

Finally, we give simple proofs of two elementary identities between cdcoefficients and the numbers b_{α} using basic quasisymmetric identities. The second of these is essentially in [31].

Proposition 5.3. Let u, v ∈ W, u < v, and n ∈ [l(u, v) − 1], n ≡ l(u, v) − 1 (mod 2). Then:

(1) ∑_{w} 2^{n−|w|_{d}}[w]_{u,v} = c_{[n]}(u, v), the number of Bruhat paths from u to v of length n + 1,

(2) ∑_{w}[w]_{u,v} = b_{{1,3,5,... }}(u, v), where the sums are over all cd-words of degree n.

Proof. By Theorem 2.2

F̃_{n+1}(u, v) = ∑_{S} c_{S}(u, v) M_{S}^{(n+1)} = ∑_{S} b_{S}(u, v) L_{S}^{(n+1)} = ∑_{w}[w]_{u,v} Θ_{w},

where the sums are over all subsets of [n] and over all cd-words of degree n (recall that we denote by F̃_{i} the homogeneous component of F̃ of degree i). We now use the relations

Θ_{w} = ∑_{S∈b[I_{w}]} 2^{|S|−|w|_{d}} M_{S}^{(n+1)} = ∑_{T ∈B[I^{w}]} L_{T}^{(n+1)}

from [6, (2.14)] (divided, as before, by 2^{|w|_{d}+1}) and (1.8). Hence the coefficient of M_{[n]}^{(n+1)} in Θ_{w} is 2^{n−|w|_{d}}, so we can conclude (1). Similarly, the coefficient of L_{{1,3,5,...}} in Θ_{w} is 1, so (2) follows. □

6. A sign conjecture for the complete cd-index

We conclude with an intriguing sign conjecture for the complete cd-index and prove one of its simple consequences in certain cases. Computation on Bruhat intervals up to rank 7 occurring in symmetric groups suggests the following.

Conjecture 6.1. Let (W, S) be a Coxeter system and u, v ∈ W, u < v. Then

[w]_{u,v} ≥ 0

for all cd-words w.

Since every Bruhat interval is shellable (e.g., [7, Theorem 2.7.5]) and Eulerian, hence Gorenstein^{∗}, it follows from the recent work of Karu [24] (see also [20]) that [w]_{u,v} ≥ 0 whenever deg w = l(u, v) − 1 (the top degree for which [w]_{u,v} ≠ 0).

If Conjecture 6.1 were true, then Proposition 5.3 would imply that

2^{n}[c^{n}]_{u,v} ≤ c_{[n]}(u, v)

for all u, v ∈ W and n ≥ 0. This is indeed true for finite Coxeter and affine Weyl groups, as we now show. From now on, we assume that W is a finite Coxeter or affine Weyl group.

Given two Bruhat paths Δ = (u, x, v), Γ = (u, y, v) ∈ B_{2}(u, v) write Δ ≤ Γ if (xu^{−1}, vx^{−1}) is lexicographically smaller than (yu^{−1}, vy^{−1}) (where T is totally ordered by the chosen reflection ordering). Let m =^{def} [t^{2}](R̃_{u,v}). It then follows easily from [7, Theorem 5.3.4] that |B_{2}(u, v)| = 2m and that

|{Δ ∈ B_{2}(u, v) : D(Δ) = ∅}| = m = |{Δ ∈ B_{2}(u, v) : D(Δ) = {1}}|.

For Γ ∈ B_{2}(u, v) let

r =^{def} |{Δ ∈ B_{2}(u, v) : D(Δ) = D(Γ), Δ ≤ Γ}|.

The flip of Γ is the r-th Bruhat path (in the lexicographic ordering) in {Δ ∈ B_{2}(u, v) : D(Δ) ≠ D(Γ)}. We denote this path by flip(Γ). This notion is a special case of that of lexicographic correspondence first introduced in [11]. The following result is a special case of [11, Corollary 2.3].

Proposition 6.2. Let W be a finite Coxeter or affine Weyl group. Further, let u, v ∈ W, u < v, (u, y, v) ∈ B_{2}(u, v) be such that D((u, y, v)) = ∅ and

(u, x, v) =^{def} flip((u, y, v)). Then yu^{−1} <_{T} xu^{−1} and vx^{−1} <_{T} vy^{−1}.

Note that flip(flip(Γ)) = Γ. Given Δ = (u_{0}, u_{1}, …, u_{k}) ∈ B_{k}(u, v) we let, for i ∈ [k − 1], flip_{i}(Δ) be the Bruhat path in B_{k}(u, v) obtained by flipping Δ at its i-th element. Namely, flip_{i}(Δ) =^{def} (u_{0}, u_{1}, …, u_{i−1},

x, u_{i+1}, …, u_{k−1}, u_{k}) where (u_{i−1}, x, u_{i+1}) =^{def} flip((u_{i−1}, u_{i}, u_{i+1})). Note

that if {i − 1, i, i + 1} ∩ D(Δ) = ∅ then, by Proposition 6.2, {i − 1, i, i + 1} ∩ D(flip_{i}(Δ)) = {i}.

Proposition 6.3. Let W be a finite Coxeter or affine Weyl group and u, v ∈ W, u < v. Then

[t^{k}](R̃_{u,v}) ≤ ⌊\frac{|B_{k}(u, v)|}{2^{k−1}}⌋

for all k ≥ 1, and so 2^{n}[c^{n}]_{u,v} ≤ c_{[n]}(u, v) for n ≥ 0.

Proof. Since [t^{k}](R̃_{u,v}) ∈ ℕ, we prove the equivalent statement that

[t^{k}](R̃_{u,v})2^{k−1} ≤ |B_{k}(u, v)|.

We do this by constructing an explicit injection.

Let Γ = (u, u_{1}, ⋯, u_{k−1}, v) ∈ B_{k}(u, v) be such that D(Γ) = ∅ and S = {s_{1}, …, s_{r}}_{<} ⊆ [k − 1]. We define

φ(Γ, S) =^{def} flip_{s_{r}}(⋯ (flip_{s_{1}}(Γ)) ⋯).

Clearly, φ(Γ, S) ∈ B_{k}(u, v). Furthermore, note that by Proposition 6.2

s_{i} = max {D(flip_{s_{i}}(⋯ (flip_{s_{1}}(Γ)) ⋯))}
= max {D(flip_{s_{i+1}}(⋯ (flip_{s_{r}}(φ(Γ, S))) ⋯))}

for i = 1, …, r.Therefore s_{r}, …, s_{1} and hence Γ are uniquely recoverable from φ(Γ, S), so φ is an injection. The result now follows from the fact that [t^{n+1}](R̃_{u,v}) = [c^{n}]_{u,v} by Corollary 2.10. □

Remark 6.4. We note that Proposition 6.3 holds whenever Proposition 6.2 does, and the latter has been conjectured to hold for all Coxeter groups (see [14, p. 117] and [11, p. 745]), giving further evidence for Conjecture 6.1.

References

[1] M. Aguiar, N. Bergeron, and F. Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville relations, Compos. Math. 142 (2006), 1–30.

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

[3] M.M. Bayer and R. Ehrenborg, The toric h-vectors of partially ordered sets, Trans. Amer. Math. Soc. 352 (2000), 4515–4531.

[4] M.M. Bayer and A. Klapper, A new index for polytopes, Discrete Comput. Geometry 6 (1991), 33–47.

[5] L.J. Billera and R. Ehrenborg, Monotonicity of the cd-index for polytopes, Math. Z. 233 (2000), 421–441.

[6] L.J. Billera, S. K. Hsiao, and S. van Willigenburg, Peak quasisymmetric functions and Eulerian enumeration, Adv. Math. 176 (2003), no. 2, 248–276.

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

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

[9] F. Brenti, Combinatorial expansions of Kazhdan-Lusztig polynomials, J. London Math. Soc. 55 (1997), 448–472.

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

[11] F. Brenti and F. Incitti, Lattice paths, lexicographic correspondence and Kazhdan-Lusztig polynomials, J. Algebra 303 (2006), 742–762.

[12] F. Brenti, F. Caselli, and M. Marietti, Special matchings and Kazhdan-Lusztig polynomials, Advances in Math. 202 (2006), 555–601.

[13] F. Caselli, Non-neegativity properties of R-polynomials, European J. Combin. 27 (2006), 1005–1021.

[14] P. Cellini, T-increasing paths on the Bruhat graph of affine Weyl groups are selfavoiding, J. Algebra, 228 (2000), 107-118.

[15] E. Delanoy, Combinatorial invariance of Kazhdan-Lusztig polynomials on intervals starting from the identity, J Algebr Comb 24 (2006), 437-463.

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

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

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

[19] R. Ehrenborg, On posets and Hopf algebras, Adv. in Math. 119 (1996), 1–25.

[20] R. Ehrenborg and K. Karu, Decomposition theorem for the cd-index of Gorenstein* posets, J. Algebr. Comb. 26 (2007), 225–251.

[21] R. Ehrenborg and M. Readdy, Coproducts and the cd-index, J. Algebraic Combinatorics 8 (1998), 273–299.

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

[23] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge University Press, Cambridge, 1990.

[24] K. Karu, The cd-index of fans and posets, Compos. Math., 142 (2006), 701-718.

[25] D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Inventiones Math. 53 (1979), 165–184.

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

[27] M. Marietti, Kazhdan-Lusztig theory: Boolean elements, special matchings and combinatorial invariance, Ph.D. thesis, Universita’ di Roma ”La Sapienza”, Roma, 2003.

[28] N. Reading, The cd-index of Bruhat intervals., Electron. J. Combin. 11 (2004), no. 1, Research Paper 74, 25 pp. (electronic).

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

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

[31] R.P. Stanley, Flag f-vectors and the cd-index, Math. Z. 216 (1994), 483–499.

[32] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, Vol. 62, Cambridge University Press, Cambridge, UK, 1999.

[33] J.R. Stembridge, Enriched P -partitions, Trans. Amer. Math. Soc. 349 no. 2 (1997), 763-788.

Department of Mathematics, Cornell University, Ithaca, NY 14853-4201

E-mail address: billera@math.cornell.edu

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

E-mail address: brenti@mat.uniroma2.it