• 検索結果がありません。

On the cyclically fully commutative elements of Coxeter groups

N/A
N/A
Protected

Academic year: 2022

シェア "On the cyclically fully commutative elements of Coxeter groups"

Copied!
26
0
0

読み込み中.... (全文を見る)

全文

(1)

DOI 10.1007/s10801-011-0327-z

On the cyclically fully commutative elements of Coxeter groups

T. Boothby·J. Burkert·M. Eichwald·D.C. Ernst· R.M. Green·M. Macauley

Received: 10 August 2011 / Accepted: 20 October 2011 / Published online: 19 November 2011

© Springer Science+Business Media, LLC 2011

Abstract LetW be an arbitrary Coxeter group. If two elements have expressions that are cyclic shifts of each other (as words), then they are conjugate (as group el- ements) inW. We say that wis cyclically fully commutative (CFC) if every cyclic shift of any reduced expression forw is fully commutative (i.e., avoids long braid relations). These generalize Coxeter elements in that their reduced expressions can be described combinatorially by acyclic directed graphs, and cyclically shifting cor- responds to source-to-sink conversions. In this paper, we explore the combinatorics of the CFC elements and enumerate them in all Coxeter groups. Additionally, we characterize precisely which CFC elements have the property that powers of them remain fully commutative, via the presence of a simple combinatorial feature called

T. Boothby

Simon Fraser University, Burnaby, BC, VSA 156, Canada e-mail:tboothby@sfu.ca

J. Burkert

Department of Mathematics, Harvey Mudd College, Claremont, CA 91711, USA e-mail:jeffrey.burkert@gmail.com

M. Eichwald

Department of Mathematical Sciences, University of Montana, Missoula, MT 59812, USA e-mail:morgan.eichwald@gmail.com

D.C. Ernst

Mathematics Department, Plymouth State University, Plymouth, NH 03264, USA e-mail:dcernst@plymouth.edu

R.M. Green

Department of Mathematics, University of Colorado, Boulder, CO 80309, USA e-mail:rmg@euclid.colorado.edu

M. Macauley (

)

Department of Mathematical Sciences, Clemson University, Clemson, SC 29634, USA e-mail:macaule@clemson.edu

(2)

a band. This allows us to give necessary and sufficient conditions for a CFC element wto be logarithmic, that is,(wk)=k·(w)for allk≥1, for a large class of Cox- eter groups that includes all affine Weyl groups and simply laced Coxeter groups.

Finally, we give a simple non-CFC element that fails to be logarithmic under these conditions.

Keywords Coxeter groups·Cyclic words·Fully commutative elements·Root automaton

1 Introduction

A classic result of Coxeter groups, known as Matsumoto’s theorem [12], states that any two reduced expressions of the same element differ by a sequence of braid rela- tions. If two elements have expressions that are cyclic shifts of each other (as words), then they are conjugate (as group elements). We say that an expression is cyclically reduced if every cyclic shift of it is reduced, and ask the following question, where an affirmative answer would be a “cyclic version” of Matsumoto’s theorem.

Do two cyclically reduced expressions of conjugate elements differ by a se- quence of braid relations and cyclic shifts?

While the answer to this question is, in general, “no,” it seems to “often be true,”

and understanding when the answer is “yes” is a central focus of a broad ongoing research project of the last three authors. It was recently shown to hold for all Coxeter elements [6,14], though the result was not stated in this manner. Key to this was establishing necessary and sufficient conditions for a Coxeter elementwW to be logarithmic, that is, for(wk)=k·(w)to hold for allk≥1. Trying to understand which elements in a Coxeter group are logarithmic motivated this work. Here, we introduce and study a class of elements that generalize the Coxeter elements, in that they share certain key combinatorial properties.

A Coxeter element is a special case of a fully commutative (FC) element [16], which is any element with the property that any two reduced expressions are equiv- alent by only short braid relations (i.e., iterated commutations of commuting gener- ators). In this paper, we introduce the cyclically fully commutative (CFC) elements.

These are the elements for which every cyclic shift of any reduced expression is a reduced expression of an FC element. If we write a reduced expression for a cycli- cally reduced element in a circle, thereby allowing braid relations to “wrap around the end of the word,” the CFC elements are those where only short braid relations can be applied. In this light, the CFC elements are the “cyclic version” of the FC ele- ments. In particular, the cyclic version of Matsumoto’s theorem for the CFC elements asks when two reduced expressions for conjugate elementswandware equivalent via only short braid relations and cyclic shifts. As with Coxeter elements, the first step in attacking this problem is to find necessary and sufficient conditions for a CFC element to be logarithmic.

This paper is organized as follows. After necessary background material on Cox- eter groups is presented in Sect.2, we introduce the CFC elements in Sect. 3. We

(3)

motivate them as a natural generalization of Coxeter elements, in the sense that like Coxeter elements, they can be associated with canonical acyclic directed graphs, and a cyclic shift (i.e., conjugation by a generator) of a reduced expression corresponds on the graph level to converting a source into a sink. In Sect.4, we prove a number of combinatorial properties of CFC elements and introduce the concept of a band, which tells us precisely when powers of a CFC element remain fully commutative (Theorem4.9). In Sect.5, we enumerate the CFC elements in all Coxeter groups, and we give a complete characterization of the CFC elements in groups that contain only finitely many. In Sect.6, we formalize the root automaton of a Coxeter group in a new way. We then use it to prove a new result on reducibility, which we utilize in Sect.7 to establish necessary and sufficient conditions for CFC elements to be logarithmic, as long as they have no “large bands” (Theorem7.1). We conclude that in any Cox- eter group without “large odd endpoints” (a class of groups includes all affine Weyl groups and simply laced Coxeter groups) a CFC element is logarithmic if and only if it is torsion-free (Corollary7.2). The CFC assumption is indeed crucial for being logarithmic, as we conclude with a simple counterexample inC2by dropping only the CFC condition.

