Math Help - Finite groups and generating sets

1. Finite groups and generating sets

Hello all,

While studying some facts about generating sets for groups, I came along the the following fact, but a proof was never given, as it should be somehow trivial.

Here the fact:
Let $G$ be a finite group. Then there exists a subset $S \subseteq G$ so that $G = $ and $2^{|S|} \leq |G|.$

When proving this, I would start like this: By Cayley's theorem $G$ is isomorphic to some permutation group $A$. Therefore it is enough to show the claim for $A\subseteq S_n.$

Now I know that $S_n$ is generated by n-1 transpositions, but I dont know how to apply this on subgroups of it. Anyone can help me with the proof?

2. Originally Posted by EinStone
Hello all,

While studying some facts about generating sets for groups, I came along the the following fact, but a proof was never given, as it should be somehow trivial.

Here the fact:
Let $G$ be a finite group. Then there exists a subset $S \subseteq G$ so that $G = $ and $2^{|S|} \leq |G|.$

When proving this, I would start like this: By Cayley's theorem $G$ is isomorphic to some permutation group $A$. Therefore it is enough to show the claim for $A\subseteq S_n.$

Now I know that $S_n$ is generated by n-1 transpositions, but I dont know how to apply this on subgroups of it. Anyone can help me with the proof?

Take a minimal genewrating set S of G ==> all the possible products of DIFFERENT elements in S are in G, and these are in 1-1 correspondence with the subsets of S...

Tonio

3. Hey Tonio, thanks for your answer. Still I don't fully understand what you mean. A minimal generating set means, that when I take all possible products of elements of it, I get G. But how do they have a 1-1 correspondence with all possible subsets of S?

4. Originally Posted by tonio
Take a minimal genewrating set S of G ==> all the possible products of DIFFERENT elements in S are in G, and these are in 1-1 correspondence with the subsets of S...

Tonio
Personally, I would induct on $n$. The case holds for a $0$-generated group, as this is the trivial group with one element. I will leave the rest to you, EinStone.

5. Originally Posted by EinStone
Hey Tonio, thanks for your answer. Still I don't fully understand what you mean. A minimal generating set means, that when I take all possible products of elements of it, I get G. But how do they have a 1-1 correspondence with all possible subsets of S?
Think about it the other way - take a subset of $S$, call it $S_1$. This subset corresponds to an element of the group, $a_{i_1}a_{i_2} \ldots a_{i_m}$ with $a_{i_r} \neq a_{i_s}$. Take a different subset of $S$, call it $S_2$, and this correspond to an element $a_{j_1}a_{j_2} \ldots a_{j_n}$. Suppose these elements are the same, then $a_{i_1}a_{i_2} \ldots a_{i_m} = a_{j_1}a_{j_2} \ldots a_{j_n}$. Re-arranging, we get that $a_{i_1} = a_{j_1}a_{j_2} \ldots a_{j_n}a_{i_m}^{-1} \ldots a_{i_2}^{-1}$. By minimality of our generating set we have that $a_{i_1} \in S_2$. Similarly, we also have that $a_{i_r}\in S_2$ for all $a_{i_r} \in S_1$ and $a_{j_r}\in S_1$ for all $a_{j_r} \in S_2$. Thus $S_1 = S_2$, a contradiction.

Thus, every subset of $S$, our minimal generating set, corresponds to a unique element of $G$. There are $2^{|S|}$ subsets, and so $|G| \geq 2^{|S|}$.

6. If I understand it correctly this is your induction base:
Let $|G| = n$.

For n = 1, we have $G = \{e\}$. So $S = \emptyset$ generates G, $2^{|S|} = 2^{0} = 1 <= n$.

But I have absolutely no clue how to get to n+1 from n. I also don't understand how you can add 1 element to a group and get a new group of size n+1?

7. Originally Posted by EinStone
If I understand it correctly this is your induction base:
Let $|G| = n$.

For n = 1, we have $G = \{e\}$. So $S = \emptyset$ generates G, $2^{|S|} = 2^{0} = 1 <= n$.

