CELLS AND REPRESENTATIONS OF RIGHT-ANGLED COXETER GROUPS

MIKHAIL BELOLIPETSKY

Abstract. We study Kazhdan-Lusztig cells and the corresponding representations of right-angled Coxeter groups and Hecke algebras associated to them. In case of the infinite groups generated by reflections in the hyperbolic plane about the sides of right-angled polygons we obtain an explicit description of the left and two-sided cells. In particular, we prove that there are infinitely many left cells but they all form only three two-sided cells.

1. Introduction

A Coxeter group is said to be right-angled if for any two distinct simple reflections their product has order 2 or ∞. Due to their special properties and rich structure right-angled Coxeter groups often arise in different geometric and algebraic problems. In a sense, the most interesting right-angled Coxeter groups are those which can be presented as groups generated by reflections in hyperbolic spaces. Examples of geometric applications of such groups can be found in [D], [MV], [BGI]. These groups also occur as Weyl groups of certain Kac-Moody Lie algebras [KP]. We are interested in the representations of right-angled Coxeter groups W and the corresponding Hecke algebras H.

An important difference between hyperbolic reflection groups and affine or finite Coxeter groups is that the former do not usually have a local system of generators in the sense of [OV]. In particular, the groups P_{n} (see 3.1), that are generated by reflections in the hyperbolic plane about the sides of right-angled n-gons can be called anti-local since only adjacent generators in the canonical system of simple reflections commute. This means that we can hardly hope to construct the representations of these groups inductively using the approach suggested in [OV]. At the same time, we can still use the global methods of [KL] and try to describe the Kazhdan-Lusztig cells in our groups. It appears that certain symmetries of the initial groups are reflected in the structure of the partitions into cells making the cells trackable. Our main results concern the groups P_{n} but the methods can be applied to the other right-angled Coxeter groups as well.

We show that the partition of the group P_{n} (n ≥ 5) into left cells consists of infinitely many elements and give an explicit description of the cells. At the same time, all the left cells in our groups form precisely three two-sided cells (one of which is, of course, the trivial cell). It was first shown in [B] that the number of one-sided cells of a hyperbolic Coxeter group can be infinite, but there the author used an implicit argument and obtained only a conjectural structure of the corresponding cell-partitions (see also [C] for discussion). The fact that infinitely many left cells can still fall into finitely many two-sided equivalence classes and hence give rise to only finitely many H-bimodules seems have been previously unnoticed.

1991 Mathematics Subject Classification. Primary 20G05; Secondary 20F55; 17B67.

The explicit description of the cells makes it possible to consider corresponding representations of the Coxeter groups and their Hecke algebras. Here we only start the related analysis leaving more detailed considerations for the future. We discuss the representations using W -graphs which were also introduced in [KL].

While working on this paper, I enjoyed the hospitality of the MPIM in Bonn. I wish to thank A. Vershik for several helpful discussions. V. Ostrik read an early version of the paper and gave me some important suggestions. Finally I am grateful to W. Casselman for his response on my submission to arXiv and lots of email conversations.

2. Preliminaries

We recall some well-known facts about Coxeter groups and Hecke algebras associated with them. The basic reference is the fundamental paper [KL]. All the material cited here can be also found in the book [H].

2.1. Let W be a Coxeter group and let S be the corresponding set of simple reflections. With some ambiguity of language we shall also call by Coxeter group the Coxeter system (W, S). The Hecke algebra H over the ring A = ℤ[q^{1/2}, q^{−1/2}] of Laurent polynomials in q^{1/2} is defined as follows. As an A-module, H is free with basis T_{w} (w ∈ W), the multiplication is defined by

T_{w}T_{w′} = T_{ww′}, if l(ww′) = l(w) + l(w′),
T_{s}^{2} = q + (q − 1)T_{s}, if s ∈ S,

where l(w) is the length of w in (W, S).

It will be also convenient to define

T̃_{w} = q^{−l(w)/2}T_{w}.

2.2. Let a → \overline{a} be the involution of the ring A defined by \overline{q^{1/2}} = q^{−1/2}. This extends to an involution h → \overline{h} of the ring H given by

\overline{∑ a_{w}T_{w}} = ∑ \overline{a}_{w}T_{w}^{−1}.

Let ≤ be the Bruhat order on W (see [H], Ch. 5.9). Denote, as usual, q_{w} = q^{l(w)}, ϵ_{w} = (−1)^{l(w)} for all w ∈ W. In [KL] it was shown that for any w ∈ W there exists a unique element element C_{w} ∈ H such that

\overline{C}_{w} = C_{w},

C_{w} = ϵ_{w}q_{w}^{1/2} ∑_{y≤w} ϵ_{y}q_{y}^{−1}\overline{P_{y,w}}T_{y},

where P_{y,w} ∈ A is a polynomial in q of degree ≤ \frac{1}{2}(l(w) − l(y) − 1) for y < w, and P_{w,w} = 1.

