Bruhat Subword Order and Lifting — Examples

For the Bruhat relation in (i): $u=s_1{s}_3$ is the value of the subword at positions $1,3$ of the word $s_1{s}_2{s}_3$, and $2341=s_1{s}_2{s}_3$ because right multiplying the identity by $s_1,s_2,s_3$ in turn gives $2134,2314,2341$ by [F2]; both words are reduced, since their lengths $2$ and $3$ equal the inversion numbers of their values $2143$ and $2341$ by [F1] and [F3]. The subword criterion [F5] therefore gives $u\le v$.

For (ii): a right-weak step $x\to x{s}_i$ with $\mathrm{\ell }(x{s}_i)>\mathrm{\ell }(x)$ is a Bruhat edge because $s_i\in S\subseteq T$ by [F4]; a left-weak step $x\to s_{i}x$ with $\mathrm{\ell }(s_{i}x)>\mathrm{\ell }(x)$ is a Bruhat edge by the left-multiplication clause of [F4]. Chains of Bruhat edges are Bruhat chains, so $u{\le }_{R}v$ or $u{\le }_{L}v$ implies $u\le v$; in particular the chain $1234\to 2134\to 2314\to 2341$ is a chain of $R$-steps with increasing lengths (each step applies $s_1$, $s_2$, $s_3$ in turn and raises the inversion number by $1$ by [F1], [F2], [F3]), so $1234{\le }_{R}2134{\le }_{R}2314{\le }_{R}2341$ and the same four elements form a Bruhat chain.

For the weak relations in (i): a chain realizing $u{\le }_{R}v$ or $u{\le }_{L}v$ has steps of length increase at least $1$, so a chain with $k$ steps satisfies $\mathrm{\ell }(v)\ge \mathrm{\ell }(u)+k$, that is, $k\le \mathrm{\ell }(v)-\mathrm{\ell }(u)=3-2=1$; since $u\mathrm{\ne }v$ at least one step is needed, so exactly one step occurs and $v=u{s}_i$ (for ${\le }_R$) or $v=s_{i}u$ (for ${\le }_L$) with $\mathrm{\ell }$ increasing. The six products, computed by the position- and value-swapping rules of [F2], are $u{s}_1=1243$, $u{s}_2=2413$, $u{s}_3=2134$, $s_{1}u=1243$, $s_{2}u=3142$ and $s_{3}u=2134$, and none of them equals $2341$; hence neither $u{\le }_{R}v$ nor $u{\le }_{L}v$ holds.

For (iii): step 2.1 exhibits $u\le v$ in Bruhat order together with the failure of both $u{\le }_{R}v$ and $u{\le }_{L}v$, so the converse of the implication proved in step 1.2 fails, in the sharp form that Bruhat comparability does not imply comparability in either weak order already in $S_4$. All assertions are finite computations in $S_4$ and use no choice principle.

For (i): $v=2431=s_1{s}_2{s}_3{s}_2=s_1{s}_3{s}_2{s}_3$, because the two words differ only in their last three letters, which are the two words $s_2{s}_3{s}_2$ and $s_3{s}_2{s}_3$ of the same element of the rank-two parabolic $⟨s_2,s_3⟩$ (the braid relation), and $v$ has inversion number $4$ by [F3], so both words have length $4=\mathrm{\ell }(v)$ and are reduced expressions of $v$ by [F1]; the product $s_1{s}_2{s}_3{s}_2=2431$ is computed by applying [F2] letter by letter. The element $u=s_2$ has one-line form $1324$ and $\mathrm{\ell }(u)=1$; it occurs in $s_1{s}_2{s}_3{s}_2$ at positions $2$ and $4$ and in $s_1{s}_3{s}_2{s}_3$ at position $3$ only, so the subword criterion [F4] gives $u\le v$ from either occurrence, at different positions in the two expressions of $v$.

For (ii): fix either reduced expression of $v$. Every subword value $x$ is the product of a subword of that reduced word, hence $x\le v$ by the right-to-left direction of [F4], and $1\le x$ by [F6], so the set of subword values of either expression is contained in the interval $[1,v]$; conversely, by [F5] every $x\in [1,v]$ has a reduced subword expression inside every reduced expression of $v$, hence is a value of a subword of either of the two words. Therefore the sets of subword values of the two expressions are both equal to $[1,v]$, so they coincide. Enumerating the $16$ subwords of $s_1{s}_2{s}_3{s}_2$ by multiplying out the indicated letters with [F2] gives exactly the $12$ displayed permutations $1234$, $1243$, $1324$, $1342$, $1423$, $1432$, $2134$, $2143$, $2314$, $2341$, $2413$, $2431$ (the empty subword gives $1234$), and enumerating the $16$ subwords of $s_1{s}_3{s}_2{s}_3$ gives the same $12$ values; hence $[1,v]$ is exactly the displayed set.

