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

Problem Statement
This paper addresses two conjectures proposed by Erdős and Hall regarding "separable numbers" and "interlocking pairs." Following their terminology, two positive integers $m$ and $n$ form an interlocking pair if, between any two consecutive divisors of $n$ (both greater than 1), there exists a divisor of $m$, and vice versa. An integer is defined as separable if it belongs to such a pair.

The authors focus on two specific open problems:

1. Density of Separable Powers of Two: Erdős and Hall conjectured that $2^k$ is separable for almost all $k$. They also noted the difficulty in determining whether the counting function $A(x)$ (the number of separable integers up to $x$) satisfies $A(x) = o(x)$.
2. Interlocking Products of Primes: Erdős and Hall conjectured that if $k$ is sufficiently large, no interlocking pair $(m, n)$ exists such that their product $mn$ equals $P_k$, the product of the first $k$ primes.

Methodology
The authors employ a combination of combinatorial number theory, divisor analysis, and results on prime gaps to resolve these conjectures.

• Divisor Counting and Parity: The paper begins by establishing Lemma 1, which relates the number of divisors $\tau(n)$ of two interlocking numbers. Specifically, if $d_2(n) < d_2(m)$, then $\tau(m) = \tau(n)$ if $n < m$, and $\tau(m) = \tau(n) - 1$ if $n > m$. This lemma is crucial for deriving contradictions regarding the structure of potential interlocking partners.
• Refuting the Conjecture on $2^k$:
  • To show that $2^k$ is not separable for a positive lower density of $k$, the authors analyze the constraints on the divisors of a hypothetical partner $m$. By examining cases where $\tau(m)$ is odd or even and utilizing modular arithmetic ($k \equiv 1, 2, 9, 10 \pmod{12}$), they demonstrate that any such $m$ would necessarily possess divisors that violate the interlocking condition (e.g., creating gaps between consecutive powers of 2 that cannot be filled).
  • To show that $2^k$ is separable for a positive lower density of $k$, the authors define a set $S$ of integers with "well-spread" divisors. Using Lemma 4 (a result on the distribution of divisors in intervals) and Lemma 3 (results on prime gaps), they prove that the set $S$ contains more than half of all positive integers. They then construct a specific interlocking partner $m$ for $n=2^k$ whenever $k$ belongs to a scaled version of $S$ ($2^t S$), thereby proving the existence of separable powers of two for a positive density of exponents.
• Confirming the Product Conjecture:
  • For the second conjecture, the authors analyze the distribution of prime factors between $m$ and $n$ when $mn = P_k$. By iteratively assigning small prime factors to $m$ and $n$ based on the interlocking requirement, they show that for $k > 8$, the constraints force a contradiction where $m$ must have divisors that $n$ cannot accommodate (specifically involving divisors like 23 and 26 versus the inability of $n$ to be a multiple of 24 or 25).

Key Contributions and Results
The paper provides definitive resolutions to the two conjectures:

1. Refutation of the "Almost All" Conjecture: The authors prove that the lower density of $k$ for which $2^k$ is separable is positive, but crucially, the lower density of $k$ for which $2^k$ is not separable is also positive.

   • Theorem 2: For all $k > 2$ with $k \equiv 1, 2, 9, 10 \pmod{12}$, $2^k$ is not separable.
   • Theorem 6: If $k \in 2^t S$ (where $S$ is the set of integers with well-distributed divisors), then $2^k$ is separable. The lower density of such $k$ is at least $1/2^{t+1}$.
   • Significance: This refutes the conjecture that $2^k$ is separable for almost all $k$, demonstrating that non-separable powers of two are frequent enough to have a positive lower density.

2. Confirmation of the Product Conjecture:

   • Theorem 9: If $(m, n)$ is an interlocking pair such that $mn = P_k$ (the product of the first $k$ primes), then $k \le 8$.
   • Significance: This confirms the Erdős-Hall conjecture that for large $k$, no such interlocking pair exists. The authors explicitly note that for even $k \le 8$, such pairs do exist, but they cease to exist beyond this threshold.

Significance
The paper resolves two long-standing open problems in the theory of separable numbers. By proving that the set of non-separable powers of two has a positive lower density, the authors clarify the distribution of separable numbers, showing that the property is not as ubiquitous as previously conjectured. Furthermore, by establishing a strict upper bound ($k \le 8$) for interlocking pairs formed by the product of the first $k$ primes, the paper settles the structural limitations of such pairs in relation to primorials. The authors also note that their results have been verified using the Lean proof assistant.