> < ^ From:

< ^ Subject:

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

> < [top]