Let $X$ be large, and let $\mathcal{P} \subset \{1, \dots, X\}$ be a set of primes. What is a good upper bound for $$ \sum_{\substack{1 \leq n \leq X,\\ p \nmid n \text{ for all }p \in \mathcal{P}}} 1. $$ From standard arguments in sieve theory (Brun's sieve, I think) one obtains that the sum in question is $$ \ll X \prod_{p \in \mathcal{P}} \left(1 - \frac{1}{p} \right). $$ However, if $\mathcal{P}$ is close to maximal (close to containing all primes in the range $\{1, \dots, X\}$), then this estimate seems to be far from being optimal. For example, when $\mathcal{P}$ contains all the primes in this range, then the sum equals 1, since not other number in $\{1, \dots, X\}$ is coprime to all primes in this range, while the upper bound above is around $X/\log X$.

That was a trivial example of course, but what happens when $\mathcal{P}$ contains "most" primes in the given range? Assume, for example, that $\mathcal{P}$ is so large that $\sum_{p \in \mathcal{P}} p^{-1} \geq (1-\varepsilon) \log \log X$, for fixed $\varepsilon$. Then what is a good upper bound for the sum above? (As noted, here $\varepsilon$ is fixed and "small", and $X \to \infty$.)

  • 1
    $\begingroup$ Disclaimer : I know nothing about sieve theory and the following proposition may be utterly stupid, but as a former expected-to-become physicist, I would try to investigate an upper bound of the form $X/(\log^{1-\delta}X.X^{\delta} )$ with $ \delta\sim\pi_{\mathcal{P}}(x)/\pi(x) $ where $ \pi_{\mathcal{P}}(x) $ is the number of elements of $ \mathcal{P} $ . $\endgroup$ Feb 12, 2018 at 22:22

1 Answer 1


This question is addressed by Granville, Koukoulopoulos, and Matomaki (paper in Duke) and its sequel by Matomaki and Shao. These results show that for the sieve bound is of the right size, then ${\mathcal P}$ should omit a good number of large primes. In other words the situation where one does much better than the sieve bound is when all the large primes are in ${\mathcal P}$ -- think of the situation of smooth numbers. Conditions like $\sum_{p\in {\mathcal P}} 1/p \ge (1-\epsilon)\log \log X$ are too coarse in this problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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