# Shortest path poset of finite Coxeter groups

Saúl A. Blanco†

Department of Mathematics, Cornell University, Ithaca, NY, 14853.

**Abstract.** We define a poset using the shortest paths in the Bruhat graph of a finite Coxeter group $W$ from the identity to the longest word in $W$, $w_0$. We show that this poset is the union of Boolean posets of rank absolute length of $w_0$; that is, any shortest path labeled by reflections $t_1, \dots, t_m$ is fully commutative. This allows us to give a combinatorial interpretation to the lowest-degree terms in the complete cd-index of $W$.

**Résumé.** Nous définons un poset en utilisant le plus court chemin entre l'identité et le plus long mot de $W$, $w_0$, dans le graph de Bruhat du groupe finie Coxeter, $W$. Nous prouvons que ce poset est l'union de posets Boolean du même rang que la longueur absolute de $w_0$; ça signifie que tous les plus courts chemins, étiquetés par reflections $t_1, \dots, t_m$ sont totalement commutatives. Ça nous permet de donner une interpretation combinatorique aux terms avec le moindre grade dans le cd-index complet de $W$.

**Keywords:** Coxeter group, Bruhat order, Boolean poset, complete cd-index.

## 1 Introduction

Let $(W, S)$ be a Coxeter system, and let $T(W) = \{wsw^{-1} : s \in S, w \in W\}$ be the set of reflections of $(W, S)$. The Bruhat graph of $(W, S)$, denoted by $B(W, S)$ or simply $B(W)$, is the directed graph with vertex set $W$, and a directed edge $w_1 \to w_2$ between $w_1, w_2 \in W$ if $\ell(w_1) < \ell(w_2)$ and there exists $t \in T(W)$ with $tw_1 = w_2$. $\ell$ denotes the length function of $(W, S)$. The edges of $B(W)$ are labeled by reflections; for instance the edge $w_1 \to w_2$ is labeled with $t$. The Bruhat graph of an interval $[u, v]$, denoted by $B([u, v])$, is the subgraph of $B(W)$ obtained by only considering the elements of $[u, v]$. A path in the Bruhat graph $B([u, v])$, will always mean a directed path from $u$ to $v$. As it is the custom, we will label these paths by listing the edges that are used.

A reflection ordering $<_{T(W)} = <_T$ is a total order of $T(W)$ so that $r <_T rtr <_T rtrtr <_T \dots <_T trt <_T t$ or $t <_T trt <_T trtrt <_T \dots <_T rtr <_T r$ for each subgroup $W' = \{\langle t, r \rangle\}$ where $t, r \in T(W)$. Let $\Delta = (t_1, t_2, \dots, t_k)$ be a path in $B([u, v])$, and define the descent set of $\Delta$ by $D(\Delta) = \{j : t_{j+1} <_T t_j\} \subset [k-1]$.

Let $w(\Delta) = x_1x_2\cdots x_{k-1}$, where $x_i = \mathbf{a}$ if $t_i < t_{i+1}$, and $x_i = \mathbf{b}$, otherwise. In other words, set $x_i$ to $\mathbf{a}$ if $i \notin D(\Delta)$ and to $\mathbf{b}$ if $i \in D(\Delta)$. In [3], Billera and Brenti showed that $\sum_{\Delta \in B([u,v])} w(\Delta)$ becomes

<footnote>†The author was supported in part by NSF grant DMS-0555268.</footnote>
a polynomial in the variables **c** and **d**, where **c** = **a** + **b** and **d** = **a****b** + **ba**. This polynomial is called the complete **cd-index** of [u, v], and it is denoted by $\tilde{\psi}_{u,v}(\mathbf{c}, \mathbf{d})$. Notice that the complete **cd-index** of [u, v] is an encoding of the distribution of the descent sets of each path $\Delta$ in the Bruhat graph of [u, v], and thus seems to depend on $<_T$. However, it can be shown that this is not the case. For details on the complete **cd-index**, see [3].

As an example, consider $A_2$, the symmetric group on 3 elements with generators $s_1 = (1 \ 2)$ and $s_2 = (2 \ 3)$. Then $t_1 = s_1 < t_2 = s_1s_2s_1 < t_3 = s_2$ is a reflection ordering. The paths of length 3 are: $(t_1, t_2, t_3)$, $(t_1, t_3, t_1)$, $(t_3, t_1, t_3)$, and $(t_3, t_2, t_1)$, that encode to $\mathbf{a}^2 + \mathbf{ab} + \mathbf{ba} + \mathbf{b}^2 = \mathbf{c}^2$. There is one path of length 1, namely $t_2$, which encodes simply to 1. So $\tilde{\psi}_{u,v}(\mathbf{c}, \mathbf{d}) = \mathbf{c}^2 + 1$.

Consider the paths in $B([u, v])$ of minimum length. Using these paths, we can define a ranked poset by thinking of the edges of these paths as cover relations. We call this poset $SP([u, v])$, and when the interval $[u, v]$ is the full group, we simply use the notation $SP(W)$. The rank of an element $x$ in $SP([u, v])$ is given by its distance from $u$ (and so if $[u, v]$ is the whole group, the rank of $x$ is given by its distance from the identity $e$). Here we are interested in $SP(W)$, where $W$ is a finite Coxeter group. To illustrate the definition consider $B_2$ and $SP(B_2)$ as depicted below. The rank of $SP(B_2)$ is two since that is the length of the shortest paths in $B(B_2)$.

<figure><img src="image_1.png" /><figcaption>Fig. 1: $B(B_2)$ and $SP(B_2)$.</figcaption></figure>

For any finite Coxeter group, there is a word $w_0^W$ of maximal length. It is a well known fact that $\ell(w_0^W) = |T(W)|$. For any $w \in W$, one can write $t_1t_2\cdots t_n = w$ for some $t_1, t_2, \ldots, t_n \in T(W)$. If $n$ is minimal, then we say that $w$ is $T(W)$-reduced, and that the absolute length of $w$ is $n$. We write $\ell_{T(W)}(w) = n$, or simply $\ell_T(w) = n$.

