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.**N. Alon and J. Spencer, The probabilistic method. Second edition. With an appendix on the life and work of Paul Erdos, Wiley-Interscience, 2000. MR**1885388 (2003f:60003)****2.**S. J. Benkoski and P. Erdos,*On weird and pseudoperfect numbers*, Math. Comp.**28**(1974), 617-623. MR**0347726 (50:228)****3.**P. Erdos,*A generalization of a theorem of Besicovitch*, J. London Math. Soc.**11**(1936), 92-98.**4.**P. Erdos,*On integers of the form and some related problems*, Summa Brasil. Math.**2**(1950), 113-123. MR**0044558 (13:437i)****5.**P. Erdos,*Problems and results in combinatorial number theory*, A survey of combinatorial theory, J. N. Srivastava, ed., North-Holland, Amsterdam, 1973, 117-138. MR**0360509 (50:12957)****6.**P. Erdos,*Some of my favourite problems in number theory, combinatorics, and geometry*, Combinatorics Week (Portuguese) (São Paulo, 1994), Resenhas**2**(1995), no. 2, 165-186. MR**1370501 (97e:11003)****7.**P. Erdos and R. L. Graham,*Old and new problems and results in combinatorial number theory*, Monographies de L'Enseignement Mathématique, No. 28, 1980. MR**0592420 (82j:10001)****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.**R. K. Guy,*Unsolved problems in number theory*, 3rd ed. Problem Books in Mathematics. Springer-Verlag, New York, 2004. MR**2076335 (2005h:11003)****11.**J. A. Haight,*Covering systems of congruences, a negative result*, Mathematika**26**(1979), 53-61.MR**0557126 (81e:10003)****12.**H. Halberstam and H.-E. Richert, Sieve methods, Academic Press, 1974.MR**0424730 (54:12689)****13.**H. Halberstam and K. Roth, Sequences. Vol. 1, Clarendon Press, 1966.MR**0210679 (35:1565)****14.**R. R. Hall and G. Tenenbaum, Divisors, Cambridge University Press, 1988.MR**0964687 (90a:11107)****15.**A. Hildebrand and G. Tenenbaum,*Integers without large prime factors*, J. de Théorie des Nombres de Bordeaux,**5**(1993), 411-484.MR**1265913 (95d:11116)****16.**S. Porubský and J. Schönheim,*Covering systems of Paul Erdos: Past, present and future*, in Paul Erdos and his mathematics, vol. I, János Bolyai Math. Soc., Budapest, 2002, pp. 581-627. MR**1954716 (2004d:11006)****17.**J. B. Rosser and L. Schoenfeld,*Approximate formulas for some functions of prime numbers*, Illinois J. Math.**6**(1962), 64-94.MR**0137689 (25:1139)****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.