# Proof involving Lagrange Theorem and subgroups help

If $G$ is a group of order $n$, and $G$ has $2^{n-1}$ subgroups, prove that $G=< e>$ or $G$ is isomorphic to $\Bbb Z_2$.

I now understand this question a bit more. I received the suggestion to use Lagrange's theorem but I am not too sure how. I was testing out different $n$ values so say for $n=1$ which would be the case for $G= < e >$, then $2^{1-1}$ is $1$, so there is one subgroup. For the second case $n$ would be two so $2^{2-1}$ is two which makes sense because order of $\Bbb Z_2$ is two. I think something with contradiction could work here but I am unsure of how to approach the proof.

• Why have you deleted your earlier post? I already answered your question there in a comment. Commented Feb 15, 2017 at 1:58
• @DerekHolt Because I wanted to include that I now know more information. I talked a bit through it with my professor and I see how plugging in different n values relates to the subgroup amount. Essentially, it has something to do with arguing this amount of subgroups is too large is what I think he was aiming to say.
– Sam
Commented Feb 15, 2017 at 2:00
• @DerekHolt yes, but I needed further explanation for the problem. I am only just learning this so I am unsure how to proceed with saying that these subgroups have order m. I think then you need to use the theorem to state m divides n?
– Sam
Commented Feb 15, 2017 at 2:43
• I still don't understand why you deleted the earlier question. Commented Feb 15, 2017 at 3:24
• I wanted to just restart the question because I have a new understanding of the question and what I had down before made no sense.
– Sam
Commented Feb 15, 2017 at 3:29

Let $G$ be a group of order $n$.

Let $S$ be the set of subsets of $G$ which are subgroups of $G$, and let $m = |S|$.

It's easy to verify that if $n = 1$ or $n = 2$, then $m = 2^{n-1}$.

Claim: If $m = 2^{n-1}$ then $n = 1$ or $n = 2$.

Suppose $n > 2$ and $m = 2^{n-1}$. Our goal is to derive a contradiction.

Let $e$ be the identity element of $G$. Define $W,E,F$ by

\begin{align*} W &= \text{ the set of nonempty subsets of }G\\[6pt] E &= \{X \in W \mid e \in X\}\\[6pt] F &= W\setminus E \end{align*}

Then

\begin{align*} |W| &= 2^n-1\\[6pt] |E| &= 2^{n-1}\\[6pt] |F| &= 2^{n-1}-1 \end{align*}

Then $H \in S \implies e \in H \implies H \in E$, hence $S \subseteq E$.

Since $|S| = |E|$, $S \subseteq E \implies S = E$.

Let $g \in G$, $g \ne e$, and let $H = G\setminus \{g\}$. Then $|H| = n - 1$.

Then

\begin{align*} e \in H &\implies H \in E\\[6pt] &\implies H \in S\\[6pt] &\implies |H| \text{ divides } |G|\;\;\text{[by Lagrange's Theorem]}\\[6pt] &\implies (n-1)|n \end{align*}

which is impossible since $n-1$ is relatively prime to $n$, and $n > 2$.

Thus, we have a contradiction, and hence, the claim is proved.

• then subsets are the same as subgroups for where you define S?
– Sam
Commented Feb 15, 2017 at 2:03
• @Sam: The set $S$ is the set of those subsets of $G$ which are subgroups of $G$. Commented Feb 15, 2017 at 2:06
• How do you know there are 2^n-1 subsets? is this because each subgroup has the identity?
– Sam
Commented Feb 15, 2017 at 2:08
• @Sam: Given any set with n elements, there are $2^n$ subsets, hence there are $2^n - 1$ nonempty subsets. That explains why the cardinality of $W$ is $2^n - 1$. Commented Feb 15, 2017 at 2:09
• Oh is this sort of like the power series? where we have 2^n subsets and since one is the empty set we have (2^n)-1 non empty subsets
– Sam
Commented Feb 15, 2017 at 2:15

Here is another approach: there is an injection $f$ between the set of subgroups of $G$ and $P(G-e)$ the set of subsets of $G-\{e\}$ such that $f(H)=H-\{e\}$. Since the cardinal of $P(G-e)$ is $2{n-1}$, the hypothesis implies that $f$ is bijective. Suppose $x\in G$, $\{x,e\}$ is a subgroup implies implies $x^{-1}=x$ or $x=e$. If every element verifies $x=e$,done. Suppose you have $x,y,x^2=y^2=e, x,y\neq e$, $\{x,y,e\}$ is a subgroup so $x=y^{-1}$.

If you want to use Lagrange theorem, suppose that $n\neq 1$, you have a non empty subset $H$ of $G$ of order $n-1$. The lines above implies $H$ is a subgroup. Lagrange impliess that $n-1$ divides $n$, this true only if $n=2$.

• I see, but I am only just learning Lagrange's Theorem so I am supposed to use this. I appreciate seeing another way to approach the problem nonetheless.
– Sam
Commented Feb 15, 2017 at 2:17
• This is simpler than Lagrange theorem. I use only basic set theory. Commented Feb 15, 2017 at 2:18
• Yes, but I have to use Lagrange Theorem because that is what we are currently learning.
– Sam
Commented Feb 15, 2017 at 2:37