Page 1 of 2 12 LastLast
Results 1 to 15 of 21

Thread: Finite groups and generating sets

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    169

    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 $\displaystyle G$ be a finite group. Then there exists a subset $\displaystyle S \subseteq G$ so that $\displaystyle G = <S> $ and $\displaystyle 2^{|S|} \leq |G|.$

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

    Now I know that $\displaystyle 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by EinStone View Post
    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 $\displaystyle G$ be a finite group. Then there exists a subset $\displaystyle S \subseteq G$ so that $\displaystyle G = <S> $ and $\displaystyle 2^{|S|} \leq |G|.$

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

    Now I know that $\displaystyle 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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2009
    Posts
    169
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by tonio View Post
    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 $\displaystyle n$. The case holds for a $\displaystyle 0$-generated group, as this is the trivial group with one element. I will leave the rest to you, EinStone.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by EinStone View Post
    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 $\displaystyle S$, call it $\displaystyle S_1$. This subset corresponds to an element of the group, $\displaystyle a_{i_1}a_{i_2} \ldots a_{i_m}$ with $\displaystyle a_{i_r} \neq a_{i_s}$. Take a different subset of $\displaystyle S$, call it $\displaystyle S_2$, and this correspond to an element $\displaystyle a_{j_1}a_{j_2} \ldots a_{j_n}$. Suppose these elements are the same, then $\displaystyle 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 $\displaystyle 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 $\displaystyle a_{i_1} \in S_2$. Similarly, we also have that $\displaystyle a_{i_r}\in S_2$ for all $\displaystyle a_{i_r} \in S_1$ and $\displaystyle a_{j_r}\in S_1$ for all $\displaystyle a_{j_r} \in S_2$. Thus $\displaystyle S_1 = S_2$, a contradiction.

    Thus, every subset of $\displaystyle S$, our minimal generating set, corresponds to a unique element of $\displaystyle G$. There are $\displaystyle 2^{|S|}$ subsets, and so $\displaystyle |G| \geq 2^{|S|}$.
    Last edited by Swlabr; Dec 1st 2009 at 01:20 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2009
    Posts
    169
    If I understand it correctly this is your induction base:
    Let $\displaystyle |G| = n$.

    For n = 1, we have $\displaystyle G = \{e\}$. So $\displaystyle S = \emptyset$ generates G, $\displaystyle 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?

    Please help me with this.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by EinStone View Post
    If I understand it correctly this is your induction base:
    Let $\displaystyle |G| = n$.

    For n = 1, we have $\displaystyle G = \{e\}$. So $\displaystyle S = \emptyset$ generates G, $\displaystyle 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?

    Please help me with this.
    Assume the result holds for $\displaystyle k$. Let $\displaystyle <S> = G$ where $\displaystyle S=\{a_1, a_2, \ldots, a_{k+1}\}$ is a minimal generating set of $\displaystyle G$. Can you think of anything you can do with the subgroup $\displaystyle H=<a_1, a_2, \ldots, a_k>$?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Nov 2009
    Posts
    169
    Now I just see you answered again, but your final conclusion is . and But I want to prove that $\displaystyle 2^{|S|}<=|G|.$, or am I getting something wrong?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Nov 2009
    Posts
    169
    Quote Originally Posted by Swlabr View Post
    Assume the result holds for $\displaystyle k$. Let $\displaystyle <S> = G$ where $\displaystyle S=\{a_1, a_2, \ldots, a_{k+1}\}$ is a minimal generating set of $\displaystyle G$. Can you think of anything you can do with the subgroup $\displaystyle H=<a_1, a_2, \ldots, a_k>$?
    Is $\displaystyle k = |S|$ or $\displaystyle k = |G|$?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by EinStone View Post
    Is $\displaystyle k = |S|$ or $\displaystyle k = |G|$?
    ooo-bad explanation by me! $\displaystyle n$ was meant to be the size of a minimal generating set for your group. So $\displaystyle k=|S|$.

    Sorry about that.

    In reply to your other post, that was a typo. I've edited it now.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Nov 2009
    Posts
    169
    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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by EinStone View Post
    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 $\displaystyle G=<a_1, \ldots, a_{k+1}>$ and $\displaystyle H=<a_1, \ldots, a_k>$. Apply the inductive assumption to $\displaystyle H$. Then note that you can just pin $\displaystyle a_{k+1}$ onto the end of every element of $\displaystyle H$ to get a new element of $\displaystyle G$. These elements are all unique (as if $\displaystyle ba_{k+1} = ca_{k+1} \Rightarrow b=c$). Thus we have $\displaystyle |H|$ new elements in $\displaystyle G$ to add to the $\displaystyle |H|$ elements we already have. How many elements does this give us?

    (Note that none of the "new" elements are in $\displaystyle H$, as otherwise we can cancel to get that $\displaystyle a_{k+1} \in H$, a contradiction).
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by EinStone View Post
    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 $\displaystyle S=\{s_1,s_2,s_3\}\subset G$ , for some group $\displaystyle G$. Then every elements of $\displaystyle G$ is the product of a finite string of elements of $\displaystyle S$ AND their inverses.

    Among these elements we have $\displaystyle \{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 $\displaystyle S:\,\,\{\emptyset\,,\,\{s_2\}\,\ldots\,\{s_1,s_2\} \,,\,\{s_1,s_2,s_3\}\,,\ldots\}$.

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

    Tonio
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Nov 2009
    Posts
    169
    Sorry, Im still not getting the inductive assumption. Do you say that for every minimal generating subset H of a group G with $\displaystyle |H| = k$, the group G can not have more than $\displaystyle 2^{k}$ elements?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Nov 2009
    Posts
    169
    Quote Originally Posted by tonio View Post
    Take for instance $\displaystyle S=\{s_1,s_2,s_3\}\subset G$ , for some group $\displaystyle G$. Then every elements of $\displaystyle G$ is the product of a finite string of elements of $\displaystyle S$ AND their inverses.

    Among these elements we have $\displaystyle \{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 $\displaystyle S:\,\,\{\emptyset\,,\,\{s_2\}\,\ldots\,\{s_1,s_2\} \,,\,\{s_1,s_2,s_3\}\,,\ldots\}$.

    Note that as elements of $\displaystyle G$, ALL the above strings of elements of $\displaystyle 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 $\displaystyle s_2s_1$?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. finite abelian groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Nov 2nd 2010, 08:00 PM
  2. Quotient Groups - Infinite Groups, finite orders
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Aug 11th 2010, 07:07 AM
  3. more about finite groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Apr 27th 2009, 10:50 PM
  4. result about finite groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Apr 10th 2009, 06:28 PM
  5. residually finite groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Feb 18th 2009, 06:05 PM

Search Tags


/mathhelpforum @mathhelpforum