Lesson 3

Proof. We prove that, for any positive integers \(k\) and \(r\), there exists a number \(W(k,r)\) such that for any \(r\)-coloring of the set \([W(k,r)]\), there exists a monochromatic arithmetic progression of length \(k\).

Let \(A_{1}, \dotsc, A_{s}\) be disjoint arithmetic progressions of length \(k-1\), where \[A_{i}=\{a_{i}, a_{i}+d_{i}, \dotsc, a_{i}+(k-2)d_{i}\}.\] We will say that \(A_{1}, \dotsc, A_{s}\) are focused at \(f\) if \(f\) is the (missing) \(k\)-th term of each of the progressions: \[f=a_{i}+(k-1)d_{i} \text{ for all }i \in [s].\] If each of the \(s\) progressions is monochromatic and all \(s\) colors are different, we will say that they are color-focused at \(f\). A simple but crucial idea: if \(s=r\) and in an \(r\)-coloring of \(\mathbb{Z}_{>0}\) there are \(s\) color-focused arithmetic progressions of length \(k-1\), then there is also a monochromatic arithmetic progression of length \(k\). Indeed, their focus \(f\) is colored in one of the \(r\) colors, so the progression of its color can be extended.

The figure below shows an example: if there are only two colors, then whatever the color of the element \(f\) is, there will be a monochromatic arithmetic progression of length \(4\).

We will prove by induction on \(k\) the statement "for any \(r\), the number \(W(k,r)\) is finite". The base case \(k=2\) is shown easily: \(W(2,r)=r+1\) for any \(r\) (by the pigeonhole principle). For fixed \(r\), we will derive the finiteness of \(W(k,r)\) from the finiteness of the number \(W(k-1,t)\), where \(t\) will be much larger than \(r\), and another statement, which we will also prove by induction (but on a different parameter). This will be a nested induction. Specifically, by induction on \(s \le r\), we will prove the existence of a number \(V(k,r,s)\) such that in any \(r\)-coloring of \([V(k,r,s)]\), there is

• either a monochromatic arithmetic \(k\)-progression;


• or color-focused arithmetic \((k-1)\)-progressions \(A_{1}, \dotsc, A_{s}\), whose common focus also falls within the set \([V(k,r,s)]\).

The base case \(s=1\) is easily checked: \(V(k,r,1) \le 2W(k-1,r)\), because in any \(r\)-coloring of \([W(k-1,r)]\), there is an arithmetic \((k-1)\)-progression whose focus is no greater than \(2W(k-1,r)\). For the induction step, assume that \(V(k,r,s-1)\) is finite. We will prove that \[V(k,r,s) \le 2V(k,r,s-1)W(k-1,r^{V(k,r,s-1)}).\] To do this, consider an \(r\)-coloring of \([N]\), where \(N=2V(k,r,s-1)W(k-1,r^{V(k,r,s-1)})\). We will divide the set \([N]\) into \(2W=2W(k-1,r^{V(k,r,s-1)})\) blocks of length \(V=V(k,r,s-1)\). There are \(r^{V}\) ways to color a block, so by the (outer) induction hypothesis, we conclude that among the first \(W\) blocks, there is an arithmetic \((k-1)\)-progression \[B_{l}, B_{l+m}, \dotsc, B_{l+(k-2)m}.\] The missing \(k\)-th term of this progression falls within the first \(2W\) blocks.

Now consider the block \(B_{l+jm}\). Its length is \(V=V(k,r,s-1)\) and it is colored in \(r\) colors (and colored exactly the same as the other blocks of the progression). By the (inner) induction step, we conclude that within the block \(B_{l+jm}\), there are \(s-1\) color-focused arithmetic \((k-1)\)-progressions along with their common focus. Assume that they have colors \(i=1,\dotsc,s-1\). Then in the block \(B_{l+jm}\) (where \(0 \le j \le k-2\)), the progression of color \(i\) (where \(i \in [s-1]\)) has the form \[\{a_{i}+jmV, a_{i}+jmV+d_{i},\dotsc, a_{i}+jmV+(k-2)d_{i}\},\] and the common focus of these progressions in this block is \(f+jmV\). If the focuses \(f+jmV\) (where \(0 \le j \le k-2\)) are colored in one of the colors from \([s-1]\), then we immediately get a monochromatic arithmetic \(k\)-progression. Therefore, we will assume that the focuses are colored in another color—for example, in color \(s\). Then we can construct \(s\) color-focused arithmetic \((k-1)\)-progressions as follows:

• for each \(i \in [s-1]\), the progression \(A_{i}\) will take one element from the progression of color \(i\) from each of the \(k-1\) blocks (each time shifting by \(mV\) and by \(d_{i}\)): \[\{a_{i}, a_{i}+(d_{i}+mV), \dotsc, a_{i}+(k-2)(d_{i}+mV)\};\]


• the progression \(A_{s}\) will consist of the focuses of the blocks (recall that they are all colored in color \(s\)): \[\{f, f+mV, \dotsc, f+(k-2)mV\} \ .\]