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 ?

Improve this question
$\endgroup$
11
  • 8
    $\begingroup$ For $n=2048$ the maximum value of $d(G)$ is 11, obtained by $(\mathbb{Z}/2\mathbb{Z})^{11}$. $\endgroup$
    – Richard Stanley
    Commented 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$
    – Noah Snyder
    Commented 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$
    – Fedor Petrov
    Commented Dec 3, 2015 at 13:44
  • 2
    $\begingroup$ I am curious why there are 3 votes to close this? $\endgroup$
    – Benjamin Steinberg
    Commented 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$
    – Frieder Ladisch
    Commented Dec 4, 2015 at 11:44

3 Answers 3

Reset to default
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).

Improve this answer
$\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$
    – Ofir Gorodetsky
    Commented Dec 3, 2015 at 14:19
  • 9
    $\begingroup$ Simple groups are all $2$-generated. $\endgroup$
    – Derek Holt
    Commented 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$
    – Geoff Robinson
    Commented Dec 4, 2015 at 0:20
  • $\begingroup$ @GeoffRobinson: Thank you very much! $\endgroup$
    – Frieder Ladisch
    Commented 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.

Improve this answer
$\endgroup$
12
  • 3
    $\begingroup$ .You could add: "... and unlike Geoff's answer, this doesn't require CFSG!" $\endgroup$
    – Stefan Kohl ♦
    Commented Dec 3, 2015 at 14:48
  • 3
    $\begingroup$ @Peter Classification of finite simple groups. $\endgroup$
    – Igor Rivin
    Commented 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$
    – Richard Stanley
    Commented 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$
    – Frieder Ladisch
    Commented 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$
    – Fedor Petrov
    Commented 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$?

Improve this answer
$\endgroup$

You must log in to answer this question.

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