# Peak algebras, paths in the Bruhat graph and Kazhdan-Lusztig polynomials *

Francesco Brenti<fnref n="1" />† and Fabrizio Caselli<fnref n="2" />‡

**Abstract.** We obtain a nonrecursive combinatorial formula for the Kazhdan-Lusztig polynomials which holds in complete generality and which is simpler and more explicit than any existing one, and which cannot be linearly simplified. Our proof uses a new basis of the peak subalgebra of the algebra of quasisymmetric functions.

**Résumé.** On montre une formule combinatoire pour les polynômes de Kazhdan-Lusztig qui est valable en toute généralité. Cette formule est plus simple et plus explicite que toutes les autres formules connues; de plus, elle ne peut pas être simplifié lineairement. La preuve utilise une nouvelle base pour la sousalgèbre des sommets de l'algèbre des fonctions quasisymmetriques.

**Keywords:** quasi-symmetric functions, cd-index, Coxeter groups, lattice paths

## 1 Introduction

In their seminal paper [19] Kazhdan and Lusztig introduced a family of polynomials, indexed by pairs of elements of a Coxeter group $W$, that are now known as the Kazhdan-Lusztig polynomials of $W$ (see, e.g., [5] or [18]). These polynomials play a fundamental role in several areas of mathematics, including representation theory, the geometry of Schubert varieties, the theory of Verma modules, Macdonald polynomials, canonical bases, immanant inequalities and the Hodge theory of Soergel bimodules (see, e.g., [1, 2, 4, 8, 13, 14, 15, 16, 17, 20], and the references cited there).

The purpose of this work is to give a new nonrecursive combinatorial formula for these polynomials which holds in complete generality. This formula expresses the Kazhdan-Lusztig polynomials as a linear combination of polynomials whose coefficients have a simple combinatorial interpretation in terms of a family of lattice paths that we call slaloms. Our proof uses the theory of quasisymmetric functions and in particular a new basis of the peak subalgebra of the algebra of quasisymmetric functions. We also investigate linear relations arising from the enumeration of Bruhat paths and show, in particular, that the formula that we have obtained cannot be linearly simplified.

<footnote n="1">¹Università di Roma Tor Vergata, Italy</footnote>

<footnote n="2">²Università di Bologna, Italy</footnote>

<footnote>*Part of this work was carried out while the authors were guests at the Mathematisches Forschungsinstitut Oberwolfach as part of their RiP Program. They would like to thank the MFO for its support and for providing an ideal environment for research.</footnote>

<footnote>†Email: brenti@mat.uniroma2.it</footnote>

<footnote>‡Email: fabrizio.caselli@unibo.it</footnote>
## 2 Notation and preliminaries

For $a \in \mathbb{N}$ we let $[a] \stackrel{\text{def}}{=} \{1, 2, \dots, a\}$ (where $[0] \stackrel{\text{def}}{=} \emptyset$). Given $n, m \in \mathbb{N}$, $n \le m$, we let $[n, m] \stackrel{\text{def}}{=} [m] \setminus [n-1]$, and we define similarly $(n, m)$, $(n, m)$, and $[n, m)$. For $S \subseteq \mathbb{Q}$ we write $S = \{a_1, \dots, a_r\} <$ to mean that $S = \{a_1, \dots, a_r\}$ and $a_1 < \dots < a_r$. Given a polynomial $P(q)$, and $i \in \mathbb{Z}$, we denote by $[q^i](P(q))$ the coefficient of $q^i$ in $P(q)$. We let $f_n$ be the $n$-th Fibonacci number defined recursively by $f_0 = 0$, $f_1 = 1$ and $f_n = f_{n-1} + f_{n-2}$ for $n > 1$.

We let $\mathbf{2} \stackrel{\text{def}}{=} \{0, 1\}$ and for $n \in \mathbb{N}$ we let $\mathbf{2}^n$ be the set of all 0-1 words of length $n$

$$ \mathbf{2}^n = \{E = (E_1 \cdots E_n) : E_i \in \mathbf{2}\}, $$

we let $\epsilon \in \mathbf{2}^0$ be the empty word, and $\mathbf{2}^* \stackrel{\text{def}}{=} \cup_{n \ge 0} \mathbf{2}^n$. We consider on $\mathbf{2}^*$ the monoid structure given by concatenation. We say that $E \in \mathbf{2}^*$ is sparse if either $E = \epsilon$ or $E$ belongs to the submonoid generated by 0 and 01 and we let $\mathbf{2}_s^*$ be the monoid of sparse sequences. We also let $12^* \stackrel{\text{def}}{=} \{1E : E \in \mathbf{2}^*\}$ and we similarly define $2^*$. If $E \in \mathbf{2}^n$ we let $\dot{E} = (E_1 \cdots E_{n-1}(1-E_n))$ if $n \ge 1$, and $\dot{\epsilon} = \epsilon$. We also let $\overline{E}$ be the complementary string (so the $i$-th element of $\overline{E}$ is 1 if and only if the $i$-th element of $E$ is 0, for $i \in n$). Finally, we let $m_0(E) = |\{j \in [n] : E_j = 0\}$ and $S(E) = \{i \in [n] : E_i = 1\}$.

Let $n \in \mathbb{N}$. A lattice path of length $n$ is a function $\Gamma : [0, n] \to \mathbb{Z}$ such that $\Gamma(0) = 0$ and $|\Gamma(i) - \Gamma(i-1)| = 1$ for all $i \in [n]$ and we denote by $\mathcal{L}(n)$ the set of all the lattice paths of length $n$. Given $\Gamma \in \mathcal{L}(n)$ we let $N(\Gamma) \in \mathbf{2}^{n-1}$ be given by