Elements C_{w} form a basis (called C-basis) of H as an A-module. This basis and the polynomials P_{y,w} (called Kazhdan-Lusztig polynomials) turn out to be of fundamental interest in the representation theory of Coxeter groups and Hecke algebras.

2.3. Given y, w ∈ W, we write y ≺ w if y < w and P_{y,w} is a polynomial in q of degree exactly \frac{1}{2}(l(w) − l(y) − 1) (which is, of course, possible only if l(w) − l(y) is odd). In this case the coefficient of the highest power of q in P_{y,w} is denoted by μ(y, w). If w ≺ y we set μ(w, y) = μ(y, w), otherwise (if neither y ≺ w nor w ≺ y) let μ(y, w) = μ(w, y) = 0. We write y − w if μ(x, y) ≠ 0.

For any w ∈ W define subsets of S:

L(w) = {s ∈ S | sw < w}, R(w) = {s ∈ S | ws < w}.

Now define y ≤_{L} w to mean that there is a chain y = y_{0}, y_{1}, …, y_{n} = w such that y_{i} − y_{i+1} and L(y_{i}) ⊄ L(y_{i+1}) for 0 ≤ i < n. Similarly, say that y ≤_{R} w if y^{−1} ≤_{L} w^{−1}. Finally, define y ≤_{LR} w to mean that there exists a chain y = y_{0}, y_{1}, …, y_{n} = w such that for each i < n either y_{i} ≤_{L} y_{i+1} or y_{i} ≤_{R} y_{i+1}.

Let ∼_{L}, ∼_{R}, ∼_{LR} be the equivalence relations associated to the preorders ≤_{L}, ≤_{R}, ≤_{LR}, respectively. The corresponding equivalence classes are called left, right and two-sided cells of W.

2.4. We shall often make use of the following properties of the defined relations.

Lemma. Let x, y ∈ W and x < y.

(i) If there exists s ∈ S such that x < sx, sy < y, then x ≺ y if and only if y = sx.

(ii) If there exists s ∈ S such that x < xs, ys < y, then x ≺ y if and only if y = xs. Moreover, in each of the cases μ(x, y) = 1.

(This statement can be found in the proof of Theorem 1.3 in [KL], it follows from the formula for the action of the elements T_{s} on the basis {C_{w} | w ∈ W } of H and the definition of C_{w}.)

Corollary.

(i) If x ≤_{L} y, then R(x) ⊃ R(y). Hence, x ∼_{L} y implies R(x) = R(y). (ii) If x ≤_{R} y, then L(x) ⊃ L(y). Hence, x ∼_{R} y implies L(x) = L(y).

(To prove the corollary it is enough to consider the case x − y with L(x) ⊄ L(y), details can be found in [KL].)

2.5. The main purpose of the partition of a Coxeter group W into cells is that it gives rise to the representations of group W and its Hecke algebra H. It is convenient to describe these representations using W -graphs.

Let X be a set. Consider an oriented graph Γ whose set of vertices is X, for each x ∈ X there is assigned a subset I_{x} of S, and if I_{x} ⊄ I_{y} then there is an edge (x, y) ∈ X × X labeled with an integer μ(x, y). Graph Γ is called W -graph if map s → τ_{s}, such that

