** — 1. Introduction — **

The Poincaré recurrence theorem (or, more accurately, its proof) implies that, given a set with positive upper Banach density, i.e.

then there exists some such that . In fact one gets that the set of those for which is “large” in many senses, in particular it is syndetic. Observe that, for some , if is non-empty, say , then both and so .

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

Theorem 1Let be subsets with positive Banach upper density , . Then the set is piecewise syndetic.

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

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 is denoted by . I defined and proved many properties of in this previous post.

** — 2. Some notation — **

We will work on a general countable amenable semigroup . 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 2Let be a semigroup, let and let .

- Define , and .
- Define and
- Define
- Define .
- A left Følner sequence on is a sequence of finite subsets of such that for each we have as .
- A right Følner sequence on is a sequence of finite subsets of such that for each we have as .
- The left Banach upper density of a subset is denoted by and is defined as the supremum over all left Følner sequences of the upper density
- The right Banach upper density of a subset is denoted by and is is defined as the supremum over all right Følner sequences of the upper density
- A subset is syndetic if there exists a finite set such that .
- A subset is (right) piecewise syndetic if there exists a syndetic set such that for each finite subset there is some shift such that .

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

Theorem 3Let be a countable amenable semigroup. Let be such that and . Then the set is (right) piecewise syndetic.

** — 3. Beiglbock’s Lemma — **

The idea of the proof is that if for some , the intersection has positive Banach density, then is syndetic, as we saw above. But then each point in is also in . Then is syndetic, and so also is syndetic. Now while it is not true in general that we can find such a (to see an example when just take some and such that is not syndetic) it turns out that a (rather relaxed) version of that is true, namely that the left Banach upper density of is positive for some ultrafilter .

To motivate what follows, let’s suppose for now that we were actually trying to prove that for some , the intersection has positive Banach density. The standard procedure would be to take a Cesaro average of the density . Let’s fix a left Følner sequence and a right Følner sequence such that and . We may try to take the Cesaro limit along since this left Følner sequence contains some information about . We get

Observe that , where the upper density is taken with respect to the right Følner sequence . Now if only we could interchange the limits, then we would get

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 . 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 to be the “model” for our measure. We will extend that density to an actual measure on the Stone-Cech compactification of .

To proceed with our discussion we need to define the expression . For an element we denote by the principal ultrafilter on associated with . We also denote by the closure of a set in , in other words is the set of all ultrafilters that contain .

Given two ultrafilters we denote by . In my earlier post mentioned above I showed that this operation defines an ultrafilter and is associative.

Definition 4Let and be an ultrafilter. We define

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

Lemma 5 (Beiglböck Lemma)Let be an amenable semigroup and let be such that and . Then for some we have

*Proof:* Let be a Følner sequence such that . Let be the set of bounded (complex valued) functions defined on and let be an invariant mean such that , for instance, take

where is non-principal.

Now we can identify the space with the space of continuous (complex valued) functions on , and then becomes a continuous linear functional on , and it is not hard to see that this is a positive functional. By the Riesz representation theorem there is some probability measure on such that . We will actually prove that

Now let be a Følner sequence on such that , and note that

Since (this can be easily checked by unwrapping the definitions) we can apply the Fatou’s lemma to obtain

where in the last step we used the invariance of .

** — 4. Proof of Jin’s Theorem — **

Now we can finish the proof of Jin’ Theorem. For completeness I will prove first that if has then is syndetic.

We proceed by contradiction. Assume that for each finite set there is some such that . Let be arbitrary and let . Construct, inductively for each the element such that and let . Choose large enough so that and denote by the product for . Note that and hence by assumption .

Observe that if then . By the pigeonhole principle, there is some such that the intersection is non-empty. Let be in that intersection. Then and also , hence . This is a contradiction which shows that is indeed syndetic.

Now, choosing such that has positive Banach upper density, note that the set contains which is syndetic.

We have by definition . Hence, for each finite set , the intersection

and in particular it is non-empty. Let be in that intersection, then , and this finishes the proof.

Pingback: Piecewise syndetic sets, topological dynamics and ultrafilters | I Can't Believe It's Not Random!

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

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