Primes in LCM recurrences

1. 문제 제기 및 배경 (Problem Statement)

1.1 Rowland 의 점화식과 LCM 변형

• Rowland 의 점화식 (2008): $a_1 = 7$, $a_n = a_{n-1} + \gcd(n, a_{n-1})$로 정의되며, 그 차분 $a_n - a_{n-1}$은 항상 1 또는 소수임이 증명되었습니다.
• LCM 변형 (본 논문 주제): $a_1 = 1$, $a_n = a_{n-1} + \text{lcm}(n, a_{n-1})$로 정의됩니다. 여기서 중요한 양은 곱셈적 증가량 $b_n = \frac{a_n}{a_{n-1}} - 1 = \frac{n}{\gcd(n, a_{n-1})}$입니다.
• 주요 가설 (Conjecture 1.1): 모든 $n \ge 2$에 대해 $b_n \in \{1\} \cup \mathbb{P}$ (1 또는 소수) 입니다.
• 현재 상태: $n=10^6$까지 수치 계산으로 확인되었으나, 모든 $n$에 대한 증명은 아직 이루어지지 않았습니다.

1.2 난이도: 린니크 장벽 (Linnik Barrier)

• GCD 대신 LCM 을 사용하면 수열이 과거의 모든 증가량을 영구적으로 인코딩하는 '글로벌 누적 (global accumulation)' 특성을 가집니다.
• Ruiz-Cabello 는 이 점화식의 점별 (pointwise) 증명을 위해서는 모든 소수 $p$와 $k \ge 1$에 대해 $p^{k+1}$보다 작은 $q \equiv -1 \pmod p$인 소수 $q$가 최소 $k$개 이상 존재해야 함을 보였습니다.
• 이는 **린니크 정리 (Linnik's theorem)**의 상수 $L=2$를 요구하는 것으로, 현재 알려진 최선의 결과 ($L \le 5$) 보다 강한 조건입니다. 따라서 점별 증명보다는 평균적 접근이 필요합니다.

---

2. 방법론: 동반자 - 체 (Companion-Sieve) 프레임워크

저자는 수열의 전체 이력 (history) 에 의존하는 $p$-진 분석의 어려움을 극복하기 위해 결정론적인 부분 곱 (sub-product) 을 추출하고 이를 상한 (majorant) 으로 대체하는 새로운 프레임워크를 개발했습니다.

2.1 소수 단계와 보장된 주식 (Guaranteed Stock)

• 소수 $q \ge 5$에서 $b_q = q$임이 증명됩니다 (Lemma 3.1).
• 이를 바탕으로 $a_{n-1}$을 나누는 결정론적 인자 $C_{n-1} = \prod_{q \le n-1, q \ne 3} (q+1)$를 정의합니다.

2.2 동반자 (Companion) 와 나누기 체인

• $b_n$을 분석하기 위해 $b_n$을 나누는 더 쉬운 상한들을 정의합니다:
  1. $B^{(P)}_n$: $n / \gcd(n, C_{n-1})$.
  2. $B^{(1)}_n$: 각 소수 $p$가 $(q+1)$을 나누는지 여부만 고려한 '1-hit stock' 기반의 상한.
• 부족 (Deficit) 개념: $\delta^{(1)}_p(n) = \max\{0, v_p(n) - S^{(1)}_p(n-1)\}$. 여기서 $S^{(1)}_p$는 $q \equiv -1 \pmod p$인 소수들의 개수입니다.
• 부족 판정 기준 (Proposition 3.7): 만약 모든 소수에 대한 총 부족량 $\sum \delta^{(1)}_p(n) \le 1$이면, $b_n$은 1 또는 소수입니다. 이는 $b_n$이 $B^{(1)}_n$을 나누기 때문입니다.

2.3 분석 도구

• Bombieri-Vinogradov 정리: 소수들이 산술 수열에서 균등 분포함을 평균적으로 보장합니다.
• 소수 개수 추정: 소수 $p$에 대해 $q \equiv -1 \pmod p$인 소수들의 분포를 분석하여 부족량이 1 이하가 되는 경우를 규명합니다.

---

3. 주요 결과 (Key Results)

3.1 밀도 1 의 점화식 증명 (Theorem 1.2)

• 결과: $b_n \in \{1\} \cup \mathbb{P}$인 정수 $n$의 집합은 점근적 밀도 (asymptotic density) 가 1 입니다.
• 의미: 대부분의 $n$에 대해 가설이 성립함을 무조건적으로 (unconditionally) 증명했습니다.
• 증명 개요:
  • 작은 소수: Siegel-Walfisz 정리를 사용하여 공급이 수요를 초과함을 보임.
  • 중간 크기 소수: Bombieri-Vinogradov 정리를 사용하여 평균적으로 부족량이 0 임을 보임.
  • 큰 소수: 제곱 인자나 두 개의 서로 다른 큰 소수 인자를 가진 $n$의 집합은 밀도가 0 임을 보임.

3.2 유효한 유한 축소 (Effective Finite Reduction, Theorem 1.3)

• 임의의 $P_0$에 대해, 계산 가능한 상한 $N^*(P_0)$이 존재하여, $n \ge N^*(P_0)$인 경우 $b_n$이 합성수라면 그 모든 소인수는 $P_0$보다 커야 합니다.
• 이는 가설의 반례가 존재한다면 오직 매우 큰 소인수들만으로 구성된다는 것을 의미하며, 소인수 크기에 대한 제한을 둠으로써 문제를 축소했습니다.

3.3 K=2 변형과 쌍둥이 소수 (The Twin Prime Connection)

• 변형 점화식: $x_1=1$, $x_n = 2x_{n-1} + \text{lcm}(n, x_{n-1})$로 정의되며, 증가량 $c_n = \frac{n}{\gcd(n, x_{n-1})}$을 연구합니다.
• 쌍둥이 소수 감지 (Theorem 1.4 & Proposition 6.10):
  • $c_p = 1$인 소수 $p$는 $p-2$가 소수인 경우 (즉, $(p-2, p)$가 쌍둥이 소수) 에 발생합니다.
  • 단, 예외적으로 $(5, 7)$ 쌍은 $c_7=7$이 되어 감지되지 않습니다.
  • 역으로, $c_p=1$이면 $p-2$는 소수입니다.
  • 의미: 이 점화식은 쌍둥이 소수 쌍을 감지하는 메커니즘으로 작동합니다.
• 2-진 계단 구조 (2-adic staircase): $c_{2 \cdot 4^k} = 2$가 무한히 반복되며, $c_n$이 짝수일 때는 항상 2 임이 증명되었습니다.
• 조건부 밀도 1 정리 (Theorem 1.5): 소수 인덱스에서의 행동에 대한 가설과 쌍둥이 소수에 대한 Brun-type 상한을 가정하면, $c_n \in \{1\} \cup \mathbb{P}$인 집합의 밀도는 1 입니다.

---

4. 잔여 장애물과 새로운 가설 (Residual Obstructions & New Conjectures)

밀도 1 증명은 모든 $n$에 대한 증명이 아니므로, 밀도 0 인 예외 집합 (잔여 장애물) 을 분석했습니다. 이는 세 가지 경우로 나뉩니다:

1. (C1) 큰 소수 $p$에 대해 $p^2 | n$인 경우.
2. (C2) 두 개의 서로 다른 큰 소수 인자를 가진 경우.
3. (C3) 특정 소수 $p$가 $-1 \pmod p$ 클래스에서 개별적으로 나쁜 분포를 보이는 경우.

이 장애물을 제거하기 위해 두 가지 새로운 가설이 제안되었습니다:

• 가설 7.2 (제 2 소수 제곱 창): 모든 소수 $p \ge 17$에 대해 $p^2$ 이하에 $q \equiv -1 \pmod p$인 소수가 최소 2 개 이상 존재한다. (이는 C1 을 제거함)
• 가설 7.3 (약분자 안전 균등 분포): $n$의 소인수 $p$에 대해 $E(n-1; p, -1)$의 오차항이 특정 조건을 만족한다. (이는 C3 을 제거함)

이 두 가설과 Elliott-Halberstam 가설을 결합하면, 충분히 큰 $n$에 대해 원래 가설이 성립함을 증명할 수 있습니다.

---

5. 의의 및 결론 (Significance)

1. 이론적 기여: 단순한 산술 점화식이 소수 분포의 깊은 문제 (린니크 정리, 쌍둥이 소수 추측, Elliott-Halberstam 가설 등) 와 어떻게 연결되는지를 보여주었습니다.
2. 방법론적 혁신: '동반자 - 체 (Companion-Sieve)' 프레임워크를 도입하여, 복잡한 수열의 이력 의존성을 우회하고 평균적 소수 분포 정리를 적용할 수 있게 했습니다.
3. 쌍둥이 소수와의 연결: K=2 변형 점화식을 통해 쌍둥이 소수 쌍을 감지하는 메커니즘을 발견하고, 이를 통해 쌍둥이 소수 추측과 관련된 새로운 통찰을 제공했습니다.
4. 증명의 한계와 방향: 무조건적으로 밀도 1 을 증명했으나, 완전한 증명을 위해서는 소수 분포에 대한 더 강한 점별 추정 (Linnik 상수 개선 또는 새로운 가설) 이 필요함을 명확히 했습니다.

이 논문은 소수 생성 점화식 연구의 지평을 넓히고, 수론의 난제들을 해결하기 위한 새로운 접근법을 제시했다는 점에서 중요한 의의를 가집니다.