2 Coxeter groups

A Coxeter group is a groupW with a distinguished set of generating involutionsS with presentation

s1, . . . , sn(sisj)mi,j=1 ,

wheremi,j :=m(si, sj)=1 if and only ifsi =sj. The exponentsm(s, t )are called bond strengths, and it is well known thatm(s, t )= |st|. We definem(s, t )to be∞ if there is no exponentk >0 such that(st )k=1. A Coxeter group is simply laced if eachm(s, t )≤3. IfS= {s1, . . . , sn}, the pair(W, S)is called a Coxeter system of rankn. A Coxeter system can be encoded by a unique Coxeter graphΓ having vertex setS and edges{s, t}for eachm(s, t )≥3. Moreover, each edge is labeled with its corresponding bond strength, although typically the labels of 3 are omitted because they are the most common. IfΓ is connected, thenW is called irreducible.

LetSdenote the free monoid overS. If a wordw=sx1sx2· · ·sxmSis equal to wwhen considered as an element ofW, we say thatwis an expression forw. (Ex- pressions will be written insans seriffont for clarity.) If furthermore,mis minimal, we say thatwis a reduced expression forw, and we callmthe length ofw, denoted (w). If every cyclic shift ofwis a reduced expression for some element inW, then we say thatwis cyclically reduced. A group elementwW is cyclically reduced if every reduced expression forwis cyclically reduced.

The left descent set ofwW is the set DL(w)= {sS|(sw) < (w)}, and the right descent set is defined analogously asDR(w)= {s∈S|(ws) < (w)}. If sDL(w)(respectively,DR(w)), thensis said to be initial (respectively, terminal).

It is well known that ifsS, then(sw)=(w)±1, and so(wk)k·(w). If equality holds for allk∈N, we say thatwis logarithmic.

(4)

For each integerm≥0 and distinct generatorss, tS, define s, t m=st st · · ·

m

S.

The relations, t m(s,t )= t, s m(s,t ) is called a braid relation, and is additionally called a short braid relation ifm(s, t )=2. (Some authors calls, t m(s,t )= t, s m(s,t ) a short braid relation ifm(s, t )=3, and a commutation relation ifm(s, t )=2.) The short braid relations generate an equivalence relation onS, and the resulting equiv- alence classes are called commutation classes. If two reduced expressions are in the same commutation class, we say that they are commutation equivalent. An element wW is fully commutative (FC) if all of its reduced expressions are commutation equivalent, and we denote the set of FC elements by FC(W ). For consistency, we say that an expressionw∈Sis FC if it is a reduced expression for somew∈FC(W ).

Ifwis not FC, then it is commutation equivalent to a wordwfor which eitherssor s, t m(s,t ) appears as a consecutive subword, withm(s, t )≥3 (this is not immedi- ately obvious; see Proposition4.2).

The braid relations generate a coarser equivalence relation onS. Matsumoto’s theorem [7, Theorem 1.2.2] says that an equivalence class containing a reduced ex- pression must consist entirely of reduced expressions and that the set of all such equivalence classes under this coarser relation is in 1–1 correspondence with the ele- ments ofW.

Theorem 2.1 (Matsumoto’s theorem) In a Coxeter groupW, any two reduced ex- pressions for the same group element differ by braid relations.

Now, consider an additional equivalence relation∼κ, generated by cyclic shifts of words, i.e.,

sx1sx2· · ·sxm−→sx2sx3· · ·sxmsx1. (2.1) The resulting equivalence classes were studied in [11] and are in general, finer than conjugacy classes, but they often coincide. Determining conditions for when κ- equivalence and conjugacy agree would lead to a “cyclic version” of Matsumoto’s theorem for some class of elements, and is one of the long-term research goals of the last three authors.

Definition 2.2 LetW be a Coxeter group. We say that a conjugacy classCsatisfies the cyclic version of Matsumoto’s theorem if any two cyclically reduced expressions of elements inCdiffer by braid relations and cyclic shifts.

One only needs to look at type An (the symmetric group SYMn+1) to find an example of where the cyclic version of Matsumoto’s theorem fails. Any two simple generators inAn are conjugate, e.g.,s1s2(s1)s2s1=s2. However, for longer words, such examples appear to be less common, and we would like to characterize them.

The support of an expressionw∈Sis simply the set of generators that appear in it. As a consequence of Matsumoto’s theorem, it is also well defined to speak of the support of a group elementwW, as the set of generators appearing in any reduced

(5)

expression forw. We denote this set by supp(w)and letWsupp(w) be the (standard parabolic) subgroup ofW that it generates. IfWsupp(w)=W (i.e., supp(w)=S), we say thatwhas full support. IfWsupp(w)has no finite factors, or equivalently, if every connected component ofΓsupp(w) (i.e., the subgraph of Γ induced by the support of w) describes an infinite Coxeter group, then we say that wis torsion-free. The following result is straightforward.

Proposition 2.3 LetWbe a Coxeter group. IfwW is logarithmic, thenwis cycli- cally reduced and torsion-free.

Proof Ifwis not cyclically reduced, then there exists a sequence of cyclic shifts of some reduced expression ofwthat results in a nonreduced expression. In this case, there existsw1, w2W such thatw=w1w2(reduced) while(w2w1) < (w). This implies that

