How many lattices are there?

The basic question is the one in the title: How many lattices are there? I intend to answer two quite different interpretations of this question.

1. How many sublattices of the standard lattice $\mathbf{Z}^n$ are there? Here sublattice just means subgroup. There are infinitely many of course. Less trivially, how many sublattices of $\mathbf{Z}^n$ are there of index at most $m$?
2. How many lattices are there in $\mathbf{R}^n$ of covolume $1$? Here a lattice means a discrete subgroup of rank $n$, and covolume refers to the volume of a fundamental domain. Again, the answer is infinitely many. Less trivially, what (in an appropriate sense) is the volume of the set of covolume-$1$ lattices?

Question number 2 obviously needs some explanation. Covolume, as can easily be proved, is equal to the determinant of any complete set of spanning vectors, from which it follows that covolume-$1$ lattices are in some way parameterised by $\text{SL}_n(\mathbf{R})$. Actually, we are counting each lattice several times here, because each lattice has a stabliser isomorphic to $\text{SL}_n(\mathbf{Z})$. Thus, the space of covolume-$1$ lattices can be identified with the quotient space $\text{SL}_n(\mathbf{R})/\text{SL}_n(\mathbf{Z})$.

This subgroup $\text{SL}_n(\mathbf{Z})$ itself is also considered a lattice, in the group $\text{SL}_n(\mathbf{R})$. Generally, let $G$ be a locally compact group, and recall that $G$ possesses a unique (up to scale) left-invariant regular Borel measure, its Haar measure $\mu$. Suppose moreover that $G$ is unimodular, i.e., that $\mu$ is also right-invariant. If $H\leq G$ is a unimodular subgroup, and we fix a Haar measure on $H$ as well, then $\mu$ descends to a unique $G$-invariant regular Borel measure on the homogeneous space $G/H$ which we also denote by $\mu$. If $\mu(G/H)<\infty$, we say that $H$ has finite covolume. For example, if $H$ is a discrete subgroup then we can fix the counting measure as a bi-invariant Haar measure. If in this case $H$ has finite covolume then we say that $H$ is a lattice.

It is a classical theorem due to Minkowski, which we prove in a moment, that $\text{SL}_n(\mathbf{Z})$ is a lattice in the unimodular group $\text{SL}_n(\mathbf{R})$. We thus consider the volume of $\text{SL}_n(\mathbf{R})/\text{SL}_n(\mathbf{Z})$, for a natural choice of Haar measure, to be the answer to question 2 above, at least in some sense. The actual computation of this volume, I understand, is originally due to Siegel, but I learnt it from this MO answer.

Let $\lambda$ be the usual Lebesgue measure on $\mathbf{R}^{n^2}$, normalized (as usual) so that $\lambda(\mathbf{R}^{n^2}/\mathbf{Z}^{n^2}) = 1$, and note that $\lambda$ is invariant under the left multiplication action of $\text{SL}_n(\mathbf{R})$. Given closed $E\subset\text{SL}_n(\mathbf{R})$, we denote $\text{cone}(E)$ the union of all the line segments which start at $0\in\mathbf{R}^{n^2}$ and end in $E$, and we define
$$\mu(E) = \lambda(\text{cone}(E)).$$
This function $\mu$ extends to a nontrivial Borel measure in the usual way, and inherits regularity and both left- and right-invariance from $\lambda$. Thus $\text{SL}_n(\mathbf{R})$ is unimodular, and $\mu$ is a Haar measure. We consider this $\mu$ to be the natural choice of Haar measure.

Now let $E\subset\text{SL}_n(\mathbf{R})$ be a measurable fundamental domain for $\text{SL}_n(\mathbf{Z})$. Then, for $R>0$,
\[
\mu(\text{SL}_n(\mathbf{R})/\text{SL}_n(\mathbf{Z})) = \mu(E) = \lambda(\text{cone}(E)) = \frac{\lambda(R\,\text{cone}(E))}{R^{n^2}}.
\]
But $\lambda(R\,\text{cone}(E))$ is asymptotic, as $m\rightarrow\infty$, to $|R\,\text{cone}(E)\cap M_n(\mathbf{Z})|$, which is just the number of sublattices of $\mathbf{Z}^n$ of index at most $R^n$. Thus we have reduced question 2 to question 1.

To finish the proof of Minkowski's theorem, it suffices to show that there are $O(R^{n^2})$ sublattices of $\mathbf{Z}^n$ of index at most $R^n$, and this much can be accomplished by a simple inductive argument. If $\Gamma\leq\mathbf{Z}^n$ has index at most $R^n$, then by Minkowski's convex bodies theorem there exists some nonzero $\gamma\in\Gamma$ of $\|\gamma\|_\infty\leq R$. Without loss of generality, $\Gamma\cap\mathbf{R}\gamma = \mathbf{Z}\gamma$. But then $\Gamma^\prime = \Gamma/(\mathbf{Z}\gamma)$ is a lattice in $\mathbf{Z}^n/(\mathbf{Z}\gamma)\cong\mathbf{Z}^{n-1}$ of index at most $R^n$. Since there are no more than $(2R+1)^n$ choices for $\gamma$ and, by induction, at most $O(R^{n(n-1)})$ choices for $\Gamma^\prime$, there are at most $O(R^{n^2})$ choices for $\Gamma$.

