On the first page of the article "When the sieve works", the authors present upper and lower bounds for $S(T,T+x;\mathcal{E})$; the number of integers in the interval $(T,T+x]$ that are coprime to all primes in $\mathcal{E}$. I quote:

By a simple inclusion-exclusion argument one expects that the number of such integers is about $$ x \prod_{p\in\mathcal{E}}\left(1-\frac{1}{p} \right). $$ This is provably always an upper bound, up to a constant: $$ S(T,T+x;\mathcal{E}) \ll x \prod_{p\in\mathcal{E}}\left(1-\frac{1}{p} \right), $$ and one gets the analogous lower bound $$ S(T,T+x;\mathcal{E}) \gg x \prod_{p\in\mathcal{E}}\left(1-\frac{1}{p} \right), $$ if $\mathcal{E}$ is a subset of the primes up to $x^{1/2-o(1)}$.

My question is simply:

QUESTION: Does anyone have references to proofs of the above bounds?

It seems these results are fairly standard knowledge, and the authors refer to the book "Opera de Cribro" by Friedlander and Iwaniec. However, they do not state any page numbers, so it is a bit hard to know exactly where to look. If the proofs are simple, perhaps someone would be able to jot them down here?

ADDED: While the provable lower bound is not as good as the provable upper bound, it seems reasonable they should be the same. This can be easily illustrated by plotting $$ \inf S(T,T+x, p_k\#) - x \cdot \prod_{p \in \mathcal P_k} \left( 1-\frac{1}{p} \right) \\ $$ and $$ \sup S(T,T+x, p_k\#) - x \cdot \prod_{p \in \mathcal P_k} \left( 1-\frac{1}{p} \right), $$ where $\mathcal P_k$ is the set of the $k$ first primes and $p_k\#=p_1 p_2 \dots p_k$ is the primorial. In the figure below, plots for both $k=4$ and $k=5$ are shown, and $x\in [0,p_k\#]$. Note that since $S(T+x, p_k\#)$ is periodic in $x$ with period $p_k\#$, we obtain the anti-symmetric property that $$ \inf S(T,T+x, p_k\#) - x \cdot \prod_{p \in \mathcal P_k} \left( 1-\frac{1}{p} \right)\\ = - \sup S(T, T+ p_k\#-x, p_k\#) + (p_k\#-x) \cdot \prod_{p \in \mathcal P_k} \left( 1-\frac{1}{p} \right), $$

This might be far fetched, but could this symmetric property be exploited in some way to better the lower bound?

Upper and lower bounds on the number of coprimes in an interval

Here is a different plot where $\mathcal{E}$ is the set of primes less or equal to $\sqrt{x}$, showing $$ \inf S(0,x,\mathcal{E}) - x \cdot \prod_{p \in \mathcal{E}} \left( 1-\frac{1}{p} \right) \\ $$ and $$ \sup S(0,x,\mathcal{E}) - x \cdot \prod_{p \in \mathcal{E}} \left( 1-\frac{1}{p} \right). $$

Upper and lower bounds on prime counting function


1 Answer 1


Note that in the quoted paper, $\mathcal{E}$ is a set of primes up to $x$. Let us be a little bit more restrictive, namely let $\mathcal{E}$ be a set of primes up to $z$, where $z\leq x$ is to be determined later. Without loss of generality, $z$ (hence also $x$) exceeds a large absolute constant.

We can apply Theorem 11.13 in Friedlander-Iwaniec: Opera de Cribro, with $D=z$ or $D=z^2$, $\kappa=1$, $\beta=2$ (cf. (11.55)). Noting that $|r_d|\leq 1$ in the present situation and $d$ is restricted to $d<D$ in the definition of $R^\pm(D,z)$ (cf. (5.29)), we get that $$ S(T,T+x;\mathcal{E}) \ll x \prod_{p\in\mathcal{E}}\left(1-\frac{1}{p} \right)+O(z)$$ $$ S(T,T+x;\mathcal{E}) \gg x \prod_{p\in\mathcal{E}}\left(1-\frac{1}{p} \right)+O(z^2)$$ The error terms here are negligible (smaller than half of the main term) if $z=x/\log^2 x$ for the upper bound and $z=\sqrt{x}/\log x$ for the lower bound.

In short, the quoted claim is justified by the quoted theorem when the largest prime in $\mathcal{E}$ is slightly more carefully bounded than just $x$ or $x^{1/2-o(1)}$.

  • $\begingroup$ Thanks for clarifying. I added a figure above giving a numerical example of the upper and lower bounds, which reveals some interesting (but obvious) symmetries. Do you have any idea whether this can be exploited to better the lower bound? $\endgroup$
    – user45947
    Nov 28, 2014 at 6:45
  • $\begingroup$ @user45947: I am no expert in these things. At any rate, the quoted paper is concerned with precisely what happens when primes well above $\sqrt{x}$ are allowed. In the introduction the authors describe certain sets of primes, for which the asymptotic formula fails heavily. Of course the set of the first few primes might have special features that general sets of primes don't have. $\endgroup$
    – GH from MO
    Nov 28, 2014 at 12:29
  • 1
    $\begingroup$ Answer accepted and greatly appreciated. It was more complicated than I had anticipated, also emphasized by the authors of Opera de Cribro in the remark after theorem 11.13. $\endgroup$
    – user45947
    Nov 28, 2014 at 13:07

Your Answer

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

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