The c-sortable subset of A3 for c = s1s2s3, a three-element fiber, and the upper endpoint map

Use $s_i=(ii+1)$ and right-to-left composition, as in [F1]-[F2]. In each table, a position list $P_d(w)$ is the set selected by the greedy scan of $d^{\mathrm{\infty }}$, and a block code such as $123\mid 12$ means the consecutive subsets $\{s_1,s_2,s_3\}\supseteq \{s_1,s_2\}$. The scan is the sorting word by [F4], so the displayed letters multiply to $w$ and determine its sortable status by [F5].

For $d=c=s_1{s}_2{s}_3$, the first twelve scan records are $(w,P_c(w),B_c(w))$: $\begin{array}{ccc}e& \mathrm{\varnothing }& \mathrm{\varnothing }\\ s_1& 1& 1\\ s_2& 2& 2\\ s_3& 3& 3\\ s_1{s}_2& 1,2& 12\\ s_1{s}_3& 1,3& 13\\ s_2{s}_1& 2,4& 2\mid 1\\ s_2{s}_3& 2,3& 23\\ s_3{s}_2& 3,5& 3\mid 2\\ s_1{s}_2{s}_1& 1,2,4& 12\mid 1\\ s_1{s}_2{s}_3& 1,2,3& 123\\ s_1{s}_3{s}_2& 1,3,5& 13\mid 2\end{array}$.

The remaining twelve scan records for $c$ are $(w,P_c(w),B_c(w))$: $\begin{array}{ccc}{s}_2{s}_1{s}_3& 2,3,4& 23\mid 1\\ s_2{s}_3{s}_2& 2,3,5& 23\mid 2\\ s_3{s}_2{s}_1& 3,5,7& 3\mid 2\mid 1\\ s_1{s}_2{s}_1{s}_3& 1,2,3,4& 123\mid 1\\ s_1{s}_2{s}_3{s}_2& 1,2,3,5& 123\mid 2\\ s_1{s}_3{s}_2{s}_1& 1,3,5,7& 13\mid 2\mid 1\\ s_2{s}_1{s}_3{s}_2& 2,3,4,5& 23\mid 12\\ s_2{s}_3{s}_2{s}_1& 2,3,5,7& 23\mid 2\mid 1\\ s_1{s}_2{s}_1{s}_3{s}_2& 1,2,3,4,5& 123\mid 12\\ s_1{s}_2{s}_3{s}_2{s}_1& 1,2,3,5,7& 123\mid 2\mid 1\\ s_2{s}_1{s}_3{s}_2{s}_1& 2,3,4,5,7& 23\mid 12\mid 1\\ w_0& 1,2,3,4,5,7& 123\mid 12\mid 1\end{array}$.

The weakly decreasing rows in the c-sorting tables above are exactly $e,s_1,s_2,s_3,s_1{s}_2,s_1{s}_3,s_2{s}_3,s_1{s}_2{s}_1,s_1{s}_2{s}_3,s_2{s}_3{s}_2,s_1{s}_2{s}_1{s}_3,s_1{s}_2{s}_3{s}_2,s_1{s}_2{s}_1{s}_3{s}_2,w_0$. The other ten rows fail respectively at $2\supseteq ̸1$, $3\supseteq ̸2$, $13\supseteq ̸2$, $23\supseteq ̸1$, $3\supseteq ̸2$, $13\supseteq ̸2$, $23\supseteq ̸12$, $2\supseteq ̸1$ in the last blocks of $23\mathrm{\mid }2\mathrm{\mid }1$, $2\supseteq ̸1$ in the last blocks of $123\mathrm{\mid }2\mathrm{\mid }1$, and $23\supseteq ̸12$. Since the tables contain 24 distinct reduced words and $\mathrm{\mid }{S}_4\mathrm{\mid }=24$, this proves (i).

