Number of finite index subgroups in a free abelian group

Question

Let $n,m\in\mathbb{N}$. Is there a formula for the number of subgroups of index $n$ in $\mathbb{Z}^m$? Perhaps in terms of the divisors of $n$?

Answer 1

Yes. This is given by OEIS sequence A160870. The number of subgroups of index $n$ in $\mathbf{Z}^m$ is there denoted $T(n,m)$. There is a recursive formula in terms of the divisors of $n$ given at this page. The initial conditions are $$ T(n,1) = 1 \quad \textrm{ for all } n\in \mathbb{N}$$ and recursively for $m > 1$, we have either $$ \quad T(n,m) = \sum_{d \mid n} \left(\frac{n}{d}\right)^{m-1} \cdot T(d, m-1) $$ or equivalently, $$ \quad T(n,m) = \sum_{d \mid n} d \cdot T(d, m-1) $$ Note that we can solve this recurrence to get the "explicit" formula $$ T(n,m) = \sum_{\substack{(d_0,d_1,\ldots,d_m)}} d_1 \cdots d_{m-1}$$ where the sum is over all sequences of integers $(d_0,d_1,\ldots,d_m)$ with $d_0=1$, $d_m=n$, and $d_i \mid d_{i+1}$ for all $i=0,\ldots,m-1$.

For example, there are $T(4,5) = 651$ subgroups of index $4$ in $\mathbf{Z}^5$.

Answer 2

There is a nice Dirichlet series generating function for this number. Denoting it by $j_m(n)$, we have $$ \sum_{n\geq 1}j_m(n)n^{-s} = \zeta(s)\zeta(s-1)\cdots \zeta(s-m+1), $$ where $\zeta$ denotes the Riemann zeta function. For the history of this result, see L. Solomon, in Relations between Combinatorics and Other Parts of Mathematics, Proc. Symp. Pure Math. 34, American Mathematical Society 1979, pp. 309-330. See also Exercise 5.13(d) (and its solution) of Enumerative Combinatorics, vol. 2.

Answer 3

This is an elaboration on Stanley's reference to Exercise 5.13 in EC2. In these two blog posts you can find proofs using groupoid cardinality of the following results. For a finitely generated group $G$ let $s_n(G)$ denote the number of subgroups of index $n$ and let $c_n(G)$ denote the number of conjugacy classes of subgroups of index $n$.

Exercise 5.13a: $$\sum_{n \ge 0} \frac{|\text{Hom}(G, S_n)|}{n!} z^n = \exp \left( \sum_{n \ge 1} s_n(G) \frac{z^n}{n} \right).$$

Exercise 5.13c: $$\sum_{n \ge 0} \frac{|\text{Hom}(\mathbb{Z} \times G, S_n)|}{n!} z^n = \prod_{n \ge 1} \frac{1}{(1 - z^n)^{c_n(G)}}.$$

Taking logarithms on both sides of 5.13c and applying 5.13a gives

$$s_n(\mathbb{Z} \times G) = \sum_{d \mid n} d c_d(G)$$

which, when applied to $G = \mathbb{Z}^k$, gives the second recurrence in Carl-Fredrik's answer (which is essentially the content of Exercise 5.13d).

(Not to toot my own horn excessively and with all respect to Stanley, I believe my proof of Exercise 5.13c is better motivated than the argument that appears in EC2.)

Answer 4

The number $\sigma_d(N)$ of subgroups of index $N$ in $\mathbb Z^d$ is also given by the formula (see Gruber, B. (1997), Alternative formulae for the number of sublattices. Acta Cryst. A53, 807--808 and Y.M. Zou, Y.M. (2006), Gaussian binomials and the number of sublattices, Acta Cryst. A62, 409--410) \begin{align}\label{formexactsigma} \sigma_d(N)&=\prod_{p\vert N}\left(\begin{array}{cc}e_p+d-1\\d-1 \end{array}\right)_p \end{align} where $\prod_{p\vert N}p^{e_p}=N$ is the factorization of $N$ into prime-powers and where $$\left(\begin{array}{cc}e_p+d-1\\d-1 \end{array}\right)_p=\prod_{j=1}^{d-1}\frac{p^{e_p+j}-1}{p^j-1}$$ is the evaluation of the $q$-binomial $$\left[\begin{array}{cc}e_p+d-1\\d-1 \end{array}\right]_q=\frac{[e_p+d-1]_q!}{[e_p]_q!\ [d-1]_q!}$$ (with $[k]_q!=\prod_{j=1}^k\frac{q^j-1}{q-1}$) at the prime-divisor $p$ of $N$.