LEFT CELLS IN THE AFFINE WEYL GROUP OF TYPE C̃_{4}

Jian-yi Shi Department of Mathematics, East China Normal University, Shanghai, 200062, P.R.C.

and

School of Mathematics and Statistics, University of Sydney, Sydney, NSW 2006, Australia

Abstract. We find a representative set of left cells of the affine Weyl group W_{a} of type C̃_{4} as well as its left cell graphs by applying an algorithm. This algorithm was designed in my previous paper [22]. It is reformulated and improved in more efficient form here. These representatives of left cells are presented as the vertices of so called essential graphs so that the generalized τ-invariants of left cells of W_{a} are actually described explicitly, the latter almost characterize the left cells of W_{a}. Some comments and conjectures are proposed on cells of affine Weyl groups, mostly for the case of type C̃_{ℓ}, ℓ ≥ 2.

Since it was designed in [22], an algorithm of finding a representative set of left cells ( an l.c.r. set for brevity) of a certain Coxeter group (W, S) has been applied extensively to Weyl groups and affine Weyl groups (see [8; 16; 22; 23; 26; 27]). In the present paper, we shall reformulate and improve this algorithm so that it can be performed more efficiently. We introduce three processes A, B and C instead of only two processes A and B in the algorithm, by which one can avoid the complicated calculation of Kazhdan-Lusztig polynomials to a great extent. On the other hand, we introduce two important concepts: an essential graph and a left cell graph associated to an element of W. The left cell graphs exhibit the generalized τ-invariants for all

Typeset by AMS-TEX

Supported partly by Max-Planck-Institut für Mathematik, Bonn, Germany, partly by Australia Research Fundation, and partly by the National Science Foundation of China and the Science Foundation of the University Doctorial Program of CNEC

2 Jian-yi Shi

the left cells of W. The essential graphs can do more, which provide an l.c.r. set of W in addition. Note that to an element of W, the associated essential graph does not always exist in general. Fortunately, such an obscurity does not occur in the case of the affine Weyl group W_{a}(C̃_{4}) of type C̃_{4}. By the results of Lusztig and Bédard (see [12; 2]), this is still the case for the affine Weyl groups W_{a}(C̃_{2}) and W_{a}(C̃_{3}). Moreover, by combining with the results of Lusztig and Bédard (see §6.), we shall see that for k = 2, 3, 4, all the left cells of W_{a}(C̃_{k}) not in the lowest two-sided cell (this can be checked easily from the alcove form of any of their elements) can be characterized only by their generalized τ-invariants. Since the left cells of any affine Weyl group in the lowest two-sided cell are characterized by their sign types (see [19; 20] for the definition of a sign type and for this result), all the left cells of W_{a}(C̃_{k}), k = 2, 3, 4, are described completely. I expect that these phenomena should be in common for all the affine Weyl groups W_{a}(C̃_{ℓ}), ℓ ≥ 2.

Some more comments and conjectures are proposed on cells of affine Weyl groups, mostly for the case of type C̃_{ℓ}, ℓ ≥ 2. This includes the combinatorial description of the Lusztig map relating the two-sided cells of W_{a}(C̃_{ℓ}) to the unipotent conjugacy classes of the corresponding algebraic group, and the group-theoretical interpretation for the number of left cells in some two-sided cells of some affine Weyl groups W_{a}, which involves both Lusztig map and Bala-Carter correspondence among two-sided cells of an affine Weyl group, unipotent conjugacy classes of the corresponding algebraic group G and the G-classes of pairs (L, P_{L′}), where L is a Levi subgroup of G, P_{L′} is a distinguished parabolic subgroup of semisimple part L′ of L.

The arrangement of the paper is as follows. In section 1, we collect some results on the cells of a Coxeter group, in particular of an affine Weyl group and even of the group W_{a}(C̃_{4}). We reformulate and improve the algorithm of finding an l.c.r. set in section 2. Then in section 3, we introduce some results and terminologies needed in performing the algorithm. Sections 4 and 5 are specially concerning the affine Weyl group W_{a}(C̃_{4}). We obtain an l.c.r. set as well as all the left cell graphs for the group W_{a}(C̃_{4}) in section 4 and make some comments on the possible generalization of some properties of left cells of W_{a}(C̃_{4}) to the more general groups W_{a}(C̃_{ℓ}), ℓ ≥ 2, in section

Left Cells in Affine Weyl Group 3

5. Finally, we put an appendix in §6, where we list all the left cell graphs and state some known results for the affine Weyl groups W_{a}(C̃_{2}) and W_{a}(C̃_{3}).

§1. Some results on cells. 1.1 Let W = (W, S) be a Coxeter group with S its Coxeter generator set. Let ≤ be the Bruhat order on W. For w ∈ W, we denote by ℓ(w) the length of w. Let A = ℤ[u] be the ring of polynomials in an indeterminate u with integer coefficients. For each ordered pair y, w ∈ W, there exists a unique polynomial P_{y,w} ∈ A, called a Kazhdan-Lusztig polynomial, which satisfies the conditions: P_{y,w} = 0 if y ⩽̸ w, P_{w,w} = 1, and deg P_{y,w} ≤ (1/2)(ℓ(w) − ℓ(y) − 1) if y < w. For y < w in W, let μ(w, y) = μ(y, w) be the coefficient of u^{(1/2)(ℓ(w)−ℓ(y)−1)} in P_{y,w}. We denote y—–w if μ(y, w) ≠ 0.

Checking the relation y—–w for y, w ∈ W usually involves very complicated computation of Kazhdan-Lusztig polynomials. But it becomes easy in some special case: if x, y ∈ W satisfy y < x and ℓ(y) = ℓ(x) − 1, then we have y—–x. Another result concerning this relation will be stated in Proposition 3.3. 1.2 The preorders ≤_{L}, ≤_{R}, ≤_{LR} and the associated equivalence relations ∼_{L},∼_{R}, ∼_{LR} on W are defined as in [10]. The equivalence classes of W with respect to ∼_{L} ( resp. ∼_{R}, ∼_{LR} ) are called left cells ( resp. right cells, two-sided cells ). 1.3 An affine Weyl group W_{a} is a Coxeter group which can be realized geometrically as follows. Let G be a connected, adjoint reductive algebraic group over ℂ. We fix a maximal torus T of G. Let X be the group of characters T ⟶ ℂ and let Φ ⊂ X be the set of roots with Δ = {α_{1}, ⋯, α_{ℓ}} a choice of simple root system. Then E = X ⊗_{ℤ} ℝ is a euclidean space with an inner product ⟨ , ⟩ such that the Weyl group (W_{0}, S_{0}) of G with respect to T acts naturally on E and preserves its inner product, where S_{0} is the set of simple reflections s_{i} corresponding to the simple roots α_{i}, 1 ≤ i ≤ ℓ. We denote by N the group of all translations T_{λ} (λ ∈ X) on E: T_{λ} sends x to x + λ,. Then the semidirect product W_{a} = W_{0} ⋉ N is called an affine Weyl group. Let K be the dual of the type of G. Then we define the type of W_{a} by K̃. Sometimes we denote W_{a} by W_{a}(K̃) to indicate its type K̃. There is a canonical homomorphism from W_{a} to W_{0}: w ↦ w̄.

4 Jian-yi Shi

Let −α_{0} be the highest short root in Φ. We define s_{0} = s_{α_{0}}T_{−α_{0}}, where s_{α_{0}} is the reflection corresponding to α_{0}. Then the generator set of W_{a} can be taken as S = S_{0} ∪ {s_{0}}. 1.4 The alcove form of an element w ∈ W_{a} is, by definition, a Φ-tuple (k(w, α))_{α∈Φ} over ℤ subject to the following conditions.

(a) k(w, −α) = −k(w, α) for any α ∈ Φ;

(b) k(e, α) = 0 for any α ∈ Φ, where e is the identity element of W_{a};

(c) If w′ = ws_{i} ( 0 ≤ i ≤ ℓ ), then

k(w′, α) = k(w, (α)s̄_{i}) + ϵ(α, i)

with

