Remarks on SmallGeneratingSet

[hulpke]

Github seems to be a better place to respond to the points raised by Mathieu Dutour in https://mail.gap-system.org/pipermail/forum/2021/006314.html (partly reproduced below). I will do so later today.

---

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.

[olexandr-konovalov]

Thanks @hulpke - I will edit the post though so that it will be clear that this is not your text, but a quote from the Forum posts https://mail.gap-system.org/pipermail/forum/2021/006314.html by @MathieuDutSik (otherwise, it will be even more unclear for GitHub users who do not read GAP Forum). @MathieuDutSik thank you very much for your remarks - you'd be very welcome to post them in this issue tracker, that's a more appropriate place indeed.

[MathieuDutSik]

Thank you @hulpke for looking at the problem.
Let me know if you need some help.

[hulpke]

1: LogPerm: Computing the order of a permutation on $n$ points is much faster than testing powers: You calculate the cycle lengths of each point, and then take the LCM. This test did not seem to take significant time.

[hulpke]

2. Generators for G/G'

The purpose of SmallGeneratingSet is to find possibly a smaller generating set, but to do so at low cost. Low cost overrides small. The number calculated here is a stopping criterion, beyond which it might not be worth (or impossible) to reduce.

Since the groups are not solvable, the ``typical'' case (in the groups I have been working with) I typically have |G/G'| small, but there are situations where the rank can be higher. This test is basically to catch these cases.

I tried to compute the rank of G/G', but that turned out too costly in some cases. Thus I'm wilfully ignoring cases of large prime power factors (which I reckon are rare) as candidates for reduction, but save on the cost of always doing a rank computation.

[hulpke]

3. Thank you -- will change this.

4. The first check should be whether MovedPoints(U) has the same length
   as MovedPoints(G):
   Yes, the initial assignment of ok should be this value, also justifying the if. Will change.

5. I'm not sure I understand what a lambda function does. But indeed, one could re-use the test. Will do so.

[hulpke]

6. Yes, I think this is a relic of deleting old code but not doing it properly.

[MathieuDutSik]

5: I am advocating the use of lambda for the following reason.
We need a functionality to check if a set of generators is valid. That check is fairly consequential: Compute the orbits, then check for primitivity, then finally check for order. So, it is non-trivial code.

This check occurs in two places:

• When we select generators at random
• When we check if we can remove generators one by one.

See an example of such code in Kernel_SmallGeneratingSet in https://github.com/MathieuDutSik/permutalib/blob/master/src_gap/NormalStructure.h

[MathieuDutSik]

2: About the quotient G/G' can we agree to the two following points?

• The value of min for Z_2^{10} and Z_{1024} is 10 for both groups.
• The minimal number of generators is 10 for Z_2^{10} and 1 for Z_{1024}.

[fingolfin]

Regarding writing your own header-only C++ permutation groups code: perhaps take a look at http://www.math.uni-rostock.de/~rehn/software/permlib.html resp. https://github.com/tremlin/PermLib which already does that and has been extensively tested and used by various people. Unfortunately it has been dormant for many years (its author left academia), but it might still be much better than starting from scratch?

[hulpke]

5: I am advocating the use of lambda for the following reason.

I don't understand what you mean by the jargon word ``lambda'' and how it would differ from just putting the tests into a function.

[hulpke]

2: About the quotient G/G' can we agree to the two following points?

Yes. I never doubted this. But the purpose of the function is not to find a generating set of minimal size, but, at low cost, find a reasonably small one in many cases.
For me, the ``typical'' nonsolvable group has G/G' of low exponent (though of course one can easily create such groups), and the lack of optimality caused by the test is more than made up by not having to calculate the structure of G/G'.

[MathieuDutSik]

5: I am advocating the use of lambda for the following reason.

I don't understand what you mean by the jargon word ``lambda'' and how it would differ from just putting the tests into a function.

Oh, sorry for terminology confusion. I meant writing an internal function to the SmallGeneratingSet.

[MathieuDutSik]

2: About the quotient G/G' can we agree to the two following points?

Yes. I never doubted this. But the purpose of the function is not to find a generating set of minimal size, but, at low cost, find a reasonably small one in many cases.
For me, the ``typical'' nonsolvable group has G/G' of low exponent (though of course one can easily create such groups), and the lack of optimality caused by the test is more than made up by not having to calculate the structure of G/G'.

I see. Then maybe the name min is not appropriate since it definitely implies that it is an absolute lower bound on the number of generators while you mean something else.

[hulpke]

2: About the quotient G/G' can we agree to the two following points?

I see. Then maybe the name min is not appropriate since it definitely implies that it is an absolute lower bound on the number of generators while you mean something else.

OK. I will rename the variable.