Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification

Support and Tits reduction. Let $w\in W$. If $s_1\cdots s_k$ and $s_1^{\mathrm{\prime }}\cdots s_k^{\mathrm{\prime }}$ are reduced expressions of $w$, then by [F3] they are braid-equivalent, and a braid move replaces an alternating block in two letters by the other alternating word of the same length, so it preserves the set of letters occurring; hence the set $S(w)$ of letters of a reduced expression is independent of the chosen expression. Next, let $t_1\cdots t_r$ be a word in $S$ with value $w$ and length $r>\mathrm{\ell }(w)$; by [F2] there are indices $i<j$ with $t_1\cdots \widehat{t_i}\cdots \widehat{t_j}\cdots t_r=t_1\cdots t_r=w$, so deleting the two letters leaves the value and uses only letters already present. Iterating, the length drops by two at each step until it reaches $\mathrm{\ell }(w)$, and the resulting reduced expression of $w$ uses only letters of the original word. The values of finite words in $J$ form a subgroup: the empty word gives $1$, concatenation gives products, and reversal gives inverses because $j^{-1}=j$ for $j\in J$. This subgroup contains $J$ and lies in every subgroup containing $J$, so it equals $W_J$ by The subgroup $⟨S⟩$ generated by a subset, the cyclic subgroup $⟨g⟩$, and cyclic groups. Consequently $w\in W_J$ if and only if $S(w)\subseteq J$: if $S(w)\subseteq J$, a reduced expression of $w$ is a word in the letters of $J$, so $w\in ⟨J⟩=W_J$; conversely, if $w\in W_J$, then $w$ is a product of elements of $J$, hence the value of some word in the letters $J$, which reduces as above to a reduced expression whose letters lie in $J$, so $S(w)\subseteq J$.