Collecting: the two reduced expressions of $v$ describe the same interval below $v$, both by the general equivalence of [F5] and by the explicit enumeration of step 1.2 of the $16$ subwords of each expression; the element $u=s_2$ is described at position $2$ in the first expression and position $3$ in the second, so the positions may differ while the value is the same, as (i) says. If the two descriptions could disagree, then some element would have a subword expression in one reduced expression of $v$ and none in the other, contradicting [F5]; all computations are finite and use no choice principle.

The displayed products are computed by [F2]: $1342\cdot s_1=3142$, $1342\cdot s_2=1432$, $1342\cdot s_3=1324$, $1423\cdot s_2=1243$, $4132\cdot s_1=1432$, $4132\cdot s_2=4312$, $1432\cdot s_3=1423$ and $4123\cdot s_2=4213$. Their inversion numbers, computed with [F3] and equal to the lengths by [F1], are: $\mathrm{\ell }(1342)=2$, $\mathrm{\ell }(1423)=2$, $\mathrm{\ell }(4132)=4$, $\mathrm{\ell }(1432)=3$, $\mathrm{\ell }(4123)=3$, $\mathrm{\ell }(3142)=3$, $\mathrm{\ell }(1324)=1$, $\mathrm{\ell }(1243)=1$, $\mathrm{\ell }(4312)=5$ and $\mathrm{\ell }(4213)=4$.

First certify $u\le v$ in each case: in (a) and (b), $1342=s_2{s}_3$ occurs at positions $1,2$ of $4132=s_2{s}_3{s}_2{s}_1$; in (c), it occurs at positions $1,2$ of $1432=s_2{s}_3{s}_2$; and in (d), $1423=s_3{s}_2$ occurs at positions $1,2$ of $4123=s_3{s}_2{s}_1$. Each ambient word has length equal to the inversion number of its value, so [F1] and [F5] prove these initial comparisons. The comparisons required by the four cases — $us\le v$ and $u\le vs$ in (a), $us\le vs$ and $u\le vs$ in (b), $us\le vs$ and $us\le v$ in (c), and $us\le v$ and $u\le vs$ in (d) — are certified by subword witnesses in the displayed reduced words, each verified by multiplying out the indicated letters: $3142=s_2{s}_3{s}_1$ is the subword at positions $1,2,4$ of $4132=s_2{s}_3{s}_2{s}_1$; $1342=s_2{s}_3$ is the subword at positions $1,2$ of $1432=s_2{s}_3{s}_2$ and at positions $1,3$ of $4312=s_2{s}_1{s}_3{s}_2{s}_1$; $1432=s_2{s}_3{s}_2$ is the subword at positions $1,3,4$ of $4312=s_2{s}_1{s}_3{s}_2{s}_1$; $1324=s_2$ is the subword at position $1$ of $1432=s_2{s}_3{s}_2$ and at position $2$ of $1423=s_3{s}_2$; $1243=s_3$ is the subword at position $1$ of $4123=s_3{s}_2{s}_1$; and $1423=s_3{s}_2$ is the subword at positions $2,3$ of $4213=s_1{s}_3{s}_2{s}_1$. Each listed ambient word is reduced, since its value has inversion number equal to its length by [F1]; hence the subword criterion [F5] applies and gives the stated comparisons.

The two negative comparisons follow from length alone: in case (a) the elements $us=3142$ and $vs=1432$ both have length $3$ and are distinct, so they are incomparable by [F6], and in particular $us\le vs$ fails; in case (c) the elements $u=1342$ and $vs=1423$ both have length $2$ and are distinct, so they are incomparable by [F6], and in particular $u\le vs$ fails. The equalities of the displayed lengths with the inversion numbers were computed in step 1.1.

The descent and ascent patterns are read off the lengths computed in step 1.1: in (a) $\mathrm{\ell }(vs)=3<4=\mathrm{\ell }(v)$ and $\mathrm{\ell }(us)=3>2=\mathrm{\ell }(u)$; in (b) $\mathrm{\ell }(vs)=5>4$ and $\mathrm{\ell }(us)=3>2$; in (c) $\mathrm{\ell }(vs)=2<3$ and $\mathrm{\ell }(us)=1<2$; and in (d) $\mathrm{\ell }(vs)=4>3$ and $\mathrm{\ell }(us)=1<2$.

