On involutions in symmetric groups and a conjecture of Lusztig

Let (W,S)(W,S) be a Coxeter system equipped with a fixed automorphism ⁎ of order ≤2 which preserves S  . Lusztig (and with Vogan in some special cases) have shown that the space spanned by set of “twisted” involutions (i.e., elements w∈Ww∈W with w⁎=w−1w⁎=w−1) was naturally endowed with a module structure of the Hecke algebra of (W,S)(W,S) with two distinguished bases, which can be viewed as twisted analogues of the well-known standard basis and Kazhdan–Lusztig basis. The transition matrix between these bases defines a family of polynomials Py,wσ which can be viewed as “twisted” analogues of the well-known Kazhdan–Lusztig polynomials of (W,S)(W,S). Lusztig has conjectured that this module is isomorphic to the right ideal of the Hecke algebra (with Hecke parameter u2u2) associated to (W,S)(W,S) generated by the element X∅:=∑w⁎=wu−ℓ(w)TwX∅:=∑w⁎=wu−ℓ(w)Tw. In this paper we prove this conjecture in the case when ⁎=id⁎=id and W=SnW=Sn (the symmetric group on n letters). Our methods are expected to be generalised to all the other finite crystallographic Coxeter groups.