Skip to main content

Section 3.3 Proof of van der Waerden's Theorem

Mathematics is really there for you to discover. — Ron Graham, American mathematician, 1935 — 2020

Recall Theorem 3.2.6:

Van der Waerden's Theorem - any number of colours, length 3: Let \(k\in \mathbb{N}\text{.}\) Any \(k\)-colouring of positive integers contains a monochromatic 3-term arithmetic progression. Moreover, there is a natural number \(N\) such that any \(k\) colouring of the segment of positive integers \([1,N]\) contains a monochromatic 3-term arithmetic progression.

  1. Note: The smallest \(N\) guaranteed by the theorem is annotated by \(W(3,k)\text{.}\)

  2. Proof - the main tool: Colour-focused arithmetic progressions and spikes: Let \(c\) be a finite colouring of an interval of positive integers \([1,m]\) and \(l,r\in \mathbb{N}\text{.}\) We say that the set of \(l\)-term arithmetic progressions \(A_1,A_2,\ldots,A_r\text{,}\) i.e., for all \(i\in[1,r]\) we have, for some \(a_i,d_i\in \mathbb{N}\text{,}\)

    \begin{equation*} A_i=\{ a_i+jd_i:j\in[0,l-1]\} \end{equation*}

    is colour-focused at \(f\in \mathbb{N}\) if

    1. \(A_i\subseteq [1,m]\) for each \(i\in[1,r]\text{.}\)

    2. Each \(A_i\) is monochromatic.

    3. If \(i\not= j\) the \(A_i\) and \(A_j\) are not of the same colour.

    4. \(a_1+ld_1=a_2+ld_2=\cdots =a_r+id_r=f\text{.}\)

    We call elements of a colour-focused set spikes.

    Figure 3.3.1. \(\color{red}{\{1,4\}}\) and \(\color{blue}{\{3,5\}}\) are colour-focused at 7.

  3. Proof - a detail: What happens when \(r=k\text{?}\)

    Figure 3.3.2. What happens when \(r=k\text{?}\) Do you see how a monochromatic \(3\)-term arithmetic progression emerges?

Recall that Conjecture 3.2.4 was about two colours and a monochromatic arithmetic progression of any (finite) length:

Baudet's Conjecture: If the sequence of integers \(1,2,3,\ldots\) is divided into two classes, at least one of the classes contains an arithmetic progression of \(l\) terms, no matter how large the length \(l\) is.

So what about any finite number of colours and a monochromatic arithmetic progression of any (finite) length?

Definition 3.3.4.

The smallest \(N\) guaranteed by Theorem 3.3.3 is annotated by \(W(l,k)\text{.}\)