w2

=(w1w2w1w2)(w1)+(w2w1)+(w2) <2(w),

and hencewis not logarithmic. Ifwis not torsion-free, then we can writew=w1w2

with every generator inw1commuting with every generator inw2, and 0<|w1| = k <∞. Now,

wk

= wk1wk2

= wk2

< k·(w),

and sowis not logarithmic.

We ask when the converse of Proposition2.3holds. In 2009, it was shown to hold for Coxeter elements [14], and in this paper, we show that it holds for all CFC ele- ments that lack a certain combinatorial feature called a “large band.” As a corollary, we can conclude that in any group without “large odd endpoints,” a CFC element is logarithmic if and only if it is torsion free. This class of groups includes all affine Weyl groups and simply laced Coxeter groups. Additionally, we give a simple coun- terexample when the CFC condition is dropped.

3 Coxeter and cyclically fully commutative elements

A common example of an FC element is a Coxeter element, which is an element for which every generator appears exactly once in each reduced expression. The set of Coxeter elements ofW is denoted by C(W ). As mentioned at the end of the previous section, the converse of Proposition2.3holds for Coxeter elements, and this follows easily from a recent result in [14] together with the simple fact that Coxeter elements are trivially cyclically reduced.

Theorem 3.1 In any Coxeter group, a Coxeter element is logarithmic if and only if it is torsion-free.

Proof The forward direction is immediate from Proposition2.3. For the converse, if c∈C(W )is torsion-free, thenc=c1c2· · ·cm, where eachci is a Coxeter element of

(6)

an infinite irreducible parabolic subgroupWsupp(ci). Theorem 1 of [14] says that in an infinite irreducible Coxeter group, Coxeter elements are logarithmic, and it follows that for anyk∈N,

ck

=

ck1· · ·cmk

= c1k

+ · · · + cmk

=k·(c1)+ · · · +k·(cm)=k·(c),

and hencecis logarithmic.

The proof of Theorem 1 of [14] is combinatorial and relies on a natural bijection between the set C(W )of Coxeter elements and the set Acyc(Γ ) of acyclic orien- tations of the Coxeter graph. Specifically, ifc∈C(W ), let(Γ , c)denote the graph where the edge{si, sj}is oriented as(si, sj)ifsi appears beforesj inc. (Some au- thors reverse this convention, orienting{si, sj}as(si, sj)ifsi appears aftersj inc.) The vertexsxi is a source (respectively, sink) of(Γ , c)if and only ifsxi is initial (re- spectively, terminal) inc. Conjugating a Coxeter elementc=sx1· · ·sxn bysx1 cycli- cally shifts the word tosx2· · ·sxnsx1, and on the level of acyclic orientations, this cor- responds to converting the source vertexsx1of(Γ , c)into a sink, which takes the ori- entation(Γ , c)to(Γ , sx1csx1). This generates an equivalence relationκon Acyc(Γ ) and on C(W ), which has been studied recently in [11]. Two acyclic orientations(Γ , c) and(Γ , c)are κ-equivalent if and only if there is a sequencex1, . . . , xk such that c=sxk· · ·sx1csx1· · ·sxk andsxi+1 is a source vertex of(Γ , sxi· · ·sx1csx1· · ·sxi)for eachi=1, . . . , k−1. Thus, two Coxeter elementsc, c∈C(W )areκ-equivalent if they differ by a sequence of length-preserving conjugations, i.e., if they are conjugate by a wordw=sx1· · ·sxk such that

(c)=(sxi· · ·sx1csx1· · ·sxi)

for eachi=1, . . . , k. Though this is in general a stronger condition than just conju- gacy, the following recent result by H. Eriksson and K. Eriksson shows that they are equivalent for Coxeter elements, thus establishing the cyclic version of Matsumoto’s theorem for Coxeter elements.

Theorem 3.2 (Eriksson–Eriksson [6]) LetW be a Coxeter group, andc, c∈C(W ).

Thencandcare conjugate if and only ifcκc.

It is well known (see [15]) that|Acyc(Γ )| =TΓ(2,0), whereTΓ is the Tutte poly- nomial [19] ofΓ. In [10], it was shown that for any undirected graphΓ, there are exactlyTΓ(1,0) κ-equivalence classes in Acyc(Γ ). Applying this to Theorem3.2, we get the following result.

Corollary 3.3 In any Coxeter groupW, theTΓ(2,0)Coxeter elements fall into ex- actlyTΓ(1,0)conjugacy classes, whereTΓ is the Tutte polynomial.

The proof of Theorem3.2hinges on torsion-free Coxeter elements being loga- rithmic, and as mentioned, the proof of this involves combinatorial properties of the acyclic orientation construction and source-to-sink equivalence relation. Thus, we are motivated to extend these properties to a larger class of elements. Indeed, the acyclic

(7)

Fig. 1 The Coxeter graph of typeE6

orientation construction above generalizes to the FC elements. Ifw∈FC(W ), then (Γ , w)is the graph where the vertices are the disjoint union of letters in any reduced expression ofw, and a directed edge is present for each pair of noncommuting let- ters, with the orientation denoting which comes first inw. Since w∈FC(W ), the graph (Γ , w) is well defined. Though the acyclic orientation construction extends from C(W )to FC(W ), the source-to-sink operation does not. The problem arises be- cause a cyclic shift of a reduced expression for an FC element need not be FC. This motivates the following definition.

Definition 3.4 An element wW is cyclically fully commutative (CFC) if every cyclic shift of every reduced expression for w is a reduced expression for an FC element.

