I am in need of a (relatively) general sieve with two parameters $y, z$. I am quite sure that on the literature there must be some result of the kind that I have in mind, probably a corollary of the large sieve inequality and some estimates of average values of multiplicative function. However, I did not find it.

For each prime number $p$, let $\Omega_p \subsetneq \{0, 1, \ldots, p - 1\}$ be a set of residues modulo $p$. Denote by $\Omega$ the whole family of the $\Omega_p$'s. Suppose that $|\Omega_p| \leq c$ for all $p$, and that $$\sum_{p \leq x} |\Omega_p| \cdot \frac{\log p}{p} = k \log x + O(1),$$ for all $x > 1$, where $c, k > 0$ are given constants.

My question is: In which ranges (respect to $x$) should $y$ and $z$ be in order to having $$(1) \quad |\{n \leq x : (n \bmod p) \notin \Omega_p\;\forall p \in [y, z]\}| \ll_{\Omega} \frac{x}{(\log x)^k},$$ for all $x > 1$ ? If that inequality is not possible at all, you can replace the exponent $k$ by some $k + o(1)$, as $x \to +\infty$. Anyway, I would like at least $y > (\log x)^\delta$, for fixed $\delta > 0$.

Note that, by the large sieve inequality, (1) would follow from $$\sum_{n \leq z} f_{y,z}(n) \gg_{\Omega} (\log x)^k ,$$ where $f_{y,z}$ is the multiplicative function supported on the squarefree integers with prime divisors in $[y, z]$ and such that $$f_{y,z}(p) = \frac{|\Omega_p|}{p - |\Omega_p|} .$$

Thank you in advance for any idea/reference.

EDIT: In light of Jan-Christoph Schlage-Puchta answer I edited the question in order to relax the hypothesis.


Such a sieve could only exist under rather special conditions. The easiest case would be $\Omega_p=\{0\}$, $z=\sqrt{x}$. In this case the sifted set consists of all integers of the form $pn\leq x$, where $p>\sqrt{x}$ is prime and $n$ has only prime factors $< y$. If $y=x^{o(1)}$, then the number of such integers is $$ \sum_{n:P^+(n)<y} \pi(x/n)-\pi(\sqrt{x}) \sim \frac{x}{\log x}\int_1^\infty\frac{1}{t}\rho(\frac{\log t}{\log y})\;dt\sim \frac{Cx\log y}{\log x}, $$ where $\rho$ is Dickman's function. Hence a sieve which gives bounds of the quality you want could only apply to some $\Omega$ which covers significantly more integers then you would initially expect.

  • $\begingroup$ Good point, so I am asking too much. I slightly changed the question accordingly to your example. $\endgroup$ – user40023 Dec 17 '16 at 10:24
  • $\begingroup$ I edited again the question. As your example shown, I think that also some conditions on $z$ are necessary. Thanks. $\endgroup$ – user40023 Dec 17 '16 at 17:25

Your Answer

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