But with a more careful analysis, this calculation can actually be carried out explicitly. An elementary(-ish) calculation shows that the number $a_m(\mathbf{Z}^n)$ of subgroups of $\mathbf{Z}^n$ of index exactly $m$ is the coefficient of $m^{-s}$ in the Dirichlet series of
\[
\zeta_{\mathbf{Z}^n}(s) = \zeta(s)\zeta(s-1)\cdots\zeta(s-n+1),
\]
where $\zeta(s) = \sum_{n\geq1} n^{-s}$ is the Riemann zeta function. Thus, by Perron's formula, if $x\notin\mathbf{Z}$,
\[
\frac{1}{x^n}\sum_{1\leq m< x} a_m(\mathbf{Z}^n) = \frac{1}{i2\pi} \int_{n+1/2-i\infty}^{n+1/2+i\infty} \zeta_{\mathbf{Z}^n}(z) \frac{x^{z-n}}{z}\,dz.
\]
But, by Cauchy's residue theorem, this integral differs from
\[
\text{Res}_{z=n}\left(\frac{\zeta_{\mathbf{Z}^n}(z) x^{z-n}}{z}\right) = \frac{1}{n}\zeta(2)\zeta(3)\cdots\zeta(n)
\]
by
\[
\frac{1}{i2\pi} \int_{n-1/2-i\infty}^{n-1/2+i\infty} \zeta_{\mathbf{Z}^n}(z) \frac{x^{z-n}}{z}\,dz,
\]
which tends to $0$ as $x\to\infty$. Thus there are about
\[
\frac{1}{n}\zeta(2)\zeta(3)\cdots\zeta(n) m^n
\]
sublattices of $\mathbf{Z}^n$ of index at most $m$, and
\[
\mu(\text{SL}_n(\mathbf{R})/\text{SL}_n(\mathbf{Z})) = \frac{1}{n}\zeta(2)\zeta(3)\cdots\zeta(n).
\]

Total ergodicity

A measure-preserving transformation $T$ of a (finite) measure space $(X,\Sigma,\mu)$ is called ergodic if whenever $A\subset X$ satisfies $T^{-1}A=A$ we have $\mu(A)=0$ or $\mu(A^c)=0$. To aid intuition, it is useful to keep in mind the ergodic theorem, which roughly states that ergodicity equals equidistribution.

Following a discussion today, I'm concerned here with the ergodicity of $T^n$ for $n\in\mathbf{N}$. This is an entertaining topic, and I thank Rudi Mrazovic for bringing it to my attention. Here's an amusing example: While $T$ being ergodic does not generally imply that $T^2$ is ergodic, $T^2$ being ergodic does imply that $T^4$ is ergodic.

Let's start with a quite simple observation.

Lemma: If $n\in\mathbf{N}$ and $T^n$ is ergodic then $T$ is ergodic.

Proof: Suppose $T^{-1}A=A$. Then $T^{-n}A=A$, so $\mu(A)=0$ or $\mu(A^c)=0$. $\square$

What is the picture of $T$ being ergodic and $T^n$ not being ergodic? Certainly one picture to imagine is a partition $X = E\cup T^{-1}E\cup\cdots\cup T^{-(d-1)}E$ with $1<d\mid n$ and $T^{-d}E=E$, or in other words a factor $X\to \mathbf{Z}/d\mathbf{Z}$. Possibly surprisingly, this is the whole story.

Theorem: If $T$ is ergodic and $T^n$ is not ergodic then for some divisor $d>1$ of $n$ there exists a partition of $X$ as $E\cup T^{-1}E\cup\cdots\cup T^{-(d-1)}E \cup N$ where $T^{-d}E=E$ and $\mu(N)=0$.

Proof: Since $T^n$ is not ergodic there exists a set $A$ with $T^{-n}A=A$ and $\mu(A)>0$ and $\mu(A^c)>0$. For any subset $S\subset \mathbf{Z}/n\mathbf{Z}$ let $X_S$ consist of those $x\in X$ such that
$$\{j\in\mathbf{Z}/n\mathbf{Z} : T^j x \in A\} = t + S$$
for some $t\in\mathbf{Z}/n\mathbf{Z}$. (Note that because $x\in A$ iff $T^n x\in A$, the sentence "$T^j x \in A$" makes sense for $j\in \mathbf{Z}/n\mathbf{Z}$.) Note that $T^{-1}X_S = X_S$, so $\mu(X_S)=0$ or $\mu(X_S^c)=0$. Since $X = \bigcup_S X_S$, we must have $\mu(X_S^c)=0$ for some $S$.

