= Solution
The \b[<Szemerédi theorem>] says that for every integer $k\geq2$ and every $\delta>0$, there is $N_0(k,\delta)$ such that, for $N\geq N_0$, every $A\subseteq\{1,\ldots,N\}$ with $|A|\geq\delta N$ contains a nonconstant <arithmetic progression>
$$
\boxed{a,a+n,\ldots,a+(k-1)n\quad(n\geq1).}
$$
Equivalently, every subset of the positive integers with positive <upper asymptotic density> contains <arithmetic progressions> of every finite length. Length one is immediate.
The \b[<Furstenberg multiple recurrence theorem>] states that for every probability <measure-preserving system>, every measurable $B$ with $\mu(B)>0$, and every integer $k\geq2$, there is $n\geq1$ with
$$
\boxed{\mu\left(\bigcap_{j=0}^{k-1}T^{-jn}B\right)>0.}
$$
Here $T^{-jn}B$ means a preimage, so invertibility is unnecessary. The <Furstenberg multiple recurrence theorem> also does not assume an <ergodic transformation>.
We prove the implication to the finite <Szemerédi theorem> by constructing the <Furstenberg correspondence principle> explicitly. Suppose, to the contrary, that for fixed $k$ and $\delta>0$ there are $N_\ell\to\infty$ and $A_\ell\subseteq\{1,\ldots,N_\ell\}$ with $|A_\ell|\geq\delta N_\ell$, but with no length-$k$ <arithmetic progression> of positive <common difference>. In the binary <full shift> $\Omega=\{0,1\}^{\mathbb Z}$, encode $A_\ell$ as $x^{(\ell)}_j=\mathbf1_{A_\ell}(j)$, taking all coordinates outside $A_\ell$ to be zero. Let $S$ be the <left shift>, $(S\omega)_j=\omega_{j+1}$, and set
$$
C=\{\omega:\omega_0=1\},\qquad
\nu_\ell=\frac1{N_\ell}\sum_{a=1}^{N_\ell}\delta_{S^ax^{(\ell)}}.
$$
The <cylinder set> $C$ is a <clopen set>, and $\nu_\ell(C)=|A_\ell|/N_\ell\geq\delta$. The binary <full shift> is a <compact metric space>, so <compactness of probability measures on a compact metric space> gives a subsequence of these <empirical measures> with <weak convergence of probability measures> to a <Borel probability measure> $\nu$.
For every continuous $h$ on the <full shift>,
$$
\int(h\circ S-h)\,d\nu_\ell
=\frac{h(S^{N_\ell+1}x^{(\ell)})-h(Sx^{(\ell)})}{N_\ell}\longrightarrow0.
$$
Passing to the weak limit shows that $\nu$ is an <invariant measure> for the continuous <left shift>. Thus $(\Omega,\mathcal B,\nu,S)$ is a probability <measure-preserving system>. Since the <indicator function> of $C$ is continuous, $\nu(C)\geq\delta$.
Apply the <Furstenberg multiple recurrence theorem> to $C$. For some $n\geq1$, the <clopen set>
$$
D=\bigcap_{j=0}^{k-1}S^{-jn}C
$$
has $\nu(D)>0$. Its continuous <indicator function> gives $\nu_\ell(D)\to\nu(D)>0$. For large $\ell$, at least one $S^ax^{(\ell)}$ in the defining <empirical measure> therefore belongs to $D$. The choice of <left shift> implies
$$
x^{(\ell)}_{a+jn}=1\quad(0\leq j<k),
$$
so $a,a+n,\ldots,a+(k-1)n$ lies in $A_\ell$. This contradicts the assumed absence of <arithmetic progressions> and proves the finite <Szemerédi theorem>. Applying the finite <Szemerédi theorem> on intervals where an infinite set has density bounded below proves the stated <upper asymptotic density> formulation.
For \b[<multiple recurrence for circle rotations>], write $\mathbb T=\mathbb R/\mathbb Z$ and $R_\alpha x=x+\alpha$, with normalized <Lebesgue measure> $m$, which is the <Haar measure> of the <circle group>. Fix a measurable $B\subseteq\mathbb T$ with $m(B)>0$ and $k\geq2$. If $\alpha$ is rational, there is $q\geq1$ with $R_\alpha^q$ the identity, and $n=q$ gives an intersection of measure $m(B)$.
For irrational $\alpha$, the <pigeonhole principle> applied to $0,\alpha,\ldots,Q\alpha$ in $Q$ equal arcs gives $1\leq n\leq Q$ with $\|n\alpha\|_{\mathbb T}\leq1/Q$. In particular there are arbitrarily small nonzero returns to zero for the <irrational rotation of the circle>.
We also need <translation continuity in L1 on the circle>. Given a measurable $B$, approximate its <indicator function> in the <L1 norm> by a continuous $g$ on the <circle group>. Such approximation follows from regularity of <Lebesgue measure>, or approximation by finite unions of intervals. Translation invariance and <uniform continuity> give
$$
\|\mathbf1_B(\cdot+t)-\mathbf1_B\|_1
\leq2\|\mathbf1_B-g\|_1+\|g(\cdot+t)-g\|_1
\longrightarrow0\quad(t\to0),
$$
where the approximation error is first made arbitrarily small. Equivalently, $m(B\mathbin\triangle(B-t))\to0$.
Choose a return time $n\geq1$ so small modulo one that for each $1\leq j<k$,
$$
m(B\mathbin\triangle R_\alpha^{-jn}B)<\frac{m(B)}{2(k-1)}.
$$
This is possible because multiplication by each fixed $j$ is continuous on the <circle group> and <translation continuity in L1 on the circle> applies to the finitely many translates. The <union bound> now gives
$$
\boxed{m\left(\bigcap_{j=0}^{k-1}R_\alpha^{-jn}B\right)
\geq m(B)-\sum_{j=1}^{k-1}m(B\setminus R_\alpha^{-jn}B)
>\frac{m(B)}2>0.}
$$
This proves the <Furstenberg multiple recurrence theorem> for every circle rotation with its normalized <Lebesgue measure>, including both rational and irrational angles.
Back to article page
