[GAP Forum] efficient generating set for a permutation group

[Ignat Soroko]

Dear Alexander,

Thank you for your insights! Indeed, SubgroupProperty sped things up, and
everything works fast now.

There was a little issue when the returned subgroup is trivial, it caused
error in my subsequent code, but I can easily treat this case separately.
(I posted it in github.)

Best,
Ignat
https://www.math.lsu.edu/~ignatsoroko/



On Mon, Aug 3, 2020 at 10:51 AM Hulpke,Alexander <
Alexander.Hulpke at colostate.edu> wrote:

> Dear Forum, Dear Ignat Soroko,
>
> > Is there a way to make GAP
> > pass to a smaller generating set? Unfortunately, commands like
> > SmallGeneratingSet(Aut); never terminate.
>
> If you have a group with 10^5 generators or so probably a lot of the
> standard routines will reduce to a crawl -- e.g. `SmallGeneratingSet` uses
> the existing generator number as a starting point for reduction.
>
> However in your code you don't really need to collect all elements. Do the
> following changes
>
>
> > G:=Group(Union(List(gen,x->GeneratorsOfGroup(SymmetricGroup(x)))));
> > aut:=[];
> Aut:=Group(()); # trivial perm group
> > for g in G do
> > if ForAll([1..n-1],i->ForAll([i+1..n],j->m[i^g][j^g]=m[i][j])=true) then
> > Add(aut,g);
> Aut:=ClosureGroup(Aut,g);
> > fi;
> > od;
>
> This will eliminate redundant elements on the fly and result in a much
> smaller generating set.
>
> even better would be to use existing information to avoid unneeded tests
> (e.g. is you have already a subgroup U satisfying the condition and g does
> not, no element in the coset Ug will do either). You can replace the whole
> loop by:
>
>
> Aut:=SubgroupProperty(G,g->ForAll([1..n-1],i->ForAll([i+1..n],j->m[i^g][j^g]=m[i][j])=true));
>
> This is likely much faster.
>
> All the best,
>
>   Alexander Hulpke
>
>
>
>