Notice that for $w \in W$, if $\ell_T(w) = \ell$, then $t_1t_2\cdots t_\ell = w$ for some reflections in $T(W)$, but this *does not* mean that $(t_1, t_2, \ldots, t_\ell)$ is a (directed) path in $B([e, w])$. Nevertheless, we will show that for finite $W$ and $w = w_0^W$, $(t_1, t_2, \ldots, t_\ell)$ and any of its permutations $(t_{\tau(1)}, t_{\tau(2)}, \ldots, t_{\tau(\ell)})$, $\tau \in A_{\ell-1}$, is a path in $B(W)$. To be more specific, we show the following theorem.

**Theorem 1.1** Let $W$ be a finite Coxeter group and $\ell_0 = \ell_{T(W)}(w_0^W)$, the absolute length of the longest element of $W$. Then $SP(W)$ is isomorphic to the union of Boolean posets of rank $\ell_0$.
In Section 2 we present the proof of the theorem for the infinite families (groups of type A, B, and D and Dihedral groups). In Section 3 we discussed the validity of the Theorem for the exceptional groups. Computer search was used for $F_4$, $H_3$, $H_4$, and $E_6$, and a geometric argument was used to prove the case $E_7$ and $E_8$. We summarize the number of Boolean posets that form $SP(W)$ and the rank of $SP(W)$ for each finite Coxeter group in Table 1.

In Section 4 we discuss why Theorem 1.1 implies that the lowest-degree terms of the complete cd-index of $W$ is given by $\alpha_W \tilde{\psi}(B_{\ell_0})$, where $\tilde{\psi}(B_{\ell_0})$ is the cd-index of the Boolean poset of rank $\ell_0 = \ell_{T(W)}(w_0^W)$, and $\alpha_W$ is the number of Boolean posets that form $SP(W)$.

The following lemma will be used in our proofs.

**Lemma 1.2 (Shifting Lemma, [1], Lemma 2.5.1)** If $w = t_1t_2 \cdots t_r$ is a $T(W)$-reduced expression for $w \in W$ and $1 \le i < r$, then $w = t_1t_2 \cdots t_{i-1}(t_i t_{i+1} t_i) t_i t_{i+2} \cdots t_r$ and $w = t_1t_2 \cdots t_{i-2}t_i(t_i t_{i-1} t_i) t_{i+1} \cdots t_r$ are $T(W)$-reduced.

As a consequence, there exists a $T(W)$-reduced expression for $w$ having $t_i$ as last reflection (or first), for $1 \le i \le r$. Furthermore, for any two reflections $t_i, t_j, i < j$ there exists a $T(W)$-reduced expression for $w$ with $t_i, t_j$ as the last two reflections (or the first two).

# 2 Groups of type A, B and D

## 2.1 The poset $SP(A_{n-1})$

**Lemma 2.1** $\ell_{T(A_{n-1})}(w_0^{A_{n-1}}) = \lfloor \frac{n}{2} \rfloor$.

**Proof:** Recall that $w_0^{A_{n-1}}$ is the reverse of the identity $123 \dots n$; that is, $w_0^{A_{n-1}} = n(n-1)(n-2) \dots 21$. So $\ell_{T(A_{n-1})}(w_0^{A_{n-1}}) \ge \lfloor \frac{n}{2} \rfloor$ since a reflection in $A_{n-1}$ is just a transposition, and thus cannot permute more than two elements of $[n]$ at a time.

For $1 \le i \le \lfloor \frac{n}{2} \rfloor = k$, let $r_i$ be the transposition permuting $i$ and $n+1-i$; that is, $r_i = (i \ n+1-i)$. Notice that $r_1 \cdots r_k = w_0^{A_{n-1}}$, and so $\ell_{T(A_{n-1})}(w_0^{A_{n-1}}) \le \lfloor \frac{n}{2} \rfloor$. $\square$

**Lemma 2.2** For $\sigma \in A_{n-1}$, let $k = \lfloor \frac{n}{2} \rfloor$,

$$f^A(\sigma) = \left\lfloor \frac{|\{i \in [n] \mid \sigma(i) = w_0^{A_{n-1}}(i)\}|}{2} \right\rfloor$$

and

$$g^A(\sigma) = \min\{\ell : \text{there exists } t_1, t_2, \dots, t_\ell \in T(A_{n-1}) \text{ with } t_1 t_2 \dots t_\ell \sigma = w_0^{A_{n-1}}\}.$$

$$\text{Then } f^A(\sigma) = i \implies g^A(\sigma) \ge \lfloor \frac{n}{2} \rfloor - i \text{ for } 0 \le i \le \lfloor \frac{n}{2} \rfloor.$$

**Proof:** We proceed by reverse (downward) induction. The case $i = k$ holds, since $g^A$ is a non-negative function. Suppose that the statement holds for $i$. We now show that it also holds for $i-1$. Let $\sigma \in A_{n-1}$ with $f^A(\sigma) = i-1$. Consider $t_1, t_2, \dots, t_\ell \in T(A_{n-1})$ with $t_1 t_2 \cdots t_\ell \sigma = w_0^{A_{n-1}}$ and $\ell = g^A(\sigma)$. Notice that there exists a positive integer $m$ with $f^A(t_{\ell-m+1} t_{\ell-m+2} \cdots t_\ell \sigma) = i$, since $f^A(t_1 t_2 \cdots t_\ell \sigma) = k$ and a reflection can fix at most two elements in their position in $w_0^{A_{n-1}}$, and so $f^A(t_\tau) \le f^A(\tau) + 1$ for $t \in T(A_{n-1})$ and $\tau \in A_{n-1}$. The last equality yields $g^A(\sigma) = \ell \ge k+m-i \ge k+1-i$. $\square$

We can now show the proposition below, which gives Theorem 1.1 for type A.
**Proposition 2.3** Let $k = \lfloor \frac{n}{2} \rfloor$, and $R = \{r_1, r_2, \dots, r_k\}$, where $r_i = (i \ n+1-i)$ is the transposition permuting $i \in [k]$ and $n+1-i$. If $t_1t_2 \cdots t_k = w_0^{A_{n-1}}$, then:

(a) $\{t_1, \dots, t_k\} = R$

(b) $t_i t_j = t_j t_i$ for all $i, j \in [k]$.

