Resolution of two conjectures by Erd\H{o}s and Hall concerning separable numbers

问题陈述
本文解决了 Erdős 和 Hall 关于“可分数”和“互锁对”提出的两个猜想。沿用他们的术语，两个正整数 $m$ 和 $n$ 构成一个互锁对，如果在 $n$ 的任意两个连续除数（均大于 1）之间存在 $m$ 的一个除数，反之亦然。如果一个整数属于这样的对，则被定义为可分的。

作者聚焦于两个具体的未解决问题：

1. 2 的幂的可分性密度：Erdős 和 Hall 猜想，对于几乎所有的 $k$，$2^k$ 是可分的。他们还指出，确定计数函数 $A(x)$（即不超过 $x$ 的可分整数个数）是否满足 $A(x) = o(x)$ 存在困难。
2. 素数乘积的互锁性：Erdős 和 Hall 猜想，如果 $k$ 足够大，则不存在互锁对 $(m, n)$ 使得它们的乘积 $mn$等于$P_k$（即前$k$ 个素数的乘积）。

方法论
作者结合组合数论、除数分析和素数间隙的研究成果来解决这些猜想。

• 除数计数与奇偶性：本文首先建立了引理 1，该引理关联了两个互锁数的除数个数 $\tau(n)$。具体而言，如果 $d_2(n) < d_2(m)$，那么当 $n < m$ 时 $\tau(m) = \tau(n)$，而当 $n > m$ 时 $\tau(m) = \tau(n) - 1$。该引理对于推导潜在互锁伙伴结构的矛盾至关重要。
• 反驳关于 $2^k$ 的猜想：
  • 为了证明对于正下密度的 $k$，$2^k$ 不可分，作者分析了假设伙伴 $m$ 的除数约束。通过考察 $\tau(m)$ 为奇数或偶数的情况，并利用模运算（$k \equiv 1, 2, 9, 10 \pmod{12}$），他们证明了任何这样的 $m$ 必然拥有违反互锁条件的除数（例如，在连续的 2 的幂之间产生无法填补的间隙）。
  • 为了证明对于正下密度的 $k$，$2^k$ 可分，作者定义了一组具有“分布良好”除数的整数集合 $S$。利用引理 4（关于区间内除数分布的结果）和引理 3（关于素数间隙的结果），他们证明了集合 $S$ 包含超过一半的正整数。随后，每当 $k$ 属于 $S$ 的缩放版本（$2^t S$）时，他们为 $n=2^k$ 构造了一个特定的互锁伙伴 $m$，从而证明了对于正密度的指数，存在可分的 2 的幂。
• 确认乘积猜想：
  • 对于第二个猜想，作者分析了当 $mn = P_k$ 时 $m$ 和 $n$ 之间素因子的分布。通过根据互锁要求迭代地将小素因子分配给 $m$ 和 $n$，他们证明了对于 $k > 8$，约束条件会导致矛盾，即 $m$ 必须拥有 $n$ 无法容纳的除数（具体涉及如 23 和 26 这样的除数，而 $n$ 无法成为 24 或 25 的倍数）。

主要贡献与结果
本文对这两个猜想提供了确定的解答：

1. 反驳“几乎所有”猜想：作者证明了 $2^k$ 可分的 $k$ 的下密度是正的，但至关重要的是，$2^k$ 不可分的 $k$ 的下密度也是正的。

   • 定理 2：对于所有满足 $k > 2$ 且 $k \equiv 1, 2, 9, 10 \pmod{12}$ 的 $k$，$2^k$ 不可分。
   • 定理 6：如果 $k \in 2^t S$（其中 $S$ 是除数分布良好的整数集合），则 $2^k$ 可分。此类 $k$ 的下密度至少为 $1/2^{t+1}$。
   • 意义：这反驳了"$2^k$ 对几乎所有 $k$ 可分”的猜想，证明了不可分的 2 的幂足够频繁，以至于具有正的下密度。

2. 确认乘积猜想：

   • 定理 9：如果 $(m, n)$ 是一个互锁对且满足 $mn = P_k$（前 $k$ 个素数的乘积），则 $k \le 8$。
   • 意义：这证实了 Erdős-Hall 猜想，即对于大的 $k$，不存在这样的互锁对。作者明确指出，对于偶数 $k \le 8$，此类对确实存在，但超过此阈值后便不再存在。

意义
本文解决了可分数理论中两个长期存在的未解决问题。通过证明不可分的 2 的幂集合具有正的下密度，作者阐明了可分数的分布，表明该性质并不像先前猜想的那样普遍。此外，通过确立由前 $k$ 个素数乘积形成的互锁对的严格上界（$k \le 8$），本文解决了此类对与素数阶乘积（primorials）相关的结构限制。作者还指出，他们的结果已通过 Lean 证明助手进行了验证。