1 Background and statement of results

The purpose of this paper is to establish an upper bound on the reflection length of elements in any Coxeter group. The reflection length has appeared in a few contexts, including as a generalization of a permutation formula [5] and in the study of reflection subgroups [6]. It has been given a geometric interpretation for the finite [2] and affine [7] groups. The first nontrivial upper bound on reflection length was a constant bound for any affine group [8]. No general nontrivial upper bound has been previously established, although Duszenko proved [3] that no constant bound exists except in the finite and affine cases.

We let (W, S) be a Coxeter system. Any element \(w\in W\) can be written as a product of the generators \(w=s_1s_2\cdots s_p\). If p is the minimum among all such expressions, then we say that p is the length of w, denoted \(l(w)=p\), and we say that \(s_1s_2\cdots s_p\) is a reduced expression for w. If a generator s appears in some reduced expression for w, then s appears in every reduced expression for w [1, Corollary 1.4.8 (ii)]. Therefore, we can define nd(w) to be the number of distinct generators in any reduced expression for w.

We define a set \(T=\{xsx^{-1}: x\in W, s\in S\}\) of the conjugates of the generators, and if \(t\in T\), then we say that t is a reflection. We can write any element as a product of reflections \(w=t_1 t_2 \cdots t_q\). If q is minimal among all such expressions, then we say that q is the reflection length of w, denoted \(l_R(w)=q\). The reflection length is sometimes called the absolute length [1] and denoted al(w). Other notations in the literature [2, 4,5,6] include v(w), n(w), l(w), and \(l'(w)\). We follow the notation of McCammond and Petersen [7, 8].

The relations in any Coxeter group W are generated by those of the form \(s_i^2=1\) and \((s_is_j)^{m_{i,j}}=1\), where the \(m_{i,j}\) are integers with \(m_{i,j}\ge 2\). In the case where the relations of W are all of the form \(s_i^2=1,\) then we say that W is universal. In any Coxeter system (W, S), the rank is the number of generators |S|.

Example 1

We take W to be a universal Coxeter group

$$\begin{aligned}W=\langle s_1, s_2, s_3, s_4\, |\, s_1^2=s_2^2=s_3^2=s_4^2=1\rangle ,\end{aligned}$$

and we consider the expression for an element w

$$\begin{aligned}w=s_1s_2s_4s_1s_2s_4s_1s_2.\end{aligned}$$

It is a reduced expression, since in a universal Coxeter group any expression without repeated factors is reduced. The element w satisfies \(l(w)=8\) and \(nd(w)=3\). A different expression

$$\begin{aligned}w=t_1t_2t_3t_4t_5t_6 \end{aligned}$$

where \(t_1=s_1s_2s_4s_2s_1\), \(t_2=s_1s_2s_1\), \(t_3=s_2\), \(t_4=s_4s_1s_4\), \(t_5=s_4\), and \(t_6=s_2\), shows that \(l_R(w)\le 6\). In fact the reflection length of w is 4; we invite the reader to find a different expression as a product of four reflections. We also emphasize that the number of distinct generators \(nd(w)=3\) can be less than the rank 4.

The following useful theorem is our main tool for computing reflection lengths.

Theorem

(Dyer’s Theorem, [4]) The reflection length of an element w is equal to the minimum number of factors deleted from any reduced expression for w, such that the remaining product is equal to the identity.

We can apply Dyer’s theorem to the element of Example 1 as follows. Since

$$\begin{aligned}s_1s_2\widehat{s_4}\widehat{s_1}s_2\widehat{s_4}s_1\widehat{s_2} = s_1s_2s_2s_1 = 1, \end{aligned}$$

where the hat denotes deletion, we see that \(l_R(w)\le 4\). We could use an exhaustive search of deleting fewer factors to conclude that \(l_R(w)=4\).

Since the generators are a subset of the reflections of w, it follows immediately that \(l_R(w)\le l(w)\) for all \(w\in W\). In fact, the reflection length is sometimes much less than the length. If W is finite, then Carter [2, Lemma 2] showed that \(l_R(w)\) is equal to the codimension of the space fixed by w in the standard geometric representation. In a finite dihedral group, for example, we have \(l_R(w)\le 2\) for all \(w\in W\), but the length l(w) could be as large as half the order of W. For W of affine type, McCammond and Petersen [8, Theorem A] showed that there exists a constant N, depending only on the number of generators, such that \(l_R(w)\le N\) for all \(w\in W\). Duszenko proved [3, Theorem 1.1] that if W is not finite or affine, then no such constant bound exists. However, we can still ask if any improvement on the obvious bound \(l_R(w) \le l(w)\) exists. Our main results are the following.

Theorem 1

We let (W, S) be a Coxeter system. For all nonidentity \(w\in W\), we have

$$\begin{aligned} l_R(w) \le l(w) - 2\left\lceil \frac{l(w)}{nd(w)} \right\rceil + 2. \end{aligned}$$
(1)

Here we have used \(\lceil r \rceil \) to denote the least integer that is greater than or equal to r, and we recall that nd(w) is the number of distinct generators appearing in w. The bound in Theorem 1 is sharp for universal groups in the following sense.

Theorem 2

We let (W, S) be a universal Coxeter system with \(|S|\ge 2\) and let m be a positive integer. There exists \(w\in W\) such that \(l(w)=m\) and

$$\begin{aligned}l_R(w) = l(w) - 2\left\lceil \frac{l(w)}{nd(w)} \right\rceil + 2. \end{aligned}$$

The remainder of this paper is organized as follows: Section 2 includes some basic properties of the reflection length function. Section 3 contains the proof of the general upper bound of Theorem 1. The proof of the upper bound includes a generalization of the pigeonhole principle. In Sect. 4 we establish the sharpness of the upper bound for universal Coxeter groups in the proof of Theorem 2. We close with some data toward enumeration of elements by length and reflection length in Sect. 5.

2 Properties of the reflection length function

In this section we state some basic properties of the reflection length function and establish a few useful lemmas. These properties are generally well known, but we collect them here and include some simple proofs as appropriate.

Lemma 1

For all \(w\in W\), we have \(l_R(w) \equiv l(w) \pmod {2}\).

Proof

By the definition of a Coxeter group, W has a presentation with each relation of the form \(s_i^2=1\) or \((s_is_j)^{m_{i,j}}=1\). In particular, the relations which reduce the number of factors in a expression reduce the number by an even number of factors. Therefore, all expressions which are equal to the identity contain an even number of factors. Then by Dyer’s theorem, l(w) is even if and only if \(l_R(w)\) is even. \(\square \)

The following result is analogous to corresponding basic properties of the length function, for example, Björner and Brenti’s Proposition 1.4.2 [1]. It may be proven by standard arguments similar to that for the length function, and we omit the proof.

Proposition 1

For all \(w, x \in W\):

  1. (i)

    \(l_R(wx) \equiv l_R(w) + l_R(x) \pmod 2\),

  2. (ii)

    for \(s \in S\), if \(w = xs\), then \(l_R(w) = l_R(x) \pm 1\),

  3. (iii)

    \(l_R(w^{-1}) = l_R(w)\),

  4. (iv)

    \(|l_R(w) - l_R(x)| \le l_R(wx) \le l_R(w) + l_R(x)\)

  5. (v)

    \(l_R(wx^{-1})\) is a metric on \(W\).

The reflection length function has some useful properties which are not analogous to properties of the length function, such as the following.

Lemma 2

We let \(w_1\) and \(w_2\) be conjugate elements in a Coxeter group W. Then, \(l_R(w_1) = l_R(w_2)\).

Proof

We let W be a Coxeter group and \(w_1, w_2 \in W\) be conjugate elements. By the definition of conjugate, there exists an element \(x\in W\) such that \(w_1 = x w_2 x^{-1}\). Suppose we delete factors from a reduced expression for \(w_2\) such that the remainder is equal to the identity. Then, deleting the same factors from \(x w_2 x^{-1}\) will reduce \(w_1\) to the identity. Therefore by Dyer’s Theorem, \(l_R(w_1) \le l_R(w_2)\). We also have that \(w_2 = x^{-1} w_1 x\), and the same argument shows that \(l_R(w_2) \le l_R(w_1)\). \(\square \)

One use of Lemma 2 is to move any factor to the beginning of an expression to help calculate its reflection length. For example, suppose that \(w=s_1s_2 xs_1s_2s_3\) where x is some factor. Conjugating by \(s_2s_1\), we can conclude that \(l_R(w) = l_R(xs_1s_2s_3s_1s_2).\) Then, we could apply Proposition 1 or other techniques to draw conclusions about \(l_R(w)\).

The final lemma that we will need is a bound on the reflection length of elements in finite or infinite dihedral groups.

Lemma 3

We let (W, S) be a Coxeter system with \(|S|=2\). For all \(w\in W\) we have \(l_R(w) \le 2\).

Proof

We let (W, S) be a Coxeter system with \(|S|=2\) and \(w\in W\). Any reduced expression for w is an alternating product of the two generators. If l(w) is odd, then this product is a palindrome and therefore w is a reflection and \(l_R(w)=1\). Otherwise, \(l_R(w)=0\) or \(l_R(w)=2\) by part (ii) of Proposition 1. \(\square \)

3 Proof of Theorem 1

We will need an inequality for the ceiling function.

Lemma 4

Suppose that \(N,k\in {\mathbb {Z}}\) with \(k>0\). Then,

$$\begin{aligned}k\left\lceil \frac{N}{k}\right\rceil \le N + k -1. \end{aligned}$$

Proof

We take \(N=qk+r\) for \(q,r\in {\mathbb {Z}}\) with \(0\le r < k\). If \(r=0\), then \(k\lceil N/k \rceil = N \le N+k-1\). Otherwise, \(1<r<k\), and

$$\begin{aligned}k\left\lceil \frac{N}{k}\right\rceil = k\left\lceil q+\frac{r}{k} \right\rceil = kq + k = N - r + k \le N+k-1,\end{aligned}$$

as desired. \(\square \)

We will also need the following generalization of the pigeonhole principle.

Lemma 5

Suppose that N objects are placed in k boxes, and that \(m_1,\) \(m_2,\) \(\ldots , m_k\) are the number of objects in each box, with \(m_1\ge m_2 \ge \cdots \ge m_k \ge 0\). Then for all j with \(1\le j \le k\), we have

$$\begin{aligned}\sum _{i=1}^j m_i \ge j \left\lceil \frac{N}{k} \right\rceil - j + 1. \end{aligned}$$

Proof

We suppose to the contrary that there exists a j such that \(m_1+m_2+\cdots +m_j < j \lceil N/k \rceil - j + 1.\) We first note that we must have \(m_j \le \lceil N/k \rceil - 1\), since otherwise \(m_1+m_2+\cdots +m_j \ge jm_j > j\lceil N/k \rceil - j.\) Since the \(m_i\) are nonincreasing, it follows that \(m_i \le \lceil N/k \rceil - 1\) for all i with \(j<i\le k\). Applying these inequalities to the sum of all the \(m_i\), we find that

$$\begin{aligned} \sum _{i=1}^k m_i&< \left( j \left\lceil \frac{N}{k} \right\rceil - j + 1\right) + (k-j) \left( \left\lceil \frac{N}{k} \right\rceil -1\right) \\&= k\left\lceil \frac{N}{k} \right\rceil -k+1 \\&\le N \end{aligned}$$

by Lemma 4. However, each of the objects is placed into a box so \(\sum _{i=1}^k m_i = N\), a contradiction. \(\square \)

We are now in a position to prove one of our main results.

Proof of Theorem 1

We let (W, S) be a rank n Coxeter system and consider some reduced expression for a nonidentity element w. If \(n=1\), then the only nonidentity element is the generator, which is easily seen to satisfy inequality (1). Therefore, we may assume that \(n\ge 2\).

In our reduced expression for w, we suppose that a most frequently occurring generator occurs \(m_1\) times and a second most frequently occurring generator occurs \(m_2\) times. We remove the other \(l(w)-m_1-m_2\) letters from w to obtain a word \(w^{\prime }\).

First we consider the case in which \(l(w^{\prime })\) is odd. By Lemmas 3 and 1, \(l_R(w^{\prime })=1\). We also have that \(m_1+m_2\ge 2 \lceil l(w)/nd(w) \rceil -1\) by Lemma 5. Therefore,

$$\begin{aligned} l_R(w)&\le l_R(w^{\prime }) + (l(w)-m_1-m_2)\\&\le 1 + (l(w) - 2\lceil l(w)/nd(w) \rceil +1)\\&= l(w) - 2\lceil l(w)/nd(w) \rceil +2, \end{aligned}$$

as desired.

We next consider the case in which \(l(w^{\prime })\) is even. By Lemma 3, \(l_R(w^{\prime })\le 2\). Since \(m_1+m_2\) must be even, we conclude from Lemma 5 that \(m_1+m_2\ge 2 \lceil l(w)/nd(w) \rceil \). Therefore,

$$\begin{aligned} l_R(w)&\le l(w) - 2\lceil l(w)/nd(w) \rceil +2, \end{aligned}$$

as desired. \(\square \)

4 Proof of Theorem 2

We let (W, S) be a Coxeter system of rank \(n\ge 2\). We first show that powers of Coxeter elements, which are elements of the form

$$\begin{aligned}w=(s_1 s_2\cdots s_n)^j,\end{aligned}$$

achieve the upper bound for any \(j\ge 1\). We emphasize that here \(s_1 s_2 \cdots s_n\) denotes a product of the elements of S, with each element appearing once in the product. Speyer showed [9] that these elements are reduced, so \(l(w)=nj\). The number of distinct generators is \(nd(w)=n\), so we wish to show that \(l_R(w) = nj - 2 \lceil (nj)/n \rceil +2 = nj-2j+2\).

Lemma 6

We let (W, S) be a universal Coxeter system of rank \(n\ge 2\). For any \(j\ge 1\), the power of the Coxeter element \(w=(s_1 s_2\cdots s_n)^j\) satisfies \(l_R(w)=nj-2j+2\).

Proof

If \(j=1\), then each generator appears exactly once so none of the relations \(s_i^2=1\) may be used to reduce w to the identity. To reduce w to the identity, every generator must be removed. Therefore, \(l_R(w)=n\), as desired.

For \(j>1\), we proceed by induction. We assume that \(l_R(w^{\prime })=n(j-1)-2(j-1)+2\), where \(w^{\prime }=(s_1 s_2 \cdots s_n)^{j-1}\), and consider the element \(w=(s_1 s_2 \cdots s_n)^j\). If we remove generators from w to obtain an expression equal to the identity, then we must remove at least \(n-1\) consecutive generators, since the only relations in the group are of the form \(s_i^2=1\). Using Lemma 2 and reindexing the generators as necessary, we may assume that the first \(n-1\) generators are removed. Therefore,

$$\begin{aligned}l_R(w) = n-1 + l_R(s_n w^{\prime })\end{aligned}$$

By Proposition 1 (ii), we have that either \(l_R(w) = n+ l_R(w^{\prime })\) or \(l_R(w) = n-2+ l_R(w^{\prime })\). However, \(l_R(w) = n+ l_R(w^{\prime })\) exceeds the bound of Theorem 1, so

$$\begin{aligned}l_R(w) = n-2+ l_R(w^{\prime }) = n-2+n(j-1)-2(j-1)+2 = nj-2j+2.\end{aligned}$$

\(\square \)

We next consider elements of the form

$$\begin{aligned}w=(s_1 s_2\cdots s_n)^js_1s_2\cdots s_r \end{aligned}$$

with \(0<r<n\). In this case, \(l(w)=nj+r\) and \(nd(w)=n\), so we wish to show that \(l_R(w) = nj+r - 2 \lceil (nj+r)/n \rceil +2 = nj+r-2j\).

Lemma 7

We let (W, S) be a universal Coxeter system with \(|S|=n\ge 2\). For any \(j\ge 0\) and r with \(0<r<n\), the element \(w=(s_1 s_2\cdots s_n)^js_1 s_2\cdots s_r\) satisfies \(l_R(w)=nj+r-2j\).

Proof

We first notice that in the case where \(j=0\), the element w is a product of r distinct generators and therefore has an reflection length of \(l_R(w)=r\), as desired.

In the case where \(j>0\) and \(r=1\), we conclude from Proposition 1 (ii) and Lemma 6 that \(l_R(w) = nj-2j+1\) or \(l_R(w) = nj-2j+3\). However, by Theorem 1, the reflection length can be at most \(nj+1-2\lceil (nj+1)/n\rceil +2 = nj+1-2j\). Therefore, \(l_R(w) = nj+1-2j\), as desired.

Finally, we note that for the elements \(w_1=(s_1 s_2\cdots s_n)^js_1\) and \(w_2=(s_1 s_2\cdots s_n)^{j+1}\), we have that \(l_R(w_2)=n(j+1)-2(j+1)+2\) by Lemma 6 and \(l_R(w_1) = nj+1-2j\) from the case \(r=1\). These have a difference of \(l_R(w_2)-l_R(w_1)=n-1\). We have the same difference \(l(w_2)-l(w_1)=n-1\) for the standard lengths. Then by Proposition 1 (ii), it must be the case that both the reflection length and the standard length increase by 1 when right multiplying by each factor of \(s_2 s_3\cdots s_n\). Therefore, the reflection length of \((s_1 s_2\cdots s_n)^js_1s_2\cdots s_r\) is \(nj+r-2j\) for all r with \(1\le r < n\). \(\square \)

Proof of Theorem 2

We let (W, S) be a rank \(n\ge 2\) Coxeter system and let m be a positive integer. Writing \(m=qn+r\) for integers \(q\ge 0\) and \(0\le r < n\) and applying Lemma 6 or Lemma 7, we obtain an element w with \(l(w)=m\) and \(l_R(w)=l(w)-2\lceil l(w)/nd(w)\rceil +2\). \(\square \)

5 Enumeration of group elements

Using Maple,Footnote 1 we computed the number of elements of length at most 17 by their reflection lengths in the universal Coxeter group \(\langle s_1, s_2, s_3 \mid s_1^2=s_2^2=s_3^2=1 \rangle \). The nonzero entries are shown in the following table.

 

1

2

3

4

5

6

7

1

3

      

2

 

6

     

3

6

 

6

    

4

 

24

     

5

12

 

36

    

6

 

90

 

6

   

7

24

 

168

    

8

 

282

 

102

   

9

48

 

714

 

6

  

10

 

858

 

678

   

11

96

 

2904

 

72

  

12

 

2304

 

3834

 

6

 

13

192

 

11,394

 

702

  

14

 

6216

 

18,270

 

90

 

15

384

 

42,822

 

5940

 

6

16

 

15,702

 

81,786

 

816

 

17

768

 

151,170

 

44,562

 

108

The main relevance of the data to our results is that the length of the rows is given by the bound in Theorem 1. A few other observations can be easily explained. For example, the parity of the row and column indices of nonzero entries is explained by Lemma 1. The divisibility by 6 follows from the action of the symmetric group on the subscripts. The \((2m+1,1)\) entry is equal to \(2^m3\), which can be explained by the multiplication principle since it counts palindromes in \(s_1\), \(s_2\), and \(s_3\). Similarly, the sum of row m is equal to \(2^{m-1}3\) because it counts words in \(s_1\), \(s_2\), and \(s_3\) without repeated factors.

It would be interesting to find a two-variable generating function for this table, but this remains an open question.