[GAP Forum] length

[Frank Luebeck]

Dear Marcus,

> How can I compute the
> length of an element
> of a group, where by
> "length" I mean the minimum
> number of generators
> needed to write the element,
> assuming that I've fixed
> a generating set for the group.

This is in general very difficult. There is essentially no better method
but a brute force search.

> In particular, I need to do
> this for the symmetric group
> using generating set
> (1,2), (2,3), (3,4), ... (n-1,n)

In this particular case there is an efficient algorithm, based on the
following easy to prove

Lemma: For pi in the symmetric group on {1,2,...,n} let
           L(pi) = {(i,j)| 1 <= i < j <= n, pi(i) > pi(j)}.
Let 1 <= k <= n-1. Then |L( (k,k+1) pi )| = |L(pi)| + 1 if pi(k) < pi(k+1)
and |L( (k,k+1) pi )| = |L(pi)| - 1 otherwise.

This shows that the length of pi with respect to your generators is |L(pi)|,
and also that the following function returns a word of minimal length
in your set of generators (there can be many of such words, this gives the
lexicographically smallest):

SnWord := function(pi)
  local word, k;
  word := [];
  while pi <> () do
    k := 1;
    while k^pi < (k+1)^pi do
      k := k + 1;
    od;
    Add(word, k);
    pi := (k,k+1) * pi;
  od;
  return word;
end;


(This can be generalized to arbitrary Coxeter groups with a given set
of Coxeter generators.)


With best regards,

   Frank Luebeck

///  Dr. Frank Lübeck, Lehrstuhl D für Mathematik, Templergraben 64,  ///
\\\                    52062 Aachen, Germany                          \\\
///  E-mail: Frank.Luebeck at Math.RWTH-Aachen.De                        ///
\\\  WWW:    http://www.math.rwth-aachen.de/~Frank.Luebeck/           \\\