Matsumoto's theorem: braid connectivity of reduced expressions, with singleton detection in dihedral subgroups

The dihedral subgroup and the singleton claim. Fix any distinct $s,t\in S$, put $m:=m(s,t)$ and $r:=st$. By [F3], $r$ has order exactly $m$ when $m<\mathrm{\infty }$ and infinite order when $m=\mathrm{\infty }$, and $srs=s(st)s=(ss)(ts)=ts=r^{-1}$; hence $s{r}^k=r^{-k}s$ for every $k$ by induction on $k$. It follows that $D:=⟨s,t⟩$ is exactly the set $D_0:=\{r^k:k\in \mathbb{Z}\}\cup \{r^{k}s:k\in \mathbb{Z}\}$: indeed $D_0$ contains $s=r^{0}s$ and $t=r^{-1}s$ (as $r^{-1}s=(ts)s=t$), and $D_0$ is closed under inverses (the inverse of $r^k$ is $r^{-k}$ and $(r^{k}s{)}^2=1$) and under multiplication, since $r^a\cdot r^b=r^{a+b}$, $r^a\cdot r^{b}s=r^{a+b}s$, $r^{a}s\cdot r^b=r^a(s{r}^b)=r^a{r}^{-b}s=r^{a-b}s$ and $r^{a}s\cdot r^{b}s=r^a(s{r}^b)s=r^a{r}^{-b}ss=r^{a-b}$; so $D_0$ is a subgroup containing $s$ and $t$, while every product of copies of $s,t$ lies in $D_0$ by this closure, whence $D=D_0$. The elements $r^k$ and $r^{k}s$ with $0\le k<m$ (all $k\in \mathbb{Z}$ when $m=\mathrm{\infty }$) are pairwise distinct: $r^k=r^l$ with $0\le k<l<m$ gives $r^{l-k}=1$, impossible by minimality of the order $m$, while for $m=\mathrm{\infty }$ the powers $r^k$ with $k\in \mathbb{Z}$ are distinct because $r$ has infinite order; and $r^k=r^{l}s$ gives $r^{k-l}=s$, so $s\in ⟨r⟩$, which cannot happen because $s\in ⟨r⟩$ would make $s$ commute with $r$, giving $t=sr=rs=sts$, hence $st=ts$ and $r=r^{-1}$; then $r^2=1$, so the order of $r$ divides $2$, an impossibility unless $m=2$, and in the case $m=2$ one has $⟨r⟩=\{1,r\}$ with $s\mathrm{\ne }1$ and $s\mathrm{\ne }r=st$ (the latter would give $t=1$). Hence $D$ has exactly $2m$ elements and is dihedral when $m<\mathrm{\infty }$, and is infinite dihedral when $m=\mathrm{\infty }$. Next, $P:=\mathrm{span}({\alpha }_s,{\alpha }_t)$ is preserved by ${\sigma }_s$ and ${\sigma }_t$, and ${\sigma }_s(v)-v\in P$ and ${\sigma }_t(v)-v\in P$ for every $v\in E$: on the basis, ${\sigma }_s({\alpha }_s)-{\alpha }_s=-2{\alpha }_s$, ${\sigma }_s({\alpha }_t)-{\alpha }_t=c_{st}{\alpha }_s$ and ${\sigma }_s({\alpha }_u)-{\alpha }_u=c_{su}{\alpha }_s$ for $u\mathrm{\notin }\{s,t\}$, and symmetrically for ${\sigma }_t$. So for every product $g$ of copies of ${\sigma }_s,{\sigma }_t$ one has $g(v)-v\in P$ for all $v$ by induction on the number of factors, and therefore every element of $D=⟨s,t⟩$ acts as the identity on $E\mathrm{/}P$. If $u\in S\setminus \{s,t\}$, then ${\alpha }_u\mathrm{\notin }P$ because the basis is linearly independent, while ${\sigma }_u({\alpha }_u)=-{\alpha }_u$, so ${\sigma }_u({\alpha }_u)-{\alpha }_u=-2{\alpha }_u\mathrm{\notin }P$. Thus ${\sigma }_u$ fails the congruence ${\sigma }_u(v)-v\in P$ satisfied by every element of $D$, without requiring ${\sigma }_u$ to preserve $P$ or induce a quotient map; since $\sigma$ is a homomorphism, $u\mathrm{\notin }D$. Hence $S\cap D=\{s,t\}$. Finally, every element of $D$ has a reduced expression with letters in $\{s,t\}$: for $0\le k<m$ the element $r^k$ equals both $(st{)}^k$ and $(ts{)}^{m-k}=r^{k-m}$, alternating words of lengths $2k$ and $2(m-k)$ whose minimum is at most $m$, and the element $r^{k}s$ equals both $(st{)}^{k}s$ and $(ts{)}^{m-k-1}t$ (for $k=0$ the first is the single letter $s$), alternating words of lengths $2k+1$ and $2(m-k)-1$ whose minimum is at most $m$; an alternating word of length at most $m$ is reduced in $W$ by [F3], so the shorter of the two is a reduced expression of the element in the letters $\{s,t\}$. When $m=\mathrm{\infty }$ every alternating word is reduced by [F3], and $r^k$ with $k<0$ is written as $(ts{)}^{-k}$ and $r^{k}s$ with $k<0$ as $(ts{)}^{-k-1}t$.

