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.

— Topological proof of van der Waerden —

We begin by giving a topological proof of Theorem 1, due to Furstenberg and Weiss, which is secretly a translation of van der Waerden’s original “colour focusing” combinatorial proof of Theorem 2 into the dynamical setting.

To prove Theorem 1, it suffices to show the following slightly weaker statement:

Theorem 4. Let (X,{\mathcal F},T) be a topological dynamical system, and let (U_\alpha)_{\alpha \in A} be an open cover of X. Then for every k \geq 1 there exists an open set U_\alpha which contains an arithmetic progression x, T^r x, T^{2r} x, \ldots, T^{(k-1)r}x for some x\in X and r > 0.

To see how Theorem 4 implies Theorem 1, first observe from compactness that we can take the open cover to be a finite cover. Then by the infinite pigeonhole principle, it suffices to establish Theorem 1 for each k \geq 1 separately. For each such k, Theorem 4 gives a single arithmetic progression x, T^r x, \ldots, T^{(k-1)r} x inside one of the U_\alpha. By replacing the system (X, T) with the product system (X \times {\Bbb Z}/N{\Bbb Z}, (x,m) \mapsto (Tx,m+1)) for some large N and replacing the open cover (U_\alpha)_{\alpha \in A} of X with the open cover (U_\alpha \times \{m\})_{\alpha \in A, m \in {\Bbb Z}/N{\Bbb Z}} of X \times {\Bbb Z}/N{\Bbb Z}, one can make the spacing r in the arithmetic progression larger than any specified integer N. Thus by another application of the infinite pigeonhole principle, one of the U_\alpha contains arithmetic progressions with arbitrarily large step r, and the claim follows.

Now we need to prove Theorem 4. By Lemma 1 of Lecture 2 to establish this theorem for minimal dynamical systems. We will need to note that for minimal systems, Theorem 4 automatically implies the following stronger-looking statement:

Theorem 5. Let (X,{\mathcal F},T) be a minimal topological dynamical system, let U be a non-empty open set in X, and let k \geq 1. Then U contains an arithmetic progression x, T^r x, \ldots T^{(k-1)r} x for some x \in X and r \geq 1.

Indeed, the deduction of Theorem 5 from Theorem 4 is immediate from the following useful fact (cf. Lemma 1 from Lecture 3):

Lemma 1. Let (X,{\mathcal F},T) be a minimal topological dynamical system, and let U be a non-empty open set in X. Then X can be covered by a finite number of translates T^n U of U.

Proof. The set X \backslash \bigcup_{n \in {\Bbb Z}} T^n U is a proper closed invariant subset of X, which must therefore be empty since X is minimal. The claim then follows from the compactness of X. \Box.

(Of course, the claim is highly false for non-minimal systems; consider for instance the case when T is the identity. More generally, if X is non-minimal, consider an open set U which is the complement of a proper subsystem of X.)

Now we need to prove Theorem 4. We do this by induction on k. The case k=1 is trivial, so suppose k \geq 2 and the claim has already been shown for k-1. By the above discussion, we see that Theorem 5 is also true for k-1.

Now fix a minimal system (X,{\mathcal F},T) and an open cover (U_\alpha)_{\alpha \in A}, which we can take to be finite. We need to show that one of the U_\alpha contains an arithmetic progression x, T^r x, \ldots, T^{(k-1)r} x of length k.

To do this, we first need an auxiliary construction.

Lemma 2. (Construction of colour focusing sequence) Let the notation and assumptions be as above. Then for any J \geq 0 there exists a sequence x_0,\ldots,x_J of points in X, a sequence U_{\alpha_0}, \ldots, U_{\alpha_J} of sets in the open cover (not necessarily distinct), and a sequence r_1,\ldots,r_J of positive integers such that T^{i(r_{a+1} + \ldots + r_b)} x_b \in U_{\alpha_a} for all 0 \leq a \leq b \leq J and 1 \leq i \leq k-1.

