Deficiency of binomial coefficients: infinitely many with deficiency 1, finitely many above? (Erdős #1093)
Statement
For $n\geq 2k$ define the deficiency of $\binom{n}{k}$ as follows. If $\binom{n}{k}$ is divisible by some prime $p\leq k$ then the deficiency is undefined. Otherwise, the deficiency is the number of indices $0\leq i<k$ such that $n-i$ is $k$-smooth, that is, divisible only by primes $\leq k$. Are there infinitely many binomial coefficients with deficiency $1$? Are there only finitely many with deficiency $>1$?
Acceptance. FULLY RESOLVES: proofs settling both questions — whether infinitely many binomial coefficients have deficiency $1$, and whether only finitely many have deficiency $>1$ (in the finite case ideally with a certified-complete list). Machine-checkable proofs (Lean/Coq) preferred; otherwise complete written proofs with all steps. Neither infinitude nor finiteness can be closed by a finite computation alone. ADVANCES: (a) an unconditional proof of either question by itself; (b) an extended exhaustive census: for all $k\leq K$ enumerate every defined-deficiency $\binom{n}{k}$ using an explicit, proved version of the $n\ll 2^k\sqrt{k}$ cutoff, with code and an exhaustiveness certificate, either exhibiting new deficiency-$\geq 2$ examples (machine-checkable witnesses) or certifying that the lists stated in the background are complete within the searched region, where the region strictly extends the $n\leq 10^5$ data stated in the background; (c) weakening the hypotheses of the known conditional resolution of the finiteness question; (d) a Lean formalisation of the [ELS93] bound. Deliver the proof file, or the enumeration code plus census tables and certificates.
Background
A problem of Erdős, Lacampagne, and Selfridge [ELS88, p.522], also posed at the 1986 West Coast Number Theory problem session; listed as open on erdosproblems.com/1093 (fetched 2026-07-13, status 'open', tagged 'number theory | binomial coefficients'). A key finiteness handle from [ELS93]: if the deficiency exists and is $\geq 1$ then $n\ll 2^k\sqrt{k}$, so for each fixed $k$ the candidate set is finite and exhaustively searchable. Known data (from [ELS88] and the WCNT problem sets): there are $58$ examples of deficiency $1$ with $n\leq 10^5$, including $\binom{7}{3},\binom{13}{4},\binom{14}{4},\binom{23}{5},\binom{62}{6},\binom{94}{10},\binom{95}{10}$. The only known examples with deficiency $>1$: deficiency $2$ — $\binom{44}{8},\binom{74}{10},\binom{174}{12},\binom{239}{14},\binom{5179}{27},\binom{8413}{28},\binom{8414}{28},\binom{96622}{42}$; deficiency $3$ — $\binom{46}{10},\binom{47}{10},\binom{241}{16},\binom{2105}{25},\binom{1119}{27},\binom{6459}{33}$; deficiency $4$ — $\binom{47}{11}$; deficiency $9$ — $\binom{284}{28}$. A commenter on the site (Barreto) has given a positive answer to the finiteness question conditional on two strong conjectures; the unconditional problem remains open. Related problems: Erdős #384 (erdosproblems.com/384) and the companion least-prime-factor conjecture Erdős #1094 (erdosproblems.com/1094), whose only possible counterexamples have deficiency $\geq 1$. The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. The attacker's tool: exhaustive enumeration — for each $k$, scan all $n$ up to the $\ll 2^k\sqrt{k}$ cutoff, testing $p\nmid\binom{n}{k}$ for all $p\leq k$ via Kummer carries and counting $k$-smooth values among $n-i$ — to extend the deficiency census far beyond $n\leq 10^5$ and hunt new high-deficiency examples.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1093 (T. F. Bloom) | website |
| REF-02 | West Coast Number Theory problem sets (1991 compilation) — deficiency examples | website |
| REF-03 | Formalised statement of Erdős #1093 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.