— 1. Introduction —
In a previous post I used a coloring trick of Bergelson to deduce Brauer’s theorem from Szemeredi’s theorem. In this post I will provide two more applications of the coloring trick. To put it simply, the coloring trick allows one to deduce a coloring statement from the density version of a weaker statement. The deduction of Brauer’s theorem from Szemerédi’s theorem I presented in the earlier post illustrates this phenomenon: Szemerédi’s theorem is the density version of van der Waerden’s theorem, which is a coloring statement weaker than Brauer’s theorem.
The first example I will give is a proof of Schur’s theorem using a strong version of Poincaré’s recurrence theorem. This was first observed by Bergelson and was the first appearance of the coloring trick in the literature. We deduce not only Schur’s theorem that in any finite coloring of there exists one pair such that is monochromatic but that the set of such pairs is large.
The second example concerns the partition regularity of the equation . Here, the density statement we use is Sárkőzy’s theorem, which states that if has positive density, then there is a perfect square in the set .
In this post I will assume the reader is familiar with basic notions of upper and lower density in and . All the definitions and lemmas I will use are stated and proved in this section of my earlier post.
— 2. Schur’s theorem —
Schur’s theorem says that, for any finite coloring of , there are and such that . Bergelson showed that in fact there is some such that
Note that equation (1) implies Schur’s theorem. To deduce Schur’s theorem we will use the following density result. For we denote by the point , where the dimension will be clear on the context.
Since for all we conclude that
We now employ the coloring trick to deduce Schur’s theorem. Let and assume without loss of generality that the sets have positive upper density and the sets have upper density for some . Thus has upper density and has lower density .
We apply Theorem 1 to . Then the set has positive upper density and, in particular, . Let . Then there exists some such that , and . Let . Therefore and this finishes the proof.
— 3. Partition regularity of —
In this section I will use the coloring trick to deduce the following result. I will use the proof from this paper of Bergelson and McCutcheon (it’s theorem 0.4 there)
In fact, the proof I will present shows that for any polynomial which is divisible (this means that for every there is some such that is divisible by ) there exists such that .
The density result we will need is a stronger version of Sarkozy’s theorem. To state it we need the notion of IP set:
Definition 3 Given an increasing sequence of positive integers we denote by the set of finite sums of the sequence .
A set is an IP-set if it contains the finite sums of some increasing sequence.
The notion of IP-set is very useful for Ramsey theory due to the fact that the family of all IP-sets is partition regular. This is the content of Hindman’s theorem:
Theorem 4 (Hindman’s theorem) Let be an IP-set and let be a finite partition of . Then, for some the set is also an IP-set.
I have posted in this blog a proof of Hindman’s theorem using ultrafilters (see section 3 of that post). The original proof of Hindman was purely combinatorial and quite involved.
To make a parallel with the proof of Schur’s theorem above, the IP sets will replace the role of intersective sets. I plan to explore this in bigger depth in a future post.
The following density result is the analogue of the strong Poincaré recurrence theorem.
Theorem 5 (IP Sárkőzy’s theorem) Let have positive upper density and let be an IP-set. Then there exists some such that .
Finally we need a folklore lemma relating IP sets with positive density:
Proof: contains arbitrarily long intervals. Let be arbitrary, and let, inductively, be such that the interval . Then clearly the sum is in for every finite non-empty set .
We can now use the coloring trick to prove Theorem 2. Let be a finite coloring of . Assume without loss of generality that have positive upper density and have upper density, for some . Then has lower density . By Lemma 6 is an IP set. By Hindman’s theorem there exists such that is an IP set. By the IP Sarkozi’s theorem there exists such that has positive density, and hence it is non-empty. Finally, let and let . Then and .