# Finding large irredundant generator sets for a finite noncommutative group

Suppose $G$ is a finite noncommutative group. A set $\{g_1,g_2,...,g_n\}$ of elements of $G$ is called irredundant if none of its elements is contained in the subgroup generated by the rest of elements (hope I properly use an already defined notion). Of course such a set is maximal if it can not be further extended i.e. it generates $G$ itself. I am looking for such maximal irredundant sets of generators of largest possible size $n$. As $G$ is finite, the existence of such sets is guaranteed.

From a theoretical point of view my question is then: what is known about the construction of such sets? From an application point of view actually I am interested in effective algorithmic computations for $G$, using GAP. As an example, in my case, think of the semidirect product of $S_6$ with $Z^6$, defined as a permutation group in GAP. In the case it is not known an algorithm to compute a largest maximal irredundant set of generators, I am interested in any algorithmic way of computing such maximal irredundant sets of generators. Of course I am looking for a set of largest size.

Thanks for any hint and advise.

• Such sets are often called independent generating sets. If you search for that, you will find some results. For example the largest size is $n-1$ for $S_n$.An earlier question on this topic was math.stackexchange.com/questions/1004210 From an algorithmic viewpoint I would expect the problem to be very hard. It is very easy to check whether a given set of generators is irredundant, but how could you establish purely computationally that the set had maximal size? – Derek Holt Oct 25 '16 at 12:21
• By the way, I don't understand your example. What is $Z^6$? "defined as a permutation group in GAP" is a strange way to define a group! – Derek Holt Oct 25 '16 at 12:54
• Sorry @Derek Holt, I would say $Z_2^6$. – Horváth S. Oct 25 '16 at 14:28
• Thanks @Derek Holt for the comments. I felt the earlier question on this topic useless to me. I felt also the sharp question (maximal size) could be hard from algorithmic viewpoint. This is why I said I would be happy to have an algorithm to compute several maximal independent generating sets. I can imagine well that such an algorithm can be set up using the many series of the group's subgroups. I also suspect that the answer can be hidden in the structure (graph) of the group's subgroup lattice, but I have no clue how. – Horváth S. Oct 25 '16 at 14:51
• There are several different semidirect products of $Z_2^6$ by $S_6$, but I am guessing that you are talking about the extension by the permutation module: i.e. $Z_2 \wr S_6$. In that case, assuming that the largest size of an irredundant generating set for $S_6$ is $5$, the largest size for the semidirect product in question must be $6$. – Derek Holt Oct 25 '16 at 22:16

This is difficult in general, but can often be computed. Dan Collins's undergrad thesis has some discussion of the question, e.g. see page 8. (He calls the largest size of an irredundant generating set $\overline r$; I'm more accustomed to calling it $m$.) One useful computational tool is the following result, which appears in some unpublished notes of Collins:
Lemma: if $N$ is a minimal normal subgroup of a finite group $G$ and $N$ is abelian, then $m(G) = m(G/N)$ if $N \leq \Phi(G)$, and $m(G) = m(G/N) + 1$ otherwise. (Here, $\Phi(G)$ is the Frattini subgroup. The first case is a standard fact and doesn't require minimality of $N$.)
This in particular allows one to recursively compute $m(G)$ for any finite solvable $G$, since a minimal normal subgroup of a solvable group is necessarily abelian. In Keith Dennis's 2013 REU program at Cornell, Atticus Christensen and I (also unpublished) observed that this lemma can also be used to calculate $m(G)$ where $G$ is the wreath product $(\mathbb Z/2\mathbb Z) \wr S_n$, by reducing to Whiston's theorem that $m(S_n) = n-1$. Namely, $m(G)$ is $n$ if $n$ is even, and $n+1$ if $n$ is odd. The proof follows without too much difficulty from writing down all the normal subgroups contained in $(\mathbb Z/2\mathbb Z)^n$ (i.e. the $S_n$-invariant subspaces of $(\mathbb F_2)^n$) and checking which ones are contained in the Frattini subgroup.
To get an explicit irredundant generating set of $G = (\mathbb Z/2\mathbb Z) \wr S_6$ of size 6, you can take a size-5 irredundant generating set of (your favorite embedding of) $S_6 < G$, and append to it any element of $(\mathbb Z/2\mathbb Z)^6 < G$ with an odd number of 1's.