# Why is the minimum size of a generating set for a finite group at most $\log_2 n$?

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.

• You mean: the maximum over all groups of order $\le n$ of the minimal size of a generating subset. – YCor Nov 3 '12 at 20:22

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$.
• Why must there be an element $g_{n + 1}$ not in $G_n$? Also, can you explain why $|G_{n + 1}| \geq 2 |G_n|$? Why must the intersection of $eG_n$ and $g_{n + 1}G_n$ be empty? – argentpepper Nov 27 '12 at 19:33
• 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. – Lukas Geyer Nov 27 '12 at 23:01
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.