Type A. Let $n\ge 2$ and let $W$ now be the group presented by the type-A matrix on $S=\{s_1,\dots ,s_{n-1}\}$; we use the library's symmetric group $S_n=\mathrm{Sym}(\{0,\dots ,n-1\})$ and the transpositions ${\tau }_i=(ii+1)$ for $0\le i\le n-2$, which are the elements written $(i+1i+2)$ in the statement under the order-preserving identification of $\{0,\dots ,n-1\}$ with $\{1,\dots ,n\}$. The relators hold in $S_n$: ${\tau }_i^2=\mathrm{id}$; ${\tau }_i{\tau }_j={\tau }_j{\tau }_i$ when $\mathrm{\mid }i-j\mathrm{\mid }>1$, because the two transpositions have disjoint supports and disjoint cycles commute by [F6]; and ${\tau }_i{\tau }_{i+1}{\tau }_i={\tau }_{i+1}{\tau }_i{\tau }_{i+1}$ by direct computation on the three symbols $i,i+1,i+2$. By the universal property in [F1] there is a homomorphism $\phi :W\to S_n$ with $\phi (s_{i+1})={\tau }_i$. It is onto by the following direct argument. If a permutation $\pi$ is not the identity, its one-line entries are not increasing (the unique increasing bijection of $\{0,\dots ,n-1\}$ fixes every entry), so some $i$ has $\pi (i)>\pi (i+1)$. Right multiplication by ${\tau }_i$ swaps these neighbouring entries and lowers $\mathrm{inv}(\pi )$ by one: the total contributions of pairs involving either position and a third position are unchanged, while the inversion $(i,i+1)$ disappears. Repeating reaches inversion number zero and hence the identity, expressing $\pi$ as a product of adjacent transpositions; this uses only [F4] and [F5]. We show $\mathrm{\mid }W\mathrm{\mid }\le n!$. Let $H:=⟨s_1,\dots ,s_{n-2}⟩\le W$ (so $H=\{1\}$ when $n=2$), and for $1\le j\le n-1$ put $r_j:=s_{n-1}{s}_{n-2}\cdots s_j$, and put $r_n:=1$. Right multiplication by a generator obeys: if $i\le j-2$ then $r_j{s}_i=s_i{r}_j$, because $s_i$ commutes with every factor of $r_j$; if $i=j-1$ then $r_j{s}_i=r_{j-1}$; if $i=j$ then $r_j{s}_i=r_{j+1}$, by $s_j^2=1$ (with $r_{n-1}{s}_{n-1}=r_n$); and if $i>j$ then $r_j{s}_i=s_{i-1}{r}_j$, because moving the final $s_i$ left past $s_{i-2},\dots ,s_j$ and using $s_i{s}_{i-1}{s}_i=s_{i-1}{s}_i{s}_{i-1}$ turns it into a leading $s_{i-1}$, which then commutes left past $s_{i+1},\dots ,s_{n-1}$; for $r_n=1$ the same rules read $r_n{s}_i=s_i{r}_n$ for $i\le n-2$ and $r_n{s}_{n-1}=r_{n-1}$. In each case $r_j{s}_i$ has the form $h{r}_k$ with $h\in H$: either $h=s_i$ with $i\le n-2$, or $h=1$, or $h=s_{i-1}$ with $i-1\le n-2$. Hence the union $T={\bigcup }_{j=1}^{n}H{r}_j$ contains $1=r_n$ and is stable under right multiplication by every generator; since every generator is its own inverse, every word in the generators lies in $T$, so $W=T$ and $\mathrm{\mid }W\mathrm{\mid }\le n\mathrm{\mid }H\mathrm{\mid }$. The relators of the type-A matrix on $n-2$ generators hold among $s_1,\dots ,s_{n-2}$ in $W$, so by [F1] there is a surjection from the corresponding presented group onto $H$; by induction on $n$, whose base $n=2$ gives $\mathrm{\mid }W\mathrm{\mid }=2$, this yields $\mathrm{\mid }H\mathrm{\mid }\le (n-1)!$ and hence $\mathrm{\mid }W\mathrm{\mid }\le n!$. On the other hand $\mathrm{\mid }{S}_n\mathrm{\mid }=n!$, since a bijection of the $n$-element set $\{0,\dots ,n-1\}$ is determined by choosing the image of $0$ in $n$ ways, then the image of $1$ in $n-1$ ways, and so on. Therefore the surjection $\phi$ between the finite groups $W$ and $S_n$ is a bijection, hence an isomorphism. It remains to identify $\mathrm{\ell }$ with the inversion number. Right multiplication by ${\tau }_i$ interchanges the entries at positions $i$ and $i+1$ in the one-line notation by [F4], so it exchanges the inversion statuses of the pairs $(p,i),(p,i+1)$ for $p<i$ and of the pairs $(i,q),(i+1,q)$ for $q>i+1$, while the pair $(i,i+1)$ becomes an inversion exactly when it was not one; hence $\mathrm{inv}(\sigma {\tau }_i)=\mathrm{inv}(\sigma )\pm 1$, with $\mathrm{inv}(\sigma {\tau }_i)=\mathrm{inv}(\sigma )-1$ exactly when $\sigma (i)>\sigma (i+1)$ by [F5]. Therefore every word of length $k$ in the generators ${\tau }_i$ representing $\sigma$ has $\mathrm{inv}(\sigma )\le k$ (each letter changes the inversion number by one), so $\mathrm{inv}(\sigma )\le {\mathrm{\ell }}_A(\sigma )$ for the length function ${\mathrm{\ell }}_A$ of $S_n$ with respect to the generating set $\{{\tau }_i\}$; and if $\mathrm{inv}(\sigma )>0$ then some $i$ has $\sigma (i)>\sigma (i+1)$ (otherwise $\sigma$ would be increasing, hence the identity), so ${\mathrm{\ell }}_A(\sigma )\le {\mathrm{\ell }}_A(\sigma {\tau }_i)+1=\mathrm{inv}(\sigma {\tau }_i)+1=\mathrm{inv}(\sigma )$ by induction on the inversion number, giving ${\mathrm{\ell }}_A=\mathrm{inv}$. Finally $\mathrm{\ell }(w)={\mathrm{\ell }}_A(\phi (w))$ for all $w\in W$: a word of length $\mathrm{\ell }(w)$ in the $s_i$ representing $w$ maps to a word of the same length in the ${\tau }_i$ representing $\phi (w)$, so ${\mathrm{\ell }}_A(\phi (w))\le \mathrm{\ell }(w)$; conversely a word ${\tau }_{i_1}\cdots {\tau }_{i_k}$ of length $k={\mathrm{\ell }}_A(\phi (w))$ for $\phi (w)$ lifts to the word $s_{i_1+1}\cdots s_{i_k+1}$, which maps to $\phi (w)$, so it represents $w$ by injectivity of $\phi$ and $\mathrm{\ell }(w)\le k$. Hence $\mathrm{\ell }(w)=\mathrm{inv}(\phi (w))$, and by [F2] a word in the $s_i$ is reduced exactly when its length equals the inversion number of its value.

