Number of Subgroups of a Group

[Bachelier]

if |G| = n . And G has 2^n-1 subgroups, prove G = <e> or it is isomorphic to Z₂.

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?

 

[Bachelier]

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 2^n-1 subgroups, then G has at least 2^n-1 elements, hence n ≥ 2^n-1

Which is only true if n =1 or n= 2.

 

[Bachelier]

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 = ∞ ≥ 2^n-1.

What do you think?

 

[Deveno]

you are given that |G| = n. presumably, then, G is finite.

 

[Bachelier]

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?

 

[adriank]

the fact that if G has 2^n-1 subgroups, then G has at least 2^n-1 elements

Why do you think this is true? Z₂ x Z₂ 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 $\binom{n-1}{d-1}$ 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
$$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}.$$
The last inequality follows from the fact that $\sum_{k=0}^{\lfloor n/2 \rfloor - 1} \binom{n-1}{k}$ consists of at most the first half of the terms in $\sum_{k=0}^{n-1} \binom{n-1}{k} = 2^{n-1}$, and the fact that $\binom{n-1}{k} = \binom{n-1}{n-1-k}$.

Now if N = 2^n-1, then N ≤ 1 + 2^n-2 can only hold if n = 1 or 2.

 

[mathwonk]

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.

 

[Bachelier]

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 H₁ 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 2^n-1

 

[Deveno]

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 <x^d>, 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}?

 

[Bachelier]

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?

 

[Bachelier]

It is clear the union (unlike the intersection) is not a subroup. In this case if H₁ 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 2^n-1

Didn't notice that you were talking about the disjoint union. Still easy to prove, then what?

 

[Deveno]

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.