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

문제 진술
본 논문은 에르되시와 홀이 제안한 "분리 가능한 수 (separable numbers)"와 "교차하는 쌍 (interlocking pairs)"에 관한 두 가지 추측을 다룬다. 그들의 용어를 따르면, 두 양의 정수 $m$과 $n$이 교차하는 쌍을 이룬다는 것은, $n$의 임의의 두 연속된 약수 (둘 다 1 보다 큼) 사이에 $m$의 약수가 존재하고, 그 역도 성립함을 의미한다. 한 정수가 그러한 쌍에 속할 때, 그 정수를 분리 가능한 것으로 정의한다.

저자들은 두 가지 구체적인 미해결 문제에 초점을 맞춘다:

1. 2 의 거듭제곱 중 분리 가능한 수의 밀도: 에르되시와 홀은 거의 모든 $k$에 대해 $2^k$가 분리 가능하다고 추측했다. 또한, 분리 가능한 정수의 개수를 $x$까지 세는 함수 $A(x)$가 $A(x) = o(x)$를 만족하는지 여부를 결정하는 것이 어렵다고 지적했다.
2. 소수의 곱에 대한 교차: 에르되시와 홀은 $k$가 충분히 크다면, 그 곱 $mn$이 처음$k$개의 소수의 곱인$P_k$와 같아지는 교차하는 쌍$(m, n)$은 존재하지 않는다고 추측했다.

방법론
저자들은 이러한 추측을 해결하기 위해 조합적 수론, 약수 분석, 그리고 소수 간격에 관한 결과를 결합하여 활용한다.

• 약수 개수와 홀짝성: 본 논문은 두 교차하는 수의 약수 개수 $\tau(n)$과 관련된 보조정리 1 을 먼저 제시한다. 구체적으로, $d_2(n) < d_2(m)$일 때, $n < m$이면 $\tau(m) = \tau(n)$이며, $n > m$이면 $\tau(m) = \tau(n) - 1$이다. 이 보조정리는 잠재적인 교차 파트너의 구조에 관한 모순을 도출하는 데 결정적이다.
• $2^k$에 관한 추측 반박:
  • $2^k$가 $k$의 양의 하한 밀도 (positive lower density) 에 대해 분리 불가능함을 보이기 위해, 저자들은 가상의 파트너 $m$의 약수에 대한 제약을 분석한다. $\tau(m)$이 홀수이거나 짝수인 경우를 검토하고 모듈러 산술 ($k \equiv 1, 2, 9, 10 \pmod{12}$) 을 활용함으로써, 그러한 $m$은 필연적으로 연속된 2 의 거듭제곱 사이에 간격을 만들어 교차 조건을 위반하는 약수를 갖게 됨을 보여준다.
  • $2^k$가 $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 과 같은 약수 대 24 나 25 의 배수가 될 수 없는 $n$) 를 갖게 된다.

주요 기여 및 결과
본 논문은 두 가지 추측에 대한 결정적인 해결책을 제시한다:

1. "거의 모든" 추측의 반박: 저자들은 $2^k$가 분리 가능한 $k$의 하한 밀도가 양수임을 증명하지만, 결정적으로 $2^k$가 분리 불가능한 $k$의 하한 밀도 또한 양수임을 증명한다.

   • 정리 2: 모든 $k > 2$에 대해 $k \equiv 1, 2, 9, 10 \pmod{12}$이면, $2^k$는 분리 불가능하다.
   • 정리 6: $k \in 2^t S$ (여기서 $S$는 잘 분포된 약수를 가진 정수들의 집합) 이면, $2^k$는 분리 가능하다. 그러한 $k$의 하한 밀도는 적어도 $1/2^{t+1}$이다.
   • 의의: 이는 거의 모든 $k$에 대해 $2^k$가 분리 가능하다는 추측을 반박하며, 분리 불가능한 2 의 거듭제곱이 양의 하한 밀도를 가질 만큼 빈번함을 보여준다.

2. 곱에 관한 추측의 확인:

   • 정리 9: $(m, n)$이 $mn = P_k$ (처음 $k$개의 소수의 곱) 인 교차하는 쌍이라면, $k \le 8$이다.
   • 의의: 이는 큰 $k$에 대해 그러한 교차하는 쌍이 존재하지 않는다는 에르되시 - 홀 추측을 확인한다. 저자들은 짝수인 $k \le 8$인 경우 그러한 쌍이 존재하지만, 이 임계값을 넘어서면 더 이상 존재하지 않는다고 명시적으로 언급한다.

의의
본 논문은 분리 가능한 수 이론의 두 가지 오랜 미해결 문제를 해결한다. 분리 불가능한 2 의 거듭제곱 집합이 양의 하한 밀도를 가진다는 것을 증명함으로써, 저자들은 분리 가능한 수의 분포를 명확히 하여 그 성질이 이전에 추측되었던 것처럼 보편적이지 않음을 보여준다. furthermore, 처음 $k$개의 소수의 곱으로 이루어진 교차하는 쌍에 대해 엄격한 상한 ($k \le 8$) 을 확립함으로써, 본 논문은 프라임리얼 (primorials) 과 관련하여 그러한 쌍의 구조적 한계를 확정한다. 저자들은 또한 그들의 결과가 Lean 증명 보조기기를 사용하여 검증되었음을 언급한다.