11
$\begingroup$

It seems to be known that the minimum size of a generating set for a finite group of order $n$ is at most $\log_2 n$. Can someone explain why this is true?

Edit: noted that the logarithm is base 2, and $n$ represents the order of the group.

  • 0
    You mean: the maximum over all groups of order $\le n$ of the minimal size of a generating subset.2012-11-03

2 Answers 2

15

If $G$ is a finite group, and $\{g_1,\ldots,g_m\}$ is a minimal set of generators, let $G_n = \langle g_1,\ldots,g_n \rangle$. Then by minimality $g_k \ne e$ for all $k$, and $g_{n+1} \notin G_n$ for all $n$. Then $G_{n+1}$ contains at least the two disjoint cosets $eG_n=G_n$ and $g_{n+1}G_n$ of $G_n$, so $|G_{n+1}| \ge 2|G_n|$. By induction $|G| = |G_m| \ge 2^m$, so $m \le \log_2 |G|$. This inequality is sharp for $G = \mathbb{Z}_2^m$.

  • 0
    If $g_{n+1} \in G_n$, then you could remove $g_{n+1}$ from the set of generators and still generate the whole group, so this would violate minimality of the set of generators. The fact that the cosets are disjoint is a general fact in group theory. If $g \in G_n \cap g_{n+1} G_n$, then $g = g_{n+1} h$ with $h \in G_n$, so $g_{n+1} = g h^{-1} \in G_{n}$, a contradiction.2012-11-27
0

Think about the smallest group which needs $r$ generators - you will find that each generator has order 2, and that the group has order $2^r$ (this isn't a proof, but an indication of a method). Your statement is only true, therefore, if your logarithms are being taken to base 2.

  • 0
    You are right, I intended the logarithmic to be base 2. Thank you.2012-11-01