Construction of arbitrary Kazhdan-Lusztig polynomials in symmetric groups

Abstract:

To each polynomial $P$ with integral nonnegative coefficients and constant term equal to $1$, of degree $d$, we associate a certain pair of elements $(y,w)$ in the symmetric group $S_n$, where $n = 1 + d + P(1)$, such that the Kazhdan-Lusztig polynomial $P_{y,w}$ equals $P$. This pair satisfies $\ell (w) - \ell (y) = 2d + P(1) - 1$, where $\ell (w)$ denotes the number of inversions of $w$.