19
$\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$
  • 5
    $\begingroup$ For $n=2048$ the maximum value of $d(G)$ is 11, obtained by $(\mathbb{Z}/2\mathbb{Z})^{11}$. $\endgroup$ – Richard Stanley Dec 3 '15 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$ – Noah Snyder Dec 3 '15 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$ – Fedor Petrov Dec 3 '15 at 13:44
  • 2
    $\begingroup$ I am curious why there are 3 votes to close this? $\endgroup$ – Benjamin Steinberg Dec 4 '15 at 1:24
  • 1
    $\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$ – Frieder Ladisch Dec 4 '15 at 11:44
38
$\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$
  • $\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$ – Ofir Gorodetsky Dec 3 '15 at 14:19
  • 8
    $\begingroup$ Simple groups are all $2$-generated. $\endgroup$ – Derek Holt Dec 3 '15 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$ – Geoff Robinson Dec 4 '15 at 0:20
  • $\begingroup$ @GeoffRobinson: Thank you very much! $\endgroup$ – Frieder Ladisch Dec 4 '15 at 11:33
22
$\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$
  • 3
    $\begingroup$ .You could add: "... and unlike Geoff's answer, this doesn't require CFSG!" $\endgroup$ – Stefan Kohl Dec 3 '15 at 14:48
  • 3
    $\begingroup$ @Peter Classification of finite simple groups. $\endgroup$ – Igor Rivin Dec 3 '15 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$ – Richard Stanley Dec 3 '15 at 16:12
  • 4
    $\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$ – Frieder Ladisch Dec 3 '15 at 19:12
  • 2
    $\begingroup$ @Lucia: When $|G| = p_1^{a_1} \dotsm p_k^{a_k}$, then the argument of this answer yields the bound $a_1 + \dotsb + a_k$ (in the worst case, as you say), while Geoff Robinson's answer yields a bound $ 1 + \max\{ a_i\} $. $\endgroup$ – Frieder Ladisch Dec 3 '15 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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