Let $X$ be a finite set. We define $\mathcal{P}(X)$ to be the power set of $X$ and $A \mathbin{\Delta} B$ to be the symmetric difference $A \mathbin{\Delta} B = (A \cup B)\setminus(A\cap B).$ I'm aware that $G_X = (\mathcal{P}(X), \Delta)$ forms an abelian group, with identity element $\varnothing$ and each element being self-inverse. I further understand by Lagrange's theorem that as $|\mathcal{P}(X)| = 2^{|X|},$ we have that any subgroup of this group must have order which is a power of 2. My goal is to find the number of subgroups of $G_X$ with order $2^n$ in terms of $|X|$ and $n$.
I've tried a combinatorial argument, but I think I'm overcounting and can't figure out where. If $H \leq G$ has order 4, then $H = \{\varnothing, A, B, A \mathbin{\Delta} B\}$ equipped with the symmetric difference, for some sets $A,B \in \mathcal{P}(X).$ However, simply specifying each element via "choose $A,B$ in $\mathcal{P}(X)$" leads me to an answer of $\binom{2^{|X|}}{2} = (2^{|X|-1})(2^{|X|}-1).$ This severely overcounts, however: letting $X = \{0,1\}$ yields that there are 6 subgroups of $G_X$ with order $4$. Yet $G_X$ itself has order 4, so this seems horribly wrong. Am I thinking of this in the wrong way? Any ideas on an overall formula? I figure this combinatorial argument (done right) can generalize to arbitrary orders of $2^n$, but as it stands it's pretty bad.
Thanks for your time! I'm relatively new to abstract algebra, so any guidance in the right direction will be quite helpful.
Best Answer
The group $P(X)$ is the vector space of dimension $m=|X|$ over $\Bbb Z/2\Bbb Z$. You want to find the number of subspaces of dimension $n$, that is the number of linearly independent subsets of $n$ vectors divided by the order of $GL_n(\Bbb Z/2\Bbb Z)$ (we need to take into account that several sets of l.i. vectors may span the same subspace, $|GL_n(\Bbb Z/2\Bbb Z)|$ is the number of bases of the $n$-dim space over $\Bbb Z/2\Bbb Z$).
To build a linearly independent subset $e_1,...,e_n$ we can pick non-zero $e_1$ arbitrarily - $2^m-1$ options, then pick $e_2$ arbitrarily, except it should not belong to $span\{e_1\}$, $2^m-2$ options, then pick $e_3$ only making sure it is not in $span\{e_1,e_2\}$, $2^m-4$ options, and so on. Altogether the number of choices is $(2^m-1)(2^m-2)\cdot ...\cdot (2^m-2^{n-1})$. Denote it by $u_{m,n}$.
Every matrix in $GL_n(\Bbb Z/2\Bbb Z)$ has $n$ linearly independent row-vectors. So the number $|GL_n(\Bbb Z/2\Bbb Z)|$ can be computed the same way as $u_{m,n}$, it is equal to $v_n=(2^n-1)(2^n-2)\cdot...\cdot (2^n-2^{n-1})$.
So the number you are interested in is $u_{m,n}/v_n$.