van der Waerden's Theorem: How Far and Where?

Section 3.4 van der Waerden's Theorem: How Far and Where?

Do not, however, confuse elementary with simple. — Aleksandr Yakovlevich Khinchin, Soviet mathematician, 1894 —1959

Figure 3.4.1. Aleksandr Yakovlevich Khinchin

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.

Reminder: The smallest $N$ guaranteed by the theorem 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{.}$

Two Questions.

How big is $W(l,k)\text{?}$
If $\mathbb{N}$ is $k$-coloured can we be sure that a certain colour contains an $l$-term arithmetic progression?

van der Waerden Numbers. In 1951, Paul Erdős and Richard Rado introduced the van der Waerden's function:

\begin{equation*} W:(l,k)\to W(l,k)\text{.} \end{equation*}

The values of van der Waerden's function are called van der Waerden numbers.

Best known lower bounds to van der Waerden numbers.

Table 3.4.2. Best known lower bounds to van der Waerden numbers.

	$l=$ length of AP
$k=$ # of colours	3	4	5	6	7	8	9
2	9	35	178	1132	$> 3703$	$> 7584$	$> 27113$
3	27	$> 292$	$> 1209$	$> 8886$	$> 43855$	$> 238400$
4	76	$> 1948$	$>10437 $	$> 90306$	$> 387967$
5	$> 125$	$> 2254$	$>24045$	$> 246956$
6	$> 207$	$>9778$	$>56693$	$>600486$

Big Question:

Figure 3.4.3. $W(l,k)\text{:}$ Can you find me?

Two Lower Bounds: It is a convention to write $W(l)$ instead of $W(l,2)\text{.}$ Hence,

$W(3)=9$ and $W(4)=35$ (Chvatal, 1970)
$W(5)=178$ (Stevens and Shantaram, 1978)
$W(6)=1132$ (Kouril and Paul, 2008)

If $l$ is a prime then $W(l+1)>l\cdot 2^l\text{.}$ (Berlekamp, 1969)

Figure 3.4.4. Elwyn Ralph Berlekamp (1940 — 2019)

For any $\varepsilon >0\text{,}$

\begin{equation*} W(l)\geq \frac{2^l}{l^\varepsilon} \end{equation*}

for large enough $l\text{.}$ (Szabó, 1990)

Upper Bounds.

Prelude:

$\displaystyle f_1(x)=\mbox{DOUBLE} (x)=2x$
$f_2(x)=\mbox{EXPONENT} (x)=2^x$ Note that

\begin{equation*} f_1^{(2)}(1)=f_1(f_1(1)))=f_1(2\cdot 1)=2\cdot 2=2^2=f_2(2), \ f_1^{(3)}(1)=f_1(2^2)=2\cdot 2^2=f_2(3) \end{equation*}

and in general

\begin{equation*} f_2(x)=f_1^{(x)}(1)\text{.} \end{equation*}
$\displaystyle f_3(x)=\text{ TOWER } (x)=\left. 2^{2^{2^{\cdot^{\cdot^{\cdot ^2}}}}}\right\} x =f_2^{(x)}(1)$
$\displaystyle f_4(x)=\text{ WOW } (x)=f_3^{(x)}(1)$
$\displaystyle f_{i+1}(x)=f_i^{(x)}(1)$
$\displaystyle f_\omega(x)=\text{ ACKERMANN } (x)=f_x(x)$

\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|c|} \hline \amp \amp 1\amp 2\amp 3\amp 4\amp 5\amp 6\\ \hline \hline \mbox{DOUBLE} \amp f_1\amp 2\amp 4\amp 6\amp 8\amp 10\amp 12\\ \hline \mbox{EXPONENT} \amp f_2\amp 2\amp 4\amp 8\amp 16\amp 32\amp 64\\ \hline \mbox{TOWER} \amp f_3\amp 2\amp 4\amp 16\amp 65536\amp 2^{65536}\amp \vdots \\ \hline \mbox{WOW} \amp f_4\amp 2\amp 4\amp 65536\amp \mbox{WOW!} \amp \vdots\amp \vdots\\ \hline \amp f_5\amp 2\amp 4\amp \mbox{WOW!} \amp \vdots\amp \vdots\amp \vdots\\ \hline \amp \amp \vdots\amp \vdots\amp \vdots\amp \vdots\amp \vdots\amp \vdots\\ \hline \text{ ACKERMANN } \amp f_\omega\amp 2\amp 4\amp 16\amp \mbox{WOW!} \amp \vdots\amp \vdots\\ \hline \end{array} \end{equation*}

van der Waerden's proof implies, for $k\geq 10$