The intrinsic parabolic presentation. Let $W_J^{\ast }$ be the group presented by $(J,m{\mathrm{\mid }}_J)$ as in [F1]. The map $f:J\to W_J\le W$, $j\mapsto j$, satisfies the relator conditions in $W$, because every relator of the restricted matrix is a relator of $(S,m)$; so [F1] gives a homomorphism $f:W_J^{\ast }\to W_J$, which is onto because the elements of $J$ generate $W_J$. For injectivity define $f^{\mathrm{\prime }}:W_J\to W_J^{\ast }$ by choosing, for $w\in W_J$, a reduced expression $w=j_1\cdots j_q$ in $W$ and setting $f^{\mathrm{\prime }}(w):=j_1\cdots j_q$ (product in $W_J^{\ast }$); by step 1.1 all letters $j_l$ lie in $J$. This is well defined: another reduced expression $j_1^{\mathrm{\prime }}\cdots j_q^{\mathrm{\prime }}$ of $w$ is braid-equivalent to it by [F3], and every braid move involved replaces an alternating block in two letters of $J$ by the other alternating word, which is a defining relation of $W_J^{\ast }$, so the two products agree. To see that $f^{\mathrm{\prime }}$ is a homomorphism it suffices to show $f^{\mathrm{\prime }}(jw)=j{f}^{\mathrm{\prime }}(w)$ for $j\in J$ and $w\in W_J$. If $\mathrm{\ell }(jw)=\mathrm{\ell }(w)+1$, then prepending $j$ to a reduced expression of $w$ gives a reduced expression of $jw$ with letters in $J$, and the claim is immediate. If $\mathrm{\ell }(jw)=\mathrm{\ell }(w)-1$, then [F2] applied to a reduced expression $w=j_1\cdots j_q$ gives $jw=j_1\cdots \widehat{j_i}\cdots j_q$ for some $i$. The deleted word is reduced of length $q-1$, and prepending $j$ to it gives another reduced expression of $w$ of length $q$, with every letter in $J$. By [F3] these two reduced expressions of $w$ are braid-equivalent using only letters in $J$, so their products agree in $W_J^{\ast }$: $j_1\cdots j_q=j{j}_1\cdots \widehat{j_i}\cdots j_q$. Multiplying this equality by $j$ in $W_J^{\ast }$ gives $j{f}^{\mathrm{\prime }}(w)=j_1\cdots \widehat{j_i}\cdots j_q=f^{\mathrm{\prime }}(jw)$. Iterating $f^{\mathrm{\prime }}(jw)=j{f}^{\mathrm{\prime }}(w)$ along a word for any $u\in W_J$, and using $f^{\mathrm{\prime }}(1)=1$, gives $f^{\mathrm{\prime }}(uw)=f^{\mathrm{\prime }}(u)f^{\mathrm{\prime }}(w)$, so $f^{\mathrm{\prime }}$ is a homomorphism. By construction $f{f}^{\mathrm{\prime }}(w)=w$ for all $w\in W_J$, and $f^{\mathrm{\prime }}f$ fixes each generator of $W_J^{\ast }$ because $f^{\mathrm{\prime }}(j)=j$ for $j\in J$; hence $f^{\mathrm{\prime }}f={\mathrm{i}\mathrm{d}}_{W_J^{\ast }}$. Thus $f$ and $f^{\mathrm{\prime }}$ are inverse isomorphisms, and $(W_J,J)$ is a Coxeter system. If $w\in W_J$ and $j_1\cdots j_q$ is a reduced expression of $w$ in $W$, then all $j_l\in J$ by step 1.1, so the same word of length $q$ is a word in the generators $J$ of $W_J^{\ast }$, giving ${\mathrm{\ell }}_J(w)\le \mathrm{\ell }(w)$; conversely a word in the letters $J$ representing $w$ is a word in $S$ representing $w$, so $\mathrm{\ell }(w)\le {\mathrm{\ell }}_J(w)$; hence ${\mathrm{\ell }}_J=\mathrm{\ell }$ on $W_J$. If $s\in S\cap W_J$, then $S(s)=\{s\}\subseteq J$ by step 1.1, so $s\in J$ and $W_J\cap S=J$.