$$ N(\Gamma)_i = 1 \iff \Gamma(i) < 0. $$

We also let $d_+(\Gamma) \stackrel{\text{def}}{=} |\{i \in [n] : \Gamma(i) - \Gamma(i-1) = 1\}|$.

Given $E \in \mathbf{2}^{n-1}$ we define, following [5, §5.4], a polynomial $\Upsilon_E(q) \in \mathbb{Z}[q]$ by

$$ \Upsilon_E(q) = (-1)^{m_0(E)} \sum_{\{\Gamma \in \mathcal{L}(n) : N(\Gamma) = E\}} (-q)^{d_+(\Gamma)}. \quad (1) $$

## 3 Dual Bayer-Billera relations

Let $\mathcal{Y}_n$ be the $\mathbb{Q}$-vector space of functions on $\mathbf{2}^n$ taking values in $\mathbb{Q}$. In particular, $\dim_{\mathbb{Q}}(\mathcal{Y}_n) = 2^n$. If $\alpha \in \mathcal{Y}_n$ and $E \in \mathbf{2}^n$ we let $\alpha_E \stackrel{\text{def}}{=} \alpha(E)$ be the value that $\alpha$ takes on $E$.

Let $P$ be an Eulerian partially ordered set of rank $n+1$ with minimum $\hat{0}$ and maximum $\hat{1}$. Given a chain $C = (\hat{0}, x_1, \dots, x_k, \hat{1})$ from $\hat{0}$ to $\hat{1}$ in $C$, we let $E(C) \in \mathbf{2}^n$ given by

$$ E(C)_i = 1 \iff \exists j \in [k] : \rho(x_j) = i, $$

where $\rho$ is the rank function of $P$. We define the flag f-vector of $P$ as the element $f(P) \in \mathcal{Y}_n$ given by

$$ f(P)_E \stackrel{\text{def}}{=} |\{\text{chains } C \text{ in } P \text{ from } \hat{0} \text{ to } \hat{1} : E(C) = E\}| $$

for all $E \in \mathbf{2}^n$.

Let $\mathcal{A}_n$ be the subspace of $\mathcal{Y}_n$ generated by the flag f-vectors $f(P)$ of all Eulerian posets of rank $n+1$.
**Theorem 3.1 (Bayer-Billera)** The vector space $\mathcal{A}_n$ has dimension $f_{n+1}$ and it is determined by the following linear relations: given $\alpha \in \mathcal{Y}_n$ we have $\alpha \in \mathcal{A}_n$ if and only if for all $E \in \mathbf{2}^*1 \cup \{\epsilon\}, F \in \mathbf{12}^* \cup \{\epsilon\}$ and $j \ge 2$ such that $E0^jF \in \mathbf{2}^n$, we have

$$ \sum_{i=1}^{j} (-1)^{j-1} \alpha_{E 0^{i-1} 10^{j-i} F} = (1 + (-1)^{j-1}) \alpha_{E 0^j F}. $$

We call the relations that appear in Theorem 3.1 the *Bayer-Billera relations*.

If $P$ is a graded poset of rank $n+1$, the function $h(P) \in \mathcal{Y}_n$ uniquely determined by

$$ f(P)_F = \sum_{E \le F} h(P)_E $$

is called the *flag h-vector* of $P$; here we have used the partial order on $\mathbf{2}^n$ given by $E \le F$ if $E_i \le F_i$ for all $i \in [n]$. The vector subspace $\mathcal{B}_n$ of $\mathcal{Y}_n$ generated by the flag h-vectors of all Eulerian posets of rank $n+1$ has clearly dimension $f_{n+1}$ by Theorem 3.1 and plays an important role in geometric and algebraic combinatorics.

It is therefore a natural problem to describe a set of linear relations that define the subspace $\mathcal{B}_n$. It is well-known that if $\beta \in \mathcal{B}_n$ then $\beta_F = \beta_{\bar{F}}$ for all $F \in \mathbf{2}^n$. These, however are only $2^{n-1}$ relations, while at least $2^n - f_{n+1}$ are needed.

**Theorem 3.2** Let $\beta \in \mathcal{Y}_n$. Then $\beta \in \mathcal{B}_n$ if and only if for all $E, F \in \mathbf{2}^*$ such that $EF \in \mathbf{2}^n$

$$ \beta_{EF} + \beta_{\bar{E}F} = \beta_{E\bar{F}} + \beta_{\bar{E}\bar{F}}. \qquad (2) $$

We refer to the relations appearing in (2) as the *dual Bayer Billera-relations*. Note that the relations $\beta_F = \beta_{\bar{F}}$ appear as a special case of (2) by letting $E = \epsilon$.

# 4 A new basis for the peak algebra

In this section, using the result in the previous one, we define a new basis for the peak subalgebra of the algebra of quasisymmetric functions, and show how to expand any peak quasisymmetric function as a linear combination of elements of this basis. This result is then used in the next section in the proof of our main result.

