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

[Max Horn]

Dear Colva,

> On 19 Dec 2017, at 13:18, Colva Roney-Dougal <Colva.Roney-Dougal at st-andrews.ac.uk> wrote:
> 
> Dear Martin
> 
> Can I suggest as a canonical form for a conjugacy class of permutation group G \leq S_n
> 
> 1. Fix once and for all an ordering on the permutations in S_n - lex ordering when storing the permutations as their image lists would do.
> 2. Find the minimal number of generators d of G.

I.e. in GAP via `MinimalGeneratingSet` but unfortunately GAP only implements
this for solvable groups. I am not aware of an effective algorithm that
works in general, but that likely just means I am not well-informed :-).
Perhaps group recognition can help? (Not that this would be particularly
helpful for a GAP user at this stage, considering the unfinished and
incomplete state of the "recog" package:/)

But let's assume we solve that somehow.

> 3. Store a lex-minimal generating set amongst the different ones of size d?

But how would one compute that efficiently, even if d and a single minimal
generating set is known? I mean, at that point of course one can easily find
the lex-minimal conjugate of that particular generating set -- but not all
minimal generating sets will be conjugate (e.g. we can generate S_n by a
transposition and an n-cycle, or a transposition and an (n-1)-cycle). So we
really need all (conjugacy classes of) minimal generating sets of the input
group, wouldn't we? Or is there some clever way around this I am missing
here?


> I’m not completely sure this would work, and it would be awkward to compute, but it would give a canonical representative of each conjugacy class of groups?

I think it is indeed likely that one can define "canonical representatives"
or "canonical forms" this way, and then for a given d enumerate all
canonical forms of subgroups of S_n this way.

But I don't see how to perform lookup in there, i.e. how to "efficiently"
compute for a given group G its canonical representative. If anybody knows,
I'd be thrilled to hear.  But wouldn't that be a major breakthrough, as it'd
solve the whole subgroup conjugacy problem, wouldn't it?


Cheers,
Max