ϵ(α, i) = \{ \begin{matrix}0  if α ≠ ±α_{i}; \\ −1  if α = α_{i}; \\ 1  if α = −α_{i}, \end{matrix}

where s̄_{i} = s_{i} if 1 ≤ i ≤ ℓ, and s̄_{0} = s_{α_{0}} ( see [18, Proposition 4.2] ).

By condition (a), we can also denote the alcove form of w ∈ W_{a} by a Φ^{+}-tuple (k(w, α))_{α∈Φ^{+}}. 1.5 Condition 1.4, (c) actually defines a set of operators {s_{i} | 0 ≤ i ≤ ℓ} on the alcove forms of elements of W_{a}:

s_{i} : (k_{α})_{α∈Φ} ⟼ (k_{(α)s̄_{i}} + ϵ(α, i))_{α∈Φ}.

These operators could be described graphically. For example, assume that W_{a} has type C̃_{ℓ}, ℓ ≥ 2, and that the indices of simple roots α_{i} are compatible with the following Dynkin diagram:

∘—————∘—— ⋯——∘—————∘⟹∘_{1  2  ℓ−2  ℓ−1  ℓ}

A root α = ∑_{i=1}^{ℓ} a_{i}α_{i} will be denoted in the form (a_{1}, a_{2}, ⋯, a_{ℓ}). Let ℓ = 4. We arrange the entries of a Φ^{+}-tuple (k_{α})_{α∈Φ^{+}} in the following way.

(1.5.1)  \begin{matrix}k_{(1,1,1,0)} \\ k_{(1,1,0,0)}  k_{(0,1,1,0)} \\ k_{(1,0,0,0)}  k_{(0,1,0,0)}  k_{(0,0,1,0)} \\ k_{(1,1,1,1)}  k_{(0,1,1,1)}  k_{(0,0,1,1)}  k_{(0,0,0,1)} \\ k_{(1,2,2,2)}  k_{(0,1,2,2)}  k_{(0,0,1,2)} \\ k_{(1,1,2,2)}  k_{(0,1,1,2)} \\ k_{(1,1,1,2)} \end{matrix}

Then the actions of s_{i}, 0 ≤ i ≤ 4, on a Φ^{+}-tuple

w = \begin{matrix}a \\ b c \\ d e f \\ g h i j \\ k l m \\ n p \\ q \end{matrix}

are listed as in the following table.

\begin{matrix}s & s_{0} & s_{1} & s_{2} & s_{3} & s_{4} \\ ws & \begin{matrix}−q \\ −n ∗ \\ −k ∗ ∗ \\ −g+1 ∗ ∗ ∗ \\ −d ∗ ∗ \\ −b ∗ \\ −a \end{matrix} & \begin{matrix}c \\ e a \\ −d−1 b ∗ \\ h g ∗ ∗ \\ ∗ n ∗ \\ l q \\ p \end{matrix} & \begin{matrix}∗ \\ d f \\ b −e−1 c \\ ∗ i h ∗ \\ n ∗ p \\ k m \\ ∗ \end{matrix} & \begin{matrix}b \\ a e \\ ∗ c −f−1 \\ ∗ ∗ j i \\ ∗ p ∗ \\ q l \\ n \end{matrix} & \begin{matrix}q \\ ∗ p \\ ∗ ∗ m \\ ∗ ∗ ∗ −j−1 \\ ∗ ∗ f \\ ∗ c \\ a \end{matrix} \end{matrix}

where the entries in the ∗ positions remain unchanged. 1.6 To each element x ∈ W_{a}, we associate two subsets of S as below.

L(x) = {s ∈ S | sx < x} and R(x) = {s ∈ S | xs < x}.

For w, w′ ∈ W_{a}, we say that w′ is a left extension of w if ℓ(w′) = ℓ(w) + ℓ(w′w^{−1}). Then the following results on the alcove form (k(w, α))_{α∈Φ} of an element w ∈ W_{a} are known.

Proposition [18, Propositions 4.1, 4.3]. (1) ℓ(w) = ∑_{α∈Φ^{+}} |k(w, α)|, where the notation |x| stands for the absolute value of x;

(2) R(w) = {s_{i} | k(w, α_{i}) < 0}.

(3) w′ is a left extension of w if and only if the inequalities k(w′, α)k(w, α) ≥ 0 and |k(w′, α)| ≥ |k(w, α)| hold for any α ∈ Φ.

1.7 Lusztig defined a function a : W_{a} ⟶ ℕ which satisfies the following properties:

(1) a(z) ≤ ν = |Φ|/2, for any z ∈ W_{a}, where Φ is the root system associated to W_{a} as in 1.3; 6 Jian-yi Shi

(2) x ≤_{LR} y ⟹ a(x) ≥ a(y). In particular, x ∼_{LR} y ⟹ a(x) = a(y). So we may define the a-value a(Γ) on a ( left, right or two-sided ) cell Γ of W_{a} by a(x) for any x ∈ Γ.

(3) a(x) = a(y) and x ≤_{L} y ( resp. x ≤_{R} y ) ⟹ x ∼_{L} y ( resp. x ∼_{R} y ).

(4) For any proper subset I of S, let w_{I} be the longest element in the subgroup W_{I} of W_{a} generated by I. Then a(w_{I}) = ℓ(w_{I}).

The above properties of function a were shown by Lusztig in his papers [12; 13]. Now we state some more properties of this function, the first two of which are simple consequences of properties (2), (3) and (4).

Let W_{(i)} = {w ∈ W_{a} | a(w) = i} for any non-negative integer i. Then by (2), W_{(i)} is a union of some two-sided cells of W_{a}.

(5) If W_{(i)} contains an element of the form w_{I} for some I ⊂ S, then {w ∈ W_{(i)} | R(w) = I} forms a single left cell of W_{a}.

(6) By the notation x = y · z (x, y, z ∈ W_{a}), we mean x = yz and ℓ(x) = ℓ(y) + ℓ(z). In this case, we have x ≤_{L} z, x ≤_{R} y and hence a(x) ≥ a(y), a(z). In particular, if I = R(x) ( resp. I = L(x) ), then a(x) ≥ ℓ(w_{I}).

(7) W_{(i)} is a single two-sided cell of W_{a} if i ∈ {0, 1, ν}. As sets, W_{(i)} (i = 0, 1, ν) can be described as below. W_{(0)} = {e}, where e is the identity element of W. W_{(1)} consists of all the non-identity elements of W_{a} each of which has a unique reduced expression (see [11]). W_{(ν)} consists of all the elements of W_{a} which have no zero entry in their alcove forms (see 1.4). W_{(ν)} can also be described as the lowest two-sided cell of W_{a} with respect to the partial order ≤_{LR} (see [19; 20]).

(8) Call an element s ∈ S special, if the subgroup of W_{a} generated by S \ {s} is isomorphic to W_{0}. Thus the element s_{0} is always special. When W_{a} is of type C̃_{ℓ}, the element s_{ℓ} is the unique special element in S other than s_{0}. It is known that for any two-sided cell Ω ≠ {e} of W_{a} and any special element s ∈ S, the set Y_{s} = {w ∈ Ω | R(w) = {s}} is non-empty and is a single left cell of W_{a} (see [15]). 1.8 Let G and W_{a} be as in 1.3. Then the following result of Lusztig is important to our purpose.

Theorem [14, Theorem 4.8]. There exists a bijection u ↦ c(u) from the set of unipotent conjugacy classes in G to the set of two-sided cells in W_{a}. This bijection satisfies the equation a(c(u)) = dim 𝔅_{u}, where u is any element in u, and dim 𝔅_{u} is the dimension of the variety of Borel subgroups of G containing u.

1.9 Let W_{a} = W_{a}(C̃_{4}). Then according to the knowledge of the unipotent classes of the complex simple algebraic group of type B_{4}, we see from Theorem 1.8 that in W_{a}, the set W_{(i)} is non-empty if and only if i ∈ Λ = {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 16}. More precisely, W_{(i)} is a single two-sided cell of W_{a} if i ∈ {0, 1, 2, 5, 6, 8, 9, 10, 16}, and is a union of two two-sided cells of W_{a} if i ∈ {3, 4}.

§2. The algorithm in finding an l.c.r. set.

Here and later, the notation W_{a} always stands for an affine Weyl group with S its Coxeter generator set. One of the main purposes of the present paper is to describe the left cells of the affine Weyl group W_{a} of type C̃_{4} by finding its l.c.r. set. We need an algorithm to do so, which was constructed in my paper [22] and is applicable to certain family of crystallographic groups including all the Weyl groups and all the affine Weyl groups. In this section, we shall recall some results of [22]. In particular, we shall reformulate the algorithm in more suitable form, where the concerned Coxeter group is always assumed to be W_{a}. Some comments on the algorithm are new. 2.1 To each element x ∈ W_{a}, we associate a set Σ(x) of all left cells Γ of W_{a} satisfying the condition that there is some element y ∈ Γ with y—x, R(y) ⊈ R(x) and a(y) = a(x).

Then the following result is known

Theorem [22, Theorem 2.1]. If x ∼_{L} y in W_{a}, then R(x) = R(y) and Σ(x) = Σ(y).

2.2 Say a set Σ of left cells of W_{a} to be represented by a set K ⊂ W_{a} if Σ is the set of all left cells Γ of W_{a} with Γ ∩ K ≠ ∅. K is called a representative set for Σ, if K represents Σ with |K ∩ Γ| = 1 for any Γ ∈ Σ, where the notation |X| stands for the cardinality of the set X.

The algorithm is based on the following result which is a consequence of Theorem 2.1.

8 Jian-yi Shi

Theorem [22, Theorem 3.1]. Let Ω be a two-sided cell of W_{a}. Then a non-empty subset K ⊂ Ω is a representative set of left cells ( an l.c.r. set for short) of W_{a} in Ω if K satisfies the following conditions.

(1) x ≁_{L} y for any x ≠ y in K;

(2) If an element y ∈ W_{a} is such that there is some element x ∈ K with y—x, R(y) ⊈ R(x) and a(y) = a(x), then y ∼_{L} z for some z ∈ K .

2.3 To each element x ∈ W_{a}, we denote by M(x) the set of all elements y such that there are a sequence of elements x_{0} = x, x_{1}, ⋯, x_{r} = y in W_{a} with some r ≥ 0, where for every i, 1 ≤ i ≤ r, the conditions x_{i−1}^{−1}x_{i} ∈ S and R(x_{i−1})_{⊈}^{⊉}R(x_{i}) are satisfied. 2.4 A subset K ⊂ W_{a} is said to be distinguished if K ≠ ∅ and x ≁_{L} y for any x ≠ y in K. 2.5 By [10, 2.3f], we know that the relations y—–x and R(y) ⊈ R(x) hold if and only if one of the following cases occurs.

(a) y^{−1}x ∈ S and R(y)_{⊈}^{⊉}R(x);

(b) y = x · s for some s ∈ S with R(y) ⫌ R(x);

(c) y < x, y—–x and R(y) ⫌ R(x).

According to this fact, we design the following three processes on a non-empty set P ⊂ W_{a}. (A) Find a largest possible subset Q from the set ⋃_{x∈P} M(x) with Q distinguished.

(B) To each x ∈ P, find elements y ∈ W_{a} such that y^{−1}x ∈ S, R(y) ⫌ R(x) and a(y) = a(x), add these elements y on the set P to form a set P′ and then take a largest possible subset Q from P′ with Q distinguished. (C) To each x ∈ P, find elements y ∈ W_{a} such that y < x, y—–x, R(y) ⫌ R(x) and a(y) = a(x), add these elements y on the set P to form a set P′ and then take a largest possible subset Q from P′ with Q distinguished.

Note that Processes (B) and (C) put together are amount to Process (B) defined in [22]. 2.6 A subset P of W_{a} is called A-saturated ( resp. B-saturated, resp. C-saturated ),

Left Cells in Affine Weyl Group 9

if Process (A) (resp. (B), resp. (C) ) on P can’t produce any element z satisfying

z ≁_{L} x for all x ∈ P.

Clearly, a set of the form ⋃_{x∈K} M(x) for any K ⊂ W_{a} is always A-saturated.

It follows from Theorem 2.2 that an l.c.r. set of W_{a} in a two-sided cell Ω is exactly a distinguished subset of Ω which is A-, B- and C-saturated. So to get such a set, we may use the following 2.7 ALGORITHM [22, 3.3].

(1) Find a non-empty subset P of Ω ( Usually we take P to be distinguished for avoiding unnecessary complication whenever it is possible );

(2) Perform Processes (A), (B) and (C) alternately on P until the resulting distinguished set can’t be further enlarged by these processes. Remark 2.8 (1) An l.c.r. set of W_{a} in a two-sided cell obtained by the above algorithm is contained in some right cell.

(2) In general, Process (A) is easier to be performed than Processes (B) and (C). The only part of Process (A) which may cause some difficulty is to find a largest distinguished subset in the set ⋃_{x∈P} M(x). On the other hand, Process (B) is easier to be performed than Process (C). In addition of the difficulty of finding a largest distinguished subset in a given set, the only other difficulty which may occur in Process (B) is to check whether or not the condition a(y) = a(x) holds. Process (C) is usually quite difficult to be performed, in particular when the lengths of the elements x ∈ P are getting larger. This is because checking the relation y—–x may involve very complicated computation of Kazhdan-Lusztig polynomials. To avoid such kind of troubles to a great extent, we shall give the first priority to Process (A) and the second priority to Process (B) in applying Algorithm 2.7. In other words, in applying Algorithm 2.7, we always first perform Process (A); Process (B) is performed only when Process (A) alone can not make any further progress; finally Process (C) is performed when no progress can be made only by Processes (A) and (B).

(3) To be simplified, Process (C) can be performed in the following way. To an 10 Jian-yi Shi

element x ∈ P, find the set Ξ(x) of all elements y with y < x, ℓ(x) ≢ ℓ(y)( mod 2), R(y) ⫌ R(x) and L(y) ⊇ L(x). Then find the set Ξ_{0}(x) of all elements y in Ξ(x) such that a(y) = a(x) and y ≁_{L} z for any z ∈ P. If Ξ_{0}(x) ≠ ∅, then find a maximal distinguished set Ξ_{1}(x) consisting of all elements y ∈ Ξ_{0}(x) with y—–x and add it to the set P.

The advantage of the above procedure is that we can reduce the calculation of Kazhdan-Lusztig polynomials to a great extent. Combining this with the convention of the priority in applying Algorithm 2.7, sometimes we can even avoid the calculation of any non-trivial Kazhdan-Lusztig polynomials entirely in practice. The set Ξ_{0}(x) is empirically always empty in the present case as well as in all the other cases so far we have dealt with [8; 16; 22; 23; 25; 26; 27]. One might think that Process (C) is absolutely redundant and should be removed from the algorithm. But I can’t rule it out in general.

§3. Some results and terminologies needed in performing Algorithm 2.7.

In applying Algorithm 2.7, we need some results which will be provided in the subsequent discussion. From 1.7, (3) and Theorem 2.1, we have the following result on a set M(x).

Proposition 3.1. (1) For any x ∈ W_{a}, the set M(x) is wholly contained in some right cell of W_{a}.

(2) If x ∼_{L} y in W_{a}, then M(x) and M(y) represent the same set of left cells of W_{a}.

3.2 In a Coxeter system (W, S), a sequence of elements of the form

(3.2.1)  \underbrace{ys, yst, ysts, …}_{m−1 terms}

is called an {s, t}-string ( or just call it a string ) if s, t ∈ S and y ∈ W satisfy the conditions that the order o(st) of the product st is m and R(y) ∩ {s, t} = ∅.

It is easily seen that a string is wholly contained in some right cell of W. For any x ∈ W, we can re-define M(x) to be the minimal set containing x, subject to the requirement: any string (regarded as a set) meeting M(x) must be wholly contained in M(x). Suppose that we are given two {s, t}-strings x_{1}, x_{2}, …, x_{m−1}

Left Cells in Affine Weyl Group 11

and y_{1}, y_{2}, …, y_{m−1} with o(st) = m. We denote the integers μ(x_{i}, y_{j}) (see 1.1) by a_{ij} for 1 ≤ i, j ≤ m − 1. Then it is known that

Proposition 3.3 [12, 10.4]. In the above setup, the following assertions hold.

(a) When m = 3, we have a_{12} = a_{21}, a_{11} = a_{22};

(b) When m = 4, we have a_{12} = a_{21} = a_{23} = a_{32}, a_{11} = a_{33}, a_{13} = a_{31} and a_{22} = a_{11} + a_{13}.

We have the following result corresponding to this.

Proposition 3.4 [10, Corollary 4.3; 22, Proposition 4.6]. Keep the setup of 3.2.

(1) If m = 3, then

(a) x_{1} ∼_{L} y_{1} ⟺ x_{2} ∼_{L} y_{2};

(b) x_{1} ∼_{L} y_{2} ⟺ x_{2} ∼_{L} y_{1}.

(2) If m = 4, then

(a) x_{1} ∼_{L} y_{2} ⟺ x_{2} ∼_{L} y_{1} ⟺ x_{2} ∼_{L} y_{3} ⟺ x_{3} ∼_{L} y_{2};

(b) x_{1} ∼_{L} y_{1} ⟺ x_{3} ∼_{L} y_{3};

(c) x_{1} ∼_{L} y_{3} ⟺ x_{3} ∼_{L} y_{1};

(d) x_{2} ∼_{L} y_{2} ⟺ either x_{1} ∼_{L} y_{1} or x_{1} ∼_{L} y_{3}

3.5 Two elements x, y ∈ W_{a} form a primitive pair, if there exist two sequences of elements x_{0} = x, x_{1}, ⋯, x_{r} and y_{0} = y, y_{1}, ⋯, y_{r} in W_{a} such that the following conditions are satisfied.

(a) x_{i}—–y_{i} for all i, 0 ≤ i ≤ r.

(b) For every i, 1 ≤ i ≤ r, there exist some s_{i}, t_{i} ∈ S such that x_{i−1}, x_{i} (and also y_{i−1}, y_{i})) are two neighboring terms in some {s_{i}, t_{i}}-string.

