Multiple recurrence and large intersections for abelian group actions

Multiple recurrence and large intersections for abelian group actions, Discrete Analysis 2021:18, 91 pp.

In 1975, Szemerédi proved his famous theorem that asserts that for every positive integer $k$ and every $\delta>0$ there exists $n$ such that every subset of $\{1,2,\dots,n\}$ of size at least $\delta n$ contains an arithmetic progression of length $k$. A couple of years later, Furstenberg found a second proof of the theorem using ergodic theory. An advantage of Furstenberg’s approach was that it was more amenable to generalization, a result of which was that it led to a whole new field of combinatorial ergodic theory and the discovery of important results such as the density Hales-Jewett theorem, due to Furstenberg and Katznelson, and the polynomial Szemerédi theorem of Bergelson and Leibman.

The starting point for the ergodic approach to these problems is a general principle known as the Furstenberg correspondence, which makes it possible to translate many combinatorial problems into equivalent statements about topological or measure-preserving dynamical systems. For example, Szemerédi’s theorem itself is equivalent to the following statement. Let $X$ be a probability space and $T:X\to X$ a measure-preserving map (meaning that $|T^{-1}(A)|=|A|$ for every measurable subset $A$ of $X$). Then for every $k$ and every $A\subset X$ of positive measure there exists $n$ such that
$$|A\cap T^{-n}(A)\cap T^{-2n}(A)\dots\cap T^{-(k-1)n}(A)|>0.$$

It is natural to ask whether something more precise can be said. In particular, can we find some explicit constant $c>0$, depending on $k$ and $|A|$, and show that the lim sup of the measure on the left-hand side is at least $c$? And if so, what $c$ can we hope to obtain?

A random set of density $\delta$ (or rather, a dynamical system built out of a sequence of such sets via the Furstenberg correspondence) shows easily that one cannot hope for better than $|A|^k$. And the following simple argument shows that one can attain a bound of $|A|^k$ when $k=2$. Let $A$ be a set of measure $\delta$ and let $\epsilon>0$. Let $f$ be the sum of the characteristic functions of $A, T^{-1}A, \dots, T^{-(r-1)}A$, and let us write $A_i$ for $T^{-i}A$. Then $\|f\|_1=r\delta$, which implies by Cauchy-Schwarz that $\|f\|_2\geq r\delta$. But $\|f\|_2^2=\sum_{i,j=0}^r|A_i\cap A_j|$, which implies that $\sum_{i\ne j}|A_i\cap A_j|\geq r^2\delta^2-r\delta$. By averaging, for large $r$ this gives us $i\ne j$ such that $|A_i\cap A_j|\geq\delta^2-\epsilon$, and then by the measure-preserving property we obtain $n$ such that $|A\cap T^{-n}A|\geq\delta^2-\epsilon$.

This argument can also be used to show that the set $R$ of $n$ such that $|A\cap T^{-n}A|\geq\delta^2-\epsilon$ is syndetic, which means that there is some $N$ such that $R$ intersects every interval of length $N$ (or in other words it has bounded gaps). Indeed, if that is not the case, then for any $r$ we can inductively build a sequence $n_1,n_2,\dots,n_r$ such that none of the sums $n_{i_1}+\dots+n_{i_t}$ belong to $R$. But by the above argument there must exist $i<j$ such that $|A_{n_1+n_2+\dots+n_i}\cap A_{n_1+n_2+\dots+n_j}|\geq \delta^2-\epsilon$, and then we have that $|A\cap A_{n_{i+1}+\dots+n_j}|\geq\delta^2-\epsilon$, contradicting the fact that $n_{i+1}+\dots+n_j\notin R$. This result is called Khintchine’s recurrence theorem.

