analysis – Page 3 – Random Permutations

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.

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}$ ?
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 by Alex Eskin.

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

$\displaystyle \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}$ ,

$\displaystyle \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

$\displaystyle \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}}$ ,

$\displaystyle \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

$\displaystyle \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)$

$\displaystyle \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\rightarrow\infty}$ . Thus there are about

$\displaystyle \frac{1}{n}\zeta(2)\zeta(3)\cdots\zeta(n) m^n$

sublattices of ${\mathbf{Z}^n}$ of index at most ${m}$ , and

$\displaystyle \mu(\text{SL}_n(\mathbf{R})/\text{SL}_n(\mathbf{Z})) = \frac{1}{n}\zeta(2)\zeta(3)\cdots\zeta(n).$

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

Lemma 1 (Fekete’s lemma) If ${f:\mathbf{N}\rightarrow\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

$\displaystyle \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}$ . $\Box$

Here is an 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.

Proposition 2 ${f(n)/n}$ converges as ${n\rightarrow\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}$ . $\Box$

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):