Each of the four cases of [F4] is therefore instantiated: case (a) by the pair $u=1342\le v=4132$ with $s=s_1$, where step 1.2 gives $us\le v$ and $u\le vs$ and step 2.1 shows the companion comparison $us\le vs$ fails; case (b) by the same pair with $s=s_2$, where $s$ is an ascent of both and step 1.2 gives $us\le vs$ and $u\le vs$; case (c) by $u=1342\le v=1432$ with $s=s_3$, where $s$ is a descent of both, step 1.2 gives $us\le vs$, $us\le v$ and step 2.1 shows $u\le vs$ fails; and case (d) by $u=1423\le v=4123$ with $s=s_2$, where step 1.2 gives $us\le v$ and $u\le vs$. In each case the four elements $u,v,us,vs$ form the lifting square of the theorem with the sides listed in the statement, and cases (a) and (c) show that the two extra comparisons cannot be asserted uniformly. All computations are finite enumerations in $S_4$ and use no choice principle.

Multiplying $s_1{s}_2{s}_3{s}_1{s}_2{s}_1$ by the position-swapping rule [F2] gives $4321$, whose six pairs are all inversions; thus the word is reduced of length $6$ by [F1] and [F3]. For (i), the word $s_1{s}_3$ is a subword of $s_1{s}_2{s}_3{s}_1{s}_2{s}_1$ at positions $1,3$, and it is reduced because $s_1$ and $s_3$ act on disjoint pairs of positions, so its value $s_1{s}_3$ has one-line form $2143$ and inversion number $2$, equal to its length of $2$ by [F1] and [F2]. The subword criterion [F4] applied to $x=u$ and $v=w_0$ gives $u\le w_0$, which is (i).

For (ii), first note that $S_4=[1,w_0]$: $S_4$ has $24$ elements and is finite, the Bruhat order on it is directed (The lifting property in all four descent cases, the cover criterion, reflection deletion, and directedness (4)), so finitely many pairwise upper bounds combine to a greatest element $z$ with $1\le x\le z$ for every $x\in S_4$; by the strict length increase of [F7] the element $z$ must have maximal length, and the maximum of $\mathrm{inv}$ on $S_4$ is $6$, attained only by the reverse permutation $4321=w_0$; hence $z=w_0$ and every element of $S_4$ satisfies $x\le w_0$, while conversely $x\le w_0$ means $x\in S_4$.

For (iii), multiplying out each deletion and reading the inversion numbers with [F1], [F2] and [F3]: deletion of position $1$, $4$ or $6$ gives $4312$, $4231$ or $3421$, each of length $5$; deletion of position $2$ or $5$ gives $4123$ or $2341$, each of length $3$; and deletion of position $3$ gives $1324$ of length $1$. By [F5] each value equals $w_0{\tau }_i$ for the reflection ${\tau }_i$ conjugated to the letter at position $i$, and each is strictly below $w_0$. Since $\mathrm{\ell }(w_0)=6$, the cover criterion [F5] says a deletion value is covered by $w_0$ exactly when its length is $5$: this holds for $i=1,4,6$ (the deletion words of length $5$ are reduced, since their length equals the inversion number of their value) and fails for $i=2,5,3$, where the deletion words of length $5$ are not reduced. Finally, the elements of $S_4$ of length $5$ are exactly $4312$, $4231$ and $3421$: a permutation has inversion number $5$ if and only if exactly one of the six pairs $i<j$ satisfies $\sigma (i)<\sigma (j)$, and the enumeration of the $24$ permutations confirms that this holds only for those three; hence the covers of $w_0$ are precisely the three elements of length $5$, and no element of length $<5$ can be covered by $w_0$ by [F5].

For (ii), every element of $S_4$ lies below $w_0$ by step 1.2 and therefore occurs as a subword value by [F4]; conversely every subword value belongs to $S_4$. Thus the $64$ position subsets realize exactly $S_4=[1,w_0]$, a set of $24$ elements. By the position-swapping rule [F2], the seven listed position sets evaluate respectively to $2134$, $1243$, $2143$, $1342$, $2341$, $2431$ and $4321$. Evaluating all $64$ subsets also gives exactly the six listed position sets for $2134$: the singletons $\{1\}$, $\{4\}$ and $\{6\}$ carry $s_1$, and $\{1,2,5\}$, $\{1,4,6\}$ and $\{2,5,6\}$ evaluate to $s_1{s}_2{s}_2=s_1$, $s_1^3=s_1$ and $s_2{s}_2{s}_1=s_1$, respectively.

Collecting: (i) is a direct instance of the subword criterion; (ii) shows that the $64$ subwords of one fixed reduced expression of $w_0$ realize exactly the $24$ elements of $S_4=[1,w_0]$, so subwords of one expression may repeat values, and the element $s_1$ arises from six different position sets; (iii) shows that the single-letter deletions of a reduced expression of $w_0$ realize three covers and three shorter elements, realizing the general cover criterion and reflection-deletion statements. All computations are finite and use no choice principle.