Singmaster's conjecture on repeated binomial coefficients

Decide whether, for every t, some number appears as a binomial coefficient C(n,k) with k ≤ n/2 in exactly t ways.

shoal State the problem, from Erdős Problems 1577ce2 · 2周前历史

44 行 · 3.8 KB 原始文件永久链接历史

1	# Singmaster's conjecture on repeated binomial coefficients
2
3	How many times can the same number appear in Pascal's triangle? The number 3003 appears eight times, and no number is known to appear more often. Erdős and Gordon asked whether every multiplicity is possible; Singmaster conjectured, and Erdős believed, that the multiplicities are bounded.
4
5	## Problem
6
7	For an integer $a>1$ count the solutions of
8
9	$$
10	\binom{n}{k}=a,\qquad 1\le k\le n/2,
11	$$
12
13	so that each pair of symmetric entries of Pascal's triangle is counted once. Is it true that for every $t\ge1$ there is an integer $a$ with exactly $t$ solutions?
14
15	Known examples: $a=120=\binom{120}{1}=\binom{16}{2}=\binom{10}{3}$ has three solutions, and $a=3003=\binom{3003}{1}=\binom{78}{2}=\binom{15}{5}=\binom{14}{6}$ has four. No number with five or more solutions is known.
16
17	## Background
18
19	Erdős credited the question to himself and Basil Gordon "many years ago"; in the literature it is usually discussed as Singmaster's conjecture, after David Singmaster's 1971 note asking for an absolute bound on the number $N(a)$ of times $a>1$ occurs in Pascal's triangle (counting both $\binom{n}{k}$ and $\binom{n}{n-k}$). Both Erdős and Singmaster expected such a bound to exist, which would answer the question above negatively. Assuming Cramér's conjecture on gaps between primes, Abbott, Erdős and Hanson showed $N(a)=O((\log a)^{2/3+\varepsilon})$.
20
21	## What is known
22
23	- Upper bounds on $N(a)$. Singmaster (1971) proved $N(a)=O(\log a)$; Abbott, Erdős and Hanson (1974) improved this to $O(\log a/\log\log a)$; the best unconditional bound is $O\big((\log a)(\log\log\log a)/(\log\log a)^3\big)$ by Kane (2007).
24	- The interior of the triangle. Matomäki, Radziwiłł, Shao, Tao and Teräväinen (2022) proved that, for $a$ large in terms of $\varepsilon$, there are at most two solutions with $k\ge\exp((\log n)^{2/3+\varepsilon})$.
25	- Lower bounds. Singmaster (1975) found infinitely many numbers that occur at least six times in the full triangle, that is, with at least three solutions in the count above.
26
27	## What would count as progress
28
29	- A number with five solutions (a ninth or tenth appearance in the full triangle), found by search and checked by exact arithmetic.
30	- A proof that $N(a)$ is bounded, or any improvement of Kane's bound.
31	- Extending the interior result of Matomäki et al. to smaller $k$.
32	- A formal proof against the Lean statement in [formal-conjectures](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/849.lean).
33
34	## References
35
36	1. D. Singmaster, How often does an integer occur as a binomial coefficient?, Amer. Math. Monthly 78 (1971), 385–386. [doi:10.1080/00029890.1971.11992769](https://doi.org/10.1080/00029890.1971.11992769)
37	2. H. L. Abbott, P. Erdős and D. Hanson, On the number of times an integer occurs as a binomial coefficient, Amer. Math. Monthly 81 (1974), 256–261. [doi:10.1080/00029890.1974.11993542](https://doi.org/10.1080/00029890.1974.11993542)
38	3. D. M. Kane, Improved bounds on the number of ways of expressing $t$ as a binomial coefficient, Integers 7 (2007), A53. [author's copy](https://cseweb.ucsd.edu/~dakane/combinations2.pdf)
39	4. K. Matomäki, M. Radziwiłł, X. Shao, T. Tao and J. Teräväinen, Singmaster's conjecture in the interior of Pascal's triangle, Q. J. Math. 73 (2022), 1137–1177. [doi:10.1093/qmath/haac006](https://doi.org/10.1093/qmath/haac006)
40	5. D. Singmaster, Repeated binomial coefficients and Fibonacci numbers, Fibonacci Quart. 13 (1975), 295–298. [doi:10.1080/00150517.1975.12430610](https://doi.org/10.1080/00150517.1975.12430610)
41
42	## Source
43
44	Imported from [Erdős Problems 849](https://www.erdosproblems.com/849), curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.