Heaps, Commutation Classes, and Fully Commutative Elements — Examples

The heap relations are computed pair by pair from [F1]: positions $1,2$ carry the distinct commuting letters $s_1,s_3$ with $m(s_1,s_3)=2$, so there is no relation between them; position $3$ is above position $1$ because $1<3$ and $m(s_1,s_2)=3\ge 3$; and position $3$ is above position $2$ because $2<3$ and $m(s_3,s_2)=m(s_2,s_3)=3$. These are therefore all generating relations, and the transitive closure adds nothing, so $P$ is the three-element poset with exactly $1\prec 3$ and $2\prec 3$. By [F5] its covering pairs are $1⋖3$ and $2⋖3$: the only elements are $1,2,3$, and no $z$ satisfies $1\prec z\prec 3$ or $2\prec z\prec 3$, since $1$ and $2$ are incomparable. The covering labels are $(s_1,s_2)$ and $(s_3,s_2)$.

The order ideals are the subsets $I\subseteq \{1,2,3\}$ that contain $1$ and $2$ whenever they contain $3$, that is, $\mathrm{\varnothing },\{1\},\{2\},\{1,2\},\{1,2,3\}$: downward closure of a subset of the three-element poset is a condition only on the predecessors of $3$. These five sets are exactly $J(P)$, and by [F6] they form a finite distributive lattice under inclusion, with meet intersection and join union.

The criterion of [F3] applies: every chain of $P$ has at most two elements, since the only relations are $1\prec 3$ and $2\prec 3$, so there is no convex chain of any length $m\ge 3$, and in particular none of length $m(s_1,s_2)=m(s_2,s_3)=3$; hence condition (a) of Fully commutative elements: the braid-factor criterion and the forbidden-chain heap criterion (2) holds. The covering pairs $1⋖3$ and $2⋖3$ have labels $(s_1,s_2)$ and $(s_3,s_2)$, and $s_1,s_2,s_3$ are pairwise distinct, so condition (b) holds. By [F3] the word $(s_1,s_3,s_2)$ is reduced, $w$ is fully commutative and $P=P_w$; since a reduced word of $w$ has length $\mathrm{\ell }(w)$, this gives $\mathrm{\ell }(w)=3$.

A listing of $\{1,2,3\}$ is a linear extension of $P$ exactly when $3$ is last, because both relations point to $3$ and $1,2$ are incomparable; the two linear extensions are therefore $(1,2,3)$ and $(2,1,3)$, with labeled words $s_1{s}_3{s}_2$ and $s_3{s}_1{s}_2$. By [F4], $L(P,s)=C(s)$, and by 2.1 the word is reduced with $w$ fully commutative, so $C(s)=\mathcal{R}(w)$; hence the reduced words of $w$ are exactly these two words, which differ by interchanging the adjacent commuting letters $s_1,s_3$.

The heap relations are computed pair by pair from [F1]. Positions $1,2$ carry the noncommuting letters $s_1,s_2$ with $m(s_1,s_2)=3$, so $1\prec 2$; positions $2,3$ carry the noncommuting letters $s_2,s_1$, so $2\prec 3$; and positions $1,3$ carry the equal label $s_1$, so $1\prec 3$ as well. Hence the generating relations are contained in the chain $1\prec 2\prec 3$, and the transitive closure of all three relations is exactly that chain; its labels are $s_1,s_2,s_1$. By [F5] the covering pairs are $1⋖2$ and $2⋖3$, since no element lies strictly between consecutive positions of the chain, and their labels $(s_1,s_2)$ and $(s_2,s_1)$ are distinct.

Reducedness and the commutation classes. By F3 the alternating words of length $3=m(s_1,s_2)$ in $⟨s_1,s_2⟩$ are reduced in $W$, so $s_1{s}_2{s}_1$ and $s_2{s}_1{s}_2$ are reduced of length $3=\mathrm{\ell }(w_0)$, and by [F2] they represent the same element $w_0$. The only braid moves between words in $\{s_1,s_2\}$ replace an alternating subword of length $m(s_1,s_2)=3$ by the other alternating word, that is, they exchange the two displayed words; by F3 every reduced word of $w_0$ is braid-equivalent to $s_1{s}_2{s}_1$, hence $\mathcal{R}(w_0)=\{s_1{s}_2{s}_1,s_2{s}_1{s}_2\}$. Neither word contains two adjacent commuting letters, since every adjacent pair is $\{s_1,s_2\}$ with $m(s_1,s_2)=3\mathrm{\ne }2$; hence no commutation applies and $C(s_1{s}_2{s}_1)=\{s_1{s}_2{s}_1\}$, $C(s_2{s}_1{s}_2)=\{s_2{s}_1{s}_2\}$ are two distinct classes whose union is $\mathcal{R}(w_0)$.

