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$