## Recurrence theorems

Let ${(X,\mu)}$ be a probability space and let ${T:X\rightarrow X}$ be a (measurable) map such that for any (measurable) set ${A\subset X}$ we have ${\mu(T^{-1}A)=\mu(A)}$, where as usual ${T^{-1}A:=\{x\in X:Tx\in A\}}$. Such ${T}$ is called a measure preserving transformation. In this setting, all sets in the pre-orbit of some given set ${A}$, i.e. the sets ${T^{-n}A}$, have the same measure. If in addition ${\mu(A)>0}$ then it is clear that two of those sets must intersect (since the total measure is ${1}$). This simple observation is (a consequence of) the Poincaré recurrence theorem.

Several improvements can be made to this theorem: we can ask for more than two sets in the orbit to intersect simultaneously, we can ask to have not one but many pairs with non-empty intersection, we can require the intersection to be not only non-empty but to have positive measure (how much measure are we guaranteed to find?). In this post I will list many such extensions that have been proved so far, as well as related results and some questions (that as far as I know are open). I will not provide the proof to most of the results, however I will always put a reference.

— 1. Single Recurrence theorems —

We start by stating properly the Poincaré recurrence theorem. In what follows (and as usual) to say that ${(X,{\cal B},\mu,T)}$ is a measure preserving system means that ${{\cal B}}$ is a ${\sigma}$-algebra on ${X}$, ${\mu:{\cal B}\rightarrow[0,1]}$ is a probability measure and ${T:X\rightarrow X}$ is a measure preserving transformation. The first 5 results appear in the beginning of this survey by Bergelson.

Theorem 1 (Poincaré recurrence theorem/Pigeonhole Principle) Let ${(X,{\cal B},\mu,T)}$ be a measure preserving system and let ${A\in {\cal B}}$ have positive measure. Then for some ${n\in {\mathbb N}}$, the intersection ${A\cap T^{-n}A}$ has positive measure. Moreover one can take ${n\leq1+1/\mu(A)}$.

The points in the intersection ${A\cap T^{-n}A}$ are called recurrent because after ${n}$ iterations of the map ${T}$ they are back to ${A}$. This is where the name “recurrence theorem” comes from.

The first part of this theorem will follow immediately from the next result which is also called the Poincaré recurrence theorem. It says roughly that almost all points in ${A}$ are recurrent:

Theorem 2 (Poincaré recurrence theorem, again) Let ${(X,{\cal B},\mu,T)}$ be a measure preserving system and let ${A\in {\cal B}}$. Then the set ${\{a\in A:T^na\in A\text{ for some }n\in{\mathbb N}\}}$ has measure ${\mu(A)}$.

This implies also that if ${\mu(A)>0}$ then for some ${n\in {\mathbb N}}$ we have ${\mu(A\cap T^{-n}A)>0}$, because the countable union of the intersections ${A\cap T^{-n}A}$ has measure ${\mu(A)>0}$.

Applying the previous theorem to each one of the transformations ${T^k}$ we obtain the following stronger looking result:

Theorem 3 (Poincaré recurrence theorem, yet again) Let ${(X,{\cal B},\mu,T)}$ be a measure preserving system and let ${A\in {\cal B}}$. Then the set ${\{a\in A:T^na\in A\text{ for infinitely many }n\in{\mathbb N}\}}$ has measure ${\mu(A)}$.

By adapting the proof of this results we can get a more general statement that applies to any sequence of sets ${\{A_n\}}$ with a stationary property (so far we have been considering ${A_n=T^{-n}A}$).

Proposition 4 Let ${{\cal B}}$ be an algebra of subsets of ${X}$ and ${\mu}$ be a finitely additive probability measure. For each ${n=0,1,...}$ let ${A_n\in{\cal B}}$ be such that for any ${n\geq m\geq0}$ we have ${\mu(A_n\cap A_m)=\mu(A_0\cap A_{n-m})}$. If ${\mu(A_0)>0}$ then for some ${n\in {\mathbb N}}$, the intersection ${A_0\cap A_n}$ has positive measure. Moreover one can take ${n\leq1+1/\mu(A)}$.

This can be useful in applications when we don’t have a (countably additive) measure, for instance when we deal with ultrafilters.

— 1.1. Large intersections —

