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.

Advertisements

About Joel Moreira

PhD Student at OSU in Mathematics. I'm portuguese.
This entry was posted in Combinatorics, Topological Dynamics and tagged , , . Bookmark the permalink.

One Response to Arithmetic progressions and the affine semigroup

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s