Erdős-Vermutung über arithmetische Folgen

Die Erdős-Vermutung über arithmetische Folgen ist ein ungelöstes Problem aus der Zahlentheorie. Die Vermutung besagt, dass jede Menge ${\displaystyle A}$ mit

${\displaystyle \sum _{n\in A}{\frac {1}{n}}\ =\ \infty ,}$

eine arithmetische Folge beliebiger Länge enthält.

Zunächst stellten Paul Erdős und Paul Turán im Jahre 1936 die schwächere Vermutung auf, dass jede Menge positiver ganzer Zahlen mit positiver Dichte unendlich viele arithmetische Folgen der Länge 3 enthalten müsse. Das wurde von Klaus Friedrich Roth im Jahre 1952 bewiesen.

1976 bot Erdős 3000 US-Dollar für die Lösung des Problems. Es ist bisher ungelöst (Stand: 2021).

Die Reziprokenreihe jeder Menge mit positiver Dichte divergiert, daher folgt aus der Vermutung von Erdős der Satz von Szemerédi.

Der Satz von Green-Tao besagt, dass die Primzahlen beliebig lange arithmetische Folgen enthalten. Das ergibt sich aus der Erdős-Vermutung, weil die Reihe der Primzahl-Reziproken divergiert.

Der Beweis ergibt sich aus einem Widerspruch. Nehme an, dass die Reihe ${\displaystyle \sum _{p\in P}{\frac {1}{p}}}$ konvergiert. Dann gibt es eine natürliche Zahl ${\displaystyle k}$ mit ${\displaystyle \sum _{i\geq k+1}{\frac {1}{p_{i}}}<{\frac {1}{2}}}$. Nenne die Primzahlen ${\displaystyle p_{1},p_{2},....,p_{k}}$ kleine Primzahlen und die anderen ${\displaystyle p_{k+1},p_{k+2},....}$ große Primzahlen. Für eine natürliche Zahl ${\displaystyle N}$ gilt

${\displaystyle \sum _{i\geq k+1}{\frac {N}{p_{i}}}<{\frac {N}{2}}}$.

Sei ${\displaystyle N_{b}}$ die Anzahl der positiven ganzen Zahlen ${\displaystyle n\leq N}$, die durch mindestens eine große Primzahl teilbar sind, und ${\displaystyle N_{s}}$ die Anzahl jener, die nur kleine Primteiler besitzen. Wir werden zeigen, dass für ein geeignetes ${\displaystyle N}$ ${\displaystyle N_{b}+N_{s}<N}$ gilt, was den gewünschten Widerspruch erzeugt. Um ${\displaystyle N_{b}}$ abzuschätzen, bemerke man, dass ${\displaystyle \lfloor {\frac {N}{p_{i}}}\rfloor }$ die positiven ganzen Zahlen ${\displaystyle n\leq N}$ zählt, die Vielfaches von ${\displaystyle p_{i}}$ sind. Wir erhalten daraus

${\displaystyle N_{b}\leq \sum _{i\geq k+1}{\frac {N}{p_{i}}}<{\frac {N}{2}}}$. (2)

Nun betrachten wir ${\displaystyle N_{s}}$. Wir schreiben jede Zahl ${\displaystyle n\leq N}$, die nur kleine Primteiler hat, in der Form ${\displaystyle n=a_{n}b_{n}^{2}}$, wobei ${\displaystyle a_{n}}$ den quadratfreien Teil bezeichnet. Jedes ${\displaystyle a_{n}}$ ist dann ein Produkt von verschiedenen kleinen Primzahlen, und wir schließen, dass es genau ${\displaystyle 2^{k}}$ verschiedene quadratfreie Teile gibt. Weiter sehen wir wegen ${\displaystyle b_{n}\leq {\sqrt {n}}\leq N}$, dass es höchstens ${\displaystyle {\sqrt {N}}}$ verschiedene Quadratteile gibt, und es folgt ${\displaystyle N_{s}\leq 2^{k}{\sqrt {N}}}$.

Da (2) für jedes ${\displaystyle N}$ gilt, müssen wir nur eine Zahl ${\displaystyle N}$ finden, die ${\displaystyle 2^{k}{\sqrt {N}}\leq {\frac {N}{2}}}$ bzw., ${\displaystyle 2^{k+1}\leq {\sqrt {N}}}$ erfüllt. Solch eine Zahl ist zum Beispiel ${\displaystyle N=2^{2k+2}}$.

• Klaus F. Roth: On certain sets of integers. J. Lond. Math. Soc. 28, 104–109 (1953).