Knuth relations for the hyperoctahedral groups

DOI 10.1007/s10801-008-0148-x

Knuth relations for the hyperoctahedral groups

Thomas Pietraho

Received: 27 March 2008 / Accepted: 22 July 2008 / Published online: 22 August 2008

© Springer Science+Business Media, LLC 2008

Abstract C. Bonnafé, M. Geck, L. Iancu, and T. Lam have conjectured a description of Kazhdan-Lusztig cells in unequal parameter Hecke algebras of typeB which is based on domino tableaux of arbitrary rank. In the integer case, this generalizes the work of D. Garfinkle. We adapt her methods and construct a family of operators which generate the equivalence classes on pairs of arbitrary rank domino tableaux described in the above conjecture.

Keywords Unequal parameter Iwahori-Hecke algebra·Domino tableaux· Robinson-Schensted algorithm

1 Introduction

In [6], D. Garfinkle classified the primitive spectrum of the universal enveloping al- gebra for a complex semisimple Lie algebra in typesB andC. By using annihilators of highest weight modules, this problem is reduced to studying equivalence classes in the corresponding Weyl groupWn. The existence of a Robinson-Schensted bijec- tion between elements ofWnand same shape pairs of standard domino tableaux with ndominos [4] turns this into an essentially combinatorial problem. In fact, Garfin- kle’s classification shows that two elements inW_nare equivalent iff their left domino tableaux are related by moving through a set of open cycles, a certain combinatorial operation. The key step of this classification was achieved by studying the action of the wall-crossing operators arising from the generalτ-invariant, as defined in [21], which were shown to be generators for both equivalences.

When interpreted in terms of cells of the equal parameter Hecke algebra of typeB, the above work takes on a new meaning.

