## Arithmetic progressions and the affine semigroup

— 1. Introduction —

Van der Waerden’s theorem on arithmetic progressions states that, given any finite partition of ${{\mathbb N}}$, 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 ${r\in{\mathbb N}}$ and ${C_1,\dots,C_r\subset{\mathbb N}}$ be disjoint sets such that ${{\mathbb N}=C_1\cup \dots\cup C_r}$ (in other words ${C_1,\dots,C_r}$ form a coloring of ${{\mathbb N}}$). Then there exists ${i\in\{1,\dots,r\}}$ such that for every ${k\in{\mathbb N}}$ there are ${a(k),s(k)\in{\mathbb N}}$ such that

$\displaystyle a(k)+js(k)\in C_i\ \forall j=1,\dots,k$

One equivalent formulation is the following:

Theorem 2 (van der Waerden, again) Let ${r\in{\mathbb N}}$ and ${C_1,\dots,C_r\subset{\mathbb N}}$ be such that ${{\mathbb N}=C_1\cup \dots\cup C_r}$. Then for every finite set ${F\subset{\mathbb N}}$ there exists an affine transformation ${g:x\mapsto a+sx}$ such that ${g(F)}$ is contained in some ${C_i}$.

To see why this formulation is equivalent to van der Waerden’s theorem, note that every finite subset of ${{\mathbb N}}$ is contained in some interval ${\{1,2,\dots,n\}}$, and hence ${g(F)}$ is contained in the arithmetic progression ${g(\{1,2,\dots,n\})}$.

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 ${({\mathbb N},+)}$ 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 ${{\mathcal A}_\mathbb{N}}$ be the affine semigroup over ${{\mathbb N}}$. In other words, an element ${g\in{\mathcal A}_\mathbb{N}}$ is a map ${g:{\mathbb N}\rightarrow{\mathbb N}}$ of the form ${g(x)=a+sx}$ for some ${a,s\in{\mathbb N}}$, and the operation is the composition of functions. We have a natural action of ${{\mathcal A}_\mathbb{N}}$ on ${{\mathbb N}}$ (by affine transformations). Now let ${[r]:=\{1,...,r\}}$ be a finite set and let ${\Omega:=[r]^{\mathbb N}}$ be the set of all ${r}$-colorings of ${{\mathbb N}}$. For each ${k\in[r]}$ we denote by ${\hat k\in\Omega}$ the constant function defined by ${\hat k(n)=k}$ for all ${n\in{\mathbb N}}$.

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 ${{\mathcal A}_\mathbb{N}}$ action (or anti-action) on ${\Omega}$ by ${(g\omega)(n)=\omega(gn)}$ for ${g\in{\mathcal A}_\mathbb{N}}$, ${\omega\in\Omega}$ and ${n\in{\mathbb N}}$. A subset ${A\subset\Omega}$ is ${{\mathcal A}_\mathbb{N}}$-invariant if for all ${a\in A}$ and all ${g\in{\mathcal A}_\mathbb{N}}$ we have ${ga\in A}$. By an application of Zorn’s lemma we get that there exists some minimal non-empty closed ${{\mathcal A}_\mathbb{N}}$-invariant subset of ${\Omega}$. For simplicity such sets will be called minimal systems of ${(\Omega,{\mathcal A}_\mathbb{N})}$.

— 2. van der Waerden Theorem as proximality —

Theorem 3 van der Waerden’s theorem is equivalent to the statement that the only minimal systems of ${(\Omega,{\mathcal A}_\mathbb{N})}$ are the singletons ${\left\{\hat k\right\}}$ with ${k\in[r]}$.

This theorem will follow quickly from the next observation:

Lemma 4 van der Waerden’s theorem is equivalent to the statement that for every ${\omega\in\Omega}$ there is some ${k\in[r]}$ such that the orbit closure ${\overline{\{g\omega:g\in{\mathcal A}_\mathbb{N}\}}}$ contains ${\hat k}$.

