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 8 liegt.

Hintergrund

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.

Postulat und Folgerungen

Mit dem Landau-Symbol lautet Singmasters Vermutung:

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

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

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

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

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

${\displaystyle 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:

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

für beliebiges ${\displaystyle \varepsilon >0}$.

Beispiele

• Jede natürliche Zahl ${\displaystyle n>2}$ tritt mindestens zweimal auf (nur die Zwei tritt nur einmal auf). Die Zahl 1, die konstruktionsbedingt unendlich oft vorkommt nimmt man aus diesen Betrachtungen heraus.
• ${\displaystyle N(3)=N(4)=N(5)=2,N(6)=3}$.
• ${\displaystyle N(3003)=8}$ ist die größte bisher bekannte Zahl, die im Pascalschen Dreieck am häufigsten vorkommt
• Jede ungerade Primzahl kommt zweimal vor.
• Jede Zahl ${\displaystyle {\binom {p}{2}}}$ mit Primzahlen ${\displaystyle p>3}$ tritt viermal auf. Die erste Zahl im Pascalschen Dreieck, die viermal vorkommt, ist 10.
• Die Anzahl der natürlichen Zahlen kleiner gleich ${\displaystyle x}$, die mehr als zweimal vorkommen, wächst wie ${\displaystyle 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 ${\displaystyle {\binom {n+1}{k+1}}={\binom {n}{k+2}}}$ gibt, die durch ${\displaystyle n=F_{2i+2}F_{2i+3}-1}$, ${\displaystyle k=F_{2i}F_{2i+3}-1}$ gegeben sind, wobei ${\displaystyle F_{i}}$ die i-te Fibonaccizahl ist. Die erste Zahl im Pascalschen Dreieck, die sechsmal auftritt, ist 120. Es gibt sechs Zahlen unterhalb von ${\displaystyle 2^{48}}$, die sechsmal vorkommen: 120, 210, 1540, 7140, 11628 und 24310.

Weblinks

• Singmasters conjecture, planetmath

Einzelnachweise

1. ↑ Singmaster: Research Problems: How often does an integer occur as a binomial coefficient ?, American Mathematical Monthly, Band 78, 1971, S. 385–386
2. ↑ Singmaster formulierte in seinem Aufsatz von 1975 (Fibonacci Quarterly, Band 13, S. 298) die Vermutung so, dass keine Zahl mehr als zehnmal auftritt und tippte auf 8 oder 12.
3. ↑ Das fand schon Singmaster 1971, Am. Math. Monthly, Band 78, S. 386. Er berechnete die Einträge im Pascalschen Dreieck kleiner gleich ${\displaystyle a=2^{23}}$, später von ihm auf ${\displaystyle 2^{48}}$ erweitert.
4. ↑ Abbott, Erdös, Hanson: On the number of times an integer occurs as a binomial coefficient, American Mathematical Monthly, Band 81, 1974, S. 256–261
5. ↑ Kane, Improved bounds on the number of ways of expressing t as a binomial coefficient, in: Integers: Electronic Journal of Combinatorial Number Theory, 7, 2007
6. ↑ Singmaster, Repeated binomial coefficients and Fibonacci numbers, Fibonacci Quarterly, Band 13, 1975, S. 295–298. Unabhängig zeigte das Douglas Lind, Fibonacci Quarterly, Band 6, 1968, S. 86–94 (Lösung der zugehörigen diophantischen Gleichung).
7. ↑ Singmaster, Am. Math. Monthly, 78, 1971, S. 386 für ${\displaystyle 2^{23}}$. 1975 verbesserte er dies auf ${\displaystyle 2^{48}}$.