> < ^ From:

< ^ Subject:

Dear GAP-forum,

Sebastian Egner asked:

I am looking for the fastest method to decide if two

permutation groups are conjugated in a sufficiently

large symmetric group and if so to find a conjugating

permutation.

In other words: Given permutation groups G, H, solve

the problem

S := SymmetricGroup(

Maximum( PermGroupOps.LargestMovedPoint(G),

PermGroupOps.LargestMovedPoint(H) ));

x := RepresentativeOperation(S,AsSubgroup(S, G),AsSubgroup(S, H));

This is -- of course -- the standard GAP semantics for solving this problem.

In the best of all possible worlds there would be a specific, fast, algorithm

to solve this problem. So far, a backtrack search for a conjugating element

is run. this search does not run over all elements of G, but the search

space might be still unfeasibly large.

Does someone know a method which does

not rely on character theory or brute force?

I'm a bit puzzled that you rule out character theory. Anyhow, I don't think,

it could give you more than weak necessary conditions.

Seriously, I doubt that there is a general solution, which works without

having to do any backtrack at all. In a general setup, the only possible

answer is: The method you suggested is the fastest possible.

There are, however lots of tricks one can play to reduce the amount of

work needed for the backtracks. To see what can be done, it would be

helpful to know a bit more about the groups you want to check for conjugacy:

- What degree ?

- What sizes are the groups ?

- Are they transitive ?

- Do they have common structure (for example all are abelian)?

- How many conjugacy tests do you have to do ?

Best,

Alexander Hulpke

> < [top]