Braid moves preserve the value. Fix distinct $s,t\in S$ with $m=m(s,t)<\mathrm{\infty }$ and let $L_m$ and $L_m^{\mathrm{\prime }}$ be the two alternating words of length $m$ in $\{s,t\}$, beginning with $s$ and with $t$. With $r:=st$ of order $m$ by [F3], one has $L_m=(st{)}^{m\mathrm{/}2}=r^{m\mathrm{/}2}$ and $L_m^{\mathrm{\prime }}=(ts{)}^{m\mathrm{/}2}=r^{-m\mathrm{/}2}$ when $m$ is even, so their values coincide; and $L_m=(st{)}^{(m-1)\mathrm{/}2}s=r^{(m-1)\mathrm{/}2}s$ while $L_m^{\mathrm{\prime }}=t(st{)}^{(m-1)\mathrm{/}2}=(ts{)}^{(m-1)\mathrm{/}2}t=r^{-(m-1)\mathrm{/}2}t=r^{-(m-1)\mathrm{/}2}{r}^{-1}s=r^{-(m+1)\mathrm{/}2}s=r^{(m-1)\mathrm{/}2}s$ when $m$ is odd, using $ts=r^{-1}$, $t=r^{-1}s$ and $r^m=1$. Hence replacing an alternating subword of length $m$ by the other alternating word of the same length leaves the value in $W$ unchanged, and so does a finite sequence of such replacements.

The reduction step. Let $q\ge 2$ and let $\mathbf{a}=(a_1,\dots ,a_q)$ and $\mathbf{b}=(b_1,\dots ,b_q)$ be reduced words for the same element $w\in W$, with $a_1\mathrm{\ne }{b}_1$; write $a:=a_1$, $b:=b_1$, and assume as induction hypothesis that part (1) holds for all elements of length at most $q-1$. Since $\mathbf{b}$ is reduced, $bw=b_2\cdots b_q$ has length $q-1$, so the exchange condition of [F4] applied to the reduced word $\mathbf{a}$ and the letter $b$ gives $bw=a_1\cdots \widehat{a_i}\cdots a_q$ for some $i\in \{1,\dots ,q\}$, that is $w=b{a}_1\cdots \widehat{a_i}\cdots a_q$. Multiplying the equality $bw=a_1\cdots \widehat{a_i}\cdots a_q$ on the right by $a_q{a}_{q-1}\cdots a_{i+1}$ and then by $a_i$ shows that it is equivalent to $b{a}_1\cdots a_{i-1}=a_1\cdots a_i$; in particular $i\mathrm{\ne }1$, since $i=1$ would give $b=a_1=a$, contrary to $a\mathrm{\ne }b$. Hence $i\ge 2$, and the word $(b,a_1,\dots ,\widehat{a_i},\dots ,a_q)$ is a reduced expression of $w$. Its tail $(a_1,\dots ,\widehat{a_i},\dots ,a_q)$ and the suffix $(b_2,\dots ,b_q)$ are reduced expressions of the same element $bw$ of length $q-1$, so by the induction hypothesis they are braid-equivalent, and prepending the letter $b$ to both words gives the braid-equivalence of $(b,a_1,\dots ,\widehat{a_i},\dots ,a_q)$ with $(b,b_2,\dots ,b_q)=\mathbf{b}$. If $i<q$, multiplying the equality $b{a}_1\cdots a_{i-1}=a_1\cdots a_i$ on the right by $a_{i+1}\cdots a_{q-1}$ shows that the words $(b,a_1,\dots ,\widehat{a_i},\dots ,a_{q-1})$ and $(a_1,\dots ,a_{q-1})$ are reduced expressions of the same element $a_1\cdots a_{q-1}$ of length $q-1$, so by the induction hypothesis they are braid-equivalent, and appending the letter $a_q$ to both gives the braid-equivalence of $(b,a_1,\dots ,\widehat{a_i},\dots ,a_q)$ with $\mathbf{a}$; combining the two braid-equivalences, $\mathbf{a}$ is braid-equivalent to $\mathbf{b}$. Thus either $\mathbf{a}$ and $\mathbf{b}$ are braid-equivalent, or $i=q$, in which case $w=b{a}_1\cdots a_{q-1}$ and $(b,a_1,\dots ,a_{q-1})$ is braid-equivalent to $\mathbf{b}$.

