12
$\begingroup$

Can we say anything about a minimal generating set of a finite group based on its normal subgroups? For example, can we bound their order, or say whether they come from the same conjugacy class?

An easy example is that when $G$ is cyclic, if $x$ generates $G$ then $x$ does not generate any (normal) subgroup of $G$.

If it isn't possible in general to relate a minimal set of generators of a finite group to its normal subgroups, can we do this when $G$ is generated by only 2 or 3 elements?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ One cannot talk about the generators of a group. For instance, one can take the entire group as a generating set. $\endgroup$
    – Moishe Kohan
    Commented May 16 at 0:08
  • 3
    $\begingroup$ Every finite simple group is generated by two elements. There is an extensive research on this. Maybe if you have only a few normal subgroups one might be able to restrict the number of generators? $\endgroup$
    – Yiftach Barnea
    Commented May 16 at 0:37
  • 5
    $\begingroup$ Please do not post simultaneously here and in math.stackexchange. Especially if you do not alert readers of the double post. $\endgroup$
    – Arturo Magidin
    Commented May 16 at 0:45
  • 4
    $\begingroup$ math.stackexchange copy has been deleted on that site. $\endgroup$
    – Arturo Magidin
    Commented May 16 at 1:32
  • 2
    $\begingroup$ I should add that for a $p$-group if you have $k$ normal subgroups, then in particular, you have at most $k$ maximal normal subgroups, Thus, if $\Phi(G)$ is the Frattini subgroup, then $G/Phi(G)$ has at most $k$ maximal subspaces, so its dimension, which is also the number of generators, is at most about $\log_p k$ (I am too tired now to figure out the $\pm 1$). $\endgroup$
    – Yiftach Barnea
    Commented May 16 at 2:22

2 Answers 2

Reset to default
12
$\begingroup$

The arXiv paper The Minimum Generating Set Problem by Lucchini and Thakkar (to be published in Journal of Algebra) describes an algorithm for finding a smallest-sized generating set of (a finite group) $G$ starting from a chief series $G = N_u > N_{u-1} > \dotsb N_1 > N_0= \{1\}$ of $G$.

The idea is to successively find smallest-sized generating sets of the quotients $G/N_{u-1}, G/N_{u-2},\dotsc,G/N_1,G/N_0 \cong G$. The top factor is simple and either cyclic with one generator, or nonabelian simple with two generators, which can quickly found by a random search.

Defining $d(G)$ to be the smallest size of a generating set of $G$, there is a useful result that, for a minimal normal subgroup $N$ of $G$, we always have $d(G/N) \le d(G) \le d(G/N)+1$ and, furthermore, if $d(G/N) = d$ with $G/N = \langle g_1N,\ldots,g_dN\rangle$, then either $d(G) = d(G/N)$ and there exist $n_1,\dotsc,n_d \in N$ with $G = \langle g_1n_1,\dotsc,g_dn_d \rangle$; or $d(G) = d(G/N)+1$ and there exist $n_1,\dotsc,n_d,n_{d+1} \in N$ with $G = \langle g_1n_1,\dotsc,g_dn_d,n_{d+1} \rangle$.

The bulk of the paper is describing methods to decide which of the two cases we are in when moving from $G/N_i$ to $G/N_{i-1}$ without recourse to too many exhaustive searches through all $d$- or ($d+1$)-tuples of elements of $N$. Implementations run very fast in practice.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Does it mean that $d(G)$ is bounded by something linear in the number of normal groups because $u$ is bounded by the number of normal subgroups? Is that best? $\endgroup$
    – Yiftach Barnea
    Commented May 16 at 9:52
  • 1
    $\begingroup$ @YiftachBarnea Yes it clearly implies that $d(G)$ is bounded by the length of a chief series, and that bound is attained in an elementary abelian group, for example. There could be a better bound in terms of the number of normal subgroups. $\endgroup$
    – Derek Holt
    Commented May 16 at 11:50
3
$\begingroup$

Let me improve my comment above. Let $G$ be a finite $p$-group generated by $d$ elements. Let $\Phi(G)=G^p[G,G]$ be its Frattini subgroup. Then $G/\Phi(G)$ is an elementary abelian $p$-group of order $p^d$, that is, a vector space of dimension $d$ over a field of $p$ elements. The number of subspaces in such vector space is about $p^{d^2/4}$ (see somewhere in Chapter 1 of Subgroup Growth by Lubotzky and Segal). Each such subspace corresponds to distinct normal subgroup of $G$. Thus, if $n(G)$ is the number of normal subgroups of $G$, we get that $n(G) \geq p^{d^2/4}$ or in other words $2\sqrt{\log_p(n(G))} \geq d$.

Notice that the best bound is achieved for elementary abelian $p$-group. It seems natural to ask what can be done for finite soluble groups and more generally for any finite group.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ I would conjecture that $d(G) = O(\log n(G))$ for general finite groups $G$, and it might be possible to prove it. $\endgroup$
    – Derek Holt
    Commented May 18 at 21:20
  • $\begingroup$ @DerekHolt I guess the most obvious example is direct sum of the same simple group, say $A_5$. Both the number of generators and the number of normal subgroups grows very slowly with the number of components. I am too tired now to think about it, but it might give an interesting example. $\endgroup$
    – Yiftach Barnea
    Commented May 19 at 11:08
  • 1
    $\begingroup$ For a finite nonabelian simple group $S$ there is a bound $d(S^n) \le 2 + \log_{60} n$ due to Wiegold, which supports my conjecture. I am not sure whether there is a known lower bound - there probably is. $\endgroup$
    – Derek Holt
    Commented May 19 at 11:46
  • $\begingroup$ @DerekHolt so $n(S^k)=2^k$ so we actually get something like $\log \log n(S^k)$ is about $d(S^k)$. Much better than your conjecture. Possibly $p$-groups are the worst case. $\endgroup$
    – Yiftach Barnea
    Commented May 19 at 13:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .