Kazhdan–Lusztig Bases, Polynomials, and Cells — Examples

Rank one. By [F1, F2], $\overline{H_{21}}=H_{21}+\alpha$ and $\overline{H_{\mathrm{i}\mathrm{d}}}=H_{\mathrm{i}\mathrm{d}}$; by [F7], this gives $r_{\mathrm{i}\mathrm{d},21}=\alpha =v-v^{-1}$. Since $\alpha +v^{-1}=v$, $C:=H_{21}+v{H}_{\mathrm{i}\mathrm{d}}$ is bar-fixed. It is triangular below $H_{21}$, so uniqueness [F3] gives $C_{21}=C$ and $C_{\mathrm{i}\mathrm{d}}=H_{\mathrm{i}\mathrm{d}}$. From $H_{21}^2=1-\alpha H_{21}$ in [F1], $C_{21}^2=(H_{21}+v{)}^2=1+(v+v^{-1})H_{21}+v^2=(v+v^{-1})(H_{21}+v)\mathrm{.}$ Its off-diagonal coefficient is $p_{\mathrm{i}\mathrm{d},21}=v$, so [F4] gives $P_{\mathrm{i}\mathrm{d},21}=1$ and $\mu (\mathrm{i}\mathrm{d},21)=1$.

Every bar image in $S_3$. Put $X=H_{213}$ and $Y=H_{132}$. The reduced words give $H_{231}=XY$, $H_{312}=YX$ and $H_{321}=YXY$. By [F1, F2], their bar images are computed by expanding $(X+\alpha )(Y+\alpha )$ and its reverse for the two length-two images, and $(Y+\alpha )(X+\alpha )(Y+\alpha )$ for the length-three word, replacing $Y^2$ by $1-\alpha Y$. The latter gives $H_{321}+\alpha (H_{231}+H_{312})+{\alpha }^2(X+Y)+({\alpha }^3+\alpha )H_{123}$. Since ${\alpha }^2=v^2-2+v^{-2}$ and ${\alpha }^3+\alpha =v^3-2v+2v^{-1}-v^{-3}$, these are exactly all the displayed bar images. Multiplicativity computes the images directly; it does not assert that $\overline{H_w}$ itself is bar-fixed.

The six KL elements. Put $A=X+v$ and $B=Y+v$. By [F1, F2], both are bar-fixed, and $AB=H_{231}+v(H_{213}+H_{132})+v^2{H}_{123},BA=H_{312}+v(H_{132}+H_{213})+v^2{H}_{123}\mathrm{.}$ A direct expansion gives $BAB=H_{321}+v(H_{231}+H_{312})+v^2{H}_{213}+(1+v^2)H_{132}+(v+v^3)H_{123},$ so subtracting $B=H_{132}+v{H}_{123}$ gives exactly the displayed $C_{321}$. Each of $1,A,B,AB,BA,BAB-B$ is bar-fixed and has top coefficient $1$ with lower coefficients in $v\mathbb{Z}[v]$; all lower indices are below its top by [F6]. Thus uniqueness [F3] identifies all six elements.

Polynomials and covers. Reading the expansions in step 1.3 gives $p_{y,w}=v^{\mathrm{\ell }(w)-\mathrm{\ell }(y)}$ for every $y\le w$, so [F4] gives $P_{y,w}=1$ and $\mu (y,w)=[v]p_{y,w}$ is $1$ exactly at length difference one. By the reduced-subword criterion [F6], the Bruhat ranks in $S_3$ are $\{123\}$, $\{132,213\}$, $\{231,312\}$, and $\{321\}$, and each element in one of these layers is below every element in the next layer. Hence the covers are precisely the two edges from $123$, the four edges from rank one to rank two, and the two edges into $321$; these are exactly the eight pairs listed. Grading rules out other covers.

The ascent multiplication check. The subword criterion [F6] gives $[\mathrm{i}\mathrm{d},231]=\{123,132,213,231\}$. Left $s_2$ sends $231$ to $321$, whereas it sends $132$ to $123$ and $213$ to $312$; thus among the strict lower indices only $132$ has a left $s_2$-descent. Step 2.1 gives $\mu (132,231)=1$, so [F5] yields $C_{132}{C}_{231}=C_{321}+C_{132}$. For comparison, left $s_1$ sends $231$ to $132<231$, and the descent formula gives $C_{213}{C}_{231}=(v+v^{-1})C_{231}$. The rank-one square was already proved in step 1.1.