We denote the set of CFC elements ofW by CFC(W ). They are precisely those whose reduced expressions, when written in a circle, avoid s, t m subwords for m=m(s, t )≥3, and as such they are the elements for which the source-to-sink operation extends in a well-defined manner. However, acyclic directed graphs are not convenient to capture this generalization—they are much better handled as periodic heaps [8].

Example 3.5 Here are some examples and nonexamples of CFC elements. We will return to Examples (iv) and (v) at the end of Sect.7.

(i) Any Coxeter element is an example of a CFC element, because Coxeter elements are FC, and any cyclic shift of a Coxeter element is also a Coxeter element.

(ii) Consider the Coxeter group of typeA3with generatorss1, s2, s3labeled so that s1 ands3 commute. The elements2s1s3s2 is a reduced expression for an FC elementw. However,wis not cyclically reduced because the above expression has a cyclic shifts2s2s1s3that reduces tos1s3, and sowis not CFC.

(iii) The Coxeter group of typeA2has generators s1, s2, s3 withm(si, sj)=3 for i=j. The elements1s3s1s2is cyclically reduced but not FC, becauses1s3s1s2= s3s1s3s2. If we increase the bond strengthm(s1, s3)from 3 to∞, it becomes FC. However, it is still not CFC because conjugating it bys1yields the element s3s1s2s1=s3s2s1s2.

(iv) Next, consider the affine Weyl group of typeE6(see Fig.1). The elementw= s1s3s2s4s3s5s4s6s0s3s2s6is a CFC element ofW (E6), and it turns out thatwis logarithmic.

(v) Now, consider the affine Weyl group of typeC4(see Fig.2). Letw1=s0s2s4s1s3

andw2=s0s1s2s3s4s3s2s1 be elements inW (C4). It is quickly seen that both elements are CFC with full support, and as we shall be able to prove later, both w1andw2are logarithmic.

(8)

Fig. 2 The Coxeter graph of typeC4

4 Properties of CFC elements

In this section, we will prove a series of results establishing some basic combinatorial properties of CFC elements. Of particular interest are CFC elements whose powers are not FC, and we give a complete characterization of these elements in any Coxeter group. Unless otherwise stated,(W, S)is assumed to be an arbitrary Coxeter system.

Recall that an expressionwnot being FC means that “wis not a reduced expression for an FC element,” i.e., it is either nonreduced, or it is a reduced expression of a non-FC element. By Matsumoto’s theorem, ifw∈Sis a reduced expression for a logarithmic elementwW, then (the group element)wk is FC if and only if (the expression)wkis FC.

Proposition 4.1 Ifwis a reduced expression of a non-CFC element ofW, then some cyclic shift ofwis not FC.

Proof Ifwis a reduced expression for a non-CFC element ofwW, then by defini- tion, a sequence oficyclic shifts of some reduced expressionw=sx1· · ·sxm forw produces an expressionu=sxi+1· · ·sxmsx1· · ·sxi that is either not reduced or is a re- duced expression for a non-FC element. We may assume thatwitself is FC, otherwise the result is trivial. Thus, we can obtainwfromwvia a sequence ofkcommutations, and we may takekto be minimal. The result we seek amounts to proving thatk=0.

By assumption, the expressionu is equivalent via commutations to one containing either (a)ssor (b)s, t m(s,t )as a consecutive subword, wherem(s, t )≥3. For sake of a contradiction, assume thatk >0. If thekth commutation (the one that yieldsw) does not involve a swap of the letters in theith and(i+1)th positions, then we can simply remove this commutation from our sequence, because these two letters will be consecutive inu, and they can be transposed after the cyclic shifts. But this con- tradicts the minimality ofk. So, thekth commutation occurs in positionsiandi+1, sending an expressionwtow, that is,

w=sx1· · ·sxi1sxi+1sxisxi+2· · ·sxm−→sx1· · ·sxi1sxisxi+1sxi+2· · ·sxm=w. Similarly, if this commutation does not involve one of the generators in either case (a) or (b), then omitting this commutation before cyclically shifting still yields an expression that is not FC. Again, this contradicts the minimality ofk, so it must be the case that thekth commutation involvessin case (a) or, without loss of generality, sin case (b). Moreover, we may assume without loss of generality thatsxi=s, which is in the(i+1)th position ofw (otherwise, we could have consideredw1, which is reduced if and only ifwis reduced). Now, applyi+1 cyclic shifts tow, which yields the element

sxi+2· · ·sxmsx1· · ·sxi1sxi+1sxi=sxi+2· · ·sxmsx1· · ·sxi1sxisxi+1W.

(9)

Note that this second expression is a single cyclic shift ofu. Sinceuis commutation equivalent to an expression containing eitherss or s, t m(s,t ) as a subword, mov- ingsxi+1 (which cannot besor t) from the front ofuto the back does not destroy this property. Thus, we can obtain an expression that is not FC fromwby applying k−1 commutations before cyclically shifting, contradicting the minimality ofkand

completing the proof.

Proposition 4.2 Letwbe an expression that is not FC. Thenwis commutation equiv- alent to an expression of the formw1w2w3, where eitherw2=ssfor somesS, or w2= s, t m(s,t )form(s, t )≥3.

Proof This is a restatement of Stembridge’s [16, Proposition 3.3]. We remark thatw1

orw3could be empty.

Lemma 4.3 LetwW be logarithmic. Ifw2is FC (respectively, CFC), thenwk is FC (respectively, CFC) for allk >2.

Proof Assume without loss of generality thatWis irreducible andwhas full support.