Still on this setting when we only have a finitely additive measure and the events ${A_n}$ are not necessarily of the form ${A_n=T^{-n}A}$ for some measure preserving transformation ${T}$ we can improve the previous result in another direction, this answers the question of how big can we make the measure of the intersection ${A_i\cap A_j}$ in the previous proposition. If the sequence ${\{A_n\}}$ consists of independent events then the intersection ${A_i\cap A_j}$ has measure ${\mu(A_0)^2}$ for any pair ${i\neq j}$, so the next result is in a way the best possible:

Proposition 5 Let ${{\cal B}}$ be an algebra over ${X}$ and ${\mu}$ be a finitely additive probability measure on ${{\cal B}}$. For each ${n=0,1,...}$ let ${A_n\in{\cal B}}$ be such that for any ${n\geq m\geq0}$ we have ${\mu(A_n\cap A_m)=\mu(A_0\cap A_{n-m})}$. If ${a=\mu(A_0)>0}$, then for each ${\lambda\lambda a^2}$. Moreover we can take ${n<1+(1-a\lambda)/(a-a\lambda)}$.

By the (infinite) Ramsey’s theorem this implies that, for any fixed ${\lambda<1}$, there exists a sequence ${\{n_i\}_i}$ such that for any ${i\lambda a^2}$. An interesting question for which I could not find an answer is if the sequence ${\{n_i\}}$ can always be taken to have positive upper density. On the other hand we can always find a sequence ${\{m_i\}_i}$ of density ${a}$ such that the intersection ${A_{m_i}\cap A_{m_j}}$ has positive measure, see proposition 15 bellow.

We now return to the case when ${A_n=T^{-n}A}$ and we consider the set of recurrent times.

Definition 6 (Recurrent times) Let ${(X,{\cal B},\mu,T)}$ be a measure preserving system and ${A\in{\cal B}}$ have positive measure. For each ${\lambda\in[0,1)}$ define the set of recurrent times by

$\displaystyle R_\lambda:=\{n\in {\mathbb N}: \mu(A\cap T^{-n}A)>\lambda\mu(A)^2\}$

Applying the previous result to ${A_n=T^{-kn}A}$ for each ${k=1,2,...}$ implies that the set ${R_\lambda}$ is always infinite, and indeed it contains multiples of each ${k}$. Furthermore, the sets ${R_\lambda}$ satisfies other notions of largeness: A subset of ${{\mathbb R}}$ is called syndetic if it has bounded gaps, i.e. if there is some ${K>0}$ such that in any interval of length ${K}$ there exists at least one element of the set.

Theorem 7 (Khintchine’s theorem) For any ${\lambda<1}$, the set ${R_\lambda}$ is syndetic.

This theorem is also proved (and generalized, see proposition 14 bellow) in the last section of the same survey of Bergelson.

It turns out that more can be said. I now define the notion of IP-set and IP${^*}$ set, as well as their finitistic versions:

