Erdős Problem #1094
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
What is the smallest prime dividing the binomial coefficient \(\binom nk\)? Erdős Problem #1094 conjectures that, whenever \(n\ge2k\), the smallest such prime is at most
apart from finitely many exceptional pairs \((n,k)\).
This is a two-variable finiteness assertion. It does not claim that the only exceptional pairs are the fourteen numerical examples listed in the original 1988 paper. It also does not follow automatically from a bound that holds for sufficiently large \(n\) for each fixed \(k\).
A small example
For \(n=7\) and \(k=3\),
The smallest prime divisor is \(5\), whereas \(\max(7/3,3)=3\). Thus \((7,3)\) is genuinely exceptional.
We independently checked the fourteen historical candidate exceptions listed by Erdős, Lacampagne and Selfridge:
| \(k\) | Exceptional \(n\) in the 1988 list |
|---|---|
| 3 | 7 |
| 4 | 13, 14 |
| 5 | 23 |
| 6 | 62 |
| 8 | 44 |
| 10 | 46, 47, 74, 94, 95 |
| 11 | 47 |
| 16 | 241 |
| 28 | 284 |
For each pair, exact integer binomial arithmetic confirms no prime less than or equal to the conjectured threshold divides the coefficient. The same program independently computes the related deficiency from #1093, including deficiency four at \((47,11)\) and nine at \((284,28)\).
A bounded sweep over \(2\le k\le10\) and \(2k\le n\le200\) found eleven exceptional pairs, all among the historical fourteen. This is not a proof that no further exceptions exist.
What is known
The maintained catalogue attributes the conjecture to Erdős, Lacampagne and Selfridge (1988), with computational and analytic follow-up in 1993. It separately reports Selfridge's conjecture about the range \(n\ge k^2-1\), and possible stronger bounds involving \(\sqrt{k}\) or a constant such as \(13\) in place of \(k\).
Those are related but different assertions. The universal finite-exceptions conjecture remains open.
GCL's current state
Authenticated source audit #2365 reproduces all fourteen historical candidate examples using exact integer division and verifies their positive deficiency. The frozen formal-conjectures statement labels the conjecture open and has no completed proof.
#1094 is one of the twenty deterministic critical-review samples. Reproducing examples is not an independent review of the general argument. The original 1988 and 1993 papers have not yet been proof-audited page by page.
What remains
Check the original paper's exact exception list, every inequality endpoint, the quantifier over all pairs, and the literature since 1993. A separate implementation of binomial prime valuations should replay the finite data. Only after source adjudication and independent second-pass review can this critical sample be marked complete.
Sources and claim boundaries
- Erdős Problem #1094, maintained open status.
- P. Erdős, C. Lacampagne and J. Selfridge, Prime factors of binomial coefficients and related problems, Acta Arithmetica (1988), pp. 507–523.
- Same authors, Estimates of the least prime factor of a binomial coefficient, Mathematics of Computation (1993), pp. 215–224.
- Authenticated GCL source audit #2365.
All finite examples are independently checked, but the open theorem is not proved. This draft and its mandatory critical review remain unaccepted.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2365 — 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.