Right-handed strong exchange and the augmentation step for reduced subwords

Assume the hypotheses of (1): $u=s_1\cdots s_q$ is reduced and $t\in T$ has $\mathrm{\ell }(ut)<\mathrm{\ell }(u)$. Then $u^{-1}=(s_1\cdots s_q{)}^{-1}=s_q\cdots s_1$ by the inverse of a product, and the reversed word $s_q\cdots s_1$ has length $q=\mathrm{\ell }(u)=\mathrm{\ell }(u^{-1})$, so it is a reduced expression of $u^{-1}$; moreover $\mathrm{\ell }(t{u}^{-1})=\mathrm{\ell }((t{u}^{-1}{)}^{-1})=\mathrm{\ell }(ut)<\mathrm{\ell }(u)=\mathrm{\ell }(u^{-1})$, since $(t{u}^{-1}{)}^{-1}=ut$.

Now assume the hypotheses of (2): $w=s_1\cdots s_q$ is reduced, $u\mathrm{\ne }w$, and $u$ is the product of the letters of $s_1\cdots s_q$ remaining after the letters at the positions of a set $D=\{i_1<\cdots <i_k\}\subseteq \{1,\dots ,q\}$ are deleted, the remaining word being a reduced expression of $u$; then its length $q-k$ equals $\mathrm{\ell }(u)$, so $k=q-\mathrm{\ell }(u)$. Fix such a description for which $i_k$ is as small as possible, for instance the lexicographically least one among those with $i_k$ minimal; this is a determinate rule on a finite nonempty set of positions, so it uses no choice. Since $i_k$ is the largest element of $D$, every position of $\{i_k+1,\dots ,q\}$ is retained. Put $Y:=s_q\cdots s_{i_k+1}$ and $C:=s_{i_k+1}\cdots s_q=Y^{-1}$, and put $t:=Y{s}_{i_k}{Y}^{-1}=(s_q\cdots s_{i_k+1})s_{i_k}(s_{i_k+1}\cdots s_q)$; then $t\in T$, because it is the conjugate of the simple reflection $s_{i_k}$ by the element $Y$.

Apply [F1] to the element $u^{-1}$, the reflection $t$ and the reduced expression $u^{-1}=t_1\cdots t_q$ with $t_j:=s_{q+1-j}$ (so $t_1=s_q$ down to $t_q=s_1$): there is a unique $i^{\mathrm{\prime }}\in \{1,\dots ,q\}$ with $t{u}^{-1}=t_1\cdots \widehat{t_{i^{\mathrm{\prime }}}}\cdots t_q=s_q\cdots \widehat{s_{q+1-i^{\mathrm{\prime }}}}\cdots s_1$ and $t=t_1\cdots t_{i^{\mathrm{\prime }}-1}{t}_{i^{\mathrm{\prime }}}{t}_{i^{\mathrm{\prime }}-1}\cdots t_1=(s_q\cdots s_{q+2-i^{\mathrm{\prime }}})s_{q+1-i^{\mathrm{\prime }}}(s_{q+2-i^{\mathrm{\prime }}}\cdots s_q)$.

Since every position greater than $i_k$ is retained, the retained letters of $s_1\cdots s_q$ are the retained letters at positions less than $i_k$, followed by the letters $s_{i_k+1},\dots ,s_q$; writing $P$ for the product of the retained letters at positions less than $i_k$, in increasing order, we have $u=PC$ by [F4]. Hence $ut=PCY{s}_{i_k}{Y}^{-1}=P{s}_{i_k}{Y}^{-1}=P{s}_{i_k}(s_{i_k+1}\cdots s_q)$, using $CY=(s_{i_k+1}\cdots s_q)(s_q\cdots s_{i_k+1})=1$; this is exactly the product $W^{\mathrm{\prime }}$ of the word obtained from $s_1\cdots s_q$ by deleting only the letters at the positions $i_1,\dots ,i_{k-1}$. The word $W^{\mathrm{\prime }}$ has length $(q-k)+1=\mathrm{\ell }(u)+1$, so $\mathrm{\ell }(ut)\le \mathrm{\ell }(u)+1$.

Invert the first identity of step 2.1: using $(xy{)}^{-1}=y^{-1}{x}^{-1}$ and $s_j^{-1}=s_j$ for all letters, $ut=(t{u}^{-1}{)}^{-1}=(s_q\cdots \widehat{s_{q+1-i^{\mathrm{\prime }}}}\cdots s_1{)}^{-1}=s_1\cdots \widehat{s_{q+1-i^{\mathrm{\prime }}}}\cdots s_q$. Put $i:=q+1-i^{\mathrm{\prime }}$, so that $i^{\mathrm{\prime }}\in \{1,\dots ,q\}$ runs through $\{1,\dots ,q\}$ exactly as $i$ does; then $ut=s_1\cdots \widehat{s_i}\cdots s_q$, the second identity of step 2.1 reads $t=(s_q\cdots s_{i+1})s_i(s_{i+1}\cdots s_q)$, and $i$ is unique because $i^{\mathrm{\prime }}$ is. Finally $u=(ut)t$ with $t\in T$ and $\mathrm{\ell }(u)>\mathrm{\ell }(ut)$, so $ut\to u$ is a Bruhat edge by [F3]. This proves (1).