T. Pietraho (

Bowdoin College, Brunswick, ME 04011, USA e-mail:tpietrah@bowdoin.edu

In the 1980s, G. Lusztig extended the cell theory to Hecke algebras with unequal parameters; see [12] for an exposition. For Weyl groups of typeB, cell theory then depends on an additional parameters, which reduces to the equal parameter case whens=1; Garfinkle’s work classified cells in exactly this latter setting. As observed in [20], Garfinkle’s bijection also admits an extension

G_r:W_n→SDT_r(n)×SDT_r(n)

to a bijection between W_n and same shape pairs of standard domino tableaux of rankr. It is reasonable to hope that the above two parameters can be linked and that a similar classification of cells is possible in this more general case. In fact:

Conjecture ([3]) When s is a positive integer, two elements ofW_n lie in the same left cell if and only if their left domino tableaux of ranks−1 are related by moving through a set of open cycles.

This is of course true whens=1 and has been verified in the asymptotic case s≥n, when the bijectionG_s−1degenerates to the generalized Robinson-Schensted correspondence of [18], see [2]. Among finite Coxeter groups, cells in unequal pa- rameter Hecke algebras have been classified in the dihedral groups and typeF4 by Lusztig [12] and Geck [7]. Only the problem of their classification in typeBremains.

We will say that two elements of the hyperoctahedral groupWn are in the same irreducible combinatorial left cell of rankrif they share the same left domino tableau under the Robinson-Schensted mapG_r, and in the same reducible combinatorial left cell of rankrif their rankrleft domino tableaux are related by moving through an open cycle. The previous conjecture can be restated as:

Conjecture ([3]) Whensis a positive integer, left cells inWncoincide with reducible combinatorial left cells of ranks−1.

Inspired by Garfinkle’s approach in the equal parameter case, the main goal of this paper is to construct a set of generators for the reducible combinatorial left cells in arbitrary rank which draws on the notion of the generalizedτ-invariant used in the equal parameter case. Such a setΛ^r+1is constructed in Section3. The main theorem then can be stated as:

Theorem 3.9 The family of operatorsΛ^r+1generates the reducible combinatorial left cells of rankr. More precisely, given wand v∈Wn whose rank r left domino tableaux differ only by moving through a set of non-core open cycles, there is a se- quence of operators inΛ^r+1sendingwtov.

This result falls into a family of similar theorems on generating sets for equiv- alence classes of standard tableaux, Garfinkle’s work not withstanding. In typeA, a family of operators generating a similar equivalence for the symmetric group on standard Young tableaux appears in [11] and is known as the set of Knuth relations.

Domino tableaux whose shapes are also partitions of nilpotent orbits in typesB,C, or Dcorrespond to the so-called orbital varieties. Their classification has been carried

out by W. M. McGovern in [13] by relying on a similar set of generators found in [9], see also [14]. The work of C. Bonnafé and L. Iancu in the asymptotic parameter case relies on finding a generating set for cells defined in terms of standard bitableaux.

Finally, very recently M. Taskin has independently found another set of generators in the arbitrary rank case, see [19].

Combinatorial cells in the unequal parameter Hecke algebras in typeBhave also appeared in the work of I. Gordon and M. Martino, where it is shown that nilpotent points of the Calogero-Moser space correspond to the partitions arising from arbitrary rank domino tableaux [8].

This paper is organized as follows. In Section 2, we define the necessary objects and catalogue basic results. Section 3 defines the family of operatorsΛ^r+1and Sec- tion 4, in addition to showing that reducible combinatorial cells are stable under their action, describes this action on pairs of domino tableaux. In Section 5, we verify the main result, and leave the proof of a few crucial lemmas to Sections 6 and 7.

2 Definitions and preliminaries

2.1 Robinson-Schensted algorithms

The hyperoctahedral group W_n of rank n is the group of permutations of the set {±1,±2, . . . ,±n}which commute with the involutioni→ −i. It is the Weyl group of typeB_n. We will writew∈W_nin one-line notation as

w=(w(1) w(2) . . . w(n)).

A Young diagram is a finite left-justified array of squares arranged with non- increasing row lengths. We will denote the square in rowi and column j of the diagram byS_i,jso thatS1,1is the uppermost left square in the Young diagram below:

Definition 2.1 Letr ∈N andλ be a partition of a positive integerm. A domino tableau of rankr and shape λ is a Young diagram of shape λ whose squares are labeled by integers in such a way that 0 labelsS_ij iffi+j < r+2, each element of some setMlabels exactly two adjacent squares, and all labels increase weakly along both rows and columns. A domino tableau is standard iffM= {1, . . . , n}for somen.

We will writeSDT_r(n)for the set of standard domino tableaux withndominos. The set of squares labeled by 0 will be called the core ofT.

Following [4] and [20], we describe the Robinson-Schensted bijections G_r:W_n→SDT_r(n)×SDT_r(n)

between elements ofWn and same-shape pairs of rankrstandard domino tableaux.

The algorithm is based on an insertion mapαwhich, given an entryw(j )in the one- line notation forw∈W_n, inserts a domino with labelw(j )into a domino tableau.

This insertion map is similar to the usual Robinson-Schensted insertion map and is precisely defined in [4](1.2.5). To construct the left tableau, start withT₁(0), the only tableau inSDT_r(0). DefineT1(1)=α(w(1), T1(0))and continue inductively by letting

T1(k+1)=α

w(k+1), T1(k) .

The left domino tableauT1(n)will be standard and of rankr. The right tableau keeps track of the sequence of shapes of the left tableaux; we defineT2(n)to be the unique tableau so thatT₂(k)∈SDT_r(k) has the same shape as T₁(k) for all k≤n. The Robinson-Schensted map is then defined byG_r(w)=(T₁(n), T₂(n)).We will also often use the notation(T₁(n−1), T2(n−1))=(T₁(n), T₂(n)).

2.2 Cycles and extended cycles

We briefly recall the definition of a cycle in a domino tableau as well as a number of related notions which we will use later.

For a standard domino tableauT of arbitrary rankr, we will say the squareS_ij is fixed wheni+j has the opposite parity asr, otherwise, we will call it variable. IfS_ij is variable andiis odd, we will saySij is of typeX; ifiis even, we will saySij is of typeW. We will writeD(k, T )for the domino labeled by the positive integerkinT andsupp D(k, T )will denote its underlying squares. Writelabel Sij for the label of the squareS_ij inT . We extend this notion slightly by lettinglabel S_ij = 0 if eitheri orj is less than or equal to zero, andlabel S_ij= ∞ifiandj are positive butS_ij is not a square inT .

Definition 2.2 Suppose that supp D(k, T )= {S_ij, S_i+1,j}or {S_i,j−1, S_ij}and the square S_ij is fixed. Define D(k) to be a domino labeled by the integer k with supp D(k, T )equal to

1. {Sij, Si−1,j}ifk < label Si−1,j+1

2. {S_ij, S_i,j+1}ifk > label S_i−1,j+1

Alternately, suppose thatsupp D(k, T )= {S_ij, S_i−1,j}or{S_i,j+1, S_ij}and the square S_ij is fixed. Definesupp D(k, T )to be

1. {Sij, Si,j−1}ifk < label Si+1,j−1

2. {Sij, Si+1,j}ifk > label Si+1,j−1

Definition 2.3 The cyclec=c(k, T )throughkin a standard domino tableauT is a union of labels ofT defined by the condition thatl∈cif either

1. l=k,

2. supp D(l, T )∩supp D(m, T )= ∅for somem∈c, or 3. supp D(l, T )∩supp D(m, T )= ∅for somem∈c.

We will identify the labels contained in a cycle with their underlying dominos.

Starting with a standard domino tableau T of rank r containing a cycle c, it is possible to define a new domino tableauMT (T , c) by replacing every domino

D(l, T )∈cby the shifted dominoD(l, T )defined above. This operation changes the labels of the variable squares incwhile preserving the labels of all of the fixed squares ofT. In fact, if we pick a labellof a square inT, the definition of a cycle together with [4](1.5.27) imply that moving throughc(l, T )is in some sense the min- imal transformation ofT which changes the label of the variable square ofD(l, T ), maintains the labels of all of the fixed squares ofT, and results in a standard domino tableau.

The shape ofMT (T , c)either equals the shape ofT, or one square will be re- moved (or added to its core) and one will be added. In the former case, the cyclecis called closed; otherwise, it is called open. If moving throughcadds a square to the core, we will callca core open cycle; the other open cycles will be called non-core.

For an open cyclecof a tableauT, we will writeS_b(c)for the square that has been removed or added to the core by moving throughc. Similarly, we will writeS_f(c) for the square that is added to the shape ofT. Note thatS_b(c)andS_f(c)are always variable squares.

Definition 2.4 A variable squareS_ijsatisfying the conditions that 1. neitherS_i,j+1norS_i+1,jlie inT, and

2. either

a) bothS_i−1,jandS_i,j−1lie inT, or

