76 Elements in finite Coxeter groups

Let (W,S) be a finite Coxeter system as in the previous chapter. For a given element w in W, the length l(w) is defined to be the smallest integer k such that w can be written as a product of k fundamental reflections. Such an expression of shortest possible length will be called a reduced word for w. A user might be interested to think of the elements of W as such words in the generating fundamental reflections. For these programs, we represent a word simply as a list of integers corresponding to the fundamental roots, e.g., [] is the identity element, and [1], [2], etc. represent the reflection along the first, the second etc. fundamental root vector. For computational purposes, it might be better to use the permutation of an element w on the root vectors. The functions CoxeterWord and PermCoxeterWord will do the conversion of one form into the other.

    gap> W := CoxeterGroup( "D", 4 );;
    gap> p := PermCoxeterWord( W, [ 1, 3, 2, 1, 3 ] );
    ( 1,14,13, 2)( 3,17, 8,18)( 4,12)( 5,20, 6,15)( 7,10,11, 9)(16,24)
    (19,22,23,21)
    gap> CoxeterWord( W, p );
    [ 1, 3, 1, 2, 3 ] 

We notice that the word we started with and the one that we ended up with, are not the same. But of course, they represent the same element of W. The reason for this difference is that the function CoxeterWord always computes a reduced word which is the lexicographically smallest among all possible expressions of an element of W as a word in the fundamental reflections! The function ReducedCoxeterWord does the same but with an arbitrary word as input (and not with a permutation). In particular, the element used in the above example has length 5. Sometimes, it is not necessary to compute a reduced word for an element w and one is only interested in the length l(w); this can be computed very effectively from the permutation, since it is also given by the number of positive roots mapped to negative roots by w, i.e., by the number of i in {1,ldots,N} such that i^w > N. This is what does the function CoxeterLength in the following example where we also show how to compute the unique element of maximal length in W.

    gap> LongestCoxeterWord( W );  # the (unique) longest element in W
    [ 1, 2, 3, 1, 2, 3, 4, 3, 1, 2, 3, 4 ]
    gap> w0 := LongestCoxeterElement( W ); # = PermCoxeterWord( W, last )
    ( 1,13)( 2,14)( 3,15)( 4,16)( 5,17)( 6,18)( 7,19)( 8,20)( 9,21)(10,22)
    (11,23)(12,24)
    gap> CoxeterLength( W, w0 );
    12 

There is another way of computing a reduced word which is more canonical for some purposes. For any set I of generators, let w_I be the unique element of maximal length which can be made in the generators I. (Note that this element is an involution.) Now take any w in W and compute the set L(w) of all generators s such that l(sw). In GAP this is done by the function LeftDescentSet. Brieskorn Bri71 has noticed that w_{L(w)} divides w, in the sense that l(w_{L(w)})+l(w_{L(w)}w)=l(w). We can now divide w by w_{L(w)} and continue this process with the quotient. In this way, we obtain a reduced expression w=w_{L_1} cdots w_{L_r} where L_i=L(w_{L_i} cdots w_{L_r}) for all i, which we call the Brieskorn normal form of w (and where we use the lexicographically smallest expression for each w_{L_i}). The CHEVIE package will use this form if you set CHEVIE.BrieskornNormalForm:= true;. When you load CHEVIE this variable is initialized with false (see also CoxeterWord).

We give an example of some other commands:

    gap> List( Reflections( W ), i -> CoxeterWord( W, i ) );  
    [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 1, 3, 1 ], [ 2, 3, 2 ], [ 3, 4, 3 ],
      [ 1, 2, 3, 1, 2 ], [ 1, 3, 4, 3, 1 ], [ 2, 3, 4, 3, 2 ],
      [ 1, 2, 3, 4, 3, 1, 2 ], [ 3, 1, 2, 3, 4, 3, 1, 2, 3 ], [ 1 ],
      [ 2 ], [ 3 ], [ 4 ], [ 1, 3, 1 ], [ 2, 3, 2 ], [ 3, 4, 3 ], 
      [ 1, 2, 3, 1, 2 ], [ 1, 3, 4, 3, 1 ], [ 2, 3, 4, 3, 2 ], 
      [ 1, 2, 3, 4, 3, 1, 2 ], [ 3, 1, 2, 3, 4, 3, 1, 2, 3 ] ]
    gap> l := List( [1 .. W.N+1], x -> CoxeterElementsLength( W, x-1 ) );; 
    gap> List( l, Length );
    [ 1, 4, 9, 16, 23, 28, 30, 28, 23, 16, 9, 4, 1 ]