Enumerating in Coxeter Groups (Survey)

Abstract

Coxeter groups are of significant interest to communities in combinatorics, algebra, and geometry. Their structures and properties are both deeply beautiful and still not entirely understood. We explore some of the many enumerative aspects of these objects. We count elements with desirable properties, we give size orderings to certain features of all group elements, and we relate some of these statistics in ways that give bounds and rankings—if not exact values—to their sizes. Our primary tools come from leveraging different group presentations against each other, and interpreting element properties at the level of generator representations. In this article, we present a sampling of results in this area, putting them into context and hopefully inspiring future research.

1 Introduction

A Coxeter group is defined by a set of generators S and relations of the form

$$\displaystyle \begin{aligned}(ss')^{m(s,s')} = e\end{aligned}$$

for s, s′∈ S, with m(s, s) = 1. There are many so-called “types” of Coxeter groups, with, perhaps, the most well-studied being the finite Coxeter group of type A, also known as the symmetric group. Due to the length of this article, we focus our discussion on the symmetric group and, as appropriate, cite analogous results for Coxeter groups of other types. The other types referenced will most often be B and D, which have interpretations as signed permutations and signed permutations with restrictions, respectively. The reader will notice that several of the enumerative problems discussed here do not have such analogues, and we close this paper by highlighting a selection of these for future research.

The symmetric group S _n consists of all permutations of {1, …, n}, and it is generated by the adjacent transpositions {s _i : 1 ≤ i < n}, where s _i is the permutation that swaps i and i + 1, and fixes all other elements. (Note that there are other generating sets for S _n, as well, but the one of interest to us here is the set of adjacent transpositions.) In addition to being involutions, these generators satisfy the commutation relation

$$\displaystyle \begin{aligned}s_i s_j = s_j s_i { when } |i-j| > 1\end{aligned}$$

and the braid relation

$$\displaystyle \begin{aligned}s_is_{i+1}s_i = s_{i+1}s_is_{i+1}.\end{aligned}$$

Further information about general Coxeter groups and their combinatorial properties can be found in the aptly titled [2].

Despite the great interest in Coxeter groups from a variety of mathematical perspectives, many questions about them remain unanswered. Combinatorial aspects of these objects are no outlier in this sense, and open combinatorial questions range from an understanding of intricate structural features to fundamental enumerative issues.

Counting questions about Coxeter groups can take a range of forms, including the enumeration of Coxeter group elements that possess certain properties, and the quantification of particular features of the group elements themselves. In this article, we present problems in both of these categories. We also hint at large classes of open questions. In this way, we hope to attract and inspire new work in this area, where this is much yet to be done and much potential interest in the results.

2 Main Tools

The main tools for our work are two theorems from the literature. Before we can state these, we make a few important definitions. We phrase these in terms of the symmetric group because that is the focus of this work, but analogous objects exist for Coxeter groups of other types, too.

Definition 1

A reduced decomposition of a permutation w ∈ S _n is a decomposition of w into minimally many generators: $w = s_{i_1}\cdots s_{i_{\ell (w)}}$. This minimal value ℓ(w) is the length of w. The set of all reduced decompositions of w is denoted R(w).

A permutation can have many reduced decompositions, as demonstrated below. The number of reduced decompositions of a permutation was calculated in [10] in terms of standard Young tableaux.

Example 1

Let w ∈ S ₄ be such that w(1) = 3, w(2) = 2, w(3) = 4, and w(4) = 1. This permutation has three reduced decompositions:

$$\displaystyle \begin{aligned}w = s_2s_1s_2s_3 = s_1s_2s_1s_3 = s_1s_2s_3s_1,\end{aligned}$$

where we think of the adjacent transpositions as maps, and thus compose them from right to left.

The Coxeter relations described above can act on reduced decompositions. They do this by replacing s _is _j by s _js _i when |i − j| > 1, and s _is _i+1s _i by s _i+1s _is _i+1. Each of these actions suggests an equivalence relation on the elements of R(w).