The order ideals are the prefixes of the chain $1\prec 2\prec 3$: a subset $I$ is downward closed exactly when $2\in I\Rightarrow 1\in I$ and $3\in I\Rightarrow 2\in I$, which gives $\mathrm{\varnothing }$, $\{1\}$, $\{1,2\}$, $\{1,2,3\}$ and no further subset.

The chain $(1,2,3)$ is convex in $P$: it exhausts the three elements of $P$, so there is no element outside it lying between two of its members. It has length $3=m(s_1,s_2)$ and its labels $s_1,s_2,s_1$ alternate between the distinct letters $s_1,s_2$, so it is a convex alternating chain of the forbidden length and condition (a) of [F4] clause (2) fails. Its covering pairs are $1⋖2$ and $2⋖3$ by 1.1, with labels $(s_1,s_2)$ and $(s_2,s_1)$ distinct, so condition (b) holds.

Since $s_1{s}_2{s}_1$ is a reduced word of $w_0$ by 1.2 and contains the contiguous factor $⟨s_1,s_2{⟩}_3$ (its three letters), [F4] clause (1) shows that $w_0$ is not fully commutative. Moreover $P$ is not the heap of any fully commutative element: if $P\cong P_{s^{\mathrm{\prime }}}$ for some $s^{\mathrm{\prime }}\in \mathcal{R}(w^{\mathrm{\prime }})$ with $w^{\mathrm{\prime }}$ fully commutative, then by [F4] clause (2) applied to the reduced word $s^{\mathrm{\prime }}$, the heap $P_{s^{\mathrm{\prime }}}$ contains no convex alternating chain of length $m(u,v)$ with $3\le m(u,v)<\mathrm{\infty }$, while $P$ contains the convex alternating chain exhibited in 2.1 and convexity, length and labels are preserved by the labeled isomorphism, a contradiction.

The data for $w$. The word $(s_1,s_3,s_2)$ has heap $P_w$ on positions $1,2,3$: positions $1,3$ carry $s_1,s_2$ with $m(s_1,s_2)=3$ and positions $2,3$ carry $s_3,s_2$ with $m(s_3,s_2)=3$, so $1\prec 3$ and $2\prec 3$; positions $1,2$ carry the distinct commuting letters $s_1,s_3$ with $m(s_1,s_3)=2$, so there is no generating relation between them; because positions $1,2$ are consecutive in the original word and every generating edge increases the position, no intermediate position can lie on a path between them, so no transitive path relates them. Both heap-criterion conditions hold: every chain of $P_w$ has at most two elements, so there is no convex alternating chain of length $3$, and the covering pairs $1⋖3$, $2⋖3$ have distinct labels $(s_1,s_2)$ and $(s_3,s_2)$; by [F3] the word is reduced, $w$ is fully commutative and $P_w$ is the heap of $w$, with $\mathrm{\ell }(w)=3$. The linear extensions of $P_w$ are $(1,2,3)$ and $(2,1,3)$, since both relations force position $3$ last; their labeled words are $s_1{s}_3{s}_2$ and $s_3{s}_1{s}_2$, so $C((s_1,s_3,s_2))=\mathcal{R}(w)=\{s_1{s}_3{s}_2,s_3{s}_1{s}_2\}$ by [F2] and [F3]. The order ideals are the subsets $I$ with $3\in I\Rightarrow 1,2\in I$, namely $\mathrm{\varnothing },\{1\},\{2\},\{1,2\},\{1,2,3\}$.

