# A corollary of Van der Waerden's theorem.

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

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.

• But how do I formallly prove that $A_0\cup...\cup A_{m-1}$ is precisely the set $\{a_1,a_1+1,...,a_p+(m-1)\}$? Commented Sep 7, 2022 at 5:43
• In particular how to show that $\{a_1,a_1+1,...,a_p+(m-1)\}\subset A_0\cup...\cup A_{m-1}$? Commented Sep 7, 2022 at 5:45