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
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 $ 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. 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 $ 2\sp k+p$ 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.

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
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.

American Mathematical Society