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

[Colva Roney-Dougal]

Dear all

I have to admit, since the question was about small groups, I wasn’t thinking about efficiency. Some of my suggestion would only need to be done once for each group when building the database (e.g. minimal number of generators and lex-least). For a look-up, I would guess less work needs to be done. First filter by order, then (expensively) find conjugacy classes, and then try to conjugate the group to contain the target generators. This would be repeated element conjugacy in S_n (and in various element centralisers in S_n) so wouldn’t be too bad.

I agree that it’s not efficient, but for smallish groups it would work fine

Colva


>> 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

*************************************

Colva Roney-Dougal
Reader in Pure Mathematics
Director of the Centre for Interdisciplinary Research in Computational Algebra
Editor of Proceedings A of the Royal Society of Edinburgh
Editor of Royal Society Open Science
Director of Undergraduate Mathematics Admissions

The University of St Andrews is a charity registered in Scotland : No SC013532