Erdős Problem #387
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (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.
The question in plain language
For integers \(n\) and \(k\) with \(1 \leq k < n\), consider the binomial coefficient
Problem 387 asks whether there is one absolute constant \(c>0\) that works for every such pair: must \(\binom{n}{k}\) always have a divisor \(d\) with \(cn<d\leq n\)? “Absolute” means that \(c\) cannot depend on \(n\) or \(k\). Since \(\binom{n}{k}=\binom{n}{n-k}\), it is equivalent to inspect \(1\leq k\leq n/2\), although the registered question uses \(k<n\).
The intuition is appealing. The numerator consists of \(k\) consecutive integers close to \(n\), so one might expect some uncancelled factor, or a product of factors, to remain close to \(n\). The difficulty is that division by \(k!\) can cancel precisely the factors that would have supplied a large divisor. The question is about the divisor structure of the resulting integer, not about the size of the binomial coefficient itself.
A small example
Take \(n=4\) and \(k=2\). Exact integer arithmetic gives
whose divisors at most \(n\) are \(1,2,3\). Thus \(2\) and \(3\) lie in \([n/k,n]=[2,4]\). This illustrates the elementary lower scale: a divisor somewhere near \(n/k\) is easy to obtain, but that is not a fixed positive fraction of \(n\) when \(k\) grows.
The historical example is more revealing. I evaluated math.comb(99215,15) exactly and checked all fifteen integers \(99215-i\) for \(0\leq i<15\). Every remainder of the binomial coefficient on division by \(99215-i\) was nonzero; the first three remainders were \(39686\), \(49607\), and \(66142\), and the last was \(33067\). Hence none of the numerator terms divides \(\binom{99215}{15}\). This verifies a finite fact, associated with Schinzel’s 1958 counterexample, but it does not by itself disprove the question for a fixed constant \(c\): a single coefficient could still have another divisor in \((cn,n]\).
What is known
The live Erdős Problems page records the original question and the historical references [ErGr76b, p. 351], [Er78g, p. 315], and [ErGr80, p. 74]. It also records Schinzel’s counterexample, the elementary interval \([n/k,n]\), and Faulkner’s result about a sufficiently large prime divisor, each of which concerns a related but different assertion.
The relevant primary modern source is H. M. Bui, S. Naprienko, K. Pratt, and A. Zaharescu, “Binomial coefficients with divisors avoiding an interval,” arXiv:2605.21221v3, revised 30 September 2026. Theorem 1.2 proves a positive result in the regime of large \(k\): for sufficiently small fixed \(\epsilon>0\), sufficiently large \(n\), and
there is a divisor in \(\left(n-n/(\log n)^{1/4},n\right]\). Theorem 1.4 gives infinitely many exceptions in a regime of small \(k\), and Corollary 1.7 states that for every fixed \(c>0\) some binomial coefficient has no divisor in \((cn,n]\). The paper describes a restricted covering argument, sieve estimates, and exponential-sum estimates; this article does not independently certify those proofs.
There is a version boundary worth preserving. The source packet and earlier arXiv wording were associated with a GRH-qualified negative answer, whereas the current v3 abstract and theorem text contain no GRH hypothesis. The audit therefore attributes the unconditional wording only to v3, not to an undated summary or to the catalogue alone.
GCL's current state
At the frozen catalogue revision teorth/erdosproblems@536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml has blob 4e60263a80af6207aca494d2e1388e44fa372889; entry 387 says informal status solved, formal status unformalized, and statement formalized yes. The live page was last edited 2 July 2026 and links to a formal statement. These are dated evidence records, not mathematical certification.
The pinned file google-deepmind/formal-conjectures@85f863718beeec7b58a3a1926ee92e3472bc2020, FormalConjectures/ErdosProblems/387.lean, blob 62649846a0215bd181729a120eb20f2c305de20a, formalizes the main shape with natural-number quantifiers, real \(c\), and divisibility by a natural \(d\). Its theorem erdos_387 has proof by sorry; it also contains a finite native_decide example, an open Schinzel variant, and an elementary lemma. The file’s category says research solved, but presence, category, and a sorry-bearing theorem do not prove semantic equivalence or certify the mathematics.
Accordingly, the status-neutral editorial description is: the cited external source reports a negative resolution, with a positive theorem for large \(k\); GCL has a statement-level formal interface but no certified proof supplied here. Accepted coverage remains whatever the V2 ledger decides.
What remains
A useful bounded successor task is a source-semantic cross-check, not a new proof campaign. Start from the exact v3 PDF and its introduction, Theorems 1.2 and 1.4, and Corollary 1.7. Normalize every quantifier, endpoint, logarithm, and “sufficiently large/small” dependence into a comparison table against erdos_387. In particular, check that the formal statement’s unrestricted condition \(1\leq k<n\), the paper’s symmetry reduction, and the divisor interval \((cn,n]\) agree. Separately mark the theorem-level negative answer, the positive subtheorem for large \(k\), and the finite examples.
Acceptance would require a line-by-line semantic report with exact source locations and no claim that sorry is proved. Falsification would be any missing hypothesis, endpoint reversal, or mismatch in the real coercions that changes the proposition. Stop after the comparison and one exact finite check; do not build all of Lean or attempt to reproduce the analytic proof. If the v3 wording and pinned formal statement cannot be reconciled, stop with a status conflict rather than silently editing the statement.
Sources and claim boundaries
Primary and historical sources used are Erdős and Graham (1976), Schinzel (1958), Erdős (1978/82), and Bui–Naprienko–Pratt–Zaharescu, arXiv:2605.21221v3. The original assignment is MATH-PROGRAMME issue #1657. The paper PDF retrieved for this audit has SHA-256 a7a8215a3fb0d2104b5fd61b5244f3a13ff48c8c960e42162cf2f15a164fd113; its arXiv source archive has SHA-256 feba9a2b742c252e59357545dcf36fa295b3b4fa3030d14ec2eb6859ead7ec74.
The catalogue and Lean hashes above pin the packet actually compared. The exact-arithmetic checks establish only the displayed finite facts. External proof claims are reported from the primary paper; formal status is reported from the pinned file; GCL mathematical certification, publication, and accepted coverage are not supplied. Original SOURCE RESULT/1 citation: authenticated original RESULT/1.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1657 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- 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.