Combinatorial properties of the Kazhdan-Lusztig \(R\)-polynomials for \(S_ n\) (Q1354673)

In their fundamental paper [Invent. Math. 53, 165-184 (1979; Zbl 0499.20035)]=[KL] \textit{D. Kazhdan} and \textit{G. Lusztig} introduced two families of polynomials indexed by pairs of elements \(x\), \(y\) in a Coxeter group \(W\). The \(R\)-polynomial \(R_{x,y}(q)\in\mathbb{Z}[q]\) is defined using the Hecke algebra associated to \(W\): it is a normalisation of the coefficient of the standard basis element \(T_x\) in the expansion of the inverse of \(T_{y^{-1}}\). If \(x\leq y\) in the Bruhat order, then \(R_{x,y}(q)\) has degree \(l(y)-l(x)\), where \(l\) is the length function on \(W\), and \(R_{x,y}(q)=0\) otherwise. \textit{J. E. Humphreys} [Reflection groups and Coxeter groups (Cambridge Univ. Press 1990; Zbl 0725.20028), Chapter 7]=[H] provides an introduction to the \(R\)-polynomials and the important polynomials \(P_{x,y}(q)\) (the Kazhdan-Lusztig polynomials), which can be computed from them. The main result proved here is a recursion formula for the \(R\)-polynomials of the symmetric group \(S_n\). For \(\sigma,\tau\in S\), with \(\sigma<\tau\), this has the form \(R_{\sigma,\tau}(q)=\sum_wq^{n(w,\sigma)}(q-1)^{k(w)-1}R_{w\sigma,\tau}(q)\). Each element \(w\) appearing in the sum is a cyclic permutation of an increasing sequence of length \(k(w)\) in \(\sigma\), and the exponent \(n(w,\sigma)\) counts certain triples \(i<k<j\) with \(\sigma(i)<\sigma(k)<\sigma(j)\). This recurrence has advantages over the standard one (see [KL] or [H]) both for computation and for theoretical work: the first because it does not `branch' into subcases, the second because the permutation \(\tau\) is not changed. By `solving' the recurrence, a closed formula \(R_{\sigma,\tau}(q)=\sum_Cq^{a(C)}(q-1)^{b(C)}\) is obtained. Here the summation \(C\) is over certain ascending chains joining \(\sigma\) to \(\tau\) in the Bruhat order, and the integers \(a(C)\) and \(b(C)\) are such that \(2a(C)+b(C)=l(\tau)-l(\sigma)\) for each chain \(C\). This would appear to be related to Deodhar's formula [see \textit{V. V. Deodhar}, Invent. Math. 79, 499-511 (1985; Zbl 0563.14023), or [H], p. 154]. Applications to special cases of the \(R\)- and \(P\)-polynomials include sufficient conditions for a polynomial of either family to factor as a product of polynomials of the same family. In the case where the interval \([\sigma,\tau]\) between \(\sigma\) and \(\tau\) does not contain an interval isomorphic to \(S_3\), it is shown that \(R_{\sigma,\tau}(q)=(q-1)^{l(\sigma)-l(\tau)}\), and that \(P_{\sigma,\tau}(q)\) is the \(g\)-polynomial [see \textit{R. P. Stanley}, Adv. Stud. Pure Math. 11, 187-213 (1987; Zbl 0652.52007)] of the dual interval \([\sigma,\tau]^*\).