Applications of the coloring trick

— 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 {{\mathbb N}} there exists one pair {(x,y)} such that {\{x,y,x+y\}} is monochromatic - but that the set of such pairs is large.

The second example concerns the partition regularity of the equation {x-y=z^2}. Here, the density statement we use is Sárkőzy’s theorem, which states that if {A\subset{\mathbb N}} has positive density, then there is a perfect square in the set {A-A}.

In this post I will assume the reader is familiar with basic notions of upper and lower density in {{\mathbb N}} and {{\mathbb N}^t}. 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 {{\mathbb N}=C_1\cup\dots\cup C_r} of {{\mathbb N}}, there are {x,y\in{\mathbb N}} and {i\in\{1,\dots,r\}} such that {\{x,y,x+y\}\subset C_i}. Bergelson showed that in fact there is some {i\in\{1,\dots,r\}} such that

\displaystyle  \bar d\Big(\Big\{x\in C_i:\bar d\big(\big\{y\in C_i:x+y\in C_i\big\}\big)>0\Big\}\Big)>0 \ \ \ \ \ (1)

Note that equation (1) implies Schur’s theorem. To deduce Schur’s theorem we will use the following density result. For {n\in{\mathbb N}} we denote by {{\bf n}} the point {(n,n,\dots,n)\in{\mathbb N}^d}, where the dimension {d} will be clear on the context.

Theorem 1 (Strong Poincaré recurrence for {{\mathbb N}^d}) Let {d\in{\mathbb N}} and let {A\subset{\mathbb N}^d} be a set with positive density. Then the set {\Big\{n\in{\mathbb N}:\bar d\big((A-{\bf n})\cap A\big)>0\Big\}} has positive upper density.

Proof: By Furstenberg’s correspondence principle and the mean ergodic theorem we have that

\displaystyle \limsup_{N\rightarrow\infty}\frac1N\sum_{n\in[N]}\bar d\big((A-{\bf n})\cap A\big)>0

Since {\bar d\big((A-{\bf n})\cap A\big)\leq1} for all {n\in{\mathbb N}} we conclude that

\displaystyle \bar d\Big(\Big\{n\in{\mathbb N}:\bar d\big((A-{\bf n})\cap A\big)>0\Big\}\Big)=\limsup_{N\rightarrow\infty}\frac{\Big|\Big\{n\in[N]:\bar d\big((A-{\bf n})\cap A\big)>0\Big\}\Big|}N>0


We now employ the coloring trick to deduce Schur’s theorem. Let {{\mathbb N}=C_1\cup\dots\cup C_r} and assume without loss of generality that the sets {C_1,\dots,C_d} have positive upper density and the sets {C_{d+1},\dots,C_r} have {0} upper density for some {d\in\{1,\dots,r\}}. Thus {A_0=C_{d+1}\cup\dots\cup C_r} has upper density {0} and {A_1:=C_1\cup\dots\cup C_d={\mathbb N}\setminus C_0} has lower density {1}.

We apply Theorem 1 to {A=C_1\times\dots\times C_d\subset{\mathbb N}^d}. Then the set {B:=\{n\in{\mathbb N}:(A-{\bf n})\cap A\neq\emptyset\}} has positive upper density and, in particular, {\bar d(B\cap A_1)>0}. Let {n\in C\cap A_1}. Then there exists some {i\in\{1,\dots,d\}} such that {n\in C_i}, and {\bar d\big((C_i-n)\cap C_i\big)>0}. Let {m\in(C_i-n)\cap C_i}. Therefore {\{n,m,n+m\}\subset C_i} and this finishes the proof.

— 3. Partition regularity of {x-y=z^2}

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)

Theorem 2 Let {{\mathbb N}=C_1\cup\dots\cup C_r} be a finite coloring of {{\mathbb N}}. Then there exists {i\in\{1,\dots,r\}} and {x,y,z\in C_i} such that {x-y=z^2}.

In fact, the proof I will present shows that for any polynomial {f\in{\mathbb Z}[x]} which is divisible (this means that for every {k\in{\mathbb N}} there is some {x\in {\mathbb Z}} such that {f(x)} is divisible by {k}) there exists {x,y,z\in C_i} such that {x-y=f(z)}.

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 {(x_n)} of positive integers we denote by {FS(x_n)} the set of finite sums of the sequence {(x_n)}.

\displaystyle FS(x_n):=\left\{\sum_{n\in S}x_n:S\subset{\mathbb N},0<|S|<\infty\right\}

A set {A\subset{\mathbb N}} is an IP-set if it contains the finite sums {FS(x_n)} 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 {A} be an IP-set and let {A=A_1\cup\dots\cup A_r} be a finite partition of {A}. Then, for some {i\in\{1,\dots,r\}} the set {A_i} 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 {A\subset{\mathbb N}} have positive upper density and let {B} be an IP-set. Then there exists some {n\in B} such that {\bar d\big(A\cap(A-n^2)\big)>0}.

This is a particular case of the polynomial IP-Szemerédi theorem that I wrote about before in this blog.

Finally we need a folklore lemma relating IP sets with positive density:

Lemma 6 Let {A\subset{\mathbb N}} have lower density {1}. Then {A} is an IP set.

Proof: {A} contains arbitrarily long intervals. Let {x_1\in A} be arbitrary, and let, inductively, {x_n\in{\mathbb N}} be such that the interval {[x_n,x_1+\dots+x_n]\subset A}. Then clearly the sum {\sum_{s\in S}x_s} is in {A} for every finite non-empty set {S\subset{\mathbb N}}. \Box

We can now use the coloring trick to prove Theorem 2. Let {{\mathbb N}=C_1\cup\dots\cup C_r} be a finite coloring of {{\mathbb N}}. Assume without loss of generality that {C_1,\dots,C_d} have positive upper density and {C_{d+1},\dots,C_r} have {0} upper density, for some {d\in\{1,\dots,r\}}. Then {A=C_1\cup\dots\cup C_d} has lower density {1}. By Lemma 6 {A} is an IP set. By Hindman’s theorem there exists {i\in\{1,\dots,d\}} such that {C_i} is an IP set. By the IP Sarkozi’s theorem there exists {z\in C_i} such that {C_i\cap(C_i-z^2)} has positive density, and hence it is non-empty. Finally, let {y\in C_i\cap(C_i-z^2)} and let {x=y+z^2}. Then {\{x,y,z\}\subset C_i} and {x-y=z^2}.


About Joel Moreira

PhD Student at OSU in Mathematics. I'm portuguese.
This entry was posted in Number Theory. Bookmark the permalink.

One Response to Applications of the coloring trick

  1. Pingback: New polynomial and multidimensional extensions of classical partition results | I Can't Believe It's Not Random!

Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s