1. Introduction and Overview
In mathematics and computer science, a trace is a set of strings or words over an alphabet for which certain pairs are allowed to commute. The commutativity rules can be encoded by an undirected graph called the dependency graph, where the vertices are the letters and edges correspond to non-commuting pairs. Given a trace, the associated trace monoid is the set of finite words under the equivalence relation generated by these commutations, where the binary operation is concatenation. The combinatorics of trace monoids were studied by Cartier and Foata in the 1960s, who called them partially commutative monoids . They are now sometimes known as Cartier-Foata monoids. We will stick with the term “trace monoid” for brevity. In 1986, G. X. Viennot  introduced the theory of heaps of pieces, which is a combinatorial interpretation of these objects that leads to a nice way to visualize them. The “pieces” represent the distinct letters in the alphabet, and a string is represented by a vertical stack, or “heap” of these pieces. Two pieces overlap vertically if the corresponding letters do not commute, as elements in the monoid. A simple example of this follows.
Example 1.1. Consider the trace monoid over the alphabet with dependency graph shown on the left in Figure 1. That is, two letters commute if and only if they are non-adjacent in . The string in defines a heap of pieces shown in the middle of Figure 1. One can think of this as being built by dropping balls in a “Towers of Hanoi” fashion onto this dependency graph—pieces of the same type are aligned vertically, and two pieces of different types overlap vertically if they do not commute. This heap (of pieces) is just a labeled poset (sometimes called its skeleton), whose Hasse diagram is shown on the right in Figure 1. Note that every “labeled” linear extension is a string that gives rise to the same heap.
Trace monoids can be defined for arbitrary graphs, though the visualization of the heap in Figure 1 works well because is a line-graph. For more complicated planar graphs, we might need to make the pieces oddly shaped for the “Towers of Hanoi” visualization to work, which originally motivated Viennot’s heaps of pieces. For example, in Figure 1 the piece does not commute with either or . If we want to further require that it does not commute with and , one way to represent this is to elongate it, as shown in Figure 2. The new dependency graph and Hasse diagram of the labeled poset are shown as well.
For more complicated dependency graphs , e.g. non-planar ones, the labeled poset arising from a trace monoid over does not have a nice visual realization
Figure 1. The dependency graph of a trace monoid (left), a heap of pieces (middle), and its associated labeled poset (right).
Figure 2. This heap of pieces is created from the heap in Figure 1 by additionally restricting from commuting with and . This adds new edges to the dependency graph and new relations to the poset.
in 2- or 3-dimensional space as a stack of pieces. However, there is still an underlying labeled poset which we can rigorously formalize as a heap. In Section 3, we will formally define all terms so there is no ambiguity about our notation. However, in the remainder of this section, we will assume a few basic definitions that the reader likely already knows, so we can summarize the outline, goals, and main ideas of this paper.
Since Viennot introduced them in 1986, heaps have been defined in various ways, depending on the context, and usually with the “of pieces” dropped from the name. The following definition is due to R.M. Green  , who defined the category of heaps and applied it to Lie theory. Having a category makes definitions like a subheap and a morphism between heaps both natural and precise, and we will revisit this in Section 3.
Definition 1.2. A heap is a triple consisting of a poset , a graph , and a function to its vertex set, satisfying:
1) For every vertex of , the subset is a chain in , called a vertex chain.
2) For every edge of , the subset is a chain in , called an edge chain.
3) If is another poset over the same set satisfying (1) and (2), then is an extension of .
Heaps arise naturally in Coxeter theory, because every reduced word in a Coxeter group can be thought of as a labeled linear extension of a heap over the Coxeter graph . This is best seen by an example, and the one that follows should be quite illustrative. It will be a running example that we will revisit throughout this paper.
Running Example 1. Consider the finite Coxeter group , whose Coxeter graph is shown in Figure 3 on the left1. In this Coxeter group, , and so the element can also be written as . Both of these reduced words gives rise to a heap, which are shown in Figure 3. It is easy to see that these two heaps describe different words in the trace monoid , where . However, they represent the same group element in .
1Normally, the vertices of are , but we are using , for consistency with the vertex sets of and , which will appear in later examples.
Heaps generally do not provide a “magic bullet” for proving theorems in Coxeter theory or elsewhere, but they are often quite useful. They have been applied to a variety of topics in pure and applied mathematics, physics, computer science,
Figure 3. The element in the Coxeter group has two heaps, one for each commutativity class.
and engineering. Examples include fully commutative   and freely braided  elements in Coxeter groups, Kazhdan-Lusztig polynomials  , representations of Kac-Moody  and Lie algebras  , Q-system cluster algebras  , parallelogram polyominoes  , -analogues of Bessel functions  , Lyndon words  , lattice animals  , Motzkin path models for polymers  , Lorentzian quantum gravity  , modeling with Petri nets  , control theory of discrete-event systems  , and many more.
Returning to Coxeter groups, heaps provide a framework for reducibility: commutativity classes of elements correspond to heaps, and reduced words to labeled linear extensions. The goal of this paper is to develop and study a cyclic version of a heap. This was originally motivated by a need for a framework of cyclic reducibility in Coxeter groups, though we expect that this structure will appear in other settings in combinatorics and beyond. Cyclic reducibility in Coxeter groups is closely related to the conjugacy problem, but it is also interesting in its own right. To motivate this connection, note that conjugating a reduced word by the initial generator cyclically shifts it, e.g.
Loosely speaking, one can think of our cyclic version of a heap as the result of identifying (or gluing) the top with the bottom of the diagrams in Figures 1-3, so that the “heap of pieces” is not a vertical stack, but rather a cylinder. For simple examples, such as the ones already given, this concept is visually clear. However, it is much less clear to how to formalize this mathematically and what the underlying structure should be, especially for general dependency graphs.
The answer to this involves a fairly new concept of a toric poset, introduced by Develin, Macauley, and Reiner in 2016 . A toric poset is a cyclic version of an ordinary poset, that is generated by the equivalence under making minimal elements maximal, in the sense of Equation (1.1) above. Many fundamental features of posets have very natural cyclic, or “toric” analogues. For example, a chain in a poset is a totally ordered set, but a toric chain in a toric poset represents a totally cyclically ordered set. An extension of a poset is defined by adding relations. The toric counterpart to this concept is called a toric extension, but in order to see how these are analogous, one has to view things geometrically, and that is where the “toric” name comes from. A finite poset can be viewed as an acyclic directed graph (but not uniquely), and that can be associated with a chamber of a graphic hyperplane arrangement in . Though and hence are not uniquely determined by the poset, the particular chamber is. The geometric interpretation of the equivalence generated by making minimal elements maximal is quotienting out by the integer lattice . The result is a (toric) hyperplane arrangement in the n-torus . The chambers of are in bijection with the acyclic orientations of under the equivalence of converting sources into sinks, and these are called toric posets over . Now, back to extensions: an extension of a poset can be described geometrically as adding hyperplanes to the arrangement , and a (toric) extension of a toric poset corresponds to adding (toric) hyperplanes to . There are also natural toric analogues of linear extensions, transitivity, Hasse diagrams, intervals, antichains, order ideals, morphisms, and -partitions, among others. The ones relevant to toric heaps will be discussed later when we formalize them in Section 6. More details about these and others can be found in   .
The formal definition of a toric poset can be found in Definition/Theorem 5.1. However, now that we have conveyed the intuitive idea of it, we can give the formal definition of a toric heap. It should be thought of as a labeled toric poset—a cyclic version of an ordinary heap.
Definition 1.3. A toric heap is a triple consisting of a toric poset , a graph , and a function to its vertex set, satisfying:
1) For every vertex of , the subset is a toric chain in , called a toric vertex chain.
2) For every edge of , the subset is a toric chain in , called a toric edge chain.
3) If is another toric poset over the same set satisfying (1) and (2), then is a toric extension of .
The remainder of this paper is organized as follows. In Section 2, we discuss posets over graphs, and review relevant concepts in Coxeter theory. We use these concepts as motivating examples in Section 3, where we further study heaps over graphs and the resulting categories. In Section 4, we show how conjugation of Coxeter elements can be described by a source-to-sink operation on acyclic orientations. Generalizing this construction leads to the fully commutative (FC) and cyclically fully commutative (CFC) elements, which illustrate the need for a framework of cyclic reducibility in Coxeter theory. In Section 5, we review the concept of a toric poset, both geometrically as a chamber of a graphic toric hyperplane arrangement, and combinatorially as an equivalence class of acyclic orientations. This allows us to finally define toric heaps formally, and we look at the resulting categories. In Section 6, we formalize cyclic reducibility in Coxeter groups. We start with cyclic words, and distinguish between words and group elements being cyclically reduced and torically reduced. This leads us to the concept of cyclic commutativity classes. Next, we define the toric heap of a torically reduced word in any Coxeter group. In Section 7, we analyze new classes of elements that arise in this paper that are called torically fully commutative (TFC) and faux CFC. The former are the elements that have only one cyclic commutativity class, and the latter are those that additionally admit long braid relations. Finally, in Section 8, we discuss recent work on reducibility, cyclic reducibility, and conjugacy using the toric heap framework. A few beautiful results by T. Marquis in  are inaccurate as stated, but easily corrected by replacing “cyclically reduced” with “torically reduced”. We conclude in Section 9 with some open problems and directions for future research.
2. Combinatorial Coxeter Theory
Though the theory of heaps can be developed independently, Coxeter groups provide a wealth of useful and motivating examples, and so we will introduce them right away. More information can be found in classic texts such as Humphreys  or Björner and Brenti . In this section, we will begin by defining posets over graphs, and then show how they arise in Coxeter theory. That will naturally lead us into heaps, which will be done in Section 3.
2.1. Posets over Graphs
Throughout this paper, will be an undirected graph without loops, a nonempty finite set, and a binary relation that is reflexive, antisymmetric, and transitive. The pair is a partially ordered set, or poset. Usually we will write instead of , as the relation is generally understood.
An acyclic orientation of determines a partial ordering on , where if and only if there is an -directed path from to . We denote this poset by , and say that it is a poset on . Let be the set of all acyclic orientations of . It should be noted that a (finite) poset does not uniquely determine a graph. However, given a poset , there is a unique minimal graph with respect to edge-inclusion, called the Hasse diagram, and a unique maximal graph , called the transitive closure, from which arises as an acyclic orientation. A simple example of this is shown in Figure 4, where acyclic orientations of four different graphs (the undirected versions of those shown) all describe the same 5-element poset.
If for every in , either or holds, then is a total order, and is a totally ordered set. Naturally, we write if and . A totally ordered subset of a poset is called a chain.
2.2. Coxeter Groups
A rank- Coxeter system is a pair consisting of a set that generates a Coxeter group by the presentation
Figure 4. Four acyclic directed graphs that describe the same 5-element poset.
Each bond strength if and only if , and is precisely the order2 of . Distinct generators commute if and only if . A Coxeter system has a Coxeter graph which has vertex set (or alternatively, ) and an edge with label for each noncommuting pair of generators. Labels of 3 are usually omitted because they are the most common. A Coxeter system is irreducible if is connected.
If a word is equal to when considered as an element of , we say that it is a word or expression for . If furthermore, is minimal, we call it a reduced word for , and we call its length, denoted . Let be the set of reduced words for and be the set of all reduced words. We typically write words using an upright font, though it is common to speak of a word as also being a group element .
For each integer and distinct generators , define
A relation of the form is a braid relation, and a short braid relation3 if . The braid relations generate an equivalence on , denoted . A classic theorem of Matsumoto  says that the resulting equivalence classes are in bijection with the elements of .
Theorem 2.1 (Matsumoto). Any two reduced words for differ only by braid relations.
2For ease of notation, we allow , and say that for any .
3Some authors call a short braid relation if , and a commutation relation if .
By Matsumoto’s theorem, it is well-defined to let the support of an element , denoted , be the set of all generators appearing in any reduced word for . If , then we say that has full support.
The short braid relations generate an equivalence relation ~ on that is coarser than . The resulting equivalence classes are called commutativity classes. Clearly, the reduced words of any are a disjoint union of commutativity classes, i.e.
for some reduced words , and where is the commutativity class that contains .
Definition 2.2. An element is fully commutative (FC) if contains only one commutativity class. Let denote the set of fully commutative elements of .
The classification of finite and affine Coxeter groups is well known, and it consists of several infinite families and some exceptional cases . We will denote these groups by e.g. , , and their Coxeter graphs by, e.g. , , etc.
Running Example 1 (continued). Consider the word as an element of three different Coxeter groups, one for each of the Coxeter graphs shown below. Recall that we are deliberately using instead of the usual as the generating set of so that all three Coxeter graphs have the same vertex sets.
The word is not reduced in because . It is reduced in but not FC, because . The partition of the reduced words into commutativity classes is
Finally, the word is reduced in and the corresponding group element has a unique commutativity class, , so it is FC.
3. Labeled Posets and Heaps
Recall from Definition 1.2 that a heap is a triple , where is a map from a poset to a graph. We will call the heap poset, the heap graph, and the labeling map. Recall that the partial order on is minimal (coarsest) such that the preimage of each vertex and the preimage of each edge in are chains. However, when defining the heap from a concrete object, such as a reduced word in a Coxeter group, it is also necessary to specify the relative order of the elements within each of these chains. We will do this with an acyclic orientation.
Definition 3.1. Given a word in , consider the graph , where and is the set of all for which and . Let be the orientation where each edge is oriented as if and otherwise. Define the poset .
Definition 3.2. Fix a Coxeter system , and let be a word in . Define the labeling map
The triple is called the heap of . If , then we say it is a heap of the group element .
By construction, distinct words in give rise to distinct heaps, even if they are in the same commutativity class. For example, consider the words and in . Even though , the heaps and are different. We would like to say that they are “the same,” and we can do this using the concept of a heap isomorphism from . Let Heap be the category of heaps, where morphisms are defined below.
Definition 3.3. A morphism from one heap to another is a pair , where is a poset morphism and is a graph homomorphism, satisfying :
If is a heap morphism with being the identity map on , and is injective, then is a subheap of . If and are both bijective, then the two heaps are isomorphic. If we want to only consider heaps over a fixed graph , which is often the case, we can define . We will mostly refrain from the category theory point of view in this paper, because the focus is more on Coxeter theory. A thorough categorical treatment of heaps and toric heaps will be done in a forthcoming paper. However, in order to speak about morphisms in Coxeter theory where , we would need to be clear on how to define a homomorphism between Coxeter graphs, especially regarding edge weights. We will not do that here because we will not be using it.
Proposition 3.4. If are reduced words in , then the heaps and are isomorphic.
Proof. Since and differ by a sequence of short braid relations, it suffices to consider the case when they differ by a single adjacent transposition . In this case, the heap isomorphism is , where the transposition is a poset isomorphism and is the identity.
Henceforth, we will always speak of heaps up to isomorphism. By Proposition 3.4, each commutativity class of has a unique heap. Therefore, if is FC, then we may speak of as the heap of the group element . In contrast, for non-FC elements, different commutativity classes generally give non-isomorphic heaps. Our running example illustrates this nicely.
Running Example 1 (continued). Let us recall first as an element in the Coxeter group , and then in . In , it has two commutativity classes, and the associated heaps were shown in Figure 3. In , the bond strength between and is increased to . This means that is FC, and so the only heap of this group element is the first one shown in Figure 3.
Heaps of reduced words in Coxeter groups were studied by Stembridge in  , though his definition was slightly different, in that he considered and incomparable if . For reduced words, this makes no difference. In our setting, such an and must be comparable because the -preimage of each edge is a chain, and also contains the preimages of two vertices, and chains in posets are closed under subsets. This is also why the vertex chain requirement is built into the definition. The advantage of our framework and this requirement will become more apparent when we formalize cyclic reducibility using toric heaps. This is also in line with Viennot’s original definition .
The concept of a labeled linear extension of a heap was studied in . Here, we give an abstract definition of a more general concept in our framework. We also drop the word “labeled” because it is implied in the context of heaps. Say that a map is an edge-inclusion if it is the identity map between graphs on the same vertex set, and every edge in is also in .
Definition 3.5. If is the image of a morphism from a heap , where is an extension, and is an edge-inclusion, then we say that it is an extension of . Moreover, it is a linear extension of heaps if is a linear extension of posets.
Given a heap and a graph homomorphism , there need not be a poset and a map such that is a morphism to a heap . However, there will always be (at least) one if is an edge-inclusion, and it is easy to see how to construct —it is a poset generated by the relations in with edge chains for each additional edge in . In general, such a is not unique because there could be a choice of how to order the elements within each new edge chain, as shown in the following simple example.
Example 3.6. Let be the edge-inclusion between the edgeless graph on to the complete graph. The antichain and labeling map define a heap . There are two linear extensions of : let denote the one with and the one with . There are canonical heap morphisms and from to and , respectively. Here, and both send , and and both send . These are shown in Figure 5.
Let denote the set of linear extensions of a heap . In  , these are called labeled linear extensions because they can be canonically indexed by words. For example, a linear extension can be described by the word , where .
Example 3.7. Let be the heap from Figure 1 and the heap from Figure 2. Note that it is easy to define the labeling maps and to adapt those heaps to our framework. Since is an extension and an edge-inclusion, the morphism is an extension of heaps. The total order uniquely describes a heap that is a linear extension of both and .
In the examples from Figure 5, the two linear extensions are clearly characterized by the words (left) and (right).
Figure 5. Two linear extensions of the same heap from Example 3.6.
4. Coxeter, FC, and CFC Elements
One of the goals of this paper is to develop a framework for studying what we call “cyclic reducibility” in Coxeter groups. In this section, we will formalize concepts such as cyclic words and cyclic commutativity classes. In a subsequent section, we will develop a cyclic version of a heap called a toric heap, which is essentially a labeled toric poset. To motivate this, we will begin with conjugation of Coxeter elements, and then extend that to the cyclically fully commutative (CFC) elements. Throughout, let be a fixed Coxeter system with Coxeter graph . Given words, e.g. in , we will denote the corresponding group elements by in .
4.1. Conjugation of Coxeter Elements
Let be a Coxeter system. A Coxeter element is the product of all generators in some order. We denote the set of all Coxeter elements by . Every Coxeter element of gives rise to a canonical acyclic orientation of the Coxeter graph , defined by
where is any linear extension of . It is easy to see that this map is a bijection, and so we write to denote “the Coxeter element defined by ”, and for “the acyclic orientation given by ”. Since Coxeter elements are FC, the heap poset of does not depend on the choice of reduced word, so we may write .
Proposition 4.1. The heap poset of a Coxeter element is for any reduced word .
Proof. Let . By construction, , and the labeling map is defined by . Since has no repeated generators, each preimage has size 1, and so is trivially a chain. For each edge in , say without loss of generality, the preimage is a chain with . This matches the orientation of the edge by from Definition 3.1.
Since linear extensions of heaps can be indexed with words, we can consider the set as a collection of words in . A subset of is said to be order-theoretic if it is the set of linear extensions of a heap. The following is a slight reformulation of Theorem 3.2 from .
Proposition 4.2. For an element , the following are equivalent:
1) is fully commutative.
2) is order-theoretic.
3) for some (equivalently, every) .
We will state and prove a cyclic analogue of this result in Theorem 7.2, which involves a new class of elements that are called torically fully commutative (TFC). Before we can get there, we will first motivate the idea of cyclic reducibility with a simple example involving Coxeter elements. Observe that a cyclic shift of a Coxeter element is also a Coxeter element, and because for every , it is also a conjugation by the initial letter:
On the level of acyclic orientations, these two Coxeter elements are related by converting the source vertex (an initial generator) into a sink (a terminal generator). This generates an equivalence relation on , and hence on , that we call toric equivalence. This was first studied by Pretzel in  via an operation he called “pushing down maximal vertices”. In  , H. Eriksson and K. Eriksson showed that these equivalence classes are in 1-1 correspondence with the conjugacy classes of . In a recent preprint of Adin et al. that introduces toric -partitions, these equivalence classes are called toric DAGs .
Theorem 4.3 (  ). In any Coxeter group, are conjugate if and only if .
Thus, there are bijections between the Coxeter elements and , and between their conjugacy classes and toric equivalence classes, defined as follows:
The sets and are enumerated by the Tutte polynomial at and , respectively .
Example 4.4. Consider the affine Coxeter group , whose Coxeter graph is the circular graph . Consider the following three reduced words for Coxeter elements: , , and (using instead of the usual ). The corresponding acyclic orientations are shown below4.
The reduced words for Coxeter elements in comprise distinct elements. The 14 acyclic orientations fall into toric equivalence classes: and have size 4, and has size 6, the elements of which are shown below.
4For convenience, in the examples in this section, all of the graphs are drawn so that their vertices are the actual generators, rather than labeled bullets.
By Theorem 4.3, the 14 Coxeter elements fall into 3 distinct conjugacy classes, and any two conjugate Coxeter elements differ only by cyclic shifts and short braid relations. This can be visualized by writing the reduced words as circular words, and allowing the usual braid relations:
In the circular words and above, no short braid relations can be
applied, so both and are conjugate to only 4 Coxeter elements each—all cyclic shifts. In contrast, the relations and can be applied to , yielding three other “reduced cyclic words”:
There are six distinct Coxeter elements, and 16 reduced words, that can arise from these four cyclic words, assuming they are read off clockwise:
The elements in the ith column above are the linear extensions of the poset defined by the ith orientation in Equation (4.2).
Example 4.4 should motivate the value of developing a theory of cyclic reducibility in Coxeter groups. For example, the four cyclic words in Equation (4.3) should be thought of as lying in the “cyclic commutativity class” containing the “cyclic word” . In Section 6, we will develop this framework. But first, we need to focus on the curious “cyclic partial order” structure that arises. Cyclic words under the equivalence generated by short braid relations are like cyclic analogues of traces, though without the monoid structure, because there is no canonical way to concatenate cyclic words. This cyclic poset structure can be formalized via toric posets  , which leads to the concept of a toric heap. This is essentially a labeled toric poset, in the same sense of how ordinary heaps are labeled ordinary posets. It allows us to extend the examples shown in this section far beyond just Coxeter elements, which we will do next.
4.2. Cyclically Fully Commutative (CFC) Elements
Now that we have seen the interplay between Coxeter elements, acyclic orientations, and heaps, and how they behave under conjugacy, we will extend these ideas to a larger class of elements. This will elucidate the key structural properties as well as motivate the main ideas of our cyclic reducibility framework.
5Some authors call this property straight, which is motivated by a geometric view of Coxeter groups. We will use the term logarithmic, as our viewpoint is more purely combinatorial.
It is well known that in any Coxeter group, if , then , and so . If equality holds for all , then we say that is logarithmic5. In 2009, it was shown independently by D. Speyer  and H. Eriksson and K. Eriksson  that in infinite irreducible Coxeter systems, Coxeter elements are logarithmic. It is simple to extend this to the non-irreducible case—each connected component of must be the Coxeter graph of an infinite group. The logarithmic property was key to the Erikssons’ proof of the conjugacy problem (Theorem 4.3). Also crucial was the source-to-sink property, i.e. toric equivalence. In plain English, we mean that 1) Coxeter elements are FC (they avoid long braids), and 2) cyclic shifts of Coxeter elements remain FC. These properties can naturally be extended beyond Coxeter elements.
Definition 4.5. An element is cyclically fully commutative (CFC) if for any reduced word of , every cyclic shift is reduced and FC.
Example 4.6. Figure 6 shows examples of CFC elements in two affine Coxeter groups. On the left is the Coxeter graph of the group and the CFC element drawn in a circle so the reader can visually see how there are no long braids. To the right is the Coxeter graph of the group and the CFC element , also drawn in a circle.
CFC elements were introduced and studied in 2012 by Boothby et al. . They have recently been characterized and enumerated in all affine Coxeter groups, and their generating functions were shown to be rational in all Coxeter groups  .
5. Labeled Toric Posets and Toric Heaps
5.1. Posets and Toric Posets, Geometrically
Throughout this section, is a Coxeter graph, is an undirected graph, is the set of acyclic orientations of , and is toric equivalence, i.e. the equivalence relation on generated by source-to-sink conversions.
A toric poset should be thought of as a cyclic version of a poset. The most concrete way to define them are as toric equivalence classes of , and we write this as, e.g. . However, this has two significant drawbacks: first, it suggests a dependence on the graph , which is a little misleading. Recall that we can similarly define a poset on a graph, though in actuality, is almost never uniquely determined. Specifically, there is a unique minimal graph (the Hasse diagram, ), and a unique maximal graph (the transitive closure, ) on such that any whose edge set is between the edge sets of these two extremes (with respect to subset inclusion) will work. Of course, care must also be taken with how to define so that , but that is straightforward—any shared edges must be oriented the same way.
Figure 6. CFC elements in affine Coxeter groups, drawn in a circle to highlight the absence of long braids, as well as to motivate concepts such as “cyclic words” and “cyclic commutativity classes”, which toric heaps will allow us to formalize.
The second drawback of the notation is that it obscures the “more proper” geometric way to define a toric poset. We will motivate this by revisiting the geometric interpretation of . In fact, finite posets can be defined and developed purely geometrically, as chambers of graphic hyperplane arrangements. For distinct vertices and in , let be the hyperplane in . The graphic arrangement of is the set . Each point in the complement determines a canonical acyclic orientation , by directing the edge as if . The fibers of this mapping are the chambers of the , and so this induces a bijection between chambers of and acyclic orientations of :
At this point, one could define a poset to be any subset of that arises as a chamber of some graphic hyperplane arrangement. This removes the reference to a particular graph in the definition. Given a poset , we write for the chamber in determined by . Given a chamber , we write for the poset determined by .
Though this geometric perspective is a bit superfluous for ordinary posets, it is absolutely necessary for toric posets, where it is not so clear how to pull apart the concept of a toric poset from the underlying graph. The geometric definition of a toric poset arises from the observation that if we first quotient out by the integer lattice , then converting a source into a sink corresponds to crossing a coordinate hyperplane , and this does not change the corresponding connected component in the torus . An example of this is shown in Figure 7.
This leads us to our first of five “Definition/Theorems”. We use that term
Figure 7. The hyperplane arrangement of the complete graph . The toric arrangement is achieved by identifying opposite sides of the unit cube. Doing this merges the three regions corresponding to the three acyclic orientations shown into one single toric chamber.
because each of them involves a non-trivial statement or equivalence proven in  , which allows us to take them as the definition in this paper.
Definition/Theorem 5.1. A toric poset over is characterized by either:
1) an equivalence class in ,
2) a chamber of the toric hyperplane arrangement in .
We will write to mean the toric poset characterized by in . Given a toric poset , we write when we wish to speak of the chamber in determined by , and given a chamber , we write to emphasize the toric poset determined by it.
Aside from the definition not depending on a distinguished graph , the second advantage to the geometric perspective is the recurring theme that many standard features of ordinary posets, such as chains, antichains, Hasse diagrams, transitive closure, order ideals, and so on, have natural toric analogues. However, it is usually not clear how these should be defined in terms of an equivalence class of acyclic orientations. Instead, the natural definition often only becomes apparent when one interprets the classical definition geometrically, and then passes to the quotient , as illustrated by the following commutative diagram:
Often, this toric analogue then has a natural combinatorial interpretation in terms of directed graphs, which usually ends up being more convenient. A list of these can be found in the Introduction of .
For an example of this, consider a non-edge . One might ask whether and are comparable in . In other words, would adding to force its orientation by , which happens when one of the two ways to orient it would create a directed cycle? If so, is implied by transitivity, and either or . Geometrically, this means that the hyperplane is disjoint from the chamber of . The combinatorial condition is also straightforward: is implied by transitivity if and only if and lie on a common directed path in (i.e. lie on a chain in ).
There is a toric analogue of transitivity, which is easy to state geometrically: the edge is implied by toric transitivity if the toric hyperplane is disjoint from the chamber of . The combinatorial condition of this is less clear due to the absence of a binary relation, but luckily, it has a simple answer, which is basically just adding the word “toric” to the ordinary case. Specifically, a toric directed path in is a directed path such that the edge is also present, as shown in Figure 8. It was shown in  that if is a toric directed path in , then some cyclic shift is a toric directed path in for each .
It is worth noting that just like directed paths in ordinary posets, a two-element
Figure 8. A chain in a poset is any subset that lies on a directed path (left). A toric chain in a toric poset is any subset that lies on a toric directed path (right).
toric directed path is an edge, and all vertices are one-element toric directed paths. We will say that the empty set is vacuously a directed path and a toric directed path.
Definition/Theorem 5.2. A non-edge is implied by transitivity in if and only if and lie on a directed path in .
A non-edge is implied by toric transitivity in if and only if and lie on a toric directed path in .
For ordinary posets, adding all edges implied by transitivity, in any order, yields the transitive closure, . The toric transitive closure can be defined analogously.
For ordinary posets, removing all unnecessary edges, in any order, yields the Hasse diagram, denoted . Geometrically, this just means removing all hyperplanes that are disjoint from the chamber . The toric Hasse diagram is completely analogous, and denoted . However, the Hasse diagram of and the toric Hasse diagram of are generally not the same. To see why, we need the notion of a toric chain.
A key concept behind the aforementioned features of posets is that of a chain, which is a totally ordered set. This can be characterized geometrically in terms of the coordinates of the entries of all points in the corresponding chamber, or combinatorially as a subset of vertices lying on a directed path in . A toric chain in is a totally cyclically ordered set. This can also be characterized geometrically in terms of the coordinates of the entries of all points in the corresponding toric chambers. Luckily, its combinatorial characterization is both simple and analogous to the ordinary poset case.
Definition/Theorem 5.3. A set is a:
• chain of if it lies on a directed path in ;
• toric chain of if it lies on a toric directed path in .
Both chains and toric chains are closed under subsets.
Example 5.4. Let , , and be the line, circular, and complete graph on 4 vertices, respectively. Assume that the vertices are ordered “naturally,” i.e. they all contain (at least) the edges , , and . Define , , and so that is oriented if . Then
Figure 9 shows a visual of these examples. The solid lines show the edges that
Figure 9. Left: The Hasse diagram of consists of the solid edges (undirected). The dashed edges are additionally implied by transitivity. Right: The toric Hasse diagram of consists of the solid edges (undirected). The dashed edges are implied by toric transitivity. See Example 5.4 for details.
make up the Hasse and toric Hasse diagram. The transitive closure and toric transitive closure are given by including the (undirected) dashed edges as well.
The last concepts that we need the toric analogue of are extensions and total orders. A total order is a poset , where is the complete graph. Geometrically, this corresponds to a chamber of . Intuitively, a total toric order is a toric poset that is totally cyclically ordered.
Definition/Theorem 5.5. A total toric order is characterized by either:
1) a toric poset ,
2) a chamber of .
An extension of a poset is characterized combinatorially by adding relations (or edges to ), or geometrically by in (the result of adding hyperplanes to ). Moreover, is a linear extension of if it is an extension and a total order.
Definition/Theorem 5.6. Let be a toric poset, and assume without loss of generality that is its toric Hasse diagram. A toric extension of a toric poset is characterized by either:
1) in ,
2) , where , , and all edges in are oriented the same way by and .
If is a toric extension of and a total toric order, then it is a total toric extension.
There are total orders on a size- set , where is the Tutte polynomial. In contrast, there are
total toric orders on . Each one is indexed by a cyclic equivalence class of permutations
Geometrically, these correspond to the toric chambers of .
5.2. Toric Heaps
Before we formalize cyclic reducibility, it is worth pausing to return to our familiar example for guiding intuition. Recall (see Definition 1.3) that a toric heap has a labeling map such that the inverse image of every vertex and every edge is a toric chain. Moreover, must be minimal with respect to these chains.
Running Example 1 (continued). Recall that the element in has two distinct heaps, shown in Figure 3. Note that in each heap, the edge chain forms a length-4 directed path in the Hasse diagram, and the size-3 edge chain lies on a length-4 directed path. In the toric heap, these directed paths become toric directed paths, and so the toric Hasse diagram gets two additional edges. This is shown in Figure 10; the curved edges are these two additional ones.
Note that the two toric heaps shown in Figure 10 are actually the same, because the Hasse diagrams of the toric heap posets differ by a single source-to-sink conversion. Algebraically, this is because the word can be transformed into two ways: by a long braid relation , or by a sequence of short braid relations and cyclic shifts. When we formalize this, we will say that the cyclic words and are in the same cyclic commutativity class. This is shown in Figure 11.
We can define structure-preserving maps between toric heaps using commutative diagrams in the same manner that we did between ordinary heaps in Definition 3.3. This leads to the category torHeap of toric heaps and toric heap morphisms. To properly define a toric heap morphism, we need the definition of a general toric poset morphism. However, we will omit this and instead refer the reader to  , because in this paper, the only morphisms we will use are extensions and isomorphisms. The former has been introduced and the latter is elementary: if there is a graph isomorphism carrying the acyclic orientation , then the toric posets and are isomorphic. Alternatively, it is straightforward to define this geometrically.
Figure 10. Though the element in the Coxeter group has two distinct heaps (see Figure 3), one for each commutativity class, both of these give rise to the same toric heap. Intuitively, one can think of this as identifying the top with the bottom of a stack of balls, making it cylindrical. The undirected versions of the digraphs shown are the toric Hasse diagrams of the toric heap posets.
Figure 11. A non-CFC element with only one cyclic commutativity class. The cyclic word shown in the middle differs from via a long braid relation , but also via a short braid relation, . This will be formalized in Section 6; this type of element will be called torically fully commutative (TFC).
Definition 5.7. A morphism from one toric heap to another is a pair , where is a toric poset morphism and is a graph homomorphism, satisfying :
As before, if and are both bijective, then the two toric heaps are isomorphic. The concept of a toric subheap is not as natural as an ordinary subheap, because the concept of a cyclic subword of a cyclic word is not as natural as subwords of regular words.
The concept of an extension naturally carries through from heaps to toric heaps. Recall that this is needed to properly formalize the minimality condition in Definition 1.3(3). We often drop the word “toric” for brevity, i.e. there is no difference between an extension and a toric extension of a toric heap.
Definition 5.8. If is the image of a morphism from a toric heap , where is an extension, and is an edge-inclusion, then we say that it is a (toric) extension of . Moreover, it is a total (toric) extension of toric heaps if is a total toric extension of toric posets.
As we did with heaps, if we want to only consider toric heaps over a fixed graph , we can define the category . However, we will generally avoid such language here, and save a thorough categorical treatment of heaps and toric heaps for a future paper.
Now that we have laid out the fundamentals for cyclic reducibility in Coxeter groups, we will develop a framework to describe it using a cyclic analogue of a heap. The basic idea is to take our “ball stack” heap of pieces and wrap it in a cylinder by identifying the top with the bottom of the picture. Obviously, this idea in such a simplistic form is well-suited for line graphs. In her 2014 masters thesis  , B. Fox proposed this idea in type A Coxeter groups (though it works equally well as long as is a line graph), calling it a “cylindrical heap”. She acknowledged that in doing this, one loses the natural poset structure. In a 2017 paper, M. Pétréolle defined an operation on heaps he called the “cylindric closure” . He basically turned each maximal edge chain and vertex chain into a cyclically ordered set by declaring for each vertex chain and each edge chain, the minimal element and the maximal element are related by . This relation extends the partial order, but since antisymmetry is immediately destroyed, it is not a poset. For example, the relation between the elements in the toric directed path in Figure 8 would be
In some sense, Pétréolle uses this relation as an effective “hack” to prove some beautiful results. Namely, he characterizes CFC elements in terms of pattern-avoidance of these cylindrical closures, and uses this to enumerate the CFC elements in all affine types. In the next section, we will formally define and develop the mathematical structure that lies behind the scenes here, and certainly elsewhere in combinatorics.
6. Cyclic Reducibility in Coxeter Groups
Throughout, let be a fixed Coxeter system with Coxeter graph . As before, given words, e.g. in , we will denote the corresponding group elements by in . At times, we can even go the other direction. Specifically, when given an element , we may write to mean “an arbitrary reduced word for ”.
6.1. Cyclic Words and Commutativity Classes
Definition 6.1. A word is cyclically reduced if every cyclic shift of it is a reduced word for some element in . A group element is cyclically reduced if every reduced word for is cyclically reduced.
A word is torically reduced if it remains reduced under any sequence of cyclic shifts and/or braids. A group element is torically reduced if any (equivalently, every) reduced word for is torically reduced.
It is clear that torically reduced implies cyclically reduced, for both words and elements. However, the converse fails, as shown by the following example.
Example 6.2. The element is cyclically reduced because it has only one reduced word, and every cyclic shift of it is reduced. However, it is not torically reduced because its cyclic shift , and this latter word is not cyclically reduced. This also shows how a word can be cyclically reduced despite the group element failing to be cyclically reduced. These examples are illustrated in Figure 12.
Definition 6.3. Let be a word in . The cyclic word or cyclic expression containing is the equivalence class
If is cyclically reduced, then we say that the cyclic word is reduced, and vice-versa. We say that is torically reduced if is torically reduced.
Let denote the set of all cyclic words and let be the set of all reduced cyclic words. Write and for the set of torically reduced words and cyclic words, respectively.
Figure 12. The element in is cyclically reduced but not torically reduced.
A word is a subword of if it appears as a (consecutive) subword of some cyclic shift of . Loosely speaking, we say that and differ by a braid if one can be converted into the other by replacing a subword with . The formal definition follows.
Definition 6.4. Two cyclic words and differ by a braid if there is some and such that can be converted into by replacing a subword of the form with for some .
The equivalence relations and , generated by short braids and all braids, respectively, each define natural equivalence classes on the set of reduced words. Elements of are commutativity classes, and by Matsumoto’s theorem, elements of are in 1-1 correspondence with the group elements of W. Since we are looking for cyclic analogues of classical results, it is natural to look at the equivalence classes of the set of torically reduced words defined by these relations.
Definition 6.5. Let be torically reduced. The cyclic commutativity classes of and of are defined as
Definition 6.6. Let be torically reduced. The toric equivalence classes containing and are
The toric equivalence class of a torically reduced element , denoted , is defined as
We write whenever .
By Matsumoto’s theorem, it is well-founded to define and . Since is coarser than , the set consists of at least the cyclic commutativity class of , and potentially more. In other words, for every torically reduced , we have a unique decomposition
of its torically equivalent cyclic words into cyclic commutativity classes, where each , and each is a union of cyclic words. We also have a similar decomposition of torically reduced words,
It is clear that is contained in the conjugacy class . It is an open question as to when contains torically reduced elements not in . This will be discussed more in Section 8.
Example 6.7. The element is torically reduced in the affine Coxeter group , and contains three cyclic commutativity classes, each containing one cyclic word: , , and , shown below.
It is clear that all three cyclic words above lie in different cyclic commutativity classes, because they have a different multiset of generators that appear in them. Additionally, each cyclic commutativity class contains only one cyclic word because none of the generators pairwise commute. The set contains 12 torically reduced words: four from each of the three cyclic commutativity classes. The set consists of the 6 distinct group elements in defined by these 12 words—each one has exactly two reduced expressions for it.
An interesting difference between reducibility and cyclic reducibility lies in the fact that in the cyclic case, the presence of long braid relations does not necessarily imply multiple (cyclic) commutativity classes. Specifically, is FC if and only if contains only one commutativity class. Our running example shows how this fails in the cyclic case.
Running Example 1 (continued). The element in (see Figure 10) is not CFC. However, contains two cyclic words, and , but only one cyclic commutativity class, as shown in Figure 11. The set consists of the ten reduced words that lie in one of these two equivalence classes. These reduced words describe four distinct group elements:
and these comprise the set of torically equivalent elements to .
Definition 6.8. A torically reduced element with a unique cyclic commutativity class is called torically fully commutative (TFC). If it is additionally not CFC, then we call it faux CFC.
The element in from Running Example 1 is faux CFC. We will return to the TFC and faux CFC elements in Section 7.
6.2. Toric Heaps in Coxeter Groups
Just like how a word gives rise to a canonical heap (Definition 3.2), it also gives rise to a canonical toric heap. With ordinary heaps, we are mainly only concerned with reduced words. Similarly, with toric heaps, we only need to focus on torically reduced words.
Though many ordinary poset features have natural toric analogues, there is one crucial property that fails to carry over, and as a result, the toric heap from a word must be carefully defined. Every finite poset is completely determined by knowing 1) its set (a simplicial complex) of chains, and 2) the total order within each chain. Among other things, this gives rise to the order complex of a poset, which is fundamental to poset topology . Unfortunately, there does not appear to be a toric analogue of this property, and hence, no sort of toric order complex either. To see why, consider the toric posets and , where is a 5-cycle, and the acyclic orientations and are shown below:
It is elementary to see that source-to-sink conversions preserve the difference between the number of clockwise edges and counterclockwise edges. Since this quantity is in and in , then , and hence T and are distinct toric posets. However, both of them have the same set of nonempty toric chains: five of size 1 (the vertices), and five of size 2 (the edges). Moreover, each size-2 toric chain trivially has the same cyclic order. Thus, to define a toric poset over a graph, it is not enough to just specify the toric chains and the cyclic order within each one.
The easiest way to resolve this is to simply define the toric heap poset directly from an acyclic orientation. Recall how the poset naturally arises from a word in Definition 3.1. This also defines a natural toric poset, denoted . Compare the following definition to that of the heap from Definition 3.2.
Definition 6.9. Fix a Coxeter system , and let be a word in . Define the labeling map
The triple is called the toric heap of .
Given a word , the labeling maps of the heap poset and toric heap poset are described by the following commutative diagram, where is the identity map on the underlying set .
Since toric directed paths are directed paths, pulls back toric chains in to chains in . However, the converse need not hold. For example, consider the word in . The heap poset is totally ordered. However, there is no size-3 toric chain in .
Consider two torically reduced words in the same commutativity class, . By Proposition 3.4, the heaps and are isomorphic. Let be the poset isomorphism. The toric heaps and are related by the following commutative diagram
where is a bijection, and so is a toric poset isomorphism. A similar argument shows that if and differ by a single cyclic shift, then and are isomorphic. Specifically, define by , and consider only the right-hand side of the commutative diagram in Equation (6.4). Since toric heaps are preserved by cyclic shifts and short braid relations, then torically equivalent words will yield isomorphic toric heaps. Thus, as with heaps, we will henceforth only consider toric heaps up to isomorphism.
Recall that there is a bijection between the linear extensions of a heap and words in the commutativity class . The cyclic analogue of this holds as well. Since a total toric extension is a toric poset that is a total toric order, we usually denote it with a cyclic word, e.g. , instead of as a toric heap over the complete graph. Clearly, is one total toric extension of . Given , define
As with the case of ordinary reducibility, there is a bijection between total toric extensions and cyclic commutativity classes.
Theorem 6.10. Let be a torically reduced word in a Coxeter system . Then
Proof. Suppose , and pick from , which defines a toric heap over the complete graph. Let be the extension, where is the edge-inclusion map.
Since and are total toric extensions of , then and differ by a sequence of cyclic shifts and short braid relations. Therefore, .
Conversely, let , which means there is a sequence of cyclic shifts and short braid relations that carries to . By Corollary 5.2 in  , every (closed) toric chamber is the union of closed chambers corresponding to the total toric extensions of . This means that and are both total toric extensions of .
Example 6.11. Let us revisit the Coxeter elements in the affine Coxeter group from Example 4.4. As before, let , , and ; see Equation (4.1). Both and are the only cyclic words in their cyclic commutativity class, and so
Additionally, for both , the set contains four reduced words—the cyclic shifts of .
In contrast, contains four cyclic words that comprise a single cyclic commutativity class:
These were shown in Equation (4.3). Finally, contains 16 reduced words, four from each cyclic word above. These fall into six distinct group elements, which appeared in Equation (4.4).
7. Torically Fully Commutative (TFC) Elements
We begin this section with a reminder of a notational convention that we will use frequently: if we have a group element and write , we are referring to an arbitrary fixed reduced word for .
The fully commutative (FC) elements have been well-studied; see   . It is clear that we have inclusions
The FC elements are those that have a unique heap, i.e. for any reduced word , we have . In this section, we will establish that the torically fully commutative (TFC) elements are those that have a unique toric heap: if , then . After that, we will study basic properties of TFC and the faux CFC elements—those that are TFC but not CFC.
Say that a subset of is torically order-theoretic if it is the set of total toric extensions of a toric heap, i.e. if it can be expressed as for some torically reduced word . We will begin with a simple lemma; note that the converse of it is trivial.
Lemma 7.1. If is torically order-theoretic, then
Proof. Write , its unique decomposition as a disjoint union of cyclic commutativity classes, as in Equation (6.1). Since it is torically order-theoretic, for some . The proof will follow once we establish the following:
The subset containment is immediate, and we have already seen the first equality. The second and fourth equalities are due to Theorem 6.10, and so now we can deduce that . However, since these are non-disjoint equivalence classes, they must be the same, which confirms that the containment in Equation (7.1) is actually an equality and completes the proof of the lemma.
Though the CFC elements are a natural cyclic analogue of the FC elements, one must go up to the TFC elements to get the cyclic version of Proposition 4.2.
Theorem 7.2. For a torically reduced element , the following are equivalent:
1) is TFC.
2) is torically order-theoretic.
3) for some (equivalently, every) .
Proof. The implication (2) (1) was established in the proof of Lemma 7.1, where it was shown that . Also simple is (3) (2), which is immediate from the definition.
For (1) (3): If is TFC, then it has only one cyclic commutativity class, . The first equality is from Equation (6.1) and the second is by Theorem 6.10. This establishes the “for some” part of (3); it suffices to prove the stronger “for every” part. Let , which means that , and is TFC because is. The following chain of equalities will complete the theorem:
Specifically, the first and third are by definition, and the second is because . The fourth equality follows from the proof of the “for some” implication above, applied to the TFC element .
Since every toric poset is completely determined by its set of total toric extensions (  , Corollary 5.2), Theorem 7.2 implies that the TFC elements are those that have a unique toric heap. An open question is to classify all TFC and faux CFC elements in an arbitrary Coxeter group. In this section, we will begin with some examples, and then give some necessary and sufficient conditions for an element to be TFC or faux CFC. Throughout, will be a torically reduced word.
Example 7.3. The following elements are all faux CFC:
1) The element in from Running Example 1.
2) The element in the affine group , which has Coxeter graph
3) The element in the Coxeter group whose Coxeter graph is shown below.
It is obvious that a faux CFC element cannot contain a long braid relation of odd length, because applying a single such relation changes the number of individual generators in the word.
Proposition 7.4. If is faux CFC and is odd, then none of the torically reduced words contain as a subword.
The previous result is a necessary condition for to be faux CFC. Next, we will provide a sufficient condition. Say that is an endpoint of the Coxeter graph if it has degree 1, and is even (respectively, odd) if is even (respectively, odd) for the unique for which . In this case, we call a spoke of , and can speak of spokes being even or odd.
Proposition 7.5. Let be a Coxeter graph with an even endpoint with adjacent vertex . Suppose is a reduced word for some element where the subword satisfies the following two properties:
• contains no generators and , and
• is a reduced word for some CFC element in .
Then is TFC.
Proof. Since is a reduced word for some CFC element containing no nor , then is torically reduced, and the only long braid relation that can be applied to is . Thus, is torically reduced but not CFC. Since commutes with every generator in ,
That is, has only one equivalence (cyclic commutativity) class, and so is TFC.
We conjecture that faux CFC elements (with full support) only occur when the Coxeter graph has at least one even endpoint. It would be desirable to understand how faux CFC elements can be “reduced” down to CFC elements. In our prior examples of faux CFC elements of the form , removing from the word yields an element that can be:
1) CFC, as in Example 7.3(1), or
2) faux CFC, as in Example 7.3(2), or
3) not TFC, as in Example 7.3(3).
Whether the new word is CFC, faux CFC, or not TFC, depends on . For the three cases above, is 1) CFC, 2) faux CFC, 3) not cyclically reduced. We end this section with a conjecture.
Conjecture 7.6. If is faux CFC and torically reduced, then is TFC.
8. Toric Heaps and Conjugacy in Coxeter Groups
We will wrap up this paper by revisiting some of the existing results on Coxeter theory from Section 4, cast them in a cyclic reducibility framework, and discuss some open problems.
Theorem 8.1. Let and be Coxeter elements of W. Then
1) if and only if they have the same heap, and
2) and are conjugate if and only if they have the same toric heap.
The first statement in Theorem 8.1 is an immediate consequence of Matsumoto’s theorem, and the second is Theorem 4.3 using the toric heap language. Note that this fails if we drop the assumption that is a Coxeter element, because in the finite Coxeter group ,
More generally, examples like this exist when distinct subsets , and hence, their standard parabolic subgroups, and , are conjugate in . This phenomenon has been completely characterized by Deodhar  , and it only happens when is finite. The technical condition can be found in (  , Theorem 3.1.3).
The proof of the second statement in Theorem 8.1 heavily relies on two properties of Coxeter elements. The first is toric equivalence, and the second is a theorem proven independently by Speyer in 2009  and by the Erikssons in 2010  : In an infinite irreducible Coxeter group, all Coxeter elements are logarithmic. It is a simple exercise to extend this to the general case of reducible Coxeter groups. Of course, the necessary and sufficient condition is that every connected component of describes an infinite group. In  , a CFC element was said to be torsion free if every factor of the parabolic subgroup describes an infinite group. Equivalently, none of the connected components of the induced graph are of finite-type. It has been proven (see   ) that CFC elements are logarithmic if and only if they are torsion free. Marquis proved that a similar result holds more generally, but it requires a relaxation of the definition of torsion free.
Definition 8.2 (  ). An element is torsion free if it has no reduced decomposition of the form for some spherical subset , some , and some normalizing .
To see why this is a necessary requirement to being logarithmic, suppose that is not torsion free and write . Then for each , we can write for some . Since is finite, there must be some such that , and so
Note that such a is not logarithmic because
Remarkably, Marquis proved that up to toric equivalence, this is the only barrier to a torically reduced element being logarithmic.
Theorem 8.3 (  ). A torically reduced is logarithmic if and only if every torically equivalent is torsion-free.
A simple example of a non torsion-free element in an infinite group can be found by modifying our Running Example from living in the group to .
Example 8.4. Consider the faux CFC element in , as shown below:
Clearly, is faux CFC but is not logarithmic because . It is not torsion-free because taking , we can write for and .
Thus far, we have seen how cyclic reducibility affects ordinary reducibility. Now, we ask how it affects conjugacy.
Matsumoto’s theorem says that if and are reduced words for the same group element, then they differ by braids, i.e. . We are interested in a “cyclic version” of Matsumoto’s theorem, which asks whether the cyclic words of torically reduced conjugate elements differ by braids, i.e. . This is to the conjugacy problem what Matsumoto’s theorem is to the word problem.
Definition 8.5. A -conjugacy class satisfies the cyclic version of Matsumoto’s theorem (CVMT) if any two reduced words of torically reduced elements in C differ by braid relations and cyclic shifts.
As we have seen in Equation (8.1), the CVMT trivially fails in conjugacy classes that have a minimal cyclically reduced element with support conjugate to some other . We conjecture that this is the only times where it fails. In a recent paper  , Marquis proved the CVMT for all elements of infinite order with property (Cent), which means that whenever normalizes a finite parabolic subgroup of , it centralizes the subgroup. Though this condition may seem peculiar, it is quite mild, as it is satisfied by any torsion-free normal subgroup of finite index, which always exists in any infinite Coxeter group by Selberg’s Lemma and the linearity of Coxeter groups (  , Lemma 1). Torically reduced elements that have property (Cent), or are in finite groups, are additionally strongly cyclically reduced (  , Corollary C), which means that , or equivalently, is of minimal length in its conjugacy class. As a corollary, it follows that the CVMT holds for torsion-free CFC elements. Equivalently, Theorem 8.1 can be extended to this class of elements.
Conjecture 8.6. The cyclic version of Matsumoto’s theorem holds for a -conjugacy classes, as long as the parabolic closure of its minimal elements contains only infinite irreducible components.
Finally, it should be noted that Marquis’ aforementioned results were incorrectly stated with “cyclically reduced” instead of “torically reduced”. For example, the cyclically reduced element in from Example 6.2 is not strongly cyclically reduced as (  , Corollary C) would suggest, because
Fortunately, this flaw is easily fixable. The author defined cyclically reduced elements as we did in Definition 6.1, but then in the proofs, used the subtly stronger concept of being torically reduced.
9. Concluding Remarks
The purpose of this paper is to present a framework for studying what we call “cyclic reducibility” in Coxeter groups, and show how this relates to ordinary problems in reducibility and conjugacy. We introduced the concept of a toric heap, which is a labeled toric poset and a cyclic version of Viennot’s classic “heaps of pieces”. We also formalized concepts such as cyclic words, cyclic commutativity classes, as well as cyclically and torically reduced words and elements in Coxeter groups. The notion of a toric heap morphism allowed us to formalize concepts such as labeled toric extensions, and prove that there is a bijection between (labeled) total toric extensions of the toric heap of a word, and its cyclic commutativity classes. This is a cyclic analogue of a theorem by Stembridge about labeled linear extensions of a heap and commutativity classes . However, not all fundamental properties carried over. We saw how elements can admit long braid relations but still have a unique toric heap. This brought up a new class of elements called torically fully commutative (TFC), which generalized the notion of the cyclically fully commutative (CFC) elements. These elements led to another theorem of Stembridge that generalized a characterization of the FC elements. Classifying elements that are TFC but not CFC remains an open question (see Conjecture 7.6). Our cyclic reducibility framework casts old and new results in a more transparent light. We are currently exploring whether techniques and proofs involving cyclic reducibility and conjugacy can be simplified and streamlined using toric heaps.
Toric heaps should be of general interest outside of Coxeter groups, both as interesting mathematical objects in their own right, and as a convenient framework when labeled cyclic poset structures arise in various applications. A common theme with toric poset research has been to explore toric analogues of features of ordinary posets. Similarly, ordinary heaps have been applied in many settings, and some of these should have natural toric analogues that can be explored. We are also working on a more thorough analysis of the categories of heaps and toric heaps. Regarding applications, it is difficult to predict where and how toric heaps might arise in the future. Naturally, this should not come as a surprise; back in 1986, Viennot surely did not anticipate his new theory of heaps springing up in Coxeter groups, Lorentzian quantum gravity  , models for polymers  , modeling with Petri nets  , and discrete-event systems .
The second author was partially supported by a Simons Foundation Collaboration Grant for Mathematicians, Award #358242.
 Viennot, G.X. (1986) Heaps of Pieces, I: Basic Definitions and Combinatorial Lemmas. In: Labelle, G. and Leroux, P., Eds., Combinatoire énumérative, Springer-Verlag, Berlin, 321-350.
 Billey, S.C. and Warrington, G.S. (2001) Kazhdan-Lusztig Polynomials for 321-Hexagon-Avoiding Permutations. Journal of Algebraic Combinatorics, 13, 111-136.
 Bousquet-Mélou, M. and Viennot, X.G. (1992) Empilements de segments et q-énumération de polyominos convexes dirigés. Journal of Combinatorial Theory, Series A, 60, 196-224.
 Brak, R., Iliev, G.K., Rechnitzer, A. and Whittington, S.G. (2007) Motzkin Path Models of Long Chain Polymers in Slits. Journal of Physics A, 40, 4415.
 Su, R., Van Schuppen, J.H. and Rooda, J.E. (2012) The Synthesis of Time Optimal Supervisors by Using Heaps-of-Pieces. IEEE Transactions on Automatic Control, 57, 105-118.
 Adin, R.M., Gessel, I.M., Reiner, V. and Roichman, Y. (2019) Cyclic Quasi-Symmetric Functions. Proceedings of the 314 Conference on Formal Power Series and Algebraic Combinatorics FPSAD Article 67, 12.
 Boothby, T., Burkert, J., Eichwald, M., Ernst, D.C., Green, R.M. and Macauley, M. (2012) On the Cyclically Fully Commutative Elements of Coxeter Groups. Journal of Algebraic Combinatorics, 36, 123-148.
 Pétréolle, M. (2017) Characterization of Cyclically Fully Commutative Elements in Finite and Affine Coxeter Groups. European Journal of Combinatorics, 61, 106-132.
 Wachs, M.L. (2007) Poset Topology: Tools and Applications. In: Miller, E., Reiner, V. and Sturmfels, B., Eds., Geometric Combinatorics, IAS/Park City Mathematics Series, American Mathematical Society, Providence, 497-615.