On the Erdos covering problem: the density of the uncovered set

• 成果类型: Article
• 署名作者: Balister, Paul; Bollobas, Bela; Morris, Robert; Sahasrabudhe, Julian; Tiba, Marius
• 署名单位: University of Oxford; University of Memphis; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
• 刊物名称: INVENTIONES MATHEMATICAE
• ISSN/ISSBN: 0020-9910
• DOI: 10.1007/s00222-021-01087-5
• 发表日期: 2022
• 页码: 377-414
• 关键词: systems

摘要

Since their introduction by Erdos in 1950, covering systems (that is, finite collections of arithmetic progressions that cover the integers) have been extensively studied, and numerous questions and conjectures have been posed regarding the existence of covering systems with various properties. In particular, Erdos asked if the moduli can be distinct and all arbitrarily large, Erdos and Selfridge asked if themoduli can be distinct and all odd, and Schinzel conjectured that in any covering system there exists a pair of moduli, one of which divides the other. Another beautiful conjecture, proposed by Erdos and Graham in 1980, states that if the moduli are distinct elements of the interval [n, Cn], andn is sufficiently large, then the density of integers uncovered by the union is bounded below by a constant (depending only on C). This conjecture was confirmed (in a strong form) by Filaseta, Ford, Konyagin, Pomerance and Yu in 2007, who moreover asked whether the same conclusion holds if the moduli are distinct and sufficiently large, and Sigma(K)(I)=1 1/di < C. Although, as we shall see, this condition is not sufficiently strong to imply the desired conclusion, as one of the main results of this paper we will give an essentially best possible condition which is sufficient. More precisely, we show that if all of the moduli are sufficiently large, then the union misses a set of density at least e(-4C)/2, where c = Sigma(K mu()(I=1)d(i))/d(i) and mu is a multiplicative function defined by mu(p(i)) = 1 + (log p)(3+epsilon)/p for some epsilon > 0. We also show that no such lower bound (i.e., depending only on C) on the density of the uncovered set holds when mu(p(i)) is replaced by any function of the form 1 + O(1/p). Our method has a number of further applications. Most importantly, as our second main theorem, we prove the conjecture of Schinzel stated above, which was made in 1967. We moreover give an alternative (somewhat simpler) proof of a breakthrough result of Hough, who resolved Erdos' minimum modulus problem, with an improved bound on the smallest difference. Finally, we make further progress on the problem of Erdos and Selfridge.