Singmaster-Vermutung

Die Singmaster-Vermutung betrifft die Häufigkeit, mit der eine natürliche Zahl im Pascalschen Dreieck vorkommt. Nach der Vermutung von David Singmaster (1971) gibt es für jede natürliche Zahl außer der Eins eine obere Schranke, die möglicherweise bei acht liegt.

Wie Singmaster in seiner Note von 1971 mitteilte, hielt Paul Erdős die Vermutung für richtig, meinte aber auch, dass der Beweis wahrscheinlich sehr schwierig sei.

Dass alle Zahlen außer der Eins nur endlich oft vorkommen, folgt unmittelbar aus der Definition des Pascalschen Dreiecks. Es ist bekannt, dass es unendlich viele Zahlen gibt, die genau zweimal, genau dreimal, genau viermal oder genau sechsmal im Pascalschen Dreieck auftreten. Nicht bekannt ist, ob es Zahlen gibt, die genau fünfmal oder genau siebenmal vorkommen. Die einzige Zahl, von der bekannt ist, dass sie genau achtmal auftritt, ist 3003. Es sind keine Zahlen bekannt, die häufiger vorkommen, und Pascals Dreieck ist numerisch für Millionen von Reihen berechnet worden.

Mit dem Landau-Symbol lautet Singmasters Vermutung:

Sei $N(a)$ die Anzahl, mit der eine natürliche Zahl $a>1$ im Pascalschen Dreieck vorkommt. Dann ist $N(a)=O(1)$.

Anders formuliert: Die Anzahl der Lösungen von ${\binom {n}{k}}=a$ bei vorgegebenem $a>1$ ist beschränkt.

Singmaster (1971) bewies $N(a)=O(\log a)$. Paul Erdős, H. L. Abbott und D. Hanson verbesserten das 1974 auf:

$N(a)=O\left({\frac {\log a}{\log \log a}}\right).$

Die beste asymptotische Abschätzung wurde von Daniel Kane 2007 gegeben:

$N(a)=O\left({\frac {(\log a)(\log \log \log a)}{(\log \log a)^{3}}}\right),$

Unter Voraussetzung der unbewiesenen Vermutung von Harald Cramér über die asymptotische Verteilung der Abstände aufeinanderfolgender Primzahlen bewiesen Abbot, Erdös und Hanson 1974:

$N(a)=O\left(\log(a)^{2/3+\varepsilon }\right)$

für beliebiges $\varepsilon >0$.

Beispiele

• Jede natürliche Zahl $n>2$ tritt mindestens zweimal auf (nur die Zwei tritt nur einmal auf).
• $N(3)=N(4)=N(5)=2,N(6)=3$.
• Jede ungerade Primzahl kommt zweimal vor.
• Jede Zahl ${\binom {p}{2}}$ mit Primzahlen $p>3$ tritt viermal auf. Die erste Zahl im Pascalschen Dreieck, die viermal vorkommt, ist 10.
• Die Anzahl der natürlichen Zahlen kleiner gleich $x$, die mehr als zweimal vorkommen, wächst wie $O({\sqrt {x}})$ (Abbott, Erdös, Hanson 1974).
• David Singmaster bewies 1975, dass es unendlich viele natürliche Zahlen gibt, die mindestens sechsmal im Pascalschen Dreieck vorkommen, indem er bewies, dass es unendliche viele Lösungen der diophantischen Gleichung ${\binom {n+1}{k+1}}={\binom {n}{k+2}}$ gibt, die durch $n=F_{2i+2}F_{2i+3}-1$, $k=F_{2i}F_{2i+3}-1$ gegeben sind, wobei $F_{i}$ die i-te Fibonaccizahl ist. Die erste Zahl im Pascalschen Dreieck, die sechsmal auftritt, ist 120. Es gibt sechs Zahlen unterhalb von $2^{48}$, die sechsmal vorkommen: 120, 210, 1540, 7140, 11628 und 24310.

Weblinks

• Singmasters conjecture, planetmath