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 $A$ mit

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

eine arithmetische Folge beliebiger Länge enthält.

Geschichte

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

Folgerungen

Satz von Szemerédi

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

Satz von Green-Tao

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 $\sum _{p\in P}\frac{1}{p}$ konvergiert. Dann gibt es eine natürliche Zahl $k$ mit $\sum _{i\ge k+1}\frac{1}{p_i}<\frac{1}{2}$. Nenne die Primzahlen $p_1,p_2,....,p_k$ kleine Primzahlen und die anderen $p_{k+1},p_{k+2},....$ große Primzahlen. Für eine natürliche Zahl $N$ gilt

$\sum _{i\ge k+1}\frac{N}{p_i}<\frac{N}{2}$.

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

$N_b\le \sum _{i\ge k+1}\frac{N}{p_i}<\frac{N}{2}$. (2)

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

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

Literatur

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