The iteration. Keep the setup of step 1.3 and assume now that the two words are not braid-equivalent. For $j\in \{1,\dots ,q\}$ let $\sigma (j)$ be the $q$-letter word consisting of the alternating word of length $q-j+1$ ending in $a$ followed by the letters $a_2,a_3,\dots ,a_j$. Thus $\sigma (q)=(a_1,\dots ,a_q)=\mathbf{a}$ and $\sigma (q-1)=(b,a,a_2,\dots ,a_{q-1})$; let $C_j$ denote the braid class of $\sigma (j)$ when $\sigma (j)$ is reduced. I claim that for every $p\in \{0,\dots ,q-2\}$: either $\mathbf{a}$ and $\mathbf{b}$ are braid-equivalent, or $\sigma (j)$ is reduced, represents $w$, and $C_j$ is the class of $\mathbf{a}$ when $j-q$ is even and the class of $\mathbf{b}$ when $j-q$ is odd, for every $j\in \{q-p-1,\dots ,q\}$. For $p=0$ this is step 1.3: either the words are braid-equivalent, or $w=b{a}_1\cdots a_{q-1}$ and the word $\sigma (q-1)=(b,a_1,\dots ,a_{q-1})$ is braid-equivalent to $\mathbf{b}$, while $\sigma (q)=\mathbf{a}$, which is the assertion for $j=q-1,q$. For the induction step, suppose the claim known for $p-1$, so that $\sigma (q-p)$ and $\sigma (q-p+1)$ are reduced words for $w$; apply step 1.3 to this pair of words. If they are braid-equivalent, then their classes coincide and, since $q-p$ and $q-p+1$ have opposite parity, the known class rule forces the classes of $\mathbf{a}$ and $\mathbf{b}$ to coincide, and we are done. Otherwise the second alternative of step 1.3 holds for the pair, which says that deleting the last letter of $\sigma (q-p)$ and prepending the first letter of $\sigma (q-p+1)$ yields a word that is reduced, represents $w$, and is braid-equivalent to $\sigma (q-p+1)$. Now $\sigma (q-p)$ is the alternating word of length $p+1$ ending in $a$ followed by $a_2,\dots ,a_{q-p}$, so deleting its last letter leaves the alternating word of length $p+1$ ending in $a$ followed by $a_2,\dots ,a_{q-p-1}$; the first letter of $\sigma (q-p+1)$ is the first letter of the alternating word of length $p$ ending in $a$, which differs from the first letter of the alternating word of length $p+1$ ending in $a$, so prepending it produces the alternating word of length $p+2$ ending in $a$ followed by $a_2,\dots ,a_{q-p-1}$, which is exactly $\sigma (q-p-1)$. Hence $\sigma (q-p-1)$ is reduced, represents $w$, and lies in the class of $\sigma (q-p+1)$; since $q-p-1$ and $q-p+1$ have the same parity, this agrees with the claimed class rule and the claim holds for $p$.