Let $d$ be the smallest positive period of $S$. Note that $d=1$ iff $S=\emptyset$, contradicting $\mu(A)>0$, or $S=\mathbf{Z}/n\mathbf{Z}$, contradicting $\mu(A^c)>0$, so $d>1$. Let
$$E = \bigcap_{j\in S} T^{-j} A.$$
(Again note that $T^{-j}A$ makes sense for $j\in\mathbf{Z}/n\mathbf{Z}$.) Then $\mu(T^{-i}E \cap T^{-j} E) = 0$ unless $-i+S = -j+S$, i.e., iff $i-j$ is divisible by $d$, in which case $T^{-i}E=T^{-j}E$. Thus we have the desired partition
$$X_S = E \cup T^{-1}E \cup \cdots \cup T^{-(d-1)}E.\square$$

Note as a corollary that "only the primes matter" insofar as far as which $n\in N$ make $T^n$ ergodic: if $n>1$ and $T^n$ is not ergodic then for some prime $p|n$, $T^p$ is not ergodic. Combining this with the initial lemma, which shows that if $T^n$ is ergodic then $T^p$ is ergodic for every $p|n$, we have thus proved one half of the following theorem.

Theorem: Given a set $S\subset\mathbf{N}$, there exists a measure-preserving system $(X,\Sigma,\mu,T)$ such that $S = \{n\in\mathbf{N} : T^n \text{ is ergodic}\}$ if and only if $S$ is empty or the set of $n\in\mathbf{N}$ not divisible by any $p\in\mathcal{P}$, for some set of primes $\mathcal{P}$.

It remains only to construct a measure-preserving system for a given set $\mathcal{P}$ of primes. For $\mathcal{P}$ finite this can be achieved even with finite spaces. In general it suffices to look at $\prod_{p\in\mathcal{P}} \mathbf{Z}/p\mathbf{Z}$.

Fekete's lemma and sum-free sets

Just a quick post to help popularise a useful lemma which seems to be well known to researchers but not to undergraduates. It would make for a good Analysis I exercise. Let $\mathbf{N}$ exclude $0$ for the purpose of this post.

Fekete's lemma: If $f:\mathbf{N}\to\mathbf{R}$ satisfies $f(m+n)\leq f(m)+f(n)$ for all $m,n\in\mathbf{N}$ then $f(n)/n\longrightarrow\inf_n f(n)/n$.

 Proof: The inequality $\liminf f(n)/n \geq \inf_d f(d)/d$ is immediate from the definition of $\liminf$, so it suffices to prove $\limsup f(n)\leq f(d)/d$ for each $d\in\mathbf{N}$. Fix such a $d$ and set $M=\max\{0,f(1),f(2),\ldots,f(d-1)\}$. Set $f(0)=0$. Now for a given $n$ choose $k$ so that $0 \leq n-kd < d$. Then
\[\frac{f(n)}{n} \leq \frac{f(n-kd)}{n} + \frac{f(kd)}{n} \leq \frac{M}{n} + \frac{kf(d)}{kd} \longrightarrow \frac{f(d)}{d},\]
so $\limsup f(n)/n \leq f(d)/d$.

Example: For $n\in\mathbf{N}$ let $f(n)$ denote the largest $k\in\mathbf{N}$ such that every set of $n$ nonzero real numbers contains a subset of size $k$ containing no solutions to $x+y=z$. We call such a subset sum-free.

Claim: $f(n)/n$ converges as $n\to\infty$.

Proof: Let $A$ be a set of size $m$ containing no sum-free subset of size larger than $f(m)$, and $B$ a set of size $n$ containing no sum-free subset of size larger than $f(n)$. Then for large enough $M\in\mathbf{N}$, the set $A\cup MB$ is a set of size $m+n$ containing no sum-free subset of size larger than $f(m)+f(n)$, so $f(m+n)\leq f(m)+f(n)$. Thus by Fekete's lemma $f(n)/n$ converges to $\inf f(n)/n$.

The value of $\sigma = \lim f(n)/n$ not easy to compute, but certainly $0\leq\sigma\leq\frac{1}{2}$. A famously simple argument of Erdos shows $\sigma\geq\frac{1}{3}$: Fix a set $A$, and for simplicity assume $A\subset\mathbf{N}$. For $\theta\in[0,1]$ consider those $n\in A$ such that the fractional part of $\theta n$ lies between $\frac{1}{3}$ and $\frac{2}{3}$. This set $A_\theta$ is sum-free, and if $\theta$ is chosen uniformly at random then $A_\theta$ has size $|A|/3$ on average.

The example $A=\{1,2,3,4,5,6,8,9,10,18\}$, due to Malouf, shows $\sigma\leq\frac{2}{5}$. The current record is due to Lewko, who showed by example $\sigma\leq\frac{11}{28}$. Since these examples are somewhat ad hoc, while Erdos's argument is beautiful, one is naturally led to the following conjecture (indeed many people have made this conjecture):

Conjecture: $\sigma=\frac{1}{3}$.

Ben Green, Freddie Manners, and I have just proved this conjecture: see http://arxiv.org/abs/1301.4579.