Erdős Problem 387

References:

• erdosproblems.com/387
• [ErGr76b] Erdős, P. and Graham, R. L., On the prime factors of ${n \choose k}$. Fibonacci Quart. (1976), 348-352.
• [Er78g] Erdős, Pál, On prime factors of binomial coefficients. II. Mat. Lapok (1978/82), 307-316.
• [ErGr80] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).
• [Sc58] Schinzel, A., Sur un problème de P. Erdős. Colloq. Math. (1958), 198-204.
• [Gu04] Guy, Richard K., Unsolved problems in number theory. (2004), xviii+437.
• [Fa66] Faulkner, M. "On a theorem of Sylvester and Schur." Journal of the London Mathematical Society 1.1 (1966): 107-110.
• [BNPZ26] Bui, H., Naprienko, S., Pratt, K., and Zaharescu, A. Binomial coefficients with divisors avoiding an interval. arXiv:2605.21221 (2026).

theorem Erdos387.erdos_387 : False ↔ ∃ (c : ℝ), 0 < c ∧ ∀ (n k : ℕ), 1 ≤ k → k < n → ∃ (d : ℕ), ↑d ∈ Set.Ioc (c * ↑n) ↑n ∧ d ∣ n.choose k

Is there an absolute constant $c > 0$ such that, for all $1 \leq k < n$, the binomial coefficient $\binom{n}{k}$ has a divisor in $(cn, n]$?

Bui, Naprienko, Pratt, and Zaharescu [BNPZ26] answered this negatively.

theorem Erdos387.erdos_387.variants.schinzel : sorry ↔ ∀ᶠ (k : ℕ) in Filter.atTop, ¬IsPrimePow k → ∃ (n : ℕ), ∀ i < k, ¬n - i ∣ n.choose k

The following is Schinzel's conjecture, which appears in [Gu04].

theorem Erdos387.erdos_387.variants.easy {n k : ℕ} (hn : 1 ≤ n) (hk : k ≤ n) : ∃ (d : ℕ), ↑d ∈ Set.Icc (↑n / ↑k) ↑n ∧ d ∣ n.choose k

It is easy to see that n.choose k has a divisor in [n / k, n].

theorem Erdos387.erdos_387.variants.guy : False ↔ ∀ c < 1, ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (k : ℕ), 1 ≤ k → k < n → ∃ (d : ℕ), ↑d ∈ Set.Ioc (c * ↑n) ↑n ∧ d ∣ n.choose k

Is it true for any $c < 1$ and all $n$ sufficiently large, for all $1 \leq k < n$, $\binom{n}{k}$ has a divisor in $(cn, n]$?

This variant appears in [Gu04]. Bui, Naprienko, Pratt, and Zaharescu [BNPZ26] answered it negatively.