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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.