[GAP Forum] Question.

[Fernando Fantino]

Dear all, dear GAP-Forum,


Thank you for all your suggestions.
I will prove with them.
And...yes, I wanted to write
s=(3,4)*(2,3)*(4,5)*(6,7)=s_3*s_2*s_4*s_6,
instead of
s=(3,4)(2,3)(4,5)(6,7)=s_3 s_2 s_4 s_6.

Thank you again.
Best wishes,
Fernando Fantino.








2007/8/8, Frank Lübeck <Frank.Luebeck at math.rwth-aachen.de>:
>
> On Tue, Aug 07, 2007 at 11:31:11PM +0200, Fernando Fantino wrote:
> > 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.
> >
> >
> > So, I would like something like this:
> > ???(G,s);
> > (3,4)(2,3)(4,5)(6,7)
> > ????(G,s);
> > 4 (the length).
> >
> > How can I do that?
>
> Dear Fernando Fantino, dear Forum,
>
> You can use the following observations which are easy to prove if you
> consider
> a permutation on N = {1,2,...,n} as list of images of 1,2,...,n:
> Let s be a permutation of N, define
> M(s) = { [i,j] | i, j in N, i < j, i^s > j^s }   and
> L(s) = { s_i = (i,i+1) | [i,i+1] in M(s) }.
> Then
> s = ()   iff  |M(s)| = 0   iff   |L(s)| = 0
> and
> |M(s_i * s)| = |M(s)| - 1 if s_i in L(s) and
> |M(s_i * s)| = |M(s)| + 1 otherwise.
>
> From this it follows that |M(s)| is the minimal length as you have defined
> above and L(s) is the "left descend set", i.e., the set of generators s_i
> which
> multiplied to s from the left give a shorter element.
>
> So, one could write the functions you are looking for as follows:
> MinLengthSn := function(s)
> local n;
> n := LargestMovedPoint(s);
> return Sum([1..n-1], i-> Number([i+1..n], j-> i^s > j^s));
> end;
> MinWordSn := function(s)
> local n, res, i;
> res := [];
> while s <> () do
>    # we construct the "lexicographically smallest" word
>    i := 1;
>    while i^s < (i+1)^s do
>      i := i+1;
>    od;
>    Add(res, i);
>    # use s = s_i * (s_i * s) and recurse on second factor
>    s := (i,i+1) * s;
> od;
> return res;   # or: return List(res, i-> (i,i+1));
> end;
>
> Applied to your example:
>
> gap> s := (2,4,5,3) (6,7);
> (2,4,5,3)(6,7)
> gap> MinLengthSn(s);
> 4
> gap> sw := MinWordSn(s);
> [ 2, 4, 3, 6 ]
> gap> Product(sw, i-> (i,i+1));
> (2,4,5,3)(6,7)
> gap> MinLengthSn(Random(SymmetricGroup(1000)));
> 242170
>
>
> [Note that your example s=(3,4)(2,3)(4,5)(6,7) doesn't fit with GAPs
> definition
> of the product of permutations (which act on the points from the right),
> so in
> GAP s = (6,7)*(4,5)*(2,3)*(3,4).]
>
> With best regards,
>
> Frank Lübeck
>
> --
> ///  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/           \\\
>