τ_{s}x = \{ \begin{matrix}−x, if x ∈ X, s ∈ I_{x}, \\ qx + q^{1/2} ∑_{y∈X, s∈I_{y}} μ(x, y)y, if x ∈ X, s ∉ I_{x}, \end{matrix}

defines a representation of H on the free A-module A(X).

In [KL] it was shown that X = W with I_{x} = L(x) and μ(x, y) defined by the polynomial P_{x,y} as in 2.3 gives a W -graph. Moreover, its full subgraphs corresponding to the left cells with the same sets I_{x} and the same function μ are W -graphs themselves. Finally, when W is a symmetric group S_{n} it was proved that all the irreducible representations of H are defined by the W -graphs associated to the left cells of W.

3. Right-angled Coxeter groups

3.1. Recall that Coxeter group (W, S) is called right-angled Coxeter group if for any s ≠ t in S the product st has order 2 or ∞. The Coxeter graph of W has only edges labeled via ∞ (see examples on Figure 1).

Figure 1. Coxeter graphs of the groups generated by reflections about the sides of a right-angled pentagon in the hyperbolic plane (the group P_{5}) and the regular right-angled dodecahedron in the hyperbolic 3-space.

The simplest example of a right-angled Coxeter group is the infinite dihedral group D_{∞} = < s_{1}, s_{2} | s_{1}^{2} = s_{2}^{2} = 1 >. We are mainly interested in right-angled Coxeter groups generated by reflections in the hyperbolic n-space. The important example for us are the groups P_{n} having representations

P_{n} = < s_{1}, s_{2}, …, s_{n} | s_{i}^{2} = 1, (s_{j}s_{j+1})^{2} = 1, (s_{n}s_{1})^{2} = 1 >

where i = 1, …, n; j = 1, … n − 1. If n ≥ 5 the group P_{n} can be presented as a group of isometries of the hyperbolic plane generated by reflections about the sides of a right-angled hyperbolic n-gon (for more information about this and other geometric facts mentioned here we refer the reader to [VS]).

3.2. If a Coxeter group (W, S) is presented by isometries of the hyperbolic space, then it gives rise to a tessellation of the space by the fundamental chambers of the group. The dual graph G of this tessellation endowed with the standard graph metric reflects the structure of the initial group: fixing a vertex e ∈ G which will correspond to the identity element of W and labelling all the edges with the corresponding simple reflections from S, we can associate to an element w ∈ W represented by a word on S a geodesic path starting from e in G. Two paths define the same element if and only if they have the same ends. Reduced expressions in W correspond to the shortest geodesics in G. The graph G is called Cayley graph of (W, S), this graph can be defined for an arbitrary group with a fixed system of generators.

3.3. Let (W, S) be an arbitrary Coxeter group. We call by lines elements w ∈ W that have unique reduced expressions. By a subword of a word s_{1}s_{2} … s_{n}, s_{i} ∈ S we mean any expression of the form s_{i}s_{i+1} … s_{j}, 1 ≤ i ≤ j ≤ n. Subword u of word w_{0}uw_{1} is called segment of the word and of the corresponding element w ∈ W, if u represents a maximal line such that any reduced expression of w has the form w′_{0}uw′_{1} with w_{0} = w′_{0}, w_{1} = w′_{1} as the elements of the group W (here “maximal” means that u is not contained in any other subword with the same properties).

Lines are exactly the unique shortest geodesics of Cayley graph that start from e. The same way, segments of w ∈ W correspond to the (maximal) geodesics of Cayley graph that are contained in any shortest geodesic corresponding to w. The only segment of a line is the line itself.

Let us give a characterization of the lines and segments in a right-angled Coxeter group.

Proposition. Let (W, S) be a right-angled Coxeter group. Then

(i) a word s_{1} … s_{k} represents a line in W if and only if for any i = 1, …, k − 1 the product s_{i}s_{i+1} has order ∞;

(ii) a subword u of w_{0}uw_{1} is a segment if and only if u gives a minimal line such that #R(w_{0}) ≠ 1 and #L(w_{1}) ≠ 1 (here “minimal” means that u does not contain any proper or empty subword with the same property).

(Proof easily follows from the definitions.)

4. Distinguished Involutions

We recall some definitions and results from [L2], [L3].

As in Section 2 we fix a Coxeter group (W, S) and denote by H the corresponding Hecke algebra over A = ℤ[q^{1/2}, q^{−1/2}]. For any x, y, z ∈ W define elements f_{x,y,z}, g_{x,y,z}, h_{x,y,z} in A so that:

T̃_{x}T̃_{y} = ∑_{z} f_{x,y,z}T̃_{z},
T̃_{x}C_{y} = ∑_{z} g_{x,y,z}C_{z},
C_{x}C_{y} = ∑_{z} h_{x,y,z}C_{z}.

4.1. Let A^{+} = ℤ[q^{1/2}]. To go further we need the following assumptions about the Coxeter group:

- (W, S) is crystallographic, which means that for any s ≠ t in S the product st has order 2, 3, 4, 6 or ∞;

- (W, S) is bounded, which means that there exists an integer N ≥ 0 such that q^{N/2}f_{x,y,z} ∈ A^{+} for all x, y, z ∈ W, or equivalently, q^{N/2}h_{x,y,z} ∈ A^{+} for all x, y, z ∈ W.

4.2. Right-angled Coxeter groups are crystallographic. We prove that they are bounded:

Lemma. If in right-angled Coxeter group (W, S) ts_{1} … s_{n} = t̂s_{1} … ŝ_{j} … s_{n} (t, s_{i} ∈ S, i = 1, …, n) then t = s_{j} and t commutes with s_{1}, …, s_{j−1}.

Proof. By [T] there is a sequence of elementary M-operations taking word ts_{1} … s_{n} to t̂s_{1} … ŝ_{j} … s_{n} (t, s_{i} ∈ S). In case of right-angled groups the operations are:

(i) ss → 1; (ii) st → ts

(s, t ∈ S). Both operations preserve parity of the number of a simple reflection occurrences in the word, which follows t = s_{j}. We shall prove that t commutes with s_{1}, …, s_{j−1} by induction on j. If j − 1 = 1 then we have ts_{1}t = s_{1}; ts_{1} = s_{1}t. Now, if ts_{1} … s_{n} is equivalent to t̂s_{1} … s_{j−1}t̂s_{j+1} … s_{n} and j > 2 then there is an Moperation which decreases the number of simple reflections between two t’s. It can be only an operation of type (ii), so t commutes with some s_{i} with i ∈ {1, …, j −1}. It follows by the induction hypothesis that t does also commute with the remaining s_{i}.

Theorem. Let (W, S) be a right-angled Coxeter group. Then it is bounded with N = max l(w_{0}^{S′}), where S′ runs through all subsets of S such that corresponding subgroup (W^{S′}, S′) is finite and w_{0}^{S′} denotes the longest element of W^{S′}.

Proof. Take arbitrary x, y ∈ W and let s_{k} … s_{1}, t_{1} … t_{n} be corresponding reduced expressions (s_{i}, t_{j} ∈ S, i = 1, …, k, j = 1, …, n). We have:

T̃_{x}T̃_{y} = T̃_{s_{k}} … T̃_{s_{1}} T̃_{y}.

If l(s_{1}y) = 1 + l(y) then T̃_{s_{1}} T̃_{y} = T̃_{s_{1}y}; otherwise, l(s_{1}y) = l(y) − 1 and T̃_{s_{1}} T̃_{y} = (q^{1/2} − q^{−1/2})T̃_{y} + T̃_{s_{1}y}.

Proceeding inductively we obtain (similarly to [L2]):

T̃_{x}T̃_{y} = ∑_{I}(q^{1/2} − q^{−1/2})^{p_{I}} T̃_{I}

where I ranges over all subsets i_{1} < ⋯ < i_{p_{I}} of {1, …, k} such that

s_{i_{l}} … ŝ_{i_{l−1}} … ŝ_{i_{1}} … s_{1}y < ŝ_{i_{l}} … ŝ_{i_{l−1}} … ŝ_{i_{1}} … s_{1}y

for l = 1, …, p_{I}, and T̃_{I} = s_{k} … ŝ_{i_{p}} … ŝ_{i_{1}} … s_{1}y, p = p_{I} = #I.

From the lemma it follows that for any such I there exists a reduced expression of x in which i_{j} = j and s_{i_{j}} ∈ L(y) for j = 1, …, l. Denoting by Γ_{y} the subgroup of W generated by simple reflections from L(y), we have s_{i_{p}} … s_{i_{1}} is a reduced expression of an element from Γ_{y}. To complete the proof it remains to show that for any y ∈ W subgroup Γ_{y} ≤ W is finite. Really, let s ≠ t ∈ L(y). This means that y has a reduced expression su_{2} … u_{n} (s, u_{j} ∈ S) and tsu_{2} … u_{n} = t̂su_{2} … û_{i} … u_{n}, so again by the lemma st = ts, which follows Γ_{y} ≅ ℤ_{2}^{p} (p = #L(y)) is a finite group.

4.3. Let a(z) be the smallest integer such that q^{a(z)/2}h_{x,y,z} ∈ A^{+} for any x, y ∈ W. It follows that 0 ≤ a(z) ≤ N for any z ∈ W. Here are some important properties of the function a obtained in [L2], [L3]:

Properties of a(z):

(i) a(w) = a(w^{−1}) for all w ∈ W; (ii) a(w) = 0 if and only if w = e; (iii) the function a is constant on the two-sided cells of W; (iv) a(w) ≤ l(w) for all w ∈ W.

4.4. Define a subset D ⊂ W as follows:

D = {z ∈ W | a(z) = l(z) − 2δ(z)},

where δ(z) is the degree of P_{e,z} as a polynomial in q.

It can be shown that d^{2} = e for any d ∈ D. The elements of D are called distinguished involutions of W. The following theorem was proved in [L3]:

Theorem. Any left cell contains a unique d ∈ D.

In the next section we shall use this powerful result to distinguish left cells of the groups P_{n}.

5. Cells and representations

We mainly consider left cells and corresponding left H-modules. The results concerning right cells are entirely similar. Two-sided cells and H-bimodules are obtained via combination of the left and right-sided ones.

Let us first suppose that (W, S) is an arbitrary Coxeter group. We shall always use s, t (possibly with subscribed indexes which will be not connected with the initial ordering of generators in the case of the group P_{n}) to denote the elements from S.

5.1. Let w_{1}, w_{2} ∈ W. We say that w_{1} and w_{2} belong to the same left precell and write w_{1} ∼_{lp} w_{2} if there exists w_{L} ≠ 1 such that w_{1}, w_{2} have reduced expressions w′_{1}w_{L}, w′_{2}w_{L}, respectively, and

(a) if l(w_{L}) > 1 then w′_{1}, w′_{2} are either trivial or segments in w_{1}, w_{2}, resp.;

(b) if l(w_{L}) = 1 then w_{1} and w_{2} are lines (with R(w_{1}) = R(w_{2}) = w_{L}). Let us also suppose 1 ∼_{lp} 1.

Proposition. Relation ∼_{lp} has the following properties:

(i) it is an equivalence relation on W; (ii) each left precell Γ contains a unique shortest element w_{L} = w_{L}(Γ) such that

Γ = {w | w = w′w_{L}} where w′ is either trivial, or a segment in w, or w′w_{L} is a line (as in the definition of ∼_{lp}).

Proof. To prove (i) we need only to check the transitivity of ∼_{lp}. Suppose

w_{1} ∼_{lp} w_{2}, w_{2} ∼_{lp} w_{3},

then we have

w_{1} = w′_{1}w_{L1}, w_{2} = w′_{2}w_{L1} = w′′_{2}w_{L2}, w_{3} = w′_{3}w_{L2},

with w′_{1}, w′_{2}, w′′_{2}, w′_{3} as in the definition of ∼_{lp}. We want to show w_{1} ∼_{L} w_{3} and we can suppose that w_{1}, w_{2}, w_{3} are all unequal since otherwise it is trivial. We now need to do some routine case by case considerations:

1) l(w_{L1}) = 1. Then w_{2} is a line, so w′′_{2} can not be its proper segment, consequently we have only two possibilities:

a) l(w_{L2}) = 1; w_{L2} = w_{L1}; w_{3} ∼_{L} w_{1}.

