Van der Waerden's theorem is a theorem in the branch of mathematics called Ramsey theory. Van der Waerden's theorem states that for any given positive integers r and k, there is some number N such that if the integers are colored, each with one of r different colors, then there are at least k integers in arithmetic progression whose elements are of the same color. The least such N is the Van der Waerden number W(r, k), named after the Dutch mathematician B. L. van der Waerden.[1]
This was conjectured by Pierre Joseph Henry Baudet in 1921. Waerden heard of it in 1926 and published his proof in 1927, titled Beweis einer Baudetschen Vermutung [Proof of Baudet's conjecture].[2] [3]
For example, when r = 2, you have two colors, say
red and blue. W(2, 3) is bigger than 8, because you can color the integers from like this:| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| B | R | R | B | B | R | R | B |
and no three integers of the same color form an arithmetic progression. But you can't add a ninth integer to the end without creating such a progression. If you add a
red 9, then the red 3, 6, and 9 are in arithmetic progression. Alternatively, if you add a blue 9, then the blue 1, 5, and 9 are in arithmetic progression.In fact, there is no way of coloring 1 through 9 without creating such a progression (it can be proved by considering examples). Therefore, W(2, 3) is 9.
It is an open problem to determine the values of W(r, k) for most values of r and k. The proof of the theorem provides only an upper bound. For the case of r = 2 and k = 3, for example, the argument given below shows that it is sufficient to color the integers with two colors to guarantee there will be a single-colored arithmetic progression of length 3. But in fact, the bound of 325 is very loose; the minimum required number of integers is only 9. Any coloring of the integers will have three evenly spaced integers of one color.
For r = 3 and k = 3, the bound given by the theorem is 7(2·37 + 1)(2·37·(2·37 + 1) + 1), or approximately 4.22·1014616. But actually, you don't need that many integers to guarantee a single-colored progression of length 3; you only need 27. (And it is possible to color with three colors so that there is no single-colored arithmetic progression of length 3; for example:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | |
| R | R | G | G | R | R | G | B | G | B | B | R | B | R | R | G | R | G | G | B | R | B | B | G | B | G |
An open problem is the attempt to reduce the general upper bound to any 'reasonable' function. Ronald Graham offered a prize of US$1000 for showing W(2, k) < 2k2.[4] In addition, he offered a US$250 prize for a proof of his conjecture involving more general off-diagonal van der Waerden numbers, stating W(2; 3, k) ≤ kO(1), while mentioning numerical evidence suggests W(2; 3, k) = k2 + o(1). Ben Green disproved this latter conjecture and proved super-polynomial counterexamples to W(2; 3, k) < kr for any r.[5] The best upper bound currently known is due to Timothy Gowers,[6] who establishes
W(r,k)\leq
| |||||||||||||
| 2 |
,
by first establishing a similar result for Szemerédi's theorem, which is a stronger version of Van der Waerden's theorem. The previously best-known bound was due to Saharon Shelah and proceeded via first proving a result for the Hales - Jewett theorem, which is another strengthening of Van der Waerden's theorem.
The best lower bound currently known for
W(2,k)
\varepsilon
W(2,k)>2k/k\varepsilon
k
The following proof is due to Ron Graham, B.L. Rothschild, and Joel Spencer.[8] Khinchin gives a fairly simple proof of the theorem without estimating W(r, k).
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| R | R | B | R | B | |
| 1 | 6 | 7 | 8 | 9 | 10 |
| B | R | R | B | R | |
| … | … | ||||
| 64 | 321 | 322 | 323 | 324 | 325 |
| R | B | R | B | R | |
Divide into the 65 blocks,, ..., thus each block is of the form for some b in . Since each integer is colored either
red or blue, each block is colored in one of 32 different ways. By the pigeonhole principle, there are two blocks among the first 33 blocks that are colored identically. That is, there are two integers b1 and b2, both in, such thatc(5b1 + k) = c(5b2 + k)
for all k in . Among the three integers 5b1 + 1, 5b1 + 2, 5b1 + 3, there must be at least two that are of the same color. (The pigeonhole principle again.) Call these 5b1 + a1 and 5b1 + a2, where the ai are in and a1 < a2. Suppose (without loss of generality) that these two integers are both
red. (If they are both blue, just exchange 'red' and 'blue' in what follows.)Let a3 = 2a2 - a1. If 5b1 + a3 is
red, then we have found our arithmetic progression: 5b1 + ai are all red.Otherwise, 5b1 + a3 is
blue. Since a3 ≤ 5, 5b1 + a3 is in the b1 block, and since the b2 block is colored identically, 5b2 + a3 is also blue.Now let b3 = 2b2 - b1. Then b3 ≤ 64. Consider the integer 5b3 + a3, which must be ≤ 325. What color is it?
If it is
red, then 5b1 + a1, 5b2 + a2, and 5b3 + a3 form a red arithmetic progression. But if it is blue, then 5b1 + a3, 5b2 + a3, and 5b3 + a3 form a blue arithmetic progression. Either way, we are done.| 0 | 1 | 2 | 3 | … | m |
|---|---|---|---|---|---|
| G | R | R | … | B | |
| 1 | m + 1 | m + 2 | m + 3 | … | 2m |
| B | R | G | … | R | |
| … | … | ||||
| g | gm + 1 | gm + 2 | gm + 3 | … | (g + 1)m |
| B | R | B | … | G | |
Divide each of these two groups into 2·37+1 subgroups of 7 integers each; of the first 37 + 1 subgroups in each group, two of the subgroups must be colored identically. Within each of these identical subgroups, two of the first four integers must be the same color, say
red; this implies either a red progression or an element of a different color, say blue, in the same subgroup.Since we have two identically-colored subgroups, there is a third subgroup, still in the same group that contains an element which, if either
red or blue, would complete a red or blue progression, by a construction analogous to the one for W(2, 3). Suppose that this element is green. Since there is a group that is colored identically, it must contain copies of the red, blue, and green elements we have identified; we can now find a pair of red elements, a pair of blue elements, and a pair of green elements that 'focus' on the same integer, so that whatever color it is, it must complete a progression.The proof for W(2, 3) depends essentially on proving that W(32, 2) ≤ 33. We divide the integers into 65 'blocks', each of which can be colored in 32 different ways, and then show that two blocks of the first 33 must be the same color, and there is a block colored the opposite way. Similarly, the proof for W(3, 3) depends on proving that
| 7(2 ⋅ 37+1) | |
| W(3 |
,2)\leq
| 7(2 ⋅ 37+1) | |
| 3 |
+1.
By a double induction on the number of colors and the length of the progression, the theorem is proved in general.
A D-dimensional arithmetic progression (AP) consists ofnumbers of the form:
a+i1s1+i2s2+ … +iDsD
A -dimensional arithmetic progression with benefits is all numbers of the form above, but where you add on some of the "boundary" of the arithmetic progression, i.e. some of the indices 's can be equal to . The sides you tack on are ones where the first 's are equal to, and the remaining 's are less than .
The boundaries of a -dimensional AP with benefits are these additional arithmetic progressions of dimension
d-1,d-2,d-3,d-4
(L,L,L,L,\ldots,L)
Next define the quantity to be the least integer so that any assignment of colors to an interval of length or more necessarily contains a homogeneous -dimensional arithmetical progression with benefits.
The goal is to bound the size of . Note that is an upper bound for Van der Waerden's number. There are two inductions steps, as follows:
Base case:, i.e. if you want a length 1 homogeneous -dimensional arithmetic sequence, with or without benefits, you have nothing to do. So this forms the base of the induction. The Van der Waerden theorem itself is the assertion that is finite, and it follows from the base case and the induction steps.[9]
Furstenberg and Weiss proved an equivalent form of the theorem in 1978, using ergodic theory.[10] The proof of the above theorem is delicate, and the reader is referred to. With this recurrence theorem, the van der Waerden theorem can be proved in the ergodic-theoretic style.