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