Sieving by large integers and covering systems of congruences

Authors:
Michael Filaseta, Kevin Ford, Sergei Konyagin, Carl Pomerance and Gang Yu

Journal:
J. Amer. Math. Soc. **20** (2007), 495-517

MSC (2000):
Primary 11B25, 11A07, 11N35

DOI:
https://doi.org/10.1090/S0894-0347-06-00549-2

Published electronically:
September 19, 2006

MathSciNet review:
2276778

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: An old question of Erdos asks if there exists, for each number , a finite set of integers greater than and residue classes for whose union is . We prove that if is bounded for such a covering of the integers, then the least member of is also bounded, thus confirming a conjecture of Erdos and Selfridge. We also prove a conjecture of Erdos and Graham, that, for each fixed number , the complement in of any union of residue classes , for distinct , has density at least for sufficiently large. Here is a positive number depending only on . Either of these new results implies another conjecture of Erdos and Graham, that if is a finite set of moduli greater than , with a choice for residue classes for which covers , then the largest member of cannot be . We further obtain stronger forms of these results and establish other information, including an improvement of a related theorem of Haight.

**1.**Noga Alon and Joel H. Spencer,*The probabilistic method*, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience [John Wiley & Sons], New York, 2000. With an appendix on the life and work of Paul Erdős. MR**1885388****2.**S. J. Benkoski and P. Erdős,*On weird and pseudoperfect numbers*, Math. Comp.**28**(1974), 617–623. MR**0347726**, https://doi.org/10.1090/S0025-5718-1974-0347726-9**3.**P. Erdos,*A generalization of a theorem of Besicovitch*, J. London Math. Soc.**11**(1936), 92-98.**4.**P. Erdös,*On integers of the form 2^{𝑘}+𝑝 and some related problems*, Summa Brasil. Math.**2**(1950), 113–123. MR**0044558****5.**P. Erdős,*Problems and results on combinatorial number theory*, A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) North-Holland, Amsterdam, 1973, pp. 117–138. MR**0360509****6.**Paul Erdős,*Some of my favourite problems in number theory, combinatorics, and geometry*, Resenhas**2**(1995), no. 2, 165–186. Combinatorics Week (Portuguese) (São Paulo, 1994). MR**1370501****7.**P. Erdős and R. L. Graham,*Old and new problems and results in combinatorial number theory*, Monographies de L’Enseignement Mathématique [Monographs of L’Enseignement Mathématique], vol. 28, Université de Genève, L’Enseignement Mathématique, Geneva, 1980. MR**592420****8.**K. Ford,*The distribution of integers with a divisor in a given interval*, preprint.**9.**D. J. Gibson,*Covering systems*, Doctoral dissertation at U. Illinois at Urbana-Champaign, 2006.**10.**Richard K. Guy,*Unsolved problems in number theory*, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR**2076335****11.**J. A. Haight,*Covering systems of congruences, a negative result*, Mathematika**26**(1979), no. 1, 53–61. MR**557126**, https://doi.org/10.1112/S0025579300009608**12.**H. Halberstam and H.-E. Richert,*Sieve methods*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York, 1974. London Mathematical Society Monographs, No. 4. MR**0424730****13.**H. Halberstam and K. F. Roth,*Sequences. Vol. I*, Clarendon Press, Oxford, 1966. MR**0210679****14.**Richard R. Hall and Gérald Tenenbaum,*Divisors*, Cambridge Tracts in Mathematics, vol. 90, Cambridge University Press, Cambridge, 1988. MR**964687****15.**Adolf Hildebrand and Gérald Tenenbaum,*Integers without large prime factors*, J. Théor. Nombres Bordeaux**5**(1993), no. 2, 411–484. MR**1265913****16.**Š. Porubský and J. Schönheim,*Covering systems of Paul Erdős. Past, present and future*, Paul Erdős and his mathematics, I (Budapest, 1999) Bolyai Soc. Math. Stud., vol. 11, János Bolyai Math. Soc., Budapest, 2002, pp. 581–627. MR**1954716****17.**J. Barkley Rosser and Lowell Schoenfeld,*Approximate formulas for some functions of prime numbers*, Illinois J. Math.**6**(1962), 64–94. MR**0137689****18.**Z.-W. Sun,*Finite covers of groups by cosets or subgroups*, Internat. J. Math., to appear.

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (2000):
11B25,
11A07,
11N35

Retrieve articles in all journals with MSC (2000): 11B25, 11A07, 11N35

Additional Information

**Michael Filaseta**

Affiliation:
Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208

Email:
filaseta@math.sc.edu

**Kevin Ford**

Affiliation:
Department of Mathematics, University of Illinois, Urbana, Illinois 61801

Email:
ford@math.uiuc.edu

**Sergei Konyagin**

Affiliation:
Department of Mathematics, Moscow State University, Moscow 119992, Russia

Email:
konyagin@ok.ru

**Carl Pomerance**

Affiliation:
Department of Mathematics, Dartmouth College, Hanover, New Hamphshire 03755-3551

Email:
carl.pomerance@dartmouth.edu

**Gang Yu**

Affiliation:
Department of Mathematical Sciences, Kent State University, Kent, Ohio 44242

Email:
yu@math.kent.edu

DOI:
https://doi.org/10.1090/S0894-0347-06-00549-2

Keywords:
Covering system.

Received by editor(s):
May 25, 2005

Published electronically:
September 19, 2006

Additional Notes:
The first author was supported by NSF grant DMS-0207302 and NSA grant H98230-05-1-0038.

The second author was supported by NSF grant DMS-0301083.

Much of the research for this paper was accomplished while the third author was visiting the University of South Carolina, Columbia, in January 2004 (supported by NSF grant DMS-0200187) and the University of Illinois at Urbana-Champaign in February 2004 (supported by NSF grant DMS-0301083).

The fourth author was supported by NSF grant DMS-0401422.

The work of the last author was completed while he was at the University of South Carolina; he was supported in part by NSF grant DMS-0601033.

Article copyright:
© Copyright 2006
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.