IfW has rank 2, thenw=(st )j andm(s, t )= ∞, in which case the result is trivial.

Thus, we may assume thatW has rankn >2, and we will prove the contrapositive.

Letwbe a reduced expression forw, and suppose thatwk is not FC (it is reduced becausewis logarithmic). By Proposition4.2,wkis commutation equivalent to some w1w2w3wherew2= s, t m(s,t ) withm(s, t )≥3. Since there is someu∈supp(w) that does not commute with bothsandt, the letters inw2can only have come from at most two consecutive copies ofwinwk. Thus,w2∈FC(W ).

Ifwk∈CFC(W ), then by Proposition4.1, some cyclic shift ofwkis not FC. Since every cyclic shift ofwk is a subword ofwk+1, this means thatwk+1is not FC. From what we just proved it follows thatw2∈FC(W ), and hencew2∈CFC(W ).

Observe that the assumption thatw is logarithmic is indeed necessary—without it, the elementw=s1s2inI2(m)form≥5 would serve as a counterexample.

Lemma 4.4 LetW be an irreducible Coxeter group of rankn2. Ifwis a reduced expression forw∈CFC(W )with full support, thenwkis not commutation equivalent to an expression withssas a subword, for anysS.

Proof For sake of contradiction, suppose that wk is commutation equivalent to an expression withssas a subword. Sincewis CFC, these twos’s must have come from different copies ofwinwkthat we may assume consecutive. Thus, we may write

w2=(u1sw1)(u2sw2), w=u1sw1=u2sw2,

where the wordsw1u2sis also commutation equivalent to an expression withssas a subword. There are two cases to consider. If(u1) > (u2), thensw1u2s is a sub- word of some cyclic shift ofw. However, this is impossible becausewis CFC. Thus, (u1)(u2). In this case, some cyclic shift ofwis contained insw1u2s as a sub- word, and sincewhas full support, every generator appears in this subword. However,

(10)

in order for commutations to make the twos’s consecutive,smust commute with ev- ery generator inw1u2, which is the required contradiction.

There is an analogous result to Lemma4.3whenwis not logarithmic. However, care is needed in distinguishing between the expressionw2being FC and the actual elementw2being FC.

Lemma 4.5 LetW be an irreducible Coxeter group of rankn >2. Ifwis a reduced expression for a nonlogarithmic elementw∈CFC(W )with full support, thenw2∈ FC(W ).

Proof Pickkso that(wk) < k·(w). By Proposition4.2,wkis commutation equiv- alent to somew1w2w3 where eitherw2=ss, or w2= s, t m(s,t ) withm(s, t )≥3.

However, the former is impossible by Lemma4.4. Moreover, there is another gener- atoruS appearing inwthat does not commute with boths andt. Therefore, the letters inw2can only have come from at most two consecutive copies ofwinwk.

Thus,w2∈FC(W ).

Proposition 4.6 LetW be an irreducible Coxeter group of rankn >2. If w is a reduced expression for w∈CFC(W ) with full support, thenwk ∈CFC(W )for all k∈N.

Proof Let w be a reduced expression for w ∈ CFC(W ). Since w2 ∈ FC(W ), Lemma4.5tells us that w is logarithmic. Suppose for sake of contradiction, that wk ∈CFC(W )for some k≥2. By Lemma 4.3, we know thatw2∈CFC(W ), and by Proposition4.1, some cyclic shift ofw2is not FC. Every cyclic shift ofw2is a subword ofw3, thusw3∈FC(W ). Applying Lemma4.3again gives w2∈FC(W ),

the desired contradiction.

Ifwis a reduced expression of a CFC element andwk is FC for allk, thenwis clearly logarithmic. Thus, we want to understand which CFC elements have the prop- erty that powers of their reduced expressions are not FC. Theorem4.9gives necessary and sufficient conditions for this to happen, but first we need more terminology. If a vertexsinΓ has degree 1, we call it an endpoint. An endpoint vertex (or genera- tor)s has a uniquetS for which m(s, t )≥3, and we call m(s, t )the weight of the endpoint. If this weight is greater than 3, we say that the endpoint is large. In the remainder of this paper, we will pay particular attention to “large odd endpoints,”

that is, endpoints sS for which m(s, t ) is odd and at least 5. (We will say that m(s, t )= ∞is large but not odd.) As we shall see, groups with large odd endpoints have CFC elements with a feature called a “large band,” and these elements have properties not shared by other CFC elements.

Definition 4.7 Letw∈CFC(W )and say that(W, S)is the Coxeter system gener- ated by supp(w). We say thatwhas anst-band if for some reduced expressionwand distinct generatorss, tS, exactly one of which is an odd endpoint of(W, S), the following two conditions hold:

(11)

1. some cyclic shift ofwis commutation equivalent to a reduced expression contain- ings, t m(s,t )1as a subword;

2. neithersnort appears elsewhere inw.

We analogously define ant s-band (i.e., some cyclic shift ofwis commutation equiv- alent to a reduced expression containingt, s m(s,t )1 as a subword). If we do not care to specify whethersortcomes first, then we will simply say thatwhas a band.

Anst-band is called small ifm(s, t )=3 and large otherwise.

Remark 4.8 Note thatwhas anst-band if and only ifw1has at s-band. Ifwhas a band, then we may assume, without loss of generality, thatwhas anst-band, where sis the odd endpoint.

The following result highlights the importance of bands and is essential for estab- lishing our main results on CFC elements.

Theorem 4.9 LetW be an irreducible Coxeter group of rankn >2, and letwbe a reduced expression forw∈CFC(W )with full support. Thenwkis FC for allk∈Nif and only ifwhas no bands.

