Satz von van der Waerden

Der Satz von van der Waerden (nach Bartel Leendert van der Waerden) ist ein 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=N(r,l)$ existiert, so dass gilt:

Färbt man die Zahlen $1,2,\ldots ,N$ mit $r$ „Farben“, so existiert eine arithmetische Progression der Länge $l$ in $1,2,\ldots ,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 jede zweielementige Teilfolge der natürlichen Zahlen.

Der Satz nennt nur die Existenz einer endlichen Zahl $N(r,l)$. Im Folgenden bezeichnet $N(r,l)$ die kleinste natürliche Zahl mit der obigen Eigenschaft. 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.

r\l	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 die allgemeine Schranke

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

mit einem verwandten Beweis des Satzes von Szemerédi.

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

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

für alle positiven ε.

Für die van-der-Waerden-Zahlen für 2 Farben und Primzahlen $p$ gilt ferner

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

Beweisskizze

Vorbemerkung

Folgende Beobachtung ist wichtig: Jede Färbung mit $r$ Farben impliziert eine Färbung mit $r^{2}$ Farben, wenn man z. B. Muster der Länge $m=2$ betrachtet. Im obigen Beispiel mit 3 Farben hat man $3\cdot 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^{4}=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\ldots 85$ mit 3 Farben und betrachtet die an den Stellen 1 … 82 beginnenden Muster der Länge 4 (es gibt 82), 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

Bei einer 3-Färbung der Zahlen 1 bis 85 muss ein Abschnitt der Länge 4 doppelt auftreten, etwa GBRB. Innerhalb dieses Abschnitts muss eine Farbe doppelt sein (hier Blau).

Der Abstand $d_{1}$ zwischen den gleichgefärbten Positionen (2 und 4) ist hier gleich 2, der Abstand $d_{2}$ zwischen den gleichgefärbten Blöcken gleich 10.

Man kann die Abschnitte auch länger wählen etwa Länge 7. Anstatt $85=3^{4}+1+3$ muss man nun $2194=3^{7}+1+6$ Stellen betrachten, damit ein Abschnitt der Länge 7 doppelt vorkommt. (Es gibt $m=2187=3^{7}$ 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_. Angenommen, es ist X = B, dann liegt bereits eine blaue arithmetische Progression der Länge 3 vor (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\ldots 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_{2}=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\cdot 2194=4388$. Dann ist im Intervall $1\ldots 4388$, unabhängig von $d_{2}$ auf jeden Fall der um $d_{2}$ verschobene Bereich enthalten ($d_{2}$ 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. In: MathWorld (englisch). – Eric W. Weisstein: van der Waerden Number. In: MathWorld (englisch).
• P. Herwig, M.J.H. 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)
• 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, math.ucsd.edu (PDF)