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

Number of Subgroups of a Group

  1. Nov 1, 2011 #1
    if |G| = n . And G has 2n-1 subgroups, prove G = <e> or it is isomorphic to Z2.

    I am thinking I need to show that n is either 1 or 2. But I don't know how to use the number of subgroups. I can't find a theorem that mentions the number of subgroups or a group.

    any Hints please?
  2. jcsd
  3. Nov 1, 2011 #2
    I guess I was looking at this the wrong way. I thought this would be an application of Lagrange thm, but all I need is the fact that if G has 2n-1 subgroups, then G has at least 2n-1 elements, hence n ≥ 2n-1

    Which is only true if n =1 or n= 2.
  4. Nov 1, 2011 #3
    This got me thinking, if Z = <1>, is my proof still correct in the case of G = <e>. If the group operation was addition. But I wasn't given any operation.
    Should it be that if G = <e>, then like Z, G may be infinite so G has infinite subgrps, and it is still true that n = ∞ ≥ 2n-1.

    What do you think?
  5. Nov 1, 2011 #4


    User Avatar
    Science Advisor

    you are given that |G| = n. presumably, then, G is finite.
  6. Nov 1, 2011 #5
    Hi Deveno. It's refreshing to see you around. :)

    true, hence my early proof is correct, and G = <e> if |G|=1. right?
  7. Nov 2, 2011 #6
    Why do you think this is true? Z2 x Z2 has 5 subgroups, but only 4 elements. Thus, your earlier proof doesn't appear correct.

    As for how to prove it, I think a simple counting argument is enough. If |G| = n, let N denote the number of subgroups of G. If d is a positive integer, then there are at most [itex]\binom{n-1}{d-1}[/itex] subgroups of G of order d (since the identity must be in the subgroup, and there are d-1 elements to choose out of the remaining n-1). Now, if there is a subgroup of order d, then d divides n by Lagrange, so either d = n or 1 ≤ d ≤ n/2. Thus, the number of subgroups of G satisfies
    [tex]N \le \binom{n-1}{n-1} + \sum_{d=1}^{\lfloor n/2 \rfloor} \binom{n-1}{d-1} \le 1 + \sum_{k=0}^{\lfloor n/2 \rfloor - 1} \binom{n-1}{k} \le 1 + 2^{n-2}.[/tex]
    The last inequality follows from the fact that [itex]\sum_{k=0}^{\lfloor n/2 \rfloor - 1} \binom{n-1}{k}[/itex] consists of at most the first half of the terms in [itex]\sum_{k=0}^{n-1} \binom{n-1}{k} = 2^{n-1}[/itex], and the fact that [itex]\binom{n-1}{k} = \binom{n-1}{n-1-k}[/itex].

    Now if N = 2n-1, then N ≤ 1 + 2n-2 can only hold if n = 1 or 2.
    Last edited: Nov 2, 2011
  8. Nov 2, 2011 #7


    User Avatar
    Science Advisor
    Homework Helper

    it seems of interest to show that if you have two subgroups that are not nested, then their union is probably not a subgroup. that should do it.
  9. Nov 5, 2011 #8
    It is clear the union (unlike the intersection) is not a subroup. In this case if H1 is the nesting set, it is the union, hence it is not a subgroup contradicting our assumption.

    But isn't this a special case? Where do we use 2n-1
  10. Nov 5, 2011 #9


    User Avatar
    Science Advisor

    see, i would be inclined to use induction, like so:

    if G is a group of n elements, with n > 2, then there is some subset containing {e} of G that is not a group.

    if |G| = 3, then {e,a} for any element a ≠ e, will work.

    assume true for any group of order 2 < k < n.

    now consider |G| = n. choose some non-identity element x in G. there are two cases:

    G = <x>, or G ≠ <x>.

    if G ≠ <x>, we can apply our induction hypothesis to <x>, and we're done.

    if n is not prime, say n = kd, then choose <xd>, and we're done.

    so it suffices to consider G cyclic of prime order. since n > 2, n = p is an odd prime.

    hence {e,x} is not a group.

    how many subsets are there, of the form {e} U X, where X ⊆ G-{e}?
    Last edited: Nov 5, 2011
  11. Nov 5, 2011 #10
    Hi Deveno.
    Why is it that if G is a group of n elements, with n > 2, then there is some subset containing {e} of G that is not a group?
    I see for the case of n=3 but how to generalize it. Actually in the case |G|= 3, G has only 2 subgroups (or 3 if you include itself). Actually I never thought about that: is G a subgroup of G?
  12. Nov 5, 2011 #11
    Didn't notice that you were talking about the disjoint union. Still easy to prove, then what?
  13. Nov 5, 2011 #12


    User Avatar
    Science Advisor

    yes, G is a subgroup of G (not a proper subgroup, however).

    my previous post is a proof of that assertion (that if |G| > 2, G has a subset containing {e} which is not a subgroup), using induction on |G|. if you do not understand the proof, i can try to clarify.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook