Posted by: yglima | January 16, 2010

## ERT5: Furstenberg Correspondence Principle

From now on, instead of upper density, we will consider upper Banach density. This notion reflects better the the asymptotic behavior of the set. For example, the union of intervals ${[n^2,n^2+n]}$, ${n\ge 1}$, has zero upper density, but has a rich combinatorics.

Definition 1 The upper Banach density of a set ${E\subset{\mathbb Z}}$ is$\displaystyle {\rm d}^*(E)=\limsup_{M-N\rightarrow+\infty}\dfrac{\left|E\cap\{N,\ldots,M\}\right|}{M-N+1}\,\cdot$

Note that ${{\rm d}^*(E)\ge \overline {\rm d}(E)}$, which will reveal to be good for our applications.

In the previous posts, we developed some machinery in Ergodic Theory and now we will relate them to combinatorics. The main tool is a correspondence principle due to Furstenberg. Before discussing it, let us restate a theorem of the last post.

Theorem 2 (Furstenberg) If ${(X,\mathcal B,\mu,T)}$ is a mps, ${A\in\mathcal B}$ such that ${\mu(A)>0}$ and ${k}$ is a positive integer, then there exists a positive integer ${n}$ such that $\displaystyle \mu\left(A\cap T^{-n}A\cap T^{-2n}A\cap\cdots\cap T^{-kn}A\right)>0\,. \ \ \ \ \ (1)$

This is the main result of Furstenberg’s 1977 paper and was used to prove Szemerédi Theorem.

Theorem 3 (Szemerédi, 1975) If ${E\subset{\mathbb Z}}$ has positive upper Banach density, then it contains arbitrarily large arithmetic progressions.

1. Furstenberg Correspondence Principle

The question is: given such set ${E}$, how to create a mps ${(X,\mathcal B,\mu,T)}$ somehow related to ${E}$?

Theorem 4 (Furstenberg Correspondence Principle) Given a subset ${E\subset{\mathbb Z}}$ of positive upper Banach density, there exist a mps ${(X,\mathcal B,\mu,T)}$ and a set ${A\in\mathcal B}$ such that ${\mu(A)={\rm d}^*(E)}$ and$\displaystyle {\rm d}^*\left(E\cap(E-n_1)\cap\cdots\cap(E-n_k)\right)\ge\mu(A\cap T^{-n_1}A\cap\cdots\cap T^{-n_k}A)$

for any integers ${n_1,\ldots,n_k}$.

Theorems 2 and 4 prove Theorem 3: note that the arithmetic progression ${a,a+n,\ldots,a+nk}$ belongs to ${E}$ if and only if ${a\in E\cap(E-n)\cap\cdots\cap(E-nk)}$. So, positive denseness of the set ${E\cap(E-n)\cap\cdots\cap(E-nk)}$, in particular, proves its non-emptyness. Apply Theorem 2 to the mps obtained by Theorem 4: given ${k}$, there exists ${n}$ such that

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

and then

$\displaystyle {\rm d}^*\left(E\cap(E-n)\cap\cdots\cap(E-nk)\right)>0\,.$

As ${k}$ is arbitrary, Szemerédi Theorem is established.

The upper Banach density gives the same weight to all integers. It might happen (altough I still did not find any examples) that a set might have positive density if some subsets of ${{\mathbb Z}}$ are heavier than others. For example, if we give no weight to the even numbers, then the odd numbers have density one. In this post, I will give a general version of the correspondence principle. It follows the same ideas of the original proof of Theorem 4. I hope this extension, in addition of proving the classical correspondence principle, give rise to new applications of Theorem 2 for some classes of sets of zero upper Banach density that are big in some other sense.

2. A general correspondence principle

Consider a sequence of non-negative real numbers ${(a_n)_{n\in{\mathbb Z}}}$ such that $\displaystyle \dfrac{a_N+a_M+\sum_{n=N}^{M-1}|a_{n+1}-a_n|}{\sum_{n=N}^{M}a_n}\longrightarrow 0\ \text{ as }M-N\rightarrow+\infty\,. \ \ \ \ \ (2)$

For example, every constant sequence satisfies this condition. Given a set ${E\subset{\mathbb Z}}$, define the upper Banach density with respect to ${(a_n)}$ as:

$\displaystyle {\rm d}^*(E)=\limsup_{M-N\rightarrow+\infty}\dfrac{a_N\cdot\delta_N(E)+\cdots+a_M\cdot\delta_{M}(E)}{a_N+\cdots+a_M}\,,$

where ${\delta_n}$ stands for the usual Dirac measure. This density is a well defined number between ${0}$ and ${1}$. We will prove the following

Theorem 5 If ${E\subset{\mathbb Z}}$ satisfies ${{\rm d}^*(E)>0}$, then there exist a mps ${(X,\mathcal B,\mu,T)}$ and a set ${A\in\mathcal B}$ such that ${\mu(A)={\rm d}^*(E)}$ and $\displaystyle {\rm d}^*\left((E-n_1)\cap\cdots\cap(E-n_t)\right)\ge\mu\left(T^{-n_1}A\cap\cdots\cap T^{-n_t}A\right), \ \ \ \ \ (3)$

for every ${n_1,\ldots,n_t\in{\mathbb Z}}$.

Proof: We consider the most natural system: the set of characteristic functions of sets of integers.

$X=\{0,1\}^{\mathbb Z}\ \ ,\ \ \mathcal B=\sigma-\text{algebra generated by the cylinders}.$

