An example showing that van der Waerden's theorem is not true for infinite arithmetic progressions

Question

One of the possible formulations of Van der Waerden's theorem is the following:

If $\mathbb N=A_1\cup \dots\cup A_k$ is a partition of the set $\mathbb N$, then one of the sets $A_1,\dots,A_k$ contains finite arithmetic progressions of arbitrary length.

In the other words, if we color the set of all positive integers by finitely many colors, there must be a monochromatic set containing arbitrarily long finite arithmetic progressions.

I assume that the same result is not true if we require that one of the sets contain an infinite arithmetic progression. (Otherwise this result would be well-known.)

What is an example showing that this stronger version of the above theorem is not true? (I.e., an example of a coloring of $\mathbb N$ by finitely many colors with no monochromatic infinite arithmetic progression.)

Answer 1

Let's build an example with just two sets in the partition, $A$ and $B$.

Enumerate the set $\mathbb{N}\times\mathbb{N}^{>0}$ as $\{(n_k,d_k)\mid k\in \mathbb{N}\}$ (think of $n$ as the starting point of an arithmetic progression and $d$ as the constant difference between the terms). We start with $A = B = \emptyset$ and ensure that at every stage of the construction (indexed by $k\in \mathbb{N}$), $A$ and $B$ are finite subsets of $\mathbb{N}$.

At stage $k$ of the construction, look at the pair $(n_k,d_k)$.

Case $1$: $n_k\in A$. Let $m$ be the least natural number such that $n_k + md_k\notin A$, and add $n_k+md_k$ to $B$.

Case $2$: $n_k\in B$. Repeat Case $1$, but with the roles of $A$ and $B$ reversed.

Case $3$: $n_k$ is not in $A$ or $B$. Add $n_k$ to $A$ and repeat Case $1$.

To complete stage $k$ of the construction, if the natural number $k$ is not in $A$ or $B$, add it to $A$.

At the end of the infinite construction, we have a partition of all of $\mathbb{N}$ into the two sets $A$ and $B$ (since each $k$ was either in $A$ or in $B$ at the end of stage $k$). Suppose there is an infinite arithmetic progression contained in $A$. It begins with some $n$ and the terms have constant difference $d$. Now $(n,d) = (n_k,d_k)$ for some $k\in \mathbb{N}$. But at the end of stage $k$, we ensured that some element $n+md$ of the arithemetic progression was in $B$, contradiction.

The symmetric argument shows that there is no infinite arithmetic progression contained in $B$.

Answer 2

The trick is to just do it. It suffices to consider the case $k=2$.

Enumerate the countably many pairs $(d,a)\in\Bbb N^2$ and handle them one by one, adding elements to $A_1$ and $A_2$ in the process (where both sets are initially empty). Note that at each step, $A_1,A_2$ are finite and disjoint. So given $(d,a)$, there are infinitely many $n\in\Bbb N$ with $a+nd\notin A_1\cup A_2$. Pick two distinct such numbers $n_1,n_2$ and add $a+n_1d$ to $A_1$ and add $a+n_2d$ to $A_2$. After that proceed to the next pair $(d,a)$.

In the end we have two disjoint sets $A_1,A_2$ such that each of them contains at least one element of every infinite arithmetic sequence $(a+nd)_n$, thus preventing the other set from containing the full infinite sequence. To actually obtain a partition which still has this property, the unused numbers of $\Bbb N$ can be added to either of the two components.

Answer 3

Color the integers black or white according to whether they have an even or an odd number of digits.

Answer 4

Define $$A = \{10^n + k: 1 \leq k\leq n\}=\{11, 101, 102, 1001, 1002, 1003, 10001, \ldots\}.$$ Clearly $A$ has natural density zero, and it clearly intersects every infinite arithmetic progression infinitely often, so the partition $\mathbb N = A \cup A^c$ is as wanted

Answer 5

I will add an example which is taken from the book Beautiful Mathematics by Martin Erickson, page 72. And it is rather similar to some of the answer which have already been posted.

$$\begin{array}{cccccccccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \circ & \bullet & \bullet & \circ & \circ & \circ & \bullet & \bullet & \bullet & \bullet & \circ & \circ & \circ & \circ & \circ & \bullet & \bullet & \bullet & \bullet & \bullet \end{array} $$

We start by coloring $1$ by one color. Then we color two following numbers by the other one. Next segment consist of three numbers of the first color, etc.

In this way we get longer and longer segments of each color.

If $a+nd$ is any arithmetic progression, then it will contain some numbers from both colors. Indeed there are two consecutive segments of lengths $d$ and $d+1$. Should this arithmetic progression be monochromatic, it would have to "skip over" one of those segments. But this is not possible, since the difference is $d$ and the length of each of these two segments is at least $d$.

Answer 6

Another beautiful example of a sequence with no infinite progressions is any Sturmian word, which can be understood as the sequence generated by taking some irrational number $\alpha$ and using the set $\Bbb N\cup\alpha\Bbb N$, with the elements of $\Bbb N$ colored red and the elements of $\alpha\Bbb N$ blue, and then putting them in increasing order to induce a coloring of $\Bbb N$. For example, with $\alpha=\varphi\approx 1.618$ we get $$\color{red}{1},\color{blue}{\varphi},\color{red}{2},\color{red}{3},\color{blue}{2\varphi},\color{red}{4},\color{blue}{3\varphi},\color{red}{5},\color{red}{6},\dots$$

which translates to the coloring of $\Bbb N$:

$$\color{red}{1},\color{blue}{2},\color{red}{3},\color{red}{4},\color{blue}{5},\color{red}{6},\color{blue}{7},\color{red}{8},\color{red}{9},\dots$$

Using the characterization of Sturmian words in terms of Beatty sequences, we can prove that it has no infinite APs. Suppose $w_n$ is a Sturmian word, treated as a sequence on $0,1$ representing red and blue. Then there exists an irrational $\alpha>0$ and $x\in\Bbb R$ such that $w_n=\lfloor \alpha n+x\rfloor-\lfloor \alpha(n-1)+x\rfloor$. Since the complement of a Sturmian word is also a Sturmian word, we can assume WLOG that the infinite AP is red, so suppose that $w_{dn+a}=0$ for $n\in\Bbb N$, meaning that $\lfloor \alpha (dn+a)+x\rfloor=\lfloor \alpha (dn+a-1)+x\rfloor$, or by setting $\beta=\alpha d$ and $x'=x+\alpha a$, $$\lfloor \beta n+x'\rfloor=\lfloor \beta n-\alpha+x'\rfloor,$$

which in particular means that there is no integer $m$ in $(\beta n-\alpha+x',\beta n+x')$. This in turn implies that the sequence $\beta n\pmod 1$ (the fractional part of $\beta n$) always misses the nonempty open interval $(-x',\alpha-x')$ (also $\bmod 1$), which contradicts the fact that $\beta n\pmod 1$ is dense (which is itself a good exercise, provable by the pigeonhole principle).

Answer 7

Consider a random $2$-coloring of the natural numbers. A given infinite arithmetic progression has probability zero of being monochromatic. As there are only countably many infinite arithmetic progressions, with probability one there is no monochromatic infinite arithmetic progression.

More generally, a random $k$-coloring of $\mathbb N$ will almost surely have no infinite arithmetic progression in which only $k-1$ colors occur.