# How to find minimal generating sets efficiently?

Let $$G$$ be a group. A minimal generating set of $$G$$ is a subset of $$R$$ of $$G$$ that generates $$G$$ such that no proper subset of $$R$$ also generates $$G$$. For arbitrary groups is its not true (unlike vector space bases) that two minimal generating sets have the same cardinality. The minimal cardinality of the minimal generating sets of $$G$$ is denoted by $$d(G)$$ and the maximal cardinality of the minimal generating sets of $$G$$ is denoted by $$m(G)$$ (or sometimes $$\mu(G))$$. The standard example for groups that have $$d(G)\not=m(G)$$ is the symmetric groups. In this case Whiston proved that $$m(Sym(n))=n-1$$ and it is easily shown that $$d(Sym(n))=2$$.

In the case when $$d(G)=m(G)$$ then the following procedure can be used to generate a minimal generating set (all of which have the same number of elements). Randomly choose an element $$x\in G$$ and let $$H=\langle x\rangle$$. Now choose any element in $$y\in G$$. If $$y\not\in H$$ then add $$y$$ to $$H$$. If $$y\in H$$ then choose another element from $$G$$. Continue until $$H=G$$. The process will be efficient if there is an efficient way to determine if an element from $$G$$ is contained within the subgroup $$H$$. Here efficient means that the number of operations needed is $$O(r(\log(|G|)))$$ for some polynomial $$r$$ when $$|G|$$ finite and some thing else that is appropriate when $$G$$ is infinite. If this condition is to difficult then we can substitute a weaker definition.

If $$G$$ satisfies the condition $$d(G)=m(G)$$ then $$G$$ is called a $$\mathcal{B}$$-group and is said to have the weak basis property. A group $$G$$ is said to have the basis property if all its subgroups are $$\mathcal{B}$$-groups. Apisa and Klopsch proved that if $$G$$ is finite then $$G$$ is a $$\mathcal{B}$$-group if, and only if, one of the following holds (1) $$G$$ is a $$p$$-group for some prime $$p$$; (2) $$G=P\rtimes Q$$ where $$P$$ is a $$p$$-group and $$Q$$ is a cyclic $$q$$-group where $$p\not=q$$ and such that $$C_Q(P)\not=Q$$ and then $$\mathbb{F}_p[Q/C_Q(P)]$$-module $$P/\Phi(P)$$ is isotypical. A similar result is true for $$G$$ that have the basis property. These results generalize Burnside's basis theorem which is usually used to show that $$p$$-groups have $$d(G)=m(G)$$.

This means that we need only find an efficient membership test for $$p$$-groups and semidirect products $$p-$$groups and a cyclic $$p$$-group (whether the extra structure needed in the generalization of Burnside's theorem is needed is not clear to me) in order to efficiently find minimal generating sets of finite $$\mathcal{B}$$-groups.

Question 1: Is there an effective membership algorithm for $$\mathcal{B}$$-groups? I assume that there is from some comments but I as of yet I seem to not see it.

Computing packages like GAP will find minimal generating sets of minimal cardinality (i.e. $$d(G)$$) when possible). GAP's manual (as pointed out below) states that there are only efficient methods known for computing minimal generating sets of finite solvable groups and of finitely generated nilpotent groups - but does not provide references.

Now finite $$\mathcal{B}$$-groups are solvable and so they fit into the first category.

Question 2: What are references for these methods (finding minimal generating sets of minimal cardinality for finite solvable groups and of finitely generated nilpotent groups). If no references are possible how different are these methods since finite nilpotent groups are solvable?

Question 3: When $$G$$ is not a $$\mathcal{B}$$-group (so $$d(G)< m(G)$$) and when $$G$$ is still a finite solvable group or is a finitely generated nilpotent group is there a known relationship between $$d(G)$$ and $$m(G)$$ beyond $$d(G)?

