# Is there a nice choice-free argument to count the number of sublattices?

It's a well known fact that the number of index $n$ sublattices of a rank two lattice $\Lambda$ is given by $\sigma_1(n) = \sum_{d\mid n} d$.

Here is a proof of this fact:

Proof: choosing a basis of $\Lambda' \subset \Lambda$ we are really counting the number of $2 \times 2$ matrices up to right-multiplication by $SL_2^\pm\mathbb{Z}$ (we have to allow determinant $\pm1$). So let $\begin{pmatrix}a & b \\ c & d \end{pmatrix}$ be the given matrix. Furthermore, let $\gamma = \gcd(c,d)$ and let $r, s$ be such that $rc + sd = \gamma$. Then one can easily verify that $$\begin{pmatrix} a & b \\ c & d \end{pmatrix} \underbrace{\begin{pmatrix} d/\gamma & r \\ -c/\gamma & s \end{pmatrix}}_{\in SL_2\mathbb{Z}} = \begin{pmatrix} n/\gamma & ra + sb \\ 0 & \gamma \end{pmatrix}$$ Furthermore, repeated post-multiplication with the matrix $\big(\begin{smallmatrix}1 & \pm1 \\ 0 & 1\end{smallmatrix}\big)$ will yield a matrix of the form $$\begin{pmatrix} n/\gamma & t \\ 0 & \gamma \end{pmatrix}$$ with $0 \leq t < n/\gamma$. It follows that we can write our basis for $\Lambda'$ uniquely in this form; so the number of such lattices is the number of such matrices, which is clearly $\sigma_1(d)$.

One can also start by choosing a splitting of the lattice $0 \to \Lambda_1 \to \Lambda \to \Lambda_2 \to 0$ and looking at how $\Lambda'$ intersects with this splitting. However, morally this seems to be pretty much the exact same proof, and it fundamentally still involves a choice of the splitting.

Is there a nice proof of this fact that doesn't involve some non-canonical choices?

• I'm not sure whether I agree that your first method involves a choice. You are counting the number of subgroups of $\mathbb{Z}^2$ of index $n$, and you observe that this corresponds to the number of $\mathrm{SL}_2^\pm\mathbb{Z}$-equivalence classes of matrices in $\mathrm{GL}_2\mathbb{Z}$ of determinant $\pm n$. (I don't see the choice yet.) Then you compute that this number is $\sigma_1(n)$, by coming up with a "normal form" for each of these equivalence classes. Is it this last step that you interpret as a "choice"? – Tom De Medts Feb 1 '16 at 15:29
• That's what I mean, yeah. Maybe my description isn't very clear. – Simon Rose Feb 1 '16 at 16:14
• @Tom: matrices in $GL_2(\mathbb{Z})$ can only have determinant $\pm 1$. – Qiaochu Yuan Feb 1 '16 at 18:22
• @QiaochuYuan Sorry for the typo, I meant matrices in $\mathrm{Mat}_2(\mathbb{Z})$ of determinant $\pm n$. – Tom De Medts Feb 2 '16 at 8:24

Here is at least a different argument.

Theorem: Let $G$ be a finitely generated group and let $s_n(G)$ be the number of subgroups of $G$ of index $n$. Then

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

For a proof see this post (I don't think I make any serious choices here). Now let $G = \mathbb{Z}^2$. Then

$$\frac{|\text{Hom}(\mathbb{Z}^2, S_n)|}{n!} = p(n)$$

because the number of pairs of commuting elements in any finite group $G$ is $|G|$ times the number of conjugacy classes, e.g. by Burnside's lemma (maybe this involves choices, who knows; and I guess if $\mathbb{Z}^2$ is replaced with a rank $2$ lattice $L$ then I need to choose a basis of it to get this result, oops). Hence

$$\sum_{n \ge 1} \frac{s_n(\mathbb{Z}^2)}{n} z^n = \log \left( \sum_{n \ge 0} p(n) z^n \right) = \sum_{d \ge 1} \log \frac{1}{1 - x^d}.$$

Now we have

$$\log \frac{1}{1 - x^d} = \sum_{k \ge 1} \frac{x^{dk}}{k}$$

which gives the desired result after summing over all $d$.

One thing you might mean by "not making choices" is that you want the argument to be $GL_2(\mathbb{Z})$-equivariant. But the summands in the sum you describe are not the sizes of the orbits under the action of $GL_2(\mathbb{Z})$ (I think they're the sizes of the orbits under the action of a Borel subgroup). So how do you even write down that sum without breaking $GL_2(\mathbb{Z})$ symmetry?

Basically I think making sensible choices is a great way to count things. If you wanted to generalize this argument to $\mathbb{Z}^n$ the generating function approach above gets more unwieldy but the generalization of your second approach is, I think, very elegant: you choose a complete flag in $\mathbb{Z}^n$ and then look at the relative position of the sublattice to this complete flag. (This is equivalent to looking at the orbits under the action of a Borel subgroup but phrased more geometrically.)

• Maybe you're right, maybe there isn't really a way around this. What I'm really after is a different counting problem (that is philosophically similar to this) that I can solve with a torturous choice-based argument. It seems that if I could find a nice argument for this one that doesn't really involve that, then this may be better. Anyhow, I'll look over your argument in more detail and see what if it relates... – Simon Rose Feb 1 '16 at 19:47
• @Simon: here is an even simpler example: the number of points in an $n$-dimensional vector space over $\mathbb{F}_q$ is $q^n$. How do you prove this without picking a basis? For that matter, how do you define "$n$-dimensional" without picking a basis? (In both cases you can again instead pick a complete flag, but I don't know how to pick less than this; said another way, I don't know how to make the argument equivariant with respect to any group larger than a Borel subgroup of $GL_n(\mathbb{F}_q)$.) – Qiaochu Yuan Feb 1 '16 at 21:39
• Hmmm.... You make a pretty convincing argument there. I'll have to think if I can make what I'm looking for a little more clear. – Simon Rose Feb 2 '16 at 10:32