— 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 ) 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
- Ramsey’s theorem which gives the name to the field,
- van der Warden’s theorem,
- Schur’s theorem,
- Hindman’s theorem,
- Rado’s theorem
- Halles-Jewett’s theorem.
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 there are of the same color such that ) since the odd numbers have density but contain no solution to . 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 , 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.
Note that this statement is stronger than van der Waerden’s theorem, where we just require and not that 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 (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.
We denote by the set and by the set , for . For a set we define the (Banach) upper density of by
If is such that we say that has positive upper density. Similarly we define the lower (Banach) density of by
Note that .
Lemma 2 If are such that , the the intersection has positive upper density and, in particular, is non-empty.
Proof: Let . By the definition of lower density there exists so that for all we have .
Then, from the definition of upper density, there are arbitrarily large such that . Since can only take finitely many values for each fixed , the supremum is obtained for some . Thus we have that, for arbitrarily large there is some such that
Rearranging we have
Therefore and since this happens for arbitrarily large we conclude that as desired.
If we have both and . Observe that for every finite coloring of , 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 .
For any we have . In particular, the union of finitely many sets with upper density also has upper density. Analogously, . If , then .
We can also define the notion of upper and lower density in higher dimensions. Let and let . We define the upper and lower density of by:
Lemma 3 If are subsets of , then the upper density of the cartesian product of the is the same as the product of the upper densities of the sets.
Proof: We will first show that for each we have
Indeed, for we have , therefore for each choice of in the left hand side there are choices of that correspond to the same quantity in both sides of the equation.
For each let be such that . From the previous equation we obtain that . Making we conclude that .
To prove the other direction, observe that, for each and , we have . Indeed, let . Then for any we have
and now dividing by we obtain
Taking as we conclude that . Finally, together with the first equation of the proof, this implies that .
— 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.
Then 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):
It should be clear that if then there exists some such that . Let be that positive . Then the set is contained in . Now fix . Each is either in or to isn’t. If it isn’t then and if it is then . Thus
and dividing by and taking as we get which implies that , and furthermore also .
Informally speaking, Proposition 4 states that a set of upper density is a set of recurrence for Szemeredi’s theorem. We are now ready to apply the coloring trick:
Let be a partition of into finitely many cells. After reordering, if necessary, we can assume that for some we have and . Thus, the complement of is the set which has upper density. We conclude that has lower density .
Now let . Then . Let be the set given by Proposition 4 (the set of returns). We have from the proposition that , therefore and so for some .
Let (this set is non-empty because it has positive upper density). From the construction of there is some such that . Looking only at the -th coordinate we obtain some such that , and this proves Brauer’s theorem.