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