Satz von Szemerédi
Van Wikipedia, de gratis encyclopedie
Der Satz von Szemerédi ist ein Resultat aus der Zahlentheorie, das arithmetische Folgen in Mengen natürlicher Zahlen mit positiver Dichte betrifft.
Aussage[Bearbeiten | Quelltext bearbeiten]
Für jede natürliche Zahl und für jedes , existiert ein , sodass jede Teilmenge von mit mehr als Elementen eine arithmetische Folge der Länge k enthält. Äquivalent lässt sich das Theorem auch folgenderweise formulieren:
- Sei die Größe der größten Teilmenge von ohne arithmetische Progression der Länge k. Dann gilt .
Erweiterungen[Bearbeiten | Quelltext bearbeiten]
Es hat sich gezeigt, dass sich die Aussage auf polynomielle Progressionen erweitern lässt. Hat also eine Menge eine positive Dichte und sind Polynome mit ganzzahligen Werten, dann gibt es unendlich viele , sodass .
Der Satz von Szemerédi folgt aus der Erdős-Vermutung über arithmetische Folgen.
Literatur[Bearbeiten | Quelltext bearbeiten]
- Endre Szemerédi: On sets of integers containing no k elements in arithmetic progression. Acta Arith. 27, 199–245 (1975).