Number of Subgroups of a Group

  • Thread starter Bachelier
  • Start date
  • #1
376
0
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
2020 Award
11,123
1,323
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
2K
  • Last Post
Replies
1
Views
3K
Replies
2
Views
2K
Replies
2
Views
871
Replies
3
Views
2K
Replies
2
Views
2K
Replies
1
Views
798
Replies
14
Views
3K
Replies
19
Views
2K
Top