Van der Waerden's theorem
Van der Waerden's theorem is a fundamental result in Ramsey theory asserting that for any positive integers r (the number of colors) and k (the length of the arithmetic progression), there exists a positive integer N = W(k, r) such that any r-coloring of the integers \{1, 2, \dots, N\} contains a monochromatic arithmetic progression of length k, that is, numbers a, a+d, \dots, a+(k-1)d (with d > 0) all sharing the same color.[1][2] The theorem was conjectured by the Dutch mathematician Pierre Joseph Henry Baudet and proved in 1927 by Bartel Leendert van der Waerden, who developed the proof during discussions with Emil Artin and Otto Schreier at the University of Hamburg.[3][2] Van der Waerden's work, published in Nieuw Archief voor Wiskunde, built on earlier results in additive number theory and marked one of the earliest triumphs in the emerging field of Ramsey theory, which explores unavoidable structures in sufficiently large systems.[2][3] The minimal such N, known as the van der Waerden number W(k, r), quantifies the theorem's finite guarantee; for example, W(3, 2) = 9, meaning any 2-coloring of \{1, \dots, 8\} avoids a monochromatic 3-term progression, but no 2-coloring of \{1, \dots, 9\} does.[2] Computing these numbers is notoriously difficult, with exact values known only for small k and r, and upper bounds growing rapidly—e.g., W(3, r) is bounded above by tower functions of height proportional to r.[3][1] Beyond its combinatorial core, the theorem has profound implications across mathematics: it connects to ergodic theory via multiple recurrence (e.g., Furstenberg's topological proof), additive combinatorics (influencing Szemerédi's theorem on progressions in dense sets), and even computer science through formal verifications and algorithmic bounds.[1][3] Generalizations extend to polynomials, multidimensional progressions, and infinite settings, underscoring its role as a pillar for studying order in chaos.[1]Background and History
Origins in Arithmetic Progressions
Arithmetic progressions form a cornerstone of number theory, representing sequences where the difference between successive terms remains constant. Formally, a sequence a, a+d, a+2d, \dots, a+(k-1)d constitutes a k-term arithmetic progression if a is the initial term and d \neq 0 is the common difference. For instance, the terms 3, 5, 7 form a 3-term arithmetic progression with a=3 and d=2, as each subsequent term increases by 2. Similarly, longer progressions like 1, 4, 7, 10 illustrate the pattern with d=3, highlighting how such structures appear naturally in the integers and underpin many analytical tools in the field.[4] In early combinatorial number theory, arithmetic progressions held significant interest due to their role in addressing questions about structure within subsets of integers, such as guaranteeing the presence of such sequences under certain conditions. This focus emerged as a central problem in additive number theory, motivating investigations into the minimal requirements for subsets to contain progressions of specified lengths. Moreover, arithmetic progressions are intrinsically linked to Diophantine equations, where solutions to linear forms like $2y = x + z correspond precisely to 3-term progressions, driving explorations into integer solutions and their distributions. These foundational ideas paved the way for subsequent advancements, such as Roth's 1953 result establishing that subsets of the integers with positive upper density must contain 3-term arithmetic progressions, which served as a key historical precursor to broader theorems on progression-free sets.Development and Proof
In 1926, while visiting the University of Göttingen as a young mathematician, Bartel Leendert van der Waerden encountered a conjecture formulated in 1921 by the Dutch mathematician Pierre Joseph Henry Baudet concerning monochromatic arithmetic progressions in colorings of the natural numbers.[5] Baudet's conjecture stated that for any positive integers k and r, there exists a number N such that any coloring of the integers from 1 to N with r colors contains a monochromatic arithmetic progression of length k. Van der Waerden learned of this open problem during his time in Göttingen, a vibrant center of mathematical activity under figures like David Hilbert and Emmy Noether.[6] After moving to Hamburg, during a casual lunch conversation in late 1926, van der Waerden discussed the conjecture with his colleagues Emil Artin and Otto Schreier, both in Hamburg at the time. The three mathematicians retreated to a seminar room after the meal and, over the course of a single afternoon, collaboratively outlined the key ideas for a proof, with van der Waerden taking the lead in formalizing it. Remarkably, at just 23 years old, van der Waerden refined and completed the argument in the ensuing weeks, culminating in his seminal 1927 publication "Beweis einer Baudetschen Vermutung" in Nieuw Archief voor Wiskunde. This work, submitted shortly after his recent PhD from the University of Amsterdam in 1926, marked his rapid ascent in combinatorial number theory.[7][8] The proof introduced a novel compactness argument, first verifying the existence of monochromatic progressions in sufficiently large finite colorings through inductive constructions, then extending the result to the infinite natural numbers via the compactness theorem from propositional logic—ensuring that if every finite initial segment admits such a progression, the entire sequence does as well. This non-constructive approach avoided explicit bounds but established the theorem's universality. Van der Waerden later reflected on the proof's discovery in his 1971 reminiscence, emphasizing the serendipitous collaboration and the elegance of the compactness technique.[9] The theorem's publication was met with swift acclaim in mathematical circles, influencing the nascent field of extremal combinatorics. It provided a cornerstone for what would become known as Ramsey theory, bridging arithmetic progressions with broader questions of order in colored structures and directly inspiring Frank P. Ramsey's 1930 generalization to hypergraph colorings. Early extensions, such as those by Richard Rado in the 1930s, built on its framework to explore linear equations in colorings, solidifying its role as a foundational result in the discipline.[10]Formal Statement
The Theorem
Van der Waerden's theorem states that for any positive integers r and k, there exists a positive integer N such that any r-coloring of the integers \{1, 2, \dots, N\} contains a monochromatic arithmetic progression of length k. Here, r represents the number of colors, and k denotes the desired length of the arithmetic progression, which is a sequence of the form a, a+d, a+2d, \dots, a+(k-1)d where a is the starting term and d > 0 is the common difference.[11] A monochromatic arithmetic progression requires that all k terms in the sequence receive the same color under the given coloring.[11] This finite version of the theorem implies an infinite version: for any fixed r, every r-coloring of the positive integers contains monochromatic arithmetic progressions of arbitrary finite length k. The implication follows immediately from the finite version: for any r-coloring of the positive integers and any k, the initial segment \{1, \dots, W(k, r)\} must contain a monochromatic arithmetic progression of length k.Van der Waerden Numbers
The van der Waerden number W(k, r) is the smallest positive integer N such that any r-coloring of the set \{1, 2, \dots, N\} contains a monochromatic arithmetic progression of length k. This minimal N captures the threshold beyond which the structural guarantee of the theorem holds for all possible colorings. By van der Waerden's theorem, W(k, r) exists and is finite for every pair of positive integers k and r. Moreover, W(k, r) is non-decreasing in both arguments: increasing k or r requires a larger N to force the monochromatic progression, as more colors or longer progressions allow for more evasive colorings.[12] Van der Waerden numbers are central to the partition regularity of linear equations defining arithmetic progressions, illustrating how finite colorings of the integers inevitably produce monochromatic solutions to such systems.[13] In this context, W(k, r) provides the precise scale at which this regularity manifests for progressions of length k. Determining exact values of W(k, r) is computationally intensive, reflecting the inherent complexity of enumerating and verifying colorings to identify the minimal N.[14]Examples
Basic Illustrations
To illustrate Van der Waerden's theorem, consider the trivial case where only one color r = 1 is used. In this situation, the entire set of positive integers \mathbb{N} forms a monochromatic arithmetic progression of any desired length k, since all elements share the same color. This demonstrates the theorem's assertion in its simplest form, where no avoidance is possible beyond the monochromatic structure itself.[15] For a non-trivial illustration with two colors (r = 2) and arithmetic progressions of length k = 3, consider coloring the integers from 1 to 8 as follows: blue for 1, 4, 5, 8 and red for 2, 3, 6, 7. An arithmetic progression of length 3 is a sequence a, a+d, a+2d for positive integers a and d. Checking all possible such progressions within {1, \dots, 8} reveals none are monochromatic; for instance, the progression 1, 4, 7 has colors blue, blue, red, and 2, 5, 8 has red, blue, blue. This coloring avoids monochromatic 3-term arithmetic progressions up to 8.[15] However, extending to 9 forces a monochromatic 3-term arithmetic progression regardless of the color assigned to 9. If 9 is colored blue, then 1, 5, 9 forms a blue progression (common difference d=4). If 9 is colored red, then 3, 6, 9 forms a red progression (common difference d=3). This example highlights how the theorem guarantees the emergence of monochromatic structure in sufficiently large colorings, even when avoidance is possible in smaller sets.[15]Small Finite Cases
The computation of exact van der Waerden numbers W(k, r) for small values of the arithmetic progression length k and number of colors r has been achieved through exhaustive enumeration and computer-assisted verification, confirming the minimal n where every r-coloring of \{1, 2, \dots, n\} forces a monochromatic k-term arithmetic progression. These values provide concrete illustrations of the theorem's implications for finite sets. For k=2, the numbers are trivial, as W(2, r) = r + 1 by the pigeonhole principle, since any r-coloring of r+1 integers must repeat a color on at least two points, which form a 2-term progression. The value W(3, 2) = 9 was established via exhaustive manual checking of all possible 2-colorings: a coloring of \{1, 2, \dots, 8\} exists without a monochromatic 3-term arithmetic progression (e.g., color 1,4,5,8 red and 2,3,6,7 blue avoids it), but no such coloring exists for 9 integers. Larger small values were obtained using systematic computer searches encoding the avoidance condition as satisfiability problems or direct enumeration.| k \setminus r | 2 | 3 | 4 |
|---|---|---|---|
| 3 | 9 | 27 | 293 |
| 4 | 35 | 76 | |
| 5 | 178 | ||
| 6 | 1132 |
Proof Techniques
Elementary Proofs for Specific Cases
To establish the van der Waerden number W(3,2) = 9, it suffices to show that there exists a 2-coloring of the integers {1, 2, ..., 8} with no monochromatic 3-term arithmetic progression, but every 2-coloring of {1, 2, ..., 9} contains one. The lower bound is demonstrated by the coloring blue for positions 1,4,5,8 and red for 2,3,6,7, which avoids monochromatic 3-term arithmetic progressions in all possible configurations within {1, 2, ..., 8}.[2] For the upper bound, an elementary proof proceeds by case analysis on a 2-coloring (red and blue) of {1, 2, ..., 9}, assuming no monochromatic 3-term arithmetic progression exists and deriving a contradiction. Without loss of generality, assume the color of 5 is red (swap colors if necessary). Then, consider the colors of 3 and 7. If 3 is red, then 7 must be blue to avoid the red progression 3,5,7. To avoid the blue progression 1,4,7, at least one of 1 or 4 must be red. If 1 is red, then 1,3,5 is a red progression, a contradiction. Thus, 1 is blue and 4 is red. To avoid the red progression 4,5,6, 6 must be blue. Continuing the analysis, the colors of the remaining positions 2,8,9 are forced to lead to a monochromatic progression, such as 2,5,8 or 1,5,9 or 3,6,9, depending on their colors. By symmetry, the case where 7 is red instead of 3 leads to the same conclusion. If neither 3 nor 7 is red, then both are blue. To avoid the blue progression 3,5,7, but since 5 is red, this is already avoided, but now consider the progression 1,5,9. If 1 is red, then to avoid red 1,5,9, 9 must be blue. Then, further cases on 2 and 8 force a progression, such as blue 3,6,9 if 6 is blue, or other patterns like red 2,5,8 if 2 and 8 are red. Exhaustive branching in this tree of cases, considering all possible color assignments consistent with no early progression, always yields a monochromatic 3-term arithmetic progression somewhere in {1, 2, ..., 9}. This case analysis confirms that no avoiding coloring exists for n=9.[17] A key lemma underlying such proofs for the 2-color case is that any 2-coloring of a sufficiently long sequence contains a monochromatic 3-term arithmetic progression, with "sufficiently long" being 9 as established above. This lemma serves as a building block for higher cases.[1] For the case r=3, k=3, the van der Waerden number W(3,3) = 27. The lower bound is shown by exhibiting a 3-coloring of {1, 2, ..., 26} without monochromatic 3-term arithmetic progressions, such as one using periodic patterns with period 13 avoiding progressions in each color. The upper bound can be sketched using induction on the number of colors, leveraging the 2-color case. Assume a 3-coloring (red, blue, green) of {1, 2, ..., N} with N large, divided into blocks of size W(3,2)=9. By the pigeonhole principle applied to the colors dominating in each block, there is either a monochromatic block in one color, which by the 2-color lemma contains a monochromatic 3-term arithmetic progression in that color, or the blocks exhibit a pattern where one color is absent in a subsequence of blocks forming an arithmetic progression of length 3, reducing to the 2-color case on the remaining colors within those blocks and forcing a monochromatic progression. Adjusting the block size and number of blocks to 3 blocks of size 9 yields the bound N=27, with exhaustive verification confirming no avoiding coloring for n=27.[18]General Compactness Proof
Van der Waerden's theorem can be equivalently stated in terms of colorings of the positive integers: for any positive integers k and r, every r-coloring of \mathbb{Z}^+ contains a monochromatic arithmetic progression of length k. To establish this infinite version from the finite one, the compactness principle from topology (or propositional logic) is invoked: the space of all r-colorings of \mathbb{Z}^+ is the product space \{1, \dots, r\}^\mathbb{N}, which is compact by Tychonoff's theorem; any coloring without a monochromatic k-term arithmetic progression would have finite initial segments also avoiding such progressions, but if every sufficiently large finite segment forces one, a contradiction arises via compactness, ensuring the infinite case holds whenever the finite van der Waerden numbers W(k, r) are finite.[1] The core of van der Waerden's original proof demonstrates the existence of finite W(k, r) via a combinatorial induction, constructing these numbers iteratively to guarantee monochromatic k-term progressions in any r-coloring of [W(k, r)], where = \{1, \dots, n\}. The proof proceeds by induction on the progression length k, with an auxiliary induction on the number of colors r or the complexity of partial structures. For fixed k and r, the construction builds larger intervals by combining smaller ones proven to work under the inductive hypothesis, ensuring no "bad" coloring (one avoiding monochromatic k-progressions) exists beyond a certain size.[1][19] The base case for k = 2 is trivial: W(2, r) = r + 1, as any r-coloring of [r+1] must repeat a color by the pigeonhole principle, yielding a monochromatic progression of length 2 (any two equal elements form one with common difference). For the inductive step, assume the theorem holds for all progression lengths k' < k and any number of colors; the goal is to find W(k, r). A key auxiliary notion is introduced: a "color-focused" (k-1)-progression, where multiple disjoint (k-1)-arithmetic progressions share a potential "focus" point f (the position to complete a k-progression), and each such subprogression is monochromatic in some color from a restricted palette.[19][20] To construct W(k, r), define a sequence of numbers V(k, r, s) for s = 1, \dots, r, where V(k, r, 1) = 2 W(k-1, r) and recursively V(k, r, s) = 2 V(k, r, s-1) \cdot W(k-1, r \cdot V(k, r, s-1)) for s > 1; then set W(k, r) \leq V(k, r, r). Consider an interval of length V(k, r, s) colored with r colors. By the inductive hypothesis on W(k-1, \cdot), either a monochromatic k-progression exists directly, or the coloring decomposes into blocks where subintervals of length V(k, r, s-1) are analyzed: if a monochromatic (k-1)-progression appears in a block using more than r \cdot V(k, r, s-1) "effective" colors (accounting for block types), it extends; otherwise, the blocks form a meta-coloring with fewer colors, forcing a monochromatic set of blocks that align to create s color-focused (k-1)-progressions converging on a focus f.[19][1] When s = r, these r color-focused (k-1)-progressions at f use at most r colors total across their monochromatic subprogressions; by the pigeonhole principle, at least one color c appears in the focus for enough subprogressions to form a monochromatic k-progression in color c (since assigning c to f completes at least one, but the avoidance assumption leads to a contradiction in the construction). This iterative building ensures the finiteness of W(k, r), completing the induction. The argument treats color classes as subsets of the interval and leverages a Ramsey-like principle for arithmetic structures within these subsets to guarantee progressions, without relying on explicit infinite Ramsey theory.[20][1]Ergodic Theory Approach
An alternative proof of van der Waerden's theorem employs concepts from ergodic theory, notably Hillel Furstenberg's multiple recurrence theorem, which links dynamical recurrence in measure-preserving systems to the existence of arithmetic progressions in colorings of the integers. This approach reframes the combinatorial problem in terms of invariant measures on the space of colorings, providing a measure-theoretic perspective that highlights deep connections between ergodic dynamics and Ramsey theory. The foundational setup involves the compact space X = \{1, \dots, r\}^{\mathbb{Z}} of all possible r-colorings of the integers \mathbb{Z}, endowed with the product topology, which makes X a compact metric space. The bilateral shift transformation T: X \to X is defined by (T f)(n) = f(n+1) for all f \in X and n \in \mathbb{Z}, yielding a topological dynamical system (X, T). To engage ergodic theory, consider the Borel \sigma-algebra \mathcal{B} on X and a T-invariant probability measure \mu on (X, \mathcal{B}); the case of primary interest is when \mu is ergodic, meaning that any T-invariant set has measure 0 or 1. For each color c \in \{1, \dots, r\}, define the cylinder set A_c = \{ f \in X \mid f(0) = c \}, which forms a clopen partition of X. Since \mu is a probability measure, at least one A_c satisfies \mu(A_c) > 0.[21] Furstenberg's multiple recurrence theorem asserts that in any ergodic measure-preserving system (X, \mathcal{B}, \mu, T) and for any integer \ell \geq 1 and measurable set E \subset X with \mu(E) > 0, there exist infinitely many d > 0 such that \mu\left( \bigcap_{j=0}^{\ell-1} T^{-j d} E \right) > 0. Applying this with E = A_c (where \mu(A_c) > 0) and \ell = k (the desired progression length), there exists d > 0 such that \mu\left( \bigcap_{j=0}^{k-1} T^{-j d} A_c \right) > 0. This positive-measure set consists of colorings f \in X for which f(0) = c, f(d) = c, ..., f((k-1)d) = c, establishing the existence of a monochromatic k-term arithmetic progression with common difference d starting at position 0 in color c. Thus, for any ergodic invariant measure \mu, the support of \mu contains colorings exhibiting monochromatic k-arithmetic progressions. To translate this ergodic result to the full combinatorial statement of van der Waerden's theorem—which applies to arbitrary (not necessarily ergodic) finite colorings of \mathbb{N}—one observes that the ergodic case directly yields monochromatic progressions in ergodic colorings of \mathbb{Z}. For general colorings, the proof leverages the ergodic decomposition theorem: any invariant measure \mu decomposes uniquely into ergodic components, each of which admits such progressions, implying the property holds \mu-almost everywhere. A direct finitary argument for van der Waerden follows by considering the infinite version on \mathbb{Z} and applying a compactness principle to extract a finite initial segment \{1, \dots, N\} guaranteed to contain a monochromatic progression, without invoking the full strength of Szemerédi's theorem (which handles arbitrary positive density sets). In contrast, Szemerédi's density version, also proved ergodically by Furstenberg, implies van der Waerden by assigning colors such that one class has density at least $1/r > 0, but the direct application here suffices for the finite-color case.[21] This ergodic approach offers advantages in uniformity and extensibility, as the multiple recurrence machinery applies uniformly across progression lengths k and colors r, facilitating generalizations to multidimensional or polynomial progressions. However, it demands substantial prerequisites in ergodic theory, contrasting with more elementary combinatorial proofs, and the bounds on the van der Waerden numbers W(k, r) obtained remain exponential tower-type, similar to compactness-based methods.Bounds and Computations
Known Values and Calculations
The computation of exact van der Waerden numbers W(k,r) is challenging due to the exponential growth in the size of the search space, requiring exhaustive enumeration of colorings to verify the absence of monochromatic arithmetic progressions of length k. Early values were established through manual calculations and basic computer-assisted searches in the mid-20th century, while more recent determinations for larger parameters rely on optimized backtracking algorithms, symmetry reductions, and satisfiability (SAT) solvers to handle the vast number of possible r-colorings of \{1, 2, \dots, n\}. Only a handful of non-trivial exact values (for k \geq 3) are known, as listed below; the trivial case W(2,r) = r+1 holds for all r \geq 1, since any set of r+1 integers must contain two of the same color, forming a monochromatic arithmetic progression of length 2. No new exact uniform values have been computed as of 2025. The following table summarizes the known exact values, focusing on small k and r:| k \ r | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 3 | 9 | 27 | 76 | |
| 4 | 35 | 293 | ||
| 5 | 178 | |||
| 6 | 1132 |