(c) $(t_{\tau(1)}, t_{\tau(2)}, \dots, t_{\tau(k)})$ is a path in $B(A_{n-1})$ for all $\tau \in A_{k-1}$.

**Proof:** (a) Suppose that there exists $t_i \in T \setminus R$. Without loss of generality, using the Shifting Lemma, we can assume that $i = k$. Say $t_k = (m \ j)$ where $m < j \le n$ and $j \ne n+1-k$. Hence $f^A(t_k) = 0$, and thus by Lemma 2.2 we have that $g^B(t_k) \ge k$. But this contradicts $t_1t_2 \cdots t_{k-1}t_k = w_0^{A_{n-1}}$, which gives that $g^A(t_k) \le k-1$.

(b) Notice that $r_i$ and $r_j$ are disjoint transpositions for $i \ne j$, and thus commute.

(c) By (b) it is enough to show that $\ell(t_1t_2 \cdots t_m) > \ell(t_1t_2 \cdots t_{m-1})$ for $1 < m \le n$. To do this, we use Proposition 1.5.2 in [4]: If $w \in A_{n-1}$ then

$$ \ell(w) = \mathrm{inv}(w) = |\{(i, j) \in [n] \times [n] \mid i < j, w(i) > w(j)\}|. $$

Let $w \in A_{n-1}$, if $i < j, w(i) > w(j)$ then we say that $(i, j)$ is an inversion pair of $w$.

Suppose that $w_m = t_1t_2 \cdots t_m$; we now compare $\mathrm{inv}(w_m)$ and $\mathrm{inv}(w_{m-1})$. By (a) we have that the $t_i$'s are in $R$, so $t_m = (i \ n+1-i)$ for some $i \in [k]$. Moreover, $w_{m-1}(i) = i, w_{m-1}(n+1-i) = n+1-i$ and $w_m(l) = w_{m-1}(l)$ for all $l \in [n] \setminus \{i, n+1-i\}$. Now consider that:

1. If $(l, i)$ is an inversion pair of $w_{m-1}$ then $l < i$ and $w_{m-1}(l) > i$. If $w_{m-1}(l) > n+1-i$ then $(l, i)$ and $(l, n+1-i)$ are inversion pairs of both $w_{m-1}$ and $w_m$. If $w_{m-1}(l) \le n+1-i$, then $(l, n+1-i)$ is not an inversion pair of $w_{m-1}$, but since $w_m(n+1-i) = i$, it is an inversion pair of $w_m$.

2. If $(l, n+1-i)$ in an inversion pair of $w_{m-1}$ then $l < n+1-i$ and $w_m(l) = w_{m-1}(l) > n+1-i > i = w_m(n+1-i)$. Hence $(l, n+1-i)$ is also an inversion pair of $w_m$

3. If $(i, l)$ an inversion pair of $w_{m-1}$ then $i < l$ and $i > w_{m-1}(l)$. Since $w_m(i) = n+1-i > i > w_{m-1}(l) = w_m(l)$, $(i, l)$ is also an inversion pair of $w_m$.

4. If $(n+1-i, l)$ is an inversion pair of $w_{m-1}$ then $n+1-i < l$ and $n+1-i > w_{m-1}(l)$. If $i > w_{m-1}(l)$ then $(i, l)$ and $(n+1-i, l)$ are inversion pairs of both $w_{m-1}$ and $w_m$. If $i \le w_{m-1}(l)$, then $(i, l)$ is not an inversion pair of $w_{m-1}$, but since $w_m(i) = n+1-i$, it is an inversion pair of $w_m$.

Thus $\mathrm{inv}(w_m) \ge \mathrm{inv}(w_{m-1})$. To show that $\mathrm{inv}(w_m) \ge \mathrm{inv}(w_{m-1}) + 1$, consider the pair $(i \ n+1-i)$ which is not an inversion pair of $w_{m-1}$. But since $w_m(i) = n+1-i > i = w_m(n+1-i)$, this is an inversion pair of $w_m$. $\square$

We remark that the above proposition shows that $\mathrm{SP}(A_{n-1})$ is isomorphic to the Boolean poset of rank $k$. Moreover, $\mathrm{SP}(A_{n-1})$ is the poset of subsets of $R$ ordered by inclusion.
## 2.2 The poset $SP(B_n)$

We used the combinatorial description of $B_n$ and $T(B_n)$ in [4], Section 8.1.

Recall that $B_n$ is the group of signed permutations; that is, the group of permutations $\sigma$ of the set $[\pm n] = \{-n, -n+1, \dots, -1, 1, 2, \dots, n-1, n\}$ with the property $\sigma(-i) = -\sigma(i)$ for all $i \in [\pm n]$. We used the notation $\underline{i}$ to denote $-i$ for $i \in [\pm n]$. We have that $w_0^{B_n} = \underline{1} \underline{2} \dots \underline{n}$. Further, $T(B_n) = \{(i \ \underline{i}) : i \in [n]\} \cup \{(i \ j)(\underline{i} \ j) : 1 \le i < j \le n\}$. We call the set $\{(i \ \underline{i}) : i \in [n]\}$ reflections of type I and the set $\{(i \ j)(\underline{i} \ j) : \underline{1} \le i < j \le \underline{n}\}$ reflections of type II. We now prove the analogous versions of the propositions in Section 2.1.

**Proposition 2.4** $\ell_{T(B_n)}(w_0^{B_n}) = n$.

**Proof:** Notice that a reflection of type II changes the sign of either zero or two elements in $[n]$ and swaps them. So at least another reflection must be used to place them back in their respective order. That is, at least two reflections of type II are needed to place two elements in $[n]$ in their positions in $w_0^{B_n}$. Hence at least $2m$ reflections of type II are needed to place $2m$ elements of $[n]$ in their position in $w_0^{B_n}$, with $0 \le m \le \lfloor \frac{n}{2} \rfloor$, and after that $n-2m$ reflections of type I are needed to place the remaining $n-2m$ elements in their position in $w_0^{B_n}$. So $\ell_{T(B_n)} \ge n$.

Now, notice that $(1 \ \underline{1})(2 \ \underline{2}) \cdots (n \ \underline{n}) = w_0^{B_n}$, and so $\ell_{T(B_n)}(w_0^{B_n}) \le n$. $\square$

