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

$\limsup_{n \to \infty} \mu( E \cap T^n E ) \geq \mu(E)^2$ (4)

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

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.

It’s now been almost a year since I moved my “What’s new?” page from my home page to this blog. Since then, I’ve been quite happy with the directions this blog has been headed in (most of which I had not anticipated when I started), and also with the level of feedback, some of which has been extremely informative to me (and, I hope, to other readers as well).

Anyway, after discussing things with some of my friends and colleagues, I have decided to convert some of the posts here from 2007 into a book format, in order to place some of the mathematical content here in a more formal and traditional context (with accurate citations and references, etc.). After some thought, I decided not to transcribe all of my posts from last year (there are 93 of them!), but instead to restrict attention to those articles which (a) have significant mathematical content, (b) are not announcements of material that will be published elsewhere, and (c) are not primarily based on a talk given by someone else. As it turns out, this still leaves about 33 articles from 2007, leading to a decent-sized book of a couple hundred pages in length. For various reasons (including legal reasons), I have decided not to incorporate the comments to each post directly into the book format, although corrections, mention of relevant references, etc. will be added with acknowledgments in the endnotes to each article.

I’ve converted a couple articles into a book format, and also created a table of contents, to see what it would look like. (The format comes from the American Mathematical Society, with whom I am planning to publish the book.) It looks like it will be relatively straightforward to convert the rest (at least compared to writing books from scratch, which I know from experience to be quite time-consuming!). I’ll of course post updates here on this blog when the book is closer to completion.

At present, the structure and content of the book is still rather flexible; like all things related to this blog, it is an experiment. As such, I am open to suggestions on these matters. (For instance, I do not have any particularly imaginative title for the book, other than “What’s new – 2007″. )

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 $(X, {\mathcal F}, T)$. In this lecture, we generalise these results to multiple recurrence. More precisely, we shall show

Theorem 1. (Multiple recurrence in open covers) Let $(X,{\mathcal F},T)$ be a topological dynamical system, and let $(U_\alpha)_{\alpha \in A}$ be an open cover of X. Then there exists $U_\alpha$ such that for every $k \geq 1$, we have $U_\alpha \cap T^{-r} U_\alpha \cap \ldots \cap T^{-(k-1)r} U_\alpha \neq \emptyset$ for infinitely many r.

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

Theorem 2. (van der Waerden’s theorem) Suppose the integers ${\Bbb Z}$ 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. $\diamond$

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. $\diamond$

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 $\{1,\ldots,N\}$ 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.) $\diamond$

We also have a stronger version of Theorem 1:

Theorem 3. (Multiple Birkhoff recurrence theorem) Let $(X,{\mathcal F},T)$ be a topological dynamical system. Then for any $k \geq 1$ there exists a point $x \in X$ and a sequence $r_j \to \infty$ of integers such that $T^{i r_j} x \to x$ as $j \to \infty$ for all $0 \leq i \leq k-1$.

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 $\alpha$ be a real number. Then there exists a sequence $r_j \to \infty$ of integers such that $\hbox{dist}(r_j^2 \alpha,{\Bbb Z}) \to 0$ as $j \to \infty$.

Proof. Consider the skew shift system $X = ({\Bbb R}/{\Bbb Z})^2$ with $T(x,y) := (x+\alpha,y+x)$. By Theorem 3, there exists $(x,y) \in X$ and a sequence $n_j \to \infty$ such that $T^{r_j}(x,y)$ and $T^{2r_j}(x,y)$ both convege to $(x,y)$. If we then use the easily verified identity

$(x,y) - 2T^{r_j}(x,y) + T^{2r_j}(x,y) = (0, r_j^2 \alpha)$ (1)

we obtain the claim. $\Box$

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

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 $(X, {\mathcal F}, T)$ – 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 $x \mapsto x+1$ on the compactified integers $\{-\infty\} \cup {\Bbb Z} \cup \{+\infty\}$. 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 $(X,{\mathcal F},T)$ be a topological dynamical system, and let $(U_\alpha)_{\alpha \in A}$ be an open cover of X. Then there exists an open set $U_\alpha$ in this cover such that $U_\alpha \cap T^n U_\alpha \neq \emptyset$ for infinitely many n.

Proof. By compactness of X, we can refine the open cover to a finite subcover. Now consider an orbit $T^{\Bbb Z} x = \{ T^n x: n \in {\Bbb Z} \}$ of some arbitrarily chosen point $x \in X$. By the infinite pigeonhole principle, one of the sets $U_\alpha$ must contain an infinite number of the points $T^n x$ counting multiplicity; in other words, the recurrence set $S := \{ n: T^n x \in U_\alpha \}$ is infinite. Letting $n_0$ be an arbitrary element of S, we thus conclude that $U_\alpha \cap T^{n_0-n} U_\alpha$ contains $T^{n_0} x$ for every $n \in S$, and the claim follows. $\Box$

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

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 $\beta {\Bbb Z}$ of the integers (i.e. ultrafilters).