In a paper that I am reading, the author claims that

Any group $G$ has a generating set of cardinality $\log|\,G\,|$ or less.

Can someone show the ideas that went into this statement?

The paper, although irrelevant to this particular question, can be found here and the statement is the first sentence of section 1.2 on the 4th page of the PDF.

  • $\begingroup$ $\log(G)$ is not well defined. If $|\, G \,|$ is the cardinality of $G$, then I think he/she means $\log |\, G\, | $ $\endgroup$ Dec 3, 2013 at 22:26
  • $\begingroup$ Yes, I actually copied the statement omitting that by mistake (will edit now). Still my question stands. $\endgroup$ Dec 3, 2013 at 22:26
  • $\begingroup$ Unless he/she's talking about some form of discrete logarithm? EDIT: never mind $\endgroup$ Dec 3, 2013 at 22:28
  • 3
    $\begingroup$ This is answered in the second answer here, I think: math.stackexchange.com/questions/114931/… $\endgroup$ Dec 3, 2013 at 22:34
  • 1
    $\begingroup$ @universalset, and what a beautiful answer they gave! $\endgroup$ Dec 3, 2013 at 22:47

1 Answer 1


Hint: Let $|G|=n$. Take $e \neq g_1 \in G$ and consider $\langle g_1 \rangle$. Since $g_1 \neq e$, then $|\langle g_1 \rangle| \geq 2$. If $G = \langle g_1 \rangle$ then $G$ is generated by 1-element set, else let $g_2 \in G - \langle g_1 \rangle$. Consider $\langle g_1,g_2 \rangle$. Since $\langle g_1 \rangle$ is a proper subgroup of $\langle g_1,g_2 \rangle$ (it should have index at least 2), we obtain $|\langle g_1,g_2 \rangle| \geq 2\cdot2$. What we'll obtain after $\log n$ steps?

  • $\begingroup$ How do we know that we can proceed after step $i$? In other words, what prevents $G-\langle g_1, g_2,\ldots, g_{i-1}\rangle$ from being empty? $\endgroup$ Dec 3, 2013 at 22:44
  • 1
    $\begingroup$ @ijkilchenko: If it is empty then we have a generating set with $i-1$ elements. But anyway $i-1 \leq \log n$. $\endgroup$
    – user35603
    Dec 3, 2013 at 22:48
  • $\begingroup$ Oh, I see. In that case, $2^{i-1} \leq n$, so the cardinality of the generating set is $i-1$ and $i-1 \leq \log(n)=\log|G|$. $\endgroup$ Dec 3, 2013 at 22:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .