Van der Waerden's theorem

The set of van der Waerden ( Bartel Leendert van der Waerden after ) is a set of combinatorics, precisely from the Ramsey theory.

He states that there exists for all natural numbers and a natural number, so that applies:

An arithmetic progression of the length of the initial part of an arithmetic sequence, then, for example, 3, 33, 63, 93 an arithmetic progression of length 4 ( four numbers at equal intervals, in this case 30). An arithmetic progression of the two-element length of two, each part of the set of natural numbers.

The sentence mentions only the existence of a finite number; a formula for how large is this number for general, is not yet known.

Examples

For l = 2 the set is - independent of r - simple is about r = 4, and we denote the colors red, blue, yellow and white, it is found that

Is: no matter how one chooses the color for the 5, a color is double. This is called the pigeonhole principle.

1 2 3 4 5 B R G W? For l = 3 and r = 3 (without the color white ) Here is an example:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 B R G R G B R G B G B R R R R B? No matter what color you choose for the 17, you get a same color arithmetic progression: at Red 11, 14, 17, Blue 9, 13, 17 and Yellow 3, 10, 17 ( above each underlined).

Values of N (r, l) - van der Waerden figures

Trivially

Since the coloring about BBB ... B with one color B is then.

As seen above, implies the pigeonhole principle

Some well-known nontrivial values and bounds are given in the following table.

With a related proof of the theorem of Szemerédi.

Further, about applies to:

For all positive ε.

Also applies to the van der Waerden numbers for 2 colors and primes

Sketch of proof

Preliminary

The following observation is important: Each coloring with r colors implies a coloring with r2 colors when m = 2 For example, consider the pattern length. In the above example with three colors has 3 x 3 = 9 Sample BB, BG, BR, ... RR.

1 2 3 4 5 6 7 8 9 10 ... RG GR BR RR GG GB BG BG RB GR ... The same applies, of course, for example, for patterns of length m = 4 - there is then in the above example rm = 34 = 81 combinations. The above example provides

1 2 3 4 5 6 7 8 9 ... Brgr RGRR GRRB RRBG RBGG BGGB GGBG GBGR BGRR ... So you color the numbers 1 ... 85 with 3 colors and looks at the beginning at the points 1 ... 82 patterns of length 4 (there are 82) is a double front in the top 82, such as at point 20 and 30:

1 2 ... 20 ... 30 ... Brgr RGRR ... GBRB ... GBRB ... For the original sequence, this means:

1 2 3 4 5 ... 20 21 22 23 ... 30 31 32 33 ... B G R R R R B B ... G ... G B R B ... sketch of proof

One proves the theorem by induction on l the same for all r. For l = 2 it is already proved above ( pigeonhole principle ), we set N ( r, 2) = r 1

We try = 3 to prove the theorem for three colors red, blue, yellow and length l.

Step 1: At one point, a color is excluded

In the preface, you could see that with a 3- coloring of the numbers 1 to 85, a portion of the length 4 had to occur twice, about GBRB. This section also had a color twice his ( here blue ), the distance d1 between the like- colored items ( 2 and 4) is here equal to 2

The same argument applies to when you choose a little longer sections, some of the length 7 instead of 85 = m = 34 1 3 one has now to 2194 = m = color 37 1 6 = three colors, so that a portion of the length 7 occurs twice. ( There are m = 37 = 2187 patterns of length 7 )

Suppose this double section begins with GBRB, so looks like this: __ GBRB_. The _ stands for any of the three colors.

It only interested in the color X here at the 6th place GBRB_X_.

It is seen that, when X = B is valid, already a blue arithmetic progression of length 3 is present ( positions 2, 4, 6).

Step 2: At one point, another color excluded

If dyeing is now the numbers from 1 to 2187 1 6 = 2194 with 3 colors and looks at the 1 ... 2188 incipient pattern of length 7 (the last one ends at 2194 ), at least two of them are the same. We assume that these are the points 100 and 600 and the pattern of our same familiar pattern GBRB_X_. For the distance here d2 = 500 Our coloring then looks like this:

1 ... 100 101 102 103 104 105 106 ... 600 601 602 603 604 605 606 ... 2194 _ X _ ... GBRB ... GBRB _ X _ ... Again, we consider, as already happened to 7 in the extension of 4, extended patterns, we take about twice, so color the numbers from 1 to 2 × 2194 = 4388th Then in the interval 1 ... 4388, regardless of d2 any case, the contained area shifted to d2 (d2 would have held 500 may also be 2000). Here, the range starts at position 1100, but we are interested in only the place 1105.

1 ... 100 ... 600 ... 1100 ... 4388 GBRB_X_ GBRB_X_ ... ... ... ... Y_ _____ As noted above, X may not be blue, we assume that X would be red ( for yellow applies the same reasoning ). Considering Y (position 1105), so it is ready when Y = R is true, because then the coloring is at 105, 605 and 1105 equal to R. The distance from 105 to 605 and from 605 to 1105 is equal to d2 = 500

1 ... 100 ... 600 ... 1100 ... 4388 GBRB_R_ GBRB_R_ ... ... ... _____ R_ ... The same applies if Y = B, because then the coloring is the same for 101, 603 and 1105 B. The distance between the points is now d1 d2 = 502

1 ... 100 ... 600 ... 1100 ... 4388 GBRB_R_ GBRB_R_ ... ... ... _____ B_ ... Thus, there remains only Y = G.

Step 3: The final color is excluded at a position

The argument is now repeated, now with patterns of length 4388th This requires N = 34388 4388 numbers are colored (a number with more than two thousand places ), where we color as above again a roughly twice as large area, so that again the right to the corresponding difference shifted range is listed.

We assume that our above specified pattern of length 4388 occurs at the points 10000 and 20000. d3 = 10,000.

10100 ... 10600 ... 11100 ... 20100 ... 20600 ... 21100 ...... ...... 30100 ... 30600 ... 31100 ... GBRB_R_ GBRB_R_ ... ... ... _____ G_ ...... GBRB_R_ ... GBRB_R_ ... _____ G_ ...... ______ ... _______ ... _____ Z_ ... What choice now remains for Z (position 31105 )?

If we choose Z = G, one has G color at the points 11105, 21105, 31105 ( distance d3 = 10000 ):

The above induction step can be generalized now. The number of iterations is equal to the number of colors.

The resulting upper bounds are growing very fast, much faster than the exponential growth.

Timothy Gowers Wolfram Research Ronald Graham

710526