I am studying the proof of Van der Waerden's theorem by Graham and Rothschild. I have tried to understand each step, but I need to fill in some gaps. Van der Waerden's theorem says that: $\forall k, r \in \mathbb{Z}^{+}, \; \exists W(k,r)\in \mathbb{Z}^{+}$ such that if the set of integers $\{1, \ldots, W(k,r)\}$ is partitioned into $r$ classes then at least one class contains a $k$-term arithmetic progression.
Proof: For $a,b\in \mathbb{Z}$ we define, $[a,b]:=\{x\in \mathbb{Z}: a\leq x \leq b\}$; Also we define $[0,l]^m := \{(x_1, \ldots , x_m) : \forall i \in [0,m], x_i \in [0,l]\}.$
Let $x,y \in [0,l]^m$. Then we say $x$ is $l$-equivalent to $y$,$(x\sim_{l} y)$ if $\exists i\in [0,m]$ such that $\forall j, i \leq j \leq m, x_j=l=y_j$ and $\forall j, 1\leq j < i, x_j \neq l , y_j\neq l$.
The $l$-equivalence classes are disjoint. They partition a proper subset of $[0,l]^m$. The remaining sequences are not used. I would like to clarify here the equivalence relation. My question is, is the relation $\sim_l$ an equivalence relation on $[0,l]^m$? Symmetric and Transitive properties are fine, but I need clarity on reflexive relations.
For any $l,m \in \mathbb{Z}^{+}$, we define the statement $S(l,m): $ $\forall r \in \mathbb{Z}^{+}, \exists N(l,m,r) \in \mathbb{Z}^{+}$ so that $\forall C:[1,N(l,m,r)] \longrightarrow [1,r], \exists a, d_1, d_2, \ldots , d_m \in \mathbb{Z}^{+}$ such that $C(a+\sum_{i=1}^{m} x_i d_i)= constant$ on each $l$-equivalence class of $[0,l]^m$; where $\forall i\in [1,m], x_i \in [0,l].$
The statement $S(l,1)$ is equivalent to Van der Waerden's theorem for $l$-term arithmetic progressions.
Now, we prove that $\forall l,m \in \mathbb{Z}^{+}, S(l,m)$ holds. We prove it by double induction on $l$ and $m$. For $l=1$ and $m=1$, we have $S(1,1)$. Take any $r \in \mathbb{Z}^{+}$ and $r > 1$. Choose $N(1,1,r)=r$. Take any map $C:[1,r] \longrightarrow [1,r]$. Choose any $a,d_1 \in \mathbb{Z}^{+}$ such that $a, a+d_1 \in [1,r]$. As there are only two equivalence classes, $(0)$ and $(1)\;$, $C(a+0.d_1)=C(a)=constant$ and $C(a+1.d_1)=C(a+d_1)=constant$ on each $1$-equivalence class of $[0,1]$. So, $S(1,1)$ holds.
Now, to prove the statement $S(l,m)$, we show,
- $S(l,m)$ holds for some $m \geq 1$ $\implies S(l,m+1)$ holds.
- $S(l,m)$ holds $\forall m \geq 1$ $\implies S(l+1,1)$ holds.
For a fixed $l \in \mathbb{Z}^{+}$, let $S(l,m)$ holds for some $m \in \mathbb{Z}^{+}$. For a fixed $r \in \mathbb{Z}^{+}$, let $M=N(l,m,r)$ and $M'=N(l,1,r^M)$ and suppose that $C: [1,MM'] \longrightarrow [1,r]$ is given. Now we take partition of $[1,MM']$ into $M'$ blocks of length $M$, i.e. $[1,MM']=[1,M]\cup[M+1,2M]\cup \ldots \cup [MM'-M+1,MM']$. The $i$-th element in the 1st block is $i$ and so, the $i$-th element in the $x$-th block is $i+(x-1)M$ and the $i$-th element in the $y$-th block is $i+(y-1)M$. Define $C':[1,M'] \longrightarrow [1,r^M]$ such that $C'(x)=C'(y) \iff C(i+(x-1))=C(i+(y-1)).$
By inductive hypothesis, as $S(l,1)$ is true, we have assumed. For a fixed $r \in \mathbb{Z}^{+}$ we chose $M'=N(l,1,r^M)$ such that given any map $C: [1, M'] \longrightarrow [1,r^M], \exists a', d' \in \mathbb{Z}^{+}$ such that $C(a'+x_1d')$=constant on each $l$-equivalence class of $[0,l]$; where $x_1$ belongs to $[0,l]$. Here, we have two equivalence classes, one class contains $(0),(1),\ldots,(l-1)$ and another class contains $(l)$.
So, $C(a')=C(a'+d')=\ldots=C(a'+(l-1)d')=constant$ and $C(a'+ld')=constant$.
Now, consider the $a'$-th interval $I_a'$(say). As, $|I_a'|=M$, and by assumption $S(l,m)$ holds for the interval $I_a'$. So, $\exists a, d_2,\ldots, d_{m+1} \in \mathbb{Z}^{+}$, so that, $C(a+\sum_{i=2}^{m+1}x_i d_i)=constant$; where $\forall i \in [2,m+1], x_i \in [0,l]$.
Let $d'_i=d_i,\; \forall i\in [2,m+1]$ and $d'_1= d'M$. Then the element $(a+\sum_{i=2}^{m+1}x_i d'_i+x_1d'_1)$ has the same position in the block $I_{a'+x_1d'}$ as the element $(a+\sum_{i=2}^{m+1}x_i d_i)$ in the block $I_{a'}$. Then $C(a+\sum_{i=2}^{m+1}x_i d'_i)+x_1d'_1)= constant$ on each $l$-equivalence class of $[0,l]^{m+1}.$
Now, for the choice of $N(l,m+1,r)=MM'$, $S(l,m+1)$ holds. (Is this correct?)
Hence, $S(l,m+1)$ holds for all $m \in \mathbb{Z}^{+}$.
Now, we prove 2. $S(l,m)$ holds $\forall m \in \mathbb{Z}^{+} \implies S(l+1,1)$ holds.
For a fixed $r\ \in \mathbb{Z}^{+}$, let $C: [1, N(l,r,r)] \longrightarrow [1,r]$ be given. So, $\exists a, d_1,\ldots, d_r$ such that $C(a+\sum_{i=1}^{r}x_id_i)$=constant on each $l$-equivalence class of $[0,l]^r$. There are $r+1$ equivalence classes, $(l,l,\ldots,l),(0,l,\ldots,l),(0,0,l,\ldots,l),\ldots,(0, \ldots,0)$. $(0,0,l,\ldots,l) \sim_{l}(\neq l, \neq l,l,\ldots,l)$. As $|Range(C)|=r$, by Pigeon-hole principle $\exists 1 \leq u<v \leq r+1$ such that $C(a+\sum_{i=u}^{r}l d_{i})=C(a+\sum_{i=v}^{r}l d_i).$ We want to prove that $\forall r \in \mathbb{Z}^{+} \exists N(l+1,1,r)$ such that $\forall C: [1,N(l+1,1,r)] \longrightarrow [1,r], \exists a', d', \in \mathbb{Z}^{+}$ so that $C(a'+xd')$=constant in each $(l+1)$-equivalence class of $[0,l+1]$. We choose $a'=(a+ \sum_{i=v}^{r} ld_i)$ and $d'=\sum_{i=u}^{v-1}d_i.$ Now, consider $C(a'+xd')$, where $x \in [0,l]$. As $m=1$, here, there are two equivalence classes. One class contains $(0),(1),\ldots,(l)$ and another class contains $(l+1)$. In the 2nd class, there is only one element, so $C(a'+(l+1)d')$=constant.
In the 1st class for $x=(0),(1),\ldots,(l-1)$, by assumption $C(a'+xd')$=constant, and for $x=(l)$, $C(a'+ld')=C(a'+0.d')$ by Pigeonhole principle. So, $C(a'+xd')$=constant for $x\in [0,l]$.
Therefore, $C(a'+xd')$=constant for each $(l+1)$-equivalence class of $[0,l+1]$, where $x\in [0,l]$.
Now $a'+(l+1)d'=a+l\sum_{i=u}^{r}d_i + \sum_{i=u}^{v-1}d_i$.
Now, should I choose $N(l+1, 1, r)=N(l,r,r,)+\sum_{i=u}^{v-1}d_i$?
This will prove $S(l+1,1)$.
I know this has become very long, but I need to understand each step clearly. I need help. Thank you for your time and consideration.