The full interval. The displayed word for $w$ has inversion length $4$, so it is reduced. Its reduced subwords of lengths $0,1,2,3,4$ give respectively $1234$; $1324,2134,1243$; $1342,1423,2314,3124,2143$; $1432,2413,3142,3214$; and $3412$. The four excluded elements $1234,2134,1243,2143$ have no reduced subword $s_2$, so they are not above $b$; the other ten are. For an explicit order check, write $a=1342=s_2{s}_3$, $c=1423=s_3{s}_2$, $d=2314=s_1{s}_2$, $f=3124=s_2{s}_1$, and $A=1432=s_2{s}_3{s}_2$, $C=2413=s_1{s}_3{s}_2$, $D=3142=s_2{s}_1{s}_3$, $F=3214=s_2{s}_1{s}_2$. The reduced-subword criterion gives the intermediate covers $a<A,D$; $c<A,C$; $d<C,F$; $f<D,F$; each rank-two element is also above $b=s_2$, and each rank-three element is below $w$. These are all cover incidences between adjacent ranks, so all other comparisons are their transitive consequences.

The correction interval. Left $s_2$ gives $s_{2}w=2413$ and $s_{2}b=1234$. Step 1.1 gives $[b,2413]=\{b,1423,2314,2413\}$. Their left $s_2$ products are respectively $1234,1432,3214,3412$, of lengths $0,3,3,4$, whereas the original lengths are $1,2,2,3$. Thus only $b$ has that descent, and $\mu (b,2413)=0$ by its even length gap. In particular $1342$ is excluded: $R_{1342}(3,2)=1<2=R_{2413}(3,2)$.

All the $R$-coefficients. By [F9], noncomparable pairs have $r_{y,z}=0$, diagonal entries are $1$, and every comparable coefficient is nonzero because its leading term is $v^{\mathrm{\ell }(z)-\mathrm{\ell }(y)}$. For a cover, the degree range and parity in [F9] leave only the terms $v$ and $-v^{-1}$, so $r_{y,z}=\alpha$. For a comparable pair of gap two, induct on $\mathrm{\ell }(y)$ and choose a left descent $s$ of $z$. If $sy<y$, the recursion gives $r_{y,z}=r_{sy,sz}$; this coefficient is nonzero, so [F9] implies $sy\le sz$, and induction gives $r_{y,z}={\alpha }^2$. If $sy>y$, then $r_{sy,sz}=0$: its indices have equal length, and equality would force $y=z$. By the lifting implication in [F1], $y\le sz$, so the other recursion term is $\alpha r_{y,sz}={\alpha }^2$. Thus every gap-two pair in $S_4$ has coefficient ${\alpha }^2$. The only gap-three pair in $[b,w]$ is $(b,w)$. Since $s_2$ is a left descent of both, $r_{b,w}=r_{1234,2413}$. For $2413$, $s_1$ is a left descent, so $r_{1234,2413}=r_{2134,1423}+\alpha r_{1234,1423}$. The first term is zero because $1423=s_3{s}_2$ has no reduced subword $s_1$; the second is $\alpha \cdot {\alpha }^2$. Hence $r_{b,w}={\alpha }^3=v^3-3v+3v^{-1}-v^{-3}$. This determines every coefficient for pairs in the displayed interval.

The sole nonconstant polynomial. By [F3], all comparable pairs of gap at most two have $P=1$, so the only possibly nonconstant pair within the interval is $(b,w)$. To evaluate $P_{1234,2413}$, apply [F4] with left $s_1$ to $2413=s_1{s}_3{s}_2$, obtaining lower top $s_3{s}_2=1423$. No element below $1423$ has left $s_1$-descent: its subwords are $1234,1243,1324,1423$, with no inversion between the values $1,2$. Also $s_1\le ̸1423$. Hence $P_{1234,2413}=q{P}_{2134,1423}+P_{1234,1423}=0+1$. Now use [F4] at $(b,w,s_2)$: step 2.1 makes its correction sum empty, $c=1$, and $P_{b,2413}=1$, so $P_{b,w}=1+q$. Therefore $p_{b,w}=v^3+v$ and $\mu (b,w)=1$. Every other comparable distinct pair has $p_{y,z}=v^{\mathrm{\ell }(z)-\mathrm{\ell }(y)}$, so its nonzero $\mu$ occurs exactly on covers.

Inverse entries and both matrix products. Step 3.1 gives diagonal $p=1$, cover entries $v$, and gap-two entries $v^2$. Each gap-two interval in step 1.1 has two intermediate elements. Thus [F5] gives inverse entries $1,-v,v^2$ at gaps $0,1,2$. At the sole gap-three pair there are four elements at each intermediate rank, so $q_{b,w}^{\mathrm{\prime }}=-(v^3+v)-4(-v)v^2-4v^{2}v=-v^3-v$. This gives every entry of the inverse matrix, including every displayed value in part (d). For $Q^{\mathrm{\prime }}P$, the off-diagonal entries at gaps one and two are $-v+v=0$ and $v^2-2v^2+v^2=0$; at gap three the entry is $(v^3+v)-4v^3+4v^3-(v^3+v)=0$. For $P{Q}^{\mathrm{\prime }}$, these entries are $v-v=0$, $v^2-2v^2+v^2=0$, and $-(v^3+v)+4v^3-4v^3+(v^3+v)=0$. Diagonal entries are $1$ and noncomparable entries are zero by support, so both matrix products are the identity. Although all $p$-entries in this finite example are nonnegative, its cover inverse entries and $q_{b,w}^{\mathrm{\prime }}$ are negative. Every calculation is finite and uses no choice principle.

