1
$\begingroup$

A set $S$ has $\log_2(|G|)$ distinct elements (arbitrary) of permutation group $G \leq S_n$. $S_n$ is symmetric group. i.e. $S \subset G$ and $|S| = \log_2(|G|) $.

Is it a generating set of $G$? i.e. $\langle S\rangle = G$ ?

The question came from this post . Some hint how I can prove it, will be appreciated.

$\endgroup$
  • 2
    $\begingroup$ If $\lvert G \rvert = 2$ then this is false. $G$ is then also a permutation group. If by permutation group you mean the group of permutations on $n$ elements, then $\lvert G \rvert = n!$ for some natural number $n$ and $\log_2(\lvert G \rvert)$ is a natural number only if $n = 2$ or $n = 1$. Even if you mean $\lvert S \rvert \geq \log_2(\lvert G \rvert)$, then the claim is still false for other $n$ (and I think it is false for all $n$). $\endgroup$ – Bib-lost Jun 2 '16 at 21:07
  • 1
    $\begingroup$ No, $G$ clearly contains proper subgroups $H$ of order $|H| \gg \log_2 |G|$. $\endgroup$ – anomaly Jun 2 '16 at 21:22
  • $\begingroup$ @Bib-lost , have a look at it math.stackexchange.com/questions/226931/… $\endgroup$ – Mike SQ Jun 2 '16 at 21:37
  • 1
    $\begingroup$ @MikeSQ: Right, and my post shows that the converse is false. $\endgroup$ – anomaly Jun 2 '16 at 21:42
  • 1
    $\begingroup$ If $|S|>|G|/2$, then it is guaranteed that $S$ generates $G$. This bound is sharp for symmetric groups. $\endgroup$ – Batominovski Jun 3 '16 at 10:50
1
$\begingroup$

An attempt to summarize what has been answered:

In the post you linked to, it is shown why for any finite group $G$, there exists some subset $S \subseteq G$ which generates $G$ and such that $\lvert S \rvert \leq \log_2(\lvert G \rvert)$. It is also shown that this inequality can be sharp.

You ask whether for any subset $S \subseteq G$ with $\lvert S \rvert = \log_2 (\lvert G \rvert)$ we have that $S$ is a generating set. Note first that, if there exists a subset $S \subseteq G$ with $\lvert S \rvert = \log_2 (\lvert G \rvert)$, then we must have that $\lvert G \rvert = 2^k$ for some $k \in \mathbb{N}$. An example of such a group $G$ is $C_{2^k}$, the cyclic group with $2^k$ elements. If we let $a$ be a generator of $C_{2^k}$, then the subset $$ S = \lbrace 1, a^2, a^4, \ldots, a^{2k} \rbrace $$ will not generate $C_{2^k}$, even though $\lvert S \rvert = k$. Thus, your hypothesis is false. Even if we weaken the condition to $\lvert S \rvert > \log_2(\lvert G \rvert)$, most groups will not satisfy it. For example, the group $S_n$ you mentioned has a $n!$ elements and a subgroup $S = A_n$ (the alternating group) with $n!/2$ elements, so $S$ does not generate $S_n$ even though $S$ already contains half of the elements of $S_n$. Of course, if a subset of a group $G$ contains over half of the elements of $G$, then it must generate $G$. (Do you see why?)

There do exist finite groups $G$ for which any subset with more then $\log_2(\lvert G \rvert)$ elements is generating. In fact, letting $C_p$ be the cyclic group with $p$ (prime) elements, then any subset with more than one element will generate $C_p$.

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