Robinson-Schensted correspondence and left cells (Q2741027)

The Robinson-Schensted correspondence associates with any permutation \(w\) of the symmetric group \(S_n\) a pair of standard tableaux \((P(w),Q(w))\) called, respectively, the P-symbol and Q-symbol of \(w\). The Kazhdan-Lusztig polynomials \(P_{y,w}(q)\in{\mathbb Z}[q]\), where \(y\leq w\) with respect to the Bruhat order in \(S_n\), are defined by the equations NEWLINE\[NEWLINEC_w=\sum_{y\leq w}(-1)^{l(w)-l(y)}q^{l(w)/2-l(y)}P_{y,w}(q^{-1})T_y =\sum_{y\leq w}(-1)^{l(w)-l(y)}q^{l(w)/2+l(y)}P_{y,w}(q)T^{-1}_{y^{-1}},NEWLINE\]NEWLINE \(P_{w,w}(q)=1\) and \(\text{deg}P_{y,w}(q)\leq (l(w)-l(y)-1)/2\) for \(y<w\). Here \(l(w)\) is the length of a reduced expression of \(w\) with respect to the transpositions \(s_i=(i,i+1)\) and \(T_y\) is the element of the Hecke algebra of \(S_n\) related with \(y\). Let \(\mu(y|w)\not=0\) mean that either \(y<w\) and the coefficient \(\mu(y,w)\) of \(q^{(l(w)-l(y)-1)/2}\) in \(P_{y,w}(q)\) is nonzero or \(\mu(w,y)\not=0\) and \(y>w\), and let \({\mathcal L}(w)=\{s_j\mid s_jw<w\}\). One defines \(y\leq_L w\) if there exists a sequence \(y=x_1,x_2,\ldots,x_r=w\) such that \({\mathcal L}(x_i)\not\subset {\mathcal L}(x_{i+1})\) and \(\mu(x_i|x_{i+1})\not=0\) for all \(i=1,2,\ldots,r-1\). The permutations \(y\) and \(w\) belong to the same left cell of \(S_n\) if both \(y\leq_L w\) and \(w\leq_L y\) hold. The theorem of Kazhdan-Lusztig states that two permutations \(y\) and \(w\) belong to the same left cell of \(S_n\) if and only if they share a common Q-symbol. This theorem is not explicitly stated in the text of \textit{D. Kazhdan} and \textit{G. Lusztig} [Invent. Math. 53, 165-184 (1979; Zbl 0499.20035)] but follows from there with some additional arguments from \textit{A. Joseph} [Lect. Notes Math. 587, 102-118 (1977; Zbl 0374.17004)]. The original proof of Kazhdan and Lusztig is quite complicated. There are other proofs; see \textit{A. M. Garsia} and \textit{T. J. McLarnan} [Adv. Math. 69, No. 1, 32-92 (1988; Zbl 0657.20014)] and \textit{D. Barbasch} and \textit{D. Vogan} [Math. Ann. 259, 153-199 (1982; Zbl 0489.22010)]. The first uses a lot of combinatorics of tableaux and the second is based on wave front sets. NEWLINENEWLINENEWLINEThe main purpose of the paper under review is to present a direct proof of the theorem of Kazhdan and Lusztig. It combines ideas of the proof of Garsia and McLarnan with arguments of Jantzen for the Joseph theorem; see \textit{J. C. Jantzen} [Einhüllende Algebren halbeinfacher Lie-Algebren (Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge, Bd. 3, Berlin etc.: Springer-Verlag) (1983; Zbl 0541.17001)]. The exposition is based on an earlier paper written in Japanese by \textit{S. Ariki} [Robinson-Schensted correspondence and left cells (RIMS kokyuroku 705, 1-27 (1989); English version in Tokyo: Kinokuniya Company Ltd. Adv. Stud. Pure Math. 28, 1-20 (2000; Zbl 0986.05097)] but the author adds some new arguments which allow to understand the result in the crystal base theory context. He also gives some bibliographical comments on non-direct proofs.NEWLINENEWLINEFor the entire collection see [Zbl 0963.00024].