Brauer’s theorem and a coloring trick of Bergelson

— 1. Introduction —

Ramsey theory concerns essentially two types of results: coloring and density results. Coloring results state that given a finite partition of some structured set (usually {{\mathbb N}}) one of the cells in the partition still has some sort of structure. Density results state that a subset of some structured set with positive density has some sort of structure itself. Instead of trying to give a precise definition of what I mean by coloring or density results, I will instead list some examples of both. Coloring results include

Examples of density results are

Since in any finite coloring of a structure, one of the cells has positive density, one can use density results to deduce coloring results. For instance Szemeredi’s theorem implies directly van der Waerden’s theorem and density Halles-Jewett’s theorem directly implies Halles-Jewett’s theorem. On the other hand, the coloring results do not imply density results. For instance, there is no density version of Schur’s theorem (which asserts that in a finite coloring of {{\mathbb N}} there are {x,y,z} of the same color such that {x+y=z}) since the odd numbers have density {1/2} but contain no solution to {x+y=z}. Moreover, even when restricted to shift invariant configurations (such as arithmetic progressions) there are coloring results whose density counterpart is false. This is the content of Kriz’s theorem, which I blogged about before.

The heuristic that density results are strictly stronger than coloring results is the main idea behind a coloring trick that I will present in this post. As far as I am aware, this trick was first used by Bergelson to give an enhancement of Schur’s theorem. The trick can be (very) vaguely stated as: “In every finite partition of {{\mathbb N}}, one of the colors is both of positive density and a set of recurrence”.