The data for $u$. The word $(s_1,s_3)$ has heap $P_u$ on positions $1,2$ with labels $s_1,s_3$: since $m(s_1,s_3)=2$ and the labels are distinct, no generating relation links the two positions, so $P_u$ is the two-element antichain and it has no covering pairs. Conditions (a) and (b) of [F3] hold vacuously (there is no chain of length $3$, and no covering pair at all), so the word is reduced, $u$ is fully commutative with heap $P_u$ and $\mathrm{\ell }(u)=2$. By [F2] its reduced words are the words read from the two linear extensions $(1,2)$, $(2,1)$ of $P_u$, namely $\mathcal{R}(u)=C((s_1,s_3))=\{s_1{s}_3,s_3{s}_1\}$. The order ideals of the antichain $P_u$ are all four subsets of $\{1,2\}$.

The interval $[1,u{]}_R$. By [F4] the map $x\mapsto I(x)$ is an order isomorphism $[1,u{]}_R\to J(P_u)$, so $[1,u{]}_R$ has exactly $\mathrm{\mid }J(P_u)\mathrm{\mid }=4$ elements and is a finite distributive lattice with meet and join given by intersection and union of ideals. By [F6] the products of the prefixes of the reduced words $s_1{s}_3$ and $s_3{s}_1$, namely $1,s_1,u$ and $1,s_3,u$, lie in $[1,u{]}_R$; they are pairwise distinct because their lengths are $0,1,1,2$ and $s_1\mathrm{\ne }{s}_3$ by [F5]; hence they exhaust the four-element interval and $[1,u{]}_R=\{1,s_1,s_3,u\}$. For the ideal map: $\mathrm{\ell }(s_1)=\mathrm{\ell }(s_3)=1$ and $\mathrm{\ell }(u)=2$ by [F5] and 1.2, so $\mathrm{\mid }I(s_1)\mathrm{\mid }=\mathrm{\mid }I(s_3)\mathrm{\mid }=1$ and $\mathrm{\mid }I(u)\mathrm{\mid }=2$; computing with the reduced words $(s_1)$, $(s_3)$ and $(s_1,s_3)$ gives $I(s_1)=\{1\}$, $I(s_3)=\{2\}$ and $I(u)=\{1,2\}$, while $I(1)=\mathrm{\varnothing }$ by [F4]. Hence $s_1\wedge s_3$ is the element with ideal $\{1\}\cap \{2\}=\mathrm{\varnothing }$, namely $1$, and $s_1\vee s_3$ is the element with ideal $\{1\}\cup \{2\}=\{1,2\}$, namely $u$.

The interval $[1,w{]}_R$. By [F4] the map $x\mapsto I(x)$ is a bijection $[1,w{]}_R\to J(P_w)$, so $[1,w{]}_R$ has exactly five elements by 1.1, and it is a finite distributive lattice with meets and joins given by intersection and union of ideals. By [F6], the prefixes of the two reduced words $s_1{s}_3{s}_2$ and $s_3{s}_1{s}_2$ of 1.1 show that all five displayed elements lie in $[1,w{]}_R$. Their ideals are computed as follows: $I(1)=\mathrm{\varnothing }$ and $I(w)=P_w$ by [F4]; and, using the chains $C_{s_1}=\{1\}$, $C_{s_3}=\{2\}$, $C_{s_2}=\{3\}$ of $P_w$, the reduced words $(s_1)$ and $(s_3)$ give $I(s_1)=\{1\}$ and $I(s_3)=\{2\}$, while the reduced word $(s_1,s_3)$ of 1.2 gives $I(s_1{s}_3)=\{1,2\}$; its prefixes are those of the reduced word $s_1{s}_3{s}_2$ of $w$, so that $s_1{s}_3{\le }_{R}w$ by [F6]. Their images $\mathrm{\varnothing },\{1\},\{2\},\{1,2\},\{1,2,3\}$ are the five distinct elements of $J(P_w)$, so $[1,w{]}_R=\{1,s_1,s_3,s_1{s}_3,w\}$ and each displayed element is the product of the ideal that is its image. In particular $s_1\wedge s_3$ has ideal $\{1\}\cap \{2\}=\mathrm{\varnothing }$, so $s_1\wedge s_3=1$; $s_1\vee s_3$ has ideal $\{1\}\cup \{2\}=\{1,2\}$, so $s_1\vee s_3=s_1{s}_3$; and $s_1{s}_3\vee s_1$ has ideal $\{1,2\}\cup \{1\}=\{1,2\}$, so $s_1{s}_3\vee s_1=s_1{s}_3$.