**Lemma 2.5** For $\sigma \in B_n$, let

$$f^B(\sigma) = |\{i \in [n] \mid \sigma(i) = w_0^{B_n}(i) = \underline{i}\}| + |\{(i, j) \in [n] \times [n], i < j \mid (\sigma(i), \sigma(j)) \in \{(j, i), (\underline{j}, \underline{i})\}\}|$$

and

$$g^B(\sigma) = \min\{\ell : \text{there exists } t_1, t_2, \dots, t_\ell \text{ with } t_1 t_2 \dots t_\ell \sigma = w_0^{B_n}\}.$$

$$\text{Then } f^B(\sigma) = i \implies g^B(\sigma) \ge n - i \text{ for } 0 \le i \le n.$$

**Proof:** We proceed by reverse induction. The case $i = n$ holds, since $g^B$ is a non-negative function. Suppose that the statement holds for $i$. We now show that it also holds for $i-1$. Let $\sigma \in B_n$ with $f^B(\sigma) = i-1$. Consider $t_1, t_2, \dots, t_\ell \in T(B_n)$ with $t_1 t_2 \cdots t_\ell \sigma = w_0^{B_n}$ and $\ell = g^B(\sigma)$. Notice that there exists $m$ with $f^B(t_{\ell-m+1} \cdots t_{\ell-1} t_\ell \sigma) = i$, since $f^B(t_1 t_2 \cdots t_\ell \sigma) = n$ and a reflection can fix at most one element in its position in $w_0^{B_n}$ or create a pair $(i, j)$ that is sent to $(\underline{j}, \underline{i})$ or $(\underline{j}, \underline{i})$. The last equality yields $g^B(\sigma) = \ell \ge k+m-i \ge k+1-i$. $\square$

Let $t_1, t_2$ be two reflections of type II satisfying $\{t_1, t_2\} = \{(k \ \underline{l})(\underline{k} \ l), (k \ l)(\underline{k} \ \underline{l})\}$ for some $k, l$ with $1 \le k < l \le n$. Then we see that $t_1 t_2(k) = t_2 t_1(k) = \underline{k}$ and $t_1 t_2(l) = t_2 t_1(l) = \underline{l}$. We call the pair $t_1, t_2$ a good pair. Good pairs play a special role in the shortest paths in $B(B_n)$, as seen in the theorem below.

**Proposition 2.6** If $t_1 t_2 \dots t_n = w_0^{B_n}$, then:

(a) For every $i \in [n]$ either $t_i$ is of type I or there exists $j \in [n]$, $i \ne j$ so that $t_i, t_j$ is a good pair.

(b) $t_i t_j = t_j t_i$ for all $i, j \in [n]$.

(c) $(t_{\tau(1)}, t_{\tau(2)}, \dots, t_{\tau(n)})$ is a path in $B(B_n)$ for all $\tau \in A_{n-1}$.
**Proof:** (a) Suppose that some reflection in $\{t_1, \dots, t_n\}$ is of type II, say $t_i = (k \ l)(\underline{k} \ \underline{l})$, and suppose that there is no $t_j$ so that $t_i, t_j$ is a good pair. Since $w_0^{B_n}(k) = \underline{k}$ and $w_0^{B_n}(l) = \underline{l}$, there must be another reflection $t_m$ that is not disjoint from $t_i$. Without loss of generality, we can assume that $\{t_i, t_m\} = \{t_{n-1}, t_n\}$. Since $t_{n-1}, t_n$ is not a good pair, then $f^B(t_{n-1}t_n) = 0$. Hence $g^B(t_{n-1}t_n) \ge n$, which contradicts $t_1t_2\cdots t_n = w_0^{B_n}$.

(b) Notice that since all the reflections in $t_1 \cdots t_n = w_0^{B_n}$ of type I are distinct, they commute with each other. Furthermore, if $t_i, t_j$ are a good pair, then they also commute. We need to verify that (i) if $t_i, t_j$ are of type II and not a good pair, then they are commuting reflections, and (ii) if $t_i, t_j$ are of mixed types, then they commute. Using the Shifting Lemma again, we can assume that the reflections in both cases are $t_{n-1}$ and $t_n$. Suppose that $t_{n-1}$ and $t_n$ do not commute. In both (i) and (ii) we see that $f^B(t_{n-1}t_n) = 0$, and so $g^B(t_{n-1}t_n) \ge n$ by Lemma 2.5, which contradicts $t_1t_2\cdots t_{n-1}t_n = w_0^{B_n}$.

(c) By Proposition 8.1.1 in [4], if $w \in B_n$ then

$$ \ell(w) = \mathrm{inv}(w) + \mathrm{Neg}(w) $$

where

$$ \mathrm{inv}(w) = \mathrm{inv}(w(1), w(2), \dots, w(n)) \quad \text{and} \quad \mathrm{Neg}(w) = - \sum_{j \in [n]: w(j) < 0} v(j). $$

For $i \in [n]$, let $w_i = t_1t_2\cdots t_i$. Notice that from (b) it is enough to prove that $\ell(w_m) > \ell(w_{m-1})$ for $1 < m \le n$. We have the following cases:

1. $t_m$ is of type I, say $t_m = (j \ \underline{j})$, with $j \in [n]$. (a) and (b) give that no other reflection involves the element $j$, and so $w_{m-1}(j) = j$. Furthermore, we have that $w_m(k) = w_{m-1}(k)$ for $k \in [n] \setminus \{j\}$. Now,

* If $(i, j)$ is an inversion pair of $w_{m-1}$, then $i < j$ and $w_{m-1}(i) > w_{m-1}(j) = j$, which gives that $w_{m-1}(i) > 0$. So $w_m(i) = w_{m-1}(i) > \underline{j} = w_m(j)$, and the pair $(i, j)$ is also an inversion pair of $w_m$. Since $\mathrm{Neg}(w_m) = \mathrm{Neg}(w_{m-1}) + \underline{j}$, we have that $\ell(w_{m-1}) < \ell(w_m)$.

