Estimate $g(k)$: the least $n>k+1$ with all prime factors of $\binom{n}{k}$ exceeding $k$ (Erdős #1095)
Statement
For $k\geq 2$ let $g(k)>k+1$ be the smallest $n$ such that all prime factors of $\binom{n}{k}$ are $>k$. Estimate $g(k)$ — in particular, determine the order of growth of $\log g(k)$.
Acceptance. FULLY RESOLVES: a proof determining the order of growth of $\log g(k)$ — matching upper and lower bounds of the same order (e.g. establishing $\log g(k)\asymp k/\log k$), or a finer asymptotic formula. Machine-checkable proof (Lean/Coq) preferred; otherwise a complete written proof with all steps. ADVANCES: (a) a lower bound for $g(k)$ strictly better than the Konyagin bound $\exp(c(\log k)^2)$ stated in the background, with proof; (b) an upper bound strictly better than $\exp((1+o(1))k)$, or a proof of the EES74 conjecture $g(k)<\mathrm{lcm}(1,\ldots,k)$ for all large $k$; (c) a proof of either $\limsup g(k+1)/g(k)=\infty$ or $\liminf g(k+1)/g(k)=0$; (d) new certified values of $g(k)$ strictly extending the published terms of OEIS A003458 — with search code and, for each reported value, a minimality certificate (verification that every $k+1<n<g(k)$ has a prime factor $\leq k$ in $\binom{n}{k}$) — plus an updated empirical fit of $\log g(k)$ against $k/\log k$. Deliver the proof file, or the code plus the table of new certified values and the fit.
Background
A question of Ecklund, Erdős, and Selfridge [EES74]; listed as open on erdosproblems.com/1095 (fetched 2026-07-13, status 'open', tagged 'number theory | binomial coefficients'). EES74 proved $k^{1+c}<g(k)\leq\exp((1+o(1))k)$ for some constant $c>0$, conjectured $g(k)<L_k=\mathrm{lcm}(1,\ldots,k)$ for all large $k$, and further conjectured $\limsup g(k+1)/g(k)=\infty$ and $\liminf g(k+1)/g(k)=0$. The lower bound was improved by Erdős, Lacampagne, and Selfridge [ELS93] and by Granville and Ramaré [GrRa96]; the current record is $g(k)\gg\exp(c(\log k)^2)$ for some $c>0$, due to Konyagin [Ko99b]. ELS93 write that 'it is clear to every right-thinking person' that $g(k)\geq\exp(ck/\log k)$ for some $c>0$, and Sorenson, Sorenson, and Webster [SSW20] give heuristic evidence that $\log g(k)\asymp k/\log k$ — so the believed truth sits far above the proved $\exp(c(\log k)^2)$ and just below the proved $\exp((1+o(1))k)$. Computed values of $g(k)$ are OEIS A003458. Related problems: Erdős #451 (erdosproblems.com/451) and the companion least-prime-factor conjecture Erdős #1094 (erdosproblems.com/1094), for which $g(k)$ is exactly the threshold below which $\binom{n}{k}$ must have a prime factor $\leq k$. The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. The attacker's tool: sieved search computing $g(k)$ for new $k$ (test candidates $n$ by checking, via Kummer carries, whether any prime $p\leq k$ divides $\binom{n}{k}$), extending OEIS A003458 and the SSW20 computations to sharpen the empirical constant in $\log g(k)\asymp k/\log k$; on the proof side, attack the enormous gap between the quasipolynomial lower bound and the exponential upper bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1095 (T. F. Bloom) | website |
| REF-02 | OEIS A003458 — g(k): least n > k+1 such that all prime factors of C(n,k) exceed k | website |
| REF-03 | Formalised statement of Erdős #1095 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.