Section 3.5 van der Waerden's Theorem: A Few Related Questions
Never measure the height of a mountain until you have reached the top. Then you will see how low it was. — Dag Hjalmar Agne Carl Hammarskjöld, Swedish diplomat, economist, and author, 1905 –1961
Recall Theorem 3.3.3:
Van der Waerden's Theorem: Let \(l,k\in \mathbb{N}\text{.}\) Any \(k\)-colouring of positive integers contains a monochromatic \(l\)-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 \(l\)-term arithmetic progression.
Question 3.5.1.
Is it true that any 2-colouring of positive integers contains an infinite monochromatic arithmetic progression?
Question 3.5.2.
Is it true that any infinite colouring of positive integers contains a monochromatic \(l\)-term arithmetic progression, for \(l\in\mathbb{N}\text{?}\)
Theorem 3.5.3.
Canonical form of van der Waerden's theorem: If \(f\) is an arbitrary function from the positive integers to the positive integers, then there are arbitrarily large arithmetic progressions \(P\) such that the restriction of \(f\) to \(P\) is either constant or one-to-one. (See Figures 3.5.4 and Figure 3.5.5.)
Question 3.5.6.
Is it true that any finite colouring of positive integers contains a monochromatic \(l\)-term arithmetic progression with an odd common difference?
Question 3.5.7.
Is it true that any finite colouring of positive integers contains a monochromatic \(l\)-term arithmetic progression with an even common difference?
Theorem 3.5.8.
Polynomial van der Waerden Theorem: Let \(l,r\in \mathbb{N}\) and let \(p\) be a polynomial with integer coefficients such that \(p(0)=0\text{,}\) . Then for any \(r\)-colouring of \(\mathbb{Z}\) there are \(a,d\in \mathbb{Z}\) such that the \(l\)-term arithmetic progression
is monochromatic.
Note: This is a very special case of the Polynomial van der Waerden Theorem proved by Bergelson and Leibman (Polynomial extensions of van der Waerden's and Szemeredi's theorems, Journal of the American Math Society, Vol. 9, 1996, 725-753.)
\(2\)-Large and Large Sets:
We say that a set \(L\subseteq \mathbb{N}\) is 2-large if any 2-colouring of \(\mathbb{N}\) contains long monochromatic arithmetic progressions with common difference in \(L\text{.}\)
We say that a set \(L\subseteq \mathbb{N}\) is large if any finite colouring of \(\mathbb{N}\) contains long monochromatic arithmetic progressions with common difference in \(L\text{.}\)
Example 3.5.12.
Is the set of all natural numbers large?
Is the set of all odd numbers large?
Is the set of all numbers divisible by \(3\) large?
Is the set of all perfect squares large?
Is the set \(\{2,6,12,,20,30,42,\ldots \}\) large?
Conjecture 3.5.13.
Every 2-large set is large. (T.C. Brown, R.L. Graham, and B.M. Landman, On the set of common differences in van der Waerden's theorem on arithmetic progressions, Canad. Math. Bull. 42 (1999), 25-36.)
Example 3.5.15.
Colour the 12 points below with three colours so that you use each colour four times. Can you avoid 3-term rainbow arithmetic progressions?
Example 3.5.17.
What About... Colour the 15 points below with three colours so that you use each colour five times. Can you avoid 3-term rainbow arithmetic progressions?
Theorem 3.5.19.
Every equinumerous 3-colouring of \([1,3n]\) contains a rainbow 3-term arithmetic progression. (Jungić, V., Radoičić, R., Rainbow Arithmetic Progressions, Integers, Electron. J. Combin. Number Theory 3 (2003) A18)
Resources.