We have seen that \(W(3,2)=9\) and that \(W(3,k)\) exists for any \(k\in \mathbb{N}\text{.}\)

  1. Strategy: We use induction on \(l\text{.}\)

  2. The base case: We already know that \(W(l,k)\) exists if \(l\leq 3\) and \(k\in \mathbb{N}\text{,}\) i.e., that the claim of the theorem is true for \(l=1,2,3\text{.}\)

  3. The inductive step: Let \(l\geq 4\) be such that \(W(l-1,k)\) exists for all \(k\text{.}\)

    1. Claim: For all \(r\leq k\text{,}\) there exists a natural number \(M\) such that whenever \([1,M]\) is \(k\)-coloured, either there exists a monochromatic \(l\)-term arithmetic progression or there exist \(r\) coloured-focused \((l-1)\)-term arithmetic progressions.

      1. The base case: Let \(r=1\) and let \(M=2W(l-1,k)\text{.}\) Any \(k\)-colouring of \([1, M]\) contains a monochromatic \(l\)-term arithmetic progression or at least one coloured-focused \((l-1)\)-term arithmetic progression focused at some \(f\in [1,M]\text{.}\)

        Figure 3.3.5. Any \(k\)-colouring of the set \([1,M]\) produces or a monochromatic \(l\)-term arithmetic progression or one coloured-focused \((l-1)\)-term arithmetic progression.

      2. The inductive step: Suppose that \(r\in [2,k]\) is such that there is an \(M\) such that any \(k\)-colouring of \([1,M]\) contains a monochromatic \(l\)-term arithmetic progression or \(r-1\) ‘spikes’, i.e., \(r-1\) colour focused \((l-1)\)-term arithmetic progressions.

        Figure 3.3.6. Where are you?

      3. Observe that any \(k\)-colouring of \([1,2M]\) contains a monochromatic \(l\)-term arithmetic progression or at least \(r-1\) coloured-focused \((l-1)\)-term arithmetic progression focused at some \(f\in [1,2M]\text{.}\) See Figure 3.3.7.

        Figure 3.3.7. There are \(r-1\) spikes.

      4. Consider the interval of positive integers \([1, 2M\cdot W(l-1, k^{2M})]\text{.}\) (How do we know that \(W(l-1, k^{2M})\) exists?) Divide this interval into \(W(l-1, k^{2M})\) consecutive blocks \(B_i\text{,}\) \(1\leq i\leq W(l-1, k^{2M})\text{,}\) of length \(2M\text{.}\) See Figure 3.3.8.

        Figure 3.3.8. The interval \([1, 2M\cdot W(l-1, k^{2M})]\) is divided into \(W(l-1, k^{2M})\) consecutive blocks \(B_i\text{,}\) \(1\leq i\leq W(l-1, k^{2M})\text{,}\) of length \(2M\text{.}\)

      5. Why \(W(l-1, k^{2M})\text{?}\)

      6. Suppose that \(c\) is a \(k\)-colouring of \([1, 2M\cdot W(l-1, k^{2M})]\) that does not contain a monochromatic \(l\)-term arithmetic progression. Each block \(B_i\) is \(k\)-coloured in one of the possible \(k^{2M}\) ways. See Figure 3.3.9.

        Figure 3.3.9. The \(k\)-colouring \(c\) of \([1, 2M\cdot W(l-1, k^{2M})]\) induces a \(k^{2M}\)-colouring of \([1,W(l-1,k^{2M})]\text{.}\)

      7. Any \(k^{2M}\)-colouring of \([1,W(l-1,k^{2M})]\) contains a monochromatic \((l-1)\)-term arithmetic progression. See Figure 3.3.10.

        Figure 3.3.10. The \(k^{2M}\)-colouring of \([1,W(l-1,k^{2M})]\) induced by the colouring \(c\) contains a monochromatic \((l-1)\)-term arithmetic progression. This means that there are \(l-1\) blocks \(B_{i_j}\text{,}\) \(1\leq j\leq l-1\text{,}\) that are coloured by \(c\) in the same way and they are equally spaced between each other.

      8. Every \(B_{i_j}\text{,}\) \(1\leq j\leq l-1\text{:}\)

        • is \(k\)-coloured the same way

        • contains \(r-1\) spikes (monochromatic \((l-1)\)-term arithmetic progressions) together with their focus. Note that there are no two spikes of the same colour (by definition!) and that the focus is of a different colour. (Why?)

      9. The key step! The \(r^{\text{ th } }\) spike appears! See Figures 3.3.11 and Figure 3.3.12 .

        Figure 3.3.11. The \(k^{2M}\)-colouring of \([1,W(l-1,k^{2M})]\) induced by the colouring \(c\) contains a monochromatic \((l-1)\)-term arithmetic progression. This means that there are \(l-1\) blocks \(B_{i_j}\text{,}\) \(1\leq j\leq l-1\text{,}\) that are coloured by \(c\) in the same way and they are equally spaced between each other.

        Take a closer look:

        Figure 3.3.12. Do you see how \(r-1\) initial spikes generate \(r\) new spikes?

    2. Where are we?

      Figure 3.3.13. Almost there!

    3. Let \(r=k\text{:}\)

      Figure 3.3.14. Done!

Resources.

  1. van der Waerden's theorem - Wikipedia

  2. Ramsey Theory by I. Leader pp 4–6

  3. The ergodic and combinatorial approaches to Szeméredi's theorem by Terrence Tao, pp 4–6

  4. Proof of van der Waerden's Theorem in Nine Figures by A. Blondal and V. Jungic

  5. Van der Waerden's theorem on arithmetic progressions by R. Swan

  6. Commentary by N. G. de Bruijn