# Depth in Coxeter groups of type B

Eli Bagno,<fnref n="1" />†Riccardo Biagioli,<fnref n="2" />‡ and Mordechai Novick <fnref n="3" />§

**Abstract.** The depth statistic was defined for every Coxeter group in terms of factorizations of its elements into product of reflections. Essentially, the depth gives the minimal path cost in the Bruaht graph, where the edges have prescribed weights. We present an algorithm for calculating the depth of a signed permutation which yields a simple formula for this statistic. We use our algorithm to characterize signed permutations having depth equal to length. These are the fully commutative top-and-bottom elements defined by Stembridge. We finally give a characterization of the signed permutations in which the reflection length coincides with both the depth and the length.

**Résumé.** La statistique profondeur a été introduite par Petersen et Tenner pour tout groupe de Coxeter W. Elle est définie pour tout $w \in W$ à partir de ses factorisations en produit de réflexions (non nécessairement simples). Pour le type B, nous introduisons un algorithme calculant la profondeur, et donnant une formule explicite pour cette statistique. On utilise par ailleurs cet algorithme pour caractériser tous les éléments ayant une profondeur égale à leur longueur. Ces derniers s'avèrent être les éléments pleinement commutatifs "hauts-et-bas" introduits par Stembridge. Nous donnons enfin une caractérisation des éléments dont la longueur absolue, la profondeur et la longueur coïncident.

**Keywords:** Coxeter groups, Bruhat graph, reflections, depths, length.

## 1 Introduction

Let $(W, S)$ be a Coxeter system. Each $w \in W$ can be written as a product of simple generators $s_i \in S$, $w = s_1s_2 \cdots s_r$. The length $\ell_S(w)$ of $w$ is the minimal number of simple reflections $s \in S$ needed to express $w$:

$$ \ell_S(w) := \min\{r \in \mathbb{N} : w = s_1 \cdots s_r \text{ for some } s_1, \ldots, s_r \in S\}. \quad (1) $$

If $r = \ell_S(w)$ then the word $s_1 \cdots s_r$ is called a reduced expression of $w$. Another measure is the following. Let

$$ T := \{ wsw^{-1} : s \in S, w \in W \}. \quad (2) $$

<footnote n="1">¹Jerusalem College of Technology, 21 Havaad Haleumi st. Jerusalem, Israel.</footnote>

<footnote n="2">²Institut Camille Jordan, Université Claude Bernard Lyon 1, 69622 Villeurbanne Cedex, France</footnote>

<footnote n="3">³Jerusalem College of Technology, 21 Havaad Haleumi st. Jerusalem, Israel.</footnote>

<footnote>†Email: bagnoe@g.jct.ac.il.</footnote>

<footnote>‡Email: biagioli@math.univ-lyon1.fr.</footnote>

<footnote>§Email: mnovick@g.jct.ac.il.</footnote>
be the set of *reflections* of W. The reflection length $\ell_T(w)$ is defined as the usual length but using all the reflections, more precisely

$$ \ell_T(w) := \min\{r \in \mathbb{N} : w = t_1 \cdots t_r \text{ for some } t_1, \ldots, t_r \in T\}. \quad (3) $$

Let $w, v \in W$. Then

i) $w \xrightarrow{t} v$ means that $w^{-1}v \in T$ and $\ell_S(u) < \ell_S(v)$;

ii) $w \to v$ means that $w \xrightarrow{t} v$ for some $t \in T$;

iii) $w \le v$ means that there exist $v_i \in W$ such that $w = v_1 \to v_2 \to \cdots \to v_k = v$.

The *Bruhat graph* is the directed graph whose nodes are the elements of W, and whose edges are given by ii). Hence $\ell_T(w)$ is the length of a shortest path from the identity to w. The *Bruhat order* is the partial order relation on the set W defined by iii). Its rank function is given by $\ell_S$.

A third statistic which turns out to lie between the two mentioned above is the *depth*. We define first the depth of a positive root of W. Denote by $\Phi^+$ the set of positive roots of W. Then for each $\beta \in \Phi^+$ we set

$$ \mathrm{dp}(\beta) := \min\{r \mid s_1 \cdots s_r(\beta) \in \Phi^+, s_j \in S\}. $$

It is easy to see that $\mathrm{dp}(\beta) = 1$ if and only if $\beta$ is a simple root. As a function on the set of roots, the depth is also the rank function on the root poset of a Coxeter group, as is developed in the classic book [3, §4].