Proof. We induct on J. The case J=0 is trivial. Now suppose inductively that J \geq 1, and that we have already constructed x_0,\ldots,x_{J-1}, U_{\alpha_0},\ldots,U_{\alpha_{J-1}}, and r_1,\ldots,r_{J-1} with the required properties. Now let V be a suitably small neighbourhood of x_{J-1} (depending on all the above data) to be chosen later. By Theorem 5 for k-1, V contains an arithmetic progression y, T^{r_J} y, \ldots, T^{(k-2) r_J} y of length k-1. If one sets x_J := T^{-r_J} y, and lets U_{\alpha_J} be an arbitrary set in the open cover containing x_J, then we observe that

T^{i(r_{a+1} + \ldots + r_J)} x_J = T^{i(r_{a+1} + \ldots + r_{J-1})} ( T^{(i-1) r_J} y ) \in T^{i(r_{a+1} + \ldots + r_{J-1})}(V) (2)

for all 0 \leq a < J and 1 \leq i \leq k-1. If V is a sufficiently small neighbourhood of x_{J-1}, we thus see (from the continuity of the T^{i(r_{a+1} + \ldots + r_{J-1})} that we verify all the required properties needed to close the induction. \Box

We apply the above lemma with J equal to the number of sets in the open cover. By the pigeonhole principle, we can thus find 0 \leq a < b \leq J such that U_{\alpha_a} = U_{\alpha_b}. If we then set x := x_b and r := r_{a+1} + \ldots + r_b we obtain Theorem 4 as required. \Box

It is instructive to compare the k=2 case of the above arguments with the proof of Theorem 1 from the previous lecture. (For a comparison of this type of proof with the more classical combinatorial proof, see my Montreal lecture notes.)

— Ultrafilter proof of van der Waerden —

We now give a translation of the above proof into the language of ultrafilters (or more precisely, the language of Stone-Čech compactifications). This language may look a little strange, but it will be convenient when we study more general colouring theorems in the next lecture. As before, we will prove Theorem 4 instead of Theorem 1 (thus we only need to find one progression, rather than infinitely many). The key proposition is

Proposition 1. (Ultrafilter version of van der Waerden) Let p be a minimal element of \beta {\Bbb Z}. Then for any k \geq 1 there exists q \in \beta ({\Bbb Z} \times {\Bbb N}) such that
\lim_{(n,r) \to q} n + ir + p = p \hbox{ for all } 0 \leq i \leq k-1. (3)

Suppose for the moment that this proposition is true. Applying it with some minimal element p of \beta {\Bbb Z} (which must exist, thanks to Exercise 10 of the previous lecture), we obtain q \in \beta ({\Bbb Z} \times {\Bbb N}) obeying (3). If we let x := T^p y for some arbitrary y \in X, we thus obtain

\lim_{(n,r) \to q} T^{n+ir} x = x \hbox{ for all } 0 \leq i \leq k-1. (4)

If we let U_\alpha be an element of the open cover that contains x, we thus see that T^{n+ir} x \in U_\alpha for all 0 \leq i \leq k-1 and all (n,r) \in {\Bbb Z} \times {\Bbb N} which lie in a sufficiently small neighbourhood of q. Since a LCH space is always dense in its Stone-Čech compactification, the space of all (n,r) with this property is non-empty, and Theorem 4 follows.

Proof of Proposition 1. We induct on k. The case k=1 is trivial (one could take e.g. q = (0,1), so suppose k > 1 and that the claim has already been proven for k-1. Then we can find q' \in \beta ({\Bbb Z} \times {\Bbb N}) such that

\lim_{(n,r) \to q'} n + ir + p = p (5)

for all 0 \leq i \leq k-2.

Now consider the expression

p_{i,a,b} := \lim_{(n_1,r_1) \to q'} \ldots \lim_{(n_b,r_b) \to q'} i(r_{a+1}+\ldots+r_b) + m_b + p (6)

for any 1 \leq a \leq b and 1 \leq i \leq k-1, where

m_b := \sum_{i=1}^b n_i - r_i. (7)

Applying (5) to the (n_b,r_b) limit in (6), we obtain the recursion p_{i,a,b} = p_{i,a,b-1} for all b > a. Iterating this, we conclude that

p_{i,a,b} = p_{i,a,a} = p_{0,a,a} (8)

for all 1 \leq i \leq k-1. For i=0, (8) need not hold, but instead we have the easily verified identity

p_{0,a,b} = p_{0,b,b}. (8′)

Now let p_* \in \beta {\Bbb N} \backslash {\Bbb N} be a non-principal ultrafilter and define p' := \lim_{a \to p_*} p_{0,a,a} = \lim_{b \to p_*} p_{0,b,b}. Observe from (6) that all the p_{i,a,b} lie in the closed set \beta {\Bbb Z} + p, and so p’ does also. Since p is minimal, there must exist p'' \in \beta {\Bbb Z} such that p = p” + p’. Expanding this out using (8) or (8′), we conclude that

\lim_{h \to p''} \lim_{a \to p_*} \lim_{b \to p_*} h+p_{i,a,b} = p (9)

for all 0 \leq i \leq k-1. Applying (6), we conclude

\lim_{h \to p''} \lim_{a \to p_*} \lim_{b \to p_*} \lim_{(n_1,r_1) \to q'} \ldots \lim_{(n_b,r_b) \to q'} n+ir+p = p (10)

where n := h + m_b and r := r_{a+1}+\ldots+r_b. Now, define q \in \beta ({\Bbb Z} \times {\Bbb N}) to be the limit

q := \lim_{h \to p''} \lim_{a \to p_*} \lim_{b \to p_*} \lim_{(n_1,r_1) \to q'} \ldots \lim_{(n_b,r_b) \to q'} (n,r) (11)

then we obtain Proposition 1 as desired. \Box

Exercise 5. Strengthen Proposition 1 by adding the additional conclusion \lim_{(n,r) \to q} r \not \in {\Bbb N}. Using this stronger version, deduce Theorem 1 directly without using the trick of multiplying X with a cyclic shift system that was used to deduce Theorem 1 from Theorem 4. \diamond

Theorem 1 can be generalised to multiple commuting shifts:

Theorem 6. (Multiple recurrence in open covers) Let (X,{\mathcal F}) be a compact topological space, and let T_1,\ldots,T_k: X \to X be commuting homeomorphisms. Let (U_\alpha)_{\alpha \in A} be an open cover of X. Then there exists U_\alpha such that T_1^{-r} U_\alpha \cap \ldots \cap T_k^{-r} U_\alpha \neq \emptyset for infinitely many r.

Exercise 6. By adapting one of the above arguments, prove Theorem 6. \diamond

Exercise 7. Use Theorem 6 to establish the following the multidimensional van der Waerden theorem (due to Gallai): if a lattice {\Bbb Z}^d is finitely coloured, and v_1,\ldots,v_d \in {\Bbb Z}^d, then one of the colour classes contains a pattern of the form n + rv_1,\ldots,n+rv_d for some n \in {\Bbb Z}^d and some non-zero r. \diamond

Exercise 8. Show that Theorem 6 can fail, even for k=3 and T_1 = \hbox{id}, if the shift maps T_j are not assumed to commute. (Hint: First show that in the free group F_2 on two generators a, b, and any word w \in F_2 and non-zero integer r, the three words w, a^n w, b^n w cannot all begin with the same generator after reduction. This can be used to disprove a non-commutative multidimensional van der Waerden theorem, which can turn be used to disprove a non-commutative version of Theorem 6.) \diamond

— Proof of multiple Birkhoff —

We now use van der Waerden’s theorem and an additional Baire category argument to deduce Theorem 3 from Theorem 1. The key new ingredient is

Lemma 3. (Semicontinuous functions are usually continuous) Let (X,d) be a metric space, and let F: X \to {\Bbb R} be semicontinuous. Then the set of points x where F is discontinuous is a set of the first category (i.e. a countable union of nowhere dense sets). In particular, by the Baire category theorem, if X is complete and non-empty, then F is continuous at at least one point.

Proof. Without loss of generality we can take F to be upper semicontinuous. Suppose F is discontinuous at some point x. Then, by upper continuity, there exists a rational number q such that

\lim \inf_{y \to x} F(y) < q \leq F(x). (3)

In other words, x lies in the boundary of the closed set \{ x : F(x) \geq q \}. But boundaries of closed sets are always nowhere dense, and the claim follows. \Box

Now we prove Theorem 3. Without loss of generality we can take X to be minimal. Let us place a metric d on the space X. Define the function F: X \to {\Bbb R}^+ by the formula

F(x) := \inf_{n \geq 1} \sup_{1 \leq i \leq k-1} d( T^{i n} x, x ). (4)

It will suffice to show that F(x)=0 for at least one x (notice that if the infimum is actually attained at zero for some n, then x is a periodic point and the claim is obvious). Suppose for contradiction that F is always positive. Observe that F is upper semicontinuous, and so by Lemma 3 there exists a point of continuity of F. In particular there exists a non-empty open set U such that F is bounded away from zero.

By uniform continuity of T^n, we see that if F is bounded away from zero on U, it is also bounded away from zero on T^n V for any n (though the bound from below depends on n). Applying Lemma 1, we conclude that F is bounded away from zero on all of X, thus there exists \varepsilon > 0 such that F(x) > \varepsilon for all x \in X. But this contradicts Theorem 1 (or Theorem 4), using the balls of radius \varepsilon/2 as the open cover. This contradiction completes the proof of Theorem 3.

Exercise 9. Generalise Theorem 3 to the case in which T is merely assumed to be continuous, rather than be a homeomorphism. (Hint: let \tilde X \subset X^{\Bbb Z} denote the space of all sequences (x_n)_{n \in {\Bbb Z}} with x_{n+1} = T x_n for all n, with the topology induced from the product space X^{\Bbb Z}. Use a limiting argument to show that \tilde X is non-empty. Then turn \tilde X into a topological dynamical system and apply Theorem 3.) \diamond

Exercise 10. Generalise Theorem 3 to multiple commuting shifts (analogously to how Theorem 6 generalises Theorem 1). \diamond

Exercise 11. Combine Exercises 9 and 10 by obtaining a generalisation of Theorem 3 to multiple non-invertible commuting shifts. \diamond

Exercise 12. Let (X, {\mathcal F}, T) be a minimal topological dynamical system, and let k \geq 1. Call a point x in X k-fold recurrent if there exists a sequence n_j \to \infty such that T^{in_j} x \to x for all 0 \leq i \leq k-1. Show that the set of k-fold recurrent points in X is residual (i.e. the complement is of the first category). In particular, the set of k-fold recurrent points is dense. \diamond

Exercise 13. In the boolean Bernoulli system (2^{\Bbb Z}, A \mapsto A+1), show that the set A consisting of all non-zero integers which are divisible by 2 an even number of times is almost periodic. Conclude that there exists a minimal topological dynamical system (X, {\mathcal F}, T) such that not every point in X is 3-fold recurrent (in the sense of the previous exercise). (Compare this with the arguments in the previous lecture, which imply that every point in X is 2-fold recurrent.) \diamond

Exercise 14. Suppose that a sequence of continuous functions f_n: X \to {\Bbb R} on a metric space converges pointwise everywhere to another function f: X \to {\Bbb R}. Show that f is continuous on a residual set. \diamond

Exercise 15. Let (X, {\mathcal F}, T) be a minimal topological dynamical system, and let f: X \to {\Bbb R} be a function which is T-invariant, thus Tf = f. Show that if f is continuous at even one point x_0, then it has to be constant. (Hint: x_0 is in the orbit closure of every point in X.) \diamond

[Update, Jan 15: bad link fixed.]

[Update, Jan 21: Additional exercise added.]

[Update, Jan 26: Another additional exercise added.]

[Update, Mar 4: Slight correction to proof of Proposition 1.]