We refer to [22, §7.19] for quasisymmetric functions notation and terminology. So let $\mathcal{Q}$ be the algebra of quasisymmetric functions with rational coefficients. If $E \in \mathbf{2}^{n-1}$ and $S(E) = \{s_1, \dots, s_t\}$< we let $\lambda(E) = (n - s_t, s_t - s_{t-1}, \dots, s_2 - s_1, s_1)$; $\lambda(E)$ is a composition of $n$ and we simply denote by $M_E$ the monomial quasisymmetric $M_{\lambda(E)}$. In turn, for $F \in \mathbf{2}^n$, we denote by $L_F = \sum_{E \le F} M_E$ the fundamental quasisymmetric functions. The peak algebra $\Pi = \oplus \Pi_n$ is a graded subalgebra of $\mathcal{Q}$ whose homogeneous components $\Pi_n$ can be defined as follows:

$$ \Pi_n \stackrel{\text{def}}{=} \left\{ \sum_{E \in \mathbf{2}^{n-1}} \beta_E L_E : \beta \in \mathcal{B}_{n-1} \right\} $$

for all $n > 0$, and $\Pi_0 \stackrel{\text{def}}{=} \mathcal{Q}$. In this section we define a family of quasisymmetric functions and show that the ones that are nonzero are a basis for the peak algebra.
For $E \in \mathbf{2}^{n-1}$ let $\partial(E) \stackrel{\text{def}}{=} \{i \in [n-2] : E_i \neq E_{i+1}\} \cup \{n-1\}$. For $T \in \mathbf{2}^{n-1}$ let $S(T) = \{s_1, \dots, s_t\}_{<, s_0} \stackrel{\text{def}}{=} 0$ and $s_{t+1} \stackrel{\text{def}}{=} n$. We let $\mathcal{G}(T)$ be the set of all $E = \mathbf{2}^{n-1}$ such that if $\{x_1, \dots, x_{p_j}\}_{<, s_0} \stackrel{\text{def}}{=} \partial(E) \cap (s_j, s_{j+1})$ then

i) $x_1 \equiv x_2 \equiv \dots \equiv x_{p_j} \pmod{2}$ for all $j \in [0, t]$;

ii) $p_j \ge 1$ for all $j \in [0, t-1]$.

Given such an $E$ we define $\operatorname{sgn}(E, T) \stackrel{\text{def}}{=} (-1)^{\sum_{j=0}^{t-1}(s_{j+1}-y_j-1)}$ where $y_j$ is any element of $\partial(E) \cap (s_j, s_{j+1})$ for $j \in [0, t-1]$, and we let

$$D_T \stackrel{\text{def}}{=} \sum_{E \in \mathcal{G}(T)} \operatorname{sgn}(E, T) L_E.$$

Note that $\mathcal{G}(T) = \emptyset$, and hence $D_T = 0$, if $T$ is not sparse. Given $E, T \in \mathbf{2}^{n-1}$ we let

$$h_{E,T} = \begin{cases} \operatorname{sgn}(E,T), & \text{if } E \in \mathcal{G}(T), \\ 0, & \text{otherwise.} \end{cases} \qquad (3)$$

The next property is crucial in the proof of the main result of this section.

**Theorem 4.1** Let $T \in \mathbf{2}^{n-1}$. Then the function $\mathbf{2}^{n-1} \to \mathbb{Q}$ given by $E \mapsto h_{E,T}$ satisfies the dual Bayer-Billera relations. In particular $D_T \in \Pi_n$.

The following result shows that the functions $D_T$, as $T$ varies in $\mathbf{2}_s^*$ together with 1 form a linear basis for the peak algebra $\Pi$.

**Theorem 4.2** The set $\{D_T : T \in \mathbf{2}_s^*\} \cup \{1\}$ is a basis of $\Pi$. Furthermore, if

$$F = \sum_{E \in \mathbf{2}^*} h_E L_E \in \Pi \implies F = \sum_{E \in \mathbf{2}_s^*} h_E D_E.$$

# 5 Main result

In this section, using the results in the two previous ones, we prove our main result, namely a nonrecursive combinatorial formula for the Kazhdan-Lusztig polynomials which holds in complete generality, and which is simpler and more explicit than any existing one. The formula involves a new set of lattice paths which we call slalom paths.

We follow [5] for general Coxeter groups notation and terminology. We will always assume that a Coxeter group $W$ is partially ordered by Bruhat order.

Recall (see [18, §8.6], or [9]) 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} \in T$ and $l(x) < l(y)$, where $T$ is the set of reflections of $W$.

Let $\Phi^+$ denote the set of positive roots of a Coxeter system $(W, S)$; we say that a total ordering $<$ on $\Phi^+$ is a reflection ordering if whenever $\alpha, \beta, c_1\alpha + c_2\beta \in \Phi^+$ for some $c_1, c_2 \in \mathbb{R}_{>0}$ and $\alpha < \beta$ then $\alpha < c_1\alpha + c_2\beta < \beta$. The existence of reflection orderings (and many of their properties) is proved in [10, §2] (see also [5, §5.2]).
By means of the canonical bijection between $\Phi^+$ and $T$ we transfer the reflection ordering also on $T$. So let $u, v \in W$, $u \le v$ in Bruhat order and $<$ a reflection ordering on $\Phi^+$ (and hence on $T$). Given a path $\Delta = (a_0, a_1, \dots, a_r)$ in $B(W, S)$ from $a_0$ to $a_r$, we define its length to be $l(\Delta) \stackrel{\text{def}}{=} r$, and its descent string with respect to $<$ to be the sequence $E_<(\Delta) \in \mathbf{2}^{r-1}$ given by

$$E_<(\Delta)_{r-i} = 1 \Leftrightarrow a_i (a_{i-1})^{-1} >_T a_{i+1} (a_i)^{-1}.$$

