Erdős Problem 1200 asks whether there is a constant such that for every sufficiently large , residue classes , one for each selected prime , cover with . Question 2 in the joint paper asks whether every fixed budget leaves a uniformly positive proportion of survivors. An affirmative answer to that question would disprove the covering conjecture.
The argument below establishes a survivor theorem when there is a common shift on the larger selected primes. The arbitrary-residue conjecture remains open in the sources checked.
Sources
- Erdős’s 1980 survey, §6, equation (1″) gives the covering conjecture. Erdős–Ruzsa, On the small sieve. I. Sifting by primes, p. 386 states the positive-proportion question. Theorem 1 there supplies the survivor bound for zero residues used below.
- Hildebrand, Quantitative mean value theorems for nonnegative multiplicative functions II identifies the sharp asymptotic minimum for the zero-residue problem. Ben Green discusses the arbitrary-residue conjecture after Problem 46 in 100 Open Problems. The 2022 Oberwolfach report, open problem 12 also records it.
- The Erdős Problems wiki gives restrictions on the prime ranges of possible covers and an overlap obstruction. The working report treats zero residues and small examples. The common-shift theorem below allows the small classes to vary at primes up to a fixed power of the interval length.
- Granville–Shao, Bombieri–Vinogradov for multiplicative functions, and beyond the -barrier, Theorem 1.6, supplies distribution in reduced residue classes after removing exceptional primitive characters. Iwaniec, Rosser's sieve, Theorem 1, supplies the lower bound with sieve parameter greater than 2.
Common shift on the larger primes
Theorem. Fix and . Let be any set of primes up to with and choose a residue for each. If there is an integer with such that for every above , then at least integers of avoid all the classes for sufficiently large .
The lower-prime classes can vary independently, including at primes comparable to . The choice of shift can vary with .
Counting integers with excluded prime factors
Let be completely multiplicative with , and suppose that . Put , and , where is Dirichlet convolution. Thus is the indicator of squarefree integers supported on the primes excluded by . For ,
Indeed, the first bound is an Euler product. Since is supported on squarefree integers, . The terms can be counted trivially. From one gets . Partial summation gives
We also need a mean square over small primitive characters. For every fixed , uniformly as with ,
The star indicates primitive characters. Write on , with and , where . For each nonprincipal primitive character of conductor , the sum against is bounded by by completing periods in the inner sum over . There are characters to consider. For ,
Here the cofactor in a tail term is at most . In the product of two tail terms write , where brackets denote the least common multiple. The support condition for implies , and all the inner cutoffs satisfy . To bound the last double sum, group by , giving the bound . The multiplicative large sieve applied to now proves (2).
Distribution over the sieve moduli
Let be a set of primes with and let contain the squarefree products of primes of , including 1. We have . Fix , and choose . In addition to the hypotheses above on , assume it is supported on -smooth integers and for all up to . Then
Apply Granville–Shao, Theorem 1.6, with . Its class includes 1-bounded completely multiplicative functions. The theorem gives a set of primitive characters and an error summed over each dyadic range of after these characters are subtracted. Enlarge the set to include the principal primitive character if needed. We bound the total contribution of the remaining exceptional characters, including the characters they induce, on .
A character of conductor can contribute only when , so . Its total possible weight is at most . Thus all exceptional characters with contribute , even with the trivial bound on each character sum, using .
For the smaller conductors, let be primitive modulo , and let be the character modulo induced from . For squarefree divisible by , complete multiplicativity gives
Summing the absolute values with weight and then over the exceptional characters with , the total is at most
Indeed, with fixed and coprime, write and sum . If , the trivial bound for each of the character sums contributes , using . For , apply Cauchy–Schwarz to the inner sum in (4). The sum of squares of the weights is at most , since there are at most characters modulo . Equation (2) with bounds the other factor by , uniformly in . Summation using completes the estimate of (4).
It follows that the residue counts in (3) can be replaced, with total error , by . To replace this principal term by , write where contains the primes up to . Dropping the coprimality condition at changes the unnormalized count by at most , and the corresponding change in is bounded by the same expression. Their total weighted cost is
For , since for , Möbius inversion gives . By (1), each term differs from by . Here . The sum over of is bounded by the Euler product . This gives (3).
Applying the lower sieve
Choose the longer of the portions and of . On it let . The numbers form an interval of at least integers, with . After translation and possibly reflection the zero classes are those primes with . Put the rest in , so all primes of are at most , and their forbidden residues modulo are nonzero.
Choose with , then choose as in (3). Define to be the indicator that is -smooth and divisible by none of the selected zero-class primes. The reciprocal cost of excluding the zero-class primes and all the primes in is by Mertens' theorem. Theorem 1 of Erdős–Ruzsa gives . Equation (1) gives
For use , and otherwise use (1). Fix with and set . To apply (3) to the interval , first apply it at . If , apply it also at , since , and for up to . For smaller , the total error at that endpoint for the indicated moduli is bounded by from the interval count without the weight .
For each , the simultaneous forbidden conditions for the primes dividing specify one reduced residue class modulo , by the Chinese remainder theorem. The weight of this class in has the form , where the sum of for is by (3). Apply the dimension-one lower sieve with density on , cutoff , and level . Its dimension bound follows from Mertens' product over all primes. The lower sieve function is positive at the fixed parameter , and . Hence the number of survivors with is .
Consequence for deviations from a common shift
Fix as in the theorem. In any bounded-cost full cover, every integer with must have
for large . Delete the indicated classes, apply the theorem, and use that the deleted classes cover at most times their reciprocal sum plus points. In particular, the common-shift theorem also allows independent deviations for all primes above , for sufficiently small fixed depending on , by Mertens' theorem. The proof uses a single shift to make the larger forbidden conditions multiplicative. Independently chosen classes in the middle range lack this feature.