www.wikidata.de-de.nina.az

Satz von van der Waerden Dieser Artikel behandelt einen Lehrsatz der Ramseytheorie Wegen eines Satzes von van der Waerde

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

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.

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

mit einem verwandten Beweis des Satzes von Szemerédi.

Ferner gilt etwa für :

für alle positiven ε.

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

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 … 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 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. (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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Dieser Artikel behandelt einen Lehrsatz der Ramseytheorie Wegen eines Satzes von van der Waerden in der Mengenlehre siehe Satz von van der Waerden Zerlegung endlicher Mengen 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 fur alle naturlichen Zahlen r displaystyle r und l displaystyle l eine naturliche Zahl N N r l displaystyle N N r l existiert so dass gilt Farbt man die Zahlen 1 2 N displaystyle 1 2 ldots N mit r displaystyle r Farben so existiert eine arithmetische Progression der Lange l displaystyle l in 1 2 N displaystyle 1 2 ldots N die gleich gefarbt monochrom ist Eine arithmetische Progression der Lange l displaystyle l ist das Anfangsstuck einer arithmetischen Folge so ist z B 3 33 63 93 displaystyle 3 33 63 93 eine arithmetische Progression der Lange 4 vier Zahlen mit gleichen Abstanden hier 30 Eine arithmetische Progression der Lange 2 ist jede zweielementige Teilfolge der naturlichen Zahlen Der Satz nennt nur die Existenz einer endlichen Zahl N r l displaystyle N r l Im Folgenden bezeichnet N r l displaystyle N r l die kleinste naturliche Zahl mit der obigen Eigenschaft Eine Formel dafur wie gross genau diese Zahl fur allgemeine r l displaystyle r l ist ist bisher nicht bekannt Inhaltsverzeichnis 1 Beispiele 2 Werte von N r l van der Waerden Zahlen 3 Beweisskizze 3 1 Vorbemerkung 3 2 Beweisskizze 3 2 1 Schritt 1 An einer Stelle ist eine Farbe ausgeschlossen 3 2 2 Schritt 2 An einer Stelle wird eine weitere Farbe ausgeschlossen 3 2 3 Schritt 3 Die letzte mogliche Farbe wird an einer Stelle ausgeschlossen 3 3 Zum allgemeinen Beweis 4 Literatur 5 EinzelnachweiseBeispiele BearbeitenFur l 2 displaystyle l 2 nbsp ist der Satz unabhangig von r displaystyle r nbsp einfach ist etwa r 4 displaystyle r 4 nbsp und bezeichnen wir die Farben mit Rot Blau Gelb und Weiss so stellt man fest dass N 4 2 5 displaystyle N 4 2 5 nbsp ist egal wie man die Farbe fur die 5 displaystyle 5 nbsp wahlt eine Farbe ist doppelt Das ist das sogenannte Schubfachprinzip 1 2 3 4 5 B R G W Fur l 3 displaystyle l 3 nbsp und r 3 displaystyle r 3 nbsp ohne die Farbe Weiss 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 displaystyle 17 nbsp wahlt erhalt man eine gleichfarbige arithmetische Progression bei Rot 11 14 17 displaystyle 11 14 17 nbsp bei Blau 9 13 17 displaystyle 9 13 17 nbsp und bei Gelb 3 10 17 displaystyle 3 10 17 nbsp oben jeweils unterstrichen Werte von N r l van der Waerden Zahlen BearbeitenTrivialerweise ist N 1 l l displaystyle N 1 l l nbsp da die Farbung dann etwa BBB B mit der einen Farbe B ist Wie oben gesehen impliziert das Schubfachprinzip N r 2 r 1 displaystyle N r 2 r 1 nbsp Einige bekannte nichttriviale Werte und Schranken sind der folgenden Tabelle zu entnehmen 1 2 r l 3 4 5 6 72 Farben 9 35 178 1 132 gt 3 703 3 Farben 27 gt 292 gt 2 173 gt 11 191 gt 43 855 4 Farben 76 gt 1 048 gt 17 705 gt 91 331 gt 393 469 5 Farben gt 170 gt 2 254 gt 98 740 gt 540 025 Timothy Gowers fand 2001 3 die allgemeine Schranke N r l 2 2 r 2 2 l 9 displaystyle N r l leq 2 2 r 2 2 l 9 nbsp mit einem verwandten Beweis des Satzes von Szemeredi Ferner gilt etwa fur N 2 l displaystyle N 2 l nbsp N 2 l gt 2 l l ϵ displaystyle N 2 l gt 2 l l epsilon nbsp fur alle positiven e 4 Fur die van der Waerden Zahlen fur 2 Farben und Primzahlen p displaystyle p nbsp gilt ferner 5 N 2 p 1 gt p 2 p displaystyle N 2 p 1 gt p cdot 2 p nbsp Beweisskizze BearbeitenVorbemerkung Bearbeiten Folgende Beobachtung ist wichtig Jede Farbung mit r displaystyle r nbsp Farben impliziert eine Farbung mit r 2 displaystyle r 2 nbsp Farben wenn man z B Muster der Lange m 2 displaystyle m 2 nbsp betrachtet Im obigen Beispiel mit 3 Farben hat man 3 3 9 displaystyle 3 cdot 3 9 nbsp 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 naturlich z B fur Muster der Lange m 4 hier gibt es dann im obigen Beispiel r m 3 4 81 displaystyle r m 3 4 81 nbsp Kombinationen Das obige Beispiel liefert 1 2 3 4 5 6 7 8 9 BRGR RGRR GRRB RRBG RBGG BGGB GGBG GBGR BGRR Farbt man also die Zahlen 1 85 displaystyle 1 ldots 85 nbsp mit 3 Farben und betrachtet die an den Stellen 1 82 beginnenden Muster der Lange 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 Fur die ursprungliche 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 vollstandige Induktion nach l displaystyle l nbsp gleichzeitig fur alle r displaystyle r nbsp Fur l 2 displaystyle l 2 nbsp ist er oben schon bewiesen Schubfachprinzip man setze N r 2 r 1 displaystyle N r 2 r 1 nbsp Wir versuchen den Satz fur drei Farben Rot Blau Gelb und Lange l 3 displaystyle l 3 nbsp zu beweisen Schritt 1 An einer Stelle ist eine Farbe ausgeschlossen Bearbeiten Bei einer 3 Farbung der Zahlen 1 bis 85 muss ein Abschnitt der Lange 4 doppelt auftreten etwa GBRB Innerhalb dieses Abschnitts muss eine Farbe doppelt sein hier Blau Der Abstand d 1 displaystyle d 1 nbsp zwischen den gleichgefarbten Positionen 2 und 4 ist hier gleich 2 der Abstand d 2 displaystyle d 2 nbsp zwischen den gleichgefarbten Blocken gleich 10 Man kann die Abschnitte auch langer wahlen etwa Lange 7 Anstatt 85 3 4 1 3 displaystyle 85 3 4 1 3 nbsp muss man nun 2194 3 7 1 6 displaystyle 2194 3 7 1 6 nbsp Stellen betrachten damit ein Abschnitt der Lange 7 doppelt vorkommt Es gibt m 2187 3 7 displaystyle m 2187 3 7 nbsp Muster der Lange 7 Angenommen dieser doppelte Abschnitt beginnt wieder mit GBRB sieht also so aus GBRB Die steht fur 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 Lange 3 vor Stellen 2 4 6 Schritt 2 An einer Stelle wird eine weitere Farbe ausgeschlossen Bearbeiten Farbt man nun die Zahlen von 1 bis 2187 1 6 2194 displaystyle 2187 1 6 2194 nbsp mit 3 Farben und betrachtet die bei 1 2188 displaystyle 1 ldots 2188 nbsp beginnenden Muster der Lange 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 Fur den Abstand gilt hier d 2 500 displaystyle d 2 500 nbsp Unsere Farbung 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 Verlangerung von 4 auf 7 geschehen langere Muster wir nehmen etwa das Doppelte farben also die Zahlen von 1 bis 2 2194 4388 displaystyle 2 cdot 2194 4388 nbsp Dann ist im Intervall 1 4388 displaystyle 1 ldots 4388 nbsp unabhangig von d 2 displaystyle d 2 nbsp auf jeden Fall der um d 2 displaystyle d 2 nbsp verschobene Bereich enthalten d 2 displaystyle d 2 nbsp hatte ja statt 500 auch 2000 sein konnen 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 ware Rot fur Gelb gilt die gleiche Argumentation Betrachtet man Y Stelle 1105 so ist man fertig wenn Y R gilt denn dann ist die Farbung 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 Farbung 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 mogliche Farbe wird an einer Stelle ausgeschlossen Bearbeiten Das Argument wird nun wiederholt jetzt mit Mustern der Lange 4388 Dazu mussen N 34388 4388 Zahlen gefarbt werden eine Zahl mit gut zweitausend Stellen wobei wir wie oben wieder einen grob doppelt so grossen Bereich farben damit wieder der rechts um die entsprechende Differenz verschobene Bereich noch enthalten ist Wir nehmen an dass unser oben angegebenes Muster der Lange 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 fur Z Stelle 31105 Wahlt 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 Wahlt 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 Wahlt 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 lasst 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 BearbeitenEric 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 Einzelnachweise Bearbeiten Archivierte Kopie Memento vom 1 Oktober 2015 im Internet Archive N 2 l displaystyle N 2 l nbsp ist Folge A005346 in OEIS und N r 3 displaystyle N r 3 nbsp ist Folge A135415 in OEIS Timothy Gowers A new proof of Szemeredi s theorem In Geom Funct Anal 11 3 2001 S 465 588 dpmms cam ac uk 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 E Berlekamp A construction for partitions which avoid long arithmetic progressions In Canadian Mathematics Bulletin 11 1968 S 409 414 Abgerufen von https de wikipedia org w index php title Satz von van der Waerden amp oldid 236559509