For $d=c^{\mathrm{\prime }}=s_1{s}_3{s}_2$, the first twelve scan records are $(w,P_{c^{\mathrm{\prime }}}(w),B_{c^{\mathrm{\prime }}}(w))$: $\begin{array}{ccc}e& \mathrm{\varnothing }& \mathrm{\varnothing }\\ s_1& 1& 1\\ s_2& 3& 2\\ s_3& 2& 3\\ s_1{s}_2& 1,3& 12\\ s_1{s}_3& 1,2& 13\\ s_2{s}_3& 3,5& 2\mid 3\\ s_2{s}_1& 3,4& 2\mid 1\\ s_3{s}_2& 2,3& 23\\ s_1{s}_2{s}_1& 1,3,4& 12\mid 1\\ s_1{s}_2{s}_3& 1,3,5& 12\mid 3\\ s_1{s}_3{s}_2& 1,2,3& 123\end{array}$.

The remaining twelve scan records for $c^{\mathrm{\prime }}$ are $(w,P_{c^{\mathrm{\prime }}}(w),B_{c^{\mathrm{\prime }}}(w))$: $\begin{array}{ccc}{s}_2{s}_3{s}_2& 2,3,5& 23\mid 3\\ s_2{s}_1{s}_3& 3,4,5& 2\mid 13\\ s_1{s}_2{s}_1{s}_3& 1,3,4,5& 12\mid 13\\ s_1{s}_2{s}_3{s}_2& 1,2,3,5& 123\mid 3\\ s_2{s}_1{s}_3{s}_2& 3,4,5,6& 2\mid 123\\ s_1{s}_2{s}_1{s}_3{s}_2& 1,3,4,5,6& 12\mid 123\\ s_3{s}_2{s}_1& 2,3,4& 23\mid 1\\ s_2{s}_3{s}_2{s}_1& 2,3,4,5& 23\mid 13\\ s_1{s}_3{s}_2{s}_1& 1,2,3,4& 123\mid 1\\ s_1{s}_2{s}_3{s}_2{s}_1& 1,2,3,4,5& 123\mid 13\\ s_2{s}_1{s}_3{s}_2{s}_1& 2,3,4,5,6& 23\mid 123\\ w_0& 1,2,3,4,5,6& 123\mid 123\end{array}$.

The weakly decreasing rows in the c'-sorting tables above are exactly $e,s_1,s_2,s_3,s_3{s}_2,s_2{s}_3{s}_2,s_1{s}_3,s_1{s}_2,s_1{s}_3{s}_2,s_1{s}_2{s}_3{s}_2,s_1{s}_2{s}_1,s_1{s}_3{s}_2{s}_1,s_1{s}_2{s}_3{s}_2{s}_1,w_0$. The ten other rows fail at $2\supseteq ̸3$, $12\supseteq ̸3$, $2\supseteq ̸1$, $2\supseteq ̸13$, $12\supseteq ̸13$, $2\supseteq ̸123$, $12\supseteq ̸123$, $23\supseteq ̸1$, $23\supseteq ̸13$, and $23\supseteq ̸123$, respectively; hence $c^{\mathrm{\prime }}$ also has 14 sortable elements.

