Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 1095

claims/: The 1 claim page of Problem 1095, one per claimant's result; the problem's standing derives from them.

Statement. Let $g(k)>k+1$ be the smallest $n$ such that all prime factors of $\binom{n}{k}$ are $>k$ . Estimate $g(k)$ .

Status. Open on the site (OPEN; page last edited 21 June 2026). The site's remarks credit the bounds $k^{1+c}<g(k)\le\exp((1+o(1))k)$ to Ecklund, Erdős and Selfridge, and the lower-bound record $g(k)\gg\exp(c(\log k)^2)$ to Konyagin. Ecklund, Erdős and Selfridge write that $g(k)<L_k=\operatorname{lcm}(1,\ldots,k)$ "seems to hold for all $k$ " (their conjecture on p. 649); their own table gives $g(k)>L_k$ at $k=2$ , $3$ and $6$ , so the question is whether $g(k)<L_k$ for all large $k$ . The standing in the frontmatter derives from the claim pages: the only claim is the pending partial claim Yang's eventual lcm bound, a manuscript of September 2026 with a Lean development, produced with GPT-6 Astra and GPT-5.6 Sol, proving $g(k)<L_k$ for every sufficiently large $k$ ; it does not estimate $g(k)$ , no reviewer has accepted it, this corpus has not built its Lean, and the site's label is unchanged, so the problem stands open with a pending partial claim.

Source. erdosproblems.com/1095, accessed 2026-09-04 and 2026-10-06 (the problem page and its proof-claims tab: OPEN; Proof claims (1)). Cite as: T. F. Bloom, Erdős Problem #1095, https://www.erdosproblems.com/1095.

References.

[EES74] Ecklund, Jr., E. F. and Erdős, P. and Selfridge, J. L., A new function associated with the prime factors of $(\sp{n}\sb{k})$ . Math. Comp. (1974), 647-649.
[ELS93] Erdős, P. and Lacampagne, C. B. and Selfridge, J. L., [[../library/factorials_binomials/erdos_1993_estimates_least_prime_factor_binomial_coefficient/_index|Estimates of the least prime factor of a binomial coefficient]]. Math. Comp. (1993), 215-224.
[GrRa96] Granville, Andrew and Ramaré, Olivier, Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients. Mathematika (1996), 73-107.
[Ko99b] Konyagin, S. V., Estimates of the least prime factor of a binomial coefficient. Mathematika (1999), 41-55.
[SSW20] Sorenson, Brianna and Sorenson, Jonathan and Webster, Jonathan, An algorithm and estimates for the Erdős-Selfridge function. (2020), 371-385.

Formalization. Statement in formal-conjectures.

Current assessment

No result determines the order of growth of $g(k)$ : $\log g(k)$ is known only to lie between a constant multiple of $(\log k)^2$ and $(1+o(1))k$ . Ecklund, Erdős and Selfridge [EES74] prove $k^{1+c}<g(k)<\exp(k(1+o(1)))$ , the upper bound through their inequality (8), $g(k)<k^2L_kP_l$ for $k>k_0$ with $l=[6k/\log k]$ (the integer part) and $P_l$ the product of the primes up to $l$ , and Konyagin [Ko99b] proves the lower bound $g(k)\gg\exp(c(\log k)^2)$ ; the site's remarks credit both. These bounds narrow the estimate without settling any instance of it, so neither has a claim page. The Lean file Erdos1095b.lean in Boris Alexeev's lean-proofs collection declares itself a partial formalization of the result of Ecklund, Erdős and Selfridge, with Aristotle and Boris Alexeev as formal authors. It proves $g(k)\le((k+1)!)^3$ for every $k\ge2$ and states the consequence as $g(k)\le\exp(k^{1+o(1)})$ , a weaker form of the upper bound of [EES74]. This corpus has not built it, so it gives no formalized evidence.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (22)

Problem 384 problems/factorials_binomials/E1095/claims Factorials and Binomial Coefficients Factorials and Binomial Coefficients factorials_binomials/ecklund_1974_new_function_associated_prime_factors Conjecture (p. 649): g(k) < L_k, the lcm of 1, …, k Conjectures (1)–(5) (pp. 647–648): the irregularity and growth of g(k)Inequality (6) (p. 648): g(k) > k^{1+c} for an absolute constant c > 0 Inequality (7) (p. 648): g(k) < N(k,k), the product of p^{α_p+1} over primes p ≤ k Inequality (8) (p. 648): g(k) < k² L_k P_l with l = [6k/log k] for k > k_0, hence g(k) < exp(k(1+o(1)))Table 1 (p. 647): the values g(k) ≤ 2500000 for 2 ≤ k ≤ 100 factorials_binomials/erdos_1993_estimates_least_prime_factor_binomial_coefficient factorials_binomials/granville_1996_explicit_bounds_exponential_sums_scarcity_squarefree Theorem 8 (p. 5): if the least prime factor of C(n, k) exceeds k then n > exp(c (log^3 k/log log k)^{1/2})factorials_binomials/sorenson_2020_algorithm_estimates_erdos_selfridge_function Computation (pp. 371--372, 383--384): g(k) for every k <= 375, with g(375) = 12863999653788432184381680413559 Theorem 5.1 (p. 377): under the uniform distribution heuristic, ĝ(k)/k <= g(k) <= kĝ(k) with probability 1 - o(1)Theorem 5.2 (p. 378): the number of n <= x with every prime factor of C(n, k) above k is (x/ĝ(k))(1 + o(1))Theorem 6.1 (p. 379): 0.530684 + o(1) <= log ĝ(k)/(k/log k) <= 1 + o(1)Theorem 6.5 (p. 381): under the uniform distribution heuristic, with probability 1 - o(1), the algorithm runs in time at most g(k) exp[-ck log log k/(log k)^2 (1 + o(1))]number_theory/guy_1991_western_number_theory_problems Problem 91:03 (p. 9): a lower bound for g(k), the least n > k+1 with binom(n,k) coprime to k!

Graph