Van der Waerden's theorem

This article deals with a theorem of Ramsey theory. Because of a van der Waerden theorem in set theory see van der Waerden's theorem (decomposition of finite sets) !

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

It says that for all natural numbers and there exists a natural number such that: ${\displaystyle r}$ ${\displaystyle l}$ ${\displaystyle N(r,l)}$

If you color the numbers with "colors", there is an arithmetic progression of the length in which is colored in the same way ( monochrome ). ${\displaystyle 1,2,\ldots ,N}$ ${\displaystyle r}$ ${\displaystyle l}$ ${\displaystyle 1,2,\ldots ,N}$

An arithmetic progression of length is the beginning of an arithmetic sequence . B. an arithmetic progression of length 4 (four equally spaced numbers, here 30). An arithmetic progression of length 2 is any two-element subsequence of the natural numbers. ${\displaystyle l}$ ${\displaystyle 3,33,63,93}$

The proposition only names the existence of a finite number ; a formula for exactly how large this number is for general is not yet known. ${\displaystyle N(r,l)}$ ${\displaystyle r,l}$

Examples

For the kit - regardless of - simple: is about and we denote the colors with R ot, B lau, G elb and W hite, it is found that ${\displaystyle l=2}$ ${\displaystyle r}$ ${\displaystyle r=4}$

${\displaystyle N(4,2)=5}$

is: no matter how you choose the color for them , one color is double. This is the so-called drawer principle . ${\displaystyle 5}$

      1 2 3 4 5
      B R G W ?

For and (without the color W hite) an example here: ${\displaystyle l=3}$ ${\displaystyle r=3}$

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
      B R G R R B G G B G  R  R  B  R  R  B  ?

No matter what color is in the selected one obtains a same color arithmetic progression: wherein R ot at, B lau and G elb (above each underlined). ${\displaystyle 17}$ ${\displaystyle 11,14,17}$ ${\displaystyle 9,13,17}$ ${\displaystyle 3,10,17}$

Values ​​of - van der Waerden numbers ${\displaystyle N(r,l)}$

Trivially it is

${\displaystyle \,N(1,l)=l,}$

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

As seen above implies the drawer principle

${\displaystyle \,N(r,2)=r+1.}$

Some known nontrivial values ​​and bounds can be found in the following table.

r \ k	3	4th	5	6th	7th
2 colors	9	35	178	1,132	> 3,703
3 colors	27	> 292	> 2.173	> 11,191	> 43,855
4 colors	76	> 1,048	> 17,705	> 91,331	> 393,469
5 colors	> 170	> 2,254	> 98,740	> 540.025

Timothy Gowers found the general bound in 2001

${\displaystyle N(r,l)\leq 2^{2^{r^{2^{2^{l+9}}}}}}$

with a related proof of Szemerédi's theorem .

The following also applies to : ${\displaystyle N(2,l)}$

${\displaystyle N(2,l)>2^{l}/l^{\epsilon }\,}$

for all positive ε.

For the van der Waerden numbers for 2 colors and prime numbers, the following also applies ${\displaystyle p}$

${\displaystyle N(2,p+1)>p\cdot 2^{p}.}$

Evidence sketch

Preliminary remark

The following observation is important: Any coloring with colors implies coloring with colors, e.g. B. Considered pattern of length . In the example above with 3 colors you have patterns BB, BG, BR, ... RR . ${\displaystyle r}$ ${\displaystyle r^{2}}$ ${\displaystyle m=2}$ ${\displaystyle 3\cdot 3=9}$

     1  2  3  4  5  6  7  8  9  10 …
     BR RG GR RR RB BG GG GB BG GR …

The same applies of course z. B. for patterns of length m = 4  - here there are combinations in the above example . The above example provides ${\displaystyle r^{m}=3^{4}=81}$

    1    2    3    4    5    6    7    8    9    …
    BRGR RGRR GRRB RRBG RBGG BGGB GGBG GBGR BGRR …

If you color the numbers with 3 colors and look at the pattern of length 4 (there are 82) beginning at positions 1 ... 82, one of the first 82 appears twice, for example at positions 20 and 30: ${\displaystyle 1\ldots 85}$

   1    2    … 20   … 30   …
  BRGR RGRR … GBRB … GBRB …

For the original episode this means:

     1 2 3 4 5 … 20 21 22 23 … 30 31 32 33 …
   B R G R R … G  B  R  B …  G  B  R  B  …

Evidence sketch

It proves the proposition by induction by the same for all . For it has already been proven above (drawer principle), one set ${\displaystyle l}$ ${\displaystyle r}$ ${\displaystyle l=2}$ ${\displaystyle N(r,2)=r+1.}$

We are trying to set for three colors R ot, B tepid, G elb and length to prove. ${\displaystyle l=3}$

Step 1: One color is excluded at one point

If the numbers 1 to 85 are colored 3, a section of length 4 must appear twice, such as GBRB . Be twice within this section has a color (here B lue).

The distance between the same colored positions (2 and 4) is here equal to 2, the distance between the same colored blocks is equal to 10. ${\displaystyle d_{1}}$ ${\displaystyle d_{2}}$

You can also choose longer sections about length 7. Instead of looking at points so that a section of length 7 appears twice. (There are 7 length patterns.) ${\displaystyle 85=3^{4}+1+3}$ ${\displaystyle 2194=3^{7}+1+6}$ ${\displaystyle m=2187=3^{7}}$

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

Only the color X is of interest here in the 6th position GBRB_ X _ . Assuming that X = B , then there is already a blue arithmetic progression of length 3 (digits 2, 4, 6).

