** — 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 acoloringof ). 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 — **

Theorem 3van der Waerden’s theorem is equivalent to the statement that the only minimal systems of are the singletons with .

This theorem will follow quickly from the next observation:

Lemma 4van der Waerden’s theorem is equivalent to the statement that for every there is some such that the orbit closure contains .

*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 5The 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 thatThen 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 8Szemeré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.

Pingback: An arithmetic van der Corput trick and the polynomial van der Waerden theorem | I Can't Believe It's Not Random!

I was reading Theorem 2 (van der Waerden, again) and it seems pretty interesting to me. But I have two questions:

1) If you start with a ring (R, +, \ast), can you expect a similar type of result? That is: If you take a finite partition of R, then for any finite set F in R, does there exist an affine transformation g from R to R such that g(F) sits inside one of the cells of the partition?

2) if G is a finite set in R. Now take a finite partition of G, then for any subset F of G, does there exist an affine transformation g from R to R such that g(F) sits inside one of the cells of the partition?

Dear Arpita,

The answer to 1) is yes for commutative rings. In fact an even more general result follows from the Hales-Jewett theorem, see Theorem 13 in this post: https://joelmoreira.wordpress.com/2014/08/26/hales-jewett-and-a-generalized-van-der-warden-theorems/#thm_generalvdw.

For general non-commutative rings it is likely that the answer is negative, but I don’t have a counter-example.

Regarding question 2) I think some quantifiers were missing; as stated the answer is trivially negative (by taking F=g, or choosing the trivial partition into singletons).

Extremely sorry for the second question. I am rewriting the question here:

For a ring (R,+,\ast), define Affine(R) is the set of all affine transformation on (R, +, \ast).

Let us assume that we are in the following situation:

We have a natural number r, such that for all finite set F of Affine(R), there exists x \in R such that the set { f(x): f \in F} is subset of \bigcup_{i=1}^r T_i for some subsets T_i in R.

Now my question is: Does there exist a finite subset K of Affine(R) such that whenever {k(x): k \in K} is partitioned into r cells, there exists h, an affine transformation, such that {h(k(x)): k \in K} sits inside one of the cells of the partition?

Thank you so much again for the kind response. Hoping to hear from you soon.

Dear Arpita, thank you for the clarification, but I still can’t understand the question. Do the sets depend on the finite set ?

And do you want this for any ring of for a specific ring? For instance if is an integral domain, affine transformations are injective, so contains as many elements as the set which is partitioned, so it is unlikely that it is monochromatic…