The dynamics considered is the bilateral shift ${T:X\rightarrow X}$ defined by

$\displaystyle T(\ldots,x_0;x_1,x_2,\ldots)=(\ldots,x_1;x_2,\ldots)\,.$

We apply a Krylov-Bogolubov argument to create a ${T}$-invariant measure ${\mu}$. Take ${\underline x=\chi_E\in X}$, that is, ${\underline x=(\ldots,x_{-1},x_0;x_1,\ldots)}$ with ${x_n=\delta_n(E)}$.

Let ${(N_k)_{k\in{\mathbb Z}}}$, ${(M_k)_{k\in{\mathbb Z}}}$ be sequences of integers for which

$\displaystyle {\rm d}^*(E)=\lim_{k\rightarrow+\infty}\dfrac{a_{N_k}\cdot\delta_{N_k}(E)+\cdots+a_{M_k}\cdot\delta_{M_k}(E)}{a_{N_k}+\cdots+a_{M_k}}\,\cdot$

We may assume (restricting ${(N_k)}$, ${(M_k)}$ to subsequences, if necessary) that the probabilities ${(\mu_k)_{k\in{\mathbb Z}}}$ defined by

$\displaystyle \mu_k=\dfrac{a_{N_k}\cdot\delta_{T^{N_k}\underline x}+\cdots+a_{M_k}\cdot\delta_{T^{M_k}\underline x}}{a_{N_k}+\cdots+a_{M_k}}$

converge in the weak-${*}$ topology to a probability ${\mu}$, that is,

$\displaystyle\int_X fd\mu_k\longrightarrow \int_X fd\mu$

for every continuous  $f:X\rightarrow{\mathbb R}$. Under the assumption (2), ${\mu}$ is ${T}$-invariant. In fact,

$\displaystyle T_*\mu_k=\dfrac{a_{N_k}\cdot\delta_{T^{N_k+1}\underline x}+\cdots+a_{M_k}\cdot\delta_{T^{M_k+1}\underline x}}{a_{N_k}+\cdots+a_{M_k}}$

and so

$\displaystyle T_*\mu_k-\mu_k=\dfrac{1}{\displaystyle\sum_{n=N_k}^{M_k}a_n} \left(a_{M_k}\delta_{T^{M_k+1}\underline x}-a_{N_k}\delta_{T^{N_k}\underline x}- \displaystyle\sum_{n=N_k}^{M_k-1}(a_{n+1}-a_n)\delta_{T^{n+1}\underline x}\right),$

implying that

$|T_*\mu_k-\mu_k|\leq\dfrac{a_{N_k}+a_{M_k}+\displaystyle\sum_{n=N_k}^{M_k-1}|a_{n+1}-a_n|} {\displaystyle\sum_{n=N_k}^{M_k}a_n}$

which, by hypothesis, converges to zero as ${k\rightarrow+\infty}$. Good: we have our probability space!

Continue the construction taking ${A=\{(\ldots,x_{-1},x_0;x_1,\ldots)\in X\,;\,x_0=1\}}$. Then

$\displaystyle \begin{array}{rcl} \delta_{T^n\underline x}(A)=1&\iff& (T^n\underline x)_0=1\\ &\iff& x_n=1\\ &\iff& n\in E\\ &\iff& \delta_n(E)=1,\\ \end{array}$

that is,

$\displaystyle \delta_{T^n\underline x}(A)=\delta_n(E).$

This is the connection between ${A}$ and ${E}$ we were looking for. It implies that

$\displaystyle \begin{array}{rcl} \mu_k(A)&=&\dfrac{a_{N_k}\cdot\delta_{T^{N_k}\underline x}(A)+\cdots+a_{M_k}\cdot\delta_{T^{M_k}\underline x}(A)}{a_{N_k}+\cdots+a_{M_k}}\\ &&\\ &=&\dfrac{a_{N_k}\cdot\delta_{N_k}(E)+\cdots+a_{M_k}\cdot\delta_{M_k}(E)}{a_{N_k}+\cdots+a_{M_k}} \end{array}$

and, as ${A}$ is a clopen set (all cylinders are clopen),

$\displaystyle \mu(A)=\lim_{k\rightarrow+\infty}\mu_k(A)={\rm d}^*(E).$

It remains to verify (3), which actually follows from the last argument:

$\displaystyle \begin{array}{rcl} \delta_{T^n\underline x}\left(T^{-n_1}A\cap\cdots\cap T^{-n_t}A\right)&=&1\\ \iff\hspace{5cm}T^n\underline x&\in&T^{-n_1}A\cap\cdots\cap T^{-n_t}A\\ \iff\hspace{2.3cm}T^{n+n_1}\underline x,\ldots,T^{n+n_t}\underline x&\in& A\\ \iff\hspace{2.9cm}x_{n+n_1},\ldots,x_{n+n_t}&=&1\\ \iff\hspace{2.6cm}n+n_1,\ldots,n+n_t&\in& E\\ \iff\hspace{5.6cm}n&\in& (E-n_1)\cap\cdots\cap(E-n_t) \end{array}$

and then

$\displaystyle {\rm d}^*\left((E-n_1)\cap\cdots\cap(E-n_t)\right)\ge\mu\left(T^{-n_1}A\cap\cdots\cap T^{-n_t}A\right).$

This concludes the proof. $\Box$

It is established the connection between combinatorics of sets of integers and ergodic theory.

Previous posts: ERT0, ERT1, ERT2, ERT3, ERT4.