In this post I will illustrate the use of this coloring trick by presenting a proof of a theorem of Alfred Brauer’s Theorem (while the original paper is not in mathscinet, this more recent paper of Brauer also mentions the theorem.

Theorem 1 (Brauer, 1928) Let {{\mathbb N}=C_1\cup C_2\cup...\cup C_r} be a partition of {{\mathbb N}} into {r} sets. Then for some {i\in\{1,...,r\}} and for all {k\in{\mathbb N}}, there are {a,n\in{\mathbb N}} such that {\{n,a,a+n,a+2n,...,a+kn\}\subset C_i}.

Note that this statement is stronger than van der Waerden’s theorem, where we just require {\{a,a+n,a+2n,...,a+kn\}\subset C_i} and not that {n\in C_i} as well. It can be thought of as the joint generalization of van der Waerden and Schur’s theorems.

The basic idea of the coloring trick is to start with a density result and use it to prove a coloring result which is stronger than the obvious consequence of the density result. For us, the density result will be Szemeredi’s theorem. To put things in perspective, Theorem 1 was proved by Brauer not so long after van der Waerden’s theorem was first proved (late 1920’s) and Szemeredi’s theorem was only proved in {1975} (and the proof of Szemeredi’s theorem is much more complicated than the original proof of Brauer’s theorem). I merely present this proof to show how one can use the coloring trick and deeper results as a black box to obtain coloring results.

— 2. Basic facts about density —

We denote by {[N]} the set {\{1,2,...,N\}} and by {(M,N]} the set {\{M+1,M+2,...,N\}}, for {M\leq N\in{\mathbb N}}. For a set {A\subset{\mathbb N}} we define the (Banach) upper density of {A} by

\displaystyle d^*(A)=\limsup_{N\rightarrow\infty}\sup_{M\in{\mathbb N}}\frac{|A\cap(M,M+N]|}N

If {A\subset{\mathbb N}} is such that {d^*(A)>0} we say that {A} has positive upper density. Similarly we define the lower (Banach) density of {A} by

\displaystyle d_*(A)=\liminf_{N\rightarrow\infty}\inf_{M\in{\mathbb N}}\frac{|A\cap(M,M+N]|}N

Note that {d_*(A)\leq d^*(A)}.

Lemma 2 If {A,B\subset{\mathbb N}} are such that {d^*(A)+d_*(B)>1}, the the intersection {A\cap B} has positive upper density and, in particular, is non-empty.

Proof: Let {\epsilon=(d^*(A)+d_*(B)-1)/2}. By the definition of lower density there exists {N_0\in{\mathbb N}} so that for all {N>N_0} we have {\inf_{M\in{\mathbb N}}|B\cap(M,M+N]|/N>1-d^*(A)+\epsilon}.

Then, from the definition of upper density, there are arbitrarily large {N>N_0} such that {\sup_{M\in{\mathbb N}}|A\cap(M,M+N]|/N>1-\inf_{M\in{\mathbb N}}|B\cap(M,M+N]|/N+\epsilon/2}. Since {|A\cap[M,M+N]|} can only take finitely many values for each fixed {N}, the supremum is obtained for some {M}. Thus we have that, for arbitrarily large {N} there is some {M\in{\mathbb N}} such that

\displaystyle  \begin{array}{rcl}  \displaystyle |A\cap(M,M+N]|&>&\displaystyle N\left(1+\frac\epsilon2\right)-\inf_{M\in{\mathbb N}}|B\cap(M,M+N]|\\&\geq&\displaystyle N\left(1+\frac\epsilon2\right)-|B\cap(M,M+N]| \end{array}

Rearranging we have

\displaystyle  \begin{array}{rcl}  \displaystyle N\left(1+\frac\epsilon2\right)&<&\displaystyle |A\cap(M,M+N]|+|B\cap(M,M+N]|\\&\leq&\displaystyle |A\cup B\cap(M,M+N]|+|A\cap B\cap(M,M+N]|\\&\leq&\displaystyle N+|A\cap B\cap(M,M+N]| \end{array}

Therefore {|A\cap B\cap(M,M+N]|/N>\epsilon/2} and since this happens for arbitrarily large {N} we conclude that {d^*(A\cap B)>0} as desired. \Box

If {A\subset B} we have both {d^*(A)\leq d^*(B)} and {d_*(A)\leq d_*(B)}. Observe that for every finite coloring of {{\mathbb N}}, one of the colors has positive upper density, but we may have a partition into two colors such that the lower density of both colors is {0}.

For any {A,B\subset{\mathbb N}} we have {d^*(A\cup B)\leq d^*(A)+d^*(B)}. In particular, the union of finitely many sets with {0} upper density also has {0} upper density. Analogously, {d_*(A\cup B)\geq d_*(A)+d_*(B)}. If {B={\mathbb N}\setminus A}, then {d^*(A)+d_*(B)=1}.

We can also define the notion of upper and lower density in higher dimensions. Let {t\in{\mathbb N}} and let {A\subset{\mathbb N}^t}. We define the upper and lower density of {A} by:

\displaystyle d^*(A)=\limsup_{N\rightarrow\infty}\sup_{M\in{\mathbb N}^t}\frac{\left|A\cap(M+[N]^t)\right|}{N^t}\qquad\qquad d_*(A)=\liminf_{N\rightarrow\infty}\inf_{M\in{\mathbb N}^t}\frac{\left|A\cap(M+[N]^t)\right|}{N^t}

Lemma 3 If {A_1,...,A_t} are subsets of {{\mathbb N}}, then the upper density {d^*(A)} of the cartesian product {A=A_1\times...\times A_t} of the {A_i} is the same as the product {d^*(A_1)d^*(A_2)\dots d^*(A_t)} of the upper densities of the sets.

Proof: We will first show that for each {N\in{\mathbb N}} we have

\displaystyle \sup_{M\in{\mathbb N}^t}\frac{\left|A\cap(M+[N]^t)\right|}{N^t}=\prod_{i=1}^t\sup_{M_i\in{\mathbb N}}\frac{|A_i\cap(M_i,M_i+N]|}N

Indeed, for {M=(M_1,...,M_t)\in{\mathbb N}^t} we have {\left|A\cap(M+[N]^t)\right|=\prod_{i=1}^t|A_i\cap(M_i,M_i+N]|}, therefore for each choice of {M} in the left hand side there are choices of {M_1,...,M_t} that correspond to the same quantity in both sides of the equation.

For each {\epsilon>0} let {N\in{\mathbb N}} be such that {d^*(A)<\sup_{M\in{\mathbb N}^t}\left|A\cap(M+[N]^t)\right|N^t+\epsilon}. From the previous equation we obtain that {d^*(A)<\prod d^*(A_i)+\epsilon}. Making {\epsilon\rightarrow0} we conclude that {d^*(A)\leq\prod d^*(A_i)}.

To prove the other direction, observe that, for each {i\in[t]} and {N\in{\mathbb N}}, we have {\sup_{M_i\in{\mathbb N}}|A_i\cap(M_i,M_i+N]|/N\geq d^*(A_i)}. Indeed, let {P\in{\mathbb N}}. Then for any {M_i\in{\mathbb N}} we have

\displaystyle  \begin{array}{rcl}  \displaystyle |A_i\cap(M_i,M_i+P]|&\leq&\displaystyle \sum_{k=0}^{\lfloor P/N\rfloor}\left|A_i\cap\big((M_i,M_i+N]+kN\big)\right|\\&\leq&\displaystyle \left(\frac PN+1\right)\sup_{M_i\in{\mathbb N}}|A_i\cap(M_i,M_i+N]| \end{array}

and now dividing by {P} we obtain

\displaystyle \frac{|A_i\cap(M_i,M_i+P]|}P\leq\left(1+\frac NP\right)\sup_{M_i\in{\mathbb N}}\frac{|A_i\cap(M_i,M_i+N]|}N

Taking {\limsup} as {P\rightarrow\infty} we conclude that {\sup_{M_i\in{\mathbb N}}|A_i\cap(M_i,M_i+N]|/N\geq d^*(A_i)}. Finally, together with the first equation of the proof, this implies that {d^*(A)\geq\prod d^*(A_i)}. \Box

— 3. Brauer’s theorem —

First we prove an extension of Szemeredi’s theorem. This should not be confused with the much more involved Multidimensional Szemeredi’s theorem of Furstenberg and Katzenelson.

Proposition 4 Let {A\subset{\mathbb N}^t} have positive upper density and let {u=(1,1,...,1)\in{\mathbb N}^t} and let {k\in{\mathbb N}}. Let

\displaystyle B:=\{n\in{\mathbb N}:\exists a\in{\mathbb N}^t,\{a,a+nu,...,a+knu\}\subset A\}

Then {B} has positive lower density

Proof: We will use Furstenberg’s multiple recurrence theorem (which both implies and follows from Szemeredi’s theorem, see this proposition from a previous post of mine regarding this equivalence):

\displaystyle \liminf_{N\rightarrow\infty}\frac1N\sum_{n=1}^Nd^*\big(A\cap(A-nu)\cap(A-2nu)\cap...\cap(A-knu)\big)>0

It should be clear that if {d^*\big(A\cap(A-nu)\cap(A-2nu)\cap...\cap(A-knu)\big)>0} then there exists some {a\in A} such that {\{a,a+nu,a+2nu,...,a+knu\}\subset A}. Let {L} be that positive {\liminf}. Then the set {C:=\{n\in{\mathbb N}:d^*\big(A\cap(A-nu)\cap(A-2nu)\cap...\cap(A-knu)\big)>L/2\}} is contained in {B}. Now fix {N\in{\mathbb N}}. Each {n\in[N]} is either in {C} or to isn’t. If it isn’t then {d^*\big(A\cap(A-nu)\cap(A-2nu)\cap...\cap(A-knu)\big)\leq L/2} and if it is then {d^*\big(A\cap(A-nu)\cap(A-2nu)\cap...\cap(A-knu)\big)\leq1}. Thus

\displaystyle \sum_{n=1}^Nd^*\big(A\cap(A-nu)\cap(A-2nu)\cap...\cap(A-knu)\big)\leq |C|+(N-|C|)\frac L2

and dividing by {N} and taking {\liminf} as {N\rightarrow\infty} we get {L\leq d_*(C)+\big(1-d_*(C)\big)L/2} which implies that {d_*(C)>0}, and furthermore also {d_*(B)>0}. \Box

Informally speaking, Proposition 4 states that a set of upper density {1} is a set of recurrence for Szemeredi’s theorem. We are now ready to apply the coloring trick:

Let {{\mathbb N}=C_1,C_2,...,C_r} be a partition of {{\mathbb N}} into finitely many cells. After reordering, if necessary, we can assume that for some {t\in\{1,...,r\}} we have {d^*(C_1),d^*(C_2),...,d^*(C_t)>0} and {d^*(C_{t+1})=d^*(C_{t+2})=...=d^*(C_r)=0}. Thus, the complement of {C:=C_1\cup C_2\cup...\cup C_t} is the set {C_{t+1}\cup C_{t+2}\cup...\cup C_r} which has {0} upper density. We conclude that {C} has lower density {1}.

Now let {A=C_1\times C_2\times...\times C_t\subset{\mathbb N}^t}. Then {d^*(A)>0}. Let {B} be the set given by Proposition 4 (the set of returns). We have from the proposition that {d_*(B)>0}, therefore {d_*(B)+d^*(C_1)+d^*(C_2)+...+d^*(C_t)>1} and so {d^*(B\cap C_i)>0} for some {i\in[t]}.

Let {n\in B\cap C_i} (this set is non-empty because it has positive upper density). From the construction of {B} there is some {\tilde a\in{\mathbb N}^t} such that {\{\tilde a,\tilde a+nu,...,\tilde a+knu\}\subset C}. Looking only at the {i}-th coordinate we obtain some {a\in{\mathbb N}} such that {\{a,a+n,...,a+kn\}\subset C_i}, and this proves Brauer’s theorem.

This entry was posted in Combinatorics, Ergodic Theory, Ramsey Theory, Tool and tagged , , , , , , . Bookmark the permalink.

3 Responses to Brauer’s theorem and a coloring trick of Bergelson

  1. Pingback: On {x+y,xy} patterns in large sets of countable fields | I Can't Believe It's Not Random!

  2. Pingback: Applications of the coloring trick | I Can't Believe It's Not Random!

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