Step 2: At one point another color is excluded

If you color the numbers from 1 to 3 colors and look at the pattern of length 7 that begins at the beginning (the last one ends at 2194), at least two of them are the same. We assume that these are the positions 100 and 600 and the pattern is the same as our known pattern GBRB_X_ . For the distance applies here . Our coloring then looks like this: ${\displaystyle 2187+1+6=2194}$ ${\displaystyle 1\ldots 2188}$ ${\displaystyle d_{2}=500}$

  1 … 100 101 102 103 104 105 106 … 600 601 602 603 604 605 606 … 2194
    … G   B   R   B   _   X   _   … G   B   R   B   _   X   _   …

Again we look at longer patterns, as we did above with the extension from 4 to 7, we take about double that, so we color the numbers from 1 to . Then the interval , regardless of , definitely contains the area shifted by ( could have been 2000 instead of 500). Here the area starts at position 1100, but we are only interested in position 1105. ${\displaystyle 2\cdot 2194=4388}$ ${\displaystyle 1\ldots 4388}$ ${\displaystyle d_{2}}$ ${\displaystyle d_{2}}$ ${\displaystyle d_{2}}$

 1 … 100     … 600     …  1.100    … 4388
   … GBRB_X_ … GBRB_X_ …  _____Y_  …

As noted above, may X not B be tepid, we assume X would be R ot (for yellow applies the same reasoning). Considering Y (position 1105), so it is ready when Y = R true, because then the coloring at 105, 605 and 1105 is equal to R . The distance from 105 to 605 and from 605 to 1105 is equal to d ₂ = 500 .

 1 … 100     … 600     …  1.100    … 4388
   … GBRB_R_ … GBRB_R_ …  _____R_  …

The same applies when Y = B , because then the coloring at 101, 603, and 1105 is equal to B . The distance between the positions is now d ₁  + d ₂  = 502

 1 … 100     … 600     …  1100    … 4388
   … GBRB_R_ … GBRB_R_ …  _____B_ …

Thus, only remains Y = G .

Step 3: The last possible color is excluded at one point

The argument is now repeated, now with patterns of length 4388. To do this, N = 3 ⁴³⁸⁸  + 4388 numbers have to be colored (a number with a good two thousand digits), whereby we color an area roughly twice as large as above, so again the one on the right The range shifted by the corresponding difference is still included.

We assume that our pattern of length 4388 given above occurs in positions 10000 and 20000. d ₃  = 10000 .

… 10100   … 10600    … 11100   … … 20100   … 20600   … 21100   … … 30100   … 30600   … 31100   …
… GBRB_R_ … GBRB_R_  … _____G_ … … GBRB_R_ … GBRB_R_ … _____G_ … …  ______ … _______ … _____Z_ …

Which choice now remains for Z (position 31105)?

• If you choose Z = G , you have the color G at positions 11105, 21105, 31105 (distance d ₃  = 10000 ):

 … 10100   … 10600    … 11100   … … 20100   … 20600   … 21100   … … 30100   … 30600   … 31100   …
… GBRB_R_ … GBRB_R_  … _____G_ … … GBRB_R_ … GBRB_R_ … _____G_ … …  ______ … _______ … _____Z_ …

• If you choose Z = R , you have the color R at the points 10105, 20605, 31105 (distance d ₂  + d ₃  = 10500 ):

… 10100   … 10600    … 11100   … … 20100   … 20600   … 21100   … … 30100   … 30600   … 31100   …
… GBRB_R_ … GBRB_R_  … _____G_ … … GBRB_R_ … GBRB_R_ … _____G_ … …  ______ … _______ … _____Z_ …

• If you choose Z = B , you have the color B at points 10101, 20603, 31105 (distance d ₁  + d ₂  + d ₃  = 10502 ):

 … 10100   … 10600    … 11100   … … 20100   … 20600   … 21100   … … 30100   … 30600   … 31100   …
… GBRB_R_ … GBRB_R_  … _____G_ … … GBRB_R_ … GBRB_R_ … _____G_ … …  ______ … _______ … _____Z_ …

For general proof

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

The upper bounds obtained in this way grow very quickly, much faster than the exponential growth .

literature

• Eric W. Weisstein : van der Waerden's theorem . In: MathWorld (English). - Eric W. Weisstein : van der Waerden Number . In: MathWorld (English).
• P. Herwig, MJH Heule, M. van Lambalgen, H. van Maaren: A new method to construct lower bounds for Van der Waerden numbers . In: The Electronic Journal of Combinatorics , 14, 2007. st.ewi.tudelft.nl (PDF)
• RL Graham , BL Rothschild: A Short Proof of van der Waerdens Theorem on Arithmetic Progressions. In: Procreedings of the American Mathematical Society , Vol. 42, No. 2, Feb. 1974, math.ucsd.edu (PDF)

Individual evidence

1. ↑ Archived copy ( Memento from October 1, 2015 in the Internet Archive )
2. ↑ Timothy Gowers : A new proof of Szemerédi's theorem . In: Geom. Funct. Anal. , 11 (3), 2001, pp. 465-588, dpmms.cam.ac.uk
3. ^ Tom C. Brown: A partition of the non-negative integers, with applications to Ramsey theory . In: M. Sethumadhavan (Ed.): Discrete Mathematics And Its Applications . Alpha Science Int'l, 2006, ISBN 81-7319-731-8 , p. 80.
4. ^ E. Berlekamp: A construction for partitions which avoid long arithmetic progressions . In: Canadian Mathematics Bulletin , 11, 1968, pp. 409-414.