[GAP Forum] Question.

[Frank Lübeck]

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/           \\\