TOPICS
Search

van der Waerden's Theorem

van der Waerden's theorem is a theorem about the existence of arithmetic progressions in sets. The theorem can be stated in four equivalent forms.

1. If N=C_1 union C_2 union ... union C_r, then some C_i contains arbitrarily long arithmetic progressions (Baudet's conjecture).

2. For all positive integers k and r, there exists a constant n(k,r) such that if n_0>=n(k,r) and {1,2,...,n_0} subset C_1 union C_2 union ... union C_r, then some set C_i contains an arithmetic progression of length k.

3. If {a_0,a_1,...} is an infinite sequence of integers satisfying 0<a_(k+1)-a_k<r for some r, then the sequence contains arbitrarily long arithmetic progressions.

4. For all positive integers k and r, there is a constant g(k,r) such that if g_0>=g(k,r) and a_1, a_2, ..., a_(g_0) satisfies 0<a_(i+1)-a_i<=r, then k of the numbers a_1, a_2, ..., a_(g_0) are in arithmetic progression.

The constants n(k,r) are called van der Waerden numbers, and no formula for n(k,r) is known. van der Waerden's theorem is a corollary of Szemerédi's theorem.

See also

Arithmetic Progression, Baudet's Conjecture, Szemerédi's Theorem, van der Waerden Number

This entry contributed by Kevin O'Bryant

Explore with Wolfram|Alpha

References

de Bruijn, N. G. "Commentary." Unpublished manuscript, pp. 116-124, 1977. http://alexandria.tue.nl/repository/freearticles/598841.pdf.Guy, R. K. "Theorem of van der Waerden, Szemerédi's Theorem. Partitioning the Integers into Classes; at Least One Contains an A.P." §E10 in Unsolved Problems in Number Theory, 3rd ed. New York: Springer-Verlag, pp. 317-323, 2004.Honsberger, R. More Mathematical Morsels. Washington, DC: Math. Assoc. Amer., p. 29, 1991.Khinchin, A. Y. "Van der Waerden's Theorem on Arithmetic Progressions." Ch. 1 in Three Pearls of Number Theory. New York: Dover, pp. 11-17, 1998.van der Waerden, B. L. "Beweis einer Baudetschen Vermutung." Nieuw Arch. Wisk. 15, 212-216, 1927.van der Waerden, B. L. "How the Proof of Baudet's Conjecture Was Found." Studies in Pure Mathematics (Presented to Richard Rado). London: Academic Press, pp. 251-260, 1971.van der Waerden, B. L. "Wie der Beweis der Vermutung von Baudet gefunden wurde." Elem. Math. 53, 139-148, 1998.

Referenced on Wolfram|Alpha

van der Waerden's Theorem

Cite this as:

O'Bryant, Kevin. "van der Waerden's Theorem." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/vanderWaerdensTheorem.html

Subject classifications