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 und eine natürliche Zahl existiert, so dass gilt:

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

Eine arithmetische Progression der Länge ist das Anfangsstück einer arithmetischen Folge, so ist z. B. 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 . Im Folgenden bezeichnet die kleinste natürliche Zahl mit der obigen Eigenschaft. Eine Formel dafür, wie groß genau diese Zahl für allgemeine ist, ist bisher nicht bekannt.

Beispiele

Bearbeiten

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

 

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

      1 2 3 4 5
      B R G W ?

Für   und   (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   wählt, erhält man eine gleichfarbige arithmetische Progression: bei Rot  , bei Blau   und bei Gelb   (oben jeweils unterstrichen).

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

Bearbeiten

Trivialerweise ist

 

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

Wie oben gesehen impliziert das Schubfachprinzip

 

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

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[3] die allgemeine Schranke

 

mit einem verwandten Beweis des Satzes von Szemerédi.

Ferner gilt etwa für  :

 

für alle positiven ε.[4]

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

 

Beweisskizze

Bearbeiten

Vorbemerkung

Bearbeiten

Folgende Beobachtung ist wichtig: Jede Färbung mit   Farben impliziert eine Färbung mit   Farben, wenn man z. B. Muster der Länge   betrachtet. Im obigen Beispiel mit 3 Farben hat man   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   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   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 … GBRBGBRB

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

Bearbeiten

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

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

Schritt 1: An einer Stelle ist eine Farbe ausgeschlossen

Bearbeiten

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   zwischen den gleichgefärbten Positionen (2 und 4) ist hier gleich 2, der Abstand   zwischen den gleichgefärbten Blöcken gleich 10.

Man kann die Abschnitte auch länger wählen etwa Länge 7. Anstatt   muss man nun   Stellen betrachten, damit ein Abschnitt der Länge 7 doppelt vorkommt. (Es gibt   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

Bearbeiten

Färbt man nun die Zahlen von 1 bis   mit 3 Farben und betrachtet die bei   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  . 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  . Dann ist im Intervall  , unabhängig von   auf jeden Fall der um   verschobene Bereich enthalten (  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 d2=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 d1 + d2 = 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

Bearbeiten

Das Argument wird nun wiederholt, jetzt mit Mustern der Länge 4388. Dazu müssen N = 34388 + 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. d3 = 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 d3 = 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 d2 + d3 = 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 d1 + d2 + d3 = 10502):
 … 10100   … 10600    … 11100   … … 20100   … 20600   … 21100   … … 30100   … 30600   … 31100   …
… GBRB_R_ … GBRB_R_  … _____G_ … … GBRB_R_ … GBRB_R_ … _____G_ … …  ______ … _______ … _____Z_ …

Zum allgemeinen Beweis

Bearbeiten

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

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Archivierte Kopie (Memento vom 1. Oktober 2015 im Internet Archive)
  2.   ist Folge A005346 in OEIS, und   ist Folge A135415 in OEIS
  3. Timothy Gowers: A new proof of Szemerédi’s theorem. In: Geom. Funct. Anal., 11(3), 2001, S. 465–588, dpmms.cam.ac.uk
  4. Tom C. Brown: Discrete Mathematics And Its Applications. Hrsg.: M. Sethumadhavan. Alpha Science Int’l, 2006, ISBN 81-7319-731-8, A partition of the non-negative integers, with applications to Ramsey theory, S. 80.
  5. E. Berlekamp: A construction for partitions which avoid long arithmetic progressions. In: Canadian Mathematics Bulletin, 11, 1968, S. 409–414.