[GAP Forum] efficient generating set for a permutation group

[Hulpke,Alexander]

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