Computing individual Kazhdan–Lusztig basis elements. (March 2016)

• Record Type: Journal Article
• Authors: Scott, Leonard L.; Sprowl, Timothy
• Is Part Of: Journal of symbolic computation. Volume 73(2016)
• Page Start: 244
• Page End: 249
• Publication Date: 2016-03
• Subjects: 20G05; Kazhdan–Lusztig polynomials -- Avoiding recursion -- 1-cohomology; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.05.003
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: In well-known work, Kazhdan and Lusztig (1979) defined a new set of Hecke algebra basis elements (actually two such sets) associated to elements in any Coxeter group. Often these basis elements are computed by a standard recursive algorithm which, for Coxeter group elements of long length, generally involves computing most basis elements corresponding to Coxeter group elements of smaller length. Thus, many calculations simply compute all basis elements associated to a given length or less, even if the interest is in a specific Kazhdan–Lusztig basis element. Similar remarks apply to "parabolic" versions of these basis elements defined later byDeodhar (1987, 1990), though the lengths involved are the (smaller) lengths of distinguished coset representatives. We give an algorithm which targets any given Kazhdan–Lusztig basis element or parabolic analog and does not precompute any other Kazhdan–Lusztig basis elements. In particular it does not have to store them. This results in a considerable saving in memory usage, enabling new calculations in an important case (for finite and algebraic group 1-cohomology with irreducible coefficients) analyzed byScott–Xi (2010) .