Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Van Der Waerden's theorem states that if $K$ and $L$ are two arbitrary natural numbers, there exists a natural number $N(K,L)$ such that if any arbitrary segment of the sequence of natural numbers of length $N(K,L)$ is divided in ANY manner into $K$ classes (some of which may be empty), then an arithmetic progression of length $L$ appears in at least one of these classes. I will give an elementary proof of it, originally due to M. A. Lukomskaya.

Van Der Waerden's theorem is a corollary of Szemerédi's theorem, which states that every sequence of integers that has positive upper Banach density (to be defined) contains arbitrarily long arithmetic progressions. Szemerédi's theorem was conjectured by Erdos and Turán (1936). Roth (1953) proved the case $k$ = 3, which was mentioned in his Fields Medal citation. Szemerédi (1969) proved the case $k$ = 4, and the general theorem in 1975 as a consequence of the so-called Szemerédi Regularity Lemma, for which he collected a $1000 prize from Erdos. The numbers $N(K,L)$ are called Van Der Waerden numbers, and only a handful of them are known exactly. The search for good upper bounds on them is still an active area of research. In fact Timothy Gowers (1998) gave a new proof, with a better bound on $N(K,L)$, for the case $K$ = 4 and this was mentioned in his Fields Medal citation. If time permits we will go into this.