The final phase. Assume the claim of step 2.1 with $p=q-2$, and assume that $\mathbf{a}$ and $\mathbf{b}$ are not braid-equivalent; then every $\sigma (j)$ for $j\in \{1,\dots ,q\}$ is a reduced word for $w$ whose class is the class of $\mathbf{a}$ when $j-q$ is even and the class of $\mathbf{b}$ when $j-q$ is odd. In particular $\sigma (1)$ is the alternating word of length $q$ ending in $a$, and $\sigma (2)$ is the alternating word of length $q-1$ ending in $a$ followed by the single letter $a_2$. Write $v$ for the value of the alternating word of length $q-1$ ending in $a$ and $\epsilon$ for the letter with which the alternating word of length $q$ ending in $a$ begins; then the word $\sigma (1)$ has value $\epsilon v$ and $\sigma (2)$ has value $v{a}_2$, and since both represent $w$ one has $\epsilon v=v{a}_2$, that is $a_2=v^{-1}\epsilon v$. So $a_2$ is conjugate to $\epsilon \in \{a,b\}$ by the element $v$, which lies in the dihedral subgroup $⟨a,b⟩$; hence $a_2\in ⟨a,b⟩$, and since $a_2\in S$, step 1.1 gives $a_2\in \{a,b\}$. The letter $a_2$ cannot be $a$: the word $\sigma (2)$ would then end in two equal letters $a,a$, and deleting that pair would express $w$ by a word shorter than $q=\mathrm{\ell }(w)$, so $\sigma (2)$ would not be reduced. Hence $a_2=b$, so $\sigma (2)$ is the alternating word of length $q$ ending in $b$; of the two alternating words of length $q$ in $\{a,b\}$, $\sigma (1)$ ends in $a$ and $\sigma (2)$ ends in $b$. To see that this forces $q=m$, compare the values of $\sigma (1)$ and $\sigma (2)$ in the dihedral group $⟨a,b⟩$, whose elements are the powers of $r=ab$; if $q$ is even these values are $(r^{-1}{)}^{q\mathrm{/}2}$ and $r^{q\mathrm{/}2}$, equal exactly when $r^q=1$, and if $q$ is odd they are $r^{(q-1)\mathrm{/}2}a$ and $r^{-(q-1)\mathrm{/}2}b$, equal exactly when $r^{q-1}=r^{-1}$, that is $r^q=1$. Since $\sigma (1)$ and $\sigma (2)$ represent the same element, $r^q=1$; when $m=\mathrm{\infty }$ no positive power of $r$ is $1$ by [F3], so this alternative cannot occur and $m<\mathrm{\infty }$, and then by minimality of the order $m$ one has $q\ge m$. Conversely $q\le m$: by [F3] the prefix reflections of the reduced word $\sigma (1)$ are pairwise distinct, while the closed form of [F3] for alternating words gives $r_{i+m}=r_i$ for these reflections (here $(ab{)}^m=1$ because $m<\mathrm{\infty }$), so $q>m$ would make the reflections at positions $1$ and $1+m$ coincide, a contradiction. Hence $q=m$. Finally, the two words $\sigma (1)$ and $\sigma (2)$ are the two alternating words of length $m$, so one is obtained from the other by the single replacement of the alternating block of length $m$ by the other alternating word of the same length; they are braid-equivalent, hence in the same class, but by the class rule their classes are the classes of $\mathbf{a}$ and of $\mathbf{b}$ respectively, so $\mathbf{a}$ and $\mathbf{b}$ are braid-equivalent, against the assumption.

Conclusion. Part (1) follows by strong induction on $q=\mathrm{\ell }(w)$: for $q\le 1$ two reduced words for $w$ coincide, and for $q\ge 2$, reduced words with the same first letter are handled by the induction hypothesis applied to their tails, while reduced words with different first letters are handled by steps 1.3, 2.1 and 3.1, which produce braid-equivalence in every case. For part (2), let $\mathbf{c}=(c_1,\dots ,c_k)$ be a word with value $w$. If $\mathbf{c}$ is reduced, no sequence of braid moves and deletions of consecutive equal pairs can shorten it: braid moves preserve the value and the length by step 1.2, deleting a consecutive pair preserves the value, and a shorter word for $w$ would contradict $k=\mathrm{\ell }(w)$. Conversely, if $\mathbf{c}$ is not reduced, we show by induction on $k$ that it can be shortened; for $k\le 1$ the word is reduced, so $k\ge 2$, and if the suffix $(c_2,\dots ,c_k)$ can be shortened, the same sequence shortens the whole word. Otherwise the suffix is M-reduced, so by induction on $k$ it is reduced, with value $w^{\mathrm{\prime }}$ and $\mathrm{\ell }(w^{\mathrm{\prime }})=k-1$. Since $w=c_1{w}^{\mathrm{\prime }}$ has length at most $k-1<\mathrm{\ell }(w^{\mathrm{\prime }})+1$, the length laws of [F4] give $\mathrm{\ell }(c_1{w}^{\mathrm{\prime }})=\mathrm{\ell }(w^{\mathrm{\prime }})-1=k-2$, and the exchange condition of [F4] applied to the reduced word $(c_2,\dots ,c_k)$ and the letter $c_1$ gives $c_1{w}^{\mathrm{\prime }}=c_2\cdots \widehat{c_j}\cdots c_k$ for some $j$, so that $w^{\mathrm{\prime }}=c_1{c}_2\cdots \widehat{c_j}\cdots c_k$ is a reduced expression of $w^{\mathrm{\prime }}$ of length $k-1$ beginning with $c_1$. By part (1) it is braid-equivalent to $(c_2,\dots ,c_k)$, and prepending $c_1$ to both words exhibits a sequence of braid moves taking $\mathbf{c}=(c_1,c_2,\dots ,c_k)$ to $(c_1,c_1,c_2,\dots ,\widehat{c_j},\dots ,c_k)$, which the deletion of the consecutive pair $c_1,c_1$ shortens. Hence a word is reduced if and only if it is M-reduced.