Given $u, v \in W$, and $k \in \mathbb{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) \stackrel{\text{def}}{=} \bigcup_{k \ge 0} B_k(u, v)$. For $u, v \in W$, and $E \in \mathbf{2}^{n-1}$, we let, following [6],

$$c(u, v)_E \stackrel{\text{def}}{=} |\{\Delta \in B_n(u, v) : E_<(\Delta) \le E\}|, \quad (4)$$

and

$$b(u, v)_E \stackrel{\text{def}}{=} |\{\Delta \in B_n(u, v) : E_<(\Delta) = E\}|. \quad (5)$$

Note that these definitions imply that

$$c(u, v)_F = \sum_{E \le F} b(u, v)_E \quad (6)$$

for all $u, v \in W$ and $F \in \mathbf{2}^{n-1}$. It follows immediately from Proposition 4.4 of [6] that $c(u, v)_E$ (and hence $b(u, v)_E$) are independent of the total reflection ordering $<$ used to define them. The following result is known (see [7, Theorem 8.4] and [3, Theorem 2.2]).

**Theorem 5.1** Let $u, v \in W$. Then $c(u, v) \in \mathcal{A}_n$ (and so $b(u, v) \in \mathcal{B}_n$) for all $n \ge 0$. We have the following result (see [5, Theorem 5.5.7]).

**Theorem 5.2** Let $u, v \in W$, $u < v$. Then

$$P_{u,v}(q) - q^{\ell(u,v)} P_{u,v}\left(\frac{1}{q}\right) = \sum_{E \in \mathbf{2}^*} q^{\frac{\ell(u,v)-\ell(E)-1}{2}} \Upsilon_E(q) b(u,v)_E.$$

Next goal is to simplify Theorem 5.1 using the dual Bayer-Billera relations which are satisfied by the function $b(u, v)$. Let $T \in \mathbf{2}^{n-1}$, $T \stackrel{\text{def}}{=} \{s_1, \dots, s_t\}_{<}$, $s_0 \stackrel{\text{def}}{=} 0$, $s_{t+1} \stackrel{\text{def}}{=} n$. We define $\mathcal{J}(T)$ to be the set of all $E \in \mathbf{2}^{n-1}$ such that:

i) $|\partial(E) \cap (s_j, s_{j+1})| = 1$ for all $j \in [0, t-1]$;

ii) $|\partial(E) \cap (s_t, s_{t+1})| \le 2$;

iii) if $\partial(E) \cap (s_t, s_{t+1}) = \{x, n-1\}$ then $x \equiv n-1 \pmod 2$.

Given such an $E$ we define $\operatorname{sgn}(E, T) \stackrel{\text{def}}{=} (-1)^{\sum_{i=1}^t (s_i - x_i - 1)}$ where $\{x_i\} \stackrel{\text{def}}{=} \partial(E) \cap (s_{i-1}, s_i)$ for $i \in [t]$ and let

$$\Omega_T(q) \stackrel{\text{def}}{=} \sum_{E \in \mathcal{J}(T)} \operatorname{sgn}(E, T) \Upsilon_E(q).$$

So, for example, if $T = 00100$, then $\mathcal{J}(T) = \{01111, 01100, 00111, 00100, 10000, 10011, 11000, 11011\}$ and $\Omega_T(q) = -\Upsilon_{01111} - \Upsilon_{01100} + \Upsilon_{00111} + \Upsilon_{00100} - \Upsilon_{10000} - \Upsilon_{10011} + \Upsilon_{11000} + \Upsilon_{11011} = \Upsilon_{00111} +$
$\Upsilon_{00100} - \Upsilon_{10000} = q^5 - 2q^4 + 2q^2 - q$. Note that $\mathcal{J}(T) = \emptyset$ if $T$ is not sparse, and that $\mathcal{J}(T) \subseteq \mathcal{G}(T)$. For $u < v$ let $\tilde{F}_{u,v} \stackrel{\text{def}}{=} \sum_{E \in \mathcal{2}^*} b(u, v)_E L_E$. It follows from Theorem 2.2 of [3] that $\tilde{F}_{u,v} \in \Pi$ and so by Theorem 4.2 we have that $\tilde{F}_{u,v} = \sum_{T \in \mathcal{2}_s^*} b(u, v)_T D_T$. This is the main ingredient in the proof of the following result.

**Theorem 5.3** Let $(W, S)$ be a Coxeter system and $u, v \in W$, $u < v$. Then

$$P_{u,v}(q) - q^{\ell(u,v)} P_{u,v} \left(\frac{1}{q}\right) = \sum_{T \in \mathcal{2}_s^*} q^{\frac{\ell(u,v)-\ell(T)-1}{2}} b(u,v)_T \Omega_T(q).$$

We illustrate the preceding theorem with some examples. If $\ell(u, v) = 2$ we obtain

$$P_{u,v}(q) - q^2 P_{u,v} \left(\frac{1}{q}\right) = b_0 \Omega_0(q) = \Upsilon_0 + \Upsilon_1 = q - q^2 + 1 - q = 1 - q^2$$

(where we have used the fact that $b(u, v)_0 = 1$ if $\ell(u, v) = 2$) and if $\ell(u, v) = 3$

