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$ – Zubin Mukerjee Dec 3 '13 at 22:26
  • $\begingroup$ Yes, I actually copied the statement omitting that by mistake (will edit now). Still my question stands. $\endgroup$ – bourbaki4481472 Dec 3 '13 at 22:26
  • $\begingroup$ Unless he/she's talking about some form of discrete logarithm? EDIT: never mind $\endgroup$ – Zubin Mukerjee Dec 3 '13 at 22:28
  • 3
    $\begingroup$ This is answered in the second answer here, I think: math.stackexchange.com/questions/114931/… $\endgroup$ – universalset Dec 3 '13 at 22:34
  • 1
    $\begingroup$ @universalset, and what a beautiful answer they gave! $\endgroup$ – bourbaki4481472 Dec 3 '13 at 22:47

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$ – bourbaki4481472 Dec 3 '13 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 '13 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$ – bourbaki4481472 Dec 3 '13 at 22:52

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.