Definition 2

Let w be a permutation and R(w) its set of reduced decompositions. This set has two natural partitions, arising from the Coxeter relations:

• the commutation classes of w are C(w) := R(w)∕(s _is _j ∼ s _js _i) when |i − j| > 1, and

• the braid classes of w are B(w) := R(w)∕(s _is _i+1s _i ∼ s _i+1s _is _i+1).

In [1, §3], the authors consider such relation-based partitions more generally, for arbitrary Coxeter groups.

That is, any two reduced decompositions that are in the same commutation class C ∈ C(w) (respectively, braid class B ∈ B(w)) can be obtained from each other by a sequence of commutation (respectively, braid) moves. We demonstrate these partitions by continuing the previous example.

Example 2

Let w be as in Example 1. Then

$$\displaystyle \begin{aligned} C(w) &= \Big\{ \{s_2s_1s_2s_3\}, \ \{s_1s_2s_1s_3,\ s_1s_2s_3s_1\} \Big\} \text{ and}\\ B(w) &= \Big\{ \{s_2s_1s_2s_3,\ s_1s_2s_1s_3\}, \ \{s_1s_2s_3s_1\} \Big\}. \end{aligned} $$

Up to now, we have written permutations as products of adjacent transpositions. In fact, there are many ways to represent permutations, including as products of different generating sets, as products of cycles, as graphs, as arrow diagrams, and in one-line notation. The final definition that we need at this point concerns a seemingly (but not for long!) unrelated feature of permutations, related to the one-line notation for a permutation.

Definition 3

Let w ∈ S _n be a permutation and write w, in one-line notation, as the word w(1)⋯w(n). Let p ∈ S _k be a permutation written similarly, with k ≤ n. The permutation w contains a p-pattern if there exist j ₁ < j ₂ < ⋯ < j _k such that the subword w(j ₁)⋯w(j _k) is in the same relative order as the word for p. If this is the case, then we write p ≺ w. If not, then w avoids p, written p⊀w.

Example 3

The permutation w from Example 1 is written in one-line notation as 3241. This permutation has a 231-pattern (in fact, it has two: the subwords w(1)w(3)w(4) = 341 and w(2)w(3)w(4) = 241 are both order isomorphic to 231). On the other hand, 123⊀w.

Although Definition 3 is specific to the symmetric group S _n, there is a notion of signed pattern for the finite Coxeter groups of types B and D. Despite obvious parallels between patterns and signed patterns, however, the (unsigned) pattern literature is notably richer than the literature for signed patterns. The reader is referred to [6, 7], among many other works.

The two theorems that have been most useful for tackling the problems discussed here each have a number of technical details. While important, pausing to define and characterize those details could be distracting in an article of this length. As a compromise, we give “big picture” statements of the theorems here, with citations to their full statements in other works.

Dictionary. :

There is a way to translate between statements about permutation patterns and statements about reduced decompositions. (See [11, Theorem 3.8] and its generalization [13, Theorem 3.9].)

Rhombic Tilings. :

There is a bijection between rhombic tilings of certain polygons and commutation classes of reduced decompositions. (See [3, Theorem 2.2].)

Elnitsky developed analogous tiling-to-commutation class bijections for types B and D, as well [3, §§6–7]. In those settings, the tilings have reflective requirements to account for sign and, in the case of type D, so-called “megatiles” are permitted.

3 Counting Special Elements: An Example

One type of enumerative problem about Coxeter groups would be to count the elements with a particular property or feature. We given an example of this type of work here.

There is a natural partial ordering on Coxeter group elements defined in terms of reduced decompositions.

Definition 4

Let G be a Coxeter group with elements v and w. Then v ≤ w in the (strong) Bruhat order if a reduced decomposition of v is a subword of a reduced decomposition of w.

