Tuesday, 1 April 2014

Erdős-Turán statistical group theory

What is Erdős-Turán "statistical group theory"? Erdős and Turán published a series of seven papers with this title, from 1965 to 1972, in which they proved many beautiful statistical or counting results about permutations. For example, if $|\sigma|$ denotes the order of a permutation $\sigma\in S_n$, they showed that when $\sigma$ is chosen uniformly at random $\log|\sigma|$ is approximately normally distributed, with mean $(\log n)^2/2$ and variance $(\log n)^3/3$. Another typical result, though much simpler, is that if $A$ is any subset of $\{1,\dots,n\}$, then the probability that a random permutation contains no cycle with length in $A$ is at most $2\left(\sum_{a\in A} 1/a\right)^{-1}$.

Although most of their results are of the above approximate nature, they prove at least one beautiful exact counting result, and I thought I might relate it here.

Theorem: If $q$ is a prime power then the proportion of $\sigma\in S_n$ with order not divisible by $q$ is exactly
\[\left(1-\frac{1}{q}\right)\left(1-\frac{1}{2q}\right)\cdots\left(1-\frac{1}{\lfloor n/q\rfloor q}\right).\]

Proof: The number of $\sigma\in S_n$ with $m_1$ cycles of length $v_1$, $m_2$ cycles of length $v_2$, $\dots$, and $m_k$ cycles of length $v_k$, where $m_1 v_1 + \cdots m_k v_k = n$, is
\[\frac{n!}{m_1!\cdots m_k! v_1^{m_1}\cdots v_k^{m_k}}:\]
indeed, one can partition $\{1,\dots,n\}$ into $m_i$ sets of size $v_i$ for each $i$ in
\[\frac{n!}{m_1!\cdots m_k! v_1!^{m_1}\cdots v_k!^{m_k}}\]
ways, and then one can arrange each of the $m_i$ sets of size $v_i$ for each $i$ into cycles in
\[(v_1 - 1)!^{m_1} \cdots (v_k - 1)!^{m_k}\]
ways. Moreover, the order of every such $\sigma$ is $\text{lcm}(v_1,\dots,v_k)$, so the order of $\sigma$ is divisible by $q$ if and only if some $v_i$ is divisible by $q$. (This is the where we use the hypothesis that $q$ is a prime power.) Thus the proportion of $\sigma\in S_n$ with order not divisible by $q$ is
\[\sum\frac{1}{m_1!\cdots m_k! v_1^{m_1} \cdots v_k^{m_k}},\]
where the sum runs over all $k\geq 0$ and $2k$-tuples $(m_1,\dots,m_k,v_1,\dots,v_k)$ of positive integers such that $m_1 v_1 + \cdots m_k v_k = n$ and such that no $v_i$ is divisible by $q$. But this is just the coefficient of $X^n$ in
\[\prod_{v:q\nmid v} \sum_{m\geq 0} \frac{X^{mv}}{m! v^m}\\=\prod_{v:q\nmid v} \exp\left(\frac{X^v}{v}\right)\\= \exp\left(\sum_{v:q\nmid v} \frac{X^v}{v}\right)\\= \exp\left(\sum_v \frac{X^v}{v} - \sum_v \frac{X^{qv}}{qv}\right)\\= \exp\left(-\log(1-X) + \log(1-X^q)/q\right)\\ = \frac{(1-X^q)^{1/q}}{1-X}\\= (1 + X + \cdots + X^{q-1}) (1-X^q)^{-\frac{q-1}{q}}\\= (1+X+\cdots+X^{q-1}) \left(1 + \left(1-\frac{1}{q}\right) X^q + \left(1-\frac{1}{q}\right)\left(1-\frac{1}{2q}\right)X^{2q} + \cdots\right),\]
where the last equality follows from the binomial formula. This completes the proof.

Such an explicit formula should make us feel foolish for having used generating functions. Is there a direct combinatorial proof?

By the way, for those who are not already aware of this invaluable resource, almost all of Erdős's papers have been made freely available by the Rényi institute here: http://www.renyi.hu/~p_erdos/Erdos.html.

Monday, 25 November 2013

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).
\]

Tuesday, 28 May 2013

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}$.