b) eitherS_i−1,jlies inT andj=1 orS_i,j−1lies inT andi=1,

will be called a hole if it is of typeWand a corner if it is of typeX. It will be called full ifSij∈T and empty otherwise.

LetUbe a set of cycles inT. Because the order in which one moves through a set of cycles is immaterial by [4](1.5.29), we can unambiguously writeMT (T , U )for the tableau obtained by moving through all of the cycles in the setU.

Moving through a cycle in a pair of same-shape tableaux is somewhat problem- atic, as it may result in a pair of tableaux which is not same-shape. We require the following definition.

Definition 2.5 Consider(T1, T2)a pair of same-shape domino tableaux,ka label in T1, andcthe cycle inT1throughk. The extended cyclec˜ofk inT1 relative toT2

is a union of cycles inT1which containsc. Further, the union of two cyclesc1∪c2

lies inc˜if either one is contained inc˜and, for some cycled inT2,S_b(d)coincides with a square ofc1andS_f(d)coincides with a square ofMT (T1, c2). The symmetric notion of an extended cycle inT2relative toT1is defined in the natural way.

For an extended cycle c˜ in T₂ relative to T₁, write c˜=c₁∪. . .∪c_m and let d₁, . . . , d_mbe cycles inT₁such thatS_b(c_i)=S_b(d_i)for alli,S_f(d_m)=S_f(c₁), and S_f(d_i)=S_f(c_i+1)for 1≤i < m. The uniond˜=d₁∪ · · · ∪d_mis an extended cycle inT₁relative toT₂called the extended cycle corresponding toc. Symmetrically,˜ c˜is the extended cycle corresponding tod˜.

We can now define a moving through operation for a pair of same-shape domino tableaux. Writebfor an ordered pair(c,˜ d)˜ of extended cycles in(T₁, T₂)that corre-

spond to each other. DefineMT ((T₁, T₂), b)to equal (MT (T1,c), MT (T˜ 2,d)).˜

It is clear that this operation produces another pair of same-shape domino tableaux.

Speaking loosely, we will often refer to this operation as moving through either of the extended cyclesc˜ord.˜ Note that if the cyclecis closed, thenc˜=cand moving through a pair of tableaux boils down to the operation(MT (T₁, c), T₂).

Definition 2.6 We will say that a set of squares in a domino tableau is boxed iff it is entirely contained in a set of squares of the form

{S_ij, S_i+1,j, S_i,j+1, S_i+1,j+1}

whereS_ij must be of typeX. A set will be called unboxed if it is not boxed.

Boxing is well-behaved with respect to cycles. If cis a cycle in T, then all of its underlying dominos are either boxed or unboxed. Furthermore, moving through a domino changes its boxing, and consequently, the boxing of all the dominos in the cycle containing it. The same holds for all of the dominos in an extended cycle of a same-shape tableau pair.

We will say that two sets of squares are adjacent in a tableauT if there are two squares, one in each set, which share a common side. One set of squares inT will be said to be below another if all of its squares lie in rows strictly below the rows of the squares of the other set. The notion of above is defined similarly. We will often call the squares underlying a domino its position, and say that a position is extremal if its removal from a Young diagram results in another Young diagram corresponding to a partition of the same rank.

2.3 Combinatorial cells

Definition 2.7 Considerw, v∈Wnof typeBnand fix a non-negative integerrletting G_r(w)=(T₁, T₂)andG_r(v)=(T˜₁,T˜₂). We will say thatwandvare

1. in the same irreducible combinatorial left cell of rankrifT₂= ˜T₂, and

2. in the same reducible combinatorial left cell of rankrif there is a setU of non- core open cycles inT2such thatT˜2=MT (T2, U ).

We will say thatw andv are in the same irreducible and reducible combinatorial right cells iff their inverses lie in the same irreducible and reducible combinatorial left cells, respectively.

Whenr≥n−1, the situation is somewhat simpler; there are no non-core open cycles implying that combinatorial left cells are determined simply by right tableaux.

Furthermore, by the main result of [15], for these values ofrall combinatorial cells are actually independent ofr.

