You are currently browsing the monthly archive for January 2008.

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

**Exercise 1.** Let be a probability space with separable. Then the Banach spaces are separable (i.e. have a countable dense subset) for every ; in particular, the Hilbert space is separable. Show that the claim can fail for . (We allow the spaces to be either real or complex valued, unless otherwise specified.)

**Remark 1. **In practice, the requirement that be separable is not particularly onerous. For instance, if one is studying the recurrence properties of a function on a non-separable measure-preserving system , one can restrict to the separable sub--algebra generated by the level sets for integer n and rational q, thus passing to a separable measure-preserving system 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.)

We are interested in the recurrence properties of sets or functions . The simplest such recurrence theorem is

Theorem 1.(Poincaré recurrence theorem) Let be a measure-preserving system, and let be a set of positive measure. Then . In particular, has positive measure (and is thus non-empty) for infinitely many n.

(Compare with Theorem 1 of Lecture 3.)

**Proof.** For any integer , observe that , and thus by Cauchy-Schwarz

(1)

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

(2)

On the other hand, . From this one easily obtains the asymptotic

(3)

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

as desired.

**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.

**Exercise 2.** Prove the following generalisation of the Poincaré recurrence theorem: if is a measure-preserving system and is non-negative, then .

**Exercise 3.** Give examples to show that the quantity in the conclusion of Theorem 1 cannot be replaced by any smaller quantity in general, regardless of the actual value of . (Hint: use a Bernoulli system example.)

**Exercise 4.** Using the pigeonhole principle instead of the Cauchy-Schwarz inequality (and in particular, the statement that if , then the sets cannot all be disjoint), prove the weaker statement that for any set E of positive measure in a measure-preserving system, the set 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.)

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 in various spaces, and in particular in .

In our final lecture on topological dynamics, we discuss a remarkable theorem of Furstenberg that classifies a major type of topological dynamical system – *distal* systems – in terms of highly structured (from an algebraic point of view) systems, namely towers of isometric extensions. This theorem is also a model for an important analogous result in ergodic theory, the *Furstenberg-Zimmer structure theorem*, which we will turn to in a few lectures. We will not be able to prove Furstenberg’s structure theorem for distal systems here in full, but we hope to illustrate some of the key points and ideas.

In this lecture, we move away from recurrence, and instead focus on the *structure* of topological dynamical systems. One remarkable feature of this subject is that starting from fairly “soft” notions of structure, such as topological structure, one can extract much more “hard” or “rigid” notions of structure, such as *geometric* or *algebraic* structure. The key concept needed to capture this structure is that of an *isometric system*, or more generally an *isometric extension*, which we shall discuss in this lecture. As an application of this theory we characterise the distribution of polynomial sequences in torii (a baby case of a variant of Ratner’s theorem due to (Leon) Green, which we will cover later in this course).

In this lecture, we use topological dynamics methods to prove some other Ramsey-type theorems, and more specifically the polynomial van der Waerden theorem, the hypergraph Ramsey theorem, Hindman’s theorem, and the Hales-Jewett theorem. In proving these statements, I have decided to focus on the ultrafilter-based proofs, rather than the combinatorial or topological proofs, though of course these styles of proof are also available for each of the above theorems.

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.

In the previous lecture, we established single recurrence properties for both open sets and for sequences inside a topological dynamical system . In this lecture, we generalise these results to multiple recurrence. More precisely, we shall show

Theorem 1. (Multiple recurrence in open covers) Let be a topological dynamical system, and let be an open cover of X. Then there exists such that for every , we have for infinitely many r.

Note that this theorem includes Theorem 1 from the previous lecture as the special case . This theorem is also equivalent to the following well-known combinatorial result:

Theorem 2. (van der Waerden’s theorem) Suppose the integers are finitely coloured. Then one of the colour classes contains arbitrarily long arithmetic progressions.

**Exercise 1**. Show that Theorem 1 and Theorem 2 are equivalent.

**Exercise 2**. Show that Theorem 2 fails if “arbitrarily long” is replaced by “infinitely long”. Deduce that a similar strengthening of Theorem 1 also fails.

**Exercise 3**. Use Theorem 2 to deduce a finitary version: given any positive integers m and k, there exists an integer N such that whenever is coloured into m colour classes, one of the colour classes contains an arithmetic progression of length k. (Hint: use a “compactness and contradiction” argument, as in my article on hard and soft analysis.)

We also have a stronger version of Theorem 1:

Theorem 3. (Multiple Birkhoff recurrence theorem) Let be a topological dynamical system. Then for any there exists a point and a sequence of integers such that as for all .

These results already have some application to equidistribution of explicit sequences. Here is a simple example (which is also a consequence of Weyl’s equidistribution theorem):

Corollary 1. Let be a real number. Then there exists a sequence of integers such that as .

**Proof**. Consider the skew shift system with . By Theorem 3, there exists and a sequence such that and both convege to . If we then use the easily verified identity

(1)

we obtain the claim.

**Exercise 4.** Use Theorem 1 or Theorem 2 in place of Theorem 3 to give an alternate derivation of Corollary 1.

As in the previous lecture, we will give both a traditional topological proof and an ultrafilter-based proof of Theorem 1 and Theorem 3; the reader is invited to see how the various proofs are ultimately equivalent to each other.

This weekend I was (once again) in San Diego, this time for the Southern California Analysis and PDE (SCAPDE) meeting. I gave a talk on “The asymptotic behaviour of large data solutions to NLS”, which is based on two of my previous papers on what solutions to focusing nonlinear Schrödinger equations behave like as time goes to infinity. (Note that this is a specialist conference, and this talk will be a bit more technical than some of the general-audience talks that I have blogged about previously.)

Avi Wigderson‘s final talk in his Distinguished Lecture Series on “Computational complexity” was entitled “Arithmetic computation“; the complexity theory of *arithmetic* circuits rather than boolean circuits.

We now begin the study of *recurrence* in topological dynamical systems – how often a non-empty open set U in X returns to intersect itself, or how often a point x in X returns to be close to itself. Not every set or point needs to return to itself; consider for instance what happens to the shift on the compactified integers . Nevertheless, we can always show that at least one set (from any open cover) returns to itself:

Theorem 1. (Simple recurrence in open covers) Let be a topological dynamical system, and let be an open cover of X. Then there exists an open set in this cover such that for infinitely many n.

**Proof**. By compactness of X, we can refine the open cover to a finite subcover. Now consider an orbit of some arbitrarily chosen point . By the infinite pigeonhole principle, one of the sets must contain an infinite number of the points counting multiplicity; in other words, the recurrence set is infinite. Letting be an arbitrary element of S, we thus conclude that contains for every , and the claim follows.

**Exercise 1**. Conversely, use Theorem 1 to deduce the infinite pigeonhole principle (i.e. that whenever is coloured into finitely many colours, one of the colour classes is infinite). *Hint*: look at the orbit closure of c inside , where A is the set of colours and is the colouring function.)

Now we turn from recurrence of sets to recurrence of individual points, which is a somewhat more difficult, and highlights the role of minimal dynamical systems (as introduced in the previous lecture) in the theory. We will approach the subject from two (largely equivalent) approaches, the first one being the more traditional “epsilon and delta” approach, and the second using the Stone-Čech compactification of the integers (i.e. ultrafilters).

## Recent Comments