Implement a function for finding minimum generating set of a group

[RuchitJagodara]

Problem Description

Currently, SageMath (or GAP) does not have any function to find the minimum generating set of a group. If a user wants to find the minimum generating set of a group, they have to go through all possible combinations of the elements of the group. As a result, the time complexity of this algorithm becomes exponential in terms of the cardinality of the group, which takes a lot of time for large groups.

Proposed Solution

Implement a polynomial time (in terms of cardinality of a group) algorithm to find the minimum generating set of a group using the logic provided in the research paper.

Alternatives Considered

Users can manually implement the logic provided in the research paper, but a built-in function would simplify the process and promote code reusability.

Additional Information

No response

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

[grhkm21]

The paper requires knowing the "chief series" of the group, and Sage doesn't seem to provide functionality for that.

[RuchitJagodara]

Actually, the chief series is just used to improve the efficiency of the algorithm, but even without using it, we can still implement the algorithm, which will have a polynomial time complexity. The only difference would be in the constant factor, which I think doesn't matter for now. (I have talked to one of the authors, Dhara Thakkar, of the research paper and confirmed this.)

I have also completed the implementation of the algorithm, and it is working fine. I will be making a PR very soon.

[kedlaya]

As a matter of implementation, in practice it would be much more efficient to first ask for a random small generating set:

sage: G = GL(10, 2)
sage: s = G.gap().SmallGeneratingSet() #random
sage: len(s)
2

as then one only has to look for even smaller generating sets. (In this example one doesn't have to do anything at all except notice that G is not cyclic, so it cannot be generated by one element!)

[pranav-joshi-iitgn]

Apparently GAP does have the MinimalGeneratingSet function which assumes that the group is either Solvable, already has a generating set of length 2, or is Finite. SageMath is unable to utilise the function fully I think.
For example, running this via sage on $A_5\times A_5$ gives :

sage: A5 = libgap.AlternatingGroup(5);
sage: G = libgap.DirectProduct(A5,A5);
sage: libgap.MinimalGeneratingSet(G);
---------------------------------------------------------------------------
GAPError                                  Traceback (most recent call last)
<ipython-input-4-bbfee5cc4a32> in <module>
----> 1 libgap.MinimalGeneratingSet(G);

/usr/lib/python3/dist-packages/sage/libs/gap/element.pyx in sage.libs.gap.element.GapElement_Function.__call__ (build/cythonized/sage/libs/gap/element.c:19906)()
   2521         try:
   2522             sig_GAP_Enter()
-> 2523             sig_on()
   2524             if n == 0:
   2525                 result = CALL_0ARGS(self.value)

GAPError: Error, `MinimalGeneratingSet' currently assumes that the group is solvable, or
already possesses a generating set of size 2.
In general, try `SmallGeneratingSet' instead, which returns a generating
set that is small but not of guaranteed smallest cardinality

while running on the same group in GAP gives :

gap> A5 := AlternatingGroup(5);
Alt( [ 1 .. 5 ] )
gap> G := DirectProduct(A5,A5);
Group([ (1,2,3,4,5), (3,4,5), (6,7,8,9,10), (8,9,10) ])
gap> MinimalGeneratingSet(G);
[ (2,5,3)(6,9,7,10,8), (1,5,4,3,2)(6,7,10,9,8) ]

If I had to guess, sage is using only the upper function in GAP (code below) for all groups, finite or not.

#############################################################################
##
#M  MinimalGeneratingSet(<G>) . . . . . . . . . . . . . for groups
##
InstallMethod(MinimalGeneratingSet,"test solvable and 2-generator noncyclic",
  true, [IsGroup and IsFinite],0,
function(G)
  if not HasIsSolvableGroup(G) and IsSolvableGroup(G) and
     CanEasilyComputePcgs(G) then
    # discovered solvable -- redo
    return MinimalGeneratingSet(G);
  elif not IsSolvableGroup(G) then
    if IsGroup(G) and (not IsCyclic(G)) and HasGeneratorsOfGroup(G)
        and Length(GeneratorsOfGroup(G)) = 2 then
      return GeneratorsOfGroup(G);
    fi;
  fi;
  TryNextMethod();
end);

#############################################################################
##
#M  MinimalGeneratingSet(<G>)
##
InstallOtherMethod(MinimalGeneratingSet,"fallback method to inform user",true,
  [IsObject],0,
function(G)
  if IsGroup(G) and IsSolvableGroup(G) then
    TryNextMethod();
  else
    Error(
  "`MinimalGeneratingSet' currently assumes that the group is solvable, or\n",
  "already possesses a generating set of size 2.\n",
  "In general, try `SmallGeneratingSet' instead, which returns a generating\n",
  "set that is small but not of guaranteed smallest cardinality");
  fi;
end);

InstallOtherMethod(MinimalGeneratingSet,"finite groups",true,
  [IsGroup and IsFinite],0,
function(g)
local r,i,j,u,f,q,n,lim,sel,nat,ok,mi;
  if not HasIsSolvableGroup(g) and IsSolvableGroup(g) and
     CanEasilyComputePcgs(g) then
    return MinimalGeneratingSet(g);
  fi;
  # start at rank 2/abelian rank
  n:=AbelianInvariants(g);
  if Length(n)>0 then
    r:=Maximum(List(Set(List(n,SmallestPrimeDivisor)),
      x->Number(n,y->y mod x=0)));
  else r:=0; fi;
  #......
  ##More code
  #.....
  #.....
end);

[kedlaya]

What version of GAP did you use for the direct test? I just tried it on the local install on 4.12.1, and the version 4.12.2 that comes up under the Sage shell; and in both cases I got the same error message as in Sage. But maybe this is a GAP bug that was fixed in a more recent version?

[pranav-joshi-iitgn]

What version of GAP did you use for the direct test? I just tried it on the local install on 4.12.1, and the version 4.12.2 that comes up under the Sage shell; and in both cases I got the same error message as in Sage. But maybe this is a GAP bug that was fixed in a more recent version?

I used version 4.14 . You're probably right.

[kedlaya]

Issue #37616 seems to about updating the GAP version in Sage to 4.13, maybe make that issue a dependency of this one?