b) w′′_{2} = 1; w_{3} = w′_{3}w_{L2} = w′_{3}w_{2}, w′_{3} ≠ 1 is a segment in w_{3} but this is impossible

by the definition of segment since w_{2} is a line.

2) The case l(w_{L2}) = 1 is entirely similar.

3) l(w_{L1}) > 1, l(w_{L2}) > 1. There are again two possibilities:

a) w′_{2} = 1; w_{1} = w′_{1}w_{L1} = w′_{1}w_{2} = w′_{1}w′′_{2}w_{L2}, w′_{1} ≠ 1 is a segment in w_{1}. We have either w′′_{2} = 1 which follows w_{3} ∼_{L} w_{1}, or w′′_{2} is a segment in w′′_{2}w_{L2} which leads to a contradiction with the definition of segment.

b) w′_{2} is a segment in w_{2} then either w′_{2} = w′′_{2} and w_{3} ∼_{L} w_{1} or w′′_{2} = 1; w_{3} = w′_{3}w_{L2} = w′_{3}w_{2} = w′_{3}w′_{2}w_{L1} which is impossible by the definition of segment.

So in all the possible cases we obtain w_{1} ∼_{L} w_{3}.

To prove (ii) we can take for w_{L} (any) shortest element of the equivalence class Γ, then any w in Γ will have the required form by the definition and uniqueness of w_{L} follows. It is also possible to deduce the existence and uniqueness of w_{L} from the proof of (i).

