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

Math Help - 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 G be a finite group. Then there exists a subset S \subseteq G so that G = <S> 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    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 G be a finite group. Then there exists a subset S \subseteq G so that G = <S> 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
    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 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.
    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 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|}.
    Last edited by Swlabr; December 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 |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?

    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 |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?

    Please help me with this.
    Assume the result holds for k. Let <S> = 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=<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 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 k. Let <S> = 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=<a_1, a_2, \ldots, a_k>?
    Is k = |S| or 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 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|.

    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 G=<a_1, \ldots, a_{k+1}> and H=<a_1, \ldots, a_k>. 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).
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    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 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
    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 |H| = k, the group G can not have more than 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 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?
    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: November 2nd 2010, 08:00 PM
  2. Quotient Groups - Infinite Groups, finite orders
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: August 11th 2010, 07:07 AM
  3. more about finite groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 27th 2009, 10:50 PM
  4. result about finite groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 10th 2009, 06:28 PM
  5. residually finite groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 18th 2009, 06:05 PM

Search Tags


/mathhelpforum @mathhelpforum