Namespaces
Variants
Actions

Van der Waerden theorem

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.


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

[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
How to Cite This Entry:
Van der Waerden theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Van_der_Waerden_theorem&oldid=54556