The existence of the canonical representatives w_{L} of the left precells implies that the following definitions make sense:

Dimension of a non-unit left precell Γ dim(Γ) = #L(w_{L}), since l(w_{L}) ≥ 1 we have dim(Γ) ≥ 1. Given two left precells Γ_{1}, Γ_{2} we say that Γ_{1} ≤_{L} Γ_{2}, Γ_{1} ≺ Γ_{2}, Γ_{1} − Γ_{2} and Γ_{1} ∼_{L} Γ_{2} if w_{L}(Γ_{1}) ≤_{L} w_{L}(Γ_{2}), w_{L}(Γ_{1}) ≺ w_{L}(Γ_{2}), w_{L}(Γ_{1}) − w_{L}(Γ_{2}) and w_{L}(Γ_{1}) ∼_{L} w_{L}(Γ_{2}), respectively. We also define L(Γ) = L(w_{L}(Γ)) and R(Γ) = R(w_{L}(Γ)).

5.2. Lemma. A left cell in W is a union of the left precells which are ∼_{L}-equivalent to each other.

Proof. By Lemma 2.4 if w_{1} ∼_{lp} w_{2} then w_{1} ∼_{L} w_{2}. The corresponding chains x_{0} − x_{1} − ⋯ − x_{k}, joining w_{1} (w_{2}) with w_{L} and having property L(x_{i}) ∩ L(x_{i+1}) = ∅ for any i (which is actually stronger than it is required for ∼_{L}), are obtained from the lines w′_{1} (w′_{2}) defined in Proposition 5.1 by the rule x_{0} = w′_{1}w_{L} = t_{1} … t_{k}w_{L}, x_{i} = t_{i+1} … t_{k}w_{L}. Since both ∼_{L} and ∼_{lp} are the equivalence relations the remaining part of the statement follows easily.

The language of precells seems to be very appropriate for the description of the cells of right-angled Coxeter groups. We shall consider in details the case W = P_{n}. Similar methods can be applied to the other right-angled Coxeter groups as well, we are going to study these cases elsewhere.

5.3. Theorem. The non-unit left cells of the group P_{n} (n ≥ 5) are:

(i) n cells corresponding to the 1-dimensional left precells of P_{n} defined by the generators of P_{n};

(ii) infinitely many cells which are equivalence classes of the left precells with the canonical representatives Γ(w_{L}), such that w_{L} = t_{1}t_{2}w′_{L} with t_{1}t_{2} = t_{2}t_{1} (t_{1}, t_{2} ∈ S) and w′_{L} is a segment in w_{L}.

