Parabolic recursions for Kazhdan–Lusztig polynomials and the hypercube decomposition

Abstract We employ general parabolic recursion methods to demonstrate the recently devised hypercube formula for Kazhdan-Lusztig polynomials of $$S_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> , and establish its generalization to the full setting of a finite Coxeter system through algebraic proof. We introduce procedures for positive decompositions of q -derived Kazhdan–Lusztig polynomials within this setting, that utilize classical Hecke algebra positivity phenomena of Dyer-Lehrer and Grojnowski–Haiman. This leads to a distinct algorithmic approach to the subject, based on induction from a parabolic subgroup. We propose suitable weak variants of the combinatorial invariance conjecture and verify their validity for permutation groups.