On The Computation Of Kazhdan-Lusztig R-polynomials Of The Symmetric Group

The main results of this thesis are some progress on the computation of KazhdanLusztig R-polynomials of the symmetric group. We calculate ordinary generating func-tions of R-polynomials indexed by permutations u, v, where v is obtained from u byapplying two crossed transpositions, two nested transpositions or three nested transpo-sitions. Since the R-polynomials are equivalent to the R-polynomials, we only concernthe R-polynomials.In Chapter1, after giving a background on the Kazhdan-Lusztig theory, we intro-duce the notation and recall some preliminary results on Coxeter systems and Kazhdan-Lusztig theory. The Coxeter system of the symmetric group is discussed in some detail.Then we make a survey of the computation of R-polynomials, both for general Coxetergroups and for the symmetric group. Two directions are reviewed: combinatorial inter-pretations and explicit formulas of the R-polynomials. Finally, we present our work onthe computation of R-polynomials of the symmetric group.In Chapter2, we compute the R-polynomials R_u, v（q）, where v is obtained from uby applying two crossed transpositions. That is, v=u（i, j）（k, l） and uiukujulis an in-creasing subsequence of u. The idea is to calculate the ordinary generating function ofM_n（q）=Re,（1,n1）（2,n）（q） first, and then express R_u, v（q） in terms of M_n（q）. The compu-tation of M_n（q） requires another class of R-polynomials Nn（q）=R（n1,n）,（1,n1）（2,n）（q）.We find a system of linear recurrence relations of M_n（q） and Nn（q） and then obtain theirordinary generating functions by solving this linear system. To prove our main result,we introduce two operators L and R on permutations, which will also be used in theproofs of the main results of the rest chapters.In Chapter3, we calculate the R-polynomials R_u, v（q）, where v is obtained fromu by applying two nested transpositions. That is, v=u（i, j）（k, l） and uiukulujis anincreasing subsequence of u. Using the operators L and R defined in Chapter2, wecan reduce the calculation to the determination of P_n（q）=Re,（1,n）（2,n1）（q）. We usetwo methods to compute the ordinary generating function of P_n（q）. One direct method is to introduce the R-polynomials Q_n（q）=R（n1,n）,（1,n）（2,n1）（q）, and find a system oflinear recurrence relations of P_n（q） and Q_n（q）. The other method is a little complicated,but along the way we get many interesting by-products.In Chapter4, we consider the R-polynomials R_u, v（q）, where v is obtained from uby applying three nested transpositions. That is, v=u（i₁, j₁）（i₂, j₂）（i₃, j₃） and u hasan increasing subsquence ui₁ui₂ui₃uj₃uj₂uj₁. The outline is to compute the ordinarygenerating function of Re,（1,n）（2,n1）（3,n2）（q） first, and then determine the bivariateordinary generating function of Re,（1,n）（2,n1）（3,n r2）（q） where0≤r≤n6. Finally,we express R_u, v（q） in terms of Re,（1,n）（2,n1）（3,n r2）（q）. We also use two differentmethods to calculate the ordinary generating function of Re,（1,n）（2,n1）（3,n2）（q）.In Chapter5, we compute the R-polynomials R_u, v（q）, where v is obtained from uby applying three nested transpositions, namely, v=u（i₁, j₁）（i₂, j₂）（i₃, j₃） withi₁<i₂<i₃<j₃<j₂<j₁and ui₁<ui₂<uj₃<ui₃<uj₂<uj₁.The strategy is to calculate the explicit formula of R（3,n2）,（1,n）（2,n1）（q） first, then ex-press R_u, v（q） in terms of R（3,n r2）,（1,n）（2,n1）（q） where0≤r≤n6, whose bivariateordinary generating function can be computed beforehand. Explicit formulas of theR-polynomials R（3,n1）,（1,n）（2,n1）（q）, R（3,n）,（1,n）（2,n1）（q）,R（3,n1,n）,（1,n）（2,n1）（q） and R（3,n2）（n1,n）,（1,n）（2,n1）（q） are also obtained.