The number of submodules of $\mathbb{Z}_q^n$

Question

Observe $\mathbb{Z}_q^n = \mathbb{Z}_q \times \cdots \times\mathbb{Z}_q$ as a module over $\mathbb{Z}_q\equiv\mathbb{Z}/q\mathbb{Z}$, for general $q$. I am interested in the following questions:

How many submodules of size $q^k$, $k\leq n$, does it have? How many of them are free? Can something be said about the ratio of these two numbers when $n\to\infty$ and $k=\lambda n$, $\lambda\in(0,1)$?

Can someone give me a reference where such or similar problems have been studied? Or else provide pointers how to tackle them?

Answer 1

First, if $q=rs$ with $(r,s)=1$ then $\mathbb{Z}_q^n=\mathbb{Z}_r^n\times\mathbb{Z}_s^n$, and every submodule of $\mathbb{Z}_q^n$ splits uniquely as a direct sum of a submodule of $\mathbb{Z}_r^n$ and a submodule of $\mathbb{Z}_s^n$. Using this, we reduce easily to the case where $q$ is a prime power, say $q=p^m$.

Now let $F$ denote the set of free submodules of rank $k$ in $\mathbb{Z}_q^n$, and let $F_0$ be the corresponding set for $\mathbb{Z}_p^n$. By a standard argument which you say you have seen, we have $|F_0|=\pi(n)/(\pi(k)\pi(n-k))$, where $\pi(k)=(p-1)(p^2-1)\dotsb(p^k-1)$. The reduction map $\rho\colon F\to F_0$ is easily seen to be surjective, so you just need to understand $|\rho^{-1}\{A_0\}|$ for $A_0\in F_0$. We can choose $A\in\rho^{-1}\{A_0\}$, and then choose a complement $B$ such that $\mathbb{Z}_q^n=A\times B$. Now $\rho^{-1}\{A_0\}$ is the set of submodules $C\leq A\times B$ that are free of rank $r$ and agree with $A$ mod $p$. For any such $C$, we have projections $A\xleftarrow{f}C\xrightarrow{g}B$, and we see that $f(C)+pA=A$ and $g(C)\leq pB$. As $f(C)+pA=A$ we see that $f$ is surjective, but $|C|=|A|=q^k$ so $f$ is an isomorphism. It follows that $C=\{(a,h(a)):a\in A\}$, where $h=gf^{-1}\in\text{Hom}(A,pB)$. This construction gives a bijection from $\rho^{-1}\{A_0\}$ to $\text{Hom}(A,pB)$, so $|\rho^{-1}\{A_0\}|=p^{(m-1)k(n-k)}$. This is independent of $A_0$, so $$ |F| = p^{(m-1)k(n-k)} \pi(n)/(\pi(k)\pi(n-k)). $$

One can say interesting things about non-free subgroups as well, but I do not have time to write that now.

Answer 2

Aren't you just asking for the number of subgroups of $\mathbb{Z}_q^n$ of size $q^k$? There isn't going to be a simple answer. The classification and enumeration of subgroups of finite abelian groups goes back to Garrett Birkhoff. See http://plms.oxfordjournals.org/content/s2-38/1/385.citation. Some more recent work is mentioned at http://www.northeastern.edu/iloseu/bhmn/Ringel04.html. One can give an answer in terms of symmetric functions. If $G$ is a finite abelian group of order $p_1^{a_1}p_2^{a_2}\cdots$ (where the $p_i$'s are distinct primes) then the face lattice $L(G)$ is the product of the lattices for each Sylow subgroup. This reduces the problem to abelian $p$-groups. Let $P_\lambda(x;t)$ be a Hall-Littlewood symmetric function. Let $$ P_\mu(x;t)P_\nu(x;t) =\sum_\lambda f^\lambda_{\mu\nu}(t) P_\lambda(x;t). $$ Let $n(\lambda) =\sum (i-1)\lambda_i$. Then $p^{n(\lambda)}f^\lambda_{\mu\nu}(1/p)$ is the number of subgroups $H$ of type $\mu$ of an abelian $p$-group of type $\lambda$ such that $G/H$ has type $\nu$ (or something close to this). In particular, one can deduce that if $h_i$ is a complete symmetric function and $$ h_mh_n = \sum_\lambda c_{m,n}^\lambda(t)P_\lambda(x;t), $$ then $p^{n(\lambda)}c_{m,n}^\lambda(1/p)$ is the number of subgroups of order $p^m$ in an abelian $p$-group of type $\lambda\vdash m+n$. All this is explained in Chapter II of Macdonald, Symmetric functions and Hall Polynomials.

Answer 3

Here's a somewhat different approach that doesn't directly yield a formula for what you want, but can be used to glean information. Fix $n$ and let $$ \nu(m) = \text{\# of subgroups of $(\mathbb Q/\mathbb Z)^n$ of order $m$.} $$ Then the Dirichlet series associated to the sequence $\nu(m)$ is given by the beautiful formula $$ \sum_{m=1}^\infty \frac{\nu(m)}{m^s} = \zeta(s)\zeta(s-1)\cdots\zeta(s-n+1). $$ Here $\zeta(s)$ is the Riemann zeta function. From this formula, properties of $\zeta(s)$, and a standard Tauberian theorem, one deduces, for example, that for all $k\ge-(n-1)$, we have $$ \sum_{m\le X} m^k\nu(m) \sim \frac{X^{n+k}}{n+k} \quad\text{as $X\to\infty$.} $$ I believe that this is all standard. It follows from the formulas for Dirichelet series with Hecke operator coefficients [1, Theorem 3.21] and some algebra. (I thank Sol Friedberg and Dan Bump for giving me this reference.)

[1] G. Shimura, Introduction to the Arithmetic Theory of Automorphic Forms, Princeton University Press, 1971.