Reducible combinatorial left cells of rankrcan also be described in terms of right tableaux of ranksrandr+1. A similar characterization holds for combinatorial right cells.

Theorem 2.8 ([16]) Reducible combinatorial left cells of rankrin the Weyl group of typeB_nare generated by the equivalence relations of having the same right tableau in either rankror rankr+1.

In what follows we will focus on reducible combinatorial right cells. Since our generalizations of the Robinson-Schensted algorithmG_r behave well with respect to inverses by merely changing the order of the two tableaux, all the statements can be easily modified to apply to reducible combinatorial left cells as well.

3 Knuth relations

The purpose of this section is to define the operators on the hyperoctahedral group Wnwhich generate the reducible combinatorial right cells of rankr. We first recount the situation in typeAfor the symmetric groupSn.

3.1 Type A

Writing the elements ofSn in one-line notation, the Knuth relations on Sn are the transformations

(w(1) w(2) . . . w(j−1) w(j+1) w(j ) . . . w(n)) which transpose thejth and(j+1)st entries ofw∈S_nwhenever (i) j ≥2 andw(j−1)lies betweenw(j )andw(j+1), or (ii) j < n−1 andw(j+2)lies betweenw(j )andw(j+1).

Every Knuth relation preserves the Robinson-Schensted left tableauT1(w) of w.

However, even more can be said:

Theorem 3.1 ([11]) Knuth relations generate the combinatorial left cells inS_n. More precisely, givenwandvwithT₁(w)=T₁(v), there is a sequence of Knuth relations sendingwtov.

Aiming to adapt this theorem to the hyperoctahedral groups, we begin by rephras- ing the Knuth relations first in terms of the length function onS_n, and then again in terms of theτ-invariant.

The groupS_nis a Weyl group of a complex semisimple Lie algebragof typeA_n−1

with Cartan subalgebrah. LetΠ_n= {α1, α2, . . . , α_n−1}be a set of simple roots for a choice of positive roots in the root system(g,h)and writes_α for the simple reflec- tion corresponding toα∈Π_n. We viewS_nas the group generated by the above sim- ple reflections and let:S_n→Zbe the corresponding length function onS_n. If we identify the reflections_αj with the transposition interchanging thejth and(j+1)st entries of the permutation corresponding tow∈S_n, then the Knuth relations onS_n are the transformations takingwtows_αj.Noting that(ws_αj) < (w)exactly when w(j ) > w(j+1), the domain for the Knuth relations is the set ofw∈S_nsatisfying

(i) (ws_αi) < (w) < (ws_αj) < (ws_αjs_αi), or (ii) (ws_αi) > (w) > (ws_αj) > (ws_αjs_αi)

for someαi∈Πn. This condition is satisfied only whenαiandαj are adjacent simple roots, that is, wheni=j±1.

Armed with this restatement of the Knuth conditions, following [21] we define the τ-invariant forSnand a related family of operators.

Definition 3.2 WriteW =S_n. Forw∈W, letτ (w)= {α∈Π_n|(ws_α) < (w)}.

Given simple rootsαandβ inΠ_n, let

D_αβ(W )= {w∈W|α /∈τ (w)andβ∈τ (w)}. Whenαandβare adjacent roots, defineTαβ:Dαβ(W )→Dβα(W )by

T_αβ(w)= {ws_α, ws_β} ∩D_βα(W ).

When defined, the operators T_αβ are single-valued and preserve the Robinson- Schensted left tableauT₁(w)ofw. These so-called wall-crossing operators also ap- pear as the “star operator” in [10]. The following is a direct consequence of the result on Knuth relations:

Corollary 3.3 The family of operators T_αβ:D_αβ(W )→D_βα(W ) generates the combinatorial left cells inS_n. More precisely, givenw and v withT1(w)=T1(v), there is a sequence ofT_αβoperators sendingwtov.

That combinatorial left cells forSn coincide with Kazhdan-Lusztig left cells is shown in [10] using A. Joseph and D. Vogan’s results on the primitive spectrum of semisimple Lie algebras. A direct proof of this fact using entirely combinatorial methods has subsequently appeared, see [1].

3.2 Type B

In order to define similar relations for the hyperoctahedral groups, we mimic the final construction in typeA. The groupWnis a Weyl group of a complex semisimple Lie algebragof typeBnwith Cartan subalgebrah. Let{1, . . . n}be a basis forh^∗such that if we defineα₁=1andα_i=_i−_i−1,then

Πn= {α₁, α2, . . . , αn}

is the set of simple roots for some choice of positive roots⁺(g,h). While this choice of simple roots is not standard, we adopt it to obtain somewhat cleaner statements and reconcile our work with [6].

We modifyΠ_n slightly to include certain non-simple roots. For i≤n, letα_i= α₁ +α₂+. . .+α_i and whenkis a non-negative integer write

Π_n^k= {α₁, α₂, . . . α_min(n,k) , α₂, . . . α_n}.

Further, writes_i for the simple reflections_αi+1 andt_i for the reflections_α

