[GAP Forum] MinimalGeneratingSet

[Stefan Kohl]

Dear Forum,

On April 14, Jon Cohen asked:

> I think there is a bug with the MinimalGeneratingSet method (I am
> running GAP 4.4.4 and have installed the latest bugfix).
> 
> It does not seem to handle nonsolvable permutation groups:
> 
> gap> MinimalGeneratingSet(SymmetricGroup(4));
> [ (2,4,3), (1,4,2,3) ]
> 
> Is fine, but:
> 
> gap> MinimalGeneratingSet(SymmetricGroup(5));
> 
> gives an error. A quick look shows that the grpperm.gi code calls the
> grppcatr.gi MinimalGeneratingSet method only when the input group is
> solvable.

In general, getting a `no method found' - message does not indicate
an error. Such a message can indicate that a particular request
does not make sense. But it can also just mean that simply no suitable
method has been implemented so far.

Here the latter is the case.

Efficient methods for computing a minimal generating set are so far
only known for finite solvable groups and for finitely-generated
nilpotent groups.

Of course, the case of an arbitrary finite group could in principle be
treated by just looping over all pairs, triples, 4-tuples, ... of
generators until one finds some k-tuple which generates.

But the performance of this would be that horrible that nobody has seen
a benefit in implementing it in GAP so far.

Best wishes,

     Stefan Kohl