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.