Erdős Problem #1095
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, binomial coefficients.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
How long must we search through binomial coefficients before finding one with no small prime divisors?
Erdős Problem #1095 defines \(g(k)\) as the least integer \(n>k+1\) such that every prime factor of \(\binom nk\) is larger than \(k\).
The question is how rapidly \(g(k)\) grows and whether its values fluctuate dramatically as \(k\) increases.
A small example
Exact integer enumeration gives the following initial values, testing every eligible smaller \(n\) against all primes \(p\le k\):
| \(k\) | \(g(k)\) |
|---|---|
| 2 | 6 |
| 3 | 7 |
| 4 | 7 |
| 5 | 23 |
| 6 | 62 |
| 7 | 143 |
| 8 | 44 |
| 9 | 159 |
The drop from \(g(7)=143\) to \(g(8)=44\) is real. This arithmetic function is not necessarily monotone, even at small inputs.
These values are exact finite calculations, not evidence for an unbounded limsup or a zero liminf of successive ratios.
What is known
Ecklund, Erdős and Selfridge introduced the problem in 1974. The maintained catalogue reports a current lower bound of the form
due to Konyagin, and an upper bound with exponential growth in \(k\).
The original conjectures include eventual comparison with the least common multiple \(L_k=\mathrm{lcm}(1,\ldots,k)\) and statements about extreme oscillation:
These are separate open questions. A later heuristic suggests that \(\log g(k)\) should have scale \(k/\log k\), but that is not an established asymptotic theorem.
GCL's current state
Authenticated source audit #2366 reproduces \(g(k)\) exactly for \(2\le k\le9\), respecting the strict condition \(n>k+1\).
The frozen formal-conjectures representation defines the same threshold through the least prime factor, but its conjectural theorem bodies contain placeholders and do not constitute certified proofs.
What remains
Read the 1974 original and the later Konyagin, Granville–Ramaré and Sorenson–Sorenson–Webster sources. Check every lower-bound dependency, distinguish proved estimates from heuristics, and independently replay prime valuations in finite cases.
Sources and claim boundaries
Erdős Problem #1095; Ecklund–Erdős–Selfridge (1974); Konyagin (1999); Sorenson–Sorenson–Webster (2020); authenticated source audit #2366. The finite values are reproducible; the general growth and oscillation conjectures remain open. This is an unaccepted draft.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2366 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.