## Sieving by large integers and covering systems of congruences

HTML articles powered by AMS MathViewer

- by Michael Filaseta, Kevin Ford, Sergei Konyagin, Carl Pomerance and Gang Yu PDF
- J. Amer. Math. Soc.
**20**(2007), 495-517 Request permission

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

- 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**, DOI 10.1002/0471722154 - S. J. Benkoski and P. Erdős,
*On weird and pseudoperfect numbers*, Math. Comp.**28**(1974), 617–623. MR**347726**, DOI 10.1090/S0025-5718-1974-0347726-9
E P. Erdős, - 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, - Richard K. Guy,
*Unsolved problems in number theory*, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR**2076335**, DOI 10.1007/978-0-387-26677-0 - J. A. Haight,
*Covering systems of congruences, a negative result*, Mathematika**26**(1979), no. 1, 53–61. MR**557126**, DOI 10.1112/S0025579300009608 - H. Halberstam and H.-E. Richert,
*Sieve methods*, London Mathematical Society Monographs, No. 4, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1974. 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**, DOI 10.1017/CBO9780511566004 - Adolf Hildebrand and Gérald Tenenbaum,
*Integers without large prime factors*, J. Théor. Nombres Bordeaux**5**(1993), no. 2, 411–484. MR**1265913**, DOI 10.5802/jtnb.101 - Š. 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,

*A generalization of a theorem of Besicovitch*, J. London Math. Soc.

**11**(1936), 92–98.

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

*Finite covers of groups by cosets or subgroups*, Internat. J. Math., to appear.

## Additional Information

**Michael Filaseta**- Affiliation: Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208
- MR Author ID: 66800
- Email: filaseta@math.sc.edu
**Kevin Ford**- Affiliation: Department of Mathematics, University of Illinois, Urbana, Illinois 61801
- MR Author ID: 325647
- ORCID: 0000-0001-9650-725X
- Email: ford@math.uiuc.edu
**Sergei Konyagin**- Affiliation: Department of Mathematics, Moscow State University, Moscow 119992, Russia
- MR Author ID: 188475
- Email: konyagin@ok.ru
**Carl Pomerance**- Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hamphshire 03755-3551
- MR Author ID: 140915
- Email: carl.pomerance@dartmouth.edu
**Gang Yu**- Affiliation: Department of Mathematical Sciences, Kent State University, Kent, Ohio 44242
- Email: yu@math.kent.edu
- 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. - © Copyright 2006
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2276778