Both intervals are finite distributive lattices by 2.1 and 2.2, illustrating F4-(3). Their heaps are the two-element antichain of 1.2 and the V-shaped poset of 1.1; the first is not a chain because its two elements are incomparable, and the second is not a chain because $1$ and $2$ are incomparable in $P_w$. So the distributivity exhibited here is not the chain case.

The group and its elements. Since $S=\{s_1,s_2\}$, the subgroup $⟨s_1,s_2⟩$ is all of $W$, so by [F4] $W$ is dihedral of order $2\cdot 3=6$; its elements are the six distinct elements $(s_1{s}_2{)}^k$ and $(s_1{s}_2{)}^k{s}_1$ for $k=0,1,2$. With $(s_1{s}_2{)}^3=1$ from the relator of [F1] these are $1$, $s_1{s}_2$, $(s_1{s}_2{)}^2=s_2{s}_1$, $s_1$, $(s_1{s}_2)s_1=s_1{s}_2{s}_1=w_0$ and $(s_1{s}_2{)}^2{s}_1=s_2$; hence $W=\{1,s_1,s_2,s_1{s}_2,s_2{s}_1,w_0\}$ and, since the displayed words are the reduced expressions by [F4], the lengths are $0,1,1,2,2,3$ respectively, in particular $\mathrm{\ell }(w_0)=3$. The reduced words of $w_0$ are exactly $s_1{s}_2{s}_1$ and $s_2{s}_1{s}_2$: both are reduced of length $3$ and represent $w_0$ by the braid relation of [F1], and by F4 every reduced word of $w_0$ is braid-equivalent to $s_1{s}_2{s}_1$, while the only braid move applicable to a length-three word in the two letters replaces the whole alternating word by the other.

The interval and the covers. By the prefix property F2, the elements of $[1,w_0{]}_R$ are the products of the prefixes of the reduced words $s_1{s}_2{s}_1$ and $s_2{s}_1{s}_2$ of $w_0$ established in step 1.1, namely $1,s_1,s_1{s}_2,w_0$ and $1,s_2,s_2{s}_1,w_0$; these are all six elements of $W$ by 1.1, so $[1,w_0{]}_R=W$. By [F3] every cover in ${\le }_R$ is of the form $v=us$ with $s\in S$ and $\mathrm{\ell }(v)=\mathrm{\ell }(u)+1$; running over the six elements $u$ and the two generators and using the length table of 1.1, the products with length increase one are exactly $1\cdot s_1=s_1$, $1\cdot s_2=s_2$, $s_1\cdot s_2=s_1{s}_2$, $s_2\cdot s_1=s_2{s}_1$, $s_1{s}_2\cdot s_1=w_0$ and $s_2{s}_1\cdot s_2=w_0$, while $s_1{s}_2\cdot s_2=s_1$, $s_2{s}_1\cdot s_1=s_2$ and the products $w_{0}s$ (of length $2$) do not raise the length. Hence these six pairs are exactly the covers. The elements $s_1{s}_2$ and $s_2{s}_1$ are distinct of equal length $2$, so neither is below the other by the strict length increase in F2, and they are incomparable; likewise $s_2{s}_1\mathrm{̸}{\le }_R{s}_1$ and $s_1{s}_2\mathrm{̸}{\le }_R{s}_2$ by length, while $s_1{\le }_R{s}_2{s}_1$ would force $\mathrm{\ell }(s_2{s}_1)=\mathrm{\ell }(s_1)+\mathrm{\ell }(s_1^{-1}{s}_2{s}_1)=1+\mathrm{\ell }(w_0)=4$ by F2, which is false; so $s_1,s_2{s}_1$ are incomparable, and symmetrically $s_2,s_1{s}_2$ are incomparable. Consequently the subposet $\{1,s_1,s_1{s}_2,s_2{s}_1,w_0\}$ has the chains $1<s_1<s_1{s}_2<w_0$ and $1<s_2{s}_1<w_0$ together with the incomparabilities just listed, that is, it is the pentagon.