Results 1 to 12 of 12

Math Help - Minimal Generating Sets (Basis) for a Group

  1. #1
    Newbie
    Joined
    Apr 2010
    From
    Florida
    Posts
    21

    Minimal Generating Sets (Basis) for a Group

    Hi guys,

    Let me quickly define my terms here:

    A generating set for a group is a set of group elements that together can express every other element of the group (and no more) through products and inverses.

    A basis or minimal generating set is a generating set such that if you remove any elements from the set, it is no longer a generating set.

    I may have used nonstandard terminology, but this is how I think about it.

    Anyways my question is:
    Let G be a group

    For any n less than |G|, does there exist a basis of this size n?
    Why?

    If anyone knows the answer to the analogous question with the group infinite, thats cool beans as well.

    Thanks in advance guys.
    Last edited by Xian; July 9th 2010 at 10:54 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by Xian View Post
    Hi guys,

    Let me quickly define my terms here:

    A generating set for a group is a set of group elements that together can express every other element of the group (and no more) through products and inverses.

    A basis or minimal generating set is a generating set that if you remove any elements from the set, it is no longer a generating set.

    I may have used nonstandard terminology, but this is how I think about it.

    Anyways my question is:
    For any n less than G, does there exist a basis of this size?
    Why?

    If anyone knows the answer to the analogous question with the group infinite, thats cool beans as well.

    Thanks in advance guys.

    1) Don't use "basis" in this context. It can be pretty misleading

    2) Your question is completely incomprehensible: what is n, what is G...what did you mean??

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    From
    Florida
    Posts
    21
    I have edited the phrasing a bit now so that its crystal clear.
    I suppose I should have defined G as a group and not accidentally omit the cardinality operation.
    I thought n would obviously be a number, considering the language being used.
    I think basis is a reasonable term here, since this set is quite analogous to the linear algebra basis in the sense that it minimally generates the space (in this case a group).

    Anyways, all those trivial details aside, any thoughts?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by Xian View Post
    I have edited the phrasing a bit now so that its crystal clear.
    I suppose I should have defined G as a group and not accidentally omit the cardinality operation.
    I thought n would obviously be a number, considering the language being used.
    I think basis is a reasonable term here, since this set is quite analogous to the linear algebra basis in the sense that it minimally generates the space (in this case a group).

    Anyways, all those trivial details aside, any thoughts?
    Once again, the name "base" is reserved for other things within group theory. And once again, again, your question makes no sense: what do you mean by "for any n less than G"??
    Perhaps you mean that G is a (finite?) group of order |G|, then does there exist a minimal generating set (for this same group G?) with n, n < |G|, elements? If this is what you meant to ask, and I'm not sure at all it is, the answer is obviously no.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2010
    From
    Florida
    Posts
    21
    Quote Originally Posted by tonio View Post
    Once again, the name "base" is reserved for other things within group theory. And once again, again, your question makes no sense: what do you mean by "for any n less than G"??
    Perhaps you mean that G is a (finite?) group of order |G|, then does there exist a minimal generating set (for this same group G?) with n, n < |G|, elements? If this is what you meant to ask, and I'm not sure at all it is, the answer is obviously no.
    Tonio
    Well, if you read the mentioned edit you would have noticed that your guess as to what my "incomprehensible" query meant was indeed correct.

    Its actually not important whether G is finite or not actually because there is an ordering for all cardinals, but as it happens to turn out it was the finite case which I was curious about.

    Now, its nice that the answer is obviously no, however that does not answer the whole question. That is, it fails to answer the why.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by Xian View Post
    Well, if you read the mentioned edit you would have noticed that your guess as to what my "incomprehensible" query meant was indeed correct.

    Its actually not important whether G is finite or not actually because there is an ordering for all cardinals, but as it happens to turn out it was the finite case which I was curious about.


    Now, its nice that the answer is obviously no, however that does not answer the whole question. That is, it fails to answer the why.
    That's even easier: take any cyclic group of order bigger than 2, then it only needs one single element to be generated...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2010
    From
    Florida
    Posts
    21
    Quote Originally Posted by tonio View Post
    That's even easier: take any cyclic group of order bigger than 2, then it only needs one single element to be generated...

    Tonio
    It is obviously true that a single element is sufficient to generate it, but I said a minimal generating set is a set that generates the group, and also has the property that it is no longer a generating set if an element is removed. This leaves room for other min. gen. sets.

    If you consider a cyclic group of order k, C_k, and let x_1, x_2, x_3,... x_m be the prime factors of k we can construct another min. gen. set. If we collect a set of elements from C_k such that for each prime factor there is exactly one element of that order, then we have a generating set. Further more it is minimal because any removal will make it lose it generating property. So there are other min. gen. sets besides those of order 1. I have an instictive feeling that there will be forbidden sizes, but I am very curious as to the properties of these forbidden sizes. They must inevitably be connected to the group structure.

    Another example of a family of groups with at least two mingen sets is S_n. Two mingen sets are {(12...n), \tau} where \tau is a tansposition or {all transposition} (according to my professor). I don't know if there are any other mingen sets but would definitely like to know if the research has been done.

    Any insight?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by Xian View Post
    It is obviously true that a single element is sufficient to generate it, but I said a minimal generating set is a set that generates the group, and also has the property that it is no longer a generating set if an element is removed. This leaves room for other min. gen. sets.

    If you consider a cyclic group of order k, C_k, and let x_1, x_2, x_3,... x_m be the prime factors of k we can construct another min. gen. set. If we collect a set of elements from C_k such that for each prime factor there is exactly one element of that order, then we have a generating set. Further more it is minimal because any removal will make it lose it generating property. So there are other min. gen. sets besides those of order 1.

    Either you are very confused, or else I don't understand what you're saying: if you meant to take the set of all the elements \{x,x^{k_1},...,x^{k_m}\} , with (k,k_j)=1 , then one single element of these is enough to generate the whole cyclic group of order k, and then the above set is not minimal generating. That'd be a contradiction to the group being cyclic.

    Tonio







    I have an instictive feeling that there will be forbidden sizes, but I am very curious as to the properties of these forbidden sizes. They must inevitably be connected to the group structure.

    Another example of a family of groups with at least two mingen sets is S_n. Two mingen sets are {(12...n), \tau} where \tau is a tansposition or {all transposition} (according to my professor). I don't know if there are any other mingen sets but would definitely like to know if the research has been done.

    Any insight?
    .
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    I haven't ever though about this before, but I do think it is quite intriguing. Take a group, then what are the possible sizes of (independent) generating sets (there is a name for these things - I can't remember it though!)? Is this a question which you have been set, or one you are contemplating yourself? However, note that if we take a group G of prime order then it is cyclic and generated by any non-trivial element. Every independent generating set (or basis or whatever) has size precisely 1. On the other hand, assume G is not cyclic then there is not a minimal generating set of size 1.

    There is a series of papers by one (James?) Wiegold which discusses this (sort of) generalised to cross products, and you may find it intriguing/usefull to look up. Let G by a group and use G^n to denote G \times G \times \ldots G n-times. Then how many elements does a minimum (a basis of smallest size) generating set of G need? This is actually an interesting question for semigroups to - if \mathbb{N} is the natural numbers under addition withzero then \mathbb{N} \times \mathbb{N} needs 2 elements to generate it, while if we remove the 0s it needs...infinitely many! You may find the semigroup stuff in papers by one Nik Ruskuc, I believe.
    Last edited by Swlabr; July 20th 2010 at 04:57 AM. Reason: Typo
    Follow Math Help Forum on Facebook and Google+

  10. #10
    rkd
    rkd is offline
    Newbie
    Joined
    Mar 2011
    Posts
    2

    Tarski answered the question

    Quote Originally Posted by tonio View Post
    .
    A theorem of Tarski (The Irredundant Basis Theorem) in universal algebra
    asserts that for groups there are no gaps. For your example, Z_m,
    m= a product of k distinct primes, the largest irredundant basis has
    k elements as you noted, the smallest has 1, and all sizes in between are
    possible.

    It is a theorem of Whiston that the largest irredundant basis of S_n, the
    n-th symmetric group is n-1; the proof requires the classification of the
    finite simple groups.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by rkd View Post
    A theorem of Tarski (The Irredundant Basis Theorem) in universal algebra
    asserts that for groups there are no gaps. For your example, Z_m,
    m= a product of k distinct primes, the largest irredundant basis has
    k elements as you noted, the smallest has 1, and all sizes in between are
    possible.

    It is a theorem of Whiston that the largest irredundant basis of S_n, the
    n-th symmetric group is n-1; the proof requires the classification of the
    finite simple groups.
    What do you mean by `there are no gaps'?

    Also - and I don't know why I didn't think of this before - the Burnside Basis Theorem solves this problem for p-groups. If |G: Frat(G)| = p^r then every basis contains precisely r elements. See p140 of Robinson's`A Course in the Theory of Groups'. (Frat(G) is the Frattini subgroup of G, and is defined to be the intersection of all the maximal subgroups of G, or equivalently the set of non-generators for G (x is a non-generator if x\in S with <S>=G then <S\setminus x> = G). The theorem also tells us that Frat(G) = G^{\prime}G^p).

    Also, another interesting fact is that some groups do not contain any basis. For example, the prufer quasicyclic p-group does not contain a basis (assume it does, then there exists some generating set, B, such than removing an element no longer generated your group. Let x\in B. However, the p-th roots of x must be contained in the group, and cannot be generated by x, and so they are contained in <B\setminus x>. However, as the p-th roots of x are in <B\setminus x> then so is x and so B\setminus x generates G, a contradiction).
    Last edited by Swlabr; March 10th 2011 at 01:06 AM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    rkd
    rkd is offline
    Newbie
    Joined
    Mar 2011
    Posts
    2
    Quote Originally Posted by Swlabr View Post
    What do you mean by `there are no gaps'?

    Also - and I don't know why I didn't think of this before - the Burnside Basis Theorem solves this problem for p-groups. If |G: Frat(G)| = p^r then every basis contains precisely r elements. See p140 of Robinson's`A Course in the Theory of Groups'. (Frat(G) is the Frattini subgroup of G, and is defined to be the intersection of all the maximal subgroups of G, or equivalently the set of non-generators for G (x is a non-generator if x\in S with <S>=G then <S\setminus x> = G). The theorem also tells us that Frat(G) = G^{\prime}G^p).

    Also, another interesting fact is that some groups do not contain any basis. For example, the prufer quasicyclic p-group does not contain a basis (assume it does, then there exists some generating set, B, such than removing an element no longer generated your group. Let x\in B. However, the p-th roots of x must be contained in the group, and cannot be generated by x, and so they are contained in <B\setminus x>. However, as the p-th roots of x are in <B\setminus x> then so is x and so B\setminus x generates G, a contradiction).

    No gaps = all possible values between smallest possible size of a generating set
    and the largest possible size of an irredundant = independent generating set
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Generating a subspace (dimension, basis)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 28th 2010, 07:25 PM
  2. Model Theory - minimal sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 20th 2010, 01:10 PM
  3. free group, generating set
    Posted in the Advanced Algebra Forum
    Replies: 9
    Last Post: May 15th 2010, 03:05 PM
  4. Generating a group
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 11th 2010, 11:18 AM
  5. generating a group problem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: May 10th 2010, 08:30 AM

Search Tags


/mathhelpforum @mathhelpforum