\begin{equation*} W(l)\leq \text{ ACKERMANN } (l)\text{.} \end{equation*}

Figure 3.4.6. Wilhelm Friedrich Ackermann (1896 -1962)

$W(l)\lt \text{ WOW } (l+2)\text{.}$ (Shelah, 1988)

$\displaystyle W(l)\leq 2^{2^{2^{2^{2^{l+9}}}}}\text{.}$ (Gowers, 1998)

Ron Graham offered $ 1000 for a proof or disproof of the bound that $\displaystyle W(l)\leq 2^{l^2}\text{.}$

Celebrating Erdős:

Figure 3.4.10. Budapest 1999: Ron Graham and Timothy Gowers (Photo by Tom Brown)

Closer to Home: Given any positive integer $r$ and positive integers $k_1\text{,}$ $k_2\text{,}$…, $k_r\text{,}$ there is an integer $m$ such that given any partition $\{1,2,\ldots,m\}=P_1 \cup P_2 \cup \ldots\cup P_r\text{,}$ there is always a class $P_j$ containing an arithmetic progression of length $k_j\text{.}$ Let us denote the least $m$ with this property by $w(r; k_1, k_2,\ldots, k_r)\text{.}$

Tom Brown, an SFU professor, in 1974 found the following:

\begin{equation*} \begin{array}{|c||c||c||c|} \hline w(3;2,3,3)=14\amp w(3;2,4,4)=40\amp w(4;2,2,3,3)=17\amp w(4;2,3,3,3)=40\\ \hline w(3;2,3,4)=21\amp w(3;2,4,5)=71\amp w(4;2,2,3,4)=25\amp \\ \hline w(3;2,3,5)=32\amp \amp w(4;2,2,3,5)=43\amp \\ \hline w(3;2,3,6)=40\amp \amp w(4;2,2,4,4)=53\amp \\ \hline \end{array} \end{equation*}

Where to look for monochromatic arithmetic progressions?

Prelude: Let $A$ be a subset of the set of natural numbers $\mathbb{N}\text{.}$ For any $n \in \mathbb{N}$ let

\begin{equation*} A(n)=\{1,2,\ldots,n\} \cap A \mbox{ and } a(n)=|A(n)|\text{.} \end{equation*}

We define the upper density $\overline{d}(A)$ of the set $A$ by

\begin{equation*} \overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{a(n)}{n}\text{.} \end{equation*}

Similarly, $\underline{d}(A)\text{,}$ the lower density of $A\text{,}$ is defined by

\begin{equation*} \underline{d}(A) = \liminf_{n \rightarrow \infty} \frac{ a(n) }{n}\text{.} \end{equation*}

We say that $A$ has density $d(A)$ if

\begin{equation*} \underline{d}(A)=\overline{d}(A)\text{.} \end{equation*}

Thus

\begin{equation*} d(A)=\lim_{n \rightarrow \infty} \frac{a(n)}{n}\text{.} \end{equation*}

Two examples:

Example 3.4.11.

What is the density of the set of all natural numbers divisible by 3?

Example 3.4.12.

What is the density of the set of all powers of 2?

Note: For more examples see: Natural density - Wikipedia

Paul Erdős and Paul Turán conjectured in 1936 that any set of integers with positive density contains a 3-term arithmetic progression.

Any set of integers with positive density contains a 3-term arithmetic progression. (Roth, 1953)

Figure 3.4.14. Klaus Friedrich Roth (1925– 2015)

Any set of integers with positive density contains an arithmetic progression of any length. (Szemerédi, 1975)

Figure 3.4.15. Endre Szemerédi (1940 — )

Any set of integers with positive density contains an arithmetic progression of any length. (Furstenberg, 1977)

Figure 3.4.16. Hillel (Harry) Furstenberg (1935 — )

For any $k\in \mathbb{N}\text{,}$ there is a $k$-term progression consisting of primes. (Green-Tao Theorem, 2004)

Figure 3.4.18. Terence Chi-Shen Tao (1975– )

Resources.

	\(l=\) length of AP
\(k=\) # of colours	3	4	5	6	7	8	9
2	9	35	178	1132	\(> 3703\)	\(> 7584\)	\(> 27113\)
3	27	\(> 292\)	\(> 1209\)	\(> 8886\)	\(> 43855\)	\(> 238400\)
4	76	\(> 1948\)	\(>10437 \)	\(> 90306\)	\(> 387967\)
5	\(> 125\)	\(> 2254\)	\(>24045\)	\(> 246956\)
6	\(> 207\)	\(>9778\)	\(>56693\)	\(>600486\)