For larger $k$ the problem becomes harder and the answers are sometimes quite surprising. For example, it was shown by Bergelson, Host and Kra that the natural analogues of Khintchine’s recurrence theorem (under the additional hypothesis of ergodicity) for $k=3$ and $k=4$ are true (so for instance when $k=3$ there is a syndetic set of $n$ such that $|A\cap T^{-n}A\cap T^{-2n}A|\geq|A|^3-\epsilon$), but the analogues for higher $k$ are false.

A similar phenomenon occurs in the combinatorial set-up: if $A$ is a subset of the cyclic group $\mathbb Z/n\mathbb Z$ of density $\delta$, then for $k\leq 4$ there exists $d\ne 0$ such that $|A\cap(A-d)\cap\dots\cap(A-(k-1)d)|\geq(\delta^k-o(1))n$, but when $k\geq 5$ such a $d$ need not exist. The counterexample is a construction of Imre Ruzsa, which also underlies the counterexample to the ergodic statement. Ruzsa’s example in its turn is a generalization of Behrend’s famous construction of a subset of $\{1,2,\dots,n\}$ of density at least $\exp(-c\sqrt{\log n})$ that contains no arithmetic progression of length 3.

This paper looks at large-intersection results, both positive and negative, for dynamical systems indexed by general countable Abelian groups. A syndetic set in such a group $G$ is defined to be a subset $S$ for which there exists a finite set $K$ such that $S$ intersects every translate of $K$. (It is easy to see that this agrees with the definition given above when $G=\mathbb Z$.) One of the main results of the paper states that if $\phi,\psi:G\to G$ are homomorphisms such that $\phi,\psi$ and $\phi-\psi$ all have images of finite index, then for every ergodic measure-preserving system indexed by $G$ – that is, a set of measure-preserving maps $T_g$ from a probability space $X$ to itself such that $T_gT_h=T_{gh}$ for all $g,h\in G$ – the analogue of the Khintchine recurrence theorem holds. In other words, if $\epsilon>0$ and $A\subset X$ is a measurable set, then the set $\{g\in G:|A\cap T_{\phi(g)}^{-1}A\cap T_{\psi(g)}^{-1}A|\geq|A|^2-\epsilon\}$ is syndetic.

They also obtain some related combinatorial results. For instance, the construction of Ruzsa mentioned above is of a subset of $\{1,2,\dots,n\}$ of density $\exp(-c\sqrt{\log n})$ that contains no non-degenerate subset of the form $\{q(0),q(1),q(2),q(3),q(4)\}$ where $q$ is a polynomial of degree at most 2. (Note that if we replace 4 by 3 and “degree at most 2” by “degree 1” then we obtain a definition of an arithmetic progression of length 4.) Given a quintuple $r=(r_0,\dots,r_4)$, the authors define a quadratic $r$-configuration of length 5 to be a set of the form $\{q(r_0),\dots,q(r_4)\}$. They then show that for every $r$ there is a constant $c(r)$ such that for each $n$ there is a subset of $\{1,2,\dots,n\}$ of density at least $\exp(-c(r)\sqrt{\log n})$ that contains no such configuration. This turns out to imply the failure of the large intersection property in the following situation: we have a dynamical system indexed by $\mathbb Z$ and distinct positive integers $r_1,\dots,r_4$, where we regard $r_i$ as the homomorphism that multiplies $\mathbb Z$ by $r_i$.

As well as these and other results, the paper contains some interesting open problems. For example, they conjecture that, more generally, five genuinely distinct homomorphisms cannot have the large-intersections property. More precisely, if $\phi_1,\dots,\phi_4$ are homomorphisms from $G$ to $G$ such that any two of them are equal only on a subgroup of infinite index (and the same is true of any one of them and the identity), then the Khintchine recurrence theorem fails, meaning that we can find a measure preserving system indexed by $G$ and a set $A$ of positive measure such that the set $\{g\in G:|A\cap T_{\phi_1(g)}^{-1}A\cap \dots\cap T_{\phi_4(g)}^{-1}A|\geq|A|^5-\epsilon\}$ is not syndetic. The result previously mentioned proves this when $G=\mathbb Z$.