An effective, algorithmic description of Kazhdan–Lusztig cells in infinite Coxeter groups

Kazhdan–Lusztig cells — the equivalence classes of the preorders that Kazhdan and Lusztig (1979) defined on a Coxeter group through its Hecke algebra and Kazhdan–Lusztig basis — are completely described for finite Coxeter groups and affine Weyl groups, and for a few special infinite families (right-angled, complete-graph, and rank-3 hyperbolic groups), but no effective description is known for a general infinite Coxeter group. The problem, articulated by the Belolipetsky–Gunnells program, is to give an explicit, effective, combinatorial or algorithmic description of the cell partition of an arbitrary infinite Coxeter group of finite rank: a decision procedure for the Kazhdan–Lusztig preorders and cell membership, or a finite, explicitly checkable set of local moves or equivalence relations that generate the same left, right, and two-sided cell partition, and a recursive enumeration of the set of distinguished involutions starting from the finite standard parabolic subgroups. A 2025 preprint of Chen and Hu establishes the existence of a bound on Lusztig's a-function for every positively weighted finite-rank Coxeter group — the foundational hypothesis of the theory, previously verified only case by case — but by a non-constructive, Ramsey-theoretic argument that yields no effective description. The problem in its natural generality remains open.

Background

A Coxeter group is a group $W$ with a finite generating set $S$ of involutions subject only to braid-type relations fixing the order $m_{st}\in\{2,3,\dots,\infty\}$ of each product $st$; the pair $(W,S)$ is a Coxeter system, its rank is $|S|$, and it is described combinatorially by its Coxeter graph with edge labels $m_{st}$. Finite Coxeter groups are the Weyl groups of Lie theory; affine Weyl groups (Coxeter groups acting discretely by translations and reflections on a Euclidean space) and hyperbolic Coxeter groups (those acting on a hyperbolic space with finite-volume fundamental domain) are the basic infinite examples, and a 'planar hyperbolic' Coxeter group is one acting on the hyperbolic plane with polygonal fundamental domain.

To any Coxeter system one associates its Hecke algebra $\mathcal H$, a one-parameter deformation of the group algebra of $W$ with basis $\{T_w\}_{w\in W}$ and quadratic relations $(T_s-v)(T_s+v^{-1})=0$ for $s\in S$. Kazhdan and Lusztig showed that $\mathcal H$ has a distinguished basis $\{c_w\}$, defined through the Kazhdan–Lusztig polynomials, and used its multiplication to define preorders $\le_L$, $\le_R$, and $\le_{LR}$ on $W$: roughly, $x\le_L y$ when the coefficient of the basis element $c_y$ in a certain product of $c_x$ with a generator is nonzero in top degree. The equivalence classes of these preorders are the left, right, and two-sided Kazhdan–Lusztig cells; they partition $W$, control representations of $\mathcal H$ (each left cell yields a 'cell representation'), and, in the Weyl-group and affine cases, encode deep representation-theoretic information such as unipotent characters. Writing $T_xT_y=\sum_z f_{x,y,z}T_z$, Lusztig's $a$-function is defined by the degree behavior of these structure constants ($a(z)$ is the smallest $a$ such that $v^{-a}f_{x,y,z}$ has no positive powers of $v$ for all $x,y$), and the structure constants $\gamma_{x,y,z}$ at the critical degree define the asymptotic Hecke algebra (the $J$-ring), a limit of $\mathcal H$ whose structure is governed by the cells. An involution $d\in W$ is a distinguished involution when it satisfies a maximality condition on these degrees (equivalently, a certain function $\Delta$ on it is extremal); each left cell contains exactly one distinguished involution, so the set $\mathcal D$ of distinguished involutions indexes the left cells. Lusztig's conjectures P1–P15 are a package of structural properties of the $a$-function, the cells, and the $J$-ring, whose availability for a class of Coxeter groups is the gateway to the whole asymptotic theory; they presuppose that the $a$-function is bounded on $W$.

