Descent reduction, minimum-length elements, and the additive factorization in a double coset

Descent reduction. A total order on $S$ exists because $S$ is finite (transport the order from any finite enumeration). Use the fixed order in every least-generator selection. Suppose $x\in \mathrm{\Omega }(d)$ and $\mathrm{\ell }(sx)<\mathrm{\ell }(x)$ for some $s\in I$; then $s\in W_I$ and $sx=s\cdot x\cdot 1\in W_{I}x{W}_J=W_{I}d{W}_J=\mathrm{\Omega }(d)$, because $W_{I}x{W}_J=W_I(W_{I}d{W}_J)W_J=W_{I}d{W}_J$ by [F3] and [F7]. Likewise, if $\mathrm{\ell }(xs)<\mathrm{\ell }(x)$ for some $s\in J$, then $xs\in \mathrm{\Omega }(d)$ by [F3] and [F7]. By [F1] each replacement lowers $\mathrm{\ell }$ by exactly $1$, so a process that starts at $x=d$, replaces $x$ by $sx$ with the least $s\in I$ of $\mathrm{\ell }(sx)<\mathrm{\ell }(x)$ if one exists and otherwise by $xs$ with the least $s\in J$ of $\mathrm{\ell }(xs)<\mathrm{\ell }(x)$ if one exists, and stops when neither exists, performs at most $\mathrm{\ell }(d)$ replacements and terminates, because the values of $\mathrm{\ell }$ lie in $\mathbb{N}$ by [F2]. At termination $x\in \mathrm{\Omega }(d)$ and there is no $s\in I$ with $\mathrm{\ell }(sx)<\mathrm{\ell }(x)$ and no $s\in J$ with $\mathrm{\ell }(xs)<\mathrm{\ell }(x)$; since the differences lie in $\{\pm 1\}$ by [F1], this says $\mathrm{\ell }(sx)>\mathrm{\ell }(x)$ for all $s\in I$ and $\mathrm{\ell }(xs)>\mathrm{\ell }(x)$ for all $s\in J$, that is, $x\in {}^I{W}^J$ by [F3].

The middle block of a reducing word is never deleted. Let $m$ be an element of minimum length in $\mathrm{\Omega }:=W_{I}w{W}_J$ and let $x\in \mathrm{\Omega }$, say $x=am{a}^{\mathrm{\prime }}$ with $a\in W_I$, $a^{\mathrm{\prime }}\in W_J$ by [F3]. Choose reduced words $A=(a_1,\dots ,a_r)$ for $a$, $M=(m_1,\dots ,m_q)$ for $m$ and $A^{\mathrm{\prime }}=(a_1^{\mathrm{\prime }},\dots ,a_{r^{\mathrm{\prime }}}^{\mathrm{\prime }})$ for $a^{\mathrm{\prime }}$; by [F5] the letters of $A$ lie in $I$ and those of $A^{\mathrm{\prime }}$ in $J$. While the current word, which begins as $A$ followed by $M$ followed by $A^{\mathrm{\prime }}$, is not reduced, choose the lexicographically least pair of positions $i<j$ whose deletion preserves the value, which exists by [F6], and delete the two positions; write the current word as $A_{i}M{A}_i^{\mathrm{\prime }}$, where $A_i$ and $A_i^{\mathrm{\prime }}$ are the surviving subwords of $A$ and $A^{\mathrm{\prime }}$ and, by induction over the rounds, the full block $M$ survives. Such a deletion pair never removes a letter of $M$: if both deleted letters lay in $M$, then the surviving word $A_i{M}_1{A}_i^{\mathrm{\prime }}$ has the value $x$ of $A_{i}M{A}_i^{\mathrm{\prime }}$, so by [F6] and [F7] the word $M_1$ has the same value $m$ as $M$, while $M_1$ has length $q-2$, contradicting $\mathrm{\ell }(m)=q$ by [F2]; if exactly one deleted letter lay in $M$ and the other in $A_i$, then the surviving word is $A_{i+1}{M}_1{A}_i^{\mathrm{\prime }}$ with $A_{i+1}$ equal to $A_i$ with one letter deleted and $M_1$ equal to $M$ with one letter deleted, so by [F6] and [F7] the value of $M_1$ equals $\mathrm{val}(A_{i+1}{)}^{-1}x\mathrm{val}(A_i^{\mathrm{\prime }}{)}^{-1}$, and this lies in $W_{I}x{W}_J=\mathrm{\Omega }$ because $\mathrm{val}(A_{i+1})\in W_I$ and $\mathrm{val}(A_i^{\mathrm{\prime }})\in W_J$ by [F3]; but $M_1$ has length $q-1$, so by [F2] the value of $M_1$ has length $\le q-1<q=\mathrm{\ell }(m)$, contradicting the minimality of $m$ in $\mathrm{\Omega }$; the case of one deleted letter in $M$ and one in $A_i^{\mathrm{\prime }}$ is the same with the roles of $A_i$ and $A_i^{\mathrm{\prime }}$ exchanged. A deletion pair with both letters outside $M$ is not excluded; it simply shortens $A_i$ or $A_i^{\mathrm{\prime }}$. Each deletion lowers the number of letters by $2$, so the process terminates at a reduced word of $x$ of the form $A_{0}M{A}_0^{\mathrm{\prime }}$, where $A_0$ and $A_0^{\mathrm{\prime }}$ arise from $A$ and $A^{\mathrm{\prime }}$ by deletions and $M$ is untouched; the words $A_0$ and $A_0^{\mathrm{\prime }}$ are themselves reduced, since a two-letter deletion inside $A_0$ preserving the value of $A_0$ would, by [F6] and [F7], preserve the value $x$ of the reduced word $A_{0}M{A}_0^{\mathrm{\prime }}$. Writing $a_0:=\mathrm{val}(A_0)\in W_I$ and $a_0^{\mathrm{\prime }}:=\mathrm{val}(A_0^{\mathrm{\prime }})\in W_J$, the reducedness of $A_{0}M{A}_0^{\mathrm{\prime }}$ gives $x=a_{0}m{a}_0^{\mathrm{\prime }}$ and $\mathrm{\ell }(x)=\mathrm{\ell }(a_0)+\mathrm{\ell }(m)+\mathrm{\ell }(a_0^{\mathrm{\prime }})$.

