Satz von Schur

Der Satz von Schur liefert in der Diskreten Mathematik Aussagen, wie groß eine Zahlenmenge $[1,s(r)]$ sein muss, damit für jede beliebige $r$ -Färbung dieser stets eine einfarbige Lösung existiert. Dieser Satz war ursprünglich ein Hilfssatz in einer Veröffentlichung von Issai Schur im Jahre 1916 gewesen. Dabei war Schur gar nicht darauf aus, die Färbung von Punkten in der Ebene zu untersuchen, sondern vielmehr Fermats letzten Satz (welcher erst durch einen Beweis im Jahre 1995 zum Satz wurde). Obwohl zwölf Jahre vor Ramsey gefunden, gilt er als erster Satz der Ramseytheorie.

Formulierung des Satzes

Hintergrund

Im Satz werden Färbungsprobleme der Ebene betrachtet. Sei $z=x+y$ eine einfache Ebene und ${\mathcal {P}}$ die Menge aller Punkte der Ebene mit positiven ganzzahligen Koordinaten. Beispielsweise $(1,1,2)$ und $(3,4,7)$ , wobei diesmal $x$ und $y$ nicht zwangsweise verschieden sein müssen. Nun wird eine endliche Menge Farben gewählt und jeder natürlichen Zahl eine Farbe zugeordnet.

Danach werden alle Punkte $(x,y,z)\in {\mathcal {P}}$ genau dann mit der entsprechenden Farbe eingefärbt, wenn die Färbung von $x,y$ und $z$ auf dem Zahlenstrahl identisch ist. Alle so nicht berücksichtigten Punkte werden mit einem $X$ markiert. Es bleibt die Frage, ob die Existenz eines gefärbten Punktes gesichert ist, oder die Möglichkeit besteht, jeden Punkt der Ebene mit einem $X$ zu markieren. In anderen Worten, ob eine Färbung für $\mathbb {N} ^{+}$ existiert, so dass kein Punkt $(x,y,z)\in {\mathcal {P}}$ farbig ist. Diese Frage beantwortet der Satz von Schur.

Satz

Für jedes $r\geq 1$ existiert ein kleinstes $s(r)\in \mathbb {N} ^{+}$ , so dass für jede $r$ -Färbung von $[1,s(r)]$ eine einfarbige Lösung zu $x+y=z$ existiert.

Beweis

Es sei $r\geq 1$ . Der Satz von Ramsey sichert die Existenz der Zahl $n=R(3;r)$ , für eine beliebige $r$ -Färbung des vollständigen Graphen $K_{n}$ mit $n$ Knoten, die Existenz eines einfarbigen Dreiecks. Wir wählen unsere Färbung wie folgt. Die Knoten des $K_{n}$ werden mit $1\ldots n$ durchnummeriert und die Menge $\{1,\ldots ,n-1\}$ in $r$ disjunkte Teilmengen zerlegt. Diese Mengen sollen den $r$ Farben entsprechen. Nun wird die Kante, die die Knoten $i$ und $j$ verbindet mit der Farbe der Menge eingefärbt, der $|j-i|$ angehört. Nach Ramsey’s Theorem existiert in dem Graphen ein einfarbiges Dreieck und dessen Ecken seien $a<b<c$ . Dann folgt, da $b-a,c-b$ und $c-a$ einfarbig sind. Mit $x=b-a,y=c-b$ und $z=c-a$ gilt dann $x+y=z$ . Damit ist der Satz bewiesen.

Verallgemeinerung

Neben dem Satz von Rado kann eine Verallgemeinerung erreicht werden, wenn statt der Gleichung $x+y=z$ die Gleichung ${\mathcal {L}}(t):x_{1}+\ldots +x_{t-1}=x_{t}$ betrachtet wird.

Sei $r\geq 1$ und für jedes $1\leq i\leq r$ sei $k_{i}\geq 3$ . Dann existiert eine kleinste Zahl $S(k_{1},\ldots ,k_{r})\in \mathbb {N} ^{+}$ , so dass jede $r$ -Färbung von $[1,S(r)]$ wenigstens ein $j\in \{1,\ldots ,r\}$ existiert, dass eine Lösung ${\mathcal {L}}(k_{j})$ der Farbe $j$ existiert.

Eine andere Verallgemeinerung untersucht die Gleichung $x^{2}+y^{2}=z^{2}$ . Die kleinste Zahl $N$ , so dass jede 2-Färbung von $[1,N]$ ein einfarbiges pythagoräisches Tripel zulässt, ist $N=7825$ .

Spezialisierung

Für den originalen und für den verallgemeinerten Fall kann jeweils untersucht werden, ob die Existenz dieser Zahlen vorliegt, wenn zusätzlich verlangt wird, dass zunächst $x\not =y$ und im verallgemeinerten Fall $x_{i}\not =x_{j}$ für $i\not =j$ ist. Vor allem in diesem Gebiet wurden bisher nur wenige obere und untere Schranken untersucht.

Sonstiges

Die Zahlen $s(r)$ werden Schur-Zahlen genannt.
Die Zahlen $S(r)$ heißen allgemeine Schur-Zahlen.
Die Tripel $\{x,y,z\}$ , die obigem Satz genügen heißen Schur-Tripel.
Die $t$ -Tupel der Verallgemeinerung $\{x_{1},\ldots ,x_{t}\}$ heißen Schur-t-Tupel.
Der Satz von Rado stellt eine Verallgemeinerung des Schurschen Theorems dar.

Während bei den Schurschen Zahlen sich der Forschungsschwerpunkt auf die Bestimmung von Schranken bezieht, interessiert bei den Tupeln die Anzahl, also wie viele der Tupel für $n\geq s(r),S(r)$ existieren.

Einzelnachweise

↑ Issai Schur: Über die Kongruenz $x^{m}+y^{m}\equiv z^{m}\ \left(\operatorname {mod} \ p\right).$ In: Jahresbericht der DMV. Bd. 25. Teubner, Stuttgart 1917, S. 114–117.
↑ Bruce M Landman, Aaron Robertson: Ramsey Theory on the Integers. AMS, Rhode Island 2004, S. 199–200.
↑ Heule, Kullmann, Marek: Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer
↑ Nature News: Two-hundred-terabyte maths proof is largest ever

Literatur

Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer: Ramsey Theory. 2. Auflage. Wiley, New York NY 1990, ISBN 0-471-50046-1.
Bruce M. Landman, Aaron Robertson: Ramsey Theory on the Integers. 1. Auflage. AMS, Rhode Island 2004, ISBN 0-8218-3199-2.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Issai Schur: Über die Kongruenz $x^{m}+y^{m}\equiv z^{m}\ \left(\operatorname {mod} \ p\right).$ In: Jahresbericht der DMV. Bd. 25. Teubner, Stuttgart 1917, S. 114–117.

[2] Bruce M Landman, Aaron Robertson: Ramsey Theory on the Integers. AMS, Rhode Island 2004, S. 199–200.

[3] Heule, Kullmann, Marek: Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer

[4] Nature News: Two-hundred-terabyte maths proof is largest ever