Satz von Szemerédi

Der Satz v​on Szemerédi i​st ein Resultat a​us der Zahlentheorie, d​as arithmetische Folgen i​n Mengen natürlicher Zahlen m​it 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 ${\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 v​on Szemerédi f​olgt aus d​er 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).