[GAP Forum] Canonical form for some small groups and efficient characterisation of the generalized symmetric groups

[Christopher Jefferson]

> On Dec 19, 2017, at 6:30 PM, Rubey Martin <martin.rubey at tuwien.ac.at> wrote:
> 
> The bad news is that there is apparently no canonical form for permutation
> groups up to conjugacy.
> 
> Indeed, the best thing would be what you called an "intrinsic" canonical form:
> a function f: permutation groups up to conjugacy -> strings such that
> 
> * f(G) can be computed in sensible time
> * f(G) = f(H) if and only if G and H are conjugate
> 
> It would be even better, if
> 
> * f has an inverse, that is, I can reconstruct G from f(G) in reasonable time
> * f(G) is human readable
> 
> In principle it should be possible to get by even without a canonical form,
> replacing it with a check for equality (in the case at hand: conjugacy), but
> that would be an awful lot of work, both technically and socially - not
> everybody in the findstat team is a big fan of having groups as a collection.
> 
> To make "sensible time" a little more concrete, it would be completely OK
> to compute the canonical form of the smallest 1000 groups in about a minute.
> For graphs it takes 15 seconds on my laptop.
> 

Looking at the comparison with graphs is interesting.

In the same way that nasty can calculate both graph automorphism and graph canonical image, I am working on extending Partition Backtrack to solve both the conjugacy problem and the canonical image problem for groups, expect a release next year.

However, having a “sensible string” is probably impossible. Nauty doesn’t produce a “sensible string” to describe the automorphism of graphs.

Also, in general Nauty can sometimes find the canonical image and automorphism group G of large graphs thousands of times faster than GAP can find the size of the group G, given the generators from Nauty! Similarly, it is hard to find graphs with less than a thousand vertices where Nauty takes a measurable amount of time, but easy to find pairs of groups G and H on even 25 points which GAP takes a long time to intersect (not the same as canonical image, but probably easier).

In short, I think your problem is solvable using a clever backtrack search, but you are never going to get a nice string, and don’t use Nauty as a guide for the performance you can expect!

Chris