Singmaster guess

The Singmaster conjecture concerns the frequency with which a natural number occurs in Pascal's triangle . According to the conjecture of David Singmaster (1971) there is an upper bound for all natural numbers except one, which is possibly eight.

As Singmaster announced in his 1971 note, Paul Erdős thought the assumption was correct, but also said that the proof would probably be very difficult.

That all numbers except one occur only finitely often follows directly from the definition of Pascal's triangle. It is known that there are infinitely many numbers that appear exactly twice, exactly three times, exactly four times or exactly six times in Pascal's triangle. It is not known whether there are numbers that occur exactly five times or exactly seven times. The only number known to occur exactly eight times is 3003. No numbers are known that occur more frequently, and Pascal's triangle has been calculated numerically for millions of series.

With the Landau symbol , Singmaster's guess is:

Let be the number with which a natural number occurs in Pascal's triangle. Then is .

{\ displaystyle N (a)}

{\ displaystyle a> 1}

{\ displaystyle N (a) = O (1)}

In other words: The number of solutions for given is limited. ${\ displaystyle {\ binom {n} {k}} = a}$ ${\ displaystyle a> 1}$

Singmaster (1971) proved . Paul Erdős, HL Abbott and D. Hanson improved this in 1974 to: ${\ displaystyle N (a) = O (\ log a)}$

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

The best asymptotic estimate was given by Daniel Kane in 2007:

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

Assuming Harald Cramér's unproven conjecture about the asymptotic distribution of the distances between successive prime numbers, Abbot, Erdös and Hanson proved in 1974:

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

for anything . ${\ displaystyle \ varepsilon> 0}$

Examples

Every natural number appears at least twice (only the two appears only once). ${\ displaystyle n> 2}$
${\ displaystyle N (3) = N (4) = N (5) = 2, N (6) = 3}$ .
Every odd prime appears twice.
Each number with prime numbers appears four times. The first number in Pascal's triangle that appears four times is 10. ${\ displaystyle {\ binom {p} {2}}}$ ${\ displaystyle p> 3}$
The number of natural numbers less than or equal to , which occur more than twice, increases as (Abbott, Erdös, Hanson 1974). ${\ displaystyle x}$ ${\ displaystyle O ({\ sqrt {x}})}$
David Sing Master proved 1975 that there are infinitely many natural numbers, at least six times occur in Pascal's triangle, by proving that there is an infinite number of solutions of the Diophantine equation is represented by , are given, wherein the i-th Fibonacci number is. The first number in Pascal's triangle that appears six times is 120. There are six numbers below that that appear six times: 120, 210, 1540, 7140, 11628, and 24310. ${\ displaystyle {\ binom {n + 1} {k + 1}} = {\ binom {n} {k + 2}}}$ ${\ displaystyle n = F_ {2i + 2} F_ {2i + 3} -1}$ ${\ displaystyle k = F_ {2i} F_ {2i + 3} -1}$ ${\ displaystyle F_ {i}}$ ${\ displaystyle 2 ^ {48}}$

Web links

Singmasters conjecture, planetmath

Individual evidence

↑ Singmaster: Research Problems: How often does an integer occur as a binomial coefficient? , American Mathematical Monthly, Volume 78, 1971, pp. 385-386
↑ Singmaster formulated in his essay from 1975 (Fibonacci Quarterly, Volume 13, p. 298) the assumption that no number appears more than ten times and guessed 8 or 12.
↑ That was already found by Singmaster 1971, Am. Math. Monthly, Volume 78, p. 386. He calculated the entries in Pascal's triangle to be less than or equal , later expanded by him to . ${\ displaystyle a = 2 ^ {23}}$ ${\ displaystyle 2 ^ {48}}$
↑ Abbott, Erdös, Hanson: On the number of times an integer occurs as a binomial coefficient , American Mathematical Monthly, Volume 81, 1974, pp. 256-261
↑ 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
↑ Singmaster, Repeated binomial coefficients and Fibonacci numbers , Fibonacci Quarterly, Volume 13, 1975, pp. 295-298. Independently this showed Douglas Lind, Fibonacci Quarterly, Volume 6, 1968, pp. 86-94 (solution of the associated Diophantine equation).
↑ Singmaster, Am. Math. Monthly, 78, 1971, p. 386 for . In 1975 he improved this on . ${\ displaystyle 2 ^ {23}}$ ${\ displaystyle 2 ^ {48}}$

[1] Singmaster: Research Problems: How often does an integer occur as a binomial coefficient? , American Mathematical Monthly, Volume 78, 1971, pp. 385-386

[2] Singmaster formulated in his essay from 1975 (Fibonacci Quarterly, Volume 13, p. 298) the assumption that no number appears more than ten times and guessed 8 or 12.

[3] That was already found by Singmaster 1971, Am. Math. Monthly, Volume 78, p. 386. He calculated the entries in Pascal's triangle to be less than or equal , later expanded by him to . ${\ displaystyle a = 2 ^ {23}}$ ${\ displaystyle 2 ^ {48}}$

[4] Abbott, Erdös, Hanson: On the number of times an integer occurs as a binomial coefficient , American Mathematical Monthly, Volume 81, 1974, pp. 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, Volume 13, 1975, pp. 295-298. Independently this showed Douglas Lind, Fibonacci Quarterly, Volume 6, 1968, pp. 86-94 (solution of the associated Diophantine equation).

[7] Singmaster, Am. Math. Monthly, 78, 1971, p. 386 for . In 1975 he improved this on . ${\ displaystyle 2 ^ {23}}$ ${\ displaystyle 2 ^ {48}}$