(c) Either R(x) ⊈ R(y) and R(y_{r}) ⊈ R(x_{r}), or R(y) ⊈ R(x) and R(x_{r}) ⊈ R(y_{r}) hold.

In this case, we have x ∼_{R} y by Proposition 3.1.

Assume that x, x′ (and also y, y′) are two neighboring terms in some {s, t}- string with x—–y and that at least one of x, y is a terminal term of the {s, t}-string containing it. Then by Proposition 3.3, we have x′—–y′. In particular, it is always the 12 Jian-yi Shi

case when o(st) = 3. Thus, if in (b), we have in addition that at least one of x_{i}, y_{i} is a terminal term of the {s_{i}, t_{i}}-string containing it for all i, 0 ≤ i < r, then we can replace condition (a) by the following weaker one in the definition of a primitive pair: (a’) x_{0}—–y_{0}. 3.6 In the present paper, by a graph 𝔐, it always means that a set M of vertices together with a set of edges, where each edge is a two-elements subset of M, and each vertex is labelled by a subset of S.

Let 𝔐 and 𝔐′ be two graphs with their vertex sets M and M′. They are said to be isomorphic (note that we call it quasi-isomorphic in [22] owing to the different definition of a graph), written 𝔐 ≅ 𝔐′, if there exists a bijective map η from the set M to the set M′ satisfying the following conditions.

(1) The labelling of w is the same as that of η(w) for any w ∈ M.

(2) For w, z ∈ M, {w, z} is an edge of 𝔐 if and only if {η(w), η(z)} is an edge

of 𝔐′. This is an equivalence relation on graphs. 3.7 We define a graph 𝔐(x) associated to an element x ∈ W_{a} as follows. Its vertex set is M(x). Its edge set consists of all two-elements subsets {y, z} ⊂ M(x) with y, z two neighboring terms of a string. Each vertex y ∈ M(x) is labelled by the set R(y).

Note that unlike the definition given in [22], we do not label the edges of a graph here. Clearly, for any x ∈ W_{a}, the graph 𝔐(x) is always connected.

A left cell graph associated to an element x ∈ W_{a}, written 𝔐_{L}(x), is by definition a graph, whose vertex set M_{L}(x) consists of all left cells Γ of W_{a} with Γ ∩ M(x) ≠ ∅. Two vertices Γ, Γ′ ∈ M_{L}(x) are joined by an edge, if there are two elements y ∈ M(x) ∩ Γ and y′ ∈ M(x) ∩ Γ′ such that {y, y′} is an edge of 𝔐(x). Each vertex Γ of 𝔐_{L}(x) is labelled by the common labelling of elements of M(x) ∩ Γ (This makes sense by [10, Proposition 2.4]). Clearly, the graph 𝔐_{L}(x) is always connected. 3.8 A subgraph 𝔐 of 𝔐(x) (x ∈ W_{a}) is said to be essential, if there exists an isomorphism η from 𝔐 to 𝔐_{L}(x) such that each vertex y of 𝔐 is contained in the left cell η(y).

It is easily seen that when a subgraph 𝔐 of 𝔐(x) is essential, its vertex set must

Left Cells in Affine Weyl Group 13

be distinguished. In particular, the graph 𝔐(x) itself is essential if and only if its vertex set M(x) is distinguished. But it should be careful that in general there does not always exist a subgraph of 𝔐(x) which is essential (Some counter-examples could be found in the two-sided cell W_{(3)} of the affine Weyl group W_{a}(D̃_{4}) and in W_{(1)} of W_{a}(Ã_{ℓ}), ℓ > 1). However, we shall see that for any x ∈ W_{a}(C̃_{4}), there always exists some essential subgraph of 𝔐(x) containing x as its vertex. 3.9 By a path in the graph 𝔐(x), we mean a sequence of vertices z_{0}, z_{1}, …, z_{t} in M(x) such that {z_{i−1}, z_{i}} is an edge of 𝔐(x) for any i, 1 ≤ i ≤ t. Two elements x, x′ ∈ W_{a} have the same generalized τ-invariant, if for any path z_{0} = x, z_{1}, …, z_{t} in the graph 𝔐(x), there is a path z′_{0} = x′, z′_{1}, …, z′_{t} in 𝔐(x′) with R(z′_{i}) = R(z_{i}) for every i, 0 ≤ i ≤ t, and if the same condition holds when interchanging the roles of x with x′. 3.10 It may happen that for two elements x, y ∈ W_{a} with x ∼_{L} y, the graphs 𝔐(x) and 𝔐(y) are not isomorphic (take x = s_{0} and y = s_{1}s_{0} in W_{a}(C̃_{4}) for example). But we have the following result.

Proposition. (a) The elements in the same left cell of W_{a} have the same generalized τ-invariant.

(b) If x ∼_{L} y in W_{a}, then the left cell graphs 𝔐_{L}(x) and 𝔐_{L}(y) are isomorphic.

The assertion (a) is well-known (see [22, Proposition 4.2]). Then (b) follows from Theorem 2.1 and Proposition 3.1 readily.

The above result allows us to talk about the generalized τ-invariant of a left cell of W_{a}, which is by definition the generalized τ-invariant of any element in this left cell. 3.11 We state some well-known results concerning the Bruhat order of a Coxeter system (W, S) which will be useful in performing Process (C) on a set.

(a) Let y ≤ w in W. Then for any reduced form w = s_{1}s_{2} ⋯ s_{r} with s_{i} ∈ S, there is a subsequence i_{1}, i_{2}, ⋯, i_{t} of 1, 2, ⋯, r such that y = s_{i_{1}}s_{i_{2}} ⋯ s_{i_{t}} is a reduced expression of y.

(b) Suppose J = L(w) for w ∈ W. Then there is some x ∈ W with w = w_{J} ·x and 14 Jian-yi Shi

ℓ(w) = ℓ(w_{J}) + ℓ(x).

Now let w ∈ W be with J = L(w). By (b), we can find a reduced expression w = s_{1}s_{2} ⋯ s_{r}, s_{i} ∈ S, with w_{J} = s_{1}s_{2} ⋯ s_{t}, where t = ℓ(w_{J}). Denote w_{j} = s_{1}s_{2} ⋯ s_{j} for t ≤ j ≤ r. Let P_{j} be the set of all elements y with y ≤ w_{j} and L(y) ⊇ J. Then P_{t} = {w_{J}}. Suppose that the set P_{k} has been found for t ≤ k < r. Then by (a), we have

P_{k+1} = P_{k} ⋃{ xs_{k+1} | x ∈ P_{k}, s_{k+1} ∉ R(x)}.

This provides a recurrence procedure to find all the elements y with y ≤ w and L(y) ⊇ L(w) for any given w ∈ W.

§4. l.c.r. sets and left cell graphs in two-sided cells of W_{a}(C̃_{4}). 4.1 We shall apply Algorithm 2.7 to find an l.c.r. set, together with the corresponding left cell graphs, in each two-sided cell Ω of W_{a} = W_{a}(C̃_{4}). Let us first choose the starting sets P of the algorithm. From the nature of the algorithm, it is preferred (but not necessary) to choose the elements x of the form w_{I}, I ⊂ S, for the set P whenever it is possible. Let P_{i} be the set of all the elements of W_{(i)} of the form w_{I}. Then we have the following table.

i  P_{i}  i  P_{i}
0  {e}  6  {w_{123}}
1  {s_{0}, s_{1}, s_{2}, s_{3}, s_{4}}  8  {w_{0134}}
2 {w_{02}, w_{03}, w_{04}, w_{13}, w_{14}, w_{24}} 9 {w_{012}, w_{234}}
3  {w_{024}, w_{12}, w_{23}}  10 {w_{0124}, w_{0234}}
4  {w_{023}, w_{124}, w_{01}, w_{34}}  16 {w_{0123}, w_{1234}}
5  {w_{013}, w_{014}, w_{034}, w_{134}}

