Is the number of distinct prime divisors of $\binom{n}{k}$ asymptotic to $k\sum_{k<p<n}1/p$? (Erdős #685)
Statement
Let $\epsilon>0$ and let $n$ be large depending on $\epsilon$. Is it true that for all $n^\epsilon<k\leq n^{1-\epsilon}$ the number of distinct prime divisors of $\binom{n}{k}$ is $$(1+o(1))\,k\sum_{k<p<n}\frac{1}{p},$$ where the sum ranges over primes $p$? Or perhaps this even holds in the much wider range $k\geq(\log n)^c$ for some constant $c$?
Acceptance. FULLY RESOLVES: a proof (machine-checkable Lean/Coq preferred, else a full written proof with all steps) that for every fixed $\epsilon>0$ the asymptotic $\omega(\binom{n}{k})=(1+o(1))k\sum_{k<p<n}1/p$ holds uniformly for $n^\epsilon<k\leq n^{1-\epsilon}$ as $n\to\infty$ — or a proof that it fails somewhere in that range (a disproof must exhibit the failing regime with proof, not just numerics, since the statement is asymptotic). Settling the stronger range $k\geq(\log n)^c$ in either direction, with proof, also fully resolves the second question. ADVANCES: a proven asymptotic in any sub-range (e.g. $k=n^{\theta}$ for fixed $\theta\in(0,1)$, or $k$ of a special shape); nontrivial proven upper or lower bounds on $\omega(\binom{n}{k})$ strictly improving the trivial $\log\binom{n}{k}/\log n$ bound stated in the background within the conjecture's range; or a reproducible large-scale computation (code + carry-counting correctness argument) mapping $\omega(\binom{n}{k})$ against the conjectured main term over a stated grid of $(n,k)$ with $n$ reaching well beyond $10^7$, quantifying the empirical error term. Deliver the proof file, or the code plus data tables and error-term analysis.
Background
Posed by Erdős [Er79d]; listed as open on erdosproblems.com/685 (fetched 2026-07-13, status 'open', tagged 'number theory | primes | binomial coefficients'), classified as not resolvable by a finite computation. The conjectured main term is the natural heuristic count: by Kummer's theorem a prime $p$ divides $\binom{n}{k}$ exactly when adding $k$ and $n-k$ in base $p$ produces a carry, and for a prime $p\in(k,n]$ this happens with 'probability' roughly $k/p$, so summing over $p$ gives $k\sum_{k<p<n}1/p$ (primes $p\leq k$ contribute negligibly many to the count in this range). The only bound recorded on the site is trivial: the number of distinct prime factors exceeds $\log\binom{n}{k}/\log n$, with asymptotic equality when $k>n^{1-o(1)}$ — which is why the conjecture is posed for $k\leq n^{1-\epsilon}$. No partial results toward the conjectured asymptotic are recorded. This sits in the same circle as Erdős #683 and #684 on the anatomy of prime factors of binomial coefficients. The attacker's tools: $\omega(\binom{n}{k})$ is computable at scale WITHOUT factorization (test each prime $p<n$ for a base-$p$ carry), so large numerical experiments can chart the ratio to the conjectured main term and its error term across the $(n,k)$ plane; a proof would likely need sieve/prime-distribution methods to control the carry events on average.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #685 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #684 (companion problem on smooth parts of binomial coefficients) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.