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

This entry was posted in Number Theory. Bookmark the permalink.

1 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 )

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