A Theorem of Schur (one of the earliest results in Ramsey Theory) asserts that given any finite coloring of the set of natural numbers , there exist of the same color such that also has the same color. As a Corollary (using any injective homomorphism between the semigroups and , for instance ) one gets that in any finite coloring of there are and of the same color such that is also of that color.
The next question is whether one can find of the same color such that both and are also of the same color. This question is still open, and even the easier looking question of whether we can find and such that and have the same color (but we don’t care about the colors of and ) is unanswered.
I was surprised to learn recently that the following related result has been proved (and has a nice proof):
The proof we will present uses the theory of idempotent ultrafilters on , one of my purposes here is to make a point for the usefulness of ultrafilters when dealing with problems from arithmetic combinatorics. I am also quite interested on this because it seems that ultrafilters are the only tool available so far to deal with combinatorics on dealing with both addition and multiplication (one can argue that polynomials involve multiplication, but quadratic polynomials are just sums of linear polynomials and so on, and the theorems involving polynomials are proved using that way of thinking about polynomials. Another theorem that seems to have some of the multiplications structure is the Green-Tao Theorem, but really the only thing about primes that is used in the proof are some statistics on their distribution. Finally in this parenthesis I should say that there are results dealing with both addition and multiplication on finite fields, proved using Fourier analysis, but unlike results dealing with only addition, it seems harder (if not completely impossible) to use those results to establish analogues on the infinite set ).
This post turned out to be a little longer than I initially expected, but that is mostly because I decided to make it completely self contained (apart from some standard results from point set topology).
— 1. Ultrafilters on countable sets —
I decided to work on a general countable (infinite) commutative ring, so in this post will always denote such a ring, so I actually present a proof of the Theorem 1 with replaced by . In this section though, I will only use the fact that is a countable set.
- If and then
- If and then also
- If then either or
In particular by the second condition (and because is non-empty), so for each , either or (by the last property). Also, iterating the last property, we get that for any finite partition of , one of the cells belongs to (and exactly one).
A trivial example of an ultrafilter can be given by the following: pick and consider the family . One can promptly check the conditions that define ultrafilters. However, in order to obtain any example of a non-principal ultrafilter, one requires (at least some weaker form of) the axiom of choice. This means that an explicit construction of an non-principal ultrafilter is hopeless. What we can (and will) do is prove existence of ultrafilters with some nice additional properties.
Proposition 3 There exist non-principal ultrafilters.
Proof: A family of subsets of satisfying the first three properties of the Definition 2 is called a filter. We first show that any maximal filter (for the partial order of inclusion) is an ultrafilter. Let be a maximal filter, let be non-empty sets such that . Assume , consider . I claim that is also a filter, by maximality this will imply that and so as desired.
To prove that , assume it is. Since is a filter and is non-empty we have that for some . But since , we have is in and also a subset of , contradicting the assumption that . The second and third conditions for a filter trivially hold for and this proves the claim.
Now it is also easy to check that the union of any totally ordered subset of filters is again a filter, so we can apply the Zorn’s lemma to conclude that any filter is contained in some ultrafilter. Since the filter of co-finite sets is not contained in any principal ultrafilter we get existence of a non-principal ultrafilter.
As I mentioned earlier in this post, the set of all ultrafilters can be identified with the Stone-Čech compactification of . Let be the set of all functions . By identifying a subset with its indicator functions, we can also think of as all subsets of . We endow with the discrete topology and give the product topology, making it into a compact space by the Tychonoff’s theorem. Now we consider the space of all functions from in , it is also compact, again by the Tychonoff’s theorem. We can also think of a point in as a subset of or, equivalently as a collection of subsets of .
Now, for each , let be the function given by for each . This gives an embedding of into , that by an abuse of language we will also denote by . The Stone-\v Cech compactification of is the closure of in (it is compact because it is a closed subset of the compact Hausdorff space ).
A point is a map from to . By identifying points in with subsets of , we can associate with the family of subsets for which . By an abuse of language we will denote this collection of subsets of also by and we will use interchangeably the notations and with the same meaning. Note that the element is the principal ultrafilters at .
Proposition 4 Let be a collection of subsets of . Then if and only if is an ultrafilter on .
Proof: Unraveling the meaning of product topology we see that if and only if for any finite collection of subsets of there exists some such that for each .
First assume that . Since for all , also and hence , proving the first property of the Definition 2. Now let and suppose . Let be such that and . Then so and thus , proving the second property. If both and are in , let be such that and agree at and . Then we conclude that proving the third property. Finally suppose that and let be such that agree with at , and . Thus either or will be in proving the fourth property. This implies that is indeed an ultrafilter.
Now suppose that is an ultrafilter. Given any subsets of , assume that are in and are not in . Then the intersection
is in and in particular it is non-empty. Let be in that intersection. Then agrees with at the sets . Since the sets were arbitrary, we conclude that there exists some at each neighborhood of , and hence .
This proves suggests the following observation about the topology of that will be useful for us later. For a set we define its closure by . Note that just defined is the closure on of the set , but we will not need this fact.
Proof: Let . By definition . Since is a clopen subset of and by the definition of product topology on we conclude that is a clopen set of , hence intersecting with we get a clopen subset of .
To prove that they form a basis for the topology on , let , let , let be subsets of and let . Consider the intersection
Then, by the ultrafilter property, . Thus .
— 2. Ultrafilters on semigroups —
So far we didn’t use any property of the set (except that it is infinite). Now we will see that a binary operation on induces a binary operation in . To motivate the definition it helps to think of ultrafilters in yet a third way, namely as finitely additive -valued measures on . In that way, the operation on is just the usual convolution of measures.
Let be an associative binary operation on (we will only use and ), let and . I use the notation to denote the set . In the case of additive notation we will use instead of .
Definition 6 Let and be ultrafilters on a semigroup . We define the operation
We first need to check that is indeed an ultrafilter on :
Proposition 7 If then also .
Proof: It is clear that . Also, if , then for each we have . It is now easy to check that if then also . Now assume that both . Since for each , we have that and hence .
Finally, if then using the fact that is an ultrafilter (and the fact that ) we have that for each in the set either or . Since is also an ultrafilter and , either or which is equivalent, respectively to or .
Moreover, this binary operation turns out to be associative:
Proposition 8 The binary operation on just defined is associative.
Proof: We first note that for and we have
and so .
Let . Then if and only if
Thus is a semigroup. It should be remarked that this operation extends the operation on . More precisely, if then . However, the operation in needs not be commutative even if is.
Another good property of the operation in is that it is left continuous:
Proposition 9 For each , the map defined by is continuous.
Proof: We will use the Lemma 5. Fix and let be an clopen neighborhood of . I need to show that contains for some . We observe that . Thus making we get that indeed contains .
Quite special elements of the semigroup are idempotent elements, i.e, ultrafilters such that . However, the existence of such ultrafilters not obvious. Their existence can be assured using a Theorem by Ellis:
Theorem 10 (Ellis Theorem) If is a compact Hausdorff left topological semigroup, then contains an idempotent.
Proof: Consider the family
is non-empty because . Also the intersection of any nested subfamily of is still in (because a nested intersection of compacts in a Hausdorff space is non-empty). Applying Zorn’s lemma we find a minimal (for the partial order of inclusion) element .
For each we have , and by left continuity is compact, hence . Also , so by minimality .
In particular for some . Thus the set is non-empty. By continuity we have that is closed (hence compact) and if then , hence . This implies that , again by minimality we have that and in particular . We conclude that , and this is our idempotent.
This implies that there are idempotent ultrafilters on .
— 3. Idempotent ultrafilters and Hindman’s Theorem —
We are now concerned with a countable set with a commutative associative binary operation . Given an infinite set we for the set of finite products of :
Hindman’s theorem asserts that, given any finite partition of , one of the cells of the partition contains a set of the form for some infinite set . Sets that contain for some infinite set are called IP sets.
In order to prove Hindman’s Theorem, it will suffice to prove the following:
The reason why this implies Hindman’s Theorem is that for any finite partition, one of the cells belong to .
Proof: Since and , we have that . Thus also and, in particular, this set is non-empty. Choose some in that set, note that and .
Now, by the same reasoning, also , choose some in that set and note that and . Moreover , hence , in other words . Now inductively we prove that for each there is a set such that , and a sequence such that .
Now assume we have this for , note that the set and in particular is non-empty. Choose some on that set, note that and that the set . Moreover, for any we have , since by induction we get that and this completes the induction.
Thus as desired.
We just proved that each set belonging to an idempotent ultrafilter is an IP set. We now prove a partial converse, and first we need a lemma:
Proof: Let be an infinite set such that and let denote the family of all co-finite subsets of . Let
Since is the intersection of a nested sequence of compact sets is compact and non-empty. I claim that is a semigroup. Let , we need to show that for each we have .
For each , we can write for some . Let . Then , in other words and since we have that and hence is in . This proves that and hence is a semigroup.
Finally, we apply Ellis theorem to to find an idempotent there.
Proof: Assume first that every is an IP set. Let be a neighborhood (in ) of . Then for some set . This implies that and hence is an IP set. By the previous Lemma is also contained in some idempotent ultrafilter , so and thus .
Now suppose that and let . Thus and hence there exists some idempotent such that also . But this implies that and hence is an IP set.
— 4. Mixing addition and multiplication —
On this section we will (finally) use the fact that is a ring with two operations. This gives two notions of idempotents in . A natural question is whether there exist any which is idempotent with respect to both the additive and the multiplicative structure. Unfortunately the answer turns out to be negative in general (at least it is negative when , I couldn’t find a proof for any other ring).
More precisely, there is no ultrafilter such that , this appears as Corollary 17.17 in this book of Hindman and Strauss.
However we can construct an ultrafilter almost as good:
Theorem 14 There exists an ultrafilter such that is multiplicative idempotent and every is an additive IP set.
Proof: Let . In view of Ellis Theorem and the Proposition 13, it suffices to prove that is a multiplicative semigroup. It turns out that it is actually a left ideal (i.e. ).
Let and . Let . Then , and in particular that set is non-empty. Choose some such that . Then is an additive IP set. Let be an infinite set such that the additive IP set . But then and hence is an (additive) IP set as desired. Since was chosen arbitrarily we get that and we are done.
— 5. Proof of the Theorem 1
We now present the proof of the Theorem 1, with replaced by any countable abelian ring .
For any ultrafilter we know that one cell of a finite partition must belong to . Thus the Theorem reduces to the following:
Theorem 15 Let be a multiplicative idempotent such that each is an additive IP set. Then for each there are such that .
Proof: Since we have that . Choose such that . Then is an additive IP set, by the Lemma 12 there exists some additive idempotent such that . Then and so also . Choose some in that intersection. Then and . Then also and so that set is non-empty.
Since we get that . Also we now have that is non-empty, and we can rewrite
Let . Then and , so there exists some such that as desired.