Erdős-Woods-Vermutung

Die Erdős-Woods-Vermutung aus der Zahlentheorie von Alan Robert Woods, aufgestellt 1981 in seiner Dissertation, besagt:

Gegeben sei eine beliebige ganze Zahl $n\geq 2$. Dann gibt es eine positive ganze Zahl $k$, so dass $n$ durch die Liste der Primfaktoren von $n+1,\dotsc ,n+k$ eindeutig bestimmt wird.

Man beachte, dass nur die Liste der Primfaktoren vorgegeben ist, nicht deren Multiplizität. Die Vermutung ist nur in Spezialfällen bewiesen.

Bezeichnet man mit $rad(m)$ die Menge der verschiedenen Primfaktoren von $m$, so lässt sie sich auch so formulieren:

Es gibt eine ganze Zahl $k\geq 3$, so dass aus $rad(n+i)=rad(m+i)$ für $i=1,2,\dotsc ,k$ folgt $m=n$.

Die Vermutung ist zusätzlich nach Paul Erdős benannt, da dieser 1980 eine Vermutung aufstellte, aus der die Erdős-Woods-Vermutung folgte (wie Woods explizit anmerkte).

Beispiele

Es gilt $k\geq 3$, da für kleinere Werte Gegenbeispiele angegeben werden können.

• Gegenbeispiel für $k=1$:

Sei $n:=8=2^{3}$ und $m:=26=2\cdot 13$.

Dann ist $n+1=9=3^{2}$ und $m+1=27=3^{3}$ und somit $rad(n+1)=rad(m+1)=\{3\}$.

Es ist $m\not =n$, somit wurde ein Gegenbeispiel der Erdős-Woods-Vermutung für den Fall $k=1$ gefunden.

• Gegenbeispiel für $k=2$:

Sei $n:=74=2\cdot 37$ und $m:=1214=2\cdot 607$.

Dann ist $n+1=75=3\cdot 5^{2}$ und $m+1=1215=3^{5}\cdot 5$ und somit $rad(n+1)=rad(m+1)=\{3,5\}$.

Weiters ist $n+2=76=2^{2}\cdot 19$ und $m+2=1216=2^{6}\cdot 19$ und somit $rad(n+2)=rad(m+2)=\{2,19\}$.

Es ist $m\not =n$, somit wurde ein Gegenbeispiel der Erdős-Woods-Vermutung für den Fall $k=2$ gefunden.

• Beispiel für $k=3$:

Sei $n:=26=2\cdot 13$.

Dann ist $n+1=27=3^{3}$ und somit $rad(n+1)=\{3\}$.

Es ist $n+2=28=2^{2}\cdot 7$ und somit $rad(n+2)=\{2,7\}$.

Weiters ist $n+3=29\in \mathbb {P}$ eine Primzahl und somit $rad(n+3)=\{29\}$.

Es gibt tatsächlich keine andere natürliche Zahl $m\in \mathbb {N}$, sodass $rad(n+i)=rad(m+i)$ mit $i=1,2,3$ gilt. Grund dafür ist der folgende Satz:

Sei $p\geq 5$ eine Primzahl und $n=p-3$. Dann ist die Erdős-Woods-Vermutung wahr mit $k=3$.

Wissenswertes

Die Vermutung folgt aus der unbewiesenen abc-Vermutung: Michel Langevin bewies 1993 unter Annahme der abc-Vermutung, dass $k=3$ für $n>C$ mit einer Konstante $C$. Die Erdős-Woods Vermutung wird durch unendlich viele ganze Zahlen $n$ erfüllt. Weiter ist sogar für $k=2$ die Anzahl positiver ganzer Zahlen $n\leq x$, die die Vermutung erfüllen, mindestens $d{\frac {x}{\log x}}$ mit einer Konstante $d>2$ (Subburam, Thangadurai).

In der Dissertation von Woods ging es darum, ob die Multiplikation in einer logischen Sprache über den natürlichen Zahlen definierbar ist, in der es das Prädikat des Nachfolgers einer natürlichen Zahl gibt und das Prädikat, dass zwei Zahlen keine gemeinsamen Primfaktoren haben (das Problem stammte von Julia Robinson). Woods bewies, dass dies äquivalent zu der Erdős-Woods-Vermutung ist. Außerdem bewies er, dass die Definierbarkeit der Multiplikation äquivalent zu der Definierbarkeit jeweils von Addition, Gleichheit und der Kleiner-Gleich-Relation ist.