You are currently browsing the monthly archive for January 2008.

We now begin our study of measure-preserving systems (X, {\mathcal X}, \mu, T), i.e. a probability space (X, {\mathcal X}, \mu) together with a probability space isomorphism T: (X, {\mathcal X}, \mu) \to (X, {\mathcal X}, \mu) (thus T: X \to X is invertible, with T and T^{-1} both being measurable, and \mu(T^n E) = \mu(E) for all E \in {\mathcal X} and all n). For various technical reasons it is convenient to restrict to the case when the \sigma-algebra {\mathcal X} is separable, i.e. countably generated. One reason for this is as follows:

Exercise 1. Let (X, {\mathcal X}, \mu) be a probability space with {\mathcal X} separable. Then the Banach spaces L^p(X, {\mathcal X}, \mu) are separable (i.e. have a countable dense subset) for every 1 \leq p < \infty; in particular, the Hilbert space L^2(X, {\mathcal X}, \mu) is separable. Show that the claim can fail for p = \infty. (We allow the L^p spaces to be either real or complex valued, unless otherwise specified.) \diamond

Remark 1. In practice, the requirement that {\mathcal X} be separable is not particularly onerous. For instance, if one is studying the recurrence properties of a function f: X \to {\Bbb R} on a non-separable measure-preserving system (X, {\mathcal X}, \mu, T), one can restrict {\mathcal X} to the separable sub-\sigma-algebra {\mathcal X}' generated by the level sets \{ x \in X: T^n f(x) > q \} for integer n and rational q, thus passing to a separable measure-preserving system (X, {\mathcal X}', \mu, T) on which f is still measurable. Thus we see that in many cases of interest, we can immediately reduce to the separable case. (In particular, for many of the theorems in this course, the hypothesis of separability can be dropped, though we won’t bother to specify for which ones this is the case.) \diamond

We are interested in the recurrence properties of sets E \in {\mathcal X} or functions f \in L^p(X, {\mathcal X}, \mu). The simplest such recurrence theorem is

Theorem 1. (Poincaré recurrence theorem) Let (X,{\mathcal X},\mu,T) be a measure-preserving system, and let E \in {\mathcal X} be a set of positive measure. Then \limsup_{n \to +\infty} \mu( E \cap T^n E ) \geq \mu(E)^2. In particular, E \cap T^n E has positive measure (and is thus non-empty) for infinitely many n.

(Compare with Theorem 1 of Lecture 3.)

Proof. For any integer N > 1, observe that \int_X \sum_{n=1}^N 1_{T^n E}\ d\mu = N \mu(E), and thus by Cauchy-Schwarz

\int_X (\sum_{n=1}^N 1_{T^n E})^2\ d\mu \geq N^2 \mu(E)^2. (1)

The left-hand side of (1) can be rearranged as

\sum_{n=1}^N \sum_{m=1}^N \mu( T^n E \cap T^m E ). (2)

On the other hand, \mu( T^n E \cap T^m E) = \mu( E \cap T^{m-n} E ). From this one easily obtains the asymptotic

(2)\leq (\limsup_{n \to \infty} \mu( E \cap T^n E ) + o(1)) N^2, (3)

where o(1) denotes an expression which goes to zero as N goes to infinity. Combining (1), (2), (3) and taking limits as N \to +\infty we obtain


as desired. \Box

Remark 2. In classical physics, the evolution of a physical system in a compact phase space is given by a (continuous-time) measure-preserving system (this is Hamilton’s equations of motion combined with Liouville’s theorem). The Poincaré recurrence theorem then has the following unintuitive consequence: every collection E of states of positive measure, no matter how small, must eventually return to overlap itself given sufficient time. For instance, if one were to burn a piece of paper in a closed system, then there exist arbitrarily small perturbations of the initial conditions such that, if one waits long enough, the piece of paper will eventually reassemble (modulo arbitrarily small error)! This seems to contradict the second law of thermodynamics, but the reason for the discrepancy is because the time required for the recurrence theorem to take effect is inversely proportional to the measure of the set E, which in physical situations is exponentially small in the number of degrees of freedom (which is already typically quite large, e.g. of the order of the Avogadro constant). This gives more than enough opportunity for Maxwell’s demon to come into play to reverse the increase of entropy. (This can be viewed as a manifestation of the curse of dimensionality.) The more sophisticated recurrence theorems we will see later have much poorer quantitative bounds still, so much so that they basically have no direct significance for any physical dynamical system with many relevant degrees of freedom. \diamond

Exercise 2. Prove the following generalisation of the Poincaré recurrence theorem: if (X, {\mathcal X}, \mu, T) is a measure-preserving system and f \in L^1(X, {\mathcal X},\mu) is non-negative, then \limsup_{n \to +\infty} \int_X f T^n f \geq (\int_X f\ d\mu)^2. \diamond

Exercise 3. Give examples to show that the quantity \mu(E)^2 in the conclusion of Theorem 1 cannot be replaced by any larger quantity in general, regardless of the actual value of \mu(E). (Hint: use a Bernoulli system example.) \diamond

Exercise 4. Using the pigeonhole principle instead of the Cauchy-Schwarz inequality (and in particular, the statement that if \mu(E_1) + \ldots + \mu(E_n) > 1, then the sets E_1,\ldots,E_n cannot all be disjoint), prove the weaker statement that for any set E of positive measure in a measure-preserving system, the set E \cap T^n E is non-empty for infinitely many n. (This exercise illustrates the general point that the Cauchy-Schwarz inequality can be viewed as a quantitative strengthening of the pigeonhole principle.) \diamond

For this lecture and the next we shall study several variants of the Poincaré recurrence theorem. We begin by looking at the mean ergodic theorem, which studies the limiting behaviour of the ergodic averages \frac{1}{N} \sum_{n=1}^N T^n f in various L^p spaces, and in particular in L^2.

Read the rest of this entry »


Read the rest of this entry »






Read the rest of this entry »


Read the rest of this entry »

I’ve just uploaded to the arXiv my joint paper with Tim Austin, “On the testability and repair of hereditary hypergraph properties“, which has been submitted to Random Structures and Algorithms. In this paper we prove some positive and negative results for the testability (and the local repairability) of various properties of directed or undirected graphs and hypergraphs, which can be either monochromatic or multicoloured.

The negative results have already been discussed in a previous posting of mine, so today I will focus on the positive results. The property testing results here are finitary results, but it turns out to be rather convenient to use a certain correspondence principle (the hypergraph version of the Furstenberg correspondence principle) to convert the question into one about exchangeable probability measures on spaces of hypergraphs (i.e. on random hypergraphs whose probability distribution is invariant under exchange of vertices). Such objects are also closely related to the”graphons” and “hypergraphons” that emerge as graph limits, as studied by Lovasz-Szegedy, Elek-Szegedy, and others. Somewhat amusingly, once one does so, it then becomes convenient to keep track of objects indexed by vertex sets and how they are exchanged via the language of category theory, and in particular using the concept of a natural transformation to describe such objects as exchangeable measures, graph colourings, and local modification rules. I will try to sketch out some of these connections, after describing the main positive results.

Read the rest of this entry »








We also have a stronger version of Theorem 1:






we obtain the claim. \Box



Read the rest of this entry »


Read the rest of this entry »


Read the rest of this entry »






Read the rest of this entry »