Each set W_{(i)} (i ∈ {0, 1, 2, 5, 6, 8, 9, 10, 16}) consists of a single two-sided cell. For such a set W_{(i)}, we shall take P_{i} as the starting set of the algorithm. The set W_{(3)} (resp. W_{(4)}) contains two two-sided cells. We shall take a one-element subset of P_{i} as the starting set of the algorithm.

For any z ∈ W_{a}, we denote by Ω(z) (resp. Γ(z)) the two-sided cell (resp. the left cell) of W_{a} containing z.

Left Cells in Affine Weyl Group 15

4.2 The case W_{(0)} is trivial and so we shall always assume i > 0 for W_{(i)}. In applying the algorithm, we shall first deal with the two-sided cell W_{(16)}, then W_{(10)}, W_{(9)}, W_{(8)}, W_{(6)}, W_{(5)}, Ω(w_{023}), W_{(4)} \ Ω(w_{023}), Ω(w_{12}), W_{(3)} \ Ω(w_{12}), W_{(2)} and W_{(1)} in turn, where X \ Y = {x ∈ X | x ∉ Y } for any sets X, Y.. The reason for taking such an order is to make it easier in performing Processes (B) and (C), in particular in the determination of the a-values of the elements occurring in the intermediate steps of these two processes.

Let ψ be the automorphism of W_{a}(C̃_{4}) which sends s_{i} to s_{4−i} for 0 ≤ i ≤ 4. Then it is clear that ψ stabilizes the sets W_{(i)}, i ≥ 0, and induces a permutation on the set of left (resp. right, resp. two-sided) cells of W_{a} in each W_{(i)}.

We shall use the notation i for the simple reflection s_{i} (0 ≤ i ≤ 4) in the subsequent discussion. 4.3 W_{(16)} is the lowest two-sided cell of W_{a}. It is known that an element of W_{a} is in W_{(16)} if and only if its alcove form has no zero entry (see 1.7,(7)). It is also known that there are totally |W_{0}| left cells of W_{a} in W_{(16)} each of which is associated to a sign type (see [20, Theorem 1.1 and Corollary 1.2]). Let x = 3210123 · w_{0124} and y = 1234321 · w_{0234}. Then we see from their alcove forms that the elements x, y, w_{0123} and w_{1234} are all in the set W_{(16)}. The graphs 𝔐(x), 𝔐(y), 𝔐(w_{0123}) and 𝔐(w_{1234}) are isomorphic to those in Fig.s 16, 17, 18 and 19, respectively ( Fig.s mentioned here and later will be displayed at the end of this section ). The vertices x, y, w_{0123}, w_{1234} are labelled by 0124 , 0234 , 0123 , 1234 respectively in the corresponding graphs. We see that the sign types associating to the elements of the union M = M(x) ∪ M(y) ∪ M(w_{0123}) ∪ M(w_{1234}) are all different. This implies that the above four graphs are all essential and that M is an l.c.r. set of W_{(16)} by the fact |M| = |W_{0}| = 384. 4.4 W_{(10)} is a single two-sided cell of W_{a}. The graph 𝔐(w_{0124}) is isomorphic to that in Fig. 16, which is essential by Proposition 3.10. The element w_{0234} does not belong to any left cell of W_{a} in M_{L}(w_{024}) since there is no vertex of 𝔐(w_{0124}) labelled by 0234 . By the fact ψ(w_{0124}) = w_{0234}, we see that the graph 𝔐(w_{0234}) is essential (see Fig. 17.). The left cell set M_{L}(w_{0124}) is disjoint to M_{L}(w_{0234}) again by Proposition 16 Jian-yi Shi

3.10. By applying Algorithm 2.7, we see that the union M(w_{0124}) ∪ M(w_{0234}) is A-, B- and C-saturated and hence forms an l.c.r. set of the two-sided cell W_{(10)}. 4.5 W_{(9)} is a single two-sided cell of W_{a}. There are two vertices of 𝔐(w_{012}) labelled by 012 (resp. 0 ). This fact, together with 1.7, (5),(8) and Propositions 3.4, 3.10, implies that the graph 𝔐(w_{012}) is not essential and that the left cell graph 𝔐_{L}(w_{012}) should be that in Fig. 14 with the vertex Γ(w_{012}) labelled by 012 . Since there is no vertex of 𝔐_{L}(w_{012}) labelled by 234 , the element w_{234} does not belong to any left cell of W_{a} in M_{L}(w_{012}). Since ψ(w_{012}) = w_{234}, we see that the left cell graph 𝔐_{L}(w_{234}) should be displayed as in Fig. 15 with Γ(w_{234}) the vertex labelled by 234 . By applying Algorithm 2.7, we can show that the union M_{L}(w_{012}) ∪ M_{L}(w_{234}) is the left cell set of W_{a} in the two-sided cell W_{(9)}. 4.6 W_{(8)} is a single two-sided cell of W_{a}. The graph 𝔐(w_{0134}) is isomorphic to that in Fig. 13, which is essential by Proposition 3.10. It can be shown by applying Algorithm 2.7 that the set M(w_{0134}) forms an l.c.r. set of W_{(8)}. 4.7 W_{(6)} is a single two-sided cell of W_{a}. The graph 𝔐(w_{123}) is infinite. By 1.7, (5),(8), we see that the set {w ∈ M(w_{123}) | R(w) = J} (J = {0}, {4} or {123}) is contained in some left cell of W_{a}. On the other hand, let x = w_{123} · 012024. Then the graph 𝔐(w_{123}) contains the following subgraph.

014 ; | ; 124 {— \atop —} 024 {— \atop —} 124 ; ^{|  |  |} ; 23 {— \atop —} 13 {— \atop —} 03 {— \atop —} 13 {— \atop —} 23 ; ^{|  |  |  |  |} ; 24 {— \atop —} 14 {— \atop —} 04 {— \atop —} 14 {— \atop —} 24 ; ^{|  |} ; 3  3  ,

where the vertex labelled by 014 is the element x. Let y = x20 and w = x · 21. Then y and w are two vertices of this subgraph, both labelled by 124 . We claim y ∼_{L} w. For, we have 210 · w = 12010 · y, denote this element by z. Then z is a common left extension of w and y (see 1.6). Let x_{1} = 210 · w_{123}. Then we see that z ∈ M(x_{1}) and x_{1}^{−1} ∈ M(w_{123}). This implies z ∈ W_{(6)}. Hence by 1.7,(3), we have y ∼_{L} z ∼_{L} w. From

Left Cells in Affine Weyl Group 17

these facts and by Proposition 3.4, we see that the left cell graph 𝔐_{L}(w_{123}) should be that in Fig. 12. Applying Algorithm 2.7, we see that M_{L}(w_{123}) is the left cell set of W_{a} in the two-sided cell W_{(6)}. 4.8 W_{(5)} is a single two-sided cell of W_{a}. The graph 𝔐(w_{013}) is infinite. By 1.7,(5), we know that the set {w ∈ M(w_{013}) | R(w) = J} is contained in some left cell of W_{a} for J = {0, 1, 3}, {0, 1, 4}, {0, 3, 4} or {1, 3, 4}. By Propositions 3.4 and 3.10, this fact tells us that the left cell graph 𝔐_{L}(w_{013}) should be that in Fig. 10. Since ψ(w_{013}) = w_{134}, we see that the left cell graph 𝔐_{L}(w_{134}) should be that in Fig.

11. The sets M_{L}(w_{013}) and M_{L}(w_{134}) are disjoint by Proposition 3.10. By applying Algorithm 2.7, we see that M_{L}(w_{013}) ∪ M_{L}(w_{134}) is the left cell set of W_{a} in the two-sided cell W_{(5)}. 4.9 There are two two-sided cells in W_{(4)}.

(a) First consider the two-sided cell Ω(w_{023}). The graph 𝔐(w_{023}) is isomorphic to that in Fig. 6, which is essential by Proposition 3.10. Let y = w_{023} · 12, y_{0} = y · 4. Then y ∈ M(w_{023}), and {y, y_{0}} is a primitive pair (see 3.5). So y_{0} ∼_{R} w_{023}. But we have R(y_{0}) = {1, 2, 4}. This implies y_{0} ∼_{L} w_{124} by 1.7,(5). Hence w_{124} ∈ Ω(w_{023}). Since ψ(w_{023}) = w_{124}, it implies from the above results that the graph 𝔐(w_{124}) is essential (see Fig. 7). It is seen easily by Proposition 3.10 that the left cell set M_{L}(w_{023}) is disjoint to M_{L}(w_{124}). By applying Algorithm 2.7, we see that the union M = M(w_{124}) ∪ M(w_{023}) is A-, B- and C-saturated. So M forms an l.c.r. set of the two-sided cell Ω(w_{023}).

(b) We have w_{01}, w_{34} ∉ Ω(w_{023}) since there is no vertex of 𝔐(w_{023}) and 𝔐(w_{124}) labelled by 01 or 34 . This implies Ω(w_{01}) = W_{(4)} \ Ω(w_{023}) and w_{34} ∈ Ω(w_{01}). The graphs 𝔐(w_{01}) and 𝔐(w_{34}) are isomorphic to those in Fig.s 8, 9, respectively. By Proposition 3.10, we see that these two graphs are both essential and that the left cell set M_{L}(w_{01}) is disjoint to M_{L}(w_{34}). By applying Algorithm 2.7, we see that the set M(w_{01}) ∪ M(w_{34}) forms an l.c.r. set of the two-sided cell Ω(w_{01}). 4.10 There are two two-sided cells in W_{(3)}.

(a) First consider the two-sided cell Ω(w_{12}). The graph 𝔐(w_{12}) is essential by Proposition 3.10 (see Fig. 4). By applying Algorithm 2.7, we see that the set M(w_{12})

18 Jian-yi Shi

forms an l.c.r. set of Ω(w_{12}).

(b) We have w_{024} ∉ Ω(w_{12}) since no vertex of the graph 𝔐(w_{12}) is labelled by 024 . So Ω(w_{024}) = W_{(3)} \ Ω(w_{12}). The graph 𝔐(w_{024}) is essential by Proposition 3.10 (see Fig. 5). The set M(w_{024}) forms an l.c.r. set of the two-sided cell Ω(w_{024}) by applying Algorithm 2.7. 4.11 By 1.7,(5) and Propositions 3.4, 3.10, we see that the graph 𝔐(w_{02}) is not essential and that the left cell graph 𝔐_{L}(w_{02}) is displayed as in Fig. 3. We have by applying Algorithm 2.7 that the set M_{L}(w_{02}) is the left cell set of W_{a} in the two-sided cell W_{(2)}. 4.12 The graph 𝔐(s_{0}) is infinite. The left cell graph 𝔐_{L}(s_{0}) can be obtained easily from 𝔐(s_{0}) by 1.7, (5) (see Fig.2.). 4.13 We have got all the left cell graphs of the two-sided cells W_{(i)}, i ∈ {1, 2, 5, 6, 9}. By a close observation of the related graphs, we see that for any left cell graph 𝔐_{L}(x) of W_{(i)} (i ∈ {1, 2, 5, 6, 9}), there exists some subgraph of the corresponding graph 𝔐(x) which is isomorphic to 𝔐_{L}(x) and contains x as its vertex. Therefore we have obtained an l.c.r. set for any of these two-sided cells of W_{a}. On the other hand, we have got an l.c.r. set for each remaining two-sided cell of W_{a} which is presented as the vertex set of certain essential graphs of the form 𝔐(x). Thus we have actually got an l.c.r. set and the left cell graphs for any two-sided cell of W_{a}. 4.14 The following are all the left cell graphs of W_{a}(C̃_{4}) obtained in the present section.

