← All problems

Erdős Problem #685 — Prime divisors of binomial coefficients

Fix ϵ>0\epsilon>0, and let nn be a sufficiently large integer depending on ϵ\epsilon. For every integer kk with nϵ<k≤n1−ϵn^\epsilon<k\leq n^{1-\epsilon}, is it true, uniformly over these kk as n→∞n\to\infty with ϵ\epsilon fixed, that

ω ⁣((nk))=(1+o(1)) k∑p prime\k<p<n1p?\omega\!\left(\binom{n}{k}\right)=(1+o(1))\,k\sum_{\substack{p\text{ prime}\k<p<n}}\frac1p?

Here ω(m)\omega(m) denotes the number of distinct prime divisors of the positive integer mm. The question also asks: “Or perhaps even when k≥(log⁡n)ck \geq (\log n)^c?” Erdős Problem #685

Background

Erdős posed this question in connection with the prime divisors of binomial coefficients; the problem is cited to his 1979 paper, “Some unconventional problems in number theory.” The proposed main term focuses on primes strictly between kk and nn, rather than on the smaller primes that may also divide the coefficient. Erdős Problem #685 Erdős, Some unconventional problems in number theory (1979)

For a prime p>kp>k, the denominator k!k! contains no factor of pp, and the numerator of (nk)\binom{n}{k} is the product of the kk consecutive integers from n−k+1n-k+1 to nn. Since k<pk<p, this interval contains at most one multiple of pp. Thus divisibility by such a prime is tied to whether that short interval contains a multiple of pp; the factor k/pk/p in the proposed main term reflects the corresponding heuristic frequency. This explains the shape of the conjectured sum but does not establish its asymptotic for a fixed nn. Erdős Problem #685 Shorey and Tijdeman, Prime Factors of Arithmetic Progressions and Binomial Coefficients

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.