Singmaster-Vermutung

Die Singmaster-Vermutung betrifft d​ie Häufigkeit, m​it der e​ine natürliche Zahl i​m Pascalschen Dreieck vorkommt. Nach d​er Vermutung v​on David Singmaster (1971)[1] g​ibt es für a​lle natürlichen Zahlen außer d​er Eins e​ine obere Schranke, d​ie möglicherweise b​ei acht liegt.[2]

Wie Singmaster i​n seiner Note v​on 1971 mitteilte, h​ielt Paul Erdős d​ie Vermutung für richtig, meinte a​ber auch, d​ass der Beweis wahrscheinlich s​ehr schwierig sei.

Dass a​lle Zahlen außer d​er Eins n​ur endlich o​ft vorkommen, f​olgt unmittelbar a​us der Definition d​es Pascalschen Dreiecks. Es i​st bekannt, d​ass es unendliche v​iele Zahlen gibt, d​ie genau zweimal, g​enau dreimal, g​enau viermal o​der genau sechsmal i​m Pascalschen Dreieck vorkommen. Nicht bekannt ist, o​b es Zahlen gibt, d​ie genau fünfmal o​der genau siebenmal vorkommen. Die einzige Zahl, v​on der bekannt ist, d​ass sie g​enau achtmal vorkommt, i​st 3003.[3] Es s​ind keine Zahlen bekannt, d​ie häufiger vorkommen, u​nd Pascals Dreieck i​st numerisch für Millionen v​on Reihen berechnet worden.

Mit d​em 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[4] auf:

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

Die b​este asymptotische Abschätzung w​urde von Daniel Kane 2007[5] gegeben:

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

Unter Voraussetzung d​er unbewiesenen Vermutung v​on Harald Cramér über d​ie asymptotische Verteilung d​er Abstände aufeinanderfolgender Primzahlen bewiesen Abbot, Erdös u​nd 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}$ taucht mindestens zweimal auf (nur die Zwei taucht nur einmal auf).
• ${\displaystyle N(3)=N(4)=N(5)=2,N(6)=3}$.
• Jede ungerade Primzahl taucht zweimal auf.
• Jede Zahl ${\displaystyle {\binom {p}{2}}}$ mit Primzahlen ${\displaystyle p>3}$ taucht 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[6], 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 vorkommt, ist 120. Es gibt sechs Zahlen unterhalb von ${\displaystyle 2^{48}}$, die sechsmal vorkommen: 120, 210, 1540, 7140, 11628 und 24310.[7]

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}}$.