A minimum has no descents. Let $w\in W$ and let $\mathrm{\Omega }:=W_{I}w{W}_J$; this set is nonempty, so the set $\{\mathrm{\ell }(x):x\in \mathrm{\Omega }\}\subseteq \mathbb{N}$ has a least element by [F4], and we choose $m\in \mathrm{\Omega }$ with $\mathrm{\ell }(m)$ that least element. If $s\in I$ and $\mathrm{\ell }(sm)<\mathrm{\ell }(m)$, then $sm\in \mathrm{\Omega }$ by [F3] and [F7], contradicting minimality; hence $\mathrm{\ell }(sm)>\mathrm{\ell }(m)$ for all $s\in I$, because $\mathrm{\ell }(sm)=\mathrm{\ell }(m)\pm 1$ by [F1]. Symmetrically $\mathrm{\ell }(ms)>\mathrm{\ell }(m)$ for all $s\in J$. Therefore $m\in {}^I{W}^J$ by [F3]: by step 1.1 every double coset $W_{I}w{W}_J$ contains an element of ${}^I{W}^J$, and taking $m$ of minimum length shows each double coset also has a minimum, which lies in ${}^I{W}^J$.

Every element of ${}^I{W}^J$ is a minimum of its double coset. Let $d\in {}^I{W}^J$ and let $m$ be a minimum-length element of $\mathrm{\Omega }(d)$, which exists by step 2.1. Applying step 1.2 with $w:=d$, $x:=d$ gives $d=a_{0}m{a}_0^{\mathrm{\prime }}$ with $a_0\in W_I$, $a_0^{\mathrm{\prime }}\in W_J$ and $\mathrm{\ell }(d)=\mathrm{\ell }(a_0)+\mathrm{\ell }(m)+\mathrm{\ell }(a_0^{\mathrm{\prime }})$. If $a_0\mathrm{\ne }1$, then $a_0$ has a reduced expression whose first letter $s$ lies in $I$ by [F5], so $\mathrm{\ell }(s{a}_0)=\mathrm{\ell }(a_0)-1$, and by [F2] and [F7] $\mathrm{\ell }(sd)=\mathrm{\ell }(s{a}_{0}m{a}_0^{\mathrm{\prime }})\le \mathrm{\ell }(s{a}_0)+\mathrm{\ell }(m)+\mathrm{\ell }(a_0^{\mathrm{\prime }})=\mathrm{\ell }(d)-1<\mathrm{\ell }(d)$, contradicting $\mathrm{\ell }(sd)>\mathrm{\ell }(d)$ for $s\in I$, which holds because $d\in {}^{I}W$ by [F3]. Hence $a_0=1$, and symmetrically $a_0^{\mathrm{\prime }}=1$, so $d=m$: the element $d$ of ${}^I{W}^J$ is a minimum-length element of $\mathrm{\Omega }(d)$.

Minimality, the equality case, and the additive factorization. Let $d\in {}^I{W}^J$ and $x\in \mathrm{\Omega }(d)$. By step 3.1 the element $d$ is a minimum-length element of $\mathrm{\Omega }(d)$, so step 1.2 applied with $m:=d$ exhibits $x=udv$ with $u\in W_I$, $v\in W_J$ and $\mathrm{\ell }(x)=\mathrm{\ell }(u)+\mathrm{\ell }(d)+\mathrm{\ell }(v)$, which is the additive factorization (3); in particular $\mathrm{\ell }(x)\ge \mathrm{\ell }(d)$, with equality if and only if $\mathrm{\ell }(u)=\mathrm{\ell }(v)=0$, that is, $u=v=1$ and $x=d$. If $d^{\mathrm{\prime }}\in {}^I{W}^J\cap \mathrm{\Omega }(d)$ is a second element, then applying the factorization with $x:=d^{\mathrm{\prime }}$ gives $\mathrm{\ell }(d^{\mathrm{\prime }})=\mathrm{\ell }(u)+\mathrm{\ell }(d)+\mathrm{\ell }(v)$ and, since $d^{\mathrm{\prime }}$ is also a minimum of $\mathrm{\Omega }(d)$ by step 3.1, $\mathrm{\ell }(d^{\mathrm{\prime }})=\mathrm{\ell }(d)$, so $u=v=1$ and $d^{\mathrm{\prime }}=d$: each double coset contains at most one element of ${}^I{W}^J$, and by step 1.1 it contains one, namely its unique element of minimum length. Finally, if $x\in W_{I}w{W}_J$ has minimum length in $W_{I}w{W}_J$, then $x\in {}^I{W}^J$ by step 2.1. This proves (2) and completes the proof.