Singmaster's conjecture is a conjecture in combinatorial number theory, named after the British mathematician David Singmaster who proposed it in 1971. It says that there is a finite upper bound on the multiplicities of entries in Pascal's triangle (other than the number 1, which appears infinitely many times). It is clear that the only number that appears infinitely many times in Pascal's triangle is 1, because any other number x can appear only within the first x + 1 rows of the triangle.
Statement Let N(a) be the number of times the number a > 1 appears in Pascal's triangle. In big O notation, the conjecture is:
N ( a ) = O ( 1 ) . {\displaystyle N(a)=O(1).}
In other words, there exists a natural number M {\textstyle M} such that:
N ( a ) ≤ M f o r a l l a . {\displaystyle N(a)\leq M\ \qquad ~{\mathsf {\ for\ all\ }}~\quad a.}
Known bound Singmaster (1971) showed that
N ( a ) = O ( log a ) . {\displaystyle N(a)=O(\log a).}
Abbott, Erdős, and Hanson (1974) (see References) refined the estimate to:
N ( a ) = O ( log a log log a ) . {\displaystyle N(a)=O\left({\frac {\log a}{\log \log a}}\right).}
The best currently known (unconditional) bound is
N ( a ) = O ( ( log a ) ( log log log a ) ( log log a ) 3 ) , {\displaystyle N(a)=O\left({\frac {(\log a)(\log \log \log a)}{(\log \log a)^{3}}}\right),}
and is due to Kane (2007). Abbott, Erdős, and Hanson note that, conditional on Cramér's conjecture on gaps between consecutive primes,
N ( a ) = O ( ( log a ) 2 / 3 + ε ) {\displaystyle N(a)=O\left((\log a)^{2/3+\varepsilon }\right)}
holds for every ε > 0 {\displaystyle \varepsilon >0} . Singmaster (1975) showed that the Diophantine equation
( n + 1 k + 1 ) = ( n k + 2 ) {\displaystyle {n+1 \choose k+1}={n \choose k+2}}
has infinitely many solutions for the two variables n, k. It follows that there are infinitely many triangle entries of multiplicity at least 6: For any non-negative i, a number a with six appearances in Pascal's triangle is given by either of the above two expressions with
n = F 2 i + 2 F 2 i + 3 − 1 , {\displaystyle n=F_{2i+2}F_{2i+3}-1,}
k = F 2 i F 2 i + 3 − 1 , {\displaystyle k=F_{2i}F_{2i+3}-1,}
where Fj is the jth Fibonacci number (indexed according to the convention that F0 = 0 and F1 = 1). The above two expressions locate two of the appearances; two others appear symmetrically in the triangle with respect to those two; and the other two appearances are at ( a 1 ) {\displaystyle {a \choose 1}} and ( a a − 1 ) . {\displaystyle {a \choose a-1}.}
… excerpt ends here. Continue reading the full article.