By reflection parity $\mathrm{\ell }(ut)\equiv \mathrm{\ell }(u)+1(\mathrm{m}\mathrm{o}\mathrm{d}2)$, so $\mathrm{\ell }(ut)\mathrm{\ne }\mathrm{\ell }(u)$; together with step 2.2 this leaves $\mathrm{\ell }(ut)=\mathrm{\ell }(u)+1$ or $\mathrm{\ell }(ut)\le \mathrm{\ell }(u)-1$. Suppose, to rule out the second alternative, that $\mathrm{\ell }(ut)<\mathrm{\ell }(u)$. Apply part (1), proved in step 3.1, to the reduced expression of $u$ formed by the retained letters of $s_1\cdots s_q$ and to the reflection $t$: there is a unique retained position $p$ of $s_1\cdots s_q$ such that $ut$ is the product of that reduced expression with its letter at $p$ deleted, and such that $t=Z^{-1}{s}_{p}Z$, where $Z$ is the product, in increasing order, of the retained letters at positions strictly greater than $p$.

Consider first the case $p>i_k$. Then every position greater than $p$ is retained, so $Z=s_{p+1}\cdots s_q$. Compute $wt$: since $s_1\cdots s_q=(s_1\cdots s_{i_k})C$ and $CY=1$, we get $wt=(s_1\cdots s_{i_k})CY{s}_{i_k}{Y}^{-1}=(s_1\cdots s_{i_k})s_{i_k}{Y}^{-1}=s_1\cdots s_{i_k-1}{s}_{i_k+1}\cdots s_q=:w^{\mathrm{\prime }\mathrm{\prime }}$, a word of length $q-1$ for $wt$, so $\mathrm{\ell }(wt)\le q-1<q=\mathrm{\ell }(w)$. Now multiply $w^{\mathrm{\prime }\mathrm{\prime }}$ on the right by $t=Z^{-1}{s}_{p}Z$: in the word $w^{\mathrm{\prime }\mathrm{\prime }}$ the letters after position $p$ are again $s_{p+1}\cdots s_q=Z$, so $w{t}^2=w^{\mathrm{\prime }\mathrm{\prime }}{Z}^{-1}{s}_{p}Z=(s_1\cdots \widehat{s_{i_k}}\cdots s_p)Z{Z}^{-1}{s}_{p}Z=s_1\cdots \widehat{s_{i_k}}\cdots \widehat{s_p}\cdots s_q$, a word of length $q-2$ representing $w{t}^2=w$, which contradicts $\mathrm{\ell }(w)=q$.

It remains to rule out the case $p<i_k$. Let $B$ be the product, in increasing order, of the retained letters at positions strictly between $p$ and $i_k$, and let $A$ be the product, in increasing order, of the retained letters at positions less than $p$; thus $u=A{s}_{p}BC$ and $Z=BC$. From $t=Z^{-1}{s}_{p}Z=C^{-1}{B}^{-1}{s}_{p}BC$ and $t=Y{s}_{i_k}{Y}^{-1}=C^{-1}{s}_{i_k}C$ we get $B^{-1}{s}_{p}B=s_{i_k}$, hence $u=A{s}_{p}BC=A(B{s}_{i_k}{B}^{-1})BC=AB{s}_{i_k}C$, so $u$ is the product of the word obtained from $s_1\cdots s_q$ by deleting the letters at the positions $(D\setminus \{i_k\})\cup \{p\}$: this word has $k$ deleted positions, hence length $q-k=\mathrm{\ell }(u)$, and it represents $u$, so it is a reduced subword expression of $u$; its largest deleted position is $\max (i_{k-1},p)$ when $k\ge 2$ and $p$ when $k=1$, in both cases strictly smaller than $i_k$, contradicting the minimality of $i_k$ in step 1.2.

Both cases being impossible, $\mathrm{\ell }(ut)=\mathrm{\ell }(u)+1$, so $u\to ut$ is a Bruhat edge by [F3]; the word $W^{\mathrm{\prime }}$ of step 2.2 has length $\mathrm{\ell }(ut)$ and represents $ut$, so it is a reduced expression of $ut$ and it is a subword of $s_1\cdots s_q$. With $v:=ut$ this is precisely the conclusion of (2). The only selections in the proof are a description with $i_k$ minimal (a deterministic rule on a finite set, step 1.2) and the unique strong-exchange index of step 2.1 or step 4.1; no choice principle is used.