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?

  • $\begingroup$ A friend told me that the answer is, in dimension two, $\sum_{d\mid n } d $ but I don't see why... $\endgroup$ – Friedrich Jul 22 '17 at 13:53
  • 1
    $\begingroup$ Perhaps start at math.stackexchange.com/questions/193863/…. $\endgroup$ – 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$.

  • $\begingroup$ 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). $\endgroup$ – Giuseppe Negro Aug 20 at 14:50
  • 1
    $\begingroup$ @GiuseppeNegro A good question with a nontrivial answer! I have included an additional paragraph into the beginning of my answer to address it. $\endgroup$ – colt_browning Aug 21 at 23:26
  • $\begingroup$ For completeness, here there is a good explanation of the formula $\lvert \det A\rvert = \text{index of the sublattice}$. $\endgroup$ – Giuseppe Negro Aug 23 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.