A corollary of Van der Waerden's theorem.

Question

The following is the well known Van der Waerden theorem:

Th. Given positive integers $k,r$ there exists positive integer $N=N(k,r)$ such that if $\{1,2,...,N\}$ is $r$-colored then there exists a monochromatic AP of length $k$.

Now consider the following statement $S(k,m)$:

Th. Given any two positive integers $k,m$ there exists a positive integer $p=p(k,m)$ such that for any $p$ positive integers $a_1<a_2<...<a_p$ with the property that $|a_{j+1}-a_j|\leq m$ for all $j=1,2,...,p-1$ ,there exists an AP within $a_1,a_2,...,a_p$ of length $k$.

Now our instructor proved that Van der Waerden $\implies S(k,m).$

I have some difficulty in understanding the proof.I think I am not getting the main philosophy.I give the proof below:

Proof: Assume that Van der Waerden theorem is true.

Let $p=p(k,m)=N(k,m)-(m-1)$,we will show that this $p$ does the job.

Let $A_0=\{a_1,a_2,...,a_p\}$ be a set of positive integers with the property that $|a_{j+1}-a_j|\leq m$ for all $1\leq j\leq p-1$.

Define $A_1=\{a_1+1,a_2+1,...,a_p+1\}\setminus A_0$

$A_2=\{a_1+2,a_2+2,...,a_p+2\}\setminus A_0\cup A_1$

$\vdots$

$A_{m-1}=\{a_1+(m-1),...,a_p+(m-1)\}\setminus A_0\cup A_1\cup\dots\cup A_{m-2}$

Then $\{a_1,a_1+1,...,a_p+(m-1)\}=A_0\cup A_1\cup\dots \cup A_{m-1}$ $($Why?$)$

Now $a_p+(m-1)-a_1+1=a_p+m-a_1\geq p+a_1-1+m-a_1=N(k,m)$ $($ Why?$)$

which completes the proof.$($Why?$)$

I do not really understand what is going on here.I have marked the lines I do not understand by writing 'Why?'.Please go through the proof and help me to digest the essence of the proof.

Answer 1

For the first point, note that any two consecutive $a_i,a_{i+1}\in A_0$ are distant by at most $m$. Then $A_1$ is the set $A_0$ with $1$ added to all the elements (and removing elements already in $A_0$). So in $A_0 \cup A_1$, any two consecutive elements are distant by at most $m-1$. Is this okay ? Build an example, e.g. $A_0=\{1,5,8,9\}$ with $m=4$, and see how $A_1$ is, and then $A_0 \cup A_1$, it should become clear. Then repeat the process. At the end, $A_0\cup\ldots A_{m-1}$ includes all numbers possible from $a_1$ to $a_p+(m-1)$

The second point is a simple computation. Not sure where is your issue (recall the definition of $p=N(k,m)-(m-1)$). Note that $a_p+(m−1)−a_1+1$ is the length of $\{a_1,\ldots,a_p+(m-1)\}$.

The last point is the interesting one. Remember that we want to prove Van der Waerden $\Rightarrow S(k,m)$. We have $\{a_1,a_1+1,\ldots,a_p+(m−1)\} = A_0\cup A_1\cup\ldots A_{m−1}$, and by the above computation, this means that $A_0\cup A_1\cup\ldots A_{m−1}$ contains at least $N(k,m)$ elements. So we can apply Van der Waerden to the set $A_0\cup A_1\cup\ldots A_{m−1}$. Do we see what would be a natural coloring of this set ?

Color the set $A_0\cup A_1\cup\ldots A_{m−1}$ such that each $A_i$ is monochromatic, each with a distinct color (note that the sets are disjoint, so this is well defined).

I now claim that the existence of a monochromatic arithmetic progression of length $k$ in this coloring implies that there is such $k$-AP in $A_0$. Do you see why ?

By definition of the coloring, the monochromatic $k$-AP must be fully contained in $A_i$ for some $i$. But element of $A_i$ are elements of $A_0$ after adding a constant $i$. So this means that $A_0$ also contains the 'same' $k$-AP, shifted by $-i$.

---

Edit to answer the comment : how to show that $\{a_1,a_1+1,\ldots,a_p+(m−1)\}\subseteq A_0 \cup\ldots\cup A_{m−1}$.

Let $x \in \{a_1,a_1+1,\ldots,a_p+(m−1)\}$. If $x\geq a_p$ then $x = a_p + i$ for some $i\in\{0,\ldots,m-1\}$, hence $x\in A_i$.

If $x\in[a_1,a_p)$, then for some $j\in\{1,\ldots,p-1\}$, $x\in[a_j,a_{j+1})$.

Using $\vert a_{j+1} - a_{j}\vert \leq m$, this implies that $x=a_j+i$ for some $i \in \{0,\ldots,m-1\}$. Hence $x\in A_i$ or $x\in A_k$ for some $k<i$.