Now, if we denote by $t_\beta$ the reflection corresponding to the root $\beta$, Petersen and Tenner [7] define the depth of any $w \in W$ as follows:

$$ \mathrm{dp}(w) := \min \left\{ \sum_{i=1}^{r} \mathrm{dp}(\beta_i) : w = t_{\beta_1} \cdots t_{\beta_r}, t_{\beta_i} \in T \right\}. $$

It can be proven that for each positive root $\beta$ one has

$$ \mathrm{dp}(t_{\beta}) = \mathrm{dp}(\beta) = \frac{\ell_S(t_{\beta}) + 1}{2}. \quad (4) $$

Moreover, the depth of an element $w \in W$ is bounded on both sides respectively by the reflection and regular length:

$$ \ell_T(w) \le \frac{\ell_T(w) + \ell_S(w)}{2} \le \mathrm{dp}(w) \le \ell_S(w). $$

In [7], Petersen and Tenner provide an explicit formula for the depth of an element in the symmetric group $S_n$, by using an algorithm similar to the “straight selection sort” of Knuth [6]. Some of their results were already shown by Diaconis and Graham in the context of total displacements [4]. The formula of Petersen and Tenner for the depth is a sum over the *size of the excedances* of a permutation, more precisely:
**Theorem 1.1** Let $w \in S_n$. Then

$$ \mathrm{dp}(w) = \sum_{w(i)>i} (w(i) - i). $$

We recall that $B_n$ is the group of all bijections $w$ of the set $[-n, n] \setminus \{0\}$ onto itself such that

$$ w(-i) = -w(i) $$

for all $i \in [-n, n] \setminus \{0\}$, with composition as the group operation. This group is usually known as the group of signed permutations on $[n]$, or as the hyperoctahedral group of rank $n$. If $w \in B_n$ then we write $w = [w(1), \dots, w(n)]$ and we call this the window notation of $w$. From now on we denote by $\mathrm{sign}(w(i))$ and $|w(i)|$, respectively the sign and the absolute value of the entry $w(i)$, moreover we write $-i$ simply by $\bar{i}$.

It is well-known that $(B_n, S_B)$ is a Coxeter system of type B with $S_B := \{s_0, s_1, \dots, s_{n-1}\}$, (see e.g., [3, §8]), where for $i \in [n-1]$

$$ s_i := [1, \dots, i-1, i+1, i, i+2, \dots, n], \quad \text{and} \quad s_0 := [-1, 2, \dots, n] = (\bar{1}, 1). $$

Petersen and Tenner ask the following questions [7, §5] (among others).

**Question 1.2** What does an analogous formula of Theorem 1.1 look like in the case of $B_n$?

**Question 1.3** Is it true that for each $w \in W$ there is a directed path $e \xrightarrow{t_1} \dots \xrightarrow{t_r} w$ in the Bruhat graph having exactly $l_T(w)$ steps, and such that $\mathrm{dp}(w) = \sum_{i=1}^r \mathrm{dp}(t_i)$?

**Question 1.4** What is the number of signed permutations for which depth equals length?

In this paper we answer these questions. We also address in the context of $B_n$ other questions discussed by Petersen and Tenner, including conditions for the coincidence of depth, length, and reflection length. Moreover we characterize the group elements for which depth achieves its maximal value.

After the submission of this extended abstract we started a collaboration with Alexander Woo. We extended our results to the group $D_n$, and we also considered related questions for general Coxeter groups.

## 1.1 Main results

In order to present our main results, we need the following definition.

**Definition 1.5** Let $u \in B_k, v \in B_{n-k}$. Define the direct sum of $u$ and $v$ by:

$$ (u \oplus v)(i) := \begin{cases} u(i) & i \in \{1, \dots, k\}; \\ v(i-k) + \mathrm{sign}(v(i-k))k & i \in \{k+1, \dots, k+l\}. \end{cases} $$

A permutation $w \in B_n$ will be called decomposable if it can be expressed as a nontrivial direct sum of permutations and indecomposable otherwise.

For example, $w = w^1 \oplus w^2 \oplus w^3 = [4, \bar{3}, 1, \bar{2}, 7, 5, \bar{6}, 9, \bar{8}]$, where $w^1 = [4, \bar{3}, 1, 2]$, $w^2 = [3, 1, \bar{2}]$, and $w^3 = [2, \bar{1}]$, while $[\bar{8}, 1, 9, 3, 5, 2, \bar{6}, 4, 7]$ is indecomposable.

