## Jin’s Theorem

— 1. Introduction —

The Poincaré recurrence theorem (or, more accurately, its proof) implies that, given a set ${A\subset{\mathbb Z}}$ with positive upper Banach density, i.e.

$\displaystyle d^*(A):=\limsup_{N\rightarrow\infty}\sup_{M\in{\mathbb Z}}\frac{|A\cap[M,M+N]|}{N+1}>0$

then there exists some ${n\in{\mathbb Z}}$ such that ${d^*[A\cap(A-n)]>0}$. In fact one gets that the set of those ${n\in{\mathbb Z}}$ for which ${d^*[A\cap(A-n)]>0}$ is “large” in many senses, in particular it is syndetic. Observe that, for some ${n\in{\mathbb Z}}$, if ${A\cap(A-n)}$ is non-empty, say ${a\in A\cap(A-n)}$, then both ${a,a+n\in A}$ and so ${n\in A-A=\{a-b:a,b\in A\}}$.

We just concluded that if ${d^*(A)>0}$ then ${A-A}$ is syndetic. Now a natural question is whether a similar phenomenon happens for the difference ${A-B}$ when both ${A}$ and ${B}$ have positive Banach upper density. The answer (or better, one answer) is provided by Jin’s theorem:

Theorem 1 Let ${A,B\subset{\mathbb Z}}$ be subsets with positive Banach upper density ${d^*(A)>0}$, ${d^*(B)>0}$. Then the set ${A-B=\{a-b:a\in A,b\in B\}}$ is piecewise syndetic.

It is not hard to find an example of ${A}$ and ${B}$ with Banach upper density ${1}$ and such that ${A-B}$ is not syndetic, for instance take ${A}$ and ${B}$ to be the union of very distant intervals:

$\displaystyle A=\bigcup_{n=1}^\infty [(2n)!-n,(2n)!+n];\qquad\qquad B=\bigcup_{n=1}^\infty[(2n+1)!-n,(2n+1)!+n]$

In this post I will present a short proof of this result due to Beiglböck, which generalizes for any amenable semigroup. This proof makes a nice use of some properties of ultrafilters. The set of all ultrafilters on a discrete set ${G}$ is denoted by ${\beta G}$. I defined and proved many properties of ${\beta G}$ in this previous post.

— 2. Some notation —

We will work on a general countable amenable semigroup ${G}$. In this (possibly) non-commutative setting one has to distinguish between left and right invariant density. In the next definition we summarize some standard notation and terminology:

Definition 2 Let ${G}$ be a semigroup, let ${A,B\subset G}$ and let ${x\in G}$.

• Define ${xA:=\{xa:a\in A\}}$, ${Ax:=\{ax:a\in A\}}$ and ${AB:=\{ab:a\in A,b\in B\}}$.
• Define ${x\backslash A:=\{y\in G:xy\in A\}}$ and ${A/x:=\{y\in G:yx\in A\}}$
• Define ${\displaystyle B\backslash A:=\{x\in G:bx\in A\text{ for some }b\in B\}=\bigcup_{b\in B}b\backslash A}$
• Define ${\displaystyle A/B:=\{x\in G:xb\in A\text{ for some }b\in B\}=\bigcup_{b\in B}A/b}$.
• A left Følner sequence on ${G}$ is a sequence ${\{F_N\}}$ of finite subsets of ${G}$ such that for each ${x\in G}$ we have ${|xF_N\cap F_N|/|F_N|\rightarrow1}$ as ${N\rightarrow\infty}$.
• A right Følner sequence on ${G}$ is a sequence ${\{F_N\}}$ of finite subsets of ${G}$ such that for each ${x\in G}$ we have ${|F_Nx\cap F_N|/|F_N|\rightarrow1}$ as ${N\rightarrow\infty}$.
• The left Banach upper density of a subset ${A\subset G}$ is denoted by ${d_L^*(A)}$ and is defined as the supremum over all left Følner sequences of the upper density

