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.

Für jede natürliche Zahl ${\displaystyle k}${\displaystyle k} und für jedes ${\displaystyle \delta >0}${\displaystyle \delta >0}, existiert ein ${\displaystyle N(k,\delta )}${\displaystyle N(k,\delta )}, sodass jede Teilmenge von ${\displaystyle \{1,....,N\}}${\displaystyle \{1,....,N\}} mit mehr als ${\displaystyle \delta N}${\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)}${\displaystyle r_{k}(N)} die Größe der größten Teilmenge von ${\displaystyle \{1,....,N\}}${\displaystyle \{1,....,N\}} ohne arithmetische Progression der Länge k. Dann gilt ${\displaystyle {\tfrac {r_{k}(N)}{N}}\longrightarrow 0}${\displaystyle {\tfrac {r_{k}(N)}{N}}\longrightarrow 0}.

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

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

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

• Zahlentheorie