Minimal coset representatives. Fix $a\in W$. The set $\{\mathrm{\ell }(x):x\in W_{J}a\}$ is a nonempty subset of $\mathbb{N}$ and so has a least element by [F8]; choose $d\in W_{J}a$ of minimal length. For $s\in J$ one has $sd\in W_{J}a$, so $\mathrm{\ell }(sd)\ge \mathrm{\ell }(d)$; by [F2] $\mathrm{\ell }(sd)=\mathrm{\ell }(d)\pm 1$, and therefore $\mathrm{\ell }(sd)=\mathrm{\ell }(d)+1>\mathrm{\ell }(d)$. Now let $u\in W_J$ with a reduced expression $u=u_1\cdots u_p$ and let $d=d_1\cdots d_q$ be reduced, so $q=\mathrm{\ell }(d)$; by step 1.1 all $u_l$ lie in $J$. Applying the Tits reduction of step 1.1 to the concatenated word $u_1\cdots u_p{d}_1\cdots d_q$ produces a reduced expression of $ud$ that is a subsequence of it, hence splits as $u^{\mathrm{\prime }}{d}^{\mathrm{\prime }}$ with $u^{\mathrm{\prime }}$ a subsequence of $u_1\cdots u_p$ and $d^{\mathrm{\prime }}$ a subsequence of $d_1\cdots d_q$; write $u^{\mathrm{\prime }},d^{\mathrm{\prime }}$ also for their values. If $d^{\mathrm{\prime }}$ is not the full word $d_1\cdots d_q$, then $d^{\mathrm{\prime }}=(u^{\mathrm{\prime }}{)}^{-1}ud\in W_{J}d=W_{J}a$, while $d^{\mathrm{\prime }}$ has fewer than $q$ letters, so $\mathrm{\ell }(d^{\mathrm{\prime }})<q=\mathrm{\ell }(d)$, contradicting the minimality of $d$. Hence $d^{\mathrm{\prime }}$ is the full $d$-word, so $u^{\mathrm{\prime }}d=ud$ and $u^{\mathrm{\prime }}=u$; since $u^{\mathrm{\prime }}$ is a subsequence of the reduced word $u_1\cdots u_p$ of length $p=\mathrm{\ell }(u)$ and represents $u$, it must use all $p$ letters, so the concatenation is reduced and $\mathrm{\ell }(ud)=p+q=\mathrm{\ell }(u)+\mathrm{\ell }(d)$. If $d^{\mathrm{\prime }\mathrm{\prime }}\in W_{J}a$ also has minimal length, write $d^{\mathrm{\prime }\mathrm{\prime }}=ud$ with $u\in W_J$; then $\mathrm{\ell }(d^{\mathrm{\prime }\mathrm{\prime }})=\mathrm{\ell }(u)+\mathrm{\ell }(d)$ with $\mathrm{\ell }(d^{\mathrm{\prime }\mathrm{\prime }})=\mathrm{\ell }(d)$, so $\mathrm{\ell }(u)=0$, $u=1$ and $d^{\mathrm{\prime }\mathrm{\prime }}=d$; this gives uniqueness. Conversely, let $d$ satisfy $\mathrm{\ell }(sd)>\mathrm{\ell }(d)$ for all $s\in J$ and write $d=u{d}_0$ with $d_0$ the minimal representative of $W_{J}d$; additivity gives $\mathrm{\ell }(d)=\mathrm{\ell }(u)+\mathrm{\ell }(d_0)$, and if $u\mathrm{\ne }1$ and $u=s_1\cdots s_p$ is a reduced expression with $p\ge 1$, then $\mathrm{\ell }(s_{1}d)=\mathrm{\ell }(s_2\cdots s_p{d}_0)\le (p-1)+\mathrm{\ell }(d_0)<\mathrm{\ell }(d)$, contradicting the hypothesis; hence $u=1$ and $d=d_0$ is the minimal representative. The factorization $w=ud$ of an arbitrary $w\in W$ is now obtained by taking $d$ minimal in $W_{J}w$ and $u:=w{d}^{-1}\in W_J$, and its uniqueness follows from the uniqueness of $d$. For left cosets, note that $\mathrm{\ell }(u^{-1})=\mathrm{\ell }(u)$ for every $u$: reversing a reduced word for $u$ gives a word of the same length for $u^{-1}$, so $\mathrm{\ell }(u^{-1})\le \mathrm{\ell }(u)$, and applying this to $u^{-1}$ gives equality. Inversion is an anti-automorphism interchanging right and left cosets and fixing lengths, so applying the right-coset statement to inverses gives unique minimal elements of the left cosets $a{W}_J$, characterized by $\mathrm{\ell }(ds)>\mathrm{\ell }(d)$ for $s\in J$ and satisfying $\mathrm{\ell }(du)=\mathrm{\ell }(d)+\mathrm{\ell }(u)$.