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

- 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 https://doi.org/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** - J. A. Haight,
*Covering systems of congruences, a negative result*, Mathematika**26**(1979), no. 1, 53–61. MR**557126**, DOI https://doi.org/10.1112/S0025579300009608 - 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,

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

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

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

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.