On the combinatorial invariance of Kazhdan-Lusztig polynomials

In this paper, we solve the conjecture about the combinatorial invariance of Kazhdan-Lusztig polynomials for the first open cases, showing that it is true for intervals of length 5 and 6 in the symmetric group. We also obtain explicit formulas for the R-polynomials and for the Kazhdan-Lusztig polynomials associated with any interval of length 5 in any Coxeter group, showing in particular what they look like in the symmetric group.     

Relations between the Clausen and Kazhdan-Lusztig representations of the symmetric group

We use Kazhdan-Lusztig polynomials and subspaces of the polynomial ring C[x_1,1,…,x_n,n] to give a new construction of the Kazhdan-Lusztig representations of S_n. This construction produces exactly the same modules as those which Clausen constructed using a different basis in [M. Clausen, Multivariate polynomials, standard tableaux, and representations of symmetric groups, J. Symbolic Comput. (11), 5-6 (1991) 483-522. Invariant-theoretic algorithms in geometry (Minneapolis, MN, 1987)], and does not employ the Kazhdan-Lusztig preorders. We show that the two resulting matrix representations are related by a unitriangular transition matrix. This provides a C[x_1,1,…,x_n,n]-analog of results due to Garsia and McLarnan, and McDonough and Pallikaros, who related the Kazhdan-Lusztig representations to Young’s natural representations.     

Kazhdan-Lusztig Polynomials for 321-Hexagon-Avoiding Permutations

In (Deodhar, Geom. Dedicata, 36(1) (1990), 95–119), Deodhar proposes a combinatorial framework for determining the Kazhdan-Lusztig polynomials P _x , _w in the case where W is any Coxeter group. We explicitly describe the combinatorics in the case where (the symmetric group on n letters) and the permutation w is 321-hexagon-avoiding. Our formula can be expressed in terms of a simple statistic on all subexpressions of any fixed reduced expression for w. As a consequence of our results on Kazhdan-Lusztig polynomials, we show that the Poincaré polynomial of the intersection cohomology of the Schubert variety corresponding to w is (1+q) ^l(w) if and only if w is 321-hexagon-avoiding. We also give a sufficient condition for the Schubert variety X _w to have a small resolution. We conclude with a simple method for completely determining the singular locus of X _w when w is 321-hexagon-avoiding. The results extend easily to those Weyl groups whose Coxeter graphs have no branch points (B C _n , F ₄, G ₂).     

Generalized Jones traces and Kazhdan-Lusztig bases

We develop some applications of certain algebraic and combinatorial conditions on the elements of Coxeter groups, such as elementary proofs of the positivity of certain structure constants for the associated Kazhdan-Lusztig basis. We also explore some consequences of the existence of a Jones-type trace on the Hecke algebra of a Coxeter group, such as simple procedures for computing leading terms of certain Kazhdan-Lusztig polynomials.     

Diagram algebras, Hecke algebras and decomposition numbers at roots of unity

We prove that the cell modules of the affine Temperley-Lieb algebra have the same composition factors, when regarded as modules for the affine Hecke algebra of type A, as certain standard modules which are defined homologically. En route, we relate these to the cell modules of the Temperley-Lieb algebra of type B, which provides a connection between Temperley-Lieb algebras on n and n−1 strings. Applications include the explicit determination of some decomposition numbers of standard modules at roots of unity, which in turn has implications for certain Kazhdan-Lusztig polynomials associated with nilpotent orbit closures. The methods involve the study of the relationships among several algebras defined by concatenation of braid-like diagrams and between these and Hecke algebras. Connections are made with earlier work of Bernstein-Zelevinsky on the “generic case” and of Jones on link invariants.     

Deformed Kazhdan-Lusztig elements and Macdonald polynomials

We introduce deformations of Kazhdan-Lusztig elements and specialised non-symmetric Macdonald polynomials, both of which form a distinguished basis of the polynomial representation of a maximal parabolic subalgebra of the Hecke algebra. We give explicit integral formula for these polynomials, and explicitly describe the transition matrices between classes of polynomials. We further develop a combinatorial interpretation of homogeneous evaluations using an expansion in terms of Schubert polynomials in the deformation parameters.     

