But you can't add a ninth integer to the end without creating such a progression.
In fact, there is no way of coloring 1 through 9 without creating such a progression (it can be proved by considering examples).
For the case of r = 2 and k = 3, for example, the argument given below shows that it is sufficient to color the integers {1, ..., 325} 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.
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 {1, ..., 26} with three colors so that there is no single-colored arithmetic progression of length 3; for example: An open problem is the attempt to reduce the general upper bound to any 'reasonable' function.
[5] 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.[6] The best upper bound currently known is due to Timothy Gowers,[7] who establishes 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.
[9] Khinchin[10] gives a fairly simple proof of the theorem without estimating W(r, k).
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).
Similarly, the proof for W(3, 3) depends on proving that 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 of numbers of the form: where a is the basepoint, the s's are positive step-sizes, and the i's range from 0 to L − 1.
A D-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 i's can be equal to L. The sides you tack on are ones where the first k i's are equal to L, and the remaining i's are less than L. The boundaries of a D-dimensional AP with benefits are these additional arithmetic progressions of dimension
The 0-dimensional arithmetic progression is the single point at index value
Next define the quantity MinN(L, D, N) to be the least integer so that any assignment of N colors to an interval of length MinN or more necessarily contains a homogeneous D-dimensional arithmetical progression with benefits.
Note that MinN(L,1,N) is an upper bound for Van der Waerden's number.
There are two inductions steps, as follows: Lemma 1 — Assume MinN is known for a given lengths L for all dimensions of arithmetic progressions with benefits up to D. This formula gives a bound on MinN when you increase the dimension to D + 1: let
The new stride parameter sD + 1 is defined to be the distance between the blocks.
Given an n-coloring of an interval of size MinN(L,n,n), by definition, you can find an arithmetic sequence with benefits of dimension n of length L. But now, the number of "benefit" boundaries is equal to the number of colors, so one of the homogeneous boundaries, say of dimension k, has to have the same color as another one of the homogeneous benefit boundaries, say the one of dimension p < k. This allows a length L + 1 arithmetic sequence (of dimension 1) to be constructed, by going along a line inside the k-dimensional boundary which ends right on the p-dimensional boundary, and including the terminal point in the p-dimensional boundary.
In formulas: if then This constructs a sequence of dimension 1, and the "benefits" are automatic, just add on another point of whatever color.
So doubling the interval size will definitely work, and this is the reason for the factor of two.
This completes the induction on L. Base case: MinN(1,d,n) = 1, i.e. if you want a length 1 homogeneous d-dimensional arithmetic sequence, with or without benefits, you have nothing to do.
The Van der Waerden theorem itself is the assertion that MinN(L,1,N) is finite, and it follows from the base case and the induction steps.
[11] Furstenberg and Weiss proved an equivalent form of the theorem in 1978, using ergodic theory.
[12] multiple Birkhoff recurrence theorem (Furstenberg and Weiss, 1978) — If
[12] With this recurrence theorem, the van der Waerden theorem can be proved in the ergodic-theoretic style.Theorem (van der Waerden, 1927) — If
contains infinitely many arithmetic progressions of arbitrarily long length
Then we can repeat this process to find that there exists at least one partition that contains infinitely many progressions of length