Such algorithms can be used to help find groups that satisfy properties like: $$d(H) for all subgroups $$e\neq H\lneq K\leq G$$ (Which appear to have a similar structure for $$\mathcal{B}$$-groups or for groups that almost satisfy this property like $$n$$-qubit Pauli groups. But in general these types of questions are just interesting.

• Before anyone can answer that (at least for groups that are not $p$-groups), you need to say what you mean by a minimal generating set. Minimal cardinality, or minimal with respect to inclusion? For $p$-groups, choosing random elements and checking that they are not in the subgroup you have already is reasonably efficient. Commented Apr 30, 2021 at 7:21
• As I understand this question, you are asking how a particular software package does a particular job. This is something which is likely best addressed by the developers or maintainers of the the package. You also seem to be asking a second question which is unrelated to GAP, but my feeling is that this question is quite broad (as the classification of groups is a rather broad topic in the first place). Finally, as pointed out in the comment above, there is some ambiguity in your question. Can you please edit the question to clear up the ambiguity and to emphasize the mathematics? Commented May 1, 2021 at 18:26
• @DerekHolt I assumed that minimal generating set was defined by inclusion - but you are right that I should have stated that I am also looking for the case a minimal generating set that has $d(G)$ elements. GAP's MinimalGeneratingSet looks for such sets so I missed that. I have updated the question.
– vand
Commented May 3, 2021 at 4:55

Presumably you're referring to MinimalGeneratingSet. The reference page says

Note that –apart from special cases– currently there are only efficient methods known to compute minimal generating sets of finite solvable groups and of finitely generated nilpotent groups. Hence so far these are the only cases for which methods are available. The former case is covered by a method implemented in the GAP library, while the second case requires the package Polycyclic.

Digging through the source code, it's implemented for finitely generated abelian groups in grppc.gi using Smith Normal Form and a polycyclic generating set. For general polycyclic groups, it's implemented in grppcatr.gi it uses a special polycyclic generating set. I know neither enough GAP nor group theory to competently say more.

• You can also use GAP functionality to find out how it is doing something - see ApplicableMethod and other tips here and there. Commented May 1, 2021 at 9:56
• math.meta.stackexchange.com/q/33508/9003 Commented May 1, 2021 at 17:50
• @amWhy Is your implication that I should not have answered this question because it is "low quality"? That's a pretty weird and indirect way to say so. In any case, it seemed borderline enough to me to answer. Commented May 1, 2021 at 18:08
• I merely posted, hoping you would read the meta post and reconsider answering poor quality questions, at least until after you help the asker improve their question. No implication. Have a great day! :-) Commented May 1, 2021 at 18:16
• @amWhy Thank you, though I have almost no interest in hand-holding people through the process of improving low-quality questions. In this particular case I was personally curious about how GAP does this and so I dug into it a little. I also strongly feel that the OP is the least important audience. Even though the question is not great as-is, my answer and Alexander Konovalov's links could conceivably be useful to others in the future. If the MSE community wants my behavior to change, structural reform will be needed. Commented May 1, 2021 at 22:46

There are a couple of questions and multiple cases as asked, and it might be worth separating these. I will only consider the case of finite solvable groups here:

If the group is given by a polycyclic presentation, there are effective methods to test membership in subgroups, using induced generating sets. See chapter 8 in: Holt, Derek F.; Eick, Bettina; O’Brien, Eamonn A. Handbook of computational group theory. Discrete Mathematics and its Applications. Boca Raton, FL: Chapman & Hall/CRC Press

A generating set of minimal size for a finite solvable group arises from special polycyclic generating systems. The standard reference for this is: Cannon, John J.; Eick, Bettina; Leedham-Green, Charles R. Special polycyclic generating sequences for finite soluble groups. J. Symb. Comput. 38, No. 5, 1445-1460 (2004), though it does not spell ot the algorithm for such a generating set explicitly. (See the code in the GAP library for such an algorithm, whose correctness follows relatively straightforward from the definitions in the paper).

If the group is not solvable, there are heuristics that give bounds, but the only general algorithm I'm aware of is a rather inefficient exhaustive search.

• Thanks very much for the references and detail. Very helpful.
– vand
Commented May 4, 2021 at 0:47