* If $(j, i)$ is an inversion pair of $w_{m-1}$, then $j < i$ and $w_{m-1}(j) = j > w_{m-1}(i)$. Suppose that $(j, i)$ is not an inversion pair of $w_m$. There are at most $j-1$ such inversion pairs $(j, i)$ of $w_{m-1}$, since $1 < w_{m-1}(i) < j$. On the other hand, notice that $\mathrm{Neg}(w_m) = \mathrm{Neg}(w_{m-1}) + \underline{j}$. So

$$ \begin{aligned} \ell(w_m) - \ell(w_{m-1}) &= \mathrm{inv}(w_m) + \mathrm{Neg}(w_m) - (\mathrm{inv}(w_{m-1}) + \mathrm{Neg}(w_{m-1})) \\ &\ge \mathrm{inv}(w_{m-1}) - (j-1) + (\mathrm{Neg}(w_{m-1}) + \underline{j}) - (\mathrm{inv}(w_{m-1}) + \mathrm{Neg}(w_{m-1})) \\ &\ge 1 \end{aligned} $$

2. $t_m$ is of type II but does not change any element's signs, say $t_m = (i \ \underline{j})(\underline{i} \ \underline{j})$ with $1 \le i < j \le n$. Then by the same argument as in the proof of Proposition 2.3 (c), we have that $\ell(w_m) > \ell(w_{m-1})$.

3. If $t_m = (i \ \underline{j})(\underline{i} \ \underline{j})$, with $1 \le i < j \le n$; that is, $t_m$ swaps $i$ and $j$ and changes their sign. (a) and (b) give that $(w_{m-1}(i), w_{m-1}(j)) \in \{(i, j), (j, i)\}$, $(w_m(i), w_m(j)) \in \{(\underline{j}, \underline{i}), (\underline{i}, \underline{j})\}$, and $w_{m-1}(k) = w_m(k)$ for $k \in [\pm n] \setminus \{\pm i, \pm j\}$. Then
* If $(k, i)$ is an inversion pair of $w_{m-1}$ then $k < i$ and either $w_{m-1}(k) > i$ or $w_{m-1}(k) > j$. In either case $(k, i)$ is also an inversion pair of $w_m$ since $w_m(k) = w_{m-1}(k) > 0$ and $w_m(i) < 0$. Further, $\mathrm{Neg}(w_m) = \mathrm{Neg}(w_{m-1}) + i + j$, and so $\ell(w_{m-1}) < \ell(w_m)$.

* If $(i, k)$ is an inversion pair of $w_{m-1}$ then $i < k$ and either $i > w_{m-1}(k)$ or $j > w_{m-1}(k)$. If we assume that $(i, k)$ is not an inversion pair of $w_m$, then in the former case, there are at most $i - 1$ pairs lost, and in the latter there are at most $j - 1$. However, since $\mathrm{Neg}(w_m) = \mathrm{Neg}(w_{m-1}) + i + j$, we still have that $\ell(w_{m-1}) < \ell(w_m)$.

* If $(j, k)$ is an inversion pair of $w_{m-1}$ then $j < k$ and either $j > w_{m-1}(k)$ or $i > w_{m-1}(k)$. If we assume that $(j, k)$ is not an inversion pair of $w_m$, then in the former case, there are at most $j - 1$ pairs lost, and in the latter there are at most $i - 1$. However, since $\mathrm{Neg}(w_m) = \mathrm{Neg}(w_{m-1}) + i + j$, we still have that $\ell(w_{m-1}) < \ell(w_m)$.

* If $(k, j)$ is an inversion pair of $w_{m-1}$ then $k < j$ and either $w_{m-1}(k) > j$ or $w_{m-1}(k) > i$. In either case $(k, j)$ is also an inversion pair of $w_m$ since $w_m(k) = w_{m-1}(k) > 0$ and $w_m(j) < 0$. Further, $\mathrm{Neg}(w_m) = \mathrm{Neg}(w_{m-1}) + i + j$, and so $\ell(w_{m-1}) < \ell(w_m)$.

In all cases, we have the desired result. □

The previous proposition says that $SP(B_n)$ is (isomorphic to) the union of Boolean posets of rank $n$, one for each set $\{t_1, t_2, \dots, t_n\}$ with $t_1t_2\cdots t_n = w_0^{B_n}$. As an example, Figure 1 illustrates that $SP(B_2)$ is the union of two Boolean posets. In general, one can compute the number of Boolean posets in $SP(B_n)$.

## 2.2.1 Number of Boolean posets in $SP(B_n)$

Let $b_n$ be the number of Boolean posets in $B_n$. We obtain a Boolean poset for each set $\{t_1, \dots, t_n\}$ with $t_1t_2\cdots t_n = w_0^{B_n}$. It is easy to see that $b_1 = 1$ and $b_2 = 2$ (see Figure 1). For $n \ge 2$, notice that if $t_1t_2\cdots t_n(1) = \underline{1}$, then by Proposition 2.6 there are two possible cases: (i) there exists $t_j = (\underline{1} \ \underline{1})$ or there exists a good pair of reflections of the form $(\underline{1} \ \underline{k})(\underline{k} \ \underline{1}), (\underline{1} \ \underline{k})(\underline{k} \ \underline{1})$. There are $b_{n-1}$ such reflections in case (i) and $(n-1)b_{n-2}$ in case (ii). So $b_n$ satisfies the recurrence relation

$$b_n = b_{n-1} + (n-1)b_{n-2}$$

with initial conditions $b_1 = 1$ and $b_2 = 2$. Notice that this count is the same as the number of partitions of a set of $n$ distinguishable elements into sets of size 1 and 2.

It is easy to see that

$$b_n = 1 + \sum_{j=1}^{\lfloor \frac{n}{2} \rfloor} \frac{1}{j!} \prod_{i=0}^{j-1} \binom{n-2i}{2}.$$

## 2.3 The poset $SP(D_n)$

As in the previous section, we used the combinatorial description of $D_n$ and $T(D_n)$ in [4] Section 8.2.

