27
$\begingroup$

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 ?

$\endgroup$
11
  • 8
    $\begingroup$ For $n=2048$ the maximum value of $d(G)$ is 11, obtained by $(\mathbb{Z}/2\mathbb{Z})^{11}$. $\endgroup$ Dec 3, 2015 at 13:30
  • 3
    $\begingroup$ 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). $\endgroup$ Dec 3, 2015 at 13:39
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 3, 2015 at 13:44
  • 2
    $\begingroup$ I am curious why there are 3 votes to close this? $\endgroup$ Dec 4, 2015 at 1:24
  • 2
    $\begingroup$ @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.) $\endgroup$ Dec 4, 2015 at 11:44

3 Answers 3

44
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ 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$? $\endgroup$ Dec 3, 2015 at 14:19
  • 9
    $\begingroup$ Simple groups are all $2$-generated. $\endgroup$
    – Derek Holt
    Dec 3, 2015 at 14:21
  • 2
    $\begingroup$ @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! $\endgroup$ Dec 4, 2015 at 0:20
  • $\begingroup$ @GeoffRobinson: Thank you very much! $\endgroup$ Dec 4, 2015 at 11:33
25
$\begingroup$

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.

$\endgroup$
12
  • 3
    $\begingroup$ .You could add: "... and unlike Geoff's answer, this doesn't require CFSG!" $\endgroup$
    – Stefan Kohl
    Dec 3, 2015 at 14:48
  • 3
    $\begingroup$ @Peter Classification of finite simple groups. $\endgroup$
    – Igor Rivin
    Dec 3, 2015 at 14:52
  • 3
    $\begingroup$ $\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. $\endgroup$ Dec 3, 2015 at 16:12
  • 7
    $\begingroup$ 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. $\endgroup$ Dec 3, 2015 at 19:12
  • 4
    $\begingroup$ 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$. $\endgroup$ Dec 4, 2015 at 10:39
1
$\begingroup$

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$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.