Definition 8 (IP, IP${^*}$, IP${_r}$ and IP${_r^*}$ sets) Given a subset of the positive integers ${A=\{n_1 (not necessarily infinite) one forms the set of their finite sums ${FS(A)=\{n_{i_1}+...+n_{i_k}|k\in {\mathbb N}, i_1<.... A set ${I\subset {\mathbb N}}$ is called an IP-set it it contains ${FS(A)}$ for some infinite set ${A}$ and it is called an IP${_r}$-set if it contains ${FS(A)}$ for some set ${A}$ with ${r}$ elements.

A subset of ${{\mathbb N}}$ is an IP${^*_r}$ if it has non-empty intersection with every IP${_r}$ set, and it is an IP${^*}$ set if it has non-empty intersection with every IP set.

For instance the set of numbers that use only the digits ${1}$ and ${0}$ (in base ${10}$) is the IP set formed by the finite sums of the sequence ${n_i=10^{i-1}}$, and the subset of those numbers with at most ${r}$ digits is an IP${_r}$ set. From this example we see that while IP sets have some nice structure, they may be very sparse. Also each IP set is an IP${_r}$ set for each ${r}$.

As an example for IP${^*_r}$ we have the trivial example of ${{\mathbb N}}$ itself. It is also not difficult to see that ${k{\mathbb N}=\{kn:n\in {\mathbb N}\}}$ is an IP${^*_r}$-set for any ${k\in {\mathbb N}}$ as well. Furthermore, since each IP set is an IP${_r}$ set, we have that each IP${_r^*}$ set is a IP${^*}$ set.

Moreover, the intersection of any two IP${^*}$-sets is again an IP${^*}$-set (this is essentially Hindman’s theorem). From this we see that IP${^*}$-sets are in a sense very large. A good exercise is to prove that every IP${^*}$-set is syndetic. Thus the following result generalizes Khintchine’s theorem.

Proposition 9 For any measure preserving system and any set ${A}$ with positive measure, the set of recurrent times ${R_\lambda}$ given by definition 6 (with ${\lambda\in(0,1)}$) is an IP${^*}$-set.

The proof (which follows from the proof of proposition 5) can be found on pages 49-50 of this other survey by Bergelson. That proof further generalizes to the finitistic version:

Proposition 10 For any measure preserving system, any set ${A}$ with positive measure and any ${\lambda\in(0,1)}$ there exists some ${r\in{\mathbb N}}$ such that the set of recurrent times ${R_\lambda}$ is an IP${_r^*}$-set.

Proof: Let ${a=\mu(A)}$ and take ${r}$ large to be determined later. We will prove that ${R_\lambda}$ is an IP${_r^*}$-set. Let ${S}$ be an IP${_r}$ set, say it contains the finite sums of the set ${\{x_1,...,x_r\}}$. Let ${s_i=x_1+...+x_i}$ and consider the sets ${T^{-s_i}A}$. We claim that two of those sets have intersection with measure larger than ${a^2\lambda}$. Assuming the claim for now, say ${\mu(T^{-s_i}A\cap T^{-s_j}A)>a^2\lambda}$ with $latex {ja^2\lambda}&fg=000000$ and ${s_i-s_j\in R_\lambda}$. On the other hand ${s_i-s_j=x_{j+1}+...+x_i\in S}$ so ${S\cap R_\lambda}$ is non-empty and since ${S}$ was an arbitrary IP${_r}$ set we conclude that ${R_\lambda}$ is an IP${_r^*}$ set.

To prove the claim let ${f_i}$ be the indicator function of ${T^{-s_i}A}$ and let ${f=\sum f_i}$. Note that ${\int f_id\mu=\mu(T^{-s_i}A)=a}$. By Jensen’s inequality applied to ${f}$ and the convex function ${x\mapsto x^2}$ we get

$\displaystyle (ra)^2=\left(\int fd\mu\right)^2\leq \int f^2d\mu=\sum_{i,j=1}^r\mu(T^{-s_i}A\cap T^{-s_j}A)=ra+\sum_{i\neq j}\mu(T^{-s_i}A\cap T^{-s_j}A)$

Thus for some ${i\neq j}$ we have

$\displaystyle \mu(T^{-s_i}A\cap T^{-s_j}A)\geq \frac{(ra)^2-ra}{r^2-r}=a^2-\frac{a-a^2}{r-1}$

and for ${r}$ sufficiently large (we need ${r>(1-a\lambda)/(a-a\lambda)}$) that is greater than ${a\lambda}$ and this finishes the proof. $\Box$

— 1.2. Large recurrent times —

In this subsection I focus on results about how “large” is the set ${R_0}$ (see definition 6) in several ways. For these results I didn’t find a correspondent formulation for ${R_\lambda}$. The first result in this section is Sarkozy’s theorem (for which I presented two different proofs in previous posts) and states that ${R_0}$ intersects the image on any divisible polynomial:

Theorem 11 (Sarkozy) Let ${R_0}$ be any set of recurrent times and let ${f\in{\mathbb Z}[x]}$ be a divisible polynomial (i.e. it has a root mod ${n}$ for any ${n}$). Then there exists ${k\in{\mathbb Z}}$ such that ${f(k)\in R_0}$.

It is also true that ${R_0}$ intersects the sets ${P+1}$ ad ${P-1}$, where ${P}$ is the set of prime numbers, this is proved for instance in this paper by Kamae and Mendes-France. Moreover for each value of ${k}$ other that ${\pm1}$ it is easy to construct a set ${R_0}$ that does not intersect ${P+k}$ (take a finite cyclic system). The same example shows that the set ${f({\mathbb Z})}$ is not for a polynomial ${f}$ which is not divisible.

Actually, a little more can be said: let ${E}$ be either ${f({\mathbb Z})}$ for a divisible polynomial ${f}$ or ${E=P-1}$ or ${E=P+1}$. Then for every measure preserving system and any set ${A}$ with ${\mu(A)>0}$ there exists ${\lambda<1}$ (which may depend on ${E}$ as well as on the system and the choice of ${A}$) such that ${R_\lambda}$ intersects ${E}$.

Many other examples of sets that intersect ${R_0}$ for every system and set with positive measure ${A}$ are know, those are called recurrent sets.

— 2. Multiple recurrence —

By using essentially the proof of proposition 10 one can generalize that result to multiple intersections:

Proposition 12 Let ${(X,{\cal B},\mu)}$ be a probability space. Let ${\{A_n\}}$ be a sequence of sets with the same measure and assume that ${a=\mu(A_i)>0}$. Then for each ${\lambda<1}$ and each ${k\in {\mathbb N}}$ there exist positive integers ${n_1 < \cdots < n_k}$ such that ${\mu(A_{n_1}\cap\cdots\cap A_{n_k})>\lambda a^k}$. Moreover we can take ${n_k}$ smaller than a constant depending only on ${a,\lambda}$ and ${k}$.

This can be considered the simplest case of multiple recurrence, but in many applications it is important to have some relation between ${n_i}$. The most well-know case is Furstenberg’s multiple recurrence theorem (see for instance Furstenberg’s original paper or this recent exposition of Zhao):

Theorem 13 Let ${(X,{\cal B},\mu,T)}$ be a probability preserving system and let ${A\in{\cal B}}$ have positive measure. Then for each ${k\in {\mathbb N}}$ there exists some ${n\in {\mathbb N}}$ such that

$\displaystyle \mu\left(A\cap T^{-n}A\cap T^{-2n}A\cap...\cap T^{-kn}A\right)>0$

First note that when ${k=1}$ this is theorem 1. Note also that this result only guarantees that the measure of the intersection is positive, there are very few results on multiple recurrence that guarantee a large intersection. The following exception is in the end of the already mentioned Bergelson’s survey (corollary 5.4).

Proposition 14 Let ${(X,{\cal B},\mu,T)}$ be an invertible measure preserving system (invertible means that ${T}$ is a bijection) and let ${A\in{\cal B}}$ with ${\mu(A)>0}$. Then for each ${\lambda<1}$ there exist ${n,m\in {\mathbb Z}}$ such that

$\displaystyle \mu(A\cap T^nA\cap T^mA\cap T^{n+m}A)>\lambda\mu(A)^4$

Moreover the set of pairs ${(n,m)\in {\mathbb Z}^2}$ that satisfy that is syndetic.

— 2.1. Large recurrent times —

Furstenberg’s multiple recurrence theorem (theorem 13) provides an alternative proof of the celebrated Szemerédi’s theorem stating that any subset ${E\subset {\mathbb N}}$ with positive upper density contains arbitrarily long arithmetic progressions. To deduce Szemerédi’s theorem from theorem 13 Furstenberg created the so called correspondence principle. Conversely, it is also possible do deduce theorem 13 from Szemerédi’s theorem, one way to do this is using the following recurrence theorem (which is similar to proposition 12 but not quite the same):

Proposition 15 Let ${(X,{\cal B},\mu,T)}$ a probability preserving system and let ${A\in{\cal B}}$ have positive measure. Then there exists a set ${E\subset{\mathbb N}}$ with Banach density ${d^*(E)\geq\mu(A)}$ and such that for any finite subset ${\{n_1,...,n_k\}\subset E}$ with ${k}$ elements we have

$\displaystyle \mu(A\cap T^{-n_1}A\cap...\cap T^{-n_k}A)>0$

The original proof of this fact, found by Bergelson, is given in this paper.

We now make a definition which is for theorem 13 the same as definition 6 is for proposition 12.

Definition 16 (Multiple-Recurrent times) Let ${(X,{\cal B},\mu,T)}$ be a measure preserving system and ${A\in{\cal B}}$ have positive measure. For each ${k\in{\mathbb N}}$ define the set of multiple-recurrent times by

$\displaystyle R_k:=\{n\in {\mathbb N}: \mu(A\cap T^{-n}A\cap T^{-2n}A\cap...\cap T^{-(k-1)n}A)>0\}$

Keeping the analogy, a theorem in the spirit of proposition 10 was proved by Furstenberg and Katznelson in this paper:

Theorem 17 For any probability preserving system, any set ${A}$ with positive measure and any ${k}$, there exists ${r\in{\mathbb N}}$ such that the set ${R_k}$ is IP${_r^*}$

To give an example why it is of interest to have IP${_r^*}$ instead of just IP${^*}$, I now present a proof of the following result:

Theorem 18 For any probability preserving system, any set ${A}$ with positive measure and any ${k}$, there exists a prime ${p}$ such that

$\displaystyle \mu(A\cap T^{-(p+1)}A\cap T^{-2(p+1)}A\cap...\cap T^{-k(p+1)}A)>0$

The same result holds for ${p-1}$ instead of ${p+1}$. Moreover, as remarked before, the result is false for any other constant different from ${\pm1}$, even for ${k=1}$. The following argument was taken from this note.

Proof: By theorem 17 it suffices to show that for any ${r}$ there exists an IP${_r}$ set inside ${P+1}$. By recent results of Green, Tao and Ziegler we have that for any ${r,l\in{\mathbb N}}$ there exists a vector ${x\in{\mathbb Z}^r}$ such that ${Ax+b}$ is a vector of ${l}$ primes, where ${A\in {\mathbb Z}_{r\times l}}$ and ${b\in{\mathbb Z}^l}$, as long as the ${l}$ affine linear forms ${x\mapsto[Ax+b]_i}$ are affinely independent and for each ${k\geq2}$ there exists ${y\in {\mathbb Z}^r}$ such that no coordinate of ${Ay+b}$ is divisible by ${k}$.

If we make ${b}$ be the vector with all coordinates ${-1}$ and ${A}$ be a matrix where each line is the characteristic function of a different nonempty subset of ${\{1,...,r\}}$ then we are in the conditions of the theorem and we get that the IP${_r}$ set generated by the coordinates of ${x}$ is inside ${P+1}$. $\Box$

Also a generalization of Sárközy’s theorem holds. In fact, not only the set ${R_k}$ intersects any divisible polynomial, but the intersection is very large in the following sense:

Theorem 19 Given any measure preserving system, any set ${A}$ with positive measure, any ${k\in{\mathbb N}}$ and any polynomials ${f_1,...,f_k\in{\mathbb Z}[x]}$ with ${f_i(0)=0}$, the set

$\displaystyle \{n:\mu(A\cap T^{-f_1(n)}A\cap T^{-f_2(n)}A\cap...\cap T^{-f_k(n)}A)>0\}$

is an IP${^*}$ set.

This result is due to Bergelson and McCutcheon and is part of several refinements of what is called the polynomial Szemerédi theorem.

Unfortunately it is not known (yet) if the set described in the previous theorem is actually IP${_r^*}$ for some ${r}$. However, a result that generalizes both this theorem and theorem 18 was obtained by Frantzikinakis, Host and Kra in this paper.

Theorem 20 Given any measure preserving system, any set ${A}$ with positive measure, any ${k\in{\mathbb N}}$ and any polynomials ${f_1,...,f_k\in{\mathbb Z}[x]}$ with ${f_i(0)=0}$, there exists a prime ${p}$ such that

$\displaystyle \mu(A\cap T^{-f_1(p-1)}A\cap T^{-f_2(p-1)}A\cap...\cap T^{-f_k(p-1)}A)>0$

Again the result with ${p+1}$ is also true.

— 3. Final Remarks —

In this post I restricted the attention to a single measure preserving transformation, in other words, a ${{\mathbb Z}}$ action. Most of the results presented have generalizations for actions of other groups (usually ${{\mathbb Z}^d}$ or a general countable abelian group). There are also many other sets that I didn’t mention which are known to intersect the set ${R_0}$ from definition 6 and the set ${R_k}$ from definition 16, although I don’t know any other (non-trivial) example for sets that intersect every ${R_\lambda}$. A notable example of sets that intersect ${R_0}$ are certain IP-polynomials, an example is the set ${f(I)}$ where ${f}$ is a polynomial and ${I}$ is an IP set. To construct another example of an IP-polynomial, let ${{\cal F}}$ denote the family of finite non-empty subsets of ${{\mathbb N}}$. Let ${\{n_i\}}$ and ${\{m_i\}}$ be strictly increasing sequences in ${{\mathbb N}}$ and for each ${\alpha\in{\cal F}}$ let $n_\alpha=\sum_\alpha n_i$ and $m_\alpha=\sum_\alpha m_i$. Now the set ${\{n_\alpha.m_\alpha|\alpha\in{\cal F}\}}$ is a degree two IP polynomial that intersects ${R_0}$.

On a different direction, one could “join” both definitions and consider the set of times of multiple returns with high intersection, formally the set

$\displaystyle \{n:\mu(A\cap T^{-n}A\cap...\cap T^{-(k-1)n}A)>\lambda\mu(A)^k\}$

I don’t remember any result of this nature, either on the positive or negative direction.