For finite Coxeter groups and for affine Weyl groups the cell structure is classically known (Lusztig), and cells have been computed in further infinite families: right-angled Coxeter groups (all $m_{st}\in\{2,\infty\}$; Belolipetsky 2004), Coxeter groups with complete graph (all $m_{st}\ge 3$; Xie 2021 proved P1–P15 there), and all rank-3 hyperbolic Coxeter groups (Gao–Xie 2021 proved P1–P15 and described the $a$-function and cells). For a general infinite Coxeter group, however, the preorder is defined through infinitely many Kazhdan–Lusztig polynomials, and nothing effective is known. The state of the art before 2025 also lacked even the qualitative foundations: boundedness of the $a$-function — Lusztig's book conjectured that the maximum length of the longest element of a finite standard parabolic subgroup is a bound — was verified only for the families above. Belolipetsky and Gunnells ('Cells in Coxeter groups, I', J. Algebra 2013) launched a program to make the cell partition of an infinite Coxeter group effectively computable: they conjectured that $\mathcal D$ has a simple recursive structure and can be enumerated algorithmically starting from the distinguished involutions of the finite standard parabolic subgroups, and constructed, for each $d\in\mathcal D$, explicitly defined equivalence relations on $W$ that conjecturally determine the left (right) cell partition, proving their conjectures only in a special case. A companion direction (Belolipetsky–Gunnells–Scott 2014, building on Casselman's conjecture) asks automata-theoretically whether the set of reduced expressions of the elements of a cell forms a regular language (a language recognizable by a finite automaton); Brink and Howlett had shown the reduced-word language of the whole group is regular, and these authors gave a conjectural cell description for planar hyperbolic groups implying Casselman's conjecture there. In 2025, Chen and Hu proved that some bound on the structure-constant degrees (hence on the $a$-function) exists for every positively weighted Coxeter group of finite rank (a positive weight function, in Lusztig's sense, is a length-like function on $W$ that is constant on conjugacy classes of reflections and deforms the equal-parameter Hecke algebra), which — combined with Lusztig's monograph and the positivity theorem of Elias and Williamson — makes P1–P15 available in the equal-parameter case for all finite-rank Coxeter groups; but their proof runs through a non-constructive Ramsey-theoretic compactness argument and produces neither the conjectured sharp bound, nor any algorithm, nor a description of the cells. Rogel and Thiel (2023, revised 2026), motivated by the asymptotic Hecke category, note that no classification of the finite two-sided cells (or of the $H$-cells, the finer pieces of a two-sided cell meeting each pair of left/right cells) in infinite Coxeter groups is known, and they compute all finite two-sided cells of $a$-value at most 2 as the only general specimen.

Problem Statement

Let $(W,S)$ be an arbitrary infinite Coxeter group of finite rank, with Hecke algebra and Kazhdan–Lusztig basis as defined by Kazhdan–Lusztig. Give an explicit, effective, combinatorial or algorithmic description of the Kazhdan–Lusztig cell partition of $W$, comprising the following two scientifically linked targets:

(1) An effective description of the cell partition, given as a decision procedure — an algorithm that, given the Coxeter matrix of $(W,S)$ and words for elements $x,y\in W$, decides whether $x\le_L y$, $x\le_R y$, or $x\le_{LR}y$, and hence whether $x$ and $y$ lie in the same left, right, or two-sided cell — or as a finite, explicitly checkable set of local moves or equivalence relations, together with a proof that the equivalence relation it generates coincides with the Kazhdan–Lusztig cell equivalence relation $\sim_L$ (respectively $\sim_R$, $\sim_{LR}$), i.e., that it defines the same left, right, or two-sided cell partition.

(2) A recursive enumeration of the set $\mathcal D$ of distinguished involutions: the Belolipetsky–Gunnells conjecture asserts that $\mathcal D$ is generated by an explicit recursion starting from the distinguished involutions of the finite standard parabolic subgroups of $W$, so that $\mathcal D$ can be enumerated algorithmically; since each left cell contains a unique distinguished involution, this indexes the left cells. An effective enumeration of $\mathcal D$ is required, independently of the truth of the Belolipetsky–Gunnells conjecture.

The two targets are jointly posed: the effective description of the cell partition of (1) and the effective enumeration of $\mathcal D$ of (2).