Proof Suppose thatwkis not FC for somek >2. Ifwis logarithmic, then Lemma4.3 tells us thatw2is not FC. However, even ifwis not logarithmic, we can still conclude thatw2is not FC, by Lemma4.5. Thus, to prove the theorem, it suffices to show that w2is not FC if and only ifwhas a band.

First, suppose thatw2is not FC. We will prove thatwhas a band by establishing the following properties:

(i) W has an odd endpoints(saym(s, t )≥3) for which the wordw2is commuta- tion equivalent to an expression of the formw1s, t m(s,t )w3;

(ii) some cyclic shift ofwis commutation equivalent to a reduced expression con- tainings, t m(s,t )1ort, s m(s,t )1as a subword;

(iii) neithersnort appears elsewhere inw.

Since w2 is not FC, Proposition 4.2implies thatw2 is commutation equivalent to an expression of the formw1w2w3in whichw2= s, t m(s,t ). (Note that w2=ssis forbidden by Lemma4.4.) To prove (i), we will first show thatsmust be an endpoint and then show thatm(s, t )must be odd.

First, we claim that becausewis CFC, two occurrences ofsinw2must correspond to the same letter ofw. To see why, consider the subword ofw2 from the original position of the initialsinw2to the original position of the final letter (which is either s or t). Clearly, the instances ofs andt in this subword must alternate. If no two occurrences ofscorrespond to the same letter ofw, then this subword is a subword of a cyclic shift ofw, contradicting the assumption thatwis CFC and establishing our claim. In particular, we can writew2=(w1sw2)(w1sw2), where both instances of soccur inw2, and the first instance ofs is the initial letter ofw2. This implies that the letters inw2andw1 are either other occurrences ofs ort, or commute withs.

Sincew=w1sw2and has full support andW is irreducible, it must be the case thats commutes with every other generator ofSexceptt, and sosis an endpoint.

(12)

It remains to show thatm(s, t )is odd. For sake of a contradiction, suppose oth- erwise, so thatw2 ends int. The argument in the previous paragraph usingw1in place ofwandt in place ofsimplies thatt must be an endpoint as well. However, we assumed thatW is irreducible, and henceW has rank 2. This contradicts our assumption thatWhas rankn≥3, and therefore,m(s, t )is odd.

To prove (ii), we first prove that the instance ofssandwiched betweenw1andw2 inw1sw2is also the terminal letter ofw2. Toward a contradiction, suppose otherwise.

That is, assume thatw2=(w1su1su2)(w1su1su2), where the fourth instance ofs is the terminal letter ofw2. Then it must be the case that every letter between the initial and terminalsinw2is eithers,t, or a generator that commutes with bothsandt. However, this includes the supports ofw1,u1, andu2, and sincew=w1su1su2, we conclude that every letter inwis eithers,t, or commutes withs andt. Again, this contradicts the assumption ofW being irreducible and of rankn≥3, so it follows that the two instances ofsin(w1sw2)(w1sw2)are the initial and terminal letters of w2, respectively. Now, (ii) follows from the observations thatsw2w1is a cyclic shift ofw, and everyt occurring inw2must occur inw2w1. Finally, (iii) follows from the easy observation that every letter ofwis contained in the wordsw2w1s, which has preciselym(s, t )letters from the set{s, t}. Together, (i), (ii), and (iii) imply thatw has anst-band.

We now turn to the converse. Letwbe a CFC element with full support and a band.

By Remark4.8, we may assume, without loss of generality, thatwhas anst-band, wheres is the endpoint. That is, some cyclic shift of wis commutation equivalent to an expression containings, t m(s,t )1as a subword. Suppose thatw=w1w2and the cyclic shift w2w1 is commutation equivalent to a word u=u1s, t m(s,t )1u3, with{s, t} ∩supp(u1u3)= ∅. Clearly,u2is not FC, and so(w2w1)2is not FC either.

However,(w2w1)2is a subword ofw3, and sow3is not FC and hence not CFC. By

Proposition4.6,w2is not FC.

Lemma 4.10 Let W be an irreducible Coxeter group with graph Γ, and let w∈ CFC(W ). Lets, tSsatisfym(s, t )3, and letΓ be the graph obtained fromΓ by removing the edge{s, t}. Suppose thatwis a reduced expression forwin which toccurs exactly once and thatΓis disconnected. Letwbe the expression obtained fromw by deleting all occurrences of generators corresponding to the connected componentΓsofΓcontainings. Thenwis a reduced expression for a CFC element ofW.

Proof Suppose for a contradiction that w is not a reduced expression for a CFC element. Then eitherwis not a reduced expression, orwis a reduced expression for a non-CFC element. In the former case,wis commutation equivalent to an expression w containing either (a) a subword of the form aa or (b) a subword of the form a, b m(a,b)withm(a, b)≥3. In the latter case, Proposition4.1implies thatwcan be cyclically shifted to yield a non-FC expression. By Proposition4.2, this expression is commutation equivalent to one with a subword equal to eitheraaora, b m(a,b)as in cases (a) and (b) above. Regardless, by applying a sequence of commutations or cyclic shifts tow, we can obtain a wordwcontaining eitheraaora, bm(a,b)(but notb, a m(a,b)).

(13)

Sincewdoes not contain such a subword, it follows in case (a) thata=t, which is a contradiction becausewcontains a unique occurrence oft. A similar contradiction arises in case (b), except possibly ifb=t andm(a, b)=3. However, in this case,a commutes with all generators inΓs, and sowwould be commutation equivalent to an expression with subword of the formaba. This contradicts the hypothesis thatw

