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 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{n} \leq \sqrt n \leq N} , dass es höchstens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sqrt N} verschiedene Quadratteile gibt, und es folgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N_{s}\leq 2^k \sqrt N} .

Da (2) für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} gilt, müssen wir nur eine Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} finden, die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^k \sqrt N \leq \frac{N}{2}} bzw., Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{k+1} \leq \sqrt N} erfüllt. Solch eine Zahl ist zum Beispiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N=2^{2k+2}} .

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.

Literatur

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