The description must hold in the problem's natural generality — all infinite Coxeter systems of finite rank, with equal parameters unless an unequal-parameter scope is explicitly claimed as the derived variant; descriptions valid only for affine Weyl groups, right-angled, complete-graph, or rank-3 hyperbolic groups, or other proper special families do not answer the question. Purely qualitative existence results (such as boundedness of the $a$-function without an effective bound) likewise do not answer it.

References

1. David Kazhdan, George Lusztig, 'Representations of Coxeter groups and Hecke algebras', Inventiones Mathematicae 53 (1979) 165–184. DOI: 10.1007/BF01390031, https://doi.org/10.1007/BF01390031
2. Mikhail Belolipetsky, 'Cells and representations of right-angled Coxeter groups', Selecta Mathematica (New Series) 10 (2004) 325–339. DOI: 10.1007/s00029-004-0355-9, https://doi.org/10.1007/s00029-004-0355-9
3. Mikhail V. Belolipetsky, Paul E. Gunnells, 'Cells in Coxeter groups, I', Journal of Algebra 385 (2013) 134–144. arXiv:1012.0489, DOI: 10.1016/j.jalgebra.2013.03.016, https://arxiv.org/abs/1012.0489
4. Mikhail V. Belolipetsky, Paul E. Gunnells, Richard A. Scott, 'Kazhdan–Lusztig cells in planar hyperbolic Coxeter groups and automata', International Journal of Algebra and Computation 24 (2014) 757–772. arXiv:1212.3274, DOI: 10.1142/S0218196714500325, https://arxiv.org/abs/1212.3274
5. M. V. Belolipetsky, P. E. Gunnells, 'Kazhdan Lusztig Cells in Infinite Coxeter Groups', Journal of Generalized Lie Theory and Applications (2015), article S1-002. DOI: 10.4172/1736-4337.s1-002, https://doi.org/10.4172/1736-4337.s1-002
6. G. Lusztig, 'Hecke algebras with unequal parameters', CRM Monograph Series 18, American Mathematical Society (2003); updated version arXiv:math/0208154 (2014), https://arxiv.org/abs/math/0208154
7. G. Lusztig, 'Open problems on Iwahori–Hecke algebras', arXiv:2006.08535 (2020), https://arxiv.org/abs/2006.08535
8. Peipei Zhou, 'Lusztig's a-function for Coxeter groups of rank 3', Journal of Algebra 384 (2013) 169–193. DOI: 10.1016/j.jalgebra.2013.02.029, https://doi.org/10.1016/j.jalgebra.2013.02.029
9. Jianwei Gao, 'The lowest two-sided cell of weighted Coxeter groups of rank 3', arXiv:1901.00161 (2019), https://arxiv.org/abs/1901.00161
10. Jianwei Gao, Xun Xie, 'Conjectures P1–P15 for hyperbolic Coxeter groups of rank 3', Journal of Algebra 567 (2021) 139–195. arXiv:1906.09451, DOI: 10.1016/j.jalgebra.2020.09.020, https://arxiv.org/abs/1906.09451
11. Xun Xie, 'Conjectures P1-P15 for Coxeter groups with complete graph', Advances in Mathematics 379 (2021) 107565. arXiv:1903.00078, DOI: 10.1016/j.aim.2021.107565, https://arxiv.org/abs/1903.00078
12. Ben Elias, Geordie Williamson, 'The Hodge theory of Soergel bimodules', Annals of Mathematics (2) 180 (2014) 1089–1136. DOI: 10.4007/annals.2014.180.3.6, https://doi.org/10.4007/annals.2014.180.3.6
13. Hongsheng Hu, 'Representations of Coxeter groups of Lusztig's a-function value 1', arXiv:2309.00593 (2023, revised 2026), https://arxiv.org/abs/2309.00593
14. Xiaoyu Chen, Hongsheng Hu, 'The boundedness of Lusztig's a-function for Coxeter groups of finite rank', arXiv:2503.06432 (2025), https://arxiv.org/abs/2503.06432
15. Liam Rogel, Ulrich Thiel, 'The center of the asymptotic Hecke category and unipotent character sheaves', arXiv:2307.07276 (2023, revised 2026), https://arxiv.org/abs/2307.07276
16. J. Guilhot, E. Little, J. Parkinson, 'Bounded weight functions on regular languages and groups', arXiv:2510.17061 (2025), https://arxiv.org/abs/2510.17061