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}.

Lemma 5 (Beiglböck Lemma) Let {G} be an amenable semigroup and let {A,B\subset G} be such that {d^*_L(A)>0} and {d^*_R(B)>0}. Then for some {p\in\beta G} we have

\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<j}. 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<j\leq m} 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: Piecewise syndetic sets, topological dynamics and ultrafilters | I Can't Believe It's Not Random!

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

  3. Pingback: A proof of the Erdős sumset conjecture | I Can't Believe It's Not Random!

  4. Pingback: Tao’s Proof of (logarithmically averaged) Chowla’s conjecture for two point correlations | I Can't Believe It's Not Random!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s