Write $D_i$ for a descent branch of [F6] at initial letter $s_i$ and $A_i(v)$ for an ascent branch whose $W_{S\setminus \{s_i\}}$-prefix is $v$; after $D_i$ rotate the word to $s_{i}c{s}_i$, and after $A_i(v)$ restrict it by deleting the initial $s_i$. Recursing through all inputs gives these image fibers (the indicated traces end at the base $e$): $\begin{array}{cll}{\pi }_c(w)& {\pi }_c^{-1}({\pi }_c(w))& \text{trace}\\ e& \{e\}& \text{base}\\ s_1& \{s_1\}& D_1\\ s_2& \{s_2,s_2{s}_1\}& A_1(s_2)D_2\\ s_3& \{s_3,s_3{s}_2,s_3{s}_2{s}_1\}& A_1(s_3)A_2(s_3)D_3\text{ for }{s}_3;A_1(s_3{s}_2)A_2(s_3)D_3\text{ for the other two}\\ s_1{s}_2& \{s_1{s}_2\}& D_1{D}_2\\ s_1{s}_3& \{s_1{s}_3,s_1{s}_3{s}_2,s_1{s}_3{s}_2{s}_1\}& D_1{A}_2(s_3)D_3\\ s_2{s}_3& \{s_2{s}_3,s_2{s}_1{s}_3,s_2{s}_1{s}_3{s}_2\}& A_1(s_2{s}_3)D_2{D}_3\\ s_1{s}_2{s}_1& \{s_1{s}_2{s}_1\}& D_1{D}_2{A}_3(s_1)D_1\\ s_1{s}_2{s}_3& \{s_1{s}_2{s}_3\}& D_1{D}_2{D}_3\\ s_2{s}_3{s}_2& \{s_2{s}_3{s}_2,s_2{s}_3{s}_2{s}_1,s_2{s}_1{s}_3{s}_2{s}_1\}& A_1(s_2{s}_3{s}_2)D_2{D}_3{D}_2\\ s_1{s}_2{s}_1{s}_3& \{s_1{s}_2{s}_1{s}_3\}& D_1{D}_2{D}_3{D}_1\\ s_1{s}_2{s}_3{s}_2& \{s_1{s}_2{s}_3{s}_2,s_1{s}_2{s}_3{s}_2{s}_1\}& D_1{D}_2{D}_3{A}_1(s_2)D_2\\ s_1{s}_2{s}_1{s}_3{s}_2& \{s_1{s}_2{s}_1{s}_3{s}_2\}& D_1{D}_2{D}_3{D}_1{D}_2\\ w_0& \{w_0\}& D_1{D}_2{D}_3{D}_1{D}_2{A}_3(s_1)D_1\end{array}$. The fibers are disjoint and their sizes sum to $24$, so the table is exhaustive and proves (ii).

In right weak order the nontrivial fiber chains are $s_2{<}_R{s}_2{s}_1$, $s_3{<}_R{s}_3{s}_2{<}_R{s}_3{s}_2{s}_1$, $s_1{s}_3{<}_R{s}_1{s}_3{s}_2{<}_R{s}_1{s}_3{s}_2{s}_1$, $s_2{s}_3{<}_R{s}_2{s}_1{s}_3{<}_R{s}_2{s}_1{s}_3{s}_2$, $s_2{s}_3{s}_2{<}_R{s}_2{s}_3{s}_2{s}_1{<}_R{s}_2{s}_1{s}_3{s}_2{s}_1$, and $s_1{s}_2{s}_3{s}_2{<}_R{s}_1{s}_2{s}_3{s}_2{s}_1$; successive quotients are simple generators with additive length. By [F8] each top is $u_c$ of the fiber image, giving exactly the endpoint values in (iii), and each displayed fiber is the interval between its bottom and top.

Put $x=s_3{s}_2{s}_1=[4,1,2,3]$ and $y=s_2{s}_3{s}_2=[1,4,3,2]$. To move $4$ from position $4$ to position $1$ in $x$ requires the adjacent swaps $s_3,s_2,s_1$ in that order, so this is its unique reduced word; $y$ is the longest element on positions $2,3,4$ and has the two reduced words $s_2{s}_3{s}_2$ and $s_3{s}_2{s}_3$. Their right weak-order prefixes intersect in $e,s_3,s_3{s}_2$, so $x\wedge y=s_3{s}_2$. The upper interval of $x$ is $\{x,x{s}_2,x{s}_3,x{s}_2{s}_3,x{s}_3{s}_2,x{s}_2{s}_3{s}_2\}=\{4123,4213,4132,4231,4312,4321\}$: $4123$ has right ascents $s_2,s_3$; $4213$ only $s_3$; $4132$ only $s_2$; $4231$ only $s_2$; $4312$ only $s_3$; and $4321$ none, and every upper element is reached by a sequence of such simple right ascents. For these six $q$, the data $(q,\mathrm{\ell }(q),y^{-1}q,\mathrm{\ell }(y^{-1}q))$ are $\begin{array}{cccc}4123& 3& 2143& 2\\ 4213& 4& 2413& 3\\ 4132& 4& 2134& 1\\ 4231& 5& 2431& 4\\ 4312& 5& 2314& 2\\ 4321& 6& 2341& 3\end{array}$. By [F7], $y{\le }_{R}q$ exactly when $\mathrm{\ell }(y^{-1}q)=\mathrm{\ell }(q)-3$, so the common upper bounds are exactly $4132,4312,4321$. Since the latter two are $4132s_2$ and $4132s_2{s}_3$, the least common upper bound is $x\vee y=s_2{s}_3{s}_2{s}_1$.

