Bound $f(n)$, the least $k$ whose $k$-smooth part of $\binom{n}{k}$ exceeds $n^2$ (Erdős #684)
Statement
For $0\leq k\leq n$ write $$\binom{n}{k} = uv$$ where the only primes dividing $u$ lie in $[2,k]$ and the only primes dividing $v$ lie in $(k,n]$ (so $u$ is the $k$-smooth part of $\binom{n}{k}$). Let $f(n)$ be the smallest $k$ such that $u>n^2$. Give bounds for $f(n)$: how fast does $f(n)$ grow?
Acceptance. FULLY RESOLVES: a proof (machine-checkable Lean/Coq preferred, else a full written proof) determining the worst-case order of growth of $f(n)$ — matching upper and lower bounds up to a constant factor valid for ALL large $n$ (e.g. establishing $f(n)\asymp(\log n)^2$, or pinning the maximal order somewhere between the super-logarithmic lower bound and the $(\log n)^2$ upper bound). Note the typical/density-one order is already known ($\approx 4.73\log n$, Li) and $\lim_n f(n)/\log n$ is already known not to exist (Bae), so full resolution now means settling the extremal order. Conditional results (RH etc.) must be clearly flagged and do not fully resolve. ADVANCES: an unconditional upper bound strictly stronger than the best stated in the background ($f(n)\ll(\log n)^2$), with proof; a quantitative worst-case lower bound improving on Bae's $\limsup_n f(n)/\log n=\infty$ (e.g. $f(n)\geq(\log n)^{1+\delta}$ infinitely often for some $\delta>0$), or any nontrivial lower bound valid for ALL large $n$, with proof; a sharpening of Li's density-one result (its error term, or its extension to other thresholds), with proof; or a reproducible computation extending OEIS A392019 substantially beyond its current range, with code, a correctness argument for the smooth-part computation, and the resulting empirical growth analysis tested against Li's $(4.73\ldots)\log n$ normal order. Deliver the proof file, or the code plus computed table and analysis.
Background
Posed by Erdős [Er79d]; listed as open on erdosproblems.com/684 (fetched 2026-07-13, status 'open', tagged 'number theory | primes | binomial coefficients'; page last edited 2026-04-01). A classical theorem of Mahler — writing $(n+1)\cdots(n+k)=ab$ with $a$ having only prime factors $\leq l$ and $b$ only prime factors $>l$, one has $a<n^{1+\epsilon}$ for all sufficiently large $n$ (depending on $\epsilon,k,l$) — implies $f(n)\to\infty$, but it is ineffective and yields no growth rate. The frontier has moved fast recently: Quanyu Tang and ChatGPT proved $f(n)\leq n^{30/43+o(1)}$ unconditionally (their note shows the same method gives $f(n)\leq n^{2/3+o(1)}$ under the Riemann Hypothesis or the Density Hypothesis); subsequently an internal OpenAI model [APSSV26] gave an elementary argument showing $f(n)\ll(\log n)^2$, and constructed arbitrarily large $n$ with $f(n)\geq(1/2-o(1))\log n$. A heuristic of Sothanaphan and ChatGPT in the site comments had suggested $f(n)\sim 2\log n$ for most $n$. Two 2026 preprints (postdating the page's last edit) then sharpened both sides: Bae proved $\limsup_n f(n)/\log n=\infty$, so $f(n)$ exceeds any fixed multiple of $\log n$ infinitely often (refuting the once-expected $f(n)\ll\log n$); and Li proved a density-one normal-order theorem — for almost all $n$, $f(n)=(4.7305\ldots+o(1))\log n$ (more generally $f_c(n)=(c/(1-\gamma)+o(1))\log n$ for the analogous threshold $u>n^c$, with Gaussian fluctuations) — a constant that supersedes the $2\log n$ heuristic. So the typical (density-one) size of $f(n)$ is now pinned and $\lim_n f(n)/\log n$ is known not to exist; what remains open is the worst-case order of growth: the gap between the super-logarithmic lower bound (infinitely often) and the $(\log n)^2$ upper bound. Bloom also raises the variant $f(n,k)$: the least threshold $t$ such that the part of $\binom{n}{k}$ built from primes $\leq t$ exceeds $n^2$. OEIS A392019 tabulates $f(n)$. The attacker's tools: compute $f(n)$ at scale via Kummer/Legendre (the exponent of $p$ in $\binom{n}{k}$ is the number of carries when adding $k$ and $n-k$ in base $p$), extend A392019, test the $2\log n$ heuristic empirically, and attack the $\log n$ vs $(\log n)^2$ gap by sharpening the elementary argument.
References
Investigations · 0
No published investigations yet. This problem is unclaimed territory.