# Number of sublattices of $\Bbb Z^2$

I would like to count the number of sublattices of index $n$ of $\Bbb Z^2$. For $n=2$, I found three lattices : $\langle(2,0), (0,1)\rangle, \langle(0,2), (1,0)\rangle$ and $\langle(1,1), (-1,1)\rangle$. How can I find the lattices of index $n$ and how many are there?

Can we generalise for other dimensions?

• A friend told me that the answer is, in dimension two, $\sum_{d\mid n } d$ but I don't see why... – Friedrich Jul 22 '17 at 13:53
• Perhaps start at math.stackexchange.com/questions/193863/…. – lhf Jul 22 '17 at 15:31

Consider a sublattice $$\langle(a_x,a_y),(b_x,b_y)\rangle$$ of index $$n$$. A node $$(r_x,r_y)$$ belongs to that sublattice when $$A\begin{pmatrix}k_a\\k_b\end{pmatrix}=\begin{pmatrix}r_x\\r_y\end{pmatrix}$$ where $$A=\begin{pmatrix}a_x&b_x\\a_y&b_y\end{pmatrix}$$ and $$k_{x,y}$$ are some integers. Since $$|\det A| = n$$ (we can even assume $$\det A=n$$ without loss of generality), we have: $$\begin{pmatrix}k_a\\k_b\end{pmatrix}=\displaystyle\frac{1}{n}\begin{pmatrix}b_y&-b_x\\-a_y&a_x\end{pmatrix}\begin{pmatrix}r_x\\r_y\end{pmatrix}$$, so the solution of that linear equation system is surely integral if $$r_{x,y}$$ are both divisible by $$n$$.
In particular, the node $$(n,0)$$ is contained in every sublattice of index $$n$$. There may be other nodes between $$(0,0)$$ and $$(n,0)$$ if the distance $$d$$ between them is a divisor of $$n$$. Thus, for every $$d|n$$ there is a way to select one basis vector of the sublattice as $$(d,0)$$. Another basis vector can be chosen in the form $$(a,n/d)$$ so the index is indeed $$d\times n/d-0\times a=n$$, and two choices of $$a$$ lead to the same sublattice iff their difference is a multiple of $$d$$. Hence the formula $$\sum_{d|n}d$$ from your comment.
For the general $$D$$-dimensional case, it works by induction: for every divisor $$d$$ of $$n$$, we can select the first basis vector to be $$(d,0,\ldots,0)$$; and to select the remaining vectors, we look at every index $$n/d$$ sublattice in $$(D-1)$$-dimensional space and take it into account multiple times, namely the number of possible shifts of that $$(D-1)$$-dimensional sublattice that do not transform it to itself again, which equals to its index, $$n/d$$; it's the same number for all sublattices, so instead of summing over $$(D-1)$$-dimensional sublattices, we count them and multiply their number by $$n/d$$. After replacement $$d\leftrightarrow n/d$$ we get the recurrent formula from OEIS A128119/A160870: $$T_{n,D} = \sum_{d|n}d\times T_{d,D-1}$$ with $$T_{1,D}=T_{n,1}=1$$.
• Could you please explain why $(n,0)$ must belong to any sublattice of index $n$? I must admit that I fail to see it. (Also, I am sorry to come here more than a year after you posted this, I just found this answer via the search engine). – Giuseppe Negro Aug 20 at 14:50
• For completeness, here there is a good explanation of the formula $\lvert \det A\rvert = \text{index of the sublattice}$. – Giuseppe Negro Aug 23 at 9:10