$$\begin{align*}
P_{u,v}(q) - q^3 P_{u,v} \left(\frac{1}{q}\right) &= q^{\frac{2-2}{2}} (b_{00} \Omega_{00}(q) + b_{01} \Omega_{01}(q)) + q^{\frac{2-0}{2}} (b_{\varepsilon} \Omega_{\varepsilon}(q)) \\
&= b_{00}(1 - 2q + 2q^2 - q^3) + b_{01}(q - q^2) + q(b_{\varepsilon}(1-q)) \\
&= 1 + q(-2 + b_{01} + b_{\varepsilon}) - q^2(-2 + b_{01} + b_{\varepsilon}) - q^3.
\end{align*}$$

We feel that the formula obtained in Theorem 5.3 is the simplest and most explicit nonrecursive combinatorial formula known for the Kazhdan-Lusztig polynomials that holds in complete generality. In fact, this formula, as the one in [3, Corollary 3.2], expresses the Kazhdan-Lusztig polynomial of $u, v \in W$ as a sum of at most $f_{\ell(u,v)}$ summands, as opposed to $2^{\ell(u,v)} + 2^{\ell(u,v)-2} + \dots$ for the one obtained in [7, Theorem 7.2], each one of which is the product of a number, which depends on $u, v$, and $W$, with a polynomial, that is independent of $u, v$, and $W$. However, this formula is more explicit than the one obtained in [3, Corollary 3.2] since in the formula obtained in [3] the polynomials have a combinatorial interpretation, but no combinatorial interpretation is known for the numbers, while in the formula obtained in Theorem 5.3 both the numbers and the polynomials have a combinatorial interpretation, as we now show.

Let $T \in \mathcal{2}_s^{n-1}$ be a sparse sequence of length $n-1$ with $S(T) = \{s_1, \dots, s_t\}$. Let $\mathcal{L}(T)$ be the set of all lattice paths of length $n$ such that $N(\Gamma) \in \mathcal{J}(T)$. For $\Gamma \in \mathcal{L}(T)$ we let $\varepsilon_T(\Gamma) = \text{sgn}(N(\Gamma), T)$ and $\eta(\Gamma) = |j \in [n-1] : \Gamma(j) \ge 0|$. We will usually write $\varepsilon(\Gamma)$ instead of $\varepsilon_T(\Gamma)$ when the sparse sequence $T$ is clear from the context.

**Example 5.4** Let $T = 0010001000$ and so $S(T) = \{3, 7\}$ and $n = 11$. A path in $\mathcal{L}(T)$ is a lattice path of length 11 that crosses the two dotted segments in Figure 1 exactly once, and crosses the dotted-solid segment at most once, but only if $\Gamma(n-1) \ge 0$. The path in Figure 1 therefore belongs to $\mathcal{L}(T)$ with $x_1 = 2$, $x_4 = 5$ and $x = 8$. Hence we have $\varepsilon(\Gamma) = (s_1 - x_1 - 1) + (s_2 - x_2 - 1) = 1$. Moreover, we have $\eta(\Gamma) = 4$ and $d_+(\Gamma) = 5$.
<figure><img src="image_1.png" /><figcaption>Fig. 1: A path in $\mathcal{L}(0010001000)$.</figcaption></figure>

<figure><img src="image_2.png" /><figcaption>Fig. 2: The constraints of a slalom path associated to $T = 0001000010001000$.</figcaption></figure>

The following formula is a direct consequence of the definitions of the polynomials $\Omega_T$ and $\Upsilon_E$. For $T \in \mathbf{2}_s^*$ we have

$$ \Omega_T = \sum_{\Gamma \in \mathcal{L}(T)} (-1)^{\varepsilon(\Gamma) + \eta(\Gamma) + d_+(\Gamma)} q^{d_+(\Gamma)}. $$

Our next target is to simplify this formula and in particular to find a combinatorial interpretation for the coefficients of $\Omega_T$. For this we introduce the following notation: for $T \in \mathbf{2}_s^{n-1}$ let

$$ \mathcal{L}_0(T) \stackrel{\text{def}}{=} \{ \Gamma \in \mathcal{L}(T) : \Gamma(s_1 + 1) \cdot \Gamma(s_2 + 1) \cdots \Gamma(s_t + 1) \cdot \Gamma(n) = 0 \}. $$

For example the path $\Gamma$ depicted in Figure 1 belongs to $\mathcal{L}_0(0010001000)$ as $\Gamma(4) = 0$.

**Proposition 5.5** We have

$$ \sum_{\Gamma \in \mathcal{L}_0(T)} (-1)^{\varepsilon(\Gamma) + \eta(\Gamma) + d_+(\Gamma)} q^{d_+(\Gamma)} = 0. $$

**Idea of proof:** The result follows from the existence of an involution $\phi : \mathcal{L}_0(T) \to \mathcal{L}_0(T)$ such that $d_+(\Gamma) = d_+(\phi(\Gamma))$ and $\varepsilon(\Gamma) + \eta(\Gamma) \equiv \varepsilon(\phi(\Gamma)) + \eta(\phi(\Gamma)) + 1 \pmod{2}$ for all $\Gamma \in \mathcal{L}_0(T)$.
<figure><img src="image_3.png" /><figcaption>Fig. 3: A slalom in $SL(0001000010001000)$.</figcaption></figure>

Proposition 5.5 leads us to consider the set of slaloms associated to a sparse sequence $T \in 2_s^*$, (see Figure 2 for an illustration in the case $T = 0001000010001000$, and so $S(T) = \{4, 9, 13\}$ and $n = 17$).

Let $T \in 2_s^{n-1}$. We say that a lattice path $\Gamma \in \mathcal{L}(n)$ is a T-slalom if

