Skip to content

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

\[ \max\left(\frac nk,k\right) \]

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\),

\[ \binom73=35=5\cdot7. \]

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.

Back to catalogue · Compendium introduction