i. We realize W_nas a set of signed permutations onnletters by identifyings_i with the transposition (1 2. . . i+1i . . . n)andt_i with the element(1 2. . .−i . . . n).

The generating set for reducible combinatorial right cells will be drawn out of the following three types of operators:

Definition 3.4 Forw∈Wn, and a non-negative integerk, let τ^k(w)= {α∈Π_n^k|(ws_α) < (w)}.

Given rootsαandβ inΠ_n^k defineD_αβ^k (W_n)= {w|α /∈τ^k(w)andβ∈τ^k(w)}.The operatorT_αβ^k :D^k_αβ(W_n)→D^k_βα(W_n)is defined by

T_αβ^k (w)= {ws_α, ws_β} ∩D^k_βα(W_n).

The above definitions add the parameterkto the standard notions of root system Π_n,τ-invariantτ (w), domainsD_αβ, and the wall-crossing operatorsT_αβas defined explicitly, say in [5]. Our definitions coincide with these standard ones when the value of this parameter isk=1.

When the set{α, β}contains roots of unequal length, the operatorT_αβ^k may be two- valued. The next definitions are an attempt to remedy this by splitting this operator into two new ones:T_IN^k andT_SC^k . Henceforth, we will reserve the notationT_αβ to meanT_αβ⁰ andD_αβto meanD_αβ⁰ , in which case the operators are single-valued.

Definition 3.5 We will sayw∈D^k_IN(W_n)if for some{δ, β} = {α_k+1, α_k}, we have w∈D^k_δβ(W_n)andws_k∈D^k_βδ(W_n).

DefineT_IN^k forw∈D^k_IN(Wn)byT_IN^k (w)=wsk.

Definition 3.6 We will sayw∈D^k_SC(Wn)if for some choice of{δi, βi} = {αi+1, α_i} for everyi≤k, we have

w∈D^k_δ

iβ_i(W_n)andwt_i∈D_β^k

iδ_i(W_n) ∀i≤k.

DefineT_SC^k forw∈D^k_SC(Wn)byT_SC^k (w)=wt1.

To phrase the above in more digestible terms, we note that inWnthe length func- tion satisfies(ws_j) < (w)iffw(j ) > w(j+1), and(wt_j) < (w)iffw(j ) <0.

Armed with this characterization, the domains and actions for the three types of op- erators which we will be interested in can be described more succinctly.

Tαβ: wlies inDαβ(W )for{α, β} = {αj+1, αj+2}wheneverw(j+1)is either greater than or smaller than bothw(j )andw(j+2);T_αβthen interchanges the smallest and largest entries amongw(j ), w(j +1), andw(j+2).

T_IN^k : w∈D_IN^k (W )iffw(k)andw(k+1)are of opposite sign. The op- eratorT_IN^k interchanges thekth andk+1st entries ofw.

T_SC^k : w∈D_SC^k (W )iff|w(1)|>|w(2)|> . . . >|w(k+1)|. The operator T_SC^k changes the sign ofw(1).

Definition 3.7 For an integerk, we define a set of operators Λ^k= {T_αβ|α, β∈Π_n⁰} ∪ {T_INⁱ |i≤k} ∪ {T_SC^k }.

This is the sought-after set of generators for reducible combinatorial right cells of arbitrary rank. The following are our two main results:

Theorem 3.8 The operators inΛ^r+1preserve reducible combinatorial left cells of rankr. IfS∈Λ^r+1, andw∈Wnis in the domain ofS, then the Robinson-Schensted left domino tableauxT₁(w)andT₁(Sw)of rankrdiffer only by moving through a set of non-core open cycles inT1(w).

Theorem 3.9 The family of operatorsΛ^r+1generates the reducible combinatorial left cells of rankr. More precisely, givenwandv∈Wnwhose Robinson-Schensted left domino tableauxT₁(w)andT₁(v)of rankrdiffer only by moving through a set of non-core open cycles, there is a sequence of operators inΛ^r+1sendingwtov.

These results have previously been obtained in two special cases. In her work on the primitive spectrum of the universal enveloping algebras in typesBandC, Devra Garfinkle constructed a generating set for the reducible combinatorial cells of rank zero [6]. Additionally, C. Bonnafé and L. Iancu obtained a generating set for combi- natorial left cells in the so-called asymptotic case whenr≥n−1. The generating set Λ^r+1proposed above for domino tableaux of arbitrary rank generalizes both of these results.

Theorem 3.10 (D. Garfinkle) The reducible combinatorial left cells of rank zero are generated by the family of operatorsT_αβ¹ whereαandβ are adjacent simple roots inΠn.

At first glance, the set Λ¹ is not exactly Garfinkle’s generating set. The latter contains multi-valued operatorsT¹

α₁α2andT¹

α2α₁. However, we note that the combined action and domains ofT¹

α₁α2 andT¹

