Problems / number-theory

number-theory / Number Theory, Erdős–Pomerance Functions

Improved Bounds for Distinct Multiples in Intervals

For the Erdős–Pomerance functions $F(n)$ and $h_{\mathbb{P}}(n)$ counting how many consecutive integers are needed to contain a distinct multiple of each integer, respectively prime, up to $n$, the paper proves $F(n) \ge h_{\mathbb{P}}(n) \ge n\exp\left(\left(\frac{\log 2}{2} - o(1)\right)\frac{\log n}{\log\log n}\right)$, disproving Kominers' conjecture that $F(n) \ll n\log n$. The paper also significantly improves known upper bounds (which were on the order of $n^{3/2}$) to $F(n) \le n^{4/3 + o(1)}$ and $h_{\mathbb{P}}(n) \le n^{4/3 - o(1)}$.