Is every multiplicity t realized by some repeated binomial coefficient? (Singmaster-type, Erdős #849)
Statement
Is it true that, for every integer $t\geq 1$, there is some integer $a$ such that the equation $$\binom{n}{k}=a,\qquad 1\leq k\leq n/2,$$ has exactly $t$ solutions $(n,k)$?
Acceptance. FULLY RESOLVES: a proof that for every $t\geq 1$ some integer $a$ has exactly $t$ solutions; OR a proof that some explicit $t$ is never attained — in particular, any proof of an absolute bound $B$ on the number of solutions (Singmaster's conjecture) fully resolves the question negatively, since $t=B+1$ is then unattained. Machine-checkable proof (Lean/Coq) preferred; otherwise a complete written proof with all steps. ADVANCES: (a) exhibit an integer $a$ whose equation has exactly $t$ solutions for some $t\geq 5$ — a machine-checkable witness: list the $t$ pairs $(n,k)$, verify each, and certify exhaustiveness by the finite $k=O(\log a)$ enumeration with code; (b) a reproducible exhaustive scan determining all $a\leq X$ of multiplicity $\geq 3$ (with code and an exhaustiveness certificate) for an explicit height $X$ strictly extending the published tables the submission documents (e.g. OEIS A003015 and the literature it cites); (c) a proof widening the MRSTT at-most-two-solutions range $k\geq\exp((\log n)^{2/3+\epsilon})$ stated in the background; (d) a Lean formalisation of a known partial result. Deliver the proof file, or the witness plus certification code, or the scan code plus tables.
Background
Erdős [Er96b] credits this question to himself and Gordon 'many years ago'; it is more commonly known in the form of Singmaster's conjecture, which asserts the number of solutions is bounded by an absolute constant. Listed as open on erdosproblems.com/849 (fetched 2026-07-13, status 'open', tagged 'number theory | binomial coefficients'). Known small multiplicities: $t=3$ is attained by $a=120$ ($120=\binom{120}{1}=\binom{16}{2}=\binom{10}{3}$) and $t=4$ by $a=3003$ ($3003=\binom{3003}{1}=\binom{78}{2}=\binom{15}{5}=\binom{14}{6}$); no example with $t\geq 5$ solutions is known. Both Erdős and Singmaster believed the answer to this question is no — that there is an absolute upper bound on the number of solutions, which would leave all sufficiently large $t$ unattained. The strongest structural result is due to Matomäki, Radziwiłł, Shao, Tao, and Teräväinen [MRSTT22]: for any $\epsilon>0$ and all sufficiently large $a$ (depending on $\epsilon$), there are at most two solutions in the range $k\geq\exp((\log n)^{2/3+\epsilon})$ — i.e. at most two solutions in the interior of Pascal's triangle. Occurrence counts of integers as binomial coefficients are OEIS A003016, and numbers occurring five or more times in Pascal's triangle (counting all entries, including the symmetric ones) are OEIS A003015. The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. Key computational lever: for any given $a$, its multiplicity is finitely computable — $\binom{2k}{k}\leq a$ forces $k=O(\log a)$, and for each $k$ the row index $n$ is found by binary search since $\binom{n}{k}$ is increasing in $n$. The attacker's tool: large-scale search for a fifth-multiplicity $a$ (equivalently, extending exhaustive multiplicity scans to new heights with certificates), plus the analytic route of widening the MRSTT interior range.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #849 (T. F. Bloom) | website |
| REF-02 | Matomäki–Radziwiłł–Shao–Tao–Teräväinen, Singmaster's conjecture in the interior of Pascal's triangle | arxiv |
| REF-03 | OEIS A003016 — number of occurrences of n as a binomial coefficient | website |
| REF-04 | OEIS A003015 — numbers that occur 5 or more times in Pascal's triangle | website |
| REF-05 | Formalised statement of Erdős #849 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.