α2α₁ agree precisely with those ofT_SC¹ andT_IN¹ ∈ Λ¹. The operators T_SC¹ andT_IN¹ merely split up Garfinkle’s original multi-valued operators.

Theorem 3.11 (C. Bonnafé and L. Iancu) When the rankr≥n−1, the reducible and irreducible combinatorial left cells coincide. They are generated by the family of operatorsΛ^r+1=Λⁿ.

We note that in the asymptotic case, the operatorT_SC^r+1is not defined, so thatΛ^r+1 consists entirely of theT_αβandT_IN^k operators, as exhibited in [2].

It was observed in [17] that combinatorial right cells are in general not well- behaved with increasing rank. This phenomenon is readily explained by examining the composition ofΛ^r+1more closely. While increasingrexpands the family ofTIN

operators contained inΛ^r+1, it also diminishes the domain ofT_SC. The complicated behavior of right cells asrincreases is a manifestation of this interplay.

Recent work of M. Taskin finds a family of relations onW_n which generates the irreducible combinatorial left cells of rankr. Using the results of [16] which show that reducible combinatorial left cells are common refinements of irreducible ones, it is then possible to describe a set of generators of the reducible combinatorial left cells of rankrbased on Taskin’s work. This set; however, does not coincide withΛ_r+1, but can be shown to be equivalent. It would be desirable to use the methods of the current paper to produce results on irreducible cells; however, it seems to the author that the moving-through operation which changes the shape of the underlying tableau is very intricately intertwined with the method of proof and the necessary unentanglement does not appear to be an easy task.

4 Stability underΛ^r+1

The goal of this section is to prove Theorem3.8, showing that reducible right cells in rankrare invariant under the operators inΛ^r+1. We will rely on a decomposition ofW_n, which we describe presently. LetW_mbe the subgroup ofW_ngenerated by the reflections{s1, . . . , s_m−1, t1}and defineX_mⁿ to be the set ofx∈W_nwhich satisfy

0< x(1) < x(2) < . . . < x(m).

ThenXⁿ_mis a cross-section ofW_n/W_mand we can write everyw∈W_nas a product w=xwwithx∈X_mⁿ andw∈W_m. The following appears in [3].

Proposition 4.1 Ifx∈X_mⁿ andw, v∈W_mare in the same irreducible combinator- ial left cell of rankr, thenxwandxv∈Wnare in the same irreducible combinato- rial left cell of rankr.

Corollary 4.2 Ifx∈X_mⁿ andw, v∈W_m are in the same reducible combinatorial left cell of rankr, thenxwand xv∈W_n are in the same reducible combinatorial left cell of rankr.

Proof The main result of [16] shows that reducible combinatorial left cells of rank rare the least common refinements of irreducible combinatorial left cells of ranksr andr+1. Hence the corollary follows directly from the above proposition.

4.1 The operatorT_SC

We first examine the family of operatorsT_SC^k which, under appropriate circumstances, change the sign of the first entry ofw.

Proposition 4.3 The operatorT_SC^r+1preserves the irreducible and, consequently, the reducible combinatorial right cells of rankrinW_r+2.

Proof Considerw∈D_SC^r+1(W_r+2)so that

|w(1)|>|w(2)|> . . .|w(r+2)|.

Writev=w⁻¹andu=(T_SC^r+1(w))⁻¹.We will show that their right tableauxT₂(v) andT₂(u)agree. Note that the condition onwimplies|v(1)|>|v(2)|> . . .|v(r+2)| and the fact thatT_SC^r+1only changes the sign ofw(1)forces

1. v(i)=u(i)fori≤r+1, and 2. u(r+2)= −v(r+2)∈ {±1}.

If we write the positive entries invasa₁> . . . > a_pand the negative ones as−b₁<

. . . <−b_q, then the left tableau ofv before the insertion ofv(r+2)must have the form:

This is also the left tableau ofubefore the insertion ofu(r+2)and we point out that the corresponding right tableaux for bothuandv are the same. Ifa1> b1, then the insertion ofv(r+2)andu(r+2)into the above tableau yields either:

or

In either case, the same domino is added to their shared right tableau andT₂(v)= T₂(u). The proof is similar whena₁< b₁. Corollary 4.4 Whenn≥r+2, the operatorT_SC^r+1 preserves the irreducible and, consequently, the reducible, combinatorial left cells of rankrinW_n.

Proof For an elementw of the setD_SC^r+1(Wn), writew=xw∈X_n^r+2Wr+2. Then w∈D^r_SC⁺¹(W_r+2) and by Proposition 4.3, T_SC^r+1(w)and w share the same irre- ducible combinatorial left cell of rankr. SinceT_SC^r+1(w)=xT_SC^r+1(w)∈X_n^r+2W_r+2, Proposition4.1and Corollary4.2imply the same is true ofT_SC^r+1(w)andw.

Our final aim is to describe the action ofT_SC^r+1on the right tableau ofw. This is more or less captured in the proof of Proposition4.3, but we will attempt to be more precise. Considerw∈D_SC^r+1(W_n), writeT₂for the right tableauT₂(w)of rankr, and

