Binomial coefficients with divisors avoiding an interval

Abstract

We solve a fifty-year-old conjecture of Erdős and Graham concerning whether the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ with $1\le k\le \frac{n}{2}$ must always have a divisor $\le n$ that is ``close'' to $n$: that is, bigger than a constant times $n$. We show this is the case when $k$ is sufficiently large as a function of $n$. However, we show it is possible to find binomial coefficients $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, where $k$ is small compared to $n$, such that $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ does not have divisors $\le n$ close to $n$. This latter, more substantial argument involves a restricted covering problem with residue classes, sieve methods, and various exponential sum estimates.

62 pages. Added a coauthor. The arguments in the paper are now unconditional, removing dependence on the Generalized Riemann Hypothesis