Proof. 1) We first show that each left precell of P_{n} belongs to an at least one left cell defined in the statement. If dim(Γ) = 1 then l(w_{L}(Γ)) = 1 (as it is easily follows from the definitions of the precell and w_{L}), so Γ is one of the 1-dimensional precells from (i). By the definition of the group P_{n} the dimensions of its left precells are not greater then 2 (this also follows from the representation of P_{n} as a group of isometries of the hyperbolic plane), thus it remains to consider a left precell Γ with dim(Γ) = 2.

Let w_{L} = w_{L}(Γ), we have w_{L} = t_{1,1} … t_{1,n_{1}}u_{1}t_{2,1} … t_{2,n_{2}}u_{2} … t_{k,1} … t_{k,n_{k}}u_{k}, where for any admissible i, j the subwords u_{i} are segments in w_{L}, n_{i} ≥ 2 and t_{i,j}t_{i,j+1} = t_{i,j+1}t_{i,j}. Define two elementary moves between reduced words:

A: t_{1}t_{2}t_{3}x → t_{2}t_{3}x for t_{1}t_{2} = t_{2}t_{1}, t_{2}t_{3} = t_{3}t_{2} and arbitrary subword x; B: s_{1}s_{2}ut_{1}t_{2}x → t_{1}t_{2}x for t_{1}t_{2} = t_{2}t_{1}, s_{1}s_{2} = s_{2}s_{1}, u is a segment or u = 1 and

arbitrary x. By applying this elementary moves to w_{L} one can obtain the word t_{k,n_{k}−1}t_{k,n_{k}}u_{k}

(u_{k} is a segment) which defines a canonical precell in (ii). We shall show that the moves produce ∼_{L}-equivalent words.

The equivalence w = t_{1}t_{2}t_{3}x ∼_{L} w_{0} = t_{2}t_{3}x is easy: we have w = t_{1}w_{0}, L(w_{0}) = {t_{1}, t_{2}}, L(w) = {t_{2}, t_{3}} and t_{3} ≠ t_{1} (because all the expressions are reduced), so w ≻ w_{0}, L(w_{0}) ⊄ L(w) and L(w) ⊄ L(w_{0}).

To prove that move B is a left equivalence we shall use a supplementary construction. Having w = s_{1}s_{2}ut_{1}t_{2}x, w_{0} = t_{1}t_{2}x, define w^{∗} = t_{1}u^{−1}s_{1}s_{2}ut_{1}t_{2}x. Note, that u is a segment in w implies u^{−1} and u are segments in w^{∗}. We are going to show the following relations:

w_{0}  ^{\underline{≤_{L}}}  w^{∗} ^{\underline{∼_{L}}} w_{1}^{∗} ^{\underline{∼_{L}}} … ^{\underline{∼_{L}}} w_{l}^{∗} ^{\underline{∼_{L}}} w
|  |
w_{1} ^{\underline{≥_{L}}} w_{2} ^{\underline{≥_{L}}} … ^{\underline{≥_{L}}} w_{n}

where w_{i+1} is obtained from w_{i} by adding at the left the next letter of w^{∗} and w_{j+1}^{∗} is obtained from w_{j}^{∗} by deleting a letter at the left.

The difficult part is to prove w_{0} ≤_{L} w^{∗} since all the other chains are just of the form x − y with |l(x) − l(y)| = 1 and so satisfy the definitions (one can also note that w^{∗} ∼_{lp} w).

Let u = u_{1} … u_{k} with u_{i} ∈ S is a (the) reduced expression of u. We need to show that the coefficient μ(w_{0}, w^{∗}) of the q^{(l(w^{∗})−l(w_{0})−1)/2} = q^{k+1} in P_{w_{0},w^{∗}} is not 0. Let us make use of the following formula for the polynomials P_{y,w} obtained in the proof of existence of the C_{w}-basis in [KL]:

P_{y,w} = q^{1−c}P_{sy,v} + q^{c}P_{y,v} − ∑_{{y≤z≺v \atop sz<z}} μ(z, v)q_{z}^{−1/2}q_{v}^{1/2}q^{1/2}P_{y,z} (y ≤ w),

where w = sv with l(w) = 1 + l(v), c = 1 if sy < y, c = 0 if sy > y and P_{x,v} = 0 unless x ≤ v.

We have:

P_{w_{0},w^{∗}} = P_{t_{1}t_{2}x,t_{1}u^{−1}s_{1}s_{2}ut_{1}t_{2}x} = P_{t_{2}x,v} + qP_{t_{1}t_{2}x,v} − Σ_{0}

with v = u^{−1}s_{1}s_{2}ut_{1}t_{2}x and Σ_{0} = ∑ μ(z, v)q_{z}^{−1/2}q_{v}^{1/2}q^{1/2}P_{y,z} where the summation is over z such that t_{1}t_{2}x ≤ z ≺ v, t_{1}z < z.

