---

Statement

Problem 2 (printed p. 386). "What happens if we sift by other residue classes?" The paper then asks: let $p_1,\ldots,p_k\le x$ be primes with $\sum_i1/p_i\le K$, and attach to each $p_i$ a residue class $a_i\pmod{p_i}$. Is the number of natural numbers $n\le x$ with $n\not\equiv a_i\pmod{p_i}$ for all $i$ at least $cx$, with $c=c(K)>0$?

The case $a_i\equiv0$ for every $i$ is the sifting of Theorem 1, which answers it with $c(K)=e^{-e^{c'K}}$, where $c'$ is that theorem's absolute constant. The paper proves nothing for other residue classes.

Source. P. Erdős and I. Z. Ruzsa, On the small sieve. I. Sifting by primes, J. Number Theory 12 (1980), 385–394; Problem 2 on printed p. 386 (PDF p. 2). The edition is identified in the source digest.

Read depth. Claims checked: the question was read on the page image. A question has no proof to check.

Dependencies

None.

Bears on

• Problem 1200: that problem asserts a constant $C$ such that for all large $x$ some primes $p_i<x$ with $\sum1/p_i<C$ and classes $a_i\pmod{p_i}$ cover every integer $n<x$. A positive answer to Problem 2 would leave at least $c(C)x-1$ of the integers $n<x$ uncovered, a positive number for large $x$, so it would refute Problem 1200; a negative answer does not by itself give the covering. The paper records no result on either.
• Problem 688: by Mertens's theorem the primes in $(n^{\epsilon},n]$ have reciprocal sum $\log(1/\epsilon)+o(1)$ for fixed $\epsilon\in(0,1)$. A positive answer to Problem 2 would leave integers in $[1,n]$ uncovered by any choice of classes for those primes once $n$ is large, so $\epsilon_n\le\epsilon$ for large $n$ and every fixed $\epsilon$, that is $\epsilon_n=o(1)$. The paper does not mention this consequence.