Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Group generated by two sets

  1. Sep 24, 2010 #1
    If A and B are mere SUBSETS of G and |A| + |B| > |G|, then AB = G.

    My thought is that a "weakest case" would be where A has |G|/2 + 1 elements (if |A| + |B| > |G|, then one of A or B must have over half of G's elements) and |G|/2 of them form a subgroup of G. Then taking B= the subgroup, it is true that AB = G because that one stray element when multiplied with the subgroup gives the rest of G. So, since AB = G in this case, it must be true in general.

    Is this valid, or should I be doing something else?
    Last edited: Sep 24, 2010
  2. jcsd
  3. Sep 26, 2010 #2
    I'm wondering exactly why |G|/2 of them form a subgroup of G. By Lagrange's theorem the order of any subgroup must divide the order of the group, but suppose your group has order p where p is a prime, then it clearly can't have a subgroup of order 2 unless p is in fact equal to 2 in which case your subgroup satisfying the stated property would simply be the identity which is trivial.
  4. Sep 26, 2010 #3
    I don't mean to imply that any group will have a subgroup that has half the elements; I'm saying that *IF* G had a subgroup H with half of its elements, then choosing A = {H plus one element from G-H} and B = H, this proposition would hold. I think that such a case is the "weakest" case possible, so if it works for this case, it must be true in general. I think this because the closure property for subgroups allows for fewer elements to be introduced by elements from A being multiplied with elements of B.

    Do you think that this is true?
  5. Sep 26, 2010 #4
    When you add that stray element to H to form the set A, you actually got the whole group. Since the order of a group is always divisible by the order the subgroup, you cannot have a subgroup of G which has an order > |G|/2 unless this subgroup is the whole group.

    This means that it is impossiple to have |A| + |B| > |G|, unless one of the subgoups is the whole group G.
  6. Sep 26, 2010 #5
    A and B are not necessarily subgroups of G; they are just subsets of G. So when I multiply A and B, I get H U aH = G. (where a is the "stray" element)

    Since it works for this case, *does* it work for all cases? Is what I have a valid proof of the proposition?
    Last edited: Sep 26, 2010
  7. Sep 26, 2010 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You don't need a subset of A or B to be a group: If you just have |G|/2+1 elements as a subset of G, the group they generate needs to be G. It doesn't matter if they or some subset of them formed a subgroup to begin with or not
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook