Skip to main content

Section 3.2 van der Waerden's Theorem: \(3\)-term APs

Say what you know, do what you must, come what may. — Sofia Vasilyevna Kovalevskaya, Russian mathematician, 1850 — 1891

Three Reminders.

  1. An \(l\)-term arithmetic progression is any set of the form

    \begin{equation*} a,a+d,a+2d,\ldots, a+(l-1)d \end{equation*}

    where \(a,d\in \mathbb{R}\text{,}\) \(d\not= 0\text{.}\)

  2. A \(k\)-colouring of a set \(A\) is any function

    \begin{equation*} c:A\to \{1,2,\ldots,k\}=[1,k]\text{.} \end{equation*}

  3. If \(c\) is a \(k\)-colouring of the set \(A\) and if \(B\subseteq A\) is such that for any \(x,y\in B\)

    \begin{equation*} c(x)=c(y) \end{equation*}

    then we say that the set \(B\) is monochromatic.

Challenge. Colour with 2-colours avoiding monochromatic 3-term arithmetic progressions:

Figure 3.2.1. Colour each set with 2-colours avoiding monochromatic 3-term arithmetic progressions

Check and Extend: Check if the following 3-colouring of the the set \(\{1,2,\ldots, 17\}\) avoids monochromatic 4-term arithmetic progressions:

Figure 3.2.2. Can you find a monochromatic 4-term arithmetic progression?
Figure 3.2.3. Can you colour numbers 18 and 19 to avoid a monochromatic 4-term arithmetic progression?

Question: Do you think that it is possible to extend the colouring above (and keep it with no monochromatic 4-term arithmetic progression) to the interval \([1,25]\text{?}\) \([1,50]\text{?}\) \([1,100]\text{?}\) Forever?

“Beweis einer Baudetschen Vermutung” = “Proof of a Baudet Conjecture”

In van der Waerden's Words:

Once in 1926, while lunching with Emil Artin and Otto Schreier, I told them about the conjecture of the Dutch mathematician Baudet: If a sequence of integers of \(1,2,3\text{,}\) etc. is divided into two classes, at least one of the classes contains an arithmetic progression of \(l\) terms - \(a,a+b,a+2b, \ldots, a+(l-1)b\) - no matter how large the length \(l\) is. After lunch we went into Artin's office … and tried to find a proof.

… One of the main difficulties in the psychology of invention is that most mathematicians publish their results with condensed proofs, but do not tell us how they found them. In many cases they do not even remember their original ideas. Moreover, it is difficult to explain our vague ideas and tentative attempts in such a way that others can understand them.

… All ideas we formed in our minds were at once put into words and explained by little drawings on the blackboard. We represented the integers \(1,2,3\text{,}\) etc. in two classes by means of vertical strokes on two parallel lines. Whatever one makes explicit and draws is much easier to remember and to reproduce than mere thoughts.

(For the whole essay “How the proof of Baudet's conjecture was found” see [7].)

Note: The smallest \(N\) guaranteed by the theorem is annotated by \(W(3,k)\text{.}\) We have seen that \(W(3,2)=9\text{.}\)

  1. 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. \(\displaystyle a_1+ld_1=a_2+ld_2=\cdots =a_r+ld_r=f\text{.}\)

    We call elements of a colour-focused set spikes.

    Figure 3.2.7. \(\{1,4\}\) and \(\{3,5\}\) are colour-focused at 7.

  2. Warm up - \(k=2\text{:}\)

    1. Consider a two colouring of \([1,3]\text{.}\)

      Figure 3.2.8. Any 2-colouring of the set \(\{ 1,2,3\} =[1,3]\) produces or a monochromatic 3-term arithmetic progression or one coloured-focused 2-term arithmetic progression.

    2. Consider the interval of positive integers \([1, (2\cdot 3)\cdot (2^6+1)]=[1,390]\text{.}\) Divide this interval into 65 consecutive blocks of length 6. See Figure 3.2.9.

      Figure 3.2.9. \((2\cdot 3)\cdot (2^{2\cdot 3}+1) = 65\) consecutive blocks of length \(2\cdot 3=6\text{.}\)

    3. In how many ways can we 2-colour six consecutive integers?

    4. Let \(c\) be a 2-colouring of the interval \([1,2\cdot 390]\text{.}\)

    5. Every 2-colouring of \([1,780]\) contains a monochromatic 3-term arithmetic progression! See Figure 3.2.10.

      Figure 3.2.10. Every 2-colouring of \([1,780]\) contains a monochromatic 3-term arithmetic progression!

    6. Thus \(W(3,2)\leq 780\text{.}\)

  3. Next we consider a \(k\)-colouring, for any \(k\geq 2\text{.}\)

    1. Strategy: We use induction on \(r\) to prove the following statement:

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

    2. The base case: Take \(r=1\) and \(n=k+1\text{.}\) See Figure 3.2.11.

      Figure 3.2.11. The base step: If the interval \([1,k+1]\) is \(k\)-coloured then there is a monochromatic \(3\)-term arithmetic progression or one coloured-focused 2-term arithmetic progression.

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

    Figure 3.2.12. The inductive step: For \(1\lt r\leq k\) there is an \(n\) such that any \(k\)-colouring of \([1,n]\) contains a monochromatic \(3\)-term arithmetic progression or \(r-1\) ‘spikes’, i.e., \(r-1\) colour focused 2-term arithmetic progressions.

    1. How many different \(k\)-colourings of the interval \([1,2n]\) are there?

    2. Consider the interval of positive integers \([1, (2\cdot n)\cdot (k^{2n}+1)]\text{.}\) Divide this interval into \(k^{2n}+1\) consecutive blocks of length \(2n\text{.}\) Call those blocks \(B_i\text{,}\) \(1\leq i\leq k^{2n}+1\text{.}\) See Figure 3.2.13.

      Figure 3.2.13. The interval \([1,2n(k^{2n}+1)]\) is divided in \(k^{2n}+1\) blocks of length \(2n\) and \(k\)-coloured.

    3. Let \(c\) be a \(k\)-colouring of the interval \([1, (2\cdot n)\cdot (k^{2n}+1)]\text{.}\) Suppose that \(c\) does not contain a monochromatic 3-term arithmetic progression.

    4. Note that by the inductive hypothesis each block \(B_i\) contains \(r-1\) spikes together with their focus. See Figure 3.2.14.

      Figure 3.2.14. Each block \(B_i\) contains \(r-1\) spikes together with their focus.

    5. There must be two blocks coloured in the same way. See Figures 3.2.15 and Figure 3.2.16.

      Figure 3.2.15. There must be two two blocks coloured in the same way. Each of them contains \(r-1\) spikes together with their focus. \(r\) spikes with the same focus emerge.

      Figure 3.2.16. A closer look: Two pairs of spikes in \(B_i\) and \(B_j\) produce a new pair of spikes.

    6. This completes the induction step:

    7. What happens when \(r=k\text{?}\) See Figure 3.2.17.

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

BIG Question. How big is \(W(3,k)\text{?}\)

Resources.

  1. van der Waerden's theorem - Wikipedia

  2. Ramsey Theory by I. Leader

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

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

  5. Commentary by N. G. de Bruijn