2
$\begingroup$

Given a group $G$, say of some size $k$. Can it be shown that it actually has a generating set H whose size can be expressed in terms of $k$? Intuitively, one can say it should be say around $O(\log k)$, as we indeed multiply an element so many times and it begins to repeat after sometime, similar to a Divide and Conquer strategy, where we throw away half the problem at every instance and then move on.

$\endgroup$
2
1
$\begingroup$

$O(\log k)$ may be an upper bound on the number of generators. But $Z_n$ has only a single generator for any value of $n$, and $D_n$ is generated by just two generators.

$\endgroup$
1
  • 2
    $\begingroup$ But the answer to the question is yes, any group of order $k$ can be generated by $O(\log k)$ elements. $\endgroup$
    – Derek Holt
    Apr 6 '18 at 17:18

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.