14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I should add that I know such example. But I think that this question might be interesting for somebody who learns about this result, so it might be good to have the question and the answer on this site. Since some users expressed the opinion that in situations like this it might be better to wait before the OP answers the question by themselves (see this answer and some comments in the same discussion), I will wait a bit. Of course, if nobody posts an answer, I will add an answer myself. $\endgroup$ – Martin Sleziak Oct 19 '15 at 17:28
  • $\begingroup$ Your statement of the theorem is inaccurate . It could be be understood as $ "\exists i (\forall k (A_i $ contains a progression of length $k$)." Your next sentence is equivalent to the correct version : $\forall k \exists i (A_i $ contains a progression of length $k$.) $\endgroup$ – DanielWainfleet Oct 19 '15 at 19:23
  • $\begingroup$ @user254665 You are right. My reformulation using colorings was incorrect. I have edited the post. $\endgroup$ – Martin Sleziak Oct 19 '15 at 19:29
  • 1
    $\begingroup$ It is just as easy to prove the stronger statement: there is a coloring of $\mathbb N$ by $\aleph_0$ colors with that each color occurs in every infinite arithmetic progression. $\endgroup$ – bof Oct 21 '15 at 20:57
21
$\begingroup$

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

$\endgroup$
21
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Good example. Of course there is no need to consider "consecutive segments", what matters is that there are arbitrarily long monochromatic segments of each color. $\endgroup$ – bof Oct 21 '15 at 5:52
11
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is so beautiful $\endgroup$ – baba Oct 20 '15 at 18:09
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @Ypnypn I won't address the question of whether it is "clear", but the reason it is true is because letting $d_n(A)=\frac{A\cap\{1,\dots,n\}}{n}$ we have, for all $10^m\le n<10^{m+1}$, $d_n(A)\le d_{10^m+m}(A)=\dfrac{\sum_{k\le m}k}{10^m+m}\to 0$ because the numerator is quadratic and the denominator is exponential. $\endgroup$ – Mario Carneiro Oct 20 '15 at 1:53
  • $\begingroup$ @MarioCarneiro That part I understood. The second part I didn't get until now. $\endgroup$ – Ypnypn Oct 20 '15 at 3:00
  • $\begingroup$ @Ypnypn Consider taking the elements of $A$ mod $d$. If $A$ is disjoint from an infinite AP, then (after ignoring finitely many initial numbers) $A$, reduced mod $d$, will not have any representative for some $a$, i.e. $(x\bmod d)\ne a$ for all sufficiently large $x\in A$. But each run of consecutive numbers in $A$ gets progressively longer, covering more elements, until after stage $d$ you get all representatives getting hit in each stage. Thus $A$ intersects every infinite AP infinitely often. $\endgroup$ – Mario Carneiro Oct 20 '15 at 12:55
  • $\begingroup$ @MarioCarneiro Okay, that makes sense. $\endgroup$ – Ypnypn Oct 20 '15 at 13:14
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.