* $\Gamma$ does not pass through the points $(s_i + 1, 0)$, $i \in [t]$, and $(n, 0)$ (the “stars” in the example in Fig. 2);

* $\Gamma$ crosses the segment $\{y = -\frac{1}{2}, x \in [s_t + 1, n-1]\}$ (the dotted-solid segment in Fig. 2) at most once and only if $(-1)^n \Gamma(n) > 0$;

* $\Gamma$ crosses the segment $\{y = -\frac{1}{2}, x \in [s_{i-1} + 1, s_i]\}$ (the dotted segments in Fig. 2) exactly once for all $i \in [t]$.

We denote by $SL(T)$ the set of T-slaloms. Figure 3 shows an example of a 0001000010001000-slalom.

For $T \in 2_s^{n-1}$ let $e(T)$ be the number of even elements in $S(T)$. The next result shows that if $\Gamma \in SL(T)$, then the class of $\varepsilon(\Gamma) + \eta(\Gamma) \pmod 2$ depends on $T$ and the sign of $\Gamma(n)$ only.

**Theorem 5.6** Let $T \in 2_s^{n-1}$, $S(T) = \{s_1, \dots, s_t\}$ and $\Gamma \in SL(T)$. Then

$$ \varepsilon(\Gamma) + \eta(\Gamma) \equiv e(T) + (n-1)\chi(\Gamma(n) > 0) \pmod 2. $$

**Corollary 5.7** Let $T$ be sparse and $S(T) = \{s_1, \dots, s_t\}$. Then

$$ |[q^i]\Omega_T| = |\{\Gamma \in SL(T) : \Gamma(n) = n - 2i\}|. $$

and the sign of $[q^i]\Omega_T$ is $(-1)^{i+e(T)+\chi(2i>n)(n-1)}$.

# 6 On the complete cd-index

Let $W$ be a Coxeter group, $< a $ reflection ordering, $u, v \in W$, $\Delta \in B_{n+1}(u, v)$ and $E = E_<(\Delta)$. We consider the monomial $m_<(\Delta) \stackrel{\text{def}}{=} a^{E_1} b^{1-E_1} \dots a^{E_n} b^{1-E_n} \in \mathbb{Z}\langle a, b \rangle$, the polynomial ring with integer coefficients in two noncommuting variables $a$ and $b$.

If $[u, v]$ is a Bruhat interval of length $r+1$ the polynomial

$$ \Psi_{u,v} \stackrel{\text{def}}{=} \sum_{\Delta \in B_{r+1}(u,v)} m_<(\Delta) \in \mathbb{Z}\langle a, b \rangle, $$
where < is any reflection ordering, turns out to be a polynomial in the variables $c = a+b$ and $d = ab+ba$, which does not depend on <: in fact one can show that it agrees with the cd-index of the Eulerian poset $[u, v]$. We consider the natural extension of this polynomial to all paths in the Bruhat graph

$$ \tilde{\Psi}_{u,v}(a, b) \stackrel{\text{def}}{=} \sum_{\Delta \in B(u,v)} m_{<}(\Delta). $$

The polynomial $\tilde{\Psi}$ has been introduced by Billera and the first author in [3]. It is a consequence of Theorem 3.1 that also $\tilde{\Psi}_{[u,v]}$ is a polynomial in the variables $c = a+b$ and $d = ab+ba$ and therefore it is called the complete cd-index of the interval $[u, v]$.

The main goal of this section is to study the complete cd-index of some classes of Bruhat intervals and to show that, for all $r \in \mathbb{N}$, the homogeneous components of degree $r-2i$ of the complete cd-indices of Bruhat intervals of rank $r+1$ span the whole space of homogeneous cd-polynomials of degree $r-2i$. An immediate consequence is the following result, which shows, in particular, that the formula appearing in Theorem 5.3 cannot be “linearly” simplified.

**Proposition 6.1** Let $a_T \in \mathbb{Q}$, $T \in \mathfrak{2}_s^*$, be such that $\sum_{T \in \mathfrak{2}_s^*} a_T b(u, v)_T = 0$ for all Coxeter groups $W$ and all $u, v \in W$. Then $a_T = 0$ for all $T \in \mathfrak{2}_s^*$.

We conjecture that the following result, which is stronger than Proposition 6.1, is still true.

Let $r > 0$ be fixed and $a_T \in \mathbb{Q}$, $T \in \mathfrak{2}_s^* \cup \mathfrak{2}_s^{r-2} \cup \dots$ be such that $\sum a_T b(u, v)_T = 0$ for all Coxeter group and all $u, v \in W$ such that $\ell(v) - \ell(u) = r + 1$. Then $a_T = 0$ for all $T \in \mathfrak{2}_s^* \cup \mathfrak{2}_s^{r-2} \cup \dots$. We have verified this conjecture for $r \le 17$.

