Satz von Van der Waerden

Der Satz von Van der Waerden (nach Bartel Leendert van der Waerden) ist ein berühmter Satz aus der Kombinatorik, genauer aus der Ramseytheorie.

Er besagt, dass für alle natürlichen Zahlen r und l eine natürliche Zahl N(r,l) existiert, so dass gilt:

Färbt man die Zahlen 1, 2, … N mit r „Farben“, so existiert eine arithmetische Progression der Länge l in 1, 2, … N, die gleich gefärbt (monochrom) ist.

Eine arithmetische Progression der Länge l ist das Anfangsstück einer arithmetischen Folge, so ist z. B. 3, 33, 63, 93 eine arithmetische Progression der Länge 4 (vier Zahlen mit gleichen Abständen, hier 30). Eine arithmetische Progression der Länge 2 ist übrigens jede zweielementige Teilmenge der natürlichen Zahlen.

Der Satz nennt nur die Existenz einer endlichen Zahl N(r,l); eine Formel dafür, wie groß genau diese Zahl für allgemeine r,l ist, ist bisher nicht bekannt.

Beispiele

Für l = 2 ist der Satz - unabhängig von r - einfach: ist etwa r = 4 und bezeichnen wir die Farben mit Rot, Blau, Gelb und Weiß, so stellt man fest, dass

N(4,2) = 5

ist: egal wie man die Farbe für die 5 wählt, eine Farbe ist doppelt. Das ist das sogenannte Schubfachprinzip.

      1 2 3 4 5 
      B R G W ?

Für l = 3 und r = 3 (ohne die Farbe Weiß) hier ein Beispiel:

      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  ?

Egal, welche Farbe man bei der 17 wählt, erhält man eine gleichfarbige arithmetische Progression: bei Rot 11, 14, 17, bei Blau 9, 13, 17 und bei Gelb 3, 10, 17 (oben jeweils unterstrichen).

Werte von N(r,l) – van der Waerden-Zahlen

Trivialerweise ist

$\, N(1,l)=l,$

da die Färbung dann etwa BBB…B mit der einen Farbe B ist.

Wie oben gesehen impliziert das Schubfachprinzip

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

Einige bekannte nichttriviale Werte und Schranken sind der folgenden Tabelle zu entnehmen.^[1]

r\k	3	4	5	6	7
2 Farben	9	35	178	1.132	> 3.703
3 Farben	27	> 292	> 2.173	> 11.191	> 43.855
4 Farben	76	> 1.048	> 17.705	> 91.331	> 393.469
5 Farben	> 170	> 2.254	> 98.740	> 540.025

Timothy Gowers fand 2001^[2] die allgemeine Schranke

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

mit einem verwandten Beweis des Satzes von Szemerédi.

Ferner gilt etwa für W(2,l):

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

für alle posoitiven ε.^[3]

Für die van der Waerden-Zahlen für 2 Farben und Primzahlen p gilt ferner^[4]

$N(2,p+1)>p\cdot2^p.$

Beweisskizze

Vorbemerkung

Folgende Beobachtung ist wichtig: Jede Färbung mit r Farben impliziert eine Färbung - mit r² Farben, wenn man z. B. Muster der Länge m = 2 betrachtet. Im obigen Beispiel mit 3 Farben hat man 3 × 3 = 9 Muster BB, BG, BR, … RR.

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

Analoges gilt natürlich z. B. für Muster der Länge m = 4 - hier gibt es dann im obigen Beispiel r^m = 3⁴ = 81 Kombinationen. Das obige Beispiel liefert

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

Färbt man also die Zahlen 1 … 85 mit 3 Farben und betrachtet die an den Stellen 1 … 82 beginnenden Muster der Länge 4 (es gibt 81), kommt unter den ersten 82 eine doppelt vor, etwa an Stelle 20 und 30:

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

Für die ursprüngliche Folge bedeutet das:

   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  …

Beweisskizze

Man beweist den Satz durch vollständige Induktion nach l gleichzeitig für alle r. Für l = 2 ist er oben schon bewiesen (Schubfachprinzip), man setze N(r,2) = r + 1.

Wir versuchen, den Satz für drei Farben Rot, Blau, Gelb und Länge l = 3 zu beweisen.

Schritt 1: An einer Stelle ist eine Farbe ausgeschlossen

In der Vorbemerkung konnte man sehen, dass bei einer 3-Färbung der Zahlen 1 bis 85 ein Abschnitt der Länge 4 doppelt auftreten musste, etwa GBRB. Außerdem musste in diesem Abschnitt eine Farbe doppelt sein (hier Blau), der Abstand d₁ zwischen den gleichgefärbten Positionen (2 und 4) ist hier gleich 2.

Das gleiche Argument gilt analog, wenn man die Abschnitte etwas länger wählt, etwas der Länge 7. Statt 85 = m = 3⁴ + 1 + 3 muss man nun bis zur 2194 = m = 3⁷ + 1 + 6  =  mit den drei Farben färben, damit sich ein Abschnitt der Länge 7 doppelt vorkommt. (Es gibt m = 3⁷ = 2187 Muster der Länge 7.)

