# How large can the smallest generating set of a group $G$ of order $n$ be?

Let $n$ be a natural number. For every group $G$ of order $n$, denote

$d(G)$ : The number of elements of the smallest generating set of $G$

How large is the maximum possible value of $d(G)$ depending on $n$ ?

If $n$ is a cyclic number, we have $d(G)=1$ for every group of order $n$. For $n=2p$ , $p$ an odd prime, there are two groups : the cyclic group and the dihedral group with $2$ generators, so in this case the maximum value is $2$.

But I wonder, if the maximal value for $d(G)$ can be determined in general, assuming the factorization of $n$ is known. Is the value known for $n=2048$, for example ?

• For $n=2048$ the maximum value of $d(G)$ is 11, obtained by $(\mathbb{Z}/2\mathbb{Z})^{11}$. – Richard Stanley Dec 3 '15 at 13:30
• For p-groups, the Burnside Basis Theorem tells you exactly how many generators you need (and the elementary abelian case is indeed the worst case). – Noah Snyder Dec 3 '15 at 13:39
• For group of order $p^n$ simply choose elements $a_1,a_2,\dots$ such that $a_k$ does not lie in a subgroup $G_{k-1}$ generated by $a_1,\dots,a_{k-1}$. Then $|G_0|=1$, $|G_k|\geq p|G_{k-1}|$, hence this process stops on at most $n$ steps. – Fedor Petrov Dec 3 '15 at 13:44
• I am curious why there are 3 votes to close this? – Benjamin Steinberg Dec 4 '15 at 1:24
• @BenjaminSteinberg: It's maybe also because, while determining the maximum value of $d(G)$ from the factorization of the order $n$ is a delicate and interesting question, the choice of the particularly bad example $n=2^{11}$ shows a certain lack of understanding. (I did not vote to close.) – Frieder Ladisch Dec 4 '15 at 11:44

By a Theorem of Guralnick and Lucchini (which does require CFSG), if each Sylow subgroup of $G$ (ranging over all primes) can be generated by $r$ or fewer elements, then $G$ can be generated by $r+1$ or fewer elements. As noted in comments, if $G$ has a Sylow $p$-subgroup $P$ of order $p^{a}$, then $P$ can be generated by $a$ or fewer elements (and $a$ are needed if and only if $P$ is elementary Abelian). Hence if $|G|$ has prime factorization $p_{1}^{a_{1}}p_{2}^{a_{2}} \ldots p_{r}^{a_{r}}$ with the $p_{i}$ distinct primes, and the $a_{i}$ positive integers, then $G$ can be generated by $1 + {\rm max}(a_{i})$ or fewer elements.

(The result attributed to Guralnick and Lucchini was not a joint paper, rather a result proved independently at around the same time: references:

R. Guralnick, "A bound for the number of generators of a finite group, Arch. Math. 53 (1989), 521-523.

A Lucchini: "A bound on the number of generators of a finite group", Arch. Math 53, (1989), 313-317).

• Interesting. I have a related vague question: Assume $G$ embedds in $S_n$. Your answer gives a bound of $n$ on the number of generators. For abelian $G$ this is tight (up to a multiplicative constant, maybe). Is there some family of $G$'s for which we have a better bound? E.g., simple subgroups of $S_n$? – Ofir Gorodetsky Dec 3 '15 at 14:19
• Simple groups are all $2$-generated. – Derek Holt Dec 3 '15 at 14:21
• @FriederLadisch : The result was proved independently by Guralnick and Lucchini at around the same time, it was not a joint paper - I had forgotten that myself! – Geoff Robinson Dec 4 '15 at 0:20
• @GeoffRobinson: Thank you very much! – Frieder Ladisch Dec 4 '15 at 11:33

The general answer (as a function just of $n$, rather than of its factorization into primes) is $\log_2 n$. It is elementary to prove that this number suffices. Just choose $1 \ne g_1,g_2,g_3,\ldots \in G$ with $g_{i+1} \not\in G_{i} := \langle x_1,\ldots,x_i \rangle$, until $G_k=G$. Since each $G_i <G_{i+1}$ for $i<k$, we have $|G_{i+1}/G_i| \ge 2$, so $|G| = |G_k| \ge 2^k$.

But since an elementary abelian $2$-group requires that number of generators, this bound is best possible.

• .You could add: "... and unlike Geoff's answer, this doesn't require CFSG!" – Stefan Kohl Dec 3 '15 at 14:48
• @Peter Classification of finite simple groups. – Igor Rivin Dec 3 '15 at 14:52
• $\log_2\,n$ is an upper bound, but sometimes one can do better. For instance, if $n$ is a product of distinct primes $p_i$, and no $p_i|(p_j-1)$, then every group of order $n$ is cyclic. – Richard Stanley Dec 3 '15 at 16:12
• With all due respect, I do not agree that $\log_2 n$ is "the general answer", since in the question it is assumed that the factorization of $n$ is known, and for example if $n$ is a big prime, then $\log_2 n$ is pretty far of the right answer. $\log_2 n$ is only the answer for $n$ a power of $2$, and also $2$-powers yield the biggest values. – Frieder Ladisch Dec 3 '15 at 19:12
• I would formulate it in the following way: for groups with at most $n$ elements, maximum is $[\log_2 n]$. While for groups with exactly $n$ elements it is a delicate question. What may be said for sure is that the answer is either $m$ or $m+1$, where $m$ is maximal exponent of primes in factorization of $n$. – Fedor Petrov Dec 4 '15 at 10:39

For natural $$n$$, let $$d(n)$$ be the maximum of $$d(G)$$ as $$G$$ runs through all groups of order $$n$$, and let $$\nu(n)$$ denote the maximal exponent occurring in the canonical prime factorization of $$n$$. It follows from answers and comments elsewhere in this thread that $$d(n)= \begin{cases} 1+\nu(n) & \text{for } n\in S \\ \nu(n) & \text{otherwise} \end{cases}$$ where $$S\subseteq\mathbb{N}$$ is a set that we would like to characterize as precisely as possible.

I have now added an entry A332766 in OEIS listing the members of $$S = \{ 6, 10, 14, 18, 21, 22, \ldots\}$$. Does anyone have any nontrivial contribution to the characterization of $$S$$?