[GAP Forum] Question.

[Alexander Hulpke]

Dear Fernando Fantino, Dear GAP-Forum,

> Let G be the symmetric group in n letters. Let s be in G.
> I want to compute a "minimal" decomposition of s as a product of the
> traspositions:
> s_1,...,s_{n-1}, where s_i=(i,i+1).
> "Minimal"  means: of minimal length.
>
> For instance: if n=7 and s=(2,4,5,3) (6,7), such a decomposition  
> would be
> s=(3,4)(2,3)(4,5)(6,7)=s_3 s_2 s_4 s_6.

The following is not the most elegant or efficient way but has the  
advantage that it needs no extra code or packages:
It uses that in the particular case of S_n the presentation yields a  
confluent rewriting system wrt shortlex order and Knuth-Bendix  
reduction can be used to obtain a shortest word. This is probably  
easiest demonstrated in an example:

Make the group

gap> g:=SymmetricGroup(7);
Sym( [ 1 .. 7 ] )

Now calculate a presentation. GAP automatically chooses for S_n the  
coxeter generators

gap> hom:=IsomorphismFpGroup(g);
[ (1,2), (2,3), (3,4), (4,5), (5,6), (6,7) ] ->
[ S_7.1, S_7.2, S_7.3, S_7.4, S_7.5, S_7.6 ]
gap> gfp:=Range(hom);
<fp group of size 5040 on the generators [ S_7.1, S_7.2, S_7.3,  
S_7.4, S_7.5,
   S_7.6 ]>

Now `hom' can be used to translate frompermutations to words. However  
it is not guaranteed to use the shortest possible words. For this we  
force this group to alwatys reduce elements, using Knuth-Bendix  
rewriting:

gap> SetReducedMultiplication(gfp);


Now we can translate:
gap> s:=(3,4)*(2,3)(4,5)(6,7);
(2,3,5,4)(6,7)
gap> w:=Image(hom,s);
S_7.6*S_7.3*S_7.4*S_7.2

For processing the following might be useful:

gap> LetterRepAssocWord(UnderlyingElement(w)); # As List of generators
[ 6, 3, 4, 2 ]
gap> Length(w); # length
4

The same mechanism would work in principle for arbitrary groups, but  
the computation of a confluent rewriting system, triggered by  
`SetReducedMultiplication' could take long and use much memory. Thus  
I would use this with care for different or large groups.

The avid reader of the GAP manual might ask herself at this point why  
I did not suggest `Factorization'. Indeed

gap> g:=Group((1,2), (2,3), (3,4), (4,5), (5,6), (6,7));
Group([ (1,2), (2,3), (3,4), (4,5), (5,6), (6,7) ])
gap> Factorization(g,s);
x6*x3*x4*x2

produces the same result with seemingly less effort. However  
`Factorization' is very general code that needs to enumerate all  
elements of the group. If the degree gets larger (e.g. try the same  
with 15 instead of 7) this will run out of memory, while the method  
proposed will still work.

I hope this is of help,

     Alexander Hulpke


-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke