Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
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 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?)


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: http://dx.doi.org/10.1090/S0894-0347-06-00549-2
PII: S 0894-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.