Bruhat Interval Labels, Shellings, and Möbius Functions — Examples

The eight elements. The fixed word $s_1{s}_2{s}_3$ is reduced with $\mathrm{\ell }(c)=3$, because $2341$ has exactly the three inversions $(3,4)$, $(2,4)$, $(1,4)$ [F3]; here the displayed letters $\{1,2,3,4\}$ are those of the published $S_4$ on $\{0,1,2,3\}$ shifted by $j\mapsto j-1$ [F4]. By [F2] an element $x$ of $W$ satisfies $x\le c$ if and only if $x$ is the product of a subword of $s_1{s}_2{s}_3$, so it remains to note that each of the eight subwords, with positions $\mathrm{\varnothing },\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$, is reduced: its product $1234,2134,1324,1243,2314,2143,1342,2341$ has inversion number equal to its number of letters, as displayed [F3]. The eight products are distinct one-line forms, so $[e,c]$ has exactly these eight elements, of ranks $0,1,1,1,2,2,2,3$.

The covers and the six maximal chains. By [F1] the elements covered by $c$ are the single-letter deletions of the reduced word $s_1{s}_2{s}_3$ whose remaining word is reduced: deleting positions $1,2,3$ leaves $s_2{s}_3=1342$, $s_1{s}_3=2143$, $s_1{s}_2=2314$, each of length $2=\mathrm{\ell }(c)-1$, so these three and no others are covered by $c$, because every element covered by $c$ has length $2$ and the length-two elements of $[e,c]$ are exactly these three. Each atom covers $e$ by the cover criterion, and each atom lies below $c$ by [F2], so the three pairs $s⋗e$ are covers. For a length-two element $x=t_i{t}_j$ with $i<j$, the products of subwords of the reduced word $t_i{t}_j$ are exactly $e,t_i,t_j,x$, so by [F2] the elements of $[e,x]$ are exactly these four and the atoms covered by $x$ are $t_i$ and $t_j$; applying this to $1342=s_2{s}_3$, $2143=s_1{s}_3$, $2314=s_1{s}_2$ gives the six covers $1342⋗1243$, $1342⋗1324$, $2143⋗1243$, $2143⋗2134$, $2314⋗1324$, $2314⋗2134$, and shows that the remaining three pairs of adjacent ranks are incomparable (for instance $2134\le ̸1342$, since $2134=s_1$ is not one of $e,s_2,s_3,s_2{s}_3$). Since every maximal chain of $[e,c]$ has $\mathrm{\ell }(c)-\mathrm{\ell }(e)=3$ steps [F11], the maximal chains are the paths of covers from $2341$ to $1234$, namely the six chains displayed in (ii).