is FC, completing the proof.

Lemma4.10has an important corollary: if a CFC element has a small band, then the corresponding endpoint can be removed to create a shorter CFC element.

Corollary 4.11 Letwbe a reduced expression forw∈CFC(W ). Ifw has a small band, then removing the corresponding endpoint fromwyields a reduced expression for a CFC elementw. Moreover, ifwhas no large bands, then neither doesw. Proof Suppose thatwhas a smallst-band wheresis the endpoint. By definition,s andtoccur uniquely inw. Deleting the edge{s, t}disconnects the Coxeter graph, and the connected component containingsisΓs= {s}. We may now apply Lemma4.10 to conclude that the wordwformed from deleting the (unique) instance ofsis CFC inW.

Ifw has no large bands, the only way that w could have a large band is if it involvedt. That is, it would have to be at u-band or a ut-band for some uwhere m(t, u)≥5. However, this is impossible becauset occurs uniquely inwand hence

inw.

It is important to note that Corollary4.11 does not generalize to large bands.

For example, suppose thats is an endpoint with m(s, t )=3 and w=w1stw2 (re- duced) is a CFC element with a small st-band. By Corollary 4.11, we can infer thatw1tw2is CFC. In contrast, suppose thatm(s, t )=5 andwhas a largest-band, e.g.,w=w1st stw2(reduced). Now, it is not necessarily the case thatw1tw2, or even w1stw2, is CFC. Indeed, it may happen that the last letter of w1 and the first let- ter ofw2are both a common generatoruwithm(t, u)=3. This peculiar quirk has far-reaching implications—in Sect.7, we will use this deletion property inductively to give a complete characterization of the logarithmic CFC elements with no large bands.

5 Enumeration of CFC elements

In this section, we will enumerate the CFC elements in all Coxeter groups. In the groups that contain finitely many, we will also completely determine the structure of the CFC elements. Once again, there is a dichotomy between the groups without large odd endpoints and those with, as the latter class of groups contain CFC elements with large bands. In [16], J. Stembridge classified the Coxeter groups that contain finitely many FC elements, calling them the FC-finite groups. In a similar vein, the CFC- finite groups can be defined as the Coxeter groups that contain only finitely many CFC elements. Our next result shows that a group is CFC-finite if and only if it is

(14)

Fig. 3 Coxeter graphs of the irreducible CFC-finite groups

FC-finite. The Coxeter graphs of these (irreducible) groups are shown in Fig.3, and they comprise seven infinite families. (The vertex labeled s0 is called the branch vertex and will be defined later.) Though it is a slight abuse of notation, we will for clarity use the same symbol for the group type (e.g.,An) and the actual group (e.g., W (An))in this section.

Theorem 5.1 The irreducible CFC-finite Coxeter groups areAn(n≥1),Bn(n≥2), Dn(n≥4),En (n≥6),Fn (n≥4),Hn (n≥3), andI2(m)(5≤m <). Thus, a Coxeter group is CFC-finite if and only if it is FC-finite.

Proof The “if” direction is immediate since CFC(W )⊆FC(W ), so it suffices to show that every CFC-finite group is FC-finite. Stembridge classified the FC-finite groups in [16] by classifying their Coxeter graphs. In particular, he gave a list of ten forbidden properties that an FC-finite group cannot have. The list of FC-finite groups is precisely those that avoid all ten of these obstructions. The first five conditions are easy to state and are listed below.

1. Γ cannot contain a cycle.

2. Γ cannot contain an edge of weightm(s, t )= ∞.

3. Γ cannot contain more than one edge of weight greater than 3.

4. Γ cannot have a vertex of degree greater than 3 or more than one vertex of de- gree 3.

5. Γ cannot have both a vertex of degree 3 and an edge of weight greater than 3.

The remaining five conditions all require the definition of a heap, and in the interest of space, will not be stated here. For each of the ten conditions, including the above five, Stembridge shows that if it fails, one can produce a wordwWsuch thatwk is FC for allk∈N. This, together with Proposition4.6, implies that ifW is CFC-finite, then it is FC-finite, and the result follows immediately.

We now turn our attention to enumerating the CFC elements in the CFC-finite groups. The following lemma is well known, but we are not aware of a suitable ref- erence, so we provide a proof here.

(15)

Lemma 5.2 LetWbe a Coxeter group of typeAn, and letsbe an endpoint generator ofAn. Ifwis a reduced expression forw∈FC(W ), thensoccurs at most once inw. Proof We may assume thats occurs inw, and by symmetry, we may assume that s=sn.

In typeAn, a well-known reduced expression for the longest elementw0is s1(s2s1)(s3s2s1)· · ·(snsn1· · ·s1).

Every element ofwsatisfiesww0with respect to the Bruhat order, which means that any suchwmay be written as a subexpression of the given expression. In par- ticular, any elementwhas a reduced expression containing at most one occurrence ofsn. This applies to the case wherew∈FC(W ), in which case one (and hence all) reduced expressions forwcontain at most one occurrence ofsn. Lemma 5.3 Let W be a Coxeter group of type Hn. Label the elements of S as s1, s2, . . . , sn in the obvious way such that m(s1, s2)=5. Let wbe a reduced ex- pression for an elementw∈CFC(Hn)having full support. Then the following all hold:

(i) wcontains precisely one occurrence of each generatorsi fori≥3;

(ii) w contains precisely j occurrences of each generator s1 and s2, where j ∈ {1,2};

(iii) ifwis not a Coxeter element, then it has a large band.

