Van der Waerden theorem

on arithmetic progressions

Given natural numbers $\ell,m$, there exists a number $N(\ell,m)$ such that if $n \ge N(\ell,m)$ and $\\{1,2,\ldots,n\\}$ is partitioned into $m$ sets, then at least one set contains $\ell$ terms in arithmetic progression [a1]. Another, equivalent, non-finitary, formulation is as follows. Let $\mathbb{N} = X_1 \cup \cdots \cup X_m$ be a finite partition of the natural numbers; then at least one $X_i$ contains arithmetic progressions of arbitrary length. The result was conjectured by A. Baudet. Let $A \subset \\{1,2,\ldots\\}$ be a set of natural numbers and let $\bar d(A)$ be its upper asymptotic density. When discussing van der Waerden's theorem stated above, P. Erdös and P. Turán conjectured that if $\bar d(A) > 0$, then $A$ contains arbitrary long arithmetic progressions; [a2].

Let $B(\ell,n)$ be a maximally large subset of $\\{1,2,\ldots,n\\}$ which contains no $\ell$ elements in arithmetic progression. Let $b(\ell,n)$ be the number of elements in a $B(\ell,n)$. Then Szemerédi's theorem, [a3], says that $\lim_{n \rightarrow \infty} n^{-1} b(\ell,n) = 0$. This implies the Erdös–Turán conjecture. Another proof of Szemerédi's theorem was given by H. Furstenberg, based on ideas from ergodic theory, [a4].

For a personal historical account of the van der Waerden theorem see [a6].

#### References[edit]

[a1] |  B.L. van der Waerden, "Beweis einer Baudetschen Vermutung" Nieuw Arch. Wisk. , 15 (1927) pp. 212–216

|

[a2] |  P. Erdös, P. Turán, "On some sequences of integers" J. London Math. Soc. , 11 (1936) pp. 261–264
[a3] |  E. Szemerédi, "On sets of integers containing no $k$-elements in arithmetic progression" Acta Arithm. , 27 (1975) pp. 199–245
[a4] |  H. Furstenberg, "Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions" J. d'Anal. Math. , 31 (1977) pp. 204–256
[a5] |  H. Furstenberg, "Recurrence in ergodic theory and combinatorial number theory" , Princeton Univ. Press (1981)
[a6] |  A.Ya. Khinchin, "Three pearls of number theory" , Graylock (1952) Translation from the second, revised Russian ed. [1948] Zbl 0048.27202 Reprinted Dover (2003) ISBN 0486400263