# Do arbitrary $\log_2(|G|)$ elements generate a group?

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.

• 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$). – Bib-lost Jun 2 '16 at 21:07
• No, $G$ clearly contains proper subgroups $H$ of order $|H| \gg \log_2 |G|$. – anomaly Jun 2 '16 at 21:22
• @Bib-lost , have a look at it math.stackexchange.com/questions/226931/… – Mike SQ Jun 2 '16 at 21:37
• @MikeSQ: Right, and my post shows that the converse is false. – anomaly Jun 2 '16 at 21:42
• If $|S|>|G|/2$, then it is guaranteed that $S$ generates $G$. This bound is sharp for symmetric groups. – Batominovski Jun 3 '16 at 10:50

## 1 Answer

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