Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



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
Published electronically: September 19, 2006
MathSciNet review: 2276778
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An old question of Erdos asks if there exists, for each number $ N$, a finite set $ S$ of integers greater than $ N$ and residue classes $ r(n)~({\rm mod}~n)$ for $ n\in S$ whose union is $ \mathbb{Z}$. We prove that if $ \sum_{n\in S}1/n$ is bounded for such a covering of the integers, then the least member of $ S$ 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 $ K>1$, the complement in $ \mathbb{Z}$ of any union of residue classes $ r(n)~({\rm mod}~n)$, for distinct $ n\in(N,KN]$, has density at least $ d_K$ for $ N$ sufficiently large. Here $ d_K$ is a positive number depending only on $ K$. Either of these new results implies another conjecture of Erdos and Graham, that if $ S$ is a finite set of moduli greater than $ N$, with a choice for residue classes $ r(n)~({\rm mod}~n)$ for $ n\in S$ which covers $ \mathbb{Z}$, then the largest member of $ S$ cannot be $ O(N)$. We further obtain stronger forms of these results and establish other information, including an improvement of a related theorem of Haight.

References [Enhancements On Off] (What's this?)

  • 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,
  • 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. 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. 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), 53-61.MR 0557126 (81e:10003)
  • 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. R. R. Hall and G. Tenenbaum, Divisors, Cambridge University Press, 1988.MR 0964687 (90a:11107)
  • 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.

Similar Articles

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

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

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

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

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

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.

American Mathematical Society