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), 495517
MSC (2000):
Primary 11B25, 11A07, 11N35
Published electronically:
September 19, 2006
MathSciNet review:
2276778
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: An old question of Erdos asks if there exists, for each number , a finite set of integers greater than and residue classes for whose union is . We prove that if is bounded for such a covering of the integers, then the least member of 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 , the complement in of any union of residue classes , for distinct , has density at least for sufficiently large. Here is a positive number depending only on . Either of these new results implies another conjecture of Erdos and Graham, that if is a finite set of moduli greater than , with a choice for residue classes for which covers , then the largest member of cannot be . We further obtain stronger forms of these results and establish other information, including an improvement of a related theorem of Haight.
 1.
Noga
Alon and Joel
H. Spencer, The probabilistic method, 2nd ed.,
WileyInterscience Series in Discrete Mathematics and Optimization,
WileyInterscience [John Wiley & Sons], New York, 2000. With an
appendix on the life and work of Paul Erdős. MR 1885388
(2003f:60003)
 2.
S.
J. Benkoski and P.
Erdős, On weird and pseudoperfect
numbers, Math. Comp. 28 (1974), 617–623. MR 0347726
(50 #228), http://dx.doi.org/10.1090/S00255718197403477269
 3.
P. Erdos, A generalization of a theorem of Besicovitch, J. London Math. Soc. 11 (1936), 9298.
 4.
P.
Erdös, On integers of the form 2^{𝑘}+𝑝 and
some related problems, Summa Brasil. Math. 2 (1950),
113–123. MR 0044558
(13,437i)
 5.
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), NorthHolland,
Amsterdam, 1973, pp. 117–138. MR 0360509
(50 #12957)
 6.
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 (97e:11003)
 7.
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
(82j:10001)
 8.
K. Ford, The distribution of integers with a divisor in a given interval, preprint.
 9.
D. J. Gibson, Covering systems, Doctoral dissertation at U. Illinois at UrbanaChampaign, 2006.
 10.
Richard
K. Guy, Unsolved problems in number theory, 3rd ed., Problem
Books in Mathematics, SpringerVerlag, New York, 2004. MR 2076335
(2005h:11003)
 11.
J.
A. Haight, Covering systems of congruences, a negative result,
Mathematika 26 (1979), no. 1, 53–61. MR 557126
(81e:10003), http://dx.doi.org/10.1112/S0025579300009608
 12.
H.
Halberstam and H.E.
Richert, Sieve methods, Academic Press [A subsidiary of
Harcourt Brace Jovanovich, Publishers], LondonNew York, 1974. London
Mathematical Society Monographs, No. 4. MR 0424730
(54 #12689)
 13.
H.
Halberstam and K.
F. Roth, Sequences. Vol. I, Clarendon Press, Oxford, 1966. MR 0210679
(35 #1565)
 14.
Richard
R. Hall and Gérald
Tenenbaum, Divisors, Cambridge Tracts in Mathematics,
vol. 90, Cambridge University Press, Cambridge, 1988. MR 964687
(90a:11107)
 15.
Adolf
Hildebrand and Gérald
Tenenbaum, Integers without large prime factors, J.
Théor. Nombres Bordeaux 5 (1993), no. 2,
411–484. MR 1265913
(95d:11116)
 16.
Š.
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
(2004d:11006)
 17.
J.
Barkley Rosser and Lowell
Schoenfeld, Approximate formulas for some functions of prime
numbers, Illinois J. Math. 6 (1962), 64–94. MR 0137689
(25 #1139)
 18.
Z.W. Sun, Finite covers of groups by cosets or subgroups, Internat. J. Math., to appear.
 1.
 N. Alon and J. Spencer, The probabilistic method. Second edition. With an appendix on the life and work of Paul Erdos, WileyInterscience, 2000. MR 1885388 (2003f:60003)
 2.
 S. J. Benkoski and P. Erdos, On weird and pseudoperfect numbers, Math. Comp. 28 (1974), 617623. MR 0347726 (50:228)
 3.
 P. Erdos, A generalization of a theorem of Besicovitch, J. London Math. Soc. 11 (1936), 9298.
 4.
 P. Erdos, On integers of the form and some related problems, Summa Brasil. Math. 2 (1950), 113123. MR 0044558 (13:437i)
 5.
 P. Erdos, Problems and results in combinatorial number theory, A survey of combinatorial theory, J. N. Srivastava, ed., NorthHolland, Amsterdam, 1973, 117138. MR 0360509 (50:12957)
 6.
 P. Erdos, Some of my favourite problems in number theory, combinatorics, and geometry, Combinatorics Week (Portuguese) (São Paulo, 1994), Resenhas 2 (1995), no. 2, 165186. MR 1370501 (97e:11003)
 7.
 P. Erdos and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathématique, No. 28, 1980. MR 0592420 (82j:10001)
 8.
 K. Ford, The distribution of integers with a divisor in a given interval, preprint.
 9.
 D. J. Gibson, Covering systems, Doctoral dissertation at U. Illinois at UrbanaChampaign, 2006.
 10.
 R. K. Guy, Unsolved problems in number theory, 3rd ed. Problem Books in Mathematics. SpringerVerlag, New York, 2004. MR 2076335 (2005h:11003)
 11.
 J. A. Haight, Covering systems of congruences, a negative result, Mathematika 26 (1979), 5361.MR 0557126 (81e:10003)
 12.
 H. Halberstam and H.E. Richert, Sieve methods, Academic Press, 1974.MR 0424730 (54:12689)
 13.
 H. Halberstam and K. Roth, Sequences. Vol. 1, Clarendon Press, 1966.MR 0210679 (35:1565)
 14.
 R. R. Hall and G. Tenenbaum, Divisors, Cambridge University Press, 1988.MR 0964687 (90a:11107)
 15.
 A. Hildebrand and G. Tenenbaum, Integers without large prime factors, J. de Théorie des Nombres de Bordeaux, 5 (1993), 411484.MR 1265913 (95d:11116)
 16.
 S. Porubský and J. Schönheim, Covering systems of Paul Erdos: Past, present and future, in Paul Erdos and his mathematics, vol. I, János Bolyai Math. Soc., Budapest, 2002, pp. 581627. MR 1954716 (2004d:11006)
 17.
 J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 6494.MR 0137689 (25:1139)
 18.
 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
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 037553551
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/S0894034706005492
PII:
S 08940347(06)005492
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 DMS0207302 and NSA grant H982300510038.
The second author was supported by NSF grant DMS0301083.
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 DMS0200187) and the University of Illinois at UrbanaChampaign in February 2004 (supported by NSF grant DMS0301083).
The fourth author was supported by NSF grant DMS0401422.
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 DMS0601033.
Article copyright:
© Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
