Random Permutations

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

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\rightarrow \mathbf{Z}/d\mathbf{Z}}$ . Possibly surprisingly, this is the whole story.

Theorem 2 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

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

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

$\displaystyle X_S = E \cup T^{-1}E \cup \cdots \cup T^{-(d-1)}E.$

This finishes the proof. $\Box$

Note as a corollary that “only the primes matter” insofar 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 3 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}}$ .

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