Largest prime factor of binomial(n,k): is $P(\binom{n}{k})\ge\min(n-k+1,\,k^{1+c})$ for some $c>0$? (Erdős #683)
Statement
Let $P(m)$ denote the largest prime divisor of $m$. Is it true that for every $1\leq k\leq n$ the largest prime divisor of the binomial coefficient $\binom{n}{k}$ satisfies $$P\left(\binom{n}{k}\right)\geq \min(n-k+1,\; k^{1+c})$$ for some absolute constant $c>0$? (The $n-k+1$ term accounts for $k$ close to $n$, where $\binom{n}{k}=\binom{n}{n-k}$ is a product of few factors; the substance of the conjecture is that for $k\leq n/2$ the largest prime factor exceeds $k^{1+c}$, a power-improvement over the classical bound $P(\binom{n}{k})>k$.)
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable Lean/Coq preferred, else a full written proof with all steps) that some absolute constant $c>0$ makes $P(\binom{n}{k})\geq\min(n-k+1,k^{1+c})$ hold for all $1\leq k\leq n$ — or a proof that for every $c>0$ the inequality fails infinitely often. No finite computation alone can close the problem (it is classified OPEN on the source site). ADVANCES: a proven lower bound on $P(\binom{n}{k})$ for $k\leq n/2$ strictly stronger than the best bound stated in the background (Erdős's $\gg k\log k$), with full proof; a proof of the conjecture in a restricted range of $k$ (e.g. $k\geq n^{\delta}$); or a reproducible exhaustive computation that, for a stated fixed $c$ (e.g. $c=1$, i.e. $P<k^2$), enumerates ALL exceptional pairs $(n,k)$ with $k\le n/2$ up to a new bound $N$, with code, an exhaustiveness argument, and the certified exception list. Deliver the proof file, or the search code plus the attained bound and exception certificates.
Background
Posed by Erdős [Er76d] and again in [Er79d]; listed as open on erdosproblems.com/683 (fetched 2026-07-13, status 'open', tagged 'number theory | primes | binomial coefficients'), where it is classified as not resolvable by any finite computation. The known frontier: the Sylvester–Schur theorem (see Erdős's elementary proof [Er34]) gives $P(\binom{n}{k})>k$ whenever $k\leq n/2$, and Erdős [Er55d] improved this to $P(\binom{n}{k})\gg k\log k$ for $k\leq n/2$ — still far from any fixed power $k^{1+c}$. Erdős [Er79d] wrote that it 'seems certain' the inequality holds for every $c>0$ with only finitely many exceptions (the number of exceptions depending on $c$), and standard prime-gap heuristics suggest the truth is much stronger: $P(\binom{n}{k})>e^{c\sqrt{k}}$ for $k\leq n/2$. Bloom notes the problem is essentially equivalent to Erdős #961 (erdosproblems.com/961). A formalized Lean statement exists in Google DeepMind's formal-conjectures repository. Related OEIS sequences: A006530 (greatest prime factor of $n$), A074399 (largest prime divisor of $n(n+1)$), A121359 (greatest prime factor of the tetrahedral numbers $\binom{n+2}{3}$). The attacker's tools: large-scale enumeration of $P(\binom{n}{k})$ via Kummer's theorem (a prime $p$ divides $\binom{n}{k}$ iff adding $k$ and $n-k$ in base $p$ carries), mapping empirical exceptional pairs for fixed $c$; a full proof would need genuine prime-distribution input, and partial results are candidates for Lean formalization.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #683 (T. F. Bloom) | website |
| REF-02 | Formalized statement of Erdős #683 (Lean, formal-conjectures) | website |
| REF-03 | OEIS A006530 — Gpf(n): greatest prime dividing n | website |
| REF-04 | OEIS A074399 — largest prime divisor of n(n+1) | website |
| REF-05 | OEIS A121359 — greatest prime factor of the pyramidal number A000292(n) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.