On the infinitary van der Waerden Theorem

In [1], Thomas Brown and the author introduced the following infinitary generalization of van der Waerden’s theorem which has the same relation with van der Waerden’s theorem as the Carlson-Simpson theorem [3] has with the Halse-Jewett theorem [5].

Theorem. Let $k\geq 2$ be a positive integer. Then, for any finite coloring of $\mathbb{N}$, there exist positive integers $d_{1},d_{2},d_{3},\dots$ and a color $\gamma$ such that for every $n\in\mathbb{N}$, there exists a positive integer $a_{n}$ such that the set

is monochromatic with the color $\gamma$.

It is possible to deduce the above theorem from the Carlson-Simpson theorem by generalizing the usual proof of deducing van der Waerden’s theorem from the Hales-Jewett theorem. The proof given in [1] uses a more elementary fact on uniformly recurrent infinite words from [6] which has its root in symbolic dynamics. It is worth noting that the above theorem can also be easily deduced from the Furstenberg-Weiss Theorem ([4], Theorem 1.5) by successive iteration. In this note we present a direct combinatorial proof.

For the convenience of the reader and at the suggestion of the referee, we show in the next section how the above theorem can be related to the Carlson-Simpson theorem and then in Section 3, we present our elementary proof. Now, we explain some notation and conventions that we will use in the sequel. For two finite subsets $A,B$ of $\mathbb{N}$, by $A<B$, we mean that every element of $B$ is greater than every element of $A$. By interval, we mean an interval of positive integers which is a set of the form $I=\{a,a+1,a+2,\dots,b\}$, for some positive integers $a\leq b$. We also denote $I$ by $[a,b]$, and for $1\leq i\leq b-a+1$, by $I[i]$ we mean the $i$th element of the interval $[a,b]$, namely, $a+i-1$. The number of elements of $I$ is denoted by $|I|$. If $b$ is a non-negative integer and $A$ is a set of integers, then $\mathbb{T}^{b}A$ will denote the set $\{a+b|a\in A\}$. Let $c$ be a positive integer, by a $c$-coloring, we mean a coloring with $c$ many colors and furthermore the set of colors is $[c]=\{1,\dots,c\}$. For positive integers $k\geq 2$, and $c\geq 1$, $W(k,c)$ will denote the van der Waerden number which is the least integer $n$ such that for any $c$-coloring of $[n]$, there exists a monochromatic arithmetic progression of length $k$.

The original van der Waerden’s theorem says that for a given $k\geq 2$ and any finite coloring of the set of positive integers, $\mathbb{N}$, there exists a monochromatic arithmetic progression of length $k$, namely, there are $a,d\in\mathbb{N}$ such that $a,a+d,\dots,a+(k-1)d$, all have the same color. It is easy to see that the obvious generalization to the infinite case is not correct and in fact there is a 2-coloring of $\mathbb{N}$ such that for no $a,d\in\mathbb{N}$, $a,a+d,a+2d,a+3d,\dots$, all have the same color, in other words, there is no monochromatic arithmetic progression of infinite length.

Now recall that van der Waerden’s theorem can be deduced from the Hales-Jewett theorem, which itself has an infinite generalization, i.e., the Carlson-Simpson theorem. So in order to obtain a suitable explicit infinite generalization of van der Waerden’s theorem, one might ask: What does the Carlson-Simpson theorem say about arithmetic progressions? It is easily seen that the answer is exactly what we stated above as the infinite generalization of van der Waerden’s theorem. To see this, we first bring here the statements of the above mentioned theorems. We follow Walters’ paper [7]. Let $[k]=\{1,2,\dots,k\}$ and let $[k]^{N}$ be the set of all sequences $a_{1}a_{2}\dots a_{N}$ of length $N$ such that $a_{i}\in[k]$ for $i=1,\dots,N$. For $a\in[k]^{N},\gamma\subseteq\{1,\dots,N\}$ and $x\in[k]$, let $a\oplus x\gamma$ denote the sequence $b\in[k]^{N}$ defined by $a_{i}=b_{i}$ if $i\notin\gamma$ and $b_{i}=x$ otherwise. A combinatorial line is a set of the form $\{a\oplus x\gamma|1\leq x\leq k\}$. The set $\gamma$ is called the set of active coordinates. Now we can state the Hales-Jewett theorem:

Now observe that the following mapping

gives a bijection $[k]^{N}\rightarrow\{1,2,\dots,k^{N}\}$ and the image of the monochromatic line $\{a\oplus x\gamma|1\leq x\leq k\}$ is the arithmetic progression

Now define a word on an alphabet $[k]$ to be an element of $[k]^{N}$ for some $N$. For $N_{2}>N_{1}$, we say that a word $a^{2}\in[k]^{N_{2}}$ extends a word $a^{1}\in[k]^{N_{1}}$ and denote it by $a^{1}<_{e}a^{2}$, if $a^{2}_{i}=a^{1}_{i}$ for $i=1,\dots,N_{1}$. Let $Q(k)$ denote the set of all words on alphabet $[k]$.

We just mention here the case $n=2$ and leave the full case to the reader. In this case it is enough to see that the image of

under the above mentioned mapping is

Fix positive integers $k\geq 2$, and $c\geq 1$. We inductively define sequences of positive integers $\langle W_{n}:n\in\mathbb{N}\rangle$ and $\langle c_{n}:n\in\mathbb{N}\rangle$ (depending on $k,c$) as follows. Put $W_{1}=W(k,c),W_{n+1}=W(k,c_{n})$ and $c_{n}=c^{W_{n}\cdots W_{1}}$. Now let $I$ be an interval with $|I|=W_{1}$. Now from $I$, we inductively define a sequence of intervals $I_{n},n\in\mathbb{N}$ as follows. Let $I_{1}=I$ and

For instance for $n=2$, we have

which according to $|I_{1}|=W_{1}$, it is easily seen that $I_{2}$ is an interval with $|I_{2}|=W_{2}W_{1}$. Similarly for each $n\in\mathbb{N}$, we have that $I_{n}$ is an interval with $|I_{n}|=W_{n}\cdots W_{1}$. Obviously in the above definition, $I_{n}$ depends on $k,c,n,I$, so we denote it by $I_{n}=\mathcal{I}(I,n,k,c)$. If $k,c$ were fixed and were clear from the context, then we may denote it by $I_{n}=\mathcal{I}(I,n)$. We will also use the easy fact that for any positive integer $b$, the interval $\mathbb{T}^{b}\mathcal{I}(I,n,k,c)$ can be written in the form of $\mathcal{I}(J,n,k,c)$ for some interval $J$ with $|J|=W_{1}$. In fact due to the additive nature of the definition, we have $\mathbb{T}^{b}\mathcal{I}(I,n,k,c)=\mathcal{I}(\mathbb{T}^{b}I,n,k,c)$.

By an easy modification of the arguments, we can actually prove a stronger theorem which is correspondent to Carlson’s generalization [2] of the Carlson-Simpson theorem. See also Theorem 3 of [1].