∅  \begin{matrix}0 & & & & 4 \\ | & & & & | \\ 1 & {— \atop —} & 2 & {— \atop —} & 3 \end{matrix}  3 {— \atop —} 24 {— \atop —} 14 {— \atop —} 04 ; ^{|  |  |} ; 4  13 {— \atop —} 03 ; | ; 2  02 ; | ; 0 {— \atop —} 1

Fig. 1.  𝔐_{L}(e)  Fig. 2.  𝔐_{L}(s_{0})  Fig. 3.  𝔐_{L}(w_{04})

\begin{matrix}1 {— \atop —} 02 {— \atop —} 12 ; ^{|  |} ; 2 {— \atop —} 13 {— \atop —} 03 {— \atop —} 13 {— \atop —} 23 ; ^{|  |  |  |} ; 3 {— \atop —} 24 {— \atop —} 14 {— \atop —} 04 {— \atop —} 14 {— \atop —} 24 ; ^{|  |  |  |  |} ; 4  13 {— \atop —} 03 {— \atop —} 13  3 ; ^{|  |} ; 2  02  2 ; | ; 0 {— \atop —} 1 & 04 {— \atop —} 03 {— \atop —} 024 ; ^{|  |  |} ; 3 {— \atop —} 24 {— \atop —} 14 {— \atop —} 13 {— \atop —} 14 ; ^{|  |  |  |} ; 4  04 {— \atop —} 03 {— \atop —} 04 ; | ; 2  02 ; | ; 0 {— \atop —} 1 \\ Fig. 4.  𝔐_{L}(w_{12}) & Fig. 5.  𝔐_{L}(w_{024}) \end{matrix}

\begin{matrix}\begin{aligned}& & 023 & {— \atop —} & 024 & {— \atop —} & 03 \\ & & | & & | & & | \\ 12 & {— \atop —} & 13 & {— \atop —} & 14 & {— \atop —} & 13 & {— \atop —} & 2 \\ | & & | & & | & & | \\ 02 & {— \atop —} & 03 & {— \atop —} & 04 & {— \atop —} & 03 & {— \atop —} & 02 \\ | & & & & & & & & | \\ 1 & & & & & & 0 & {— \atop —} & 1 \end{aligned} & \begin{aligned}& & 124 & {— \atop —} & 024 & {— \atop —} & 14 \\ & & | & & | & & | \\ 23 & {— \atop —} & 13 & {— \atop —} & 03 & {— \atop —} & 13 & {— \atop —} & 2 \\ | & & | & & | & & | \\ 24 & {— \atop —} & 14 & {— \atop —} & 04 & {— \atop —} & 14 & {— \atop —} & 24 \\ | & & & & & & & & | \\ 3 & & & & & & 4 & {— \atop —} & 3 \end{aligned} \\ Fig. 6.  𝔐_{L}(w_{023}) & Fig. 7.  𝔐_{L}(w_{124}) \end{matrix}

\begin{matrix}\begin{aligned}& & 23 & {— \atop —} & 24 & {— \atop —} & 3 \\ & & | & & | \\ 12 & {— \atop —} & 13 & {— \atop —} & 14 & {— \atop —} & 13 & {— \atop —} & 2 \\ | & & | & & | & & | \\ 02 & {— \atop —} & 03 & {— \atop —} & 04 & {— \atop —} & 03 & {— \atop —} & 02 \\ | & & & & & & & & | \\ 01 & & & & & & 0 & {— \atop —} & 1 \end{aligned} & \begin{aligned}& & 12 & {— \atop —} & 02 & {— \atop —} & 1 \\ & & | & & | \\ 23 & {— \atop —} & 13 & {— \atop —} & 03 & {— \atop —} & 13 & {— \atop —} & 2 \\ | & & | & & | & & | \\ 24 & {— \atop —} & 14 & {— \atop —} & 04 & {— \atop —} & 14 & {— \atop —} & 24 \\ | & & & & & & & & | \\ 34 & & & & & & 4 & {— \atop —} & 3 \end{aligned} \\ Fig. 8.  𝔐_{L}(w_{01}) & Fig. 9.  𝔐_{L}(w_{34}) \end{matrix}

\begin{matrix}3 ; | ; 23 {— \atop —} 24 ; ^{|  |} ; 124 {— \atop —} 13 {— \atop —} 14 ; ^{|  |  |} ; 013 {— \atop —} 014 {— \atop —} 024 {— \atop —} 03 {— \atop —} 04 ; | ; 02  023 {— \atop —} 024 {— \atop —} 03 ; ^{|  |  |  |} ; 12 {— \atop —} 13 {— \atop —} 14 {— \atop —} 13 {— \atop —} 2 ; ^{|  |  |  |} ; 02 {— \atop —} 03 {— \atop —} 04 {— \atop —} 03 {— \atop —} 02 ; ^{|  |} ; 01  0 {— \atop —} 1 & 1 ; | ; 12 {— \atop —} 02 ; ^{|  |} ; 023 {— \atop —} 13 {— \atop —} 03 ; ^{|  |  |} ; 134 {— \atop —} 034 {— \atop —} 024 {— \atop —} 14 {— \atop —} 04 ; | ; 24  124 {— \atop —} 024 {— \atop —} 14 ; ^{|  |  |  |} ; 23 {— \atop —} 13 {— \atop —} 03 {— \atop —} 13 {— \atop —} 2 ; ^{|  |  |  |} ; 24 {— \atop —} 14 {— \atop —} 04 {— \atop —} 14 {— \atop —} 24 ; ^{|  |} ; 34  4 {— \atop —} 3 \\ Fig. 10.  𝔐_{L}(w_{013}) & Fig. 11.  𝔐_{L}(w_{134}) \end{matrix}

01 –— 02 {— \atop —} 03 {— \atop —} 04 {— \atop —} 03 {— \atop —} 02 {— \atop —} 1 {— \atop —} 0
| | | |
12 {— \atop —} 13 {— \atop —} 14 {— \atop —} 13 {— \atop —} 2
|  |  |  |
02  023 –— 024 –— 03  1
|  |
013  12 –— 02
|  |  |
014 –— 013  123 –— 124 –— 13 {— \atop —} 23  023 –— 13 –— 03
|  |  |  |  |  |  |  |  |
04 –— 03 –— 024  02  023 –— 024 –— 03  24  024 –— 14 –— 04
|  |  |  |  |  |  |  |  |
14 –— 13 –— 124  12 {— \atop —} 13 {— \atop —} 14 {— \atop —} 13  134 –— 034
|  |  |  |
24 –— 23  2  134
|  |
3  14 –— 024 –— 124  24
|  |  |  |
13 {— \atop —} 03 {— \atop —} 13 {— \atop —} 23
| | | |
4 {— \atop —} 3 {— \atop —} 24 {— \atop —} 14 {— \atop —} 04 {— \atop —} 14 {— \atop —} 24 –— 34
Fig. 12. 𝔐_{L}(w_{123})

\begin{aligned}01 & {— \atop —} & 02 & {— \atop —} & 03 & {— \atop —} & 04 & {— \atop —} & 03 & {— \atop —} & 02 & {— \atop —} & 1 \\ & & & & | & & | & & | & & | & & & & | \\ 23 & {— \atop —} & 24 & {— \atop —} & 3 & 12 & {— \atop —} & 13 & {— \atop —} & 14 & {— \atop —} & 13 & {— \atop —} & 2 & 0 \\ & & & | & | & & | & & | & & | \\ 04 & {— \atop —} & 14 & {— \atop —} & 04 & 02 & 023 & {— \atop —} & 024 & {— \atop —} & 03 \\ | & | & | & | \\ 03 & {— \atop —} & 13 & {— \atop —} & 03 & 013 \\ | & | & | & | \\ 024 & {— \atop —} & 124 & {— \atop —} & 024 & {— \atop —} & 014 \\ & & | & & | \\ & & 014 & & 013 & {— \atop —} & 02 \\ & & | & & & & | \\ 014 & {— \atop —} & 013 & {— \atop —} & {— \atop —} & {— \atop —} & {— \atop —} & {— \atop —} & 02 & {— \atop —} & 12 \\ | & & & & & & | \\ 024 & {— \atop —} & 03 & {— \atop —} & 04 & 123 & {— \atop —} & 023 & {— \atop —} & 13 \\ | & | & | & | & | & | \\ 124 & {— \atop —} & 13 & {— \atop —} & 14 & 124 & {— \atop —} & 024 & {— \atop —} & 14 \\ | & | & | & | & | & | \\ 024 & {— \atop —} & 023 & {— \atop —} & 024 & 13 & {— \atop —} & 03 & {— \atop —} & 13 \\ | & | & | & | \\ 0134 & 034 & 23 & {— \atop —} & 24 & 2 \\ | & | & | \\ 034 & {— \atop —} & 134 & {— \atop —} & 24 & 134 \\ & & | & & | \\ 024 & {— \atop —} & 023 & {— \atop —} & 024 & {— \atop —} & 034 \\ | & | & | & | \\ 14 & {— \atop —} & 13 & {— \atop —} & 14 & 134 \\ | & | & | & | \\ 04 & {— \atop —} & 03 & {— \atop —} & 04 & 24 & 124 & {— \atop —} & 024 & {— \atop —} & 14 \\ & & & | & | & & | & & | & & | \\ 12 & {— \atop —} & 02 & {— \atop —} & 1 & 23 & {— \atop —} & 13 & {— \atop —} & 03 & {— \atop —} & 13 & {— \atop —} & 2 & 4 \\ & & & & | & & | & & | & & | & & & & | \\ 34 & {— \atop —} & 24 & {— \atop —} & 14 & {— \atop —} & 04 & {— \atop —} & 14 & {— \atop —} & 24 & {— \atop —} & 3 \end{aligned} Fig. 13. 𝔐_{L}(w_{0134})

1 / |

3  12 –— 02
|  |  |
01  04{— \atop —}14 –— 24  023–— 13 –— 03
|  |  |  |  |  |  |
02 –— 12 –— 02 –—013  03{— \atop —}13 –—23  134–—034–—024 –— 14 –— 04
|  |  |  |  |  |  |  |  |
03 –— 13 –— 023  014–—024–—124  23 –— 24  023–— 13 –— 03
|  |  |  |  |  |  |  |
04 –— 14 –—024  013 123–—124 –—13  23  02{— \atop —} 12 –— 02
|  |  |  |  |  |  |  |  |  |
03 –— 13 –— 03  02  023–—024–— 03  13 –— 03  013  01
|  |  |  |  |  |  |  |  |
02  2  12 –— 13 –— 14 –— 13  124–—024–—014
|  |  |  |  |
1 {— \atop —} 0  2  123–—023 –– 013–—012
Fig. 14. 𝔐_{L}(w_{012})

3 / |

