Dear Colva, > On 19 Dec 2017, at 13:18, Colva Roney-Dougal > <colva.roney-dou...@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 _______________________________________________ Forum mailing list Forum@gap-system.org https://mail.gap-system.org/mailman/listinfo/forum