$D_n$ ($n > 1$) is the group of signed permutations with an even number of negative elements (e.g, $\underline{1} \ \underline{2} \ \underline{3}$ is an element in $D_3$ whereas $\underline{1} \ \underline{2} \ \underline{3}$ is not). Like $B_n$, if $\sigma \in D_n$ then $\sigma(-i) = -\sigma(i)$ for $i \in [\pm n]$. Moreover, $w_0^{D_n} = \underline{1} \ \underline{2} \ \dots \ \underline{n}$ if $n$ is even and $w_0^{D_n} = \underline{1} \ \underline{2} \ \dots \ \underline{n}$ if $n$ is odd. Further, $T(D_n) = \{(i \ j)(\underline{i} \ \underline{j}) : 1 \le i < |j| \le n\}$; that is, the reflections of $D_n$ are the reflections of $B_n$ of type II.
**Proposition 2.7** $\ell_{T(D_n)}(w_0^{D_n}) = n$ if $n$ is even, and $\ell_{T(D_n)} = n - 1$ if $n$ is odd.

**Proof:** Same as for Proposition 2.4, but only using reflections of type II. Notice that for $n$ even, $r_1r'_1r_2r'_2\cdots r_kr'_k = w_0^{D_n}$, where $k = n/2$ and $r_i = (2i-1\underline{2i})(\underline{2i}2i-1)$, $r'_i = (2i-1\underline{2i})(\underline{2i}2i-1)$, $1 \le i \le n/2$. Similarly, for $n$ odd, we have that $t_1t'_1t_2t'_2\cdots t_kt'_k = w_0^{D_n}$, where $k = (n-1)/2$ and $r_i = (2i\underline{2i+1})(\underline{2i+1}2i)$, $r'_i = (2i\underline{2i+1})(\underline{2i+1}2i)$, $1 \le i \le (n-1)/2$. $\square$

**Lemma 2.8** For $\sigma \in D_n$, for $n$ even, define

$$f^D(\sigma) = |\{i \in [n] \mid \sigma(i) = w_0^{D_n}(i) = i\}| + |\{(i,j) \in [n] \times [n], i < j \mid (\sigma(i), \sigma(j)) \in \{(j,i), (\underline{j}, i)\}\}|$$

and for $n$ odd, define

$$f^D(\sigma) = |\{i \in [n] \setminus \{1\} \mid \sigma(i) = w_0^{D_n}(i) = i\}| + |\{(i,j) \in [n] \times [n], i < j \mid (\sigma(i), \sigma(j)) \in \{(j,i), (\underline{j}, i)\}\}|$$

Moreover, let

$$g^D(\sigma) = \min\{\ell : \text{there exists } t_1, t_2, \dots, t_\ell \text{ with } t_1t_2\dots t_\ell\sigma = w_0^{D_n}\}.$$

$$\text{Then } f^D(\sigma) = i \implies g^D(\sigma) \ge m - i \text{ for } 0 \le i \le m \text{ and } m = n \text{ if } n \text{ is even, } m = n - 1 \text{ if } n \text{ is odd.}$$

**Proof:** Same as in Lemma 2.5, using only reflections of type II. $\square$

**Proposition 2.9** Suppose that $t_1t_2\dots t_m = w_0^{D_n}$, where $m = n$ if $n$ is even and $m = n - 1$ if $n$ is odd.

Then:

(a) For every $i \in [m]$ there exists $j \in [m]$, $i \neq j$ so that $t_i, t_j$ is a good pair.

(b) $t_i t_j = t_j t_i$ for all $i, j \in [m]$.

(c) $(t_{\tau(1)}, t_{\tau(2)}, \dots, t_{\tau(m)})$ is a path in $B(D_n)$ for all $\tau \in A_{m-1}$.

**Proof:** The proof for (a) and (b) is the same as in Proposition 2.6, but only using reflections of type II.

For (c), even though the length function is not the same as described in the Section 2.2, we recall that $B(D_n)$ is the induced graph of $B(B_n)$ on the elements of $D_n$ by Proposition 8.2.6 in [4]. $\square$

### 2.3.1 Number of Boolean posets in $SP(D_n)$

Let $d_n$ be the number of Boolean posets in $SP(D_n)$ for each set $\{t_1, t_2, \dots, t_n\} \subset T(D_n)$ with $t_1t_2\cdots t_n = w_0^{D_n}$. Counting these subsets is equivalent to counting the partitions of $[n]$, if $n$ is even, or $[n-1]$, if $n$ is odd, into subsets of two elements (these represents the good pairs). That is,

$$d_m = \frac{1}{\lfloor \frac{m}{2} \rfloor!} \prod_{i=0}^{\lfloor \frac{m}{2} \rfloor - 1} \binom{m-2i}{2}$$

where $m = n$ if $n$ is even, and $m = n - 1$ if $n$ is odd. Since $m$ is even, notice that this is the same as counting the number of partitions of $[m]$ into sets of size 2.
## 2.4 Finite Dihedral groups

Let $I_2(m)$, $m \ge 1$ be the dihedral group of order $2m$ with generating set $\{s_1, s_2\}$, and let $T = T(I_2(m))$ its reflection set. If $n$ is odd, then

$$w_0^{I_2(m)} = \underbrace{s_1 s_2 s_1 \cdots s_1}_{m} = \underbrace{s_2 s_1 s_2 \cdots s_2}_{m}$$

is a reflection, and so $\ell_T(w_0) = 1$. Hence $SP(I_2(m))$ is isomorphic to the Boolean poset of rank 1, if $m$ is odd.

The case where $m$ is even is more interesting, as $w_0^{I_2(m)} \notin T$. We readily see that $\ell_T(w_0) = 2$, since for instance $w_0^{I_2(m)} = s_1 \underbrace{s_2 s_1 \cdots s_2}_{m-1}$. Thus $SP(I_2(m))$ is the union of Boolean posets of rank 2, if $m$ is even.

Fix $w_0$ to start with $s_1$. We now count number of Boolean posets in $SP(I_2(m))$ for $m$ even. This number is the same as the number of sets $\{t_1, t_2\}$ with $t_1 t_2 = w_0^{I_2(m)}$. There is one such set for each element of odd rank that starts with $s_1$, since for each such element $t_1$ there exists a unique element $t_2$ with $t_1 t_2 = w_0^{I_2(m)}$. Since there are $\frac{m}{2}$ such elements, there are $\frac{m}{2}$ Boolean posets in $SP(I_2(m))$.

# 3 Exceptional Coxeter groups