1  23 –— 24
|  |  |
34  04{— \atop —}03{— \atop —}02  124–— 13 –— 14
|  |  |  |  |  |  |
24 –— 23 –— 24 –—134  14{— \atop —}13 {— \atop —}12  013–—014–—024 –— 03 –— 04
|  |  |  |  |  |  |  |  |
14 –— 13 –—124 034–—024–—023  12{— \atop —}02  124–— 13 –— 14
|  |  |  |  |  |  |  |
04 –— 03 –—024 134 123–—023 –—13  12  24{— \atop —}23 –— 24
|  |  |  |  |  |  |  |  |  |
14 –— 13 –— 14  24  124–—024–— 14  13{— \atop —}14  134  34
|  |  |  |  |  |  |  |  |
24  2  23{— \atop —}13 –— 03{— \atop —}13  023–—024–—034
|  |  |  |  |
3 {— \atop —} 4  2  123–—124 –– 134–—234
Fig. 15. 𝔐_{L}(w_{234})

0124  012  01  1 ; ^{|  |  |  |} ; 013 {— \atop —} 023 {— \atop —} 123 –— 023 –— 013  02 {— \atop —} 03 {— \atop —} 04 {— \atop —} 03 –— 02 ; ^{|  |  |  |  |  |  |  |  |  |} ; 014 {— \atop —} 024 {— \atop —} 124 –— 024 –— 014  12 {— \atop —} 13 {— \atop —} 14 {— \atop —} 13 –— 12 ; ^{|  |  |  |  |  |  |  |} ; 03 {— \atop —} 13 {— \atop —} 03  013 –— 02  023 –— 024 –— 023 ; ^{|  |} ; 23  034 ; ^{|  |} ; 24 {— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}134 ; ^{|  |} ; 23  2  0134  034 ; ^{|  |  |  |} ; 0  13 {— \atop —} 03 {— \atop —} 13  024 –— 023 –— 024 ; ^{|  |  |  |  |  |  |} ; 1  124 –— 024 –— 14  124 {— \atop —} 13 {— \atop —} 14 ; ^{|  |  |  |  |  |  |} ; 02  2  123 –— 023 –— 13  024 {— \atop —} 03 {— \atop —} 04 ; ^{|  |  |  |} ; 03 {— \atop —} 13 {— \atop —} 03  02 {— \atop —} 12  014 ; ^{|  |  |  |  |  |} ; 04 {— \atop —} 14 {— \atop —} 024  013  02 {— \atop —} 013 –— 014 ; ^{|  |  |  |  |} ; 03 {— \atop —} 13 {— \atop —} 023  014 –— 024 –— 124 –— 024 ; ^{|  |  |  |  |  |} ; 02 {— \atop —} 12 {— \atop —} 02 –— 013  03 {— \atop —} 13 {— \atop —} 03 ; ^{|  |  |  |} ; 01  04 {— \atop —} 14 {— \atop —} 04 ; | ; 3 {— \atop —} 24 {— \atop —} 23 Fig. 16.  𝔐_{L}(w_{0124}) or 𝔐_{L}(3210123 · w_{0124})

0234  234  34  3 ; ^{|  |  |  |} ; 134 {— \atop —} 124 {— \atop —} 123 –— 124 –— 134  24 {— \atop —} 14 {— \atop —} 04 {— \atop —} 14 –— 24 ; ^{|  |  |  |  |  |  |  |  |  |} ; 034 {— \atop —} 024 {— \atop —} 023 –— 024 –— 034  23 {— \atop —} 13 {— \atop —} 03 {— \atop —} 13 –— 23 ; ^{|  |  |  |  |  |  |  |} ; 14 {— \atop —} 13 {— \atop —} 14  134{— \atop —} 24  124 –— 024 –— 124 ; ^{|  |} ; 12  014 ; ^{|  |} ; 02 {— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}013 ; ^{|  |} ; 12  2  0134  014 ; ^{|  |  |  |} ; 4  13 {— \atop —} 14 {— \atop —} 13  024 –— 124 –— 024 ; ^{|  |  |  |  |  |  |} ; 3  023 –— 024 –— 03  023 {— \atop —} 13 {— \atop —} 03 ; ^{|  |  |  |  |  |  |} ; 24  2  123 –— 124 –— 13  024 {— \atop —} 14 {— \atop —} 04 ; ^{|  |  |  |} ; 14 {— \atop —} 13 {— \atop —} 14  24 {— \atop —} 23  034 ; ^{|  |  |  |  |  |} ; 04 {— \atop —} 03 {— \atop —} 024  134  24 {— \atop —} 134 {— \atop —}034 ; ^{|  |  |  |  |} ; 14 {— \atop —} 13 {— \atop —} 124  034 –— 024 –— 023 –— 024 ; ^{|  |  |  |  |  |} ; 24 {— \atop —} 23 {— \atop —} 24 –— 134  14 {— \atop —} 13 {— \atop —} 14 ; ^{|  |  |  |} ; 34  04 {— \atop —} 03 {— \atop —} 04 ; | ; ! 1 {— \atop —} 02 {— \atop —} 12 Fig. 17.  𝔐_{L}(w_{0234}) or 𝔐_{L}(1234321 · w_{0234})

1  01  012  0124 ; ^{|  |  |  |} ; 02 {— \atop —} 03 {— \atop —} 04 {— \atop —}03{— \atop —} 02  013 –— 023 –—123–—023–— 013 ; ^{|  |  |  |  |  |  |  |  |  |} ; 12 {— \atop —} 13 {— \atop —} 14 {— \atop —}13{— \atop —} 12  014 –— 024 –—124–—024–— 014 ; ^{|  |  |  |  |  |  |  |} ; 023 {— \atop —} 024 –—023  02 {— \atop —}013  03 {— \atop —}13{— \atop —}03 ; ^{|  |} ; 034  23 ; ^{|  |} ; 134 {— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}24 ; ^{|  |} ; 034  0134  2  23 ; ^{|  |  |  |} ; 0123  024 –—023–— 024  13 {— \atop —} 03 {— \atop —}13 ; ^{|  |  |  |  |  |  |} ; 0124  14 {— \atop —}13{— \atop —} 124  14 –— 024 –—124 ; ^{|  |  |  |  |  |  |} ; 013  0134  04 {— \atop —}03{— \atop —} 024  13 –— 023 –—123 ; ^{|  |  |  |} ; 023 {— \atop —} 024 {— \atop —} 023  013–— 014  12 ; ^{|  |  |  |  |  |} ; 123 {— \atop —} 124 {— \atop —} 13  02  013 {— \atop —} 02 {— \atop —} 12 ; ^{|  |  |  |  |} ; 023 {— \atop —} 024 {— \atop —} 03  12{— \atop —} 13 {— \atop —} 14 {— \atop —} 13 ; ^{|  |  |  |  |  |} ; 013 {— \atop —} 014 {— \atop —} 013 {— \atop —}02  023 –— 024 –— 023 ; ^{|  |  |  |} ; 012  123 –— 124 –— 123 ; | ; 0234 –— 134 –— 034 Fig. 18.  𝔐_{L}(w_{0123})

3  34  234  0234
|  |  |  |
24 {— \atop —} 14 {— \atop —} 04 {— \atop —}14 –— 24  134–—124–—123–—124–— 134
|  |  |  |  |  |  |  |  |  |
23 {— \atop —} 13 {— \atop —} 03 {— \atop —}13 –— 23  034–—024–—023–—024–— 034
|  |  |  |  |  |  |  |
124 {— \atop —} 024 –—124  24 –—134  14{— \atop —}13{— \atop —}14
|  |
014  12
|  |
013 {— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}{— \atop —}02
|  |
014  0134  2  12
|  |  |  |
1234  024 –—124–— 024  13{— \atop —}14{— \atop —}13
|  |  |  |  |  |  |
0234  03 {— \atop —}13{— \atop —}023  03 –—024–—023
|  |  |  |  |  |  |
134  0134  04 {— \atop —}14{— \atop —} 024  13 –—124–—123
|  |  |  |
124 {— \atop —} 024 {— \atop —} 124  134–— 034  23
|  |  |  |  |  |
123 {— \atop —} 023 {— \atop —} 13  24  134{— \atop —}24{— \atop —}23
|  |  |  |  |
124 {— \atop —} 024 {— \atop —} 14  23{— \atop —} 13 {— \atop —}03{— \atop —}13
|  |  |  |  |  |
134 {— \atop —} 034 {— \atop —} 134 {— \atop —}24  124 –—024–—124
|  |  |  |
234  123 –—023–—123
|
0124–—013–—014
Fig. 19. 𝔐_{L}(w_{1234})

§5. Some comments.

In this section, we shall make some observations and comments on the left cells of W_{a}(C̃_{k}), k = 2, 3, 4 by the results we have got so far. Based on these, we shall further consider the possible generalization to the more general affine Weyl groups. 5.1 Let us start with recalling some concepts and known results. A partition of ℓ ∈ ℕ is by definition a sequence of integers λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{r} > 0 with ∑_{i=1}^{r} λ_{i} = ℓ. We

Left Cells in Affine Weyl Group 27

shall not distinguish between two such sequences which differ only by a string of zeros at the end. Let Λ_{2ℓ+1} be the set of all partitions of 2ℓ + 1. Let λ = (λ_{1}, λ_{2}, ⋯, λ_{r}), μ = (μ_{1}, μ_{2}, ⋯, μ_{t}) be in Λ_{2ℓ+1}. We say that μ is dual to λ if for any i ≥ 1, μ_{i} is the number of parts λ_{j}, 1 ≤ j ≤ r, with λ_{j} ≥ i. We say that λ dominates μ, written λ ≥ μ, if ∑_{i=1}^{k} λ_{i} ≥ ∑_{i=1}^{k} μ_{i} for any k ≥ 1. This defines a partial order, called the natural order, on the set Λ_{2ℓ+1}. Let \overline{Λ}_{2ℓ+1} be the set of all partitions in Λ_{2ℓ+1} each of whose even parts occurs with even multiplicity. Let G(B_{ℓ}) be the complex adjoint algebraic group of type B_{ℓ}, ℓ ≥ 2. Then it is well known that the unipotent conjugacy classes of G(B_{ℓ}) are parametrized by elements of \overline{Λ}_{2ℓ+1} such that if u_{λ}, u_{μ} are two unipotent classes of G(B_{ℓ}) parametrized by λ, μ, respectively, then u_{λ} ⊆ \overline{u}_{μ} if and only if λ ≤ μ, where \overline{u}_{μ} is the closure of u_{μ} in the variety of unipotent elements of G(B_{ℓ}) (see [3, Chapter 13]). 5.2 For λ ∈ \overline{Λ}_{9}, let u_{λ} be the corresponding unipotent conjugacy class of G(B_{4}). Let Ω_{λ} = c(u_{λ}) be the two-sided cell of W_{a} = W_{a}(C̃_{4}) associated to u_{λ} under the Lusztig map in Theorem 1.8 (see [14]). We denote by n_{λ} the number of left cells of W_{a} contained in Ω_{λ}, and by A(λ) = C(u)/C(u)^{∘} the component group of the centralizer of an element u ∈ u_{λ}, the latter makes sense since it is independent of the choice of u up to isomorphism. Then by the result of §4 and by Theorem 1.8, we have the following table.

