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

Sei $r_{k}(N)$ die Größe der größten Teilmenge von $\{1,....,N\}$ ohne arithmetische Progression der Länge k. Dann gilt ${\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 $A\subset N$ eine positive Dichte und sind $p_{1},p_{2},....,p_{k}$ Polynome mit ganzzahligen Werten, dann gibt es unendlich viele $u,n\in N$, sodass $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).