Number of Subgroups of a Group

  • Thread starter Bachelier
  • Start date
  • #1
376
0

Main Question or Discussion Point

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?
 

Answers and Replies

  • #2
376
0
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.
 
  • #3
376
0
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?
 
  • #4
Deveno
Science Advisor
906
6
you are given that |G| = n. presumably, then, G is finite.
 
  • #5
376
0
you are given that |G| = n. presumably, then, G is finite.
Hi Deveno. It's refreshing to see you around. :)

true, hence my early proof is correct, and G = <e> if |G|=1. right?
 
  • #6
534
1
the fact that if G has 2n-1 subgroups, then G has at least 2n-1 elements
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:
  • #7
mathwonk
Science Advisor
Homework Helper
10,822
988
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.
 
  • #8
376
0
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.
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
 
  • #9
Deveno
Science Advisor
906
6
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:
  • #10
376
0
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.
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?
 
  • #11
376
0
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
Didn't notice that you were talking about the disjoint union. Still easy to prove, then what?
 
  • #12
Deveno
Science Advisor
906
6
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.
 

Related Threads on Number of Subgroups of a Group

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
3K
Replies
2
Views
2K
Replies
2
Views
2K
Replies
2
Views
748
Replies
3
Views
2K
Replies
2
Views
2K
Replies
1
Views
706
Replies
14
Views
3K
Replies
19
Views
2K
Top