$\displaystyle \bar d(A)=\limsup_{N\rightarrow\infty}\frac{|A\cap F_N|}{|F_N|}$

• The right Banach upper density of a subset ${A\subset G}$ is denoted by ${d_R^*(A)}$ and is is defined as the supremum over all right Følner sequences of the upper density

$\displaystyle \bar d(A)=\limsup_{N\rightarrow\infty}\frac{|A\cap F_N|}{|F_N|}$

• A subset ${A\subset G}$ is syndetic if there exists a finite set ${F\subset G}$ such that ${G=A/F}$.
• A subset ${A\subset G}$ is (right) piecewise syndetic if there exists a syndetic set ${B}$ such that for each finite subset ${F\subset B}$ there is some shift ${n\in G}$ such that ${nF\subset A}$.

We can now formulate the general version of Jin’s Theorem (for amenable semigroups):

Theorem 3 Let ${G}$ be a countable amenable semigroup. Let ${A,B\subset G}$ be such that ${d_L^*(A)>0}$ and ${d_R^*(B)>0}$. Then the set ${B/A}$ is (right) piecewise syndetic.

— 3. Beiglbock’s Lemma —

The idea of the proof is that if for some ${k\in G}$, the intersection ${C:=A\cap(k\backslash B)}$ has positive Banach density, then ${C/C}$ is syndetic, as we saw above. But then each point in ${C/C}$ is also in ${(k\backslash B)/A=k\backslash (B/A)}$. Then ${k\backslash (B/A)}$ is syndetic, and so also ${B/A}$ is syndetic. Now while it is not true in general that we can find such a ${k\in G}$ (to see an example when ${G={\mathbb Z}}$ just take some ${A}$ and ${B}$ such that ${A-B}$ is not syndetic) it turns out that a (rather relaxed) version of that is true, namely that the left Banach upper density of ${A\cap(p\backslash B)}$ is positive for some ultrafilter ${p\in\beta{\mathbb Z}}$.

