Sieving by large integers and covering systems of congruences

Simple item page
dc.creatorFilaseta, Michael
dc.creatorFord, Kevin
dc.creatorKonyagin, Sergei
dc.creatorPomerance, Carl
dc.creatorYu, Gang
dc.date2005-07-18
dc.date2006-08-09
dc.date.accessioned2026-07-07T07:45:33Z
dc.date.available2026-07-07T07:45:33Z
dc.descriptionAn 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) mod n for n in S whose union is all the integers. 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 the integers of any union of residue classes r(n) 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) mod n for n in S which covers the integers, 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.
dc.descriptionv3. 28 pages. Minor corrections and notational improvements. Added reference to recent discovery by Gibson of a covering system with least modulus 25. To appear in J. Amer. Math. Soc
dc.identifierhttps://arxiv.org/abs/math/0507374
dc.identifierhttp://arxiv.org/abs/math/0507374
dc.identifierJ. Amer. Math. Soc. 20 (2007), 495-517.
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/123566
dc.subjectNumber Theory
dc.subject11B25; 11A07; 11N35
dc.titleSieving by large integers and covering systems of congruences
dc.typetext

Files

Collections

arXiv