Proof: Assume true the van der Waerden theorem. Let ${\omega\in\Omega}$. It induces a coloring of ${{\mathbb N}}$ in ${r}$ colors. By the van der Waerden theorem one of the colors, say ${k\in[r]}$, contains arbitrarily long arithmetic progressions. For each ${L\in{\mathbb N}}$ let ${P_L}$ be an arithmetic progression of length ${L}$ such that ${\omega(n)=k}$ for all ${n\in P_L}$. We can write ${P=g[L]}$ for some ${g\in{\mathcal A}_\mathbb{N}}$, and so ${(g\omega)(n)=k}$ for all ${n\in[L]}$. Since ${L}$ can be arbitrarily large, we conclude that ${\hat k\in\overline{\{g\omega:g\in{\mathcal A}_\mathbb{N}\}}}$.

Now assume that for all ${\omega\in\Omega}$, there is some ${k\in[r]}$ such that ${\hat k\in\overline{\{g\omega:g\in{\mathcal A}_\mathbb{N}\}}}$. Then for any ${L\in{\mathbb N}}$ there is some ${g\in{\mathcal A}_\mathbb{N}}$ such that ${(g\omega)(n)=k}$ for all ${n\in[L]}$ and so the arithmetic progression ${g[L]}$ is colored ${k}$. We conclude that the color ${k}$ has arbitrarily long arithmetic progressions. $\Box$

We now deduce the Theorem 3:

Proof: Let ${A}$ be a minimal system of ${(\Omega,{\mathcal A}_\mathbb{N})}$ and let ${\omega\in A}$. The set ${A}$ is invariant under ${{\mathcal A}_\mathbb{N}}$, so the orbit closure of ${\omega}$ is also in ${A}$. Note that, for each ${k\in [r] }$, the point ${\hat k}$ is a fixed point of the system ${(\Omega,{\mathcal A}_\mathbb{N})}$. Therefore, if ${\hat k\in A}$ then ${A=\left\{\hat k\right\}}$. By the previous lemma, van der Waerden is equivalent to the statement that every orbit closure contains a point ${\hat k}$, and so this is equivalent to the statement that the only minimal systems are those singletons. $\Box$

In order to get an even cleaner statement we need to consider a slightly different system. For ${x,y\in\Omega}$, we say that ${x\sim y}$ if there is some permutation ${\sigma}$ of ${[r]}$ such that ${x=\sigma\circ y}$ (where ${x}$ and ${y}$ are seen as functions ${{\mathbb N}\rightarrow[r]}$). Let ${X}$ be the set of equivalent classes under this relation.

Note that the projection ${\pi:\Omega\rightarrow X}$ satisfy ${\pi(gx)=\pi(gy)}$ whenever ${\pi(x)=\pi(y)}$. Therefore we can define ${gz}$ for ${z=\pi(x)\in X}$ by letting ${gz=\pi(gx)}$. Now we see that ${\pi}$ is a factor map.

Note that ${\hat k\sim \hat j}$ for each ${k,j\in[r]}$. This observation implies the following result:

Theorem 5 The van der Waerden theorem is equivalent to the statement that the only minimal system of ${(X,{\mathcal A}_\mathbb{N})}$ is the fixed point ${\{\pi(\hat1)\}}$.

This theorem states that the van der Waerden theorem is equivalent to the statement that the system ${(X,{\mathcal A}_\mathbb{N})}$ is proximal (in the sense that any two points get arbitrarily close to each other under some ${g\in{\mathcal A}_\mathbb{N}}$). 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 ${d,r\in{\mathbb N}}$ and ${{\mathbb N}^d=C_1\cup\dots\cup C_r}$ be a coloring of ${{\mathbb N}^d}$. Then for every ${k\in{\mathbb N}}$ there exists ${i\in[r]}$, ${a\in{\mathbb N}^d}$ and ${s\in{\mathbb N}}$ such that

$\displaystyle a+sj\in C_i\ \forall j\in\{1,\dots,k\}^d$

Fix ${d\in{\mathbb N}}$ and let ${G}$ be the group of affine transformations of ${{\mathbb N}^d}$. In other words ${G}$ is the set of functions ${g:{\mathbb N}^d\rightarrow{\mathbb N}^d}$ of the form ${g:x\mapsto a+sx}$ for some ${a\in{\mathbb N}^d}$ and some ${s\in{\mathbb N}}$. We have a natural action by ${G}$ on ${{\mathbb N}^d}$.

