TOPICS
Search

van der Waerden Number

A van der Waerden number is the least threshold in the finite form of van der Waerden's theorem. This theorem states that for all positive integers k and r, there exists a positive integer n(r,k) such that, for every integer n_0>=n(r,k), if {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 elementary values are n(r,1)=1, n(1,k)=k, and n(r,2)=r+1. Nontrivial values are summarized in the following table (Kouril 2012, p. 2). 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 Kouril and Paul (2008).

r\k3456
29351781132
327293
476

Shelah (1988) gave primitive recursive upper bounds for van der Waerden's numbers. For r>=2, there are absolute constants c_1,c_2>0 such that

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

and that

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

(Gowers 1998, p. 626). Gowers' subsequent proof implies the general bound

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

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

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

For each fixed r>=2, a probabilistic argument using the Lovász local lemma shows that, as k->infty,

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

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

For explicit numerical lower bounds, Kim (2026) constructed colorings giving n(3,9)>4002705 and n(3,28)>159594201561100726. Kim (2026) also gave improved three-color lower bounds for every progression length from 9 through 28, compared with the published bounds considered there. These finite constructions do not improve the asymptotic growth rate.

The growth question for two colors is problem 138 in the Erdős problems collection. Writing W(k)=n(2,k), it asks in particular whether W(k)^(1/k)->infty as k->infty (Bloom 2026).

See also

Gallai-van der Waerden Number, 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. R. "A Construction for Partitions Which Avoid Long Arithmetic Progressions." Canad. Math. Bull. 11, 409-414, 1968. https://doi.org/10.4153/CMB-1968-047-7.Bloom, T. "Erdős Problem #138." Accessed Oct. 26, 2026. https://www.erdosproblems.com/138.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, Germany, pp. 617-629, 1998. https://doi.org/10.4171/DMS/1-1/23.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. Funct. Anal. 11, 465-588, 2001. https://doi.org/10.1007/s00039-001-0332-9.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.Kim, S. "Polychromatic Blocks and Explicit Lower Bounds for Multicolour van der Waerden Numbers." 22 Oct 2026. https://arxiv.org/abs/2610.32000.Kouril, M. "Computing the van der Waerden Number W(3,4)=293." Integers 12, A46, 2012. https://math.colgate.edu/~integers/m46/m46.pdf.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:

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

Subject classifications