— 1. Introduction —
In a previous post I presented a proof of van der Waerden’s theorem on arithmetic progressions:
Theorem 1 (van der Waerden, 1927) Consider a partition of the set of the natural numbers into finitely many pieces . Then one of the pieces contains arbitrarily long arithmetic progressions.
It follows easily from van der Waerden’s theorem that, for any finite partition of , one of the pieces in the partition contains arbitrarily long geometric progressions. To see this consider the partition of the set . In fact, we can take the same piece to contain arbitrarily long arithmetic progressions and arbitrarily long geometric progressions. More precisely:
In this post I will present a proof of this fact due to Bergelson and Hindman.
This proof uses the technology of ultrafilters on , and the only other proof I know of this fact uses the much stronger Szemeredi’s theorem.
— 2. Preliminaries on ultrafilters —
In this section I will list some facts about ultrafilters on that I will need later in the post. For a more complete treatment, including the proof of all facts claimed here, see, for instance, my previous post on the subject, or these two surveys by Bergelson.
In this post, will denote a countable abelian semigroup and will denote a general semigroup. Also will always denote the identity of the semigroups (it will be clear in the context which semigroup belongs to). We will only use and , but the theorems and definitions are easier to state in this general form.
An ultrafilter over is a collection of subsets of such that, for every finite partition of , exactly one of the pieces is in . It follows easily from the definition that the empty set is not in ; that if then , and that if and , then also .
The only explicit examples of ultrafilters are the principal ultrafilters and are defined as follows: let and let . The existence of any other ultrafilter requires the axiom of choice (or at least some weak form of it).
The set of all ultrafilters over is denoted by . Given a set we denote by the set of all ultrafilters that contain . We will use the topology on generated by the clopen sets with . With this topology is compact.
Given we define the operation by
where . It follows that, with this operation, becomes a left topological semigroup. Moreover if and , then . All the facts stated so far are proved is my previous post mentioned above.
We will need the following theorem of Ellis:
An element which satisfies is called an idempotent.
A left ideal of a non-abelian semigroup is a compact set such that . Analogously one define right ideal as a compact set such that . We will also say that is a two-sided ideal if is both a left and a right ideal.
Definition 4 An ultrafilter is a minimal idempotent if and there exists a right ideal which is minimal with respect to inclusion and such that . A set is called central if there exists a minimal idempotent such that .
It is true that for any semigroup there exists a minimal idempotent ultrafilter , but we will not need this fact for this post.
Finally we will use the following technical definition. This is not standard terminology.
Definition 5 We say that a semigroup is without inverses if for every , there is no such that .
It’s easy to verify that both and are semigroups without inverses.
— 3. Proof of Theorem 2 —
The following theorem is a generalization of van der Waerden theorem for any abelian semigroup without inverses.
Theorem 6 Let be an abelian semigroup without inverses and let be central. Then for each there exist such that .
Proof: Let be the identity of , if it exists. Otherwise, we can always create an identity, and we will denote it also by (keep in mind that we will apply this theorem to both semigroups and , the second has an identity but the first doesn’t. In any case, this is just a technical detail).
Fix . Let and let it have the product topology. Note that is a semigroup for pointwise operation. Let be the closure in of the set and let be the closure in of the set . Note that
Similarly for we get
In particular, for any , we have . Indeed, for any , the intersection is also in and in particular it is non-empty. Choosing in the intersection and we conclude that for all .
We claim that is a semigroup and is a two-sided ideal. Indeed, let . For each let . This implies that . Let and be such that for each . Let . Let and be such that for each . Then and so . Moreover, if either or is in , then not both of is equal to , and since is without inverses, we conclude that , which implies that . This proves the claim.
Now let be a minimal ultrafilter such that . We will show that . Let . This is a right ideal of . Therefore there exists a minimal right ideal of contained in . We will show that .
Since is minimal it is in some minimal right ideal of . Let be an idempotent, it exists by Ellis theorem. Then for some . This means that for each we have , and thus . We conclude that , and in particular for some . Therefore , and since this happens for every we obtain that . Finally this gives as claimed.
Now we note that is a non-empty right ideal of . Indeed, it is non-empty because if and then . But since is a minimal right ideal, this implies that , and since , we conclude that .
Since we have that there exists with such that , as desired.
Now to finish the proof of Theorem 2 it suffices to show that, for every finite partition of , one of the pieces is both additively central and multiplicatively central. This in turn is a direct consequence of the following theorem:
Theorem 7 There exists an ultrafilter such that each set is both additively central and multiplicatively central.
Proof: Let be the set of all additive minimal idempotents. To see that is non-empty, let be a minimal right ideal (in ), which exists by Zorn lemma. Then is a compact semigroup in itself. Applying Ellis theorem (Theorem 3) we obtain a minimal idempotent for .
Note that if , then for every there exists such that , and so is central. Conversely, if every is central, then every neighborhood of intersects and so . We claim that is a right ideal in .
Indeed, let and let . We need to show that . Let , we need to show that is central. By definition of we have that , and in particular this set is non-empty.
Let be such that . Since we conclude that is central. Let be such that . This means that , where is the principal ultrafilter at . We need to show that . Let be a minimal right ideal in such that . Then also and so is a minimal ultrafilter. It remains to show that is an idempotent:
We have that is a right ideal in the semigroup . By Zorn’s lemma we can find a minimal multiplicative ideal inside . This is a sub-semigroup of , so by Ellis theorem we obtain a multiplicative minimal idempotent . In particular every set is both additively and multiplicatively central, as desired.