Is there a simple formula for the number of subgroups of index 2 of $\mathbb{Z}_2^n$?

Question

Let $\lambda(n)$ denote the total number of subgroups of $\mathbb{Z}_2^n$ of index $2$ (equivalently, of order $2^{n-1}$), for $n=1,2,3,\ldots$

Is there a neat general formula for $\lambda(n)$ ?

For $n=1$, the only such subgroup of $\mathbb{Z}_2^n=\mathbb{Z}_2$ is $(0)$, so $\lambda(1)=1$. This is the only time the trivial subgroup contributes to the value of $\lambda.$

For $n=2$, the subgroups of $\mathbb{Z}_2^2$ of index $2$ are: $\mathbb{Z}_2\times(0), \hspace{2mm} (0) \times \mathbb{Z}_2, \hspace{2mm} (1,1)=\{(0,0),(1,1) \}$, so in this case $\lambda(2)=3$.

For $n=3$, the number of index 2 subgroups of $\mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2$, is, as explained here: Find all proper nontrivial subgroups of $\mathbb Z_2 \times \mathbb Z_2 \times \mathbb Z_2$ - Fraleigh p. 110 Exercise 11.10 equal to $7$, so $\lambda(3)=7$.

By this point, one could guess that $\lambda(n)=2^n-1$.

Surely, for $\mathbb{Z}_2^n$, one can write $\mathbb{Z}_2^n=\mathbb{Z}_2^{m} \times \mathbb{Z}_2^{n-m}$ in $\binom{n}{m}$ isomorphic but different ways, each giving rise to $\lambda(m)$ subgroups of index $2$ (when we replace $\mathbb{Z}_2^m$ by one of its index $2$ subgroups in this representation). Therefore, I guess one can conclude from this that $$\lambda(n) \geq \sum_{m=1}^{n-1}\binom{n}{m}\lambda(m)\lambda(n-m).$$ This looks awfully similar to the binomial formula, but I have no idea if the formula $\lambda(n)=2^n-1$ for lambda is correct or how to prove it. Perhaps there are subgroups of index 2 of $\mathbb{Z}_2^{n}$ not of this form I mentioned above as well...

Answer 1

Every subgroup of index 2 is normal, and the quotient by such a subgroup has a unique isomorphism to $\mathbb Z_2$.

So, your question is equivalent to asking for the number of surjective homomorphisms $\mathbb Z^n_2 \mapsto \mathbb Z_2$.

Writing $\mathbb Z^n_2 = \langle z_1 \rangle \oplus \cdots \oplus \langle z_n \rangle$, the set of homomorphisms $\mathbb Z^n_2 \mapsto \mathbb Z_2$ is in one-to-one correspondence with the set of functions $\{z_1,\ldots,z_n\} \mapsto \mathbb Z_2$; that is to say, each such function extends to a unique homomorphism. There is exactly one such function which extends to a nonsurjective homomorphism, namely the one that takes each of $z_1,\ldots,z_n$ to the identity element of $\mathbb{Z}_2$.

There are exactly $a^b$ functions from any $b$-element set to any $a$-element set. You could regard this as a general fact of set theory, with a proof by double induction.

So, there are exactly $2^n$ functions from the $n$-element set $\{z_1,\ldots,z_n\}$ to the $2$-element set $\mathbb Z_2$. We throw out one of them, leaving $2^n - 1$ such functions which, by the previous analysis, are in one-to-one correspondence with the index $2$ subgroups of $\mathbb Z^n_2$.

Answer 2

Think of that group as an $n$-dimensional vector sace over the field of two elements, and you're asking for the number of $n-1$-dimensional subspaces.

Such a subspace is the solution space of a single equation in $n$ unknowns (with coefficients not all zero), and there are $2^n-1$ such equations. Further, no two equations have the same solution space, since the solution space is determined by the reduced row-echelon form of the system, and a one-row matrix over the field of two elements is already in reduced row-echelon form.

So, yes, the answer is $2^n-1$.