λ n_{λ}  Ω_{λ}  A(λ)  λ  n_{λ} Ω_{λ} A(λ)
(9) 1  W_{(0)}  1  (3^{2}1^{3}) 56 W_{(5)} S_{2}
(71^{2}) 5  W_{(1)}  S_{2}  (32^{2}1^{2}) 72 W_{(6)} S_{2}
(531) 11 W_{(2)}  S_{2}^{2}  (2^{4}1) 96 W_{(8)}  1
(52^{2}) 24 Ω(w_{12})  1  (31^{6}) 144 W_{(9)} S_{2}
(4^{2}1) 16 Ω(w_{024})  1  (2^{2}1^{5}) 192 W_{(10)} 1
(51^{4}) 32 Ω(w_{01}) S_{2}  (1^{9}) 384 W_{(16)} 1
(3^{3}) 32 Ω(w_{023})  1

Here the notation (32^{2}1^{2}) (for example) in the table stands for a partition with five parts 3,2,2,1,1. Thus the total number of left cells in W_{a}(C̃_{4}) is 1065. 5.3 Let G be a simple algebraic group of adjoint type over ℂ. According to Bala-Carter Theorem, there is a bijective map between unipotent conjugacy classes of 28 Jian-yi Shi

G and G-classes of pairs (L, P_{L′}), where L is a Levi subgroup of G and P_{L′} is a distinguished parabolic subgroup of the semisimple part L′ of L. The unipotent class corresponding to the pair (L, P_{L′}) contains the dense orbit of P_{L′} on its unipotent radical (see [3, Theorem 5.9.6]).

For λ ∈ \overline{Λ}_{2ℓ+1}, let (L, P_{L′}) be the pair associated to the unipotent conjugacy class u_{λ} of G(B_{ℓ}) and let W_{L} be the Weyl group of L′. Then from the existing datum, we assert that for any λ ∈ \overline{Λ}_{2ℓ+1} with ℓ = 2, 3, 4 or a(Ω_{λ}) ≤ 4, the number n_{λ} of left cells of W_{a}(C̃_{ℓ}) in the two-sided cell Ω_{λ} is equal to |W_{0}|/|W_{L}| if and only if A(λ) is trivial (see 5.2, §6 and [11; 4; 5; 16]). In fact, the parts of any λ ∈ \overline{Λ}_{2ℓ+1} can be listed in the following way: α_{1}, α_{1}, α_{2}, α_{2}, ⋯, α_{r}, α_{r}, 2β_{1} + 1, 2β_{2} + 1, ⋯, 2β_{t} + 1 with α_{1} ≥ α_{2} ≥ ⋯ ≥ α_{r} > 0 and β_{1} > β_{2} > ⋯ > β_{t} ≥ 0. In the associated pair (L, P_{L′}) to u_{λ}, we know that L′ (and hence W_{L}) has type A_{α_{1}−1} + ⋯ + A_{α_{r}−1} + B_{∑ β_{i}+[t/2]}, where [t/2] is the largest integer not exceeding t/2. We know that the group A(λ) is trivial if and only if λ has exactly one distinct odd part (see [3, Chapter 13]). Thus the above assertion can be checked easily from the existing datum. I conjecture that this result holds also for any two-sided cell of W_{a}(C̃_{ℓ}), ℓ ≥ 2.

Again by the existing datum, we observe that the analogous result also holds for the affine Weyl groups of types Ã_{ℓ} (ℓ ≥ 1), B̃_{3}, B̃_{4}, F̃_{4} and for all the two-sided cells Ω of the affine Weyl groups of type B̃_{ℓ} (ℓ ≥ 2) with a(Ω) ≤ 4. But it is false for the affine Weyl groups of types D̃_{ℓ} (ℓ ≥ 4), Ẽ_{7}, Ẽ_{8} (see [17; 9; 27; 25; 4; 16; 6; 7; 23]).

Note that the above phenomena were predicted implicitly by Lusztig in his conjecture on the number of left cells in a two-sided cell of an affine Weyl group (see [1]). 5.4 It has been shown in [24] that the Lusztig map u ⟶ c(u) from the set of unipotent conjugacy classes of G(B_{k}) (k = 2, 3, 4) to the set of two-sided cells of W_{a}(C̃_{k}) is order-preserving: u ⊆ \overline{u′} if and only if c(u) ≤_{LR} c(u′) (see 1.8, the tables in 5.2 and in §6). For a two-sided cell Ω of W_{a}, let T (Ω) be the set of all subsets I of S such that I = L(w) for some w ∈ Ω. Then we have the following fact in the groups W_{a}(C̃_{k}) (k = 2, 3, 4): two two-sided cells Ω, Ω′ ≠ {e} satisfy the relation Ω ≤_{LR} Ω′ if and only if T (Ω) ⊇ T (Ω′). I conjecture that this result holds in any affine Weyl

Left Cells in Affine Weyl Group 29

group. We can say even more for the groups W_{a}(C̃_{k}), k = 2, 3, 4. Let us introduce some more notations.

Let S = {s_{0}, s_{1}, ⋯, s_{ℓ}} be the Coxeter generator set of the group W_{a}(C̃_{ℓ}) whose indices are compatible with the corresponding extended Dynkin diagram ( which is obtained from the Dynkin diagram in 1.5 by adding one more node labelled by 0 to the diagram which joins the node labelled by 1 by a double arrowed edge). For any J ⊂ S, a decomposition J = J_{1} ∪ J_{2} ∪ ⋯ ∪ J_{t} is called standard, if the following conditions are satisfied.

(a) Each J_{i}, 1 ≤ i ≤ t, is not empty and the corresponding Dynkin subdiagram is connected.

(b) For any pair i, j, 1 ≤ i < j ≤ t, we have J_{i}∩J_{j} = ∅ and the Dynkin subdiagram corresponding to J_{i} ∪ J_{j} is not connected.

(c) |J_{1}| ≥ |J_{2}| ≥ ⋯ ≥ |J_{t}|. where we stipulate that a standard decomposition of an empty set is the trivial one. Now assume that J = J_{1} ∪ J_{2} ∪ ⋯ ∪ J_{t} is a standard decomposition of a proper subset J ⊂ S. For any i with J_{i} ∩ {s_{0}, s_{ℓ}} = ∅, we are given two equal integers a_{i1} = a_{i2} = |J_{i}| + 1. On the other hand, suppose J_{j} ∩ {s_{0}, s_{ℓ}} ≠ ∅ for some j. Then we are given an integer a_{j} equal to 2|J_{j}| + 1 if J_{k} ∩ {s_{0}, s_{ℓ}} = ∅ for any k < j, and equal to 2|J_{j}| if otherwise. We denote by ζ(J) the dual partition of (λ_{1}, λ_{2}, ⋯, λ_{r}) ∈ Λ_{2ℓ+1}, where the sequence λ_{1}, λ_{2}, ⋯, λ_{r} is obtained by arranging all the numbers a_{i1}, a_{i2}, a_{j}, ∀i, j, in decreasing order, and adding some parts 1’s at the end whenever it is necessary. It is clear that ζ(J) does not depend on the chosen standard decomposition of J and so it is well defined. Thus we have defined a map ζ from the set of all proper subsets of S to the set Λ_{2ℓ+1}. It can be shown that for any subset K of Λ_{2ℓ+1}, there exists a unique element of \overline{Λ}_{2ℓ+1} dominated by all the elements in K and being maximum with this property. Then the following result can be checked directly from the existing datum.

Proposition. Let Ω be a two-sided cell of the group W_{a}(C̃_{k}), k = 2, 3, 4. Let λ(Ω) be the unique maximal element of \overline{Λ}_{2k+1} dominated by all the elements in the set ζ(T (Ω)) ⊂ Λ_{2k+1}. Then the partition λ(Ω) parametrizes the unipotent class of the 30 Jian-yi Shi

algebraic group G of type B_{k} corresponding to Ω under the Lusztig map.

This proposition gives an explicit combinatorial description of the Lusztig map for the groups W_{a}(C̃_{k}), k = 2, 3, 4. I conjecture that it remains valid for all the groups W_{a}(C̃_{ℓ}), ℓ ≥ 2. 5.5 Proposition 5.4 encourages us to propose one more conjecture which is concerned with the relation ∼_{LR} on elements of W_{a}(C̃_{ℓ}). For any w ∈ W_{a} = W_{a}(C̃_{ℓ}), ℓ ≥ 2, we define a set T (w) = {J ⊂ S | w = x · w_{J} · y, for some x, y ∈ W_{a}}. Let λ(w) be the unique maximal element of \overline{Λ}_{2ℓ+1} dominated by all the elements in the set ζ(T (w)) ⊂ Λ_{2ℓ+1}.

Conjecture. Let x, y ∈ W_{a}(C̃_{ℓ}). Then x ∼_{LR} y if and only if λ(x) = λ(y).

5.6 From the left cell graphs displayed in 4.14, we see that any left cell Γ of W_{a}(C̃_{4}) is determined uniquely by its generalized τ-invariant (see 3.9) except for the cases that there is some (and hence any) element x ∈ Γ such that the graph 𝔐_{L}(x) is that in Fig. 16 or 17. But in these exceptional cases, we have a(Γ) ∈ {10, 16}. Then the alcove form of any element of Γ could tell us the actual value a(Γ): it is equal to 16 if no entry of the alcove form is zero, or 10 if otherwise (see 17, (7)), and hence the left cell Γ is determined uniquely. Therefore we have the following

Theorem. Let Γ be a left cell of the affine Weyl group W_{a}(C̃_{4}). If Γ is not in the lowest two-sided cell, then it is determined entirely by its generalized τ-invariant. On the other hand, if Γ is in the lowest two-sided cell, then it is determined by the corresponding sign type.

An analogous result also holds for the groups W_{a}(C̃_{2}) and W_{a}(C̃_{3}) (see §6.). One might expect that this also hold for all the affine Weyl groups W_{a}(C̃_{ℓ}), ℓ ≥ 2. 5.7 By closely observing all its left cell graphs, we have the following result for the group W_{a}(C̃_{4}).

Proposition. For any w ∈ W_{a}(C̃_{4}) not in the lowest two-sided cell, there is a vertex v with I = R(v) in the graph 𝔐(w) such that ℓ(w_{I}) = a(w).

This result, together with the result in 1.7, (7) concerning the lowest two-sided

Left Cells in Affine Weyl Group 31

cell, make it easier to determine the a-value of any element of the group W_{a}(C̃_{4}). Also, by [21, Proposition 5.12], this result enables us to find all the distinguished involutions of W_{a}(C̃_{4}) only by successively applying star operations on the elements w_{J}, J ⊂ S (see [13; 17] for the definitions of a distinguished involution and a star operation). It is known that the distinguished involutions play an important role in the representation theory of Coxeter groups and Hecke algebras and that finding these elements usually involves very complicated computation of Kazhdan-Lusztig polynomials. By the results of Lusztig and Bédard (see §6. or [12; 2]), we see that the above proposition remains valid if we replace the group W_{a}(C̃_{4}) by W_{a}(C̃_{k}), k = 2 or 3. Thus one might further expect the validity of this result for all the groups W_{a}(C̃_{ℓ}), ℓ ≥ 2. Unfortunately, this is not the case. By Theorem 1.8, we see that for any ℓ ≥ 5, there always exists some element w ∈ W_{a}(C̃_{ℓ}) such that a(w) ≠ ℓ(w_{I}) for any I ⊂ S and hence for such an element w, the conclusion of the above proposition should be false. 5.8 Let ψ be the unique non-trivial automorphism of the affine Weyl group W_{a}(C̃_{ℓ}) (ℓ ≥ 2) which preserves the Coxeter generator set S (see 4.2). Let 𝔐, 𝔑 be two graphs with M, N the corresponding vertex sets ( in the sense of 3.6). We say that the graph 𝔑 is opposed (resp. dual) to 𝔐, if there is a bijective map ϕ from the set M to N satisfying that for any x, y ∈ M,