Now, we can present an explicit formula for the depth of a permutation in $B_n$.
**Theorem 1.6** Let $w = w^1 \oplus \cdots \oplus w^k \in B_n$. Then

$$ \mathrm{dp}(w) = \sum_{\{i \in \{1, \dots, n\} : w(i) > i\}} (w(i) - i) + \sum_{i \in \mathrm{Neg}(w)} |w(i)| - \sum_{i=1}^{k} \left\lfloor \frac{\mathrm{neg}(w^i)}{2} \right\rfloor, $$

where for each $w \in B_n$, $\mathrm{Neg}(w) = \{i \in \{1, \dots, n\} : w(i) < 0\}$, and $\mathrm{neg}(w) = |\mathrm{Neg}(w)|$.

Our proof is based on an algorithm using only right multiplications by reflections. Once applied to (unsigned) permutations it yields a path in the $S_n$ Bruhat graph, different from that considered in [7].

In $S_n$ an element has depth equal to length if and only if it is fully commutative. Petersen and Tenner conjectured that in $B_n$ an analogous characterization holds. We confirm their conjecture, by showing that the fully commutative top-and-bottom elements defined by Stembridge in [8], are the only elements in $B_n$ having depth equal to length. This will be proved in Section 4, where also the necessary definitions will be given.

**Theorem 1.7** Let $w \in B_n$. Then $\ell_S(w) = \mathrm{dp}(w)$ if and only if $w$ is a fully-commutative top-and-bottom element.

**Corollary 1.8** The number of elements $w \in B_n$ satisfying $\mathrm{dp}(w) = \ell_S(w)$ is the Catalan number $C_{n+1}$.

Moreover, we have the following two results.

**Theorem 1.9** Let $w \in B_n$. Then $\ell_T(w) = \mathrm{dp}(w) = \ell_S(w)$ if and only if each (equivalently, any) reduced expression of $w$ has no repeated generators.

**Corollary 1.10**

1. The number of elements $w \in B_n$ satisfying $\ell_T(w) = \mathrm{dp}(w) = \ell_S(w)$ is the Fibonacci number $F_{2n+1}$.

2. The number of elements $w \in B_n$ satisfying $\ell_T(w) = \mathrm{dp}(w) = \ell_S(w) = k$ is

$$ \sum_{i=1}^{k} \binom{n+1-i}{k+1-i} \binom{k-1}{i-1}. $$

## 2 An explicit formula for the depth

In the group $B_n$ the set of reflections is given by (see e.g. [3, Proposition 8.1.5])

$$ T^B := \{t_{ij}, t_{\bar{ij}} : 1 \le i < j \le n\} \cup \{t_{ii} : i \in [n]\}, $$

where $t_{ij} = (i, j)(\bar{i}, \bar{j})$, $t_{\bar{ij}} = (\bar{i}, j)(i, \bar{j})$, and $t_{ii} = (\bar{i}, i)$, in cycle notation. In particular there are $n^2$ reflections in $B_n$.

