0
$\begingroup$

$G$ is a permutation group. So, $G < S_n$ where $S_n$ is a symmetric group acts on $n$ object.

$G$ is not isomorphic to any symmetric or alternating group, i.e. $G \neq S_t , A_t$ for $1 <t \leq n$ where $S_t , A_t$ are symmetric group and alternating group respectively.

Question:

$k$ is the size of minimal generating set of group $G$.

How many minimal generating set of group $G$ are possible with size $k$?

$\endgroup$
  • 3
    $\begingroup$ I think this question is hopelessly broad. We know from Cayley's theorem that $G$ could be any group (except symmetric and alternating groups, by your exclusion). I suspect nobody can characterize the number of minimal generating sets of a generic group. You might want to play around with GAP (possibly through Sage) for some data, but I'm willing to bet it'll be all over the map. $\endgroup$ – pjs36 Jun 5 '16 at 1:15
2
$\begingroup$

The assumption $G \le S_n$ seems irrelevant. Every group embeds into a symmetric group, so $G$ might just as well be an arbitrary finite group.

If $|G|=m$ then the answer is clearly at most $\binom{m}{k}$ and in many (but not all) groups it is more than half of this number.

For example, for all finite nonabelian simple groups $G$, we have $k=2$ and the number of minimal generating sets is at least $53\binom{m}{k}/90$ with equality when $G=A_6$ (although I note that for some unknown reason you are not counting alterning or symmetric groups).

But for $G=A_5^{19}$, we still have $k=2$ but the number is much smaller as a proportion of $|G|$, and if you chose pairs of elements, you would be unlikely to find a pair of generators in the lifetime of the universe.

Cyclic groups are also interesting, where $k=1$ and the number of generators is $\Phi(m)$. Note that $\Phi(m)/m$ can be arbitrarily small.

$\endgroup$

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.