(a) R(ϕ(x)) = S \ R(x) (resp. R(ϕ(x)) = ψ(R(x))).

(b) {x, y} is an edge of 𝔐 if and only if {ϕ(x), ϕ(y)} is an edge of 𝔑.

It is easily seen that if W_{(i)} ⊂ W_{a}(C̃_{ℓ}) consists of a single two-sided cell and has only one left cell graph, say 𝔐_{L}, then 𝔐_{L} must be self-dual. This is the case for the sets W_{(i)} ⊂ W_{a}(C̃_{4}) with i ∈ {0, 1, 2, 6, 8} (see Fig.s 1, 2, 3, 12, 13). The other self-dual left cell graphs of W_{a}(C̃_{4}) are in Fig.s 4 and 5. All the remaining displayed left cell graphs in 4.14 fall into six mutual dual pairs: {𝔐_{L}(w_{023}), 𝔐_{L}(w_{124})}, {𝔐_{L}(w_{01}), 𝔐_{L}(w_{34})}, {𝔐_{L}(w_{013}), 𝔐_{L}(w_{134})}, {𝔐_{L}(w_{012}), 𝔐_{L}(w_{234})}, { Fig. 16, Fig. 17 } and { Fig. 18, Fig. 19 }.

There is no self-opposed left cell graph in W_{a}(C̃_{4}). But there are just two pairs of mutual opposed left cell graphs: { Fig. 16, Fig. 19} and { Fig. 17, Fig. 18 }, where 32 Jian-yi Shi

all the left cell graphs in the lowest two-sided cell of W_{a}(C̃_{4}) are involved (The last statement should hold for any affine Weyl group). 5.9 We see that the automorphism ψ stabilizes each two-sided cell of W_{a}(C̃_{4}). This also holds for W_{a}(C̃_{2}) and W_{a}(C̃_{3}) (see §6.). As a consequence of the conjectures in 5.4 and 5.5, I expect that this is still the case for the groups W_{a}(C̃_{ℓ}), ℓ ≥ 5.

§6. Appendix.

Here we list all the left cell graphs, and some related results due to Lusztig and Bedard [2; 12] for the affine Weyl groups W_{a}(C̃_{2}) and W_{a}(C̃_{3}) (we omit the graph 𝔐_{L}(e) in each case since it is too trivial). Keep the notations as before. The indices of the related simple reflections are compatible with the corresponding extended Dynkin diagrams (see 1.5 and 5.4). 6.1 There are four two-sided cells in the group W_{a}(C̃_{2}), which are W_{(i)}, i = 0, 1, 2, 4. The non-travial left cell graphs of W_{a}(C̃_{2}) are as below.

\begin{matrix}0 {— \atop —} 1 {— \atop —} 2 & 02 ; | ; 0 {— \atop —} 1 {— \atop —} 2 & \begin{matrix}0 & & 01 \\ | & & | \\ 1 & {— \atop —} & 02 \end{matrix} & \begin{matrix}2 & & 12 \\ | & & | \\ 1 & {— \atop —} & 02 \end{matrix} \\ 𝔐_{L}(s_{0}) & 𝔐_{L}(w_{02}) & 𝔐_{L}(w_{01}) & 𝔐_{L}(w_{12}) \end{matrix}

We have the following table.

\begin{matrix}λ & n_{λ} & Ω_{λ} & A(λ) & λ & n_{λ} & Ω_{λ} & A(λ) \\ (5) & 1 & W_{(0)} & 1 & (2^{2}1) & 4 & W_{(2)} & 1 \\ (31^{2}) & 3 & W_{(1)} & S_{2} & (1^{5}) & 8 & W_{(4)} & 1 \end{matrix}

So there are sixteen left cells in W_{a}(C̃_{2}). 6.2 There are seven two-sided cells in the group W_{a}(C̃_{3}), which are W_{(i)}, i = 0, 1, 2, 3, 4, 5, 9. The non-trivial left cell graphs of W_{a}(C̃_{3}) are listed as follows.

\begin{matrix}\begin{matrix}0 & & 3 \\ | & & | \\ 1 & {— \atop —} & 2 \end{matrix} & 3 {— \atop —} 2 {— \atop —} 13 ; | ; 0 {— \atop —} 1 {— \atop —} 02 {— \atop —} 03 \\ 𝔐_{L}(s_{0}) & 𝔐_{L}(w_{02}) \end{matrix}

\begin{matrix}1  3 ; ^{|  |} ; 12 {— \atop —} 02  2 ; ^{|  |  |} ; 2 {— \atop —} 13 {— \atop —} 03 {— \atop —} 13 ; | ; 0 {— \atop —} 1 {— \atop —} 02 & 01 ; | ; 12 {— \atop —} 02 ; ^{|  |} ; 2 {— \atop —} 13 {— \atop —} 03 ; | ; 0 {— \atop —} 1 {— \atop —} 02 & 23 ; | ; 12 {— \atop —} 13 ; ^{|  |} ; 1 {— \atop —} 02 {— \atop —} 03 ; | ; 3 {— \atop —} 2 {— \atop —} 13 \\ 𝔐_{L}(w_{12}) & 𝔐_{L}(w_{01}) & 𝔐_{L}(w_{23}) \end{matrix}

\begin{matrix}013 {— \atop —} 02 {— \atop —} 12 {— \atop —} 02 {— \atop —} 01 ; ^{|  |  |} ; 03 {— \atop —} 13 {— \atop —} 03 ; ^{|  |} ; 2  02 ; | ; 0 {— \atop —} 1 & 023 {— \atop —} 13 {— \atop —} 12 {— \atop —} 13 {— \atop —} 23 ; ^{|  |  |} ; 03 {— \atop —} 02 {— \atop —} 03 ; ^{|  |} ; 1  13 ; | ; 3 {— \atop —} 2 \\ 𝔐_{L}(w_{013}) or 𝔐_{L}(21012 · w_{013}) & 𝔐_{L}(w_{023}) or 𝔐_{L}(12321 · w_{023}) \end{matrix}

\begin{matrix}2 {— \atop —} 13 {— \atop —} 03 {— \atop —} 13 {— \atop —} 23 ; ^{|  |  |} ; 12 {— \atop —} 02 {— \atop —} 12 ; ^{|  |} ; 013  13 ; | ; 123 {— \atop —} 023 & 1 {— \atop —} 02 {— \atop —} 03 {— \atop —} 02 {— \atop —} 01 ; ^{|  |  |} ; 12 {— \atop —} 13 {— \atop —} 12 ; ^{|  |} ; 023  02 ; | ; 012 {— \atop —} 013 \\ 𝔐_{L}(w_{123}) & 𝔐_{L}(w_{012}) \end{matrix}

We have the following table.

λ n_{λ} Ω_{λ} A(λ)  λ  n_{λ} Ω_{λ} A(λ)
(7) 1 W_{(0)} 1  (31^{4}) 18 W_{(4)} S_{2}
(51^{2}) 4 W_{(1)} S_{2} (2^{2}1^{3}) 24 W_{(5)} 1
(3^{2}1) 7 W_{(2)} S_{2}  (1^{7}) 48 W_{(9)} 1
(32^{2}) 12 W_{(3)} 1

Thus the number of left cells of W_{a}(C̃_{3}) is 114.

References

1. T. Asai et al., Open problems in algebraic groups, Proc. Twelfth International Symposium, Tohoku Univ., Japan (1983), 14.

2. R. Bédard:, Cells for two Coxeter groups, Comm. in Alg. 14(7) (1986), 1253– 1286.

3. R. W. Carter, Finite Groups of Lie Type: Conjugacy Classes and Complex Characters, Wiley Series in Pure and Applied Mathematics, John Wiley, London, 1985.

4. Chen Chengdong, Two-sided cells in affine Weyl groups, Northeastern Math. J. 6 (1990), 425–441.

5. Chen Chengdong, Left cells with a-value 4 in the affine Weyl group of type C̃_{n}, Bull. London Math. Soc. 26 (1994), 582–592.

6. Chen Chengdong, Left cells with a-value 4 in the affine Weyl group of type B̃_{n}, Comm. in Algebra 23(7) (1995), 2499-2515.

7. Chen Chengdong, Left cells with a-value 4 in the affine Weyl group of type D̃_{n}, Chinese Math. Ann. 16A:3 (1995), 375-380.

8. Chen Yu and Jian-yi Shi, Left cells in the Weyl group of type E_{7}, Preprint.

9. Du Jie:, The decomposition into cells of the affine Weyl group of type B̃_{3}, Comm. in Algebra 16(7) (1988), 1383–1409.

10. D. Kazhdan & G. Lusztig:, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165–184.

11. G. Lusztig, Some examples in square integrable representations of semisimple padic groups, Trans. of the AMS 277 (1983), 623–653.

12. G. Lusztig:, Cells in affine Weyl groups, in “ Algebraic Groups and Related Topics ”, pp255-287,, Advanced Studies in Pure Math., Kinokunia and North Holland, 1985.

13. G. Lusztig:, Cells in affine Weyl groups, II, J. Alg. 109 (1987), 536–548.

14. G. Lusztig:, Cells in affine Weyl groups, IV, J. Fac. Sci. Univ. Tokyo Sect. IA. Math. (2)36 (1989), 297–328.

Left Cells in Affine Weyl Group 35

15. G. Lusztig & Xi Nan-hua, Canonical left cells in affine Weyl groups, Adv. in Math. 72 (1988), 284-288.

16. Rui Hebing, Left cells in affine Weyl groups of types other than Ã_{n} and G̃_{2}, J. Algebra 175 (1995), 732-756.

17. Jian-yi Shi:, The Kazhdan-Lusztig cells in certain affine Weyl groups, Lect. Notes in Math. vol.1179, Springer-Verlag, Berlin, 1986.

18. Jian-yi Shi:, Alcoves corresponding to an affine Weyl group, J. London Math. Soc. (2)35 (1987), 42–55.

19. Jian-yi Shi:, A two-sided cell in an affine Weyl group, J. London Math. Soc. (2)36 (1987), 407–420.

20. Jian-yi Shi:, A two-sided cell in an affine Weyl group, II, J. London Math. Soc. (2)37 (1988), 253–264.

21. Jian-yi Shi, The joint relations and the set D_{1} in certain crystallographic groups, Adv. in Math. 81(1) (1990), 66-89.

22. Jian-yi Shi, Left cells in affine Weyl groups, Tohoku J. Math. 46(1) (1994), 105-124.

23. Jian-yi Shi, Left cells of the affine Weyl group W_{a}(D̃_{4}), Osaka J. Math. 31(1) (1994), 27-50.

24. Jian-yi Shi, The partial order on two-sided cells of certain affine Weyl groups, J. Algebra 179(2) (1996), 607-621.

25. Jian-yi Shi, Left cells in the affine Weyl group of type F̃_{4}, to appear in J. Algebra.

26. Tong Chang-qing, Left cells in the Weyl group of type E_{6}, Comm. in Algebra 23 (13) (1995), 5031-5047.

27. Zhang Xin-fa, Cells decomposition in the affine Weyl group W_{a}(B̃_{4}), Comm. in Algebra 22(6) (1994), 1955-1974.