Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
You are right, I intended the logarithmic to be base 2. Thank you. –  argentpepper Nov 1 '12 at 19:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.