μ(t_{2}x, v) = 0 because L(v) = u_{k} ∉ L(t_{2}x) since u is a segment in w, and so by Lemma 2.4 P_{t_{2}x,v} has the maximal possible degree (= k + 1) if and only if u^{−1}s_{1}s_{2}ut_{1}t_{2}x = u_{k}t_{2}x which is impossible. Consider the second term:

qP_{t_{1}t_{2}x,v} = q^{2}P_{u_{k}t_{1}t_{2}x,u_{k−1}...u_{1}s_{1}s_{2}u_{1}...u_{k}t_{1}t_{2}x} + qP_{1} − qΣ_{1},

defining for i = 1, …, k :

P_{i} = P_{y_{i},v_{i}},
Σ_{i} = ∑_{{y_{i}≤z≺v_{i} \atop u_{k−i+1}z<z}} μ(z, v)q_{z}^{−1/2}q_{v_{i}}^{1/2}q^{1/2}P_{y_{i},z},

y_{i} = u_{k−i+2} … u_{k}t_{1}t_{2}x,
v_{i} = u_{k−i} … u_{1}s_{1}s_{2}u_{1} … u_{k}t_{1}t_{2}x

(with the conventions that u_{k−i+2} … u_{k} = 1 for i = 1 and u_{k−i} … u_{1} = 1 for i = k).

The remarkable point is that the coefficients of q^{k−i+2} in qP_{i} and Σ_{i−1} for i = 1, …, k are equal! Really, consider the sum Σ_{i}. We have L(v_{i}) = u_{k−i} ∉ L(z) (since u_{k−i+1} ∈ L(z) and it does not commute with u_{k−i}) so by Lemma 2.4 z ≺ v_{i} implies v_{i} = u_{k−i}z, μ(z, v_{i}) = 1, z = u_{k−i−1} … u_{1}s_{1}s_{2}u_{1} … u_{k}t_{1}t_{2}x = v_{i+1} and this is possible only if

u_{k−i−1} = u_{k−i+1}. (∗)

In this case we have P_{y_{i},z} = P_{y_{i},v_{i+1}} = P_{y_{i+1},v_{i+1}} (the last equality is the consequence of L(y_{i}) = u_{k−i+2} ≠ u_{k−i+1} = L(v_{i+1})) and so Σ_{i} = qP_{i+1}. It remains to check that if μ(y_{i+1}, v_{i+1}) ≠ 0 then the equality (∗) holds, which can be easily done by supposing in the contrary that u_{k−i−1} ≠ u_{k−i+1} and applying Lemma 2.4. The case of Σ_{0} should be considered separately, of course, but appears to be very similar.

So the leading terms of qP_{i} and Σ_{i−1} do repetitively cancel each other and we finally obtain that the coefficient of q^{k+1} in P_{w_{0},w^{∗}} is equal to the leading coefficient of q^{k+1}P_{u_{1}y_{k},v_{k}}, which is equal to 1 because u_{1}y_{k} < v_{k} and l(v_{k}) − l(u_{1}y_{k}) = 2.

This proves w_{0} ≺ w^{∗} with μ(w_{0}, w^{∗}) = 1.

2) It remains to show that the cells defined in the statement do not intersect. We shall use the distinguished involutions.

For the non-unit elements z ∈ P_{n} we have a(z) ∈ {1, 2}. If z is in a cell of type (i) then there exists s ∼_{L} z and by the Properties 4.3 a(z) = a(s) = 1. Now let z is in a cell of type (ii). Using Moves A, B from the first part of this proof and their right-side analogs we see that z belongs to the same two-sided cell as st (s, t ∈ S, (st)^{2} = 1). It is easy to show that a(st) = 2 (take x = y = st in the definition of the function a), so again by 4.3 a(z) = 2.

It immediately follows from the definitions that s_{i} ∈ D, i = 1, …, n so we have the distinguished involutions for each of the cells of type (i). Now consider a cell of type (ii) with the represenative Γ(w_{L}) as in the statement of the theorem. An element z = w′_{L}^{−1}t_{1}t_{2}w′_{L} ∈ Γ(w_{L}) is an involution, we shall see that z ∈ D. Supposing w′_{L} = u_{1} … u_{k}, all u_{i} ∈ S we have

P_{e,z} = P_{e,u_{k}...u_{1}t_{1}t_{2}u_{1}...u_{k}} = P_{u_{k},u_{k}...u_{1}t_{1}t_{2}u_{1}...u_{k}}.

After denoting u_{k} by t_{1} we see that the argument, which was used to show that w_{0} ≤_{L} w∗ in part (1) of this proof, works without any changes in this case either, giving deg(P_{e,z}) = k. So

l(z) − 2δ(z) = 2k + 2 − 2k = 2 = a(z)

and z ∈ D by the definition.

It remains to apply Theorem 4.4 to distinguish all the left cells.

5.4. It was pointed out to me by V. Ostrik that the cells of type (i) were previously considered in [L1]. There the cells and corresponding representations were constructed for an arbitrary Coxeter group and then thoroughly studied in the finite and affine cases.

