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

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

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – argentpepper Nov 27 '12 at 19:33
  • $\begingroup$ 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. $\endgroup$ – Lukas Geyer Nov 27 '12 at 23:01
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You are right, I intended the logarithmic to be base 2. Thank you. $\endgroup$ – argentpepper Nov 1 '12 at 19:29

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.