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$ .