One form of van der Waerden's theorem states that for all positive integers and , there exists a constant such that if and , then
some set
contains an arithmetic progression of length
.
The least possible value of 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 for , 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).
3
4
5
6
2
9
35
178
1132
3
27
4
76
Shelah (1988) proved that van der Waerden's numbers are primitive
recursive. It is known that
(1)
and that
(2)
for some constants and . In 1998, T. Gowers announced that he has proved the
general result
(3)
(Gowers 2001). Berlekamp (1968) showed that for a prime,
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."
and 
, there exists a constant 
such that if 
and 
, then
some set 
contains an arithmetic progression of length
.
The least possible value of 
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 
for 
, 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).
and 
. In 1998, T. Gowers announced that he has proved the
general result
a prime,
