Satz von Szemerédi

mathematischer Satz

Der Satz von Szemerédi ist ein Resultat aus der Zahlentheorie, das arithmetische Folgen in Mengen natürlicher Zahlen mit positiver Dichte betrifft.

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

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
  • Endre Szemerédi: On sets of integers containing no k elements in arithmetic progression. Acta Arith. 27, 199–245 (1975).