On the Erdős covering problem: the density of the uncovered set
On the Erdős covering problem: the density of the uncovered set
复制标题
关于 ErdÅs 覆盖问题：未覆盖集的密度
DOI：
10.1007/s00222-021-01087-5
复制
发表时间：
2022
影响因子：
3.1
通讯作者：
Tiba, Marius
中科院分区：
文献类型：
--
作者：
Balister, Paul;Bollobás, Béla;Morris, Robert;Sahasrabudhe, Julian;Tiba, Marius
自1950年Erdős引入覆盖系统以来，覆盖系统（即覆盖整数的算术数列的有限集合）已经被广泛研究，并且已经提出了许多关于具有各种性质的覆盖系统的存在性的问题和猜想。特别地，Erdős问模是否可以是不同的并且都是任意大的，Erdős和Selfridge问模是否可以是不同的并且都是奇数的，Schinzel推测在任何覆盖系统中都存在一对模，其中一个模可以除另一个模。另一个美丽的猜想，由Erdős和Graham在1980年提出，指出如果模是区间[n，Cn]的不同元素，并且足够大，那么由并集揭示的整数的密度在下面由一个常数（仅取决于c）限定。这个猜想在2007年被Filaseta， Ford, Konyagin， Pomerance和Yu（以一种强形式）证实，他们还问如果模是不同的并且足够大，那么同样的结论是否成立。虽然，正如我们将要看到的，这个条件并不足以暗示我们所期望的结论，但作为本文的主要结果之一，我们将给出一个本质上最好的可能条件，它是充分的。更准确地说，我们证明了如果所有的模都足够大，那么这个并集至少遗漏了一组密度，其中$$\begin{aligned} C = \sum _{i=1}^k \frac{\mu (d_i)}{d_i} \end{aligned}$$和是一个由某些定义的乘法函数。我们还表明，当被任何形式的函数取代时，未覆盖集的密度没有这样的下界（即，仅依赖于一个c）。我们的方法有许多进一步的应用。最重要的是，作为我们的第二个主要定理，我们证明了上面提到的Schinzel猜想，这是1967年提出的。此外，我们还给出了Hough解决Erdős最小模问题的突破性结果的另一种（更简单的）证明，并改进了最小差的界。最后，对Erdős和Selfridge的问题进行了进一步的研究。
Since their introduction by Erdős 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, Erdős asked if the moduli can be distinct and all arbitrarily large, Erdős and Selfridge asked if the moduli 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 Erdős and Graham in 1980, states that if the moduli are distinct elements of the interval [n,Cn], andnis sufficiently large, then the density of integers uncovered by the union is bounded below by a constant (depending only onC). 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. 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, where $$\begin{aligned} C = \sum _{i=1}^k \frac{\mu (d_i)}{d_i} \end{aligned}$$andis a multiplicative function defined byfor some. We also show that no such lower bound (i.e., depending only onC) on the density of the uncovered set holds whenis replaced by any function of the form. 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 Erdős’ minimum modulus problem, with an improved bound on the smallest difference. Finally, we make further progress on the problem of Erdős and Selfridge.
影响因子：
2.5
作者：
Hough, Robert D.;Nielsen, Pace P.
通讯作者：
Nielsen, Pace P.