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"? Commented Feb 1, 2016 at 15:29
• That's what I mean, yeah. Maybe my description isn't very clear. Commented Feb 1, 2016 at 16:14
• @Tom: matrices in $GL_2(\mathbb{Z})$ can only have determinant $\pm 1$. Commented Feb 1, 2016 at 18:22
• @QiaochuYuan Sorry for the typo, I meant matrices in $\mathrm{Mat}_2(\mathbb{Z})$ of determinant $\pm n$. Commented Feb 2, 2016 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... Commented Feb 1, 2016 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)$.) Commented Feb 1, 2016 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. Commented Feb 2, 2016 at 10:32