Bruhat Subword Order and Lifting

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.

For the implication from left to right in (1), let $u=x_0\to x_1\to \cdots \to x_m=w$ be a chain exhibiting $u\le w$, with $x_{j+1}=x_j{t}_j$, $t_j\in T$ and $\mathrm{\ell }(x_{j+1})>\mathrm{\ell }(x_j)$; the case $m=0$ (so $u=w$) is the case of the full subword, and we prove by downward induction on $j$ that every $x_j$ is the product of a subword of $s_1\cdots s_q$. For the base case $j=m$ this is clear since $x_m=w=s_1\cdots s_q$.

For the implication from right to left in (1), assume $u=s_{i_1}\cdots s_{i_k}$ with $1\le i_1<\cdots <i_k\le q$; reducing that word by two-letter deletions if necessary, we may suppose it is a reduced expression of $u$, since deletions only remove positions and so the result is still a subword of $s_1\cdots s_q$. Induct on $d:=\mathrm{\ell }(w)-\mathrm{\ell }(u)\ge 0$: if $d=0$ then $k=q$ and $u=w$, so $u\le w$ by reflexivity.

For the inductive step of step 1.1, suppose $x_{j+1}$ is the product of the subword at positions $P_{j+1}\subseteq \{1,\dots ,q\}$. If the word $(s_p{)}_{p\in P_{j+1}}$ is not reduced, apply the two-letter deletion property repeatedly to replace it by a reduced expression of $x_{j+1}$ obtained by deleting letters, so that the result is again a subword of $s_1\cdots s_q$; applying the right-handed strong exchange of [F2] to this reduced expression of $x_{j+1}$ and to $t_j$ (legal since $\mathrm{\ell }(x_{j+1}{t}_j)=\mathrm{\ell }(x_j)<\mathrm{\ell }(x_{j+1})$) exhibits $x_j=x_{j+1}{t}_j$ as that word with one letter deleted, hence as the product of a subword of $s_1\cdots s_q$.

For the inductive step of step 1.2, let $d>0$, so $u\mathrm{\ne }w$; the augmentation lemma [F1] applied to the fixed reduced expression $w=s_1\cdots s_q$ produces $v\in W$ with $u\to v$, $\mathrm{\ell }(v)=\mathrm{\ell }(u)+1$, and $v$ the product of a reduced subword of $s_1\cdots s_q$. The induction hypothesis applies to $v$ (the length gap is $d-1$) and gives $v\le w$, whence $u\le v\le w$ by transitivity.

This completes the downward induction of step 2.1: $x_0=u$ is the product of a subword of $s_1\cdots s_q$, and applying the two-letter deletion property once more to that subword word produces a reduced subword expression of $u$, whose length is $\mathrm{\ell }(u)$; hence the indices in (1) may always be chosen with $k=\mathrm{\ell }(u)$. Together with step 2.2 this proves (1) in both directions.

For (2), the statement of part (1) is formulated for an arbitrary reduced expression $w=s_1\cdots s_q$ of $w$ and its proof used nothing particular about that expression, so (a) implies (b); (b) trivially implies (c); and (c) implies (a) by the right-to-left direction of (1). Finally the empty subword of any reduced expression of $w$ realizes $1$ and is one of the subwords allowed in (1), so $1\le w$ for every $w$, which is (3). No use of the Axiom of Choice is made: the induction runs on natural numbers, deletions act on the current explicit word, and the subword expressions used are the given ones.

For (1), fix a reduced expression $v=s_1\cdots s_q$. For every $x\in [u,v]$ the relation $x\le v$ and [F1] provide at least one subset $P\subseteq \{1,\dots ,q\}$ with $x$ the product of the letters at the positions in $P$ in increasing order; assign to $x$ the lexicographically first such subset, a determinate rule on a nonempty finite set of subsets of $\{1,\dots ,q\}$. The resulting map $[u,v]\to \{0,1{\}}^q$ is injective, because a subset determines $x$ as the product of its letters in the given order; hence $\mathrm{\mid }[u,v]\mathrm{\mid }\le 2^q=2^{\mathrm{\ell }(v)}$, which proves (1).

For (2), induct on $d:=\mathrm{\ell }(v)-\mathrm{\ell }(u)\ge 0$. If $d=0$ then $u=v$ by the strict length increase of [F3], and the one-element chain $x_0:=u=v$ works.

For the inductive step of step 1.2, let $d>0$, so that $u\mathrm{\ne }v$. Fix a reduced expression $v=s_1\cdots s_q$ and a reduced subword expression of $u$ inside it, written in deleted-position form; the augmentation lemma [F2] gives $x_1\in W$ with $u\to x_1$, $\mathrm{\ell }(x_1)=\mathrm{\ell }(u)+1$, and $x_1$ the product of a reduced subword of the same word $s_1\cdots s_q$. By the subword criterion [F1], $x_1\le v$; the length gap $\mathrm{\ell }(v)-\mathrm{\ell }(x_1)$ is $d-1$, so the induction hypothesis of step 1.2 applies to the pair $(x_1,v)$ and produces a chain $x_1<y_2<\cdots <y_m=v$ with lengths $\mathrm{\ell }(x_1)+1,\dots ,\mathrm{\ell }(v)$; prepending the edge $u\to x_1$ gives the required chain, each step of which is a Bruhat edge increasing the length by exactly one. This proves (2).

For (3), along a strict step the length strictly increases by [F3], so a chain from $u$ to $v$ with $m$ strict steps satisfies $\mathrm{\ell }(v)\ge \mathrm{\ell }(u)+m$, that is, $m\le \mathrm{\ell }(v)-\mathrm{\ell }(u)$. If $m<\mathrm{\ell }(v)-\mathrm{\ell }(u)$, then some step $x_{i-1}<x_i$ of the chain has $\mathrm{\ell }(x_i)-\mathrm{\ell }(x_{i-1})\ge 2$, and step 2.1 applied to that pair produces $z$ with $x_{i-1}<z<x_i$, so the chain is not maximal; hence every maximal chain has exactly $\mathrm{\ell }(v)-\mathrm{\ell }(u)$ steps, that is, $\mathrm{\ell }(v)-\mathrm{\ell }(u)+1$ elements. Thus the rank function $x\mapsto \mathrm{\ell }(x)-\mathrm{\ell }(u)$ is well defined on $[u,v]$ and every maximal chain between two comparable elements has the same length. If $x<y$ with no $z$ satisfying $x<z<y$, then the two-element chain $x<y$ is maximal in $[x,y]$, so it has exactly $\mathrm{\ell }(y)-\mathrm{\ell }(x)$ strict steps, whence $\mathrm{\ell }(y)=\mathrm{\ell }(x)+1$. No use of the Axiom of Choice is made: the only selection is the lexicographically first subword of step 1.1, a deterministic rule on a finite set.