[GAP Forum] length

[Goetz Pfeiffer]

Dear Forum, dear marcus,

On Sun, 2004-03-28 at 06:00, marcus at thunder.realcool.org wrote:
> 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.
> In particular, I need to do
> this for the symmetric group
> using generating set
> (1,2), (2,3), (3,4), ... (n-1,n) 

the length of a permutation p with respect to 
the generating set { (i, i+1) } is the number of pairs
i < j  with i^p > j^p.  It can for example be computed 
by this function LengthPerm:

gap> LengthPerm:= p -> 
> Sum([1..LargestMovedPoint(p)], j-> Number([1..j-1], i-> i^p > j^p));
function( p ) ... end
gap> LengthPerm((1,2,3,4,5));
4
gap> Collected(List(Elements(SymmetricGroup(4)), LengthPerm));
[ [ 0, 1 ], [ 1, 3 ], [ 2, 5 ], [ 3, 6 ], [ 4, 5 ], [ 5, 3 ], [ 6, 1 ] ]

In general, the computation of the length of a
group element is less straight forward.

Goetz Pfeiffer.

-------------------------------------------------------------------------
Goetz.Pfeiffer at NUIGalway.ie              http://schmidt.nuigalway.ie/~goetz/
National University of Ireland, Galway.       phone +353-91-512027 (x3591)