To motivate what follows, let’s suppose for now that we were actually trying to prove that for some ${k\in G}$, the intersection ${C:=A\cap(k\backslash B)}$ has positive Banach density. The standard procedure would be to take a Cesaro average of the density ${d^*_L(A\cap(k\backslash B)}$. Let’s fix a left Følner sequence ${\{I_N\}}$ and a right Følner sequence ${\{F_N\}}$ such that ${d^*_L(A)=\lim_{N\rightarrow\infty}|A\cap I_N|/|I_N|}$ and ${d^*_R(B)=\lim_{N\rightarrow\infty}|B\cap F_N|/|F_N|}$. We may try to take the Cesaro limit along ${\{F_N\}}$ since this left Følner sequence contains some information about ${B}$. We get

$\displaystyle \begin{array}{rcl} \displaystyle\limsup_{N\rightarrow\infty}\frac1{|F_N|}\sum_{k\in F_N}d_L^*[A\cap(k\backslash B)]&\geq&\displaystyle\limsup_{N\rightarrow\infty}\frac1{|F_N|}\sum_{k\in F_N}\limsup_{M\rightarrow\infty}\frac{|A\cap(k\backslash B)\cap I_M|}{|I_M|}\\&=& \displaystyle\limsup_{N\rightarrow\infty}\limsup_{M\rightarrow\infty}\frac1{|F_N|.|I_M|}\sum_{n\in A\cap I_M}\sum_{k\in F_N}1_{k\backslash B}(n)\\&=& \displaystyle\limsup_{N\rightarrow\infty}\limsup_{M\rightarrow\infty}\frac1{|F_N|.|I_M|}\sum_{n\in A\cap I_M}\sum_{k\in F_N}1_{B/n}(k)\\&=& \displaystyle\limsup_{N\rightarrow\infty}\limsup_{M\rightarrow\infty}\frac1{|I_M|}\sum_{n\in A\cap I_M}\frac{|B/n\cap F_N|}{|F_N|} \end{array}$

Observe that ${\bar d(B)=\bar d(B/n)}$, where the upper density is taken with respect to the right Følner sequence ${\{F_N\}}$. Now if only we could interchange the limits, then we would get

$\displaystyle \limsup_{N\rightarrow\infty}\frac1{|F_N|}d_L^*[A\cap(k\backslash B)]\geq\limsup_{M\rightarrow\infty}\frac{|A\cap I_M|}{|I_M|}d^*_R(B)=d^*_L(A)d^*_R(B)>0$

Note that we only cheated by changing the order of limits (which is, of course, no small cheat). While at first this seems a hopeless approach, there is a way to use most of this argument (and that is Beiglböck’s lemma below). The trick is to use a standard way to interchange limits, in this case we will use Fatou’s lemma. Since upper density is not a measure, the direct application fails, to overcome this we need to define a measure in a way that replicates most properties of ${d^*}$. Also note that, since Fatou’s lemma only gives an inequality (and only one direction would interest us) we want to make the density along ${\{F_N\}}$ to be the “model” for our measure. We will extend that density to an actual measure on the Stone-Cech compactification of ${G}$.

To proceed with our discussion we need to define the expression ${p\backslash B}$. For an element ${n\in G}$ we denote by ${\tilde n}$ the principal ultrafilter on ${\beta G}$ associated with ${n}$. We also denote by ${\bar B}$ the closure of a set ${B\subset G}$ in ${\beta G}$, in other words ${\bar B}$ is the set of all ultrafilters that contain ${B}$.

Given two ultrafilters ${p,q\in\beta G}$ we denote by ${p.q=\{A:\{n:A/n\in p\}\in q\}}$. In my earlier post mentioned above I showed that this operation defines an ultrafilter and is associative.

Definition 4 Let ${B\subset G}$ and ${p\in\beta G}$ be an ultrafilter. We define

$\displaystyle p\backslash B:=\{n\in G:B/n\in p\}=\{n\in G:p.\tilde n\in\bar B\}$

The second equality in the definition is easy to check just by unwrapping the definitions and should be compared with the definition for ${n\backslash B}$ (with ${n\in G}$). We will not need that second characterization of ${p\backslash B}$ but it may help to give intuition on why it’s defined that way. Also note that ${n\backslash B=\tilde n\backslash B}$.

$\displaystyle d^*_L[A\cap(p\backslash B)]>d^*(A)d^*(B)$

Proof: Let ${\{F_N\}}$ be a Følner sequence such that ${d^*(B)=\lim_{N\rightarrow\infty}|B\cap F_N|/|F_N|}$. Let ${B(G)}$ be the set of bounded (complex valued) functions defined on ${G}$ and let ${\lambda:B(G)\rightarrow{\mathbb C}}$ be an invariant mean such that ${\lambda(1_B)=d^*(B)}$, for instance, take

$\displaystyle \lambda(f)=\lim_{N\rightarrow p}\left(\frac1{|F_N|}\sum_{n\in F_N}f(n)\right)$

where ${p\in\beta{\mathbb N}}$ is non-principal.

Now we can identify the space ${B(G)}$ with the space ${C(\beta G)}$ of continuous (complex valued) functions on ${\beta G}$, and then ${\lambda}$ becomes a continuous linear functional on ${C(\beta G)}$, and it is not hard to see that this is a positive functional. By the Riesz representation theorem there is some probability measure ${\mu}$ on ${\beta G}$ such that ${\lambda(f)=\int_{\beta G}fd\mu}$. We will actually prove that

$\displaystyle \int_{\beta G}d^*[A\cap(p\backslash B)]d\mu(p)>d^*(A)d^*(B)$

Now let ${\{I_N\}}$ be a Følner sequence on ${G}$ such that ${d^*(A)=\lim_{N\rightarrow\infty}|A\cap I_N|/|I_N|}$, and note that

$\displaystyle d^*[A\cap(p\backslash B)]\geq\limsup_{N\rightarrow\infty}\frac{|A\cap(p\backslash B)\cap I_N|}{|I_N|}=\limsup_{N\rightarrow\infty}\frac1{|I_N|}\sum_{n\in I_N\cap A}1_{p\backslash B}(n)$

Since ${1_{p\backslash B}(n)=1_{\overline{B/n}}(p)}$ (this can be easily checked by unwrapping the definitions) we can apply the Fatou’s lemma to obtain

$\displaystyle \begin{array}{rcl} \displaystyle\int_{\beta G}d^*[A\cap(p\backslash B)]d\mu(p)&\geq&\displaystyle\int_{\beta G}\limsup_{N\rightarrow\infty}\frac1{|I_N|}\sum_{n\in I_N\cap A}1_{\overline{B/n}}(p)d\mu(p)\\&\geq&\displaystyle\limsup_{N\rightarrow\infty}\frac1{|I_N|}\sum_{n\in I_N\cap A}\int_{\beta G}1_{\overline{B/n}}(p)d\mu(p)\\&=&\displaystyle\limsup_{N\rightarrow\infty}\frac1{|I_N|}\sum_{n\in I_N\cap A}\lambda(1_{\overline{B/n}})\\&=&\displaystyle d^*(A)d^*(B)\end{array}$

where in the last step we used the invariance of ${\lambda}$. $\Box$

— 4. Proof of Jin’s Theorem —

Now we can finish the proof of Jin’ Theorem. For completeness I will prove first that if ${C\subset G}$ has ${d^*_L(C)>0}$ then ${S:=C/C}$ is syndetic.

We proceed by contradiction. Assume that for each finite set ${F\subset G}$ there is some ${n=n(F)\in G}$ such that ${nF\cap S=\emptyset}$. Let ${x_1\in G\setminus S}$ be arbitrary and let ${F_1=\{x_1\}}$. Construct, inductively for each ${k=2,3,...}$ the element ${x_k\in G\setminus S}$ such that ${x_kF_{k-1}\cap S=\emptyset}$ and let ${F_k=F_{k-1}\cup x_kF_{k-1}}$. Choose ${m\in{\mathbb N}}$ large enough so that ${m.d^*_L(C)>1}$ and denote by ${x_{i,j}}$ the product ${x_jx_{j-1}...x_{i+2}x_{i+1}}$ for ${i. Note that ${x_{i,j}\in F_j}$ and hence by assumption ${x_{i,j}\notin S}$.

Observe that if ${x\in G}$ then ${d^*_L(x\backslash C)=d^*_L(C)}$. By the pigeonhole principle, there is some ${1\leq i such that the intersection ${(x_{0,i}\backslash C)\cap (x_{0,j}\backslash C)}$ is non-empty. Let ${a}$ be in that intersection. Then ${x_{0,i}a\in C}$ and also ${x_{0,j}a=x_{i,j}x_{0,i}a\in C}$, hence ${x_{i,j}\in C/C=S}$. This is a contradiction which shows that ${S}$ is indeed syndetic.

Now, choosing ${p\in\beta G}$ such that ${C=A\cap(p\backslash B)}$ has positive Banach upper density, note that the set ${p\backslash (B/A)\supset (p\backslash B)/A}$ contains ${C/C}$ which is syndetic.

We have by definition ${x\in p\backslash(B/A)\iff (B/A)/x\in p}$. Hence, for each finite set ${F\subset p\backslash(B/A)}$, the intersection

$\displaystyle \bigcap_{x\in F}(B/A)/x\in p$

and in particular it is non-empty. Let ${y}$ be in that intersection, then ${yF\subset B/A}$, and this finishes the proof.

This entry was posted in Combinatorics, Ergodic Theory, Ramsey Theory and tagged , , , , , , . Bookmark the permalink.

### 4 Responses to Jin’s Theorem

1. Pingback: I Can't Believe It's Not Random!