# 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 ] ```

The last line tells us that there is 1 element of length 0, there are 4 elements of length 4, etc.

For many basic functions (like `CoxeterElementsLength`, `Reflections`, `Bruhat`, etc.) we have chosen the convention that if the input is an element of a Coxeter group, then this element should by given as a permutation (and similarly for the output). As a rule of thumb one should keep in mind that, if in some application one has to do a lot of computations with Coxeter group elements then using the low level GAP functions for permutations is usually much faster than manipulating lists of reduced expressions. For example, suppose we are given an element w in W and a generator s_i and we want to check if l(s_iw). Then it is more efficient to represent w by a permutation and to check the condition `i^wW.N` than to work with a reduced expression and check the condition

``` Length( ReducedCoxeterWord( W, Concatenation( [i], w ) ) ) ```

``` ```

``` ```

### ` Subsections`

``` PermCoxeterWord CoxeterWord CoxeterLength ReducedCoxeterWord LeftDescentSet RightDescentSet Reflections LongestCoxeterElement LongestCoxeterWord HighestShortRoot CoxeterElementsLength CoxeterWords CoxeterConjugacyClasses ChevieClassInfo Bruhat MatXPerm MatYPerm PermMatX PermMatY Previous Up NextIndex GAP 3.4.4April 1997```