Let ${\Omega=[r]^{{\mathbb N}^d}}$. We can induce a right action of ${G}$ on ${\Omega}$ by ${(g\omega)(n)=\omega(gn)}$ for all ${g\in G}$, ${\omega\in\Omega}$ and ${n\in{\mathbb N}^d}$. For each pair ${x,y\in\Omega}$ we say that ${x\sim y}$ if there is some permutation ${\pi}$ of ${[r]}$ such that ${x=\pi\circ y}$. Let ${X}$ be the set of equivalent classes. It is not hard to see that the action of ${G}$ on ${\Omega}$ projects to an action on ${X}$.

Now the multidimensional van der Waerden theorem is equivalent to the statement that the only minimal system of ${(X,G)}$ is the fixed point ${\hat 1}$.

— 2.2. Szemerédi’s Theorem —

Theorem 7 (Szemerédi’s theorem) Let ${A\subset{\mathbb N}}$ be such that

$\displaystyle \bar d(A):=\limsup_{N\rightarrow\infty}\frac{|A\cap\{1,\dots,N\}|}N>0.$

Then ${A}$ contains arbitrarily long arithmetic progressions.

Given a set ${A\subset{\mathbb N}}$, its characteristic function ${1_A}$ is an element of ${\{0,1\}^{\mathbb N}}$. This gives the following equivalent formulation of Szemerédi’s theorem.

Theorem 8 Szemerédi’s theorem is equivalent to the fact that if ${A\subset{\mathbb N}}$ is such that ${\bar d(A)>0}$, then

$\displaystyle \hat1\in\overline{\{g1_A:g\in{\mathcal A}_\mathbb{N}\}}$

Proof: This theorem will follow from the fact that a set ${A\subset{\mathbb N}}$ has arbitrarily long arithmetic progressions if and only if its orbit closure contains the singleton ${\hat 1}$.

If ${\hat1\in\overline{\{g1_A:g\in{\mathcal A}_\mathbb{N}\}}}$ then for every ${k\in{\mathbb N}}$ there exists ${g\in{\mathcal A}_\mathbb{N}}$ such that ${g1_A}$ agrees with ${\hat1}$ in the coordinates ${1,2,\dots,k}$. In other words ${g1_A(j)=1}$ for all ${j=1,\dots,k}$. By the definition of ${g1_A}$ this means that the arithmetic progression ${g(\{1,2,\dots,k\})}$ of length ${k}$ is a subset of ${A}$. Since ${k}$ was arbitrary this implies that ${A}$ contains arbitrarily long arithmetic progressions.

Conversely, if ${A}$ contains an arithmetic progression of arbitrary length, then for any finite set ${F\subset{\mathbb N}}$ there exists some ${k\in{\mathbb N}}$ such that ${F\subset\{1,2,\dots,k\}}$ and there exists ${g\in{\mathcal A}_\mathbb{N}}$ such that ${g(\{1,\dots,k\})\subset A}$. Thus ${g1_A}$ agrees with ${\hat1}$ in the first ${k}$ coordinates, and hence in ${F}$. Since ${F}$ is an arbitrary finite subset of ${{\mathbb N}}$ this implies that ${\hat1\in\overline{\{g1_A:g\in{\mathcal A}_\mathbb{N}\}}}$, by the definition of product topology. $\Box$

We can also reformulate in this language the multidimensional Szemeredi’s theorem or the Green-Tao theorem.

This entry was posted in Combinatorics, Topological Dynamics and tagged , , . Bookmark the permalink.

### 5 Responses to Arithmetic progressions and the affine semigroup

1. Arpita Ghosh says:

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?

2. Joel Moreira says:

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).

• Arpita Ghosh says:

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.

3. Joel Moreira says:

Dear Arpita, thank you for the clarification, but I still can’t understand the question. Do the sets $T_i$ depend on the finite set $F$?
And do you want this for any ring of for a specific ring? For instance if $R$ is an integral domain, affine transformations are injective, so $\{h(k(x)):k\in K\}$ contains as many elements as the set $\{k(x):k\in K\}$ which is partitioned, so it is unlikely that it is monochromatic…