Suppose that $p_1,...,p_k$ are distinct prime numbers.

Let $f(n,l)$ be equal to the number of elements from set $\{n+1,n+2,...,n+l\}$ that are divisible by some $p_1,...,p_k$. Is it true that $$\sup_{n,m,l \in \mathbb{N}} |f(n,l)-f(m,l)| = O(k).$$


No. There are various results which give counterexamples.

For example, Rankin's construction of large prime gaps boils down to the fact that if $p_1, \ldots, p_k$ denote all prime numbers below $x$, then there exists some $n$ with $f\left(n, \frac{x\log x\log\log\log x}{(\log\log x)^2}\right)=0$.

If $n=x, \ell=x^2-x$, then $f(n, \ell)=\pi(x^2)+\mathcal{O}(x)\sim\frac{x^2}{2\log x}$, but the average taken over all $n$ is $\ell \prod_{p\leq x}\left(1-\frac{1}{p}\right)\sim \frac{e^{-\gamma}x^2}{\log x}$.

  • $\begingroup$ Thanks for your answer. What do you think about the correct order? Is it $O(k^2 \log k)$? $\endgroup$ – Martin Hicks Jun 12 at 19:35
  • $\begingroup$ A bound involving $k^2$ might be achievable, but I don't think anybody has done it yet. For the upper bound Selberg's sieve might suffice. The lower bound is probably more difficult. A good starting point might be Iwaniec's work on Jacobsthal function. $\endgroup$ – Jan-Christoph Schlage-Puchta Jun 13 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.