The six RSK pairs in $S_3$. Repeated insertion using [F1] gives $\begin{array}{ccc}w& P(w)& Q(w)\\ 123& [123]& [123]\\ 132& [12\mathrm{\mid }3]& [12\mathrm{\mid }3]\\ 213& [13\mathrm{\mid }2]& [13\mathrm{\mid }2]\\ 231& [13\mathrm{\mid }2]& [12\mathrm{\mid }3]\\ 312& [12\mathrm{\mid }3]& [13\mathrm{\mid }2]\\ 321& [1\mathrm{\mid }2\mathrm{\mid }3]& [1\mathrm{\mid }2\mathrm{\mid }3]\end{array}$. For example, $132$ inserts $1$, then appends $3$, then inserts $2$ in place of $3$ and bumps $3$ to a new second row; the third recording label is therefore in row two. The same leftmost-greater rule gives the other displayed pairs.

All RSK pairs in $S_4$, grouped by $Q$. Applying [F1] to each of the $24$ one-line words gives $\begin{array}{cl}\text{Q(w)}& \text{(w,P(w))}\\ \text{[1234]}& \text{(1234,[1234])}\\ \text{[12|34]}& \text{(2413,[13|24]),(3412,[12|34])}\\ \text{[123|4]}& \text{(1243,[123|4]),(1342,[124|3]),(2341,[134|2])}\\ \text{[124|3]}& \text{(1324,[124|3]),(1423,[123|4]),(2314,[134|2])}\\ \text{[13|24]}& \text{(2143,[13|24]),(3142,[12|34])}\\ \text{[134|2]}& \text{(2134,[134|2]),(3124,[124|3]),(4123,[123|4])}\\ \text{[12|3|4]}& \text{(1432,[12|3|4]),(2431,[13|2|4]),(3421,[14|2|3])}\\ \text{[13|2|4]}& \text{(3241,[14|2|3]),(4132,[12|3|4]),(4231,[13|2|4])}\\ \text{[14|2|3]}& \text{(3214,[14|2|3]),(4213,[13|2|4]),(4312,[12|3|4])}\\ \text{[1|2|3|4]}& \text{(4321,[1|2|3|4])}\end{array}$. As a nontrivial check on the convention, insertion of $2413$ first gives rows $[2,4]$, then bumps $2$ below when $1$ is inserted, and finally bumps $4$ below $3$; thus $P(2413)=[13\mathrm{\mid }24]$ and $Q(2413)=[12\mathrm{\mid }34]$.

Cells in $S_3$. By [F2] and step 1.1, grouping by equal $Q$ gives the four left fibers in part (b), grouping by equal $P$ gives the four right fibers, and grouping by the common shape gives the three two-sided fibers. The displayed RSK pairs contain all six permutations, so there are no omitted elements in any fiber.

Left cells in $S_4$. By [F2], each row label $Q$ in step 1.2 indexes exactly one left cell. The possible shapes of size four are $(4),(3,1),(2,2),(2,1,1),(1,1,1,1)$; their standard tableaux are respectively $[1234]$; $[123\mathrm{\mid }4],[124\mathrm{\mid }3],[134\mathrm{\mid }2]$; $[12\mathrm{\mid }34],[13\mathrm{\mid }24]$; $[12\mathrm{\mid }3\mathrm{\mid }4],[13\mathrm{\mid }2\mathrm{\mid }4],[14\mathrm{\mid }2\mathrm{\mid }3]$; and $[1\mathrm{\mid }2\mathrm{\mid }3\mathrm{\mid }4]$. These are exactly the ten distinct $Q$-labels in the table. The listed fibers contain $1+2+3+3+2+3+3+3+3+1=24$ permutations, so every element of $S_4$ occurs and the table proves part (c) and the claimed bijection.

Equal right descents do not determine the left cell. In one-line notation, $1324$ has length $1$ and right products $1324s_1=3124$, $1324s_2=1234$, $1324s_3=1342$ of lengths $2,0,2$. Thus $R(1324)=\{s_2\}$. The word $2413$ has length $3$ and right products $2413s_1=4213$, $2413s_2=2143$, $2413s_3=2431$ of lengths $4,2,4$, so $R(2413)=\{s_2\}$ as well. But step 1.2 gives $Q(1324)=[124\mathrm{\mid }3]\mathrm{\ne }[12\mathrm{\mid }34]=Q(2413)$, so [F2] places them in different left cells. This proves the counterexample while [F3] records that descent sets are constant within each left cell.