We need a general construction about reflection orderings. Let $(W, S)$ be a Coxeter system, $\Pi$ be the associated set of simple roots, and $\Phi^+$ the associated set of positive roots. A weight function on $\Phi^+$ is a map $p: \Phi^+ \to \mathbb{R}_{\ge 0}$ which is linear, in the sense that if $\beta = c_1\beta_1 + c_2\beta_2$, with $\beta, \beta_1, \beta_2 \in \Phi^+$ and $c_1, c_2 \in \mathbb{N}$, then $p(\beta) = c_1p(\beta_1) + c_2p(\beta_2)$. It is clear that a weight function $p$ is uniquely determined by its images on $\Pi$ and that the set $\Phi_0^+(p) = \{\beta \in \Phi^+ : p(\beta) = 0\}$ is the set of positive roots of a parabolic subgroup of $W$. Let $I = (\alpha_1, \dots, \alpha_l)$ be an indexing (total ordering) of the elements in $\Pi$. Then the associated lexicographic order on the root space $\mathbb{R}\alpha_1 \oplus \dots \oplus \mathbb{R}\alpha_l$ is given by $\sum c_i\alpha_i < \sum d_i\alpha_i$ if $(c_1, \dots, c_l)$ is smaller than $(d_1, \dots, d_l)$ lexicographically.

