## 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$

$\Box$

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