Proof We prove (i) and (ii) by induction on n. For both, the base case is n=2, which follows by a direct check ofW (I2(5)). We will prove (i) first and will assume thatn >2. From Theorem5.1we know thatW has finitely many CFC elements. It follows that for somek∈N(actually,k=2 works, but this is unimportant),wkis not FC, and so by Theorem4.9,whas a band. Thus,whas a reduced expressionwthat can be cyclically shifted to a word that is commutation equivalent to an expressionu containing eithers1s2s1s2orsn1snas a subword (by Remark4.8, we can disregard the other two cases,s2s1s2s1andsnsn1).

First, suppose w has an s1s2-band, so u = u1s1s2s1s2u2, and {s1, s2} ∩ supp(u1u2)= ∅. Sincewis CFC,u2u1is FC. This element sits inside a typeAn2

parabolic subgroup of W of which s3 is an endpoint. By Lemma 5.2, s3 occurs uniquely inu2u1. Now consider the wordu1u2. By Lemma 4.10applied towand the pair of generators{s2, s3}, we see thatu1u2is CFC, and we already know that it contains a unique instance ofs3. By repeated applications of Corollary4.11and the fact that typeAis finite, we deduce thatu1u2contains precisely one occurrence of each generator in the set{s3, s4, . . . , sn}, and this proves (i).

For (ii), assume again thatn >2 and suppose thatwhas no large band, meaning it must have ansn1sn-band. We may use Corollary4.11to delete the (unique) oc- currence ofsnfromwto obtain a CFC element ofW (Hn1)also having full support and no large band. The result now follows by induction.

For (iii), assume thatwis CFC but not a Coxeter element, andn >2. By (i) and (ii),s1ands2must occur inwtwice each, ands3can only occur once. Clearly,wis a

(16)

cyclic shift of a CFC element beginning withs3, and since this is the only occurrence ofs3(the only generator that does not commute with boths1ands2), this element is commutation equivalent to one containing eithers1s2s1s2ors2s1s2s1as a subword.

Therefore,whas a large band.

Suppose thatΓ is the Coxeter graph for an irreducible CFC-finite Coxeter group.

DefineΓ0to be the typeAsubgraph ofΓ consisting of (a) the generators0as labeled in Fig.3and (b) everything to the right of it. We callΓ0the branch ofΓ and refer to the distinguished vertexs0as the branch vertex.

The FC elements in the FC-finite groups can be quite complicated to describe (see [16,17]). In contrast, the CFC elements have a very restricted form. The fol- lowing result shows that except in types Hn and I2(m), they are just the Coxeter elements.

Proposition 5.4 Let W be an irreducible CFC-finite group. Suppose that w∈ CFC(W )has full support and that some generatorsS appears inw more than once. Then one of the following situations occurs.

(i) W=I2(m), andw=st st· · ·sthas even length and satisfies 0(w) < m, or (ii) W=Hnforn >2, andwhas a large band.

Proof The proof is by induction on |S| =n, the case with n=1 being trivial. If n=2, thenW=I2(m). In this case, it is easily checked that the CFC elements are those of the formw=st st· · ·st, wheresandt are distinct generators,(w)is even, and 0≤(w) < m=m(s, t ).

Suppose now thatn >2. The case whereW=Hn follows from Lemma5.3. For all other cases, Theorem5.1tells us thatW has no large odd endpoints. Letwbe a reduced expression forw. SinceW is CFC-finite, there existsk∈Nsuch thatwk is not FC. In this case, it follows by induction on rank and Corollary4.11thatw is a

Coxeter element, which is a contradiction.

Remark 5.5 Ifw∈CFC(W )with full support such thatW=I2(m), Hn, thenwmust be a Coxeter element.

Finally, we can drop the restriction thatwshould have full support.

Corollary 5.6 LetWbe an irreducible CFC-finite group. Suppose thatw∈CFC(W ) and that some generator sS appears in w more than once. Then there exists a unique generatortSwithm(s, t )5. Furthermore, the generatorssandt occur j times each, in alternating order (but not necessarily consecutively), where 2j <

m(s, t ).

Proof This follows from Proposition5.4by considering the parabolic subgroup cor- responding to supp(w)and by considering each connected component of the resulting

Coxeter graph.

Corollary5.6allows us to enumerate the CFC elements of the CFC-finite groups.

LetWndenote a rank-nirreducible CFC-finite group of a fixed type, wheren≥3, and

参照

関連したドキュメント

In the next section we gather preliminaries on poset topology and Coxeter groups, including some new ma- terial on twisted involutions, that we need in the sequel.. Section 5

For groups as discussed in Section 5 experiments with the above algorithm show that already for a free group of rank 3, any surjection contains a primitive element for all groups

We specify a selection spiraling polygons with be- tween three and eleven sides whose groups of transformations form representations of affine Weyl groups with types that coincide

These include the relation between the structure of the mapping class group and invariants of 3–manifolds, the unstable cohomology of the moduli space of curves and Faber’s

In the present paper, starting from Matsumoto’s presentations, we calculate pre- sentations for all punctured mapping class groups M (F g,r , P n ) as quotients of Artin groups by

In this paper, we prove that Conjecture 1.1 holds in all the covering groups of the symmetric and alternating groups, provided p is odd (Theorem 5.1).. The proof makes heavy use of

The Grothendieck-Teichm¨ uller group and the outer automorphism groups of the profinite braid groups (joint.. work with

A space similar to Outer space was introduced in [6] for Aut(F r ), and is some- times referred to as “Auter space.” The definition and auxiliary constructions are entirely analogous