Angenommen, dieser doppelte Abschnitt beginnt wieder mit GBRB, sieht also so aus: GBRB_ _ _. Die _ steht für irgendeine der drei Farben.

Es interessiert nur die Farbe X hier an der 6. Stelle GBRB_X_.

Man sieht, dass, wenn X = B gilt, bereits eine blaue arithmetische Progression der Länge 3 vorliegt (Stellen 2, 4, 6).

Schritt 2: An einer Stelle wird eine weitere Farbe ausgeschlossen

Färbt man nun die Zahlen von 1 bis 2187 + 1 + 6 = 2194 mit 3 Farben und betrachtet die bei 1 … 2188 beginnenden Muster der Länge 7 (das letzte endet bei 2194), sind wenigstens zwei davon gleich. Wir nehmen an, das sind die Stellen 100 und 600 und das Muster gleiche unserem bekannten Muster GBRB_X_. Für den Abstand gilt hier d₂ = 500. Unsere Färbung sieht dann so aus:

 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   _   …

Wieder betrachten wir, wie oben schon bei der Verlängerung von 4 auf 7 geschehen, längere Muster, wir nehmen etwa das doppelte, färben also die Zahlen von 1 bis 2 · 2194 = 4388. Dann ist im Intervall 1 … 4388, unabhängig von d₂ auf jeden Fall der um d₂ verschobene Bereich enthalten (d₂ hätte ja statt 500 auch 2000 sein können). Hier beginnt der Bereich bei Position 1100, uns interessiert aber nur die Stelle 1105.

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

Wie oben bemerkt, darf X nicht Blau sein, nehmen wir an, X wäre Rot (für Gelb gilt die gleiche Argumentation). Betrachtet man Y (Stelle 1105), so ist man fertig, wenn Y = R gilt, denn dann ist die Färbung bei 105, 605 und 1105 gleich R. Der Abstand von 105 zu 605 und von 605 zu 1105 ist gleich d₂=500.

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

Gleiches gilt wenn Y = B, denn dann ist die Färbung bei 101, 603 und 1105 gleich B. Der Abstand der Stellen ist nun d₁ + d₂ = 502

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

Somit verbleibt nur Y = G.

Schritt 3: Die letzte mögliche Farbe wird an einer Stelle ausgeschlossen

Das Argument wird nun wiederholt, jetzt mit Mustern der Länge 4388. Dazu müssen N = 3⁴³⁸⁸ + 4388 Zahlen gefärbt werden (eine Zahl mit gut zweitausend Stellen), wobei wir wie oben wieder einen grob doppelt so großen Bereich färben, damit wieder der rechts um die entsprechende Differenz verschobene Bereich noch enthalten ist.

Wir nehmen an, dass unser oben angegebenes Muster der Länge 4388 an den Stellen 10000 und 20000 vorkommt. d₃ = 10000.

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

Welche Wahl verbleibt nun für Z (Stelle 31105)?

• Wählt man Z = G, hat man die Farbe G an den Stellen 11105, 21105, 31105 (Abstand d₃ = 10000):

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

• Wählt man Z = R, hat man die Farbe R an den Stellen 10105, 20605, 31105 (Abstand d₂ + d₃ = 10500):

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

• Wählt man Z = B, hat man die Farbe B an den Stellen 10101, 20603, 31105 (Abstand d₁ + d₂ + d₃ = 10502):

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

Zum allgemeinen Beweis

Der oben angegebene Induktionsschritt lässt sich nun verallgemeinern. Die Zahl der Iterationen ist gleich der Zahl der Farben.

Die so erhaltenen oberen Schranken wachsen sehr schnell, viel schneller als das exponentielle Wachstum.

Literatur

• Eric W. Weisstein: van der Waerden's Theorem und van der Waerden Number auf MathWorld
• P. Herwig, M.J.H. Heule, M. van Lambalgen, H. van Maaren: A new method to construct lower bounds for Van der Waerden numbers. The Electronic Journal of Combinatorics 14, 2007. PDF
• R.L. Graham, B.L. Rothschild: A Short Proof of van der Waerdens Theorem on Arithmetic Progressions. In: Procreedings of the American Mathematical Society, Vol. 42, Nr. 2, Feb. 1974. PDF

Einzelnachweise

1. ↑ http://www.st.ewi.tudelft.nl/sat/slides/waerden.pdf
2. ↑ Timothy Gowers: A new proof of Szemerédi's theorem, Geom. Funct. Anal., 11(3): S. 465-588, 2001. Online-Version bei http://www.dpmms.cam.ac.uk/~wtg10/papers.html.
3. ↑ Tom C. Brown: A partition of the non-negative integers, with applications to Ramsey theory. In: M. Sethumadhavan (Hrsg.): Discrete Mathematics And Its Applications, S. 80, Alpha Science Int'l Ltd. 2006, ISBN 8173197318
4. ↑ E. Berlekamp: A construction for partitions which avoid long arithmetic progressions, In Canadian Mathematics Bulletin 11 (1968), S. 409–414.