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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |j-i|} angehört. Nach Ramsey’s Theorem existiert in dem Graphen ein einfarbiges Dreieck und dessen Ecken seien Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a<b<c} . Dann folgt, da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b-a, c-b} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c-a} einfarbig sind. Mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=b-a, y=c-b} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z=c-a} gilt dann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x+y=z} . Damit ist der Satz bewiesen.

Verallgemeinerung

Neben dem Satz von Rado kann eine Verallgemeinerung erreicht werden, wenn statt der Gleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x+y=z} die Gleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{L}(t): x_1 + \ldots + x_{t-1} = x_t} betrachtet wird.

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r \geq 1} und für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq i \leq r} sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k_i \geq 3} . Dann existiert eine kleinste Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(k_1, \ldots, k_r) \in \mathbb{N}^+} , so dass jede Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} -Färbung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [1,S(r)]} wenigstens ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j \in \{1, \ldots, r\}} existiert, dass eine Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{L}(k_j)} der Farbe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} existiert.

Eine andere Verallgemeinerung untersucht die Gleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^2+y^2=z^2} . Die kleinste Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} , so dass jede 2-Färbung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [1,N]} ein einfarbiges pythagoräisches Tripel zulässt, ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \not= y} und im verallgemeinerten Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i \not= x_j} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \not= j} ist. Vor allem in diesem Gebiet wurden bisher nur wenige obere und untere Schranken untersucht.

Sonstiges

• Die Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s(r)} werden Schur-Zahlen genannt.
• Die Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(r)} heißen allgemeine Schur-Zahlen.
• Die Tripel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{x,y,z\}} , die obigem Satz genügen heißen Schur-Tripel.
• Die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} -Tupel der Verallgemeinerung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \geq s(r), S(r)} existieren.

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.