Despite the fact that both v and w in Definition 4 can have multiple reduced decompositions, this ordering is well-defined. (The weak Bruhat order, which we do not study here, requires that the reduced decomposition of v appear as a prefix (or suffix) of a reduced decomposition of w, whereas the Bruhat order does not even require the reduced decomposition of v to appear as a consecutive subword in the reduced decomposition of w.)

Viewed as posets under the Bruhat order, Coxeter groups can have quite snarly structure. The principal order ideal of an element w is the set of all elements that are less than or equal to w in the poset, and even the principal order ideals in the Bruhat order need not be well-behaved. To get a sense of which elements might have “nice” principal order ideals, we consider the following classification.

Definition 5

In a Coxeter group, an element w is a boolean element if its principal order ideal {v : v ≤ w in the Bruhat order} is a boolean poset.

We demonstrate Definition 5 by looking at boolean elements in the Coxeter group S ₄. This group has 13 boolean elements. The poset structure of S ₄, with those 13 boolean elements highlighted, is shown in Fig. 1.

Fig. 1

The Coxeter group S ₄, drawn as a poset under the Bruhat order. Group elements are written as permutations in one-line notation, and the 13 boolean elements of the group are circled

To support interest in these boolean elements, we note that they describe a structure with beautiful topology. Indeed, the collection of boolean elements in any Coxeter group forms a simplicial poset. This poset, then, is the face poset of a regular cell complex called the boolean complex. If the Coxeter group has rank n, then that boolean complex is homotopy equivalent to a wedge of (n − 1)-dimensional spheres. This topology is discussed, and in more depth, in [8, 9].

It turns out (see [12]) that, in any Coxeter group, boolean elements can be identified by whether or not their reduced decompositions have repeated letters. In the case of the symmetric group, among others, this can also be characterized by pattern avoidance.

Theorem 1 ([12])

A permutation is boolean iff it avoids 321 and 3412.

Boolean elements in the finite Coxeter groups of types B and D can also be characterized by (signed, in these cases) pattern avoidance [12, §7].

Having identified these elements, and with such attractive characterizations, it is enticing to try to enumerate them. In fact, they can be enumerated, both overall and by length.

Theorem 2 ([4, 14])

The number of boolean permutations in S _n is F _2n−1 , the odd-indexed Fibonacci number.

Theorem 3 ([12])

The number of boolean permutations in S _n of length k is

$$\displaystyle \begin{aligned}\sum_{i=1}^k\binom{n-i}{k+1-i}\binom{k-1}{i-1}.\end{aligned}$$

Boolean elements in the finite Coxeter groups of types B and D can be enumerated [4], and enumerated by length [12, §7]. For type B, these enumerations closely resemble the type A results cited above, while the results for type D are notably different and more complicated to state.

Boolean elements are just one example of a noteworthy class of elements in a Coxeter group whose enumeration might be of interest. Moreover, in enumerating such a class of objects, one might develop a new characterization for them that could shed light on other topics or unanswered questions. Depending on the enumerative technique used, this might even hint at a deeper structure in the group.

4 Counting an Element’s Special Features: An Example

The second category of enumerative problems that we present for Coxeter groups is to calculate the size of a particular feature of a group element. To demonstrate this, we look at the reduced decompositions R(w), the commutation classes C(w), and the braid classes B(w) of a permutation w.

The natural first approach to evaluating the sizes of these sets—to evaluating the size of anything, really—is a straightforward calculation. Indeed, as discussed above, Stanley computes |R(w)| by counting Young tableaux of particular shape(s), with the special case that just one shape is needed iff w is 2143-avoiding [10]. On the other hand, outside of special cases like classifying the permutations for which |C(w)| = 1 or those for which |B(w)| = 1, there are no known similar results for |C(w)| or |B(w)|.

