Erdős-Vermutung über arithmetische Folgen
# 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}}\ =\ \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\geq 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\geq k+1}{\frac {N}{p_{i}}}<{\frac {N}{2}}$.

Sei $N_{b}$ die Anzahl der positiven ganzen Zahlen $n\leq 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\leq N$ zählt, die Vielfaches von $p_{i}$ sind. Wir erhalten daraus

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

Nun betrachten wir $N_{s}$. Wir schreiben jede Zahl $n\leq 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}\leq {\sqrt {n}}\leq N$, dass es höchstens ${\sqrt {N}}$ verschiedene Quadratteile gibt, und es folgt $N_{s}\leq 2^{k}{\sqrt {N}}$.

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

