— 1. Introduction —
Van der Waerden’s theorem on arithmetic progressions states that, given any finite partition of , one of the cells contains arbitrarily long arithmetic progressions. For the sake of completion we give a precise formulation.
Theorem 1 (van der Waerden) Let and be disjoint sets such that (in other words form a coloring of ). Then there exists such that for every there are such that
One equivalent formulation is the following:
Theorem 2 (van der Waerden, again) Let and be such that . Then for every finite set there exists an affine transformation such that is contained in some .
To see why this formulation is equivalent to van der Waerden’s theorem, note that every finite subset of is contained in some interval , and hence is contained in the arithmetic progression .
There are by now many different proofs of van der Waerden’s theorem and of generalizations of it, each revealing something about the “true nature” of this fundamental result in Ramsey Theory. One particular proof is due to Furstenberg and Weiss (which I have posted about before) involving topological dynamics. In that proof, the dynamics of the semigroup are used.
On a different perspective, the second formulation of van der Waerden’s theorem presented above suggests that perhaps a different semigroup is behind this result.
Let be the affine semigroup over . In other words, an element is a map of the form for some , and the operation is the composition of functions. We have a natural action of on (by affine transformations). Now let be a finite set and let be the set of all -colorings of . For each we denote by the constant function defined by for all .
It turns out that one can formulate van der Waerden’s theorem in terms of the dynamics of this semigroup in a certain space. In this post I will do precisely this. Also, some other results about arithmetic progressions can be reformulated in this language.
We can induce a right action (or anti-action) on by for , and . A subset is -invariant if for all and all we have . By an application of Zorn’s lemma we get that there exists some minimal non-empty closed -invariant subset of . For simplicity such sets will be called minimal systems of .
— 2. van der Waerden Theorem as proximality —
This theorem will follow quickly from the next observation:
Proof: Assume true the van der Waerden theorem. Let . It induces a coloring of in colors. By the van der Waerden theorem one of the colors, say , contains arbitrarily long arithmetic progressions. For each let be an arithmetic progression of length such that for all . We can write for some , and so for all . Since can be arbitrarily large, we conclude that .
Now assume that for all , there is some such that . Then for any there is some such that for all and so the arithmetic progression is colored . We conclude that the color has arbitrarily long arithmetic progressions.
We now deduce the Theorem 3:
Proof: Let be a minimal system of and let . The set is invariant under , so the orbit closure of is also in . Note that, for each , the point is a fixed point of the system . Therefore, if then . By the previous lemma, van der Waerden is equivalent to the statement that every orbit closure contains a point , and so this is equivalent to the statement that the only minimal systems are those singletons.
In order to get an even cleaner statement we need to consider a slightly different system. For , we say that if there is some permutation of such that (where and are seen as functions ). Let be the set of equivalent classes under this relation.
Note that the projection satisfy whenever . Therefore we can define for by letting . Now we see that is a factor map.
Note that for each . This observation implies the following result:
Theorem 5 The van der Waerden theorem is equivalent to the statement that the only minimal system of is the fixed point .
This theorem states that the van der Waerden theorem is equivalent to the statement that the system is proximal (in the sense that any two points get arbitrarily close to each other under some ). We note that the same language can be used to formulate some other related theorems.
— 2.1. Multidimensional vdW —
Theorem 6 (Multidimensional van der Waerden theorem) Let and be a coloring of . Then for every there exists , and such that
Fix and let be the group of affine transformations of . In other words is the set of functions of the form for some and some . We have a natural action by on .
Let . We can induce a right action of on by for all , and . For each pair we say that if there is some permutation of such that . Let be the set of equivalent classes. It is not hard to see that the action of on projects to an action on .
Now the multidimensional van der Waerden theorem is equivalent to the statement that the only minimal system of is the fixed point .
— 2.2. Szemerédi’s Theorem —
Theorem 7 (Szemerédi’s theorem) Let be such that
Then contains arbitrarily long arithmetic progressions.
Given a set , its characteristic function is an element of . This gives the following equivalent formulation of Szemerédi’s theorem.
Theorem 8 Szemerédi’s theorem is equivalent to the fact that if is such that , then
Proof: This theorem will follow from the fact that a set has arbitrarily long arithmetic progressions if and only if its orbit closure contains the singleton .
If then for every there exists such that agrees with in the coordinates . In other words for all . By the definition of this means that the arithmetic progression of length is a subset of . Since was arbitrary this implies that contains arbitrarily long arithmetic progressions.
Conversely, if contains an arithmetic progression of arbitrary length, then for any finite set there exists some such that and there exists such that . Thus agrees with in the first coordinates, and hence in . Since is an arbitrary finite subset of this implies that , by the definition of product topology.
We can also reformulate in this language the multidimensional Szemeredi’s theorem or the Green-Tao theorem.