Sieving by large integers and covering systems of congruences

Filaseta, Michael¹ ; Ford, Kevin² ; Konyagin, Sergei³ ; Pomerance, Carl⁴ ; Yu, Gang⁵

¹ Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208
² Department of Mathematics, University of Illinois, Urbana, Illinois 61801
³ Department of Mathematics, Moscow State University, Moscow 119992, Russia
⁴ Department of Mathematics, Dartmouth College, Hanover, New Hamphshire 03755-3551
⁵ Department of Mathematical Sciences, Kent State University, Kent, Ohio 44242

Journal of the American Mathematical Society, Tome 20 (2007) no. 2, pp. 495-517

Résumé

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.

Détail

DOI : 10.1090/S0894-0347-06-00549-2

Bibliographie

[1] Alon, Noga, Spencer, Joel H. The probabilistic method 2000

[2] Benkoski, S. J., Erdå‘S, P. On weird and pseudoperfect numbers Math. Comp. 1974 617 623

[3] Erdã¶S, P. On integers of the form 2^{𝑘}+𝑝 and some related problems Summa Brasil. Math. 1950 113 123

[4] Erdå‘S, P. Problems and results on combinatorial number theory 1973 117 138

[5] Erdå‘S, Paul Some of my favourite problems in number theory, combinatorics, and geometry Resenhas 1995 165 186

[6] Erdå‘S, P., Graham, R. L. Old and new problems and results in combinatorial number theory 1980 128

[7] Guy, Richard K. Unsolved problems in number theory 2004

[8] Haight, J. A. Covering systems of congruences, a negative result Mathematika 1979 53 61

[9] Halberstam, H., Richert, H.-E. Sieve methods 1974

[10] Halberstam, H., Roth, K. F. Sequences. Vol. I 1966

[11] Hall, Richard R., Tenenbaum, Gã©Rald Divisors 1988

[12] Hildebrand, Adolf, Tenenbaum, Gã©Rald Integers without large prime factors J. Théor. Nombres Bordeaux 1993 411 484

[13] Porubskã½, Å ., Schã¶Nheim, J. Covering systems of Paul Erdős. Past, present and future 2002 581 627

[14] Rosser, J. Barkley, Schoenfeld, Lowell Approximate formulas for some functions of prime numbers Illinois J. Math. 1962 64 94