Left cells of the group P_{n} can be visualized on the corresponding tessellation of the hyperbolic plane. Figure 2 presents the cells for the group P_{5}: pentagon in the center is the unit cell, five shaded regions represent the cells of type (i) all giving a one two-sided cell (see Corollary 5.7), each white region represents a cell of type (ii) and altogether they form the third two-sided cell.

Figure 2. Cells of the group P_{5}.^{1}

Below we give several corollaries that follow from Theorem 5.3 and its proof.

1 This picture uses W. Casselman’s PostScript library for hyperbolic geometry.

5.5. Corollary. The distinguished involutions of the group P_{n} are

D = {1} ∪ {s_{1}, …, s_{n}} ∪ {ustu^{−1} | (st)^{2} = 1, u is a segment in ustu^{−1}}.

The distinguished involutions are related with algebra J defined in [L3] which may be regarded as an asymptotic version of Hecke algebra H. Using the methods from [L3] this corollary can be applied to retrieve a partial structure information about algebra J of the group P_{n}.

5.6. Corollary. W -graphs associated to the left cells of type (i) are infinite rooted trees (binary trees for the group P_{5}, see Figure 3), while the W -graphs associated to the type (ii) cells admit infinetely many different cycles.

One can see, that all the W -graphs corresponding to the cells of type (i) of the group P_{n} define equivalent representations of H, with the equivalences induced by the cyclic permutations of the simple reflections s_{i} ∈ S. We suppose that the representations corresponding to the cells of type (ii) are also all equivalent but this does not readily follow from the above arguments.

Figure 3. Example of a W -graph corresponding to a left cell of type (i) of the group P_{5} (all μ(x, y) = 1, the vertices are represented by circles with the corresponding subsets of S inside).

5.7. Corollary. The partition of the group P_{n} (n ≥ 5) onto two-sided cells consits of 3 elements:

- the unit cell corresponding to the trivial representation of H;

- the union of the left cells of type (i) (a 1-dimensional cell), the corresponding W -graph is an infinite tree;

- the union of the left cells of type (ii) (a 2-dimensional cell), the corresponding W -graph admits infinitely many different cycles.

The remarkable point about this corollary is that to establish it we actually need only the Moves A, B from the proof 5.3 with their right-side analogs, and so we do not use part (2) of the argument which relies on certain very strong results about distinguished involutions.

References

[B] R. Bédard, Left V-cells for hyperbolic Coxeter groups. Comm. Algebra, 17 (1989), 2971– 2997.

[BGI] E. Bujalance, G. Gromadzki, R. Izquierdo, On real forms of a complex algebraic curve, J. Aust. Math. Soc., 70 (2001), 134–142.

[C] W. Casselman, Automata to perform basic calculations in Coxeter groups, Representations of groups (Banff, AB, 1994), Amer. Math. Soc., Providence, 1995, pp. 35–58.

[D] M. Davis, Groups generated by reflections and aspherical manifolds not covered by Euclidean space, Ann. of Math., 117 (1983), 293–324.

[H] J. Humphreys, Reflection groups and Coxeter groups, Cambridge studies in advanced mathematics 29, Cambridge University Press, Cambridge, 1990.

[KL] D. Kazhdan, G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165–184.

[KP] V. Kac, D. Peterson, Defining relations for certain infinite-dimensional groups, Astérisque Hors-Sèrie (1985), 165–208.

[L1] G. Lusztig, Some examples of square integrable representations of semisimple p-adic groups, Trans. Amer. Math. Soc., 277 (1983), 623–653.

[L2] G. Lusztig, Cells in affine Weyl groups, Algebraic Groups and Related Topics, Advanced Studies in Pure Math. 6, Kinokuniya and North-Holland, Amsterdam, 1985, pp. 255–287

[L3] G. Lusztig, Cells in affine Weyl groups, II, J. Algebra, 109 (1987), 536–548.

[MV] A. Mednykh, A. Vesnin, On three-dimensional hyperbolic manifolds of Löbell type, Complex analysis and applications ’85 (Varna, 1985), Publ. House Bulgar. Acad. Sci., Sofia, 1986, pp. 440–446.

[OV] A. Okounkov, A. Vershik, A new approach to representation of symmetric groups, Selecta Math. (N.S.), 2 (1996), 581–605.

[T] J. Tits, Le problème des mots dans les groupes de Coxeter, Symposia Mathematica (INDAM, Rome, 1967/68), Acad. Press, London, 1969, pp. 175–185.

[VS] E.B. Vinberg, O.V. Shvartsman, Discrete groups of motions of spaces of constant curvature, Geometry II, Encyc. Math. Sci. 29, Springer-Verlag, 1993, pp. 139–248.

Sobolev Institute of Mathematics, Koptyuga 4, 630090 Novosibirsk, Russia, Max Planck Institute of Mathematics, Vivatsgasse 7, 53111 Bonn, Germany

   E-mail address: mbel@math.nsc.ru