Dear Gap-Forum.

Jakob Hirbawi asked:

I'd like to solicit the forum's help in a group action problem that I'm
looking at : start with a permutation group G and let one of its subgroups
act by conjugation on one of its (G's) conjugacy classes. I'd like to get
representatives of the orbits of this action.

For the particluar case that I need now, G is the symmetric group of degree 2n,
the subgroup is the cyclic group of the same degree, and the conjugacy class
corresponds to the partition [2,2,...,2] of 2n. I wrote the function below to
do this but it doesn't seem to handle the n>5 cases very well, so it seems
that I need something more efficient -- I'd like to look at the 1<n<10 cases.

Is there a better way to do this?

I think there is. Four comments to your problem:

[ original procedure nearly almost ommitted ]

orbits := Orbits(group, Elements(class),function(d,g) return d^g; end);

since you are operating in the 'natural' way, you dont have to give a
special operation function, but can use 'OnPoints' or even leave it out. GAP
will then use the internal 'OnPoints', which is faster.

However, for n>6 or so, the class becomes too big, to write down all
elements. A 'generic' way to cope with it, is trying to find enough class
elements by random, as does the following procedure:

GenerateOrbits := function(n) local
permutation,class,generator,group,orbits,lengthsum,orb,r;
# permutation corresponding to partition [2,2,...,2] of 2n
permutation := PermList(List([1..2*n],x->x+Mod(x,2)-Mod(x+1,2)));
# conjugacy class of Sym(2n) corresponding to permutation
class := ConjugacyClass(SymmetricGroup(2*n),permutation);
Print("size of class : ",Size(class),"\n");
# cyclic permutation (1,2,3,...,2n)
generator := PermList(List([1..2*n],x->Mod(x,2*n)+1));
# cyclic group of order 2n
group := Group( generator );
# orbits of group on class
orbits:=[];
lengthsum:=0;

repeat
r:=Random(class);
# we suppose, that the subgroup is small. So writing down one orbit, is
# actually no problem. If the subgroup is larger, One should use
# RepresentativeOperation to test for conjugacy instead
orb:=Orbit(group,r);
if Length(Intersection(orb,orbits))=0 then
# we have found a new one
Add(orbits,r);
lengthsum:=lengthsum+Length(orb);
Print("#I Length ",Length(orb)," found, total ",lengthsum," \n");
fi;
until lengthsum=Size(class);

Print("number of orbits : ",Length(orbits),"\n");
return orbits;
end;

However, this routine still takes too long, though it does not waste memory.

The next possibility would be to compute double cosets

U\S_2n/Centralizer

and conjugate with representatives, but in your example, this seems to be
no advantage.

Up to this point, we have not utilized the specific structure, i.e. that we
have the full symmetric group. We may use this, by running in a special loop
through all elements of the specified class, and check again, whether they
are conjugated under the action of U.
As we get the elements in lexicographic order, they are mostly non
conjugate, and we get enough orbit representatievs fairly quick. The work is
done by the following routine:

GenerateOrbits1 := function(n)
local ran,p,pw,orb,orbits,l,sel,i,j,e,a,b,lengthsum,pl,generator,group,
permutation,class;
# permutation corresponding to partition [2,2,...,2] of 2n
permutation := PermList(List([1..2*n],x->x+Mod(x,2)-Mod(x+1,2)));
# conjugacy class of Sym(2n) corresponding to permutation
class := ConjugacyClass(SymmetricGroup(2*n),permutation);
class:=Size(class);
# cyclic permutation (1,2,3,...,2n)
generator := PermList(List([1..2*n],x->Mod(x,2*n)+1));
# cyclic group of order 2n
group := Group( generator );
ran:=[1..2*n];

# the class, which is a power of <permutation> is found last after some
# search in vain. So we start with it.
orbits:=[permutation^n];
lengthsum:=1;
# now run through the class of multiple transpositions
l:=List([1..2*n],i->1);
p:=[1];
sel:=[];
for  i in [1..n] do
  sel[2*i]:=Filtered(ran,j->j>=2*i);
od;
sel[2*n]:=[];
i:=2;
pl:=[];
repeat
  while i<2*n do
    p[i]:=sel[i][l[i]];
    # next lexicographic point as start point of next transposition
    pw:=p{[1..i]};
    p[i+1]:=First(ran,j->not j in pw);
    i:=i+2;
    if i<2*n then
      sel[i]:=Difference(ran,p{[1..i-1]});
      l[i]:=1;
    fi;
  od;
  pw:=p{[1..2*n-1]};
  p[2*n]:=First(ran,i->not i in pw);
  # now translate p to permutation
  for j in [1..n] do
    a:=p[2*j-1];
    b:=p[2*j];
    pl[a]:=b;
    pl[b]:=a;
  od;
  e:=PermList(pl);
  orb:=Orbit(group,e);
  if Length(Intersection(orb,orbits))=0 then
    # we have found a new one
    AddSet(orbits,e);
    lengthsum:=lengthsum+Length(orb);
    Print("#I  Length ",Length(orb)," found, total ",lengthsum," \n");
  fi;
  while i>2 and l[i]>Length(sel[i]) do
    i:=i-2;
    l[i]:=l[i]+1;
  od;
until l[i]>Length(sel[i]) or lengthsum=class;
Print("#I  class constructed up to ",e,"\n");

Print("number of orbits : ",Length(orbits),"\n");
return orbits;
end;

For curiosity, I used both routines for n=6 on a DECstation 5000. The first
routine took 1700 seconds, while the second one finished after
about 105 seconds. (Both routines ran in the initial 3MB memory).

I hope this helps,

Alexander Hulpke

-- Alexander Hulpke, Lehrstuhl D f"ur |Ce po`eme est, en effet, divis'e en
   Mathematik, RWTH Aachen            |cinq strophes successivement et respec-
                                      |tivement compos'ees de 3-1-4-1-5 vers,
  ahulpke@math.rwth-aachen.de         |   Jacques Bens:  Le sonnet irrationnel