[GAP Forum] Remarks on SmallGeneratingSet

[Mathieu Dutour]

Hi All,

I have some remarks on the performance of SmallGeneratingSet.

Back to the code of SmallGeneratingSet:
1) The code of SmallGeneratingSet uses a "LogPerm" operation.
It is a sophisticated algorithm for testing if a permutation is a power
of the other. The idea is to avoid computing all the powers. From my
viewpoint, a potential problem is that this function starts by computing
the order of the elements. Doesn't that computation require the computation
of the sequential element powers? Or is the order computed at the
permutation construction?

2) The computation of lower bounds on the number of generators
is in my opinion broken. The code is
  # minimal: AbelianInvariants

min:=Maximum(List(Collected(Factors(Size(G)/Size(DerivedSubgroup(G)))),x->x[2]));
    min:=Maximum(min,2);
I do agree that for a group of the form Z_2^{10} there is a lower bound of
10 on the number of generators. However the value of min is also 10 for
the cyclic group of order 1024 which is clearly wrong.
I think it is difficult to identify lower bound on the number of generators
in
a fast way and that we may be content with 1 for commutative and 2 for
non-commutative groups.

3) The next check
    if min=Length(GeneratorsOfGroup(G)) then return GeneratorsOfGroup(G);fi;
is suboptimal since the work precedingly using LogPerm has obtained a small
set of generators gens. This is what the comparison should be with.

4) The sequential list of checks
        ok:=true;
        # first test orbits
        if ok then
          ok:=Length(orb)=Length(Orbits(U,MovedPoints(U))) and
              ForAll(orp,x->IsPrimitive(U,orb[x]));
        fi;
        StabChainOptions(U).random:=100; # randomized size
#Print("A:",i,",",j," ",Size(G)/Size(U),"\n");
        if ok and Size(U)=Size(G) then
          gens:=Set(GeneratorsOfGroup(U));
        fi;
is I think suboptimal.
The first check should be whether MovedPoints(U) has the same length
as MovedPoints(G). The second check should be about the second check
with the number of orbit. This is because if U=SymmetricGroup(4) and
G=SymmetricGroup(5) we pass the first equality check while we should not.

5) This consistency check should be rewritten as a lambda function. This
is because it is reused in the last sequence of the code where generators
are checked one by one. Note also that this code has obvious issues as the
"ok" is computed without being used.

6) I disagree with the
  if not IsAbelian(G) then
    i:=i+1;
  fi;
It is true that if the group is not Abelian then the lower bound on the
number
of generators is now 2. However, the i is not used as a lower bound but as
an index. Thus it is perfectly possible that the first generator in gens is
redundant
and so there is no reason for increasing the index.

Note that none of those issues led to an inexact result. The resulting
generating set may be larger than necessary, but it is still generating.

I am doing this because I am reimplementing some part of the GAP
code for permutation groups in C++ as a header only library. This is
because it is rather unwieldy to use GAP from C++ and I thought that
this was a better approach to having permutation group in C++. See
https://github.com/MathieuDutSik/permutalib which has the same
licensing as GAP. I am using this code in
https://github.com/MathieuDutSik/polyhedral_common
but I am open to contributions if there are other interests.

Thank you very much for all your work,

  Mathieu