But I have absolutely no clue how to get to n+1 from n. I also don't understand how you can add 1 element to a group and get a new group of size n+1?

Assume the result holds for $k$. Let $ = G$ where $S=\{a_1, a_2, \ldots, a_{k+1}\}$ is a minimal generating set of $G$. Can you think of anything you can do with the subgroup $H=$?

8. Now I just see you answered again, but your final conclusion is . and But I want to prove that $2^{|S|}<=|G|.$, or am I getting something wrong?

9. Originally Posted by Swlabr
Assume the result holds for $k$. Let $ = G$ where $S=\{a_1, a_2, \ldots, a_{k+1}\}$ is a minimal generating set of $G$. Can you think of anything you can do with the subgroup $H=$?
Is $k = |S|$ or $k = |G|$?

10. Originally Posted by EinStone
Is $k = |S|$ or $k = |G|$?
ooo-bad explanation by me! $n$ was meant to be the size of a minimal generating set for your group. So $k=|S|$.

In reply to your other post, that was a typo. I've edited it now.

11. So we use induction on the size of S, but how does this work? I mean assuming that we have proven it for arbitrary k, how does this prove my original statement?

12. Originally Posted by EinStone
So we use induction on the size of S, but how does this work? I mean assuming that we have proven it for arbitrary k, how does this prove my original statement?
We have $G=$ and $H=$. Apply the inductive assumption to $H$. Then note that you can just pin $a_{k+1}$ onto the end of every element of $H$ to get a new element of $G$. These elements are all unique (as if $ba_{k+1} = ca_{k+1} \Rightarrow b=c$). Thus we have $|H|$ new elements in $G$ to add to the $|H|$ elements we already have. How many elements does this give us?

(Note that none of the "new" elements are in $H$, as otherwise we can cancel to get that $a_{k+1} \in H$, a contradiction).

13. Originally Posted by EinStone
Hey Tonio, thanks for your answer. Still I don't fully understand what you mean. A minimal generating set means, that when I take all possible products of elements of it, I get G. But how do they have a 1-1 correspondence with all possible subsets of S?

Take for instance $S=\{s_1,s_2,s_3\}\subset G$ , for some group $G$. Then every elements of $G$ is the product of a finite string of elements of $S$ AND their inverses.

Among these elements we have $\{1\mbox{ (the empty product of elements of S) }\,,\,s_2\,\ldots\,,\,s_1s_2\,,s_1s_2s_3\,\ldots\}$
The above products are all in G, and they're in 1-1 correspondence with the subsets of $S:\,\,\{\emptyset\,,\,\{s_2\}\,\ldots\,\{s_1,s_2\} \,,\,\{s_1,s_2,s_3\}\,,\ldots\}$.

Note that as elements of $G$, ALL the above strings of elements of $S$ are different, otherwise the generating set wouldn't be minimal.

Tonio

14. Sorry, Im still not getting the inductive assumption. Do you say that for every minimal generating subset H of a group G with $|H| = k$, the group G can not have more than $2^{k}$ elements?

15. Originally Posted by tonio
Take for instance $S=\{s_1,s_2,s_3\}\subset G$ , for some group $G$. Then every elements of $G$ is the product of a finite string of elements of $S$ AND their inverses.

Among these elements we have $\{1\mbox{ (the empty product of elements of S) }\,,\,s_2\,\ldots\,,\,s_1s_2\,,s_1s_2s_3\,\ldots\}$
The above products are all in G, and they're in 1-1 correspondence with the subsets of $S:\,\,\{\emptyset\,,\,\{s_2\}\,\ldots\,\{s_1,s_2\} \,,\,\{s_1,s_2,s_3\}\,,\ldots\}$.

Note that as elements of $G$, ALL the above strings of elements of $S$ are different, otherwise the generating set wouldn't be minimal.

Tonio
Ok that makes sense. Im just wondering which is the corresponding subset of S to the product $s_2s_1$?

Page 1 of 2 12 Last