Satz von Szemerédi

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

Aussage

Für jede natürliche Zahl ${\displaystyle k}$ und für jedes ${\displaystyle \delta >0}$, existiert ein ${\displaystyle N(k,\delta )}$, sodass jede Teilmenge von ${\displaystyle \{1,....,N\}}$ mit mehr als ${\displaystyle \delta N}$ Elementen eine arithmetische Folge der Länge k enthält. Äquivalent lässt sich das Theorem auch folgenderweise formulieren:

Sei ${\displaystyle r_{k}(N)}$ die Größe der größten Teilmenge von ${\displaystyle \{1,....,N\}}$ ohne arithmetische Progression der Länge k. Dann gilt ${\displaystyle {\tfrac {r_{k}(N)}{N}}\longrightarrow 0}$.

Erweiterungen

Es hat sich gezeigt, dass sich die Aussage auf polynomielle Progressionen erweitern lässt. Hat also eine Menge ${\displaystyle A\subset N}$ eine positive Dichte und sind ${\displaystyle p_{1},p_{2},....,p_{k}}$ Polynome mit ganzzahligen Werten, dann gibt es unendlich viele ${\displaystyle u,n\in N}$, sodass ${\displaystyle u+p_{i}(n)\in A}$.

Der Satz von Szemerédi folgt aus der Erdős-Vermutung über arithmetische Folgen.

Literatur

• Endre Szemerédi: On sets of integers containing no k elements in arithmetic progression. Acta Arith. 27, 199–245 (1975).