The projection table gives ${\pi }_c(x)=s_3$, ${\pi }_c(y)=s_2{s}_3{s}_2$, ${\pi }_c(x\wedge y)={\pi }_c(s_3{s}_2)=s_3$, and ${\pi }_c(x\vee y)={\pi }_c(s_2{s}_3{s}_2{s}_1)=s_2{s}_3{s}_2$. The same results are $s_3\wedge s_2{s}_3{s}_2=s_3$ and $s_3\vee s_2{s}_3{s}_2=s_2{s}_3{s}_2$ (use the reduced word $s_3{s}_2{s}_3$ for $s_2{s}_3{s}_2$). This verifies the two sample equalities in (iv); the universal identities there are [F9].

The complete $c^{\mathrm{\prime }}$ projection recursion table, in the same $D_i,A_i(v)$ notation, is $\begin{array}{cll}{\pi }_{c^{\mathrm{\prime }}}(w)& {\pi }_{c^{\mathrm{\prime }}}^{-1}({\pi }_{c^{\mathrm{\prime }}}(w))& \text{trace}\\ e& \{e\}& \text{base}\\ s_1& \{s_1\}& D_1\\ s_2& \{s_2,s_2{s}_1,s_2{s}_3,s_2{s}_1{s}_3,s_2{s}_1{s}_3{s}_2\}& A_1(s_2)A_3(s_2)D_2\text{ for the first two};A_1(s_2{s}_3)A_3(s_2)D_2\text{ for the last three}\\ s_3& \{s_3\}& A_1(s_3)D_3\\ s_1{s}_2& \{s_1{s}_2,s_1{s}_2{s}_3\}& D_1{A}_3(s_2)D_2\\ s_1{s}_3& \{s_1{s}_3\}& D_1{D}_3\\ s_3{s}_2& \{s_3{s}_2,s_3{s}_2{s}_1\}& A_1(s_3{s}_2)D_3{D}_2\\ s_1{s}_2{s}_1& \{s_1{s}_2{s}_1,s_1{s}_2{s}_1{s}_3,s_1{s}_2{s}_1{s}_3{s}_2\}& D_1{A}_3(s_2{s}_1)D_2{D}_1\\ s_1{s}_3{s}_2& \{s_1{s}_3{s}_2\}& D_1{D}_3{D}_2\\ s_2{s}_3{s}_2& \{s_2{s}_3{s}_2,s_2{s}_3{s}_2{s}_1,s_2{s}_1{s}_3{s}_2{s}_1\}& A_1(s_2{s}_3{s}_2)D_3{D}_2{D}_3\\ s_1{s}_2{s}_3{s}_2& \{s_1{s}_2{s}_3{s}_2\}& D_1{D}_3{D}_2{A}_1(s_3)D_3\\ s_1{s}_3{s}_2{s}_1& \{s_1{s}_3{s}_2{s}_1\}& D_1{D}_3{D}_2{D}_1\\ s_1{s}_2{s}_3{s}_2{s}_1& \{s_1{s}_2{s}_3{s}_2{s}_1\}& D_1{D}_3{D}_2{D}_1{D}_3\\ w_0& \{w_0\}& D_1{D}_3{D}_2{D}_1{D}_3{D}_2\end{array}$. Its disjoint preimages cover all $24$ inputs, and the $s_2$-row is exactly the five-element fiber in (v).

The $c^{\mathrm{\prime }}$-sorting tables show $14$ sortable elements, matching the $14$ in the $c$-sorting tables; the different sizes of the displayed $s_2$-fibers show the partitions differ. Every calculation is finite, with no selection from an arbitrary family, so no Choice is used.