By definition in the Bruhat graph of $B_n$ there is an edge between $w$ and $v$ if and only if $v = wt$ where $t \in T^B$, or equivalently if there exists a reflection $t'$ such that $v = t'w$ (denoted by $v \stackrel{t'}{\leftarrow} w$). There is no such equivalence in terms of depth since right multiplication by $t$ and left multiplication by $t'$ may have different costs. Below we summarize the effects of the different reflections using the window notation.
1. The reflections $t_{ij}$.

Right multiplication of $w$ by $t_{ij}$ swaps the entry $w(i)$ with the entry $w(j)$ in such a way that each digit moves with its sign. For example $[\bar{3}, 1, 4, 2] \xrightarrow{t_{12}} [1, \bar{3}, 4, 2]$.

Left multiplication of $w$ by $t_{ij}$ swaps entries $i$ and $j$. Note that in this case each sign (if any) remains in its original place. For example, $[3, \bar{2}, 4, 1] \xleftarrow{t_{12}} [3, \bar{1}, 4, 2]$.

2. The reflections $t_{\bar{ij}}$.

Right multiplication by $t_{\bar{ij}}$ swaps entry $w(i)$ with entry $w(j)$ and changes both signs. For example $[\bar{3}, 1, 4, 2] \xrightarrow{t_{12}} [\bar{1}, 3, 4, 2]$.

Left multiplication by $t_{\bar{ij}}$ swaps entries $i$ and $j$, and changes both signs in positions $i$ and $j$. For example $[3, 2, 4, \bar{1}] \xleftarrow{t_{12}} [3, \bar{1}, 4, 2]$.

3. The reflections $t_{\bar{ii}}$.

Right multiplication by $t_{\bar{ii}}$ changes the sign of the entry $w(i)$. For example $[3, \bar{1}, 4, 2] \xrightarrow{t_{22}} [3, 1, 4, 2]$.

Left multiplication by $t_{\bar{ii}}$ changes the sign of the entry $i$. For example $[3, 1, 4, 2] \xleftarrow{t_{11}} [3, \bar{1}, 4, 2]$.

From equation (4) we immediately obtain the depths of the three types of reflections.

**Lemma 2.1** Let $T^B$ be the set of reflections of $B_n$. Then

$$ \mathrm{dp}(t_{ij}) = j - i, \quad \mathrm{dp}(t_{\bar{ij}}) = i + j - 1, \quad \text{and} \quad \mathrm{dp}(t_{\bar{\bar{ii}}}) = i. $$

As noted at the beginning of this section, the edge from $w$ to $v$ in the Bruhat graph may be labeled by a left or a right reflection. In order to reach the minimal cost we will show that we can restrict our choices and use only right multiplications.

For each $w = w^1 \oplus \cdots \oplus w^k \in B_n$, let us denote:

$$ d(w) = \sum_{\{i \in \{1, \dots, n\} \mid w(i) > i\}} (w(i) - i) - \sum_{i \in \mathrm{Neg}(w)} w(i) - \sum_{i=1}^{k} \left\lfloor \frac{\mathrm{neg}(w^i)}{2} \right\rfloor. \quad (5) $$

In order to prove Theorem 1.6, we proceed in two steps. First, we supply an algorithm that associates to each $w \in B_n$ a decomposition of $w$ into a product of reflections whose sum of depths is $d(w)$. This will prove that $d(w)$ is an upper bound for $\mathrm{dp}(w)$. Then we will show that $d(w)$ is also a lower bound for $\mathrm{dp}(w)$. This will settle Question 1.2.

Our algorithm shows that for any $w \in B_n$ there exists a path $e \xrightarrow{t_1} \cdots \xrightarrow{t_r} w$ in the weak Bruhat order such that $\mathrm{dp}(w) = \sum_{i=1}^{r} \mathrm{dp}(t_i)$. This path usually has more than $\ell_T(w)$ steps. Moreover, computer calculations show that there exist elements in $B_n$ for which all paths giving the depth (in the Bruhat order) have strictly more than $\ell_T(w)$ steps. One example is the permutation $[-4, -2, -3, -1] \in B_4$ which has depth 8 and absolute length 3, but all the paths achieving the depth have length 5. Also, in $D_4$ there are many examples. Hence we may answer Question 1.3 (in $B_n$ and in $D_n$) in the negative.
**Example 2.2** The reflection length, the depth, the length, a reduced expression, and a path giving the depth for each element of $B_2$ are depicted in the following table. All this information can be read off from the Bruhat graph in Figure 2: the dashed lines correspond to reflections having depth 2, the regular lines to simple ones having depth 1.

<table><caption>Fig. 1: The group $B_2$.</caption><thead><tr><th>w &isin; B<sub>2</sub></th><th>&ell;<sub>T</sub>(w)</th><th>dp(w)</th><th>&ell;<sub>S</sub>(w)</th><th>Red(w)</th><th>Path e to w</th></tr></thead><tbody><tr><td>[1, 2]</td><td>0</td><td>0</td><td>0</td><td>e</td><td>e</td></tr><tr><td>[2, 1]</td><td>1</td><td>1</td><td>1</td><td>s<sub>1</sub></td><td>t<sub>12</sub></td></tr><tr><td>[1&#773;, 2]</td><td>1</td><td>1</td><td>1</td><td>s<sub>0</sub></td><td>t<sub>1&#773;1</sub></td></tr><tr><td>[2&#773;, 1]</td><td>2</td><td>2</td><td>2</td><td>s<sub>1</sub>s<sub>0</sub></td><td>t<sub>12</sub>t<sub>1&#773;1</sub></td></tr><tr><td>[2&#773;, 1&#773;]</td><td>2</td><td>2</td><td>2</td><td>s<sub>0</sub>s<sub>1</sub></td><td>t<sub>1&#773;1</sub>t<sub>12</sub></td></tr><tr><td>[2&#773;, 1&#773;]</td><td>1</td><td>2</td><td>3</td><td>s<sub>0</sub>s<sub>1</sub>s<sub>0</sub></td><td>t<sub>1&#773;2</sub></td></tr><tr><td>[1&#773;, 2&#773;]</td><td>1</td><td>2</td><td>3</td><td>s<sub>1</sub>s<sub>0</sub>s<sub>1</sub></td><td>t<sub>2&#773;2</sub></td></tr><tr><td>[1&#773;, 2&#773;]</td><td>2</td><td>3</td><td>4</td><td>s<sub>1</sub>s<sub>0</sub>s<sub>1</sub>s<sub>0</sub></td><td>t<sub>12</sub>t<sub>1&#773;2</sub></td></tr></tbody></table>

<figure><img src="image_1.png" /><figcaption>Fig. 2: The Bruhat graph of $B_2$.</figcaption></figure>

## 2.1 The algorithm

The algorithm consists of a sequence of moves, which change the order, the sign, or both, of the entries of a given signed permutation. We start by defining these moves. We say that entry $x$ is in its *natural position* in $w$ if $x = w(x)$. In all this section we use the natural order of $\mathbb{Z}$.

**Definition 2.3 (Moves)**
1. A shuffling move is the right multiplication of $w$ by a reflection of type $t_{ij}$.

2. A single unsigned move is the right multiplication of $w$ by a reflection of type $t_{\bar{i}\bar{i}}$, where $x = w(i)$ is the unique negative entry in $w$.

3. A double unsigned move is the right multiplication of $w$ by a reflection of type $t_{\bar{i}\bar{j}}$, where $x = w(i)$ and $y = w(j)$ are two negative entries in $w$.

**Definition 2.4 (The algorithm)** Let $w \in B_n$ be indecomposable.

1. If possible apply a shuffling move $t_{ij}$ to $w$, where $x = w(i)$ is maximal positive entry in $w$ with $x > i$, and $y = w(j)$ is the smallest entry in $w$ with $i < j \le x$. Consider $wt_{ij}$ and repeat this procedure until this is not possible any more.

1.1. Let $u$ be the element obtained after the last application of Step 1, $w \xrightarrow{t_{i_1 j_1}} \dots \xrightarrow{t_{i_k j_k}} u$.

2. If $\text{neg}(u) > 2$ then apply a double unsigned move $t_{\bar{i}\bar{j}}$ to $u$, where $x = w(i)$ and $y = w(j)$ are the two negative entries of maximal absolute value in $w$, and go back to Step 1.

3. If $\text{neg}(u) = 1$ then apply a single unsigned move $t_{\bar{i}\bar{j}}$ to $u$, and go back to Step 1.

In other words, the algorithm begins by shuffling each positive element $w(x)$ which appears to the left of its natural position $x$, starting from the largest, and continuing in descending order. Once this is completed, an unsigned move is performed. If there is more than one negative entry in $w$, we unsigned a couple, thus, obtaining two new positive entries. The process restarts, and the remaining elements might be further shuffled. The alternation of unsigned and shuffling moves continues until neither type of move can be performed. The last unsigned move will be a single one when the number of negative entries in $w$ is odd.

An application of the previous algorithm is given in the following example. The depth of each reflection is depicted below the corresponding arrow.

**Example 2.5** Let $w = [\bar{6}, \bar{3}, \bar{2}, 8, 7, 5, 9, \bar{4}, \bar{1}] \in B_9$. Our first step will be to shuffle entry 9 to position 9:

$$w = [\bar{6}, \bar{3}, \bar{2}, 8, 7, 5, \mathbf{9}, \bar{4}, \bar{1}] \xrightarrow{t_{\bar{1}\bar{8}}} [\bar{6}, \bar{3}, \bar{2}, 8, 7, 5, \bar{4}, \mathbf{9}, \bar{1}] \xrightarrow{t_{\bar{8}\bar{9}}} [\bar{6}, \bar{3}, \bar{2}, 8, 7, 5, \bar{4}, \bar{1}, 9].$$

Then we apply Step 1, consecutively to entry 8, and 7:

$$[\bar{6}, \bar{3}, \bar{2}, \mathbf{8}, 7, 5, \bar{4}, \bar{1}, 9] \xrightarrow{t_{\bar{4}\bar{7}}} [\bar{6}, \bar{3}, \bar{2}, \bar{4}, 7, 5, \mathbf{8}, \bar{1}, 9] \xrightarrow{t_{\bar{7}\bar{8}}} [\bar{6}, \bar{3}, \bar{2}, \bar{4}, \mathbf{7}, 5, \bar{1}, 8, 9] \xrightarrow{t_{\bar{5}\bar{7}}} [\bar{6}, \bar{3}, \bar{2}, \bar{4}, \bar{1}, 5, 7, 8, 9].$$

Now, none of the positive entries is located to the left of its natural position, so we proceed with Step 2 to unsigned the two largest negative digits in absolute order, these are 6 and 4:

$$[\bar{6}, \bar{3}, \bar{2}, \bar{4}, \bar{1}, 5, 7, 8, 9] \xrightarrow{t_{\bar{1}\bar{4}}} [4, \bar{3}, \bar{2}, 6, \bar{1}, 5, 7, 8, 9].$$

Then we apply again Step 1, to push 6, and then 4 forward to their natural positions:

$$[4, \bar{3}, \bar{2}, \mathbf{6}, \bar{1}, 5, 7, 8, 9] \xrightarrow{t_{\bar{4}\bar{5}}} [4, \bar{3}, \bar{2}, \bar{1}, \mathbf{6}, 5, 7, 8, 9] \xrightarrow{t_{\bar{5}\bar{6}}} [\mathbf{4}, \bar{3}, \bar{2}, \bar{1}, 5, 6, 7, 8, 9] \\ \xrightarrow{t_{\bar{12}}} [\bar{3}, \mathbf{4}, \bar{2}, \bar{1}, 5, 6, 7, 8, 9] \xrightarrow{t_{\bar{23}}} [\bar{3}, \bar{2}, \mathbf{4}, \bar{1}, 5, 6, 7, 8, 9] \xrightarrow{t_{\bar{34}}} [\bar{3}, \bar{2}, \bar{1}, 4, 5, 6, 7, 8, 9].$$
We unsigned now the couple 3 and 2:

$$[\bar{3}, \bar{2}, \bar{1}, 4, 5, 6, 7, 8, 9] \xrightarrow{\frac{t_{\bar{1}2}}{2}} [2, 3, \bar{1}, 4, 5, 6, 7, 8, 9].$$

Now again Step 1, to move 3 and 2 to their natural places:

$$[2, \mathbf{3}, \bar{1}, 4, 5, 6, 7, 8, 9] \xrightarrow{t_{23}} [\mathbf{2}, \bar{1}, 3, 4, 5, 6, 7, 8, 9] \xrightarrow{t_{12}} [\bar{1}, 2, 3, 4, 5, 6, 7, 8, 9].$$

Finally we unsigned 1:

$$[\bar{1}, 2, 3, 4, 5, 6, 7, 8, 9] \xrightarrow{\frac{t_{\bar{1}1}}{1}} [1, 2, 3, 4, 5, 6, 7, 8, 9],$$

and we are done. We obtained $w = t_{\bar{1}1}t_{12}t_{23}t_{\bar{1}2}t_{34}t_{23}t_{12}t_{56}t_{45}t_{\bar{1}4}t_{57}t_{78}t_{47}t_{89}t_{78}$. The sum of depths of the reflection in the decomposition is 22, and corresponds to $d(w) = (8-4) + (7-5) + (9-7) - (-6-3-2-4-1) - \lfloor \frac{5}{2} \rfloor$, since $w$ is indecomposable.

Note that in $w$, 9 is two places away from its natural position, so $9 - w^{-1}(9) = 2$. This is the cost we paid when moving 9 to its place. Likewise, 8 and 7 contribute 4 and 2, respectively. The treatment of the pair 6 and 4, from the unsigned process to the arrival at their natural positions costs $6 + 4 - 1 = 9$. This can be proven to be the general case. The treatment of 2 and 3 took $2 + 3 - 1$ steps depth and the unsigneding of 1 costs 1.

It is clear from the definition, that the output of the algorithm is the identity permutation. Now, let $w \in B_n$ be indecomposable. We claim that the total cost of the algorithm is $d(w)$. The proof is based on the following lemmas.

**Lemma 2.6** Let $w \in B_n$ be indecomposable. Then the cost of the algorithm at the end of Step 1 is
$$ \sum_{w(i)>i} (w(i) - i). $$

**Lemma 2.7** Let $w \in B_n$ and let $x, y, i, j$ be such that $w(i) = \bar{x}, w(j) = \bar{y}$ with $i < j$, $x \ge j$ and $y \ge i$. Then the total cost of the process of unsigneding $x$ and $y$ and putting them in their natural positions is $x + y - 1$.

Note that if $x < j$ or $y < i$, then after unsigneding $\bar{x}$ and $\bar{y}$, the digits $x$ or $y$ might be placed after their natural positions. This will cause the overall process of unsigneding $\bar{x}$ and $\bar{y}$, and putting $x$ and $y$ in their natural positions, to cost more than $x+y-1$. The next lemma assures that this situation can never happen provided that $w$ is indecomposable.

**Lemma 2.8** Let $w \in B_n$ be indecomposable. Let $x, y$ be the two largest negative entries in absolute value, with $\bar{x}$ appearing before $\bar{y}$ in the window notation of $w$. Then after performing Step 1 of the algorithm, we get a permutation $u$ satisfying $u(i) = \bar{x}, u(j) = \bar{y}, x \ge j$, and $y \ge i$.

The discussion above proves that if $w \in B_n$ is indecomposable then the total cost of the process of converting $w$ into the identity is $d(w)$. Now, as we noted above, if $w$ is not indecomposable then the algorithm will be applied for each indecomposable part separately and we conclude that $d(w)$ is an upper bound for $dp(w)$.
In order to show that $d(w)$ is also a lower bound, note first that each positive entry $x$ such that $w(i) = x$, must contribute at least $x - i$ steps (each of depth 1) to the overall cost. Negative entries $\bar{x}, \bar{y}$ which can be paired contribute not less than $x + y - 1$, while the remaining negative entry $\bar{x}$ which cannot be paired (if there is any) contributes $x$. This will be proved, using the next two lemmas (among others).

**Lemma 2.9** Let $w \in B_n$ and let $x, i$ be such that $w(i) = \bar{x}$. Then every series of moves which unsigns only $x$ and places it in its natural position costs at least $x$.

**Lemma 2.10** Let $w \in B_n$ be an indecomposable permutation and let $x, i, y, j$ be such that $w(i) = \bar{x}$ and $w(j) = \bar{y}$. Then every series of moves which unsigns $\bar{x}$ and $\bar{y}$ and places them in their natural positions costs at least $x + y - 1$.

We can use the algorithm described above to obtain the maximum value of the depth on $B_n$.

**Theorem 2.11** For each $w \in B_n$ we have $\mathrm{dp}(w) \le \binom{n+1}{2}$ with equality if and only if $w = [\bar{1}, \bar{2}, \dots, \bar{n}]$.

### 3 Coincidence of length and depth

In this section we present a characterization of the signed permutations $w \in B_n$ satisfying $\mathrm{dp}(w) = \ell_S(w)$. The corresponding problem in the case of the group $S_n$ was solved by Petersen and Tenner, who proved that these elements are precisely the fully commutative permutations. As was conjectured by these authors, the situation in $B_n$ is rather similar.

**Definition 3.1** An element $w$ of a Coxeter group $W$ is called *fully commutative* if every reduced expression $w = s_1 \cdots s_\ell$ for $w$ can be obtained from any other by transposing adjacent commuting generators.

**Definition 3.2** Fix $w \in B_n$ and $p \in B_k$ for $k \le n$. We say that $w$ contains the pattern $p$ if there exist $1 \le i_1 < \cdots < i_k \le n$ such that

1. $w(i_j)$ and $p(j)$ have the same sign;

2. $|w(i_1)| \cdots |w(i_k)|$ is in the same relative order as $|p(1)| \cdots |p(k)|$.

If $w$ does not contain $p$, then $w$ avoids $p$, or is $p$-avoiding.

It [2], it was shown that a permutation is fully commutative if and only if it is $[3, 2, 1]$-avoiding. In $B_n$, the situation is a bit subtler. Stembridge proved in [8, Theorem 5.1] that a signed permutation is fully commutative if and only if it avoids a specific set of patterns. He introduced also *fully commutative top-and-bottom elements*, and enumerated them [8, §4]. In the language of reduced expressions, they are *alternating elements* which have at most one occurrence of the generator $s_0$, see [1]. In order to present our result we recall below Stembridge’s characterization of fully commutative top-and-bottom elements in terms of pattern avoidance [8, Corollaries 5.6 and 5.7], with a minor change of convention, since we use the inverse permutation.

**Proposition 3.3** An element $w \in B_n$ is a fully commutative top-and-bottom element if and only if $w$ avoids the following list of patterns: $\{[\bar{1}, \bar{2}], [\bar{2}, \bar{1}], [1, \bar{2}], [3, 2, 1], [3, 2, \bar{1}], [3, 1, \bar{2}]}$.

A case-by-case analysis on the avoided patterns, gives us the following result.

**Theorem 3.4** Let $w \in B_n$. Then $\mathrm{dp}(w) = \ell_S(w)$ if and only if $w$ is a fully commutative top-and-bottom element.
# 4 Coincidence of depth, length and reflection length

In this section we deal with the permutations of $B_n$ which satisfy $\ell_T(w) = \text{dp}(w)$. By [7, Observation 2.3], this is equivalent to $\ell_T(w) = \ell_S(w)$. Actually, the results of this section can be concluded from [5], [7], and [9], which were written before the formula for the depth in $B_n$ had been known; nevertheless, we present them here for the sake of completeness.

Let $W$ is a Coxeter group of type $A, B$ or $D$. An element $w \in W$ is called *boolean* if the principal order ideal of $w$ in $W$, $B(w) := \{x \in W \mid x \le w\}$ is a boolean poset, where $\le$ refers to the strong Bruhat order. Recall that a poset is called *boolean* if it is isomorphic to the poset $2^k$ for some $k$.

Theorem 7.3 of [9], claims that an element $w \in W$ is boolean if and only if some (and hence any) reduced decomposition of $w$ has no repeated letters. The following result is due to Dyer [5, Theorem 1.1].

**Proposition 4.1** Let $(W, S)$ be a Coxeter system and let $w = s_1 \cdots s_n$ be a reduced decomposition of $w \in W$. Then $\ell_T(w)$ is the minimum of the natural numbers $k$ for which there exists $1 \le i_1 < \cdots < i_k \le n$ such that $e = s_1 \cdots \hat{s}_{i_1} \cdots \hat{s}_{i_k} \cdots s_n$, where $\hat{s}$ indicates the omission of $s$.

From the above result and the previous discussion we easily conclude that for each $w \in W$ we have that $\ell_T(w) = \ell_S(w)$ if and only if $w$ is boolean. Hence by [9, Theorem 7.4] we get the following result.

**Theorem 4.2** Let $w \in B_n$. Then $\ell_T(w) = \text{dp}(w) = \ell_S(w)$ if and only if $w$ avoids the following list of patterns:

$$ \{[\bar{1}, \bar{2}], [\bar{2}, \bar{1}], [1, \bar{2}], [3, 2, 1], [3, 2, \bar{1}], [\bar{3}, 2, 1], [3, \bar{2}, 1], [3, 4, 1, 2], [3, 4, \bar{1}, 2], [\bar{3}, 4, 1, 2]\}. $$

Moreover by [9, Corollaries 7.5 and 7.6] we get a proof of Corollary 1.10.

# References

[1] R. Biagioli, F. Jouhet, and P. Nadeau. Fully commutative elements in finite and affine Coxeter groups. To appear in *Monatsh. Math.*, DOI: 10.1007/s00605-014-0674-7, arXiv:1402.2166, 2014.

[2] S. C. Billey, W. Jockusch, and R. P. Stanley. Some combinatorial properties of Schubert polynomials. *J. Algebraic Combin.*, 2(4):345–374, 1993.

[3] A. Björner and F. Brenti. *Combinatorics of Coxeter groups*, volume 231 of *Graduate Texts in Mathematics*. Springer, New York, 2005.

[4] Persi Diaconis and R. L. Graham. Spearman's footrule as a measure of disarray. *J. Roy. Statist. Soc. Ser. B*, 39(2):262–268, 1977.

[5] M. J. Dyer. On minimal lengths of expressions of Coxeter group elements as products of reflections. *Proc. Amer. Math. Soc.*, 129(9):2591–2595, 2001.

[6] Donald E. Knuth. *The art of computer programming. Vol. 3*. Addison-Wesley, Reading, MA, 1998. Sorting and searching, Second edition [of MR0445948].

[7] T. K. Petersen and B. E. Tenner. The depth of a permutation. *J. Comb., to appear*, 2014.
[8] J. R. Stembridge. Some combinatorial aspects of reduced words in finite Coxeter groups. *Trans. Amer. Math. Soc.*, 349(4):1285-1332, 1997.

[9] B. E. Tenner. Pattern avoidance and the Bruhat order. *J. Combin. Theory Ser. A*, 114(5):888-905, 2007.