This leads us to a second approach, which is not to evaluate the absolute sizes of these sets, but to determine relative sizes. “Relative to what?” one might ask. Recall the Dictionary mentioned above, and the link it provides between reduced decompositions and permutation patterns. Inspired by that result, we consider pattern containment as a possible yardstick against which to measure these set sizes. (Note that the idea of ordering the set of all permutations—of any size—by pattern containment is not new. Indeed, this leads to a poset whose Möbius function has been the subject of great interest since at least [15].)

Not only does pattern containment seem to be an appropriate yardstick, but it yields more information about the sizes of these sets than was previously known.

Theorem 4 ([13])

• (a) If p ≺ w then |R(p)|≤|R(w)|. Moreover, if p ≺ w and |R(w)| > 1, then |R(p)| = |R(w)| iff ℓ(p) = ℓ(w); equivalently, iff p and w have equally many 21-patterns.

• (b) If p ≺ w then |C(p)|≤|C(w)|. Moreover, if p ≺ w, then |C(p)| = |C(w)| iff p and w have equally many 321-patterns.

Any analysis of commutation classes is greatly helped by the Rhombic Tilings result mentioned above. Unfortunately, similar machinery has not (yet) been developed for studying braid classes. This seems to be more an issue of oversight than the result of any great complexity to braid classes that might prevent such machinery’s existence. Braid classes have received some attention (see [1, 16]), but not nearly as much as commutation classes. Recently, in an attempt to begin to remedy this, important strides were made in understanding the set B(w) by considering it simultaneously with C(w) [5].

The strength of that technique is that it recognizes that B(w) and C(w) are both partitions of the same set, R(w), and so knowledge about one of the partitions might imply knowledge about the other. In fact, this turns out to be the case, and the sets can be leveraged against each other to good effect.

In an important sense, these two sets are orthogonal to each other: as shown in [5], for any permutation w and any B ∈ B(w) and C ∈ C(w),

$$\displaystyle \begin{aligned}|B \cap C| \le 1.\end{aligned}$$

Thus, one can index the reduced decompositions of R(w) by ordered pairs (B, C) representing their braid and commutation classes, and each possible pair appears at most once in this list. This gives an upper bound to |R(w)| in terms of |B(w)| and |C(w)|. A lower bound follows from the fact (see, for example, [2]) that any reduced decomposition for w can be obtained from any other by a sequence of braid and commutation moves. These bounds are combined in the following theorem.

Theorem 5 ([5])

For any permutation w,

$$\displaystyle \begin{aligned}|B(w)| + |C(w)| - 1 \le |R(w)| \le |B(w)| \cdot |C(w)|.\end{aligned}$$

With so little known about the structure and behavior of braid classes, it is instructive to try to understand the bounds of Theorem 5. As shown in [5], those bounds are sharp, and the permutations achieving them can be characterized and enumerated.

We have used this section to give a sense of this category of enumerative questions about Coxeter group elements, and the results and implications that they might have. Certainly there is a substantial range of topics still to be studied, both related to the discussion above and independent of it.

5 Directions for Future Research

The goal of this article is to demonstrate the different ways that enumerative combinatorialists might approach the study of Coxeter groups. Although we have listed many results and cited many sources, the reader should not assume that this is a “closed” field of study. There is much still to be uncovered about the combinatorics of these objects, including questions that have been studied for many years and others that, themselves, have not yet been identified.

In particular, while some of the results described for the symmetric group have analogues in Coxeter groups of other types, much remains to be uncovered. There is every reason to expect, for example, a type B analogue of Theorem 5 relating braid classes, commutation classes, and the classes R(w)∕(s ₀s ₁s ₀s ₁ ∼ s ₁s ₀s ₁s ₀). Similarly, just as Enlitsky’s tiling bijections can be constructed for types B and D, there may well be a Dictionary for groups of other types. Finally, we reiterate that while much has studied about commutation classes of reduced decompositions, much less attention has been given to partitions based on other Coxeter relations.