Least prime factor of $\binom{n}{k}$: at most $\max(n/k,k)$ with finitely many exceptions? (Erdős #1094)
Statement
Is it true that for all $n\geq 2k$ the least prime factor of $\binom{n}{k}$ is $\leq\max(n/k,\,k)$, with only finitely many exceptions? Erdős, Lacampagne, and Selfridge conjectured that the complete list of exceptions is the following $14$ binomial coefficients: $$\binom{7}{3},\binom{13}{4},\binom{23}{5},\binom{14}{4},\binom{44}{8},\binom{46}{10},\binom{47}{10},$$ $$\binom{47}{11},\binom{62}{6},\binom{74}{10},\binom{94}{10},\binom{95}{10},\binom{241}{16},\binom{284}{28}.$$
Acceptance. FULLY RESOLVES: a proof that the least prime factor of $\binom{n}{k}$ ($n\geq 2k$) is $\leq\max(n/k,k)$ for all but finitely many pairs $(n,k)$ — ideally with a certified-complete exception list — OR a proof that there are infinitely many exceptions. Machine-checkable proof (Lean/Coq) preferred; otherwise a complete written proof with all steps. ADVANCES: (a) a new exception beyond the $14$ listed in the statement — a machine-checkable witness $(n,k)$ with a certificate that every prime $p\leq\max(n/k,k)$ does not divide $\binom{n}{k}$; (b) a reproducible exhaustive scan certifying there are no further exceptions for all $k\leq K$ (searching the full finite candidate region via an explicit, proved cutoff of the $n\ll 2^k\sqrt{k}$ type), with code and exhaustiveness certificate, for a region strictly beyond the computational evidence stated in the background; (c) a proof of Selfridge's threshold form (least prime factor $\leq n/k$ whenever $n\geq k^2-1$, or whenever $n>17.125k$), even restricted to an explicit range of $k$; (d) progress, with proof, on the stronger $\max(n/k,\sqrt{k})$ or $\max(n/k,O(\log k))$ variants. Deliver the proof file, the witness plus certificate, or the scan code plus certified tables.
Background
A conjecture of Erdős, Lacampagne, and Selfridge [ELS88], strengthening Erdős #384 (erdosproblems.com/384); listed as open on erdosproblems.com/1094 (fetched 2026-07-13, status 'open', tagged 'number theory | binomial coefficients'). Erdős observed that the least prime factor of $\binom{n}{k}$ is always $\leq n/k$ once $n$ is sufficiently large depending on $k$; Selfridge [Se77] conjectured this already holds whenever $n\geq k^2-1$, with the single exception $\binom{62}{6}$. ELS88 also proposed stronger variants: least prime factor $\leq\max(n/k,\sqrt{k})$ with finitely many exceptions, or perhaps even $\leq\max(n/k,O(\log k))$; in [ELS93] they add computational evidence and note it is consistent with their data that the bound $\leq\max(n/k,13)$ holds with only $12$ exceptions. Guy discusses the problem in B31 and B33 of [Gu04], crediting Selfridge with the conjecture that $n>17.125k$ forces a prime factor $\leq n/k$. Structural connection: any counterexample must have deficiency $\geq 1$ in the sense of the companion problem Erdős #1093 (erdosproblems.com/1093), and by [ELS93] such $(n,k)$ satisfy $n\ll 2^k\sqrt{k}$, making the exception hunt a per-$k$ finite search. There is an extended discussion on MathOverflow (question 368183). The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. The attacker's tool: a computational sweep testing, for candidate pairs $(n,k)$ in the finite deficiency region, whether every prime $p\leq\max(n/k,k)$ fails to divide $\binom{n}{k}$ (Kummer carry test per prime) — a new exception is a finite, machine-checkable discovery, and certified exception-free ranges sharpen the conjecture.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1094 (T. F. Bloom) | website |
| REF-02 | MathOverflow 368183 — Updates on a least prime factor conjecture by Erdős | website |
| REF-03 | Formalised statement of Erdős #1094 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.