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 Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: An old question of Erdős asks if there exists, for each number $N$, a finite set $S$ of integers greater than $N$ and residue classes $r(n)~(\textrm {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 Erdős and Selfridge. We also prove a conjecture of Erdős and Graham, that, for each fixed number $K>1$, the complement in $\mathbb Z$ of any union of residue classes $r(n)~(\textrm {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 Erdős and Graham, that if $S$ is a finite set of moduli greater than $N$, with a choice for residue classes $r(n)~(\textrm {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?)

  • 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
  • S. J. Benkoski and P. Erdős, On weird and pseudoperfect numbers, Math. Comp. 28 (1974), 617–623. MR 347726, DOI
  • E P. Erdős, A generalization of a theorem of Besicovitch, J. London Math. Soc. 11 (1936), 92–98.
  • P. Erdös, On integers of the form $2^k+p$ and some related problems, Summa Brasil. Math. 2 (1950), 113–123. MR 44558
  • 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
  • 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
  • P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de “L’Enseignement Mathématique” [Monographs of L’Enseignement Mathématique], vol. 28, Université de Genève, L’Enseignement Mathématique, Geneva, 1980. MR 592420
  • F K. Ford, The distribution of integers with a divisor in a given interval, preprint. G1 D. J. Gibson, Covering systems, Doctoral dissertation at U. Illinois at Urbana–Champaign, 2006.
  • Richard K. Guy, Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335
  • J. A. Haight, Covering systems of congruences, a negative result, Mathematika 26 (1979), no. 1, 53–61. MR 557126, DOI
  • 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
  • H. Halberstam and K. F. Roth, Sequences. Vol. I, Clarendon Press, Oxford, 1966. MR 0210679
  • Richard R. Hall and Gérald Tenenbaum, Divisors, Cambridge Tracts in Mathematics, vol. 90, Cambridge University Press, Cambridge, 1988. MR 964687
  • Adolf Hildebrand and Gérald Tenenbaum, Integers without large prime factors, J. Théor. Nombres Bordeaux 5 (1993), no. 2, 411–484. MR 1265913
  • Š. 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
  • J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
  • S 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
MR Author ID: 66800

Kevin Ford
Affiliation: Department of Mathematics, University of Illinois, Urbana, Illinois 61801
MR Author ID: 325647
ORCID: 0000-0001-9650-725X

Sergei Konyagin
Affiliation: Department of Mathematics, Moscow State University, Moscow 119992, Russia
MR Author ID: 188475

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

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.