defineT₂(r+2)to be the subtableau ofT₂which contains only dominos whose labels are less than or equal tor+2. Becausew∈D_SC^r+1(W_n),T₂(r+2)contains exactly the dominos adjacent to the core ofT₂ as well as the unique domino ofT₂ which shares its long edge with the long edge of one of the dominos adjacent to the core.

Furthermore,T₂(r+2)must have the form

or

whereα₁=r+2, noting thatpmay equal zero. By the proof of Proposition4.3,T_SC^r+1 acts onT₂(r+2)by interchanging one of its possible two forms of the same shape with the other. It is easy to see that the remaining dominos of the tableauxT₂and the right tableauT₂(T_SC^r+1(w))are the same, since both keep track of the subsequent insertions into the left tableauT1(w)(r+2)=T1(T_SC^k+1(w))(r+2).

Example 4.5 Considerw=(4,−3,−2,1)which lies inD_SC³ (W₄).ThenT_SC³ (w)= (−4,−3,−2,1)and

T₂(w)= and T₂(T_SC³ (w))=

On a final note, we observe that this description of the action ofT_SC^r+1reproduces the action of a portion of the multi-valuedT_α

1α2 operator detailed in [5](2.3.4) for the rank zero case.

4.2 The operatorsT_αβ

Given adjacent simple roots{α, β} = {α_j+1, α_j+2}, an operatorT_αβinterchanges the smallest and largest entries amongw(j ),w(j+1),andw(j+2).The following is a consequence of Proposition 3.10 in [3].

Proposition 4.6 The operatorsT_αβ preserve the irreducible and, consequently, the reducible combinatorial right cells of rankrinWn.

What is still required is a description of their action on right tableaux. We begin with an explicit description of their domains. Recall thatα_j+1∈τ (w)iff(ws_αj+1) <

(w)which occurs iffw(j ) > w(j+1). This condition is easily read off from the right tableauT₂(w). We will say thatk lies below l in a domino tableau iff every row containing a square of the domino labeledklies below every row of the domino

labeledl. Thenα_j+1∈τ (w)iffj+1 lies belowjinT₂(w). Unraveling the definition ofD_αβ(W ), we find that when{α, β} = {α_j+1, α_j+2},wlies in the domain ofT_αβiff in the tableauT_R(w)either:

1. j+1 lies belowj andj+2 does not lie belowj+1, or 2. j+1 does not lie belowj andj+2 lies belowj+1.

Two cases are necessary to describe the action ofT_αβ.

Case 1. In the following, letk=j+1 andl=j+2. If either one of the following four configurations of dominos appears inT2(w):

F1(j )= and F1(j )=

F2(j )= and F2(j )=

then the actionT_αβon the right tableau ofwswapsF_i(j )andF_i(j )withinT_R(w).

Case 2. If none of the above four configurations appear inT2(w)andw lies in the domainD_αβ(W_n), thenT_αβ acts by swapping either the dominos labeledj and j+1 orj+1 andj+2.

The proof that this description ofT_αβ on domino tableau accurately depicts the action ofT_αβdefined onW_nis not difficult. It appears as [5](2.1.19) in rank zero, and follows almost identically for higher rank tableaux.

4.3 The operatorsT_IN^k

The operatorT_IN^k interchanges the entriesw(k)andw(k+1)inwwhenever they are of opposite signs. The following is again a consequence of Proposition 3.10 in [3].

Proposition 4.7 Whenk≤r, the operatorT_IN^k preserves the irreducible and, conse- quently, the reducible combinatorial left cells of rankrinWn.

Slightly more is true:

Proposition 4.8 The operatorT_IN^r+1preserves the reducible combinatorial left cells of rankrinW_n.

Proof By Proposition4.7, the operatorT_IN^r+1preserves the irreducible combinatorial left cells of rankr+1 inW_n. Since reducible combinatorial left cells of rankr are the least common refinements of irreducible cells in ranksr andr+1, the result

follows.

Next, we describe the action ofT_IN^k on the left and right tableauxT1(w)andT2(w).

Recall thatα_k∈τ (w)iff(wtk) < (w)which occurs iffw(k) <0. As long ask≤ r+1, this occurs iff the domino with label k inT2(w)is vertical. Recalling that α_k+1∈τ (w)iffk+1 lies belowkinT₂(w), we can describe the domain ofT_IN^k as follows.

Definition 4.9 We will call a tableauT of rankr sparse if there is a square of the formS_m,r+3−mwhich is empty inT.

Case 1. If the tableauT2(w)(r+2)is sparse, thenw∈S_IN^k for allk≤r+1 iff the dominos with labelsk andk+1 inT₂(w)are of opposite orientations. In this setting, sinceT_IN^k swapsw(k)andw(k+1)inwwhenever they are of opposite sign, its action merely reverses the order in which thekth andk+1st dominos are inserted into the left tableau. Since T2(w)(r+2)is sparse, these insertions do not interact with each other. Thus on the shape-tracking tableau T2(w),T_IN^k merely swaps the dominos with labelskandk+1, while acting trivially onT1(w).