## 3.1 $F_4$, $H_3$, $H_4$, and $E_6$

We were able to verify through computer search that the results in the previous sections also worked for the following exceptional groups: $F_4$, $H_3$, $H_4$, $E_6$. That is, the shortest path poset for these groups form a union of Boolean posets of rank the absolute length of the longest word $w_0^W$. We summarize the results in Table 1. The computer search was done using Stembridge's *coxeter* Maple package [7], and it basically consisted of finding all shortest paths and verifying the analogous of Propositions 2.3, 2.6, 2.9 for those groups; that is, that the paths are given by reflections that are fully commutative.

An interesting observation is that the 3 Boolean posets that form $SP(E_6)$ are almost disjoint, sharing only $e$ and $w_0^{E_6}$ (the bottom and top elements of each poset).

### 3.1.1 $E_7$ and $E_8$

For $E_7$ and $E_8$ we were not able to verify by computer that the shortest paths form a union of Boolean posets, since it involved more computer power (or a better code) than was available to us. However, we can argue that this is indeed the case using geometric arguments. Let $(W, S)$ be Coxeter system, and consider the *geometric representation* of $W$, $\sigma: W \hookrightarrow GL(V)$, where $V$ is a vector space with basis $\Pi = \{\alpha_s | s \in S\}$ ($\Pi$ is called the set of *simple roots*). It is shown in [6] Section 5.4 that $\sigma$ is a faithful representation.

The *root system* of the Coxeter system $(W, S)$ is the set $\Phi = \{\sigma(w)(\alpha_s) : s \in S, w \in W\}$. Let $\beta \in \Phi$, then $\beta = \sum_{s \in S} c_s \alpha_s$. It is a well-known result that either $c_s \ge 0$ or $c_s \le 0$ for all $s \in S$. In the former case we say that $\beta$ is a *positive root*, and in the latter case we say that $\beta$ is a *negative root*. The set of positive roots is denoted by $\Phi^+$ and the set of negative roots is denoted by $\Phi^-$. It is also a well known fact (Proposition 4.4.5 in [4]) that there is a bijection between the set of reflections of $W$, $T(W)$ and $\Phi^+$ given by $t = wsw^{-1} \mapsto \sigma(w)(\alpha_s)$.
Finally, we shall use the fact that $\sigma(w_0^{E_n}) = -\mathbf{id}$, where $\mathbf{id}$ is the identity matrix of dimension $n$, and $n = 7, 8$. We point out that $\sigma(w_0^{E_n}) \neq -\mathbf{id}$, and thus $\mathrm{rank}(SP(E_6)) < 6)$. For details, see [2] Chapter VI, §4.10 and §11. With this in mind we can show

**Proposition 3.1** For $E_n$, where $n = 7, 8$ we have that:

(a) $\ell_T(w_0^{E_n}) = n$.

(b) If $w_0^{E_n} = t_1t_2\cdots t_n$ then $t_i t_j = t_j t_i$ for all $i, j \in [n]$.

(c) $(t_{\tau(1)}, t_{\tau(2)}, \dots, t_{\tau(n)})$ is a path in $B(E_n)$ for all $\tau \in A_{n-1}$.

**Proof:** (a) Since a reflection fixes a hyperplane, the product of $k$ reflections fixes the intersection of the $k$ hyperplanes that are fixed by each reflection. This intersection has codimension at most $k$, and so it's not empty unless $k \ge n$. In particular, $\sigma(w_0^{E_n}) = -\mathbf{id}$ leaves no points fixed (except for $0$) and so cannot be written as a product of fewer than $n$ reflections; that is $\ell_T(w_0^{E_n}) \ge n$. Moreover by Carter's Lemma (Lemma 2.4.5 in [1]), we have that $\ell_T(w_0^{E_n}) \le n$. Thus $\ell_T(w_0^{E_n}) = n$.

(b) Now consider $-\mathbf{id} = s_{t_1}s_{t_2}\cdots s_{t_n}$, where $\sigma(t_i) = s_{t_i}$ for $1 \le i \le n$ are the reflections (in $V$) with respect to the hyperplanes $\mathcal{H}_1, \mathcal{H}_2, \dots, \mathcal{H}_n$ that are perpendicular to the unit vectors $\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n$. The space fixed by the product $s_{t_1}s_{t_2}\cdots s_{t_{n-1}}$ is $\mathbb{R}\mathbf{v}_n$ (since the product of everything is $-\mathbf{id}$) which has co-dimension $n-1$ and then by the previous argument,

$$ \bigcap_{i<n} \mathcal{H}_i = \mathbb{R}\mathbf{v}_n, $$

that is, $v_n \in \mathcal{H}_i$ for all $i < n$. Hence, $\mathbf{v}_i \perp \mathbf{v}_n$, which means that $t_n$ commutes with $t_i$ for $i < n$. By the Shifting Lemma, we have that any two reflections $t_i, t_j$ commute.

(c) Let $t_1 \cdots t_n = w_0^{E_n}$. We are going to show that $\ell(t_1t_2\cdots t_k) > \ell(t_1t_2\cdots t_{k-1})$ for $1 < k \le n$. As before, let $s_{t_i} = \sigma(t_i)$ be the reflection on $V$ corresponding to $t_i$ about the hyperplane $\mathcal{H}_i$, and let $\mathbf{v}_i$ be the normal vector to $\mathcal{H}_i$. Since $\mathbf{v}_i \perp \mathbf{v}_j$ for all $i \neq j$, we have that $s_{t_1}s_{t_2}\cdots s_{t_{i-1}}(\alpha_i) = \alpha_i$, where $\alpha_i \in \Phi^+$ is the positive root corresponding to $t_i$. Thus by Proposition 4.4.6 in [4], we have that $\ell(t_1t_2\cdots t_i) > \ell(t_1t_2\cdots t_{i-1})$ for $1 \le i \le n$. $\square$

As a consequence of the above theorem, $SP(E_7)$ and $SP(E_8)$ are both formed by the union of Boolean posets that share at least the bottom and top elements. We are now done with the proof of Theorem 1.1.

### 3.1.2 Number of Boolean posets in $SP(E_7)$ and $SP(E_8)$