A finiteness theorem for W-graphs

A W-graph for a Coxeter group W is a combinatorial structure that encodes a module for the group algebra of W, or more generally, a module for the associated Iwahori–Hecke algebra. Of special interest are the W-graphs that encode the action of the Hecke algebra on its Kazhdan–Lusztig basis, as well as the action on individual cells. In previous work, we isolated a few basic features common to the W-graphs in Kazhdan–Lusztig theory and used these to define the class of “admissible” W-graphs. The main result of this paper resolves one of the basic question about admissible W-graphs: there are only finitely many admissible W-cells (i.e., strongly connected admissible W-graphs) for each finite Coxeter group W. Ultimately, the finiteness depends only on the fact that admissible W-graphs have nonnegative integer edge weights. Indeed, we formulate a much more general finiteness theorem for “cells” in finite-dimensional algebras which in turn is fundamentally a finiteness theorem for nonnegative integer matrices satisfying a polynomial identity.     

Quasisymmetric functions and Kazhdan-Lusztig polynomials

We associate a quasisymmetric function to any Bruhat interval in a general Coxeter group. This association can be seen to be a morphism of Hopf algebras to the subalgebra of all peak functions, leading to an extension of the cd-index of convex polytopes. We show how the Kazhdan-Lusztig polynomial of the Bruhat interval can be expressed in terms of this complete cd-index and otherwise explicit combinatorially defined polynomials. In particular, we obtain the simplest closed formula for the Kazhdan-Lusztig polynomials that holds in complete generality.     

More on the combinatorial invariance of Kazhdan-Lusztig polynomials

We prove that the Kazhdan-Lusztig polynomials are combinatorial invariants for intervals up to length 8 in Coxeter groups of type A and up to length 6 in Coxeter groups of type B and D. As a consequence of our methods, we also obtain a complete classification, up to isomorphism, of Bruhat intervals of length 7 in type A and of length 5 in types B and D, which are not lattices.     

Factoring Polynomials and the Knapsack Problem

For several decades the standard algorithm for factoring polynomials f with rational coefficients has been the Berlekamp-Zassenhaus algorithm. The complexity of this algorithm depends exponentially on n, where n is the number of modular factors of f. This exponential time complexity is due to a combinatorial problem: the problem of choosing the right subsets of these n factors. In this paper, this combinatorial problem is reduced to a type of Knapsack problem that can be solved with lattice reduction algorithms. The result is a practical algorithm that can factor polynomials that are far out of reach for previous algorithms. The presented solution to the combinatorial problem is different from previous lattice-based factorizers; these algorithms avoided the combinatorial problem by solving the entire factorization problem with lattice reduction. This led to lattices of large dimension and coefficients, and thus poor performance. This is why lattice-based algorithms, despite their polynomial time complexity, did not replace Berlekamp-Zassenhaus as the standard method. That is now changing; new versions of computer algebra systems such as Maple, Magma, NTL and Pari have already switched to the algorithm presented here.     

Quantum Brownian motion and generalizations of Hermite polynomials

We introduce new families of orthogonal polynomials H_D,n, motivated by the non-equilibrium evolution of a quantum Brownian particle (qBp). The H_D,n’s generalize non-trivially the standard Hermite polynomials, employed for classical Brownian motion. We treat several models (labelled by D) for a non-equilibrium qBp, by means of the Wigner function W, in the presence of a “heat bath” at thermal equilibrium, with and without ab initio friction. For long times (for a suitable class of initial conditions), the non-equilibrium Wigner function W should approach, in some sense, the (time-independent) equilibrium Wigner function W_eq,D, which describes the thermal equilibrium of the qBp with the “heat bath” and plays a central role. W_eq,D is chosen to be the weight function which orthogonalizes the H_D,n’s. New results on W_eq,D and on the H_D,n’s are reported. We justify the key role of the H_D,n’s as follows. Using the H_D,n’s, moments W_eq,D,n and W_n are introduced for W_eq,D and W, respectively. At equilibrium, all moments W_eq,D,n except the lowest one (W_eq,D,0) vanish identically. Off-equilibrium, one expects that, for long times (for suitable initial conditions): (i) all non-equilibrium moments W_n (except the lowest moment W₀), will approach zero, while (ii) the lowest non-equilibrium moment W₀ will tend to W_eq,D,0(≠0). To complete the justification, we outline how the approximate long-time non-equilibrium theories determined by W₀ for the different models (D) yield Smoluchowski equations and irreversible evolutions of the qBp towards thermal equilibrium.     

