23
$\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$
  • 7
    $\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
  • 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$ – Frieder Ladisch Dec 4 '15 at 11:44
40
$\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).

| cite | improve this answer | |
$\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
  • 9
    $\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
24
$\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.

| cite | improve this answer | |
$\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
  • 6
    $\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
  • 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$ – Fedor Petrov Dec 4 '15 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$?

| cite | improve this answer | |
$\endgroup$

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.