Theorem 47.5.5 (van der Waerden).label For every $k \in \natp$ and finite colouring $c: \integer \to \bracsn{1, \cdots, r}$, there exists $a \in \integer$ and $n \ge 1$ such that $\bracsn{a + jn|0 \le j \le k}$ is monochromatic. In other words, there exists monochromatic arithmetic progressions of arbitrary length.
Proof. Let $A = \bracsn{1, \cdots, k}$ and
By the Hales-Jewett Theorem, there exists $N = N(r)$ such that $\tilde c$ contains a monochromatic combinatorial line. In other words, there exists a variable word $v \in (A \sqcup \bracsn{*})^{N} \setminus A^{N}$ such that the set
is monochromatic. Let $J = \bracsn{1 \le j \le N|v_j = *}$, then as $v \not\in A^{N}$, $J$ is non-empty. Take $n = |J|$ and $a = \sum_{j \not\in J}v_{j}$, then for each $1 \le i \le k$,
In particular, for each $1 \le i, i' \le k$,
Therefore the arithmetic progression $\bracsn{a + in|1 \le i \le k}$ is monochromatic.$\square$
Post a Comment