Explicit combinatorial interpretation of Kerov character polynomials as numbers of permutation factorizations

We find an explicit combinatorial interpretation of the coefficients of Kerov character polynomials which express the value of normalized irreducible characters of the symmetric groups S(n) in terms of free cumulants R₂,R₃,… of the corresponding Young diagram. Our interpretation is based on counting certain factorizations of a given permutation.     

Some non-trivial Kazhdan-Lusztig coefficients of an affine Weyl group of type _n

In this paper we show that the leading coeficient μ(y,w) of some Kazhdan-Lusztig polynomials Py,w with y,w in an affine Weyl group of type n is n + 2.This fact has some consequences on the dimension of first extension groups of finite groups of Lie type with irreducible coefficients.     

Non-negative Spectral Measures and Representations of C*-Algebras

Regular normalized W-valued spectral measures on a compact Hausdorff space X are in one-to-one correspondence with unital *-representations ${\rho : C(X, \mathbb{C}) \to W}$ , where W stands for a von Neumann algebra. In this paper we show that for every compact Hausdorff space X and every von Neumann algebras W ₁, W ₂ there is a one-to-one correspondence between unital *-representations ${\rho : C(X, W_1) \to W_2}$ and special B(W ₁, W ₂)-valued measures on X that we call non-negative spectral measures. Such measures are special cases of non-negative measures that we introduced in our previous paper (Cimpri? and Zalar, J Math Anal Appl 401:307–316, 2013) in connection with moment problems for operator polynomials.     

Some polynomials associated with the $${\vavec{}}$$-Whitney numbes

In the present article, we study three families of polynomials associated with the r-Whitney numbers of the second kind. They are the r-Dowling polynomials, r-Whitney–Fubini polynomials and the r-Eulerian–Fubini polynomials. Then we derive several combinatorial results by using algebraic arguments (Rota’s method), combinatorial arguments (set partitions) and asymptotic methods.     

Cambrian lattices

For an arbitrary finite Coxeter group W, we define the family of Cambrian lattices for W as quotients of the weak order on W with respect to certain lattice congruences. We associate to each Cambrian lattice a complete fan, which we conjecture is the normal fan of a polytope combinatorially isomorphic to the generalized associahedron for W. In types A and B we obtain, by means of a fiber-polytope construction, combinatorial realizations of the Cambrian lattices in terms of triangulations and in terms of permutations. Using this combinatorial information, we prove in types A and B that the Cambrian fans are combinatorially isomorphic to the normal fans of the generalized associahedra and that one of the Cambrian fans is linearly isomorphic to Fomin and Zelevinsky's construction of the normal fan as a “cluster fan.” Our construction does not require a crystallographic Coxeter group and therefore suggests a definition, at least on the level of cellular spheres, of a generalized associahedron for any finite Coxeter group. The Tamari lattice is one of the Cambrian lattices of type A, and two “Tamari” lattices in type B are identified and characterized in terms of signed pattern avoidance. We also show that open intervals in Cambrian lattices are either contractible or homotopy equivalent to spheres.     

Reversion of power series and the extended Raney coefficients

In direct as well as diagonal reversion of a system of power series, the reversion coefficients may be expressed as polynomials in the coefficients of the original power series. These polynomials have coefficients which are natural numbers (Raney coefficients). We provide a combinatorial interpretation for Raney coefficients. Specifically, each such coefficient counts a certain collection of ordered colored trees. We also provide a simple determinantal formula for Raney coefficients which involves multinomial coefficients.