To count the number of paths (chains) in $SP(E_n)$ where $n = 7, 8$ we simply count the number $n$-tuples of perpendicular roots, since $\sigma(w_0^{E_n}) = -\mathbf{id}$. Each one of these $n$-tuples up to signs and permutations represents a Boolean poset. Direct computation yields 135 Boolean posets in $SP(E_7)$ and 2025 Boolean posets in $SP(E_8)$. These results are included in Table 1.

**Remark 3.2** The above geometric argument can be used to obtain the results that were proven in Section 2. As was the case in our proofs, each group type requires its own argument, since $\sigma(w_0^W)$ is different for each case. However we believe that the combinatorial proofs are more appropriate for the FPSAC audience.
# 4 Lowest-degree terms of the complete cd-index of finite Coxeter groups

For any Eulerian poset $P$, one can define the cd-index of $P$. This polynomial encodes the flag h-vector. The interested reader is referred to [5] for more information on the cd-index of Eulerian posets. Since Bruhat intervals are Eulerian and the reflection ordering has the property of having a unique chain (path in the Bruhat graph) with no descents for every interval $[u, v]$, the highest-degree terms of the complete cd-index coincide with the cd-index.

Let $\tilde{\psi}(B_n)$ be the cd-index of the Boolean poset $B_n$ (so $B_n$ is the poset of subsets of $[n]$ ordered by inclusion). We can use Theorem 5.2 in [5] to compute $\tilde{\psi}(B_n)$. First $\tilde{\psi}(B_1) = 1$ and for $n > 1$,

$$ \tilde{\psi}(B_n) = \tilde{\psi}(B_{n-1}) \cdot c + G(\tilde{\psi}(B_{n-1})) \quad (1) $$

where $G$ is the derivation $G(c) = d$ and $G(d) = cd$. In particular, we have that $\tilde{\psi}(B_2) = c$, $\tilde{\psi}(B_3) = c^2 + d$, $\tilde{\psi}(B_4) = c^3 + 2cd + 2dc$, and so on.

Propositions 2.3, 2.6 and 2.9, and the results and computer search of Section 3 give that for a finite Coxeter group $W$, the corresponding $SP(W)$ is the union of Boolean posets (that share at least the bottom and top elements). So any interval in $SP(W)$ belongs to a Boolean poset corresponding to a set $R = \{t_1, t_2, \dots, t_\ell\} \subset T(W)$ with $\ell_{T(W)}(w_0^W) = \ell$ and $t_1t_2 \cdots t_\ell = w_0^W$. Thus any interval of $SP(W)$ (thought of as paths in $B(W)$ labeled with $T(W)$, where $T(W)$ is ordered by a reflection ordering) has a unique chain (path) with empty descent set. Hence counting descent sets in the chains given by $R$ is the same as counting the flag h-vector of the Boolean poset of rank $\ell$.

As a consequence, the lowest-degree terms in the complete cd-index of $W$ add up to a multiple $N$ of the cd-index of the Boolean poset of ranks $\ell_{T(W)}(w_0^W)$. $N$ is the number of Boolean posets in $SP(W)$; that is, the number of sets $\{t_1, \dots, t_{\ell_{T(W)}(w_0^W)}\}$ with $t_1t_2 \cdots t_{\ell_{T(W)}(w_0^W)} = w_0^W$. These terms can be computed using (1) and Table 1. So we have

**Theorem 4.1** Let $W$ be a finite Coxeter group, $\alpha_W$ is the number of Boolean posets that form $SP(W)$ and $\ell_0 = \ell_T(w_0^W)$. Then lowest degree terms of $\tilde{\psi}_{e,w_0^W}$ are given by $\alpha_W \tilde{\psi}(B_{\ell_0})$.

In particular, the lowest-degree terms of $\tilde{\psi}_{e,w_0^W}$ are minimized by $\tilde{\psi}(B_{\ell_0})$.

# Acknowledgements

I thank Professor Louis J. Billera for insightful conversations and suggestions, including simplifying and correcting proofs. Martin Kassabov helped me (very patiently and diligently) understand the geometric argument used in Section 3. Finally, Mihai Bailesteanu helped with the translation of the abstract to French.
<table><caption>**Tab. 1:** Finite coxeter groups $W$, rank($SP(W)$), and the number of Boolean posets in $SP(W)$</caption><thead><tr><th>W</th><th>rank(SP(W))</th><th># of Boolean posets in SP(W)</th></tr></thead><tbody><tr><td>A<sub>n-1</sub></td><td>$$\lfloor \frac{n-1}{2} \rfloor$$</td><td>1</td></tr><tr><td>B<sub>n</sub></td><td>n</td><td>b<sub>n</sub></td></tr><tr><td>D<sub>n</sub></td><td>n if n is even; n - 1 if n is odd</td><td>d<sub>n</sub></td></tr><tr><td>I<sub>2</sub>(m)</td><td>2 if m is even; 1 if m is odd</td><td>$$\frac{m}{2}$$ if m is even; 1 if m is odd</td></tr><tr><td>F<sub>4</sub></td><td>4</td><td>24</td></tr><tr><td>H<sub>3</sub></td><td>3</td><td>5</td></tr><tr><td>H<sub>4</sub></td><td>4</td><td>75</td></tr><tr><td>E<sub>6</sub></td><td>4</td><td>3</td></tr><tr><td>E<sub>7</sub></td><td>7</td><td>135</td></tr><tr><td>E<sub>8</sub></td><td>8</td><td>2025</td></tr></tbody></table>

## References

[1] D. Armstrong, Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups. to appear in *Memoirs of the Am. Math. Soc.* arXiv:math/0611106v2.

[2] A. Bourbaki *Elements of Mathematics, Lie Groups and Lie Algebras*, Chapter 4 – 6. Springer-Verlag, Berlin, 2002.

[3] L. Billera and F. Brenti, *Quasisymmetric functions and Kazhdan-Lusztig polynomials*. arXiv:0710.3965.

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

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

[6] J. E. Humphreys, *Reflection Groups and Coxeter Groups*. Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, 1990.

[7] J. Stembridge, *coxeter Maple package for finite Coxeter groups and partially-ordered sets*. Available at http://math.lsa.umich.edu/~jrs.