math.NT — Number Theory

Small witnesses for eventual Erdős--Straus binomial divisibility

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

Erdős and Straus asked whether, for each fixed $n\ge2$, every sufficiently large integer $m$ admits $1\le k\le m-n$ with $\binom{n+k}{n}\mid\binom{m+k}{k}$. We prove that it does; previously this was known only for a set of $m$ of density one. The witness can be taken with $k=O_{n,\varepsilon}(m^\varepsilon)$ for every $\varepsilon>0$: a factorial identity reduces the problem to finding a small value of a fixed polynomial coprime to $\binom mn$, which an elementary sieve provides. Conversely, the least witness is at least logarithmic in $m$ along an infinite sequence.