Satz von van der Waerden

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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 | Quelltext 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]

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

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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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.

Einzelnachweise

[Bearbeiten | Quelltext 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.