The label words. At the first step the retained expression is $c=s_1{s}_2{s}_3$ and the deleted position is read off from the cover by [F5]: $2341⋗1342$ deletes position $1$, $2341⋗2143$ deletes position $2$, $2341⋗2314$ deletes position $3$. In the rooted intervals the retained expressions are $1342=s_2{s}_3$, $2143=s_1{s}_3$, $2314=s_1{s}_2$, with their original positions; deleting the letter $s_1$, $s_2$ or $s_3$ from such a retained word gives the corresponding atom, so the second and third labels are the original positions of the deleted letters. Reading the six chains of step 1.2 gives exactly the six words $(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$. These are pairwise distinct and, as the six permutations of $\{1,2,3\}$, exhaust all label words; the only strictly falling one is $(3,2,1)$, and $(1,2,3)$ is increasing.

The lexicographically first chain. By step 2.1 the six label words are distinct permutations of $\{1,2,3\}$, so the lexicographically first maximal chain is the one with word $(1,2,3)$, namely $2341⋗1342⋗1243⋗1234$, and this word is increasing; by [F7] the increasing maximal chain of $[e,c]$ is unique and lexicographically first, in agreement.

The local descent replacement. Consider the chain $m\text{\hspace{0.17em}⁣}:2341⋗1342⋗1324⋗1234$, whose word $(1,3,2)$ has its descent at position $2$. Its part above $m_1=1342$ is the single cover $2341⋗1342$, and the rooted rank-two interval $([m_3,m_1],c_m)=([1234,1342],2341⋗1342)$ has retained expression $s_2{s}_3$, with the two maximal chains $1342⋗1324⋗1234$ and $1342⋗1243⋗1234$ and label words $(3,2)$ and $(2,3)$, by [F8] and step 2.1 (the words are computed from the retained expression with its original positions $2,3$). The second chain is the unique increasing one, so replacing the falling segment by it gives the maximal chain $2341⋗1342⋗1243⋗1234$ with word $(1,2,3)\prec (1,3,2)$, which is the lexicographically first chain of step 3.1; this is the instance for $e=2$ of the local descent replacement [F9], and it agrees with the earlier/later comparison [F10] with $m^{\mathrm{\prime }}$ the lexicographically first chain, for which $m^{\mathrm{\prime }}\cap m=\{2341,1342,1234\}$, $\mathrm{\mid }{m}^{\mathrm{\prime }}\cap m\mathrm{\mid }=3=\mathrm{\mid }m\mathrm{\mid }-1$ and $\lambda (m^{\mathrm{\prime }})\prec \lambda (m)$.

The eight elements and the twelve covers. The word $s_1{s}_2{s}_3$ is reduced and its subword products are $1234,2134,1324,1243,2314,2143,1342,2341$, each reduced of its number of letters because its inversion number equals its length [F3]; by [F1] these are exactly the elements of $[e,c]$, of ranks $0,1,1,1,2,2,2,3$. By [F2] the elements covered by $c$ are the single-letter deletions of $s_1{s}_2{s}_3$ whose remaining word is reduced, namely $s_2{s}_3=1342$, $s_1{s}_3=2143$, $s_1{s}_2=2314$, the three elements of length $2$; each atom covers $e$; and for a length-two element $x=t_i{t}_j$ the subword products of the reduced word $t_i{t}_j$ are exactly $e,t_i,t_j,x$, so the atoms below $x$ are $t_i$ and $t_j$ and every other adjacent-rank pair involving $x$ is incomparable, which yields the six covers $1342⋗1243$, $1342⋗1324$, $2143⋗1243$, $2143⋗2134$, $2314⋗1324$, $2314⋗2134$. This is the same twelve-cover diagram used for the label words below, and by [F12] every maximal chain of $[e,c]$ has three steps.

The atoms. By step 1.1 the three atoms $2134,1324,1243$ cover $e$ and have nothing strictly between, so the recurrence [F4] gives $\mu (e,s)=-(\mu (e,e))=-1$ for each of them.

Parity balance. The lengths of the eight elements are $0,1,1,1,2,2,2,3$ [F3], so four elements have even and four have odd length and ${\sum }_{x\in [e,c]}(-1{)}^{\mathrm{\ell }(x)}=4-4=0$, as required by the parity-balance statement [F8]; the count is a cardinality of a finite set [F11].

The rank-two elements. By step 1.1 the elements of $[e,x]$ other than $x$ are exactly $e$ and the two atoms it covers, so the recurrence [F4] gives $\mu (e,x)=-(1-1-1)=1$ for $x=1342,2143,2314$.

The top value. The elements of $[e,c]$ other than $c$ are $e$, the three rank-one elements and the three rank-two elements, so the recurrence [F4] gives $\mu (e,c)=-(1+3\cdot (-1)+3\cdot 1)=-(1-3+3)=-1$, which equals $(-1{)}^{\mathrm{\ell }(c)-\mathrm{\ell }(e)}=(-1{)}^3$ by [F3] and agrees with the sign formula [F7].

The falling-chain check. Reading off deletions from the cover diagram of step 1.1 with the recursion [F5] gives the six label words $(1,2,3)$ and $(1,3,2)$ for the chains through $1342$, $(2,1,3)$ and $(2,3,1)$ for those through $2143$, and $(3,1,2)$ and $(3,2,1)$ for those through $2314$; since these are the six permutations of $\{1,2,3\}$, exactly one maximal chain has a strictly falling word [F6], namely $2341⋗2314⋗2134⋗1234$ with word $(3,2,1)$. By [F9] the deleted-position labeling satisfies (N) and (L) on every rooted interval and by [F12] the interval $[e,c]$ is finite and graded, so the falling-chain formula [F10] applies and gives $\mu (e,c)=(-1{)}^{\mathrm{\ell }(c)-\mathrm{\ell }(e)}\cdot 1=-1$, consistent with step 4.1 and with the count-one clause of [F7].

Conclusion. Steps 4.1, 2.2 and 5.1 compute $\mu (1234,2341)=-1=(-1{)}^3$ from the recurrence and confirm the two independent checks of the Eulerian theorem: the equal numbers of even and odd elements [F8] and the single strictly falling maximal chain [F10].

The quotient interval. By [F1] an element $w$ lies in $W^I$ exactly when neither $s_1$ nor $s_3$ is a right descent of $w$, that is, when $\mathrm{\ell }(w{s}_1)>\mathrm{\ell }(w)$ and $\mathrm{\ell }(w{s}_3)>\mathrm{\ell }(w)$; since right multiplication by $s_i$ swaps the entries in positions $i$ and $i+1$ of the one-line form, this says $w(1)<w(2)$ and $w(3)<w(4)$. Testing the $24$ elements of $S_4$ leaves exactly $W^I=\{1234,1324,1423,2314,2413,3412\}$, of lengths $0,1,2,2,3,4$ by [F4]; in particular $3412$ is the unique element of $W^I$ of length $4$.

The covers. By [F2] the order on $W^I$ is the restriction of the Bruhat order, and two elements of $W^I$ whose lengths differ by one form a cover exactly when they are comparable; the adjacent length pairs in $W^I$ are only the pairs $\{1234,1324\}$, $\{1324,1423\}$, $\{1324,2314\}$, $\{1423,2413\}$, $\{2314,2413\}$ and $\{2413,3412\}$, because $W^I$ has exactly one element of length $0$ and of length $1$, two of length $2$, and one of length $3$ and of length $4$. Each of these six pairs is comparable, as the subword criterion [F3] shows with the reduced expressions $1324=s_2$, $1423=s_3{s}_2$, $2314=s_1{s}_2$, $2413=s_1{s}_3{s}_2$ and $3412=s_2{s}_1{s}_3{s}_2$: the subwords $s_2\le s_3{s}_2$, $s_2\le s_1{s}_2$, $s_3{s}_2\le s_1{s}_3{s}_2$, $s_1{s}_2\le s_1{s}_3{s}_2$ and $s_1{s}_3{s}_2\le s_2{s}_1{s}_3{s}_2$ exhibit the five comparabilities above the bottom, and $1234\le 1324$ is the empty subword. Hence the covers inside $W^I$ are exactly $1234⋖1324$, $1324⋖1423$, $1324⋖2314$, $1423⋖2413$, $2314⋖2413$ and $2413⋖3412$, and these covers chain every element of $W^I$ below $3412$; so $3412$ is the greatest element of $W^I$ and the quotient interval $[1234,3412{]}^I=[1234,3412]\cap W^I$ has exactly these six elements.

The fullness failure. The element $1432$ of $S_4$ satisfies $1432\mathrm{\notin }{W}^I$ because $\mathrm{\ell }(1432s_3)=\mathrm{\ell }(1423)=2<3=\mathrm{\ell }(1432)$ [F4], while $1432\le 3412$ in the full Bruhat order: $3412=s_2{s}_1{s}_3{s}_2$ is a reduced expression (its length $4$ equals the inversion number of $3412$) and $1432=s_2{s}_3{s}_2$ is the product of its subword at positions $1,3,4$ [F3]. Hence $1432\in [1234,3412]\setminus [1234,3412{]}^I$, the quotient interval is a proper subset of the full interval $[1234,3412]$, and the fullness hypothesis fails for it.

The Möbius values. With the recurrence [F5] and the cover list of step 2.1: $\mu (1234,1234)=1$ and $\mu (1234,1324)=-1$ (the atom covers the bottom); $\mu (1234,1423)=-(\mu (1234,1234)+\mu (1234,1324))=-(1-1)=0$ and likewise $\mu (1234,2314)=0$ (each has exactly the two displayed elements below it in the quotient interval); $\mu (1234,2413)=-(1-1+0+0)=0$; and finally $\mu (1234,3412)=-(1-1+0+0+0)=0$.

The refutation. By step 3.1 the induced quotient interval has $\mu (1234,3412)=0$, whereas $(-1{)}^{\mathrm{\ell }(3412)-\mathrm{\ell }(1234)}=(-1{)}^4=1$ by [F4]; so the indiscriminate Eulerian claim displayed above is false for this $I$ and this interval. The exact dropped hypothesis is fullness of the interval: step 2.2 shows $[1234,3412{]}^I⊊[1234,3412]$, and for full intervals the sign formula holds by [F6]. This is why the theorem restricts its scope in [F7].