TOPICS
Search

van der Waerden Number

One form of van der Waerden's theorem states that for all positive integers k and r, there exists a constant n(r,k) such that if n_0>=n(r,k) 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. The least possible value of n(r,k) is known as a van der Waerden number. The only nontrivial van der Waerden numbers that are known exactly are summarized in the following table. As shown in the table, the first few values of n(2,k) for k=1, 2, ... are 1, 3, 9, 35, 178, 1132, ... (OEIS A005346), the last of which is due to M. Kouril and J. L. Paul in 2007 (Kouril and Paul 2008).

r\k3456
29351781132
327
476

Shelah (1988) proved that van der Waerden's numbers are primitive recursive. It is known that

n(r,3)<=e^(r^(c_1))
(1)

and that

n(r,4)<=e^(e^(e^(r^(c_2))))
(2)

for some constants c_1 and c_2. In 1998, T. Gowers announced that he has proved the general result

n(r,k)<=e^(e^(r^(e^(e^(k+110)))))
(3)

(Gowers 2001). Berlekamp (1968) showed that for p a prime,

n(2,p+1)>p·2^p.
(4)

A probabilistic argument using the Lovász local lemma shows that

n(r,k)>((r^k)/(erk))(1+o(1)).
(5)

New lower bounds have been given by Heule (2008).

See also

Szemerédi's Theorem, van der Waerden's Theorem

Portions of this entry contributed by Kevin O'Bryant

Explore with Wolfram|Alpha

References

Berlekamp, E. A. "Construction for Partitions Which Avoid Long Arithmetic Progressions." Canad. Math. Bull. 11, 409-414, 1968.Goodman, J. E. and O'Rourke, J. (Eds.). Handbook of Discrete & Computational Geometry. Boca Raton, FL: CRC Press, p. 159, 1997.Gowers, W. T. "Fourier Analysis and Szemerédi's Theorem." In Proceedings of the International Congress of Mathematicians, Vol. 1. Doc. Math. 1998, Extra Vol. 1. Berlin, pp. 617-629, 1998. Available electronically from http://www.mathematik.uni-bielefeld.de/documenta/xvol-icm/Fields/Fields.html.Gowers, W. T. "A New Proof of Szemerédi's Theorem for Arithmetic Progressions of Length Four." Geom. Funct. Anal. 8, 529-551, 1998.Gowers, W. T. "A New Proof of Szemerédi's Theorem." Geom. Func. Anal. 11, 465-588, 2001.Heule, M. J. H. "Improving the Odds: New Lower Bounds for Van der Waerden Numbers." March 4, 2008. http://www.st.ewi.tudelft.nl/sat/slides/waerden.pdf.Honsberger, R. More Mathematical Morsels. Washington, DC: Math. Assoc. Amer., p. 29, 1991.Kouril, M.  and Paul, J. L. "The van der Waerden Number W(2,6) Is 1132." Experimental Math. 17, 53-61, 2008.Shelah, S. "Primitive Recursive Bounds for van der Waerden Numbers." J. Amer. Math. Soc. 1, 683-697, 1988.Sloane, N. J. A. Sequence A005346/M2819 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

van der Waerden Number

Cite this as:

O'Bryant, Kevin and Weisstein, Eric W. "van der Waerden Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/vanderWaerdenNumber.html

Subject classifications