Case 2. If the tableauT₂(w)(r+2)is not sparse, thenk=r+1 and the insertions ofw(k)andw(k+1)into the left tableau interact with each other.

It is easy to see that there are four possible configurations of dominos with labels k=r+1 andl=r+2 withinT2(w)whenw∈S_IN^r+1(W ):

E0(j )= and E0(j )=

E1(j )= and E1(j )=

Proposition 4.10 Consider w ∈ D^r_IN⁺¹(W ) and let v =T_IN^r+1(w). If Gr(w)= (T1, T2), then the tableau pairG_r(v)=(T˜1,T˜2)admits the following description:

1. IfT₂(r+2)is sparse, thenT₁= ˜T₁andT˜₂is obtained by swapping the dominos with labelsr+1 andr+2 in the tableauT₂.

2. IfT₂(r+2)is not sparse, then the description of the action depends on the exact configuration of the dominos with labelsr+1 andr+2 inT2:

(a) If the configurationE0(r+1)orE1(r+1)appears inT2, write it asEi(r+1) and letT¯2=(T2\Ei(r+1))∪E1−i(r+1). Letcbe the extended cycle through r+2 inT¯₂relative toT₁. Then

(T˜1,T˜2)=MT ((T1,T¯2), c).

(b) IfE0(r+1)orE1(r+1)appears inT2, letcbe the extended cycle through r+2 in T2 relative to T1 and define(T¯1,T¯2)=MT ((T1, T2), c).Note that T¯₂ must contain one of the configurations E₀(k)or E₁(k), which we label E_i(r+1). Then

(T˜₁,T˜₂)=T¯₁, (T¯₂\E_i(r+1))∪E_1−i(r+1) .

Proof The first case has already been considered above. In the special situation when n=r+2, the second case follows by inspection. We mimic the proof of [5](2.3.8) to verify the second case in general. So considerw∈D_IN^r+1(W )assuming thatT2(r+2) is not sparse. By symmetry and the fact thatT_IN^r+1is an involution, it is sufficient to consider only w for which also |w(r+1)|<|w(r +2)|, w(r +1) >0 and w(r+2) <0. For such aw, letw¯ =vt_r+1. WriteG_r(w)¯ =(T¯₁,T¯₂).Then

1. E₁(r+1)⊂T₂,E₀(r+1)⊂ ˜T₂, andE₁(r+1)⊂ ¯T₂, 2. T¯₂=(T˜₂\E₀(r+1))∪E₁(r+1)andT¯₁= ˜T₁,

3. (T¯1,T¯2)=MT ((T1, T2), c)where c is the extended cycle throughr+2 inT2

relative toT1.

Once these are verified, the proposition follows. The last two parts imply thatT˜₁= ¯T₁, and the latter equalsMT (T₁, d)whered is the extended cycle inT₁corresponding toc, as desired. Meanwhile, the second part then implies thatT˜2will be as specified by the proposition.

Statements (1) and (2) follow easily from the definition of domino insertion, while the proof of (3) is identical to the rank zero case. That the extended cycle through r+2 inT2 consists only of non-core cycles follows from the remark at the end of this section, and then, for non-core cycles, the description detailing the relationship between moving through and domino insertion of [5](2.3.2) carries without modifi-

cation to the arbitrary rank case.

Example 4.11 Let w=(4,−3,−2,1)∈D³_IN(W4). ThenT_IN³ (w)=(4,−3,1,−2) and the corresponding tableau pairs are:

G₂(w)= and

G₂(T_IN³ (w))=

The extended cycle throughr+2=4 inT₂(w)consists of the open cycle {4}in T2(w)and the corresponding open cycle{4}inT1(w).

Remark 4.12 In the case whenT2(r+2), is not sparse it is not immediately clear that the operation on tableaux described in Proposition4.10actually produces a domino tableau of rankr. That it does follows from the fact that the extended cycle through which the tableaux are being moved through does not contain any core open cycles.

We verify this presently. Suppose thatw∈T_IN^r+1,so thatw(r+1)andw(r+2)are of opposite sign.

Case 1. Suppose eitherE₀(r+1)orE₁(r+1)appears inT₂, and without loss of generality, assume that it isE₀(r+1). The domino with labelr+2 is adjacent to r+1 as well as to another domino adjacent to the core ofT2, which we labell. For r+2 to be in an extended cycle containing a core open cycle, the extended cycle must also contain eitherr+1 orl. We show that this is impossible. First,r+1 andr+2 cannot be in the same extended cycle; one of them is boxed but not the other. Since w(r+1)andw(r+2)are of opposite sign, it is easy to check that withinT2(r+2), r+2 andlare in different extended cycles. But Lemmas 3.6 and 3.7 of [15] imply that this remains the case within the full tableauT₂, see also [5](2.3.3).