Let $W$ be a Coxeter group, $p$ be a weight function on $\Phi^+(W)$, and $W'$ the parabolic subgroup of $W$ given by $\Phi^+(W') = \Phi_0^+(p)$. Let $<$ be a reflection ordering on $\Phi^+(W')$ and $I$ an indexing of $\Pi$. Then we define a total ordering $\ll$ on $\Phi^+$ depending on $p, <, I$ in the following way: for $\beta, \beta' \in \Phi^+$ we let $\beta \ll \beta'$ if one of the following conditions apply

* $p(\beta) = p(\beta') = 0$ and $\beta < \beta'$;

* $p(\beta) \neq 0$ and $p(\beta') = 0$;

* $p(\beta), p(\beta') \neq 0$ and $\frac{\beta}{p(\beta)} < \frac{\beta'}{p(\beta')}$ in the lexicographic order associated to $I$.

It is clear that $\ll$ is a total ordering on $\Phi^+(W)$.

**Proposition 6.2** The total ordering $\ll$ on $\Phi^+(W)$ constructed above is a reflection ordering.

Proposition 6.2 allows us to construct reflection ordering satisfying some desirable properties.
**Corollary 6.3** Let $(W, S)$ be a Coxeter system and $P$ the maximal parabolic subgroup generated by $S \setminus \{s\}$, for some $s \in S$. Then there exists a reflection ordering $\ll$ on $\Phi^+$ such that

* $t \ll s$ for every reflection $t$ in $W$;

* if $t$ is a reflection in $P$ then $t \ll \text{sts}$;

* if $t$ and $t'$ are reflections in $P$ then $t \ll t'$ if and only if $\text{sts} \ll \text{st}'s$.

Let $(W, S)$ be a Coxeter system and $[u, v]$ be an interval in $W$. We say that an interval $[u, vs]$ is a *pyramid* over $[u, v]$ if $s \in S$ and $s \not\le v$. The name pyramid comes from the fact that if $[u, v]$ is isomorphic as a poset to the face lattice of a polytope $P$ then $[u, vs]$ is isomorphic to the face lattice of a pyramid over $P$. The following result states that the complete cd-index of a pyramid over a Bruhat interval $[u, v]$ depends uniquely on the complete cd-index of $[u, v]$, generalizing the corresponding result for the standard cd-index proved by Ehrenborg and Readdy in [12]. Its proof uses the reflection ordering constructed in Corollary 6.3.

**Theorem 6.4** Let $(W, S)$ be a Coxeter system, $u, v \in W$, $u < v$, and $s \in S$ be such that $s \not\le v$. Then

$$ \tilde{\Psi}_{u,vs} = c\tilde{\Psi}_{u,v} + G(\tilde{\Psi}_{u,v}), $$

where $G$ denotes the derivation on the algebra of cd-polynomials given by $G(c) = d$ and $G(d) = dc$.

Let $(W, S)$ be a Coxeter system such that $m(s, s') = 3$ for all $s, s' \in S$, $s \neq s'$. We call this the 3-complete Coxeter system. The following result can be interpreted as a concrete criterion to determine the set of (left) descents of a generic element in a 3-complete Coxeter group: it will be used in the sequel in the construction of reflection orderings, but has some interest in its own right.

Let $(W, S)$ be a 3-complete Coxeter system, $S = \{s_1, \dots, s_l\}$, $l > 1$, and let $W'$ be the parabolic subgroup of $W$ generated by $S \setminus \{s_1\}$. We also let $\Pi = \{\alpha_1, \dots, \alpha_l\}$ where $\alpha_i$ is the simple root corresponding to $s_i$ for all $i \in [l]$.

We will consider the $W'$-orbit of the simple root $\alpha_1$ to study the sets of left descents of elements in $W'$. We adopt the following notation: for all $w \in W'$ we let $c_i(w), d_i(w) \in \mathbb{Z}$, $i \in [l]$, be given by

$$ w(\alpha_1) = \sum_{i=1}^{l} c_i(w)\alpha_i $$

and $d_i(w) \stackrel{\text{def}}{=} 2c_i(w) - \sum_{k \neq i} c_k(w)$.

**Proposition 6.5** Let $w \in W'$ and $i \in [2, l]$. Then $d_i(w) \neq 0$ and

$$ d_i(w) > 0 \Leftrightarrow i \in \text{Des}_L(w). $$

Let $(W, S)$ be a 3-complete Coxeter system. Let $r, s \in S$, $r \neq s$. We consider the weight $p$ given by $p(\alpha) = 1$ for all $\alpha \in \Pi \setminus \{\alpha_r\}$ and $p(\alpha_r) = 2$. We also consider an indexing $I$ of $\Pi = \{\alpha_1, \alpha_2, \dots, \alpha_l\}$ such that $\alpha_1 = \alpha_s$ and $\alpha_2 = \alpha_r$ and we let $\ll$ be the unique reflection ordering associated to $p$ and $I$. Proposition 6.5 is the main ingredient in the proof of the following properties satisfied by $\ll$.
**Lemma 6.6** Let $P$ be the parabolic subgroup of $W$ generated by $S \setminus \{r, s\}$; for every $t, z, w \in P$, $t$ a reflection, $\ell(z) \ge 2$, we have $t \ll szsz^{-1}s \ll sts \ll s$ and $t \ll swrw^{-1}s \ll sts$.

The ordering $\ll$ is the one that is used in the proof of the following result.

**Theorem 6.7** Let $(W, S)$ be a 3-complete Coxeter system. Let $r, s \in S$, $r \neq s$, and $P$ be the parabolic subgroup generated by $S \setminus \{s, r\}$. Then for all $v \in P$, $v \neq e$, we have

$$ \tilde{\Psi}_{e,svs} + d \cdot \tilde{\Psi}_{e,v} = \tilde{\Psi}_{e,rvs} + \tilde{\Psi}_{e,v}. $$

Following an idea of Reading [21], we consider a set $W_n$ of elements in the 3-complete Coxeter group $W$ of rank $n+1$ generated by $s_1, \dots, s_{n+1}$ constructed recursively in the following way: we let $W_0 = \{s_1\}$, $W_1 = \{s_1s_2\}$ and, for $n \ge 2$,

$$ W_n = \{ws_{n+1} : w \in W_{n-1}\} \cup \{s_{n+1}ws_{n+1} : w \in W_{n-2}\}. $$

Let $V_n = \text{Span}\{\tilde{\Psi}_{e,v} : v \in W_n\}$. Since $\ell(v) = n+1$ for all $v \in W_n$ we deduce that $V_n$ is contained in the space of cd-polynomials of degree bounded by $n$. A set of generators for $V_n$ can also be described in the following way. Let $A_0 = \{1\}$, $A_1 = \{c\}$ and

$$ A_n = \{c \cdot P + G(P) : P \in A_{n-1}\} \cup \{(d-1) \cdot P : P \in A_{n-2}\}. $$

By Theorems 6.4 and Theorem 6.7 we have that $A_n$ is a spanning set for $V_n$. We observe that $|A_n| = f_{n+1}$ and we denote its elements by $P_{n,1}, \dots, P_{n,f_{n+1}}$ in the following way. We let $P_{0,1} = 1$, $P_{1,1} = c$ and

$$ P_{n,j} = \begin{cases} G(P_{n-1,j}) & \text{if } 1 \le j \le f_n \\ (d-1)P_{n-2,j-f_n} & \text{if } f_n < j \le f_n + f_{n-1} \end{cases} $$

**Theorem 6.8** Let $k \ge 0$. Then the homogeneous parts of degree $n$ of the polynomials $(d-1)^k P_{n,j}$, for $j \in [f_{n+1}]$, are linearly independent.

We conclude this extended abstract with the result that was announced at the beginning of this section.

**Corollary 6.9** Let $n, k \in \mathbb{N}$. The homogeneous components of degree $n$ of the complete cd-indices of all Bruhat intervals of rank $n + 2k + 1$ span the whole space of cd-polynomials of degree $n$.

## References

[1] H. H. Andersen, *The irreducible characters for semi-simple algebraic groups and for quantum groups*, Proc. of the ICM, Zürich, 1994, 732-743, Birkhäuser, Basel, Switzerland, 1995.

[2] A. Beilinson, J. Bernstein, *Localisation de g-modules*, C. R. Acad. Sci. Paris, **292** (1981), 15-18.

[3] L. Billera and F. Brenti, Quasisymmetric functions and Kazhdan-Lusztig polynomials, Israel J. Math. 184 (2011), 317-348.

[4] S. Billey, V. Lakshmibai, *Singular loci of Schubert varieties*, Progress in Math., **182**, Birkhäuser, Boston, MA, 2000.
[5] A. Björner, F. Brenti, *Combinatorics of Coxeter Groups*, Graduate Texts in Mathematics 231, Springer, New York, 2005.

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

[7] F. Brenti, Lattice paths and Kazhdan-Lusztig polynomials, J. Amer. Math. Soc. 11 (1998), no. 2, 22-259.

[8] J.-L. Brylinski, M. Kashiwara, *Kazhdan-Lusztig conjecture and holonomic system*, Invent. Math. **64** (1981), 387-410.

[9] M. Dyer, On the "Bruhat graph" of a Coxeter system, *Compos. Math.*, **78** (1991), 185-191.

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

[11] R. Ehrenborg, M. Goresky, M. Readdy, *Euler flag enumeration of Whitney stratified spaces*, preprint, 2011. arXiv:1201.3377 [math.CO].

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

[13] B. Elias, G. Williamson, *The Hodge theory of Soergel bimodules*, Ann. Math. to appear.

[14] I. Frenkel, M. Khovanov, A. Kirillov, *Kazhdan-Lusztig polynomials and canonical basis*, Transform. Groups, **3** (1998), 321-336.

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

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

[17] M. Haiman, *Hecke algebra characters and immanant conjectures*, J. Amer. Math. Soc., **6** (1993), 569-595.

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

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

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

[21] N. Reading, The cd-index of Bruhat intervals. Electron. J. Combin. 11 (2004), Res. Pap. 74, 25 pp.

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