Two dimensional covering systems and possible prime producing $a^m-b^n$

앤드루 그라빌 (Andrew Granville) 과 프란체스코 파팔라르디 (Francesco Pappalardi) 의 논문 **"TWO DIMENSIONAL COVERING SYSTEMS AND POSSIBLE PRIME PRODUCING $a^m - b^n$"**은 정수론의 고전적인 문제인 $a^m - b^n$ 형태의 수가 소수를 생성하는 조건과 그 개수를 추정하는 데 초점을 맞춘 연구입니다.

이 논문은 **2 차원 덮개 시스템 (Two-dimensional covering systems)**을 새로운 도구로 활용하여, 특정 조건 하에서 $a^m - b^n$이 소수 값을 가질 수 없는 경우를 체계적으로 분류하고, 그렇지 않은 경우 소수의 분포에 대한 점근적 공식을 제시합니다.

다음은 논문의 상세한 기술적 요약입니다.

---

1. 문제 제기 (Problem Statement)

연구자들은 두 정수 $a, b \ge 2$에 대해 식 $|a^m - b^n|$이 무한히 많은 서로 다른 소수 값을 가질 수 있는지 여부에 대한 근본적인 질문을 던집니다.

• 기본 관측: 특정 $a, b$의 경우 (예: $41^m - 34^n$), 모든 $m, n \ge 0$에 대해 $|a^m - b^n|$이 유한한 소수 집합 (예: $\{3, 5, 7\}$) 중 하나의 배수가 되어 소수가 될 수 없거나, 유한한 경우만 소수가 될 수 있습니다.
• 시겔의 S-단위 정리 (Siegel's S-unit theorem): 만약 $|a^m - b^n|$의 소인수들이 유한한 집합 $S$에만 속한다면, $a^m - b^n = c$인 해는 유한합니다. 이를 통해 만약 $a^m - b^n$이 항상 어떤 정수 $Q$와 1 보다 큰 공약수를 가진다면, 소수 값은 유한하게만 존재함을 보일 수 있습니다.
• 핵심 질문: $a^m - b^n$이 소수 값을 무한히 많이 가지지 못하는 유일한 장애물 (Obstruction) 은 $a^m - b^n$이 항상 어떤 고정된 정수 $Q$와 1 보다 큰 공약수를 갖는 경우인가?

2. 주요 가설 (Conjectures)

저자들은 다음과 같은 가설을 제시합니다.

• 가설 1 (Conjecture 1): $a, b \ge 2$이고, $a$나 $b$가 어떤 정수의 거듭제곱이 아닌 경우, $a^m - b^n$이 소수 값을 무한히 많이 가지지 않는 유일한 경우는 모든 $m, n \ge 1$에 대해 $(a^m - b^n, Q) > 1$인 0 이 아닌 정수 $Q$가 존재하는 경우입니다.
  • 만약 이러한 $Q$가 존재하지 않는다면, 소수의 개수는 $\sim c_{a,b} \log x$로 점근적으로 증가할 것으로 예상합니다.
• 가설 2 (Conjecture 2): $a$나 $b$가 거듭제곱인 경우 ($a=A^k, b=B^\ell$) 에는 $(m, \ell)=1, (n, k)=1$인 조건 하에서 위와 유사한 장애물이 존재하는지 여부를 다룹니다.

3. 방법론 (Methodology)

이 논문은 **2 차원 덮개 시스템 (2D Covering Systems)**을 핵심 도구로 사용하여 문제를 해결합니다.

3.1. 2 차원 덮개 시스템의 정의

정수 쌍의 집합 $\{(u_i, v_i, r_i)\}$이 모든 정수 쌍 $(m, n)$에 대해 적어도 하나의 $i$에 대해 $m v_i \equiv n u_i \pmod{r_i}$를 만족할 때, 이를 2 차원 덮개 시스템이라고 정의합니다.

3.2. 소수 $p$에 의한 분할 구조

정수 $a, b$가 소수 $p$로 나누어지지 않을 때, $a^m \equiv b^n \pmod p$가 성립하는 $(m, n)$의 집합은 2 차원 격자 (sublattice) 로 표현됩니다.

• Proposition 3 에 따르면, $a^m \equiv b^n \pmod p$인 조건은 축소된 3 중항 (reduced triple) $(u, v, L)$에 의해 정의된 집합 $S(u, v, L)$과 동일합니다. 여기서 $L = [\text{ord}_p(a), \text{ord}_p(b)]$입니다.

3.3. 덮개 시스템과 장애물의 동치성

• Corollary 1: 모든 $m, n \ge 1$에 대해 $(a^m - b^n, Q) > 1$인 정수 $Q$가 존재할 필요충분조건은, $Q$의 소인수 $p$들에 대응하는 축소된 3 중항들의 집합 $\{S(u_p, v_p, L_p)\}$이 2 차원 덮개 시스템을 이룬다는 것입니다.
• 즉, $a^m - b^n$이 소수가 될 수 없는 "장애물"은 2 차원 덮개 시스템의 존재와 정확히 일치합니다.

3.4. 구성 알고리즘

저자들은 주어진 2 차원 덮개 시스템으로부터 이를 만족하는 $(a, b, Q)$를 구성하는 방법을 제시합니다.

• 덮개 시스템의 각 요소 $(u_i, v_i, L_i)$에 대해 서로 다른 소수 $p_i \equiv 1 \pmod{L_i}$를 선택하고, 중국인의 나머지 정리를 이용해 $a, b$를 구성합니다.
• 이를 통해 $a^m - b^n$이 항상 $Q = \prod p_i$와 1 보다 큰 공약수를 갖도록 하는 $(a, b)$ 쌍을 생성할 수 있습니다.

4. 주요 결과 (Key Results)

4.1. 장애물의 완전한 분류

논문은 $a^m - b^n$이 소수 값을 무한히 많이 가지지 않는 경우를 2 차원 덮개 시스템을 통해 완전히 분류할 수 있음을 보였습니다.

• 예시: $41^m - 34^n$의 경우, 2 차원 덮개 시스템 $\{(1, 0, 2), (0, 1, 2), (1, 1, 2)\}$에 의해 모든 경우 3, 5, 7 중 하나로 나누어짐이 증명됩니다.
• $a=51, b=64$와 같은 혼합 사례 (한쪽이 거듭제곱) 에 대해서도 유사한 논리가 적용됨을 보였습니다.

4.2. 소수 개수의 점근적 추정 (Heuristic)

장애물이 없는 경우, $|a^m - b^n| \le x$인 소수의 개수는 다음과 같이 추정됩니다.
$$\#\{ |a^m - b^n| \le x : |a^m - b^n| \text{ is prime} \} \sim c_{a,b} \log x$$
여기서 상수 $c_{a,b}$는 다음과 같이 정의됩니다:
$$c_{a,b} = \frac{2ab \kappa_{a,b}}{\phi(ab) \log a \log b}$$

• $\kappa_{a,b}$는 작은 소수들에 대한 국소적 확률 (local probabilities) 을 보정한 상수입니다.
• 크래머 (Cramér) 가설을 기반으로 하되, $a^m - b^n$이 특정 소수로 나누어질 확률이 독립적이지 않다는 점을 고려하여 보정되었습니다.

4.3. 계산적 검증 (Computational Evidence)

저자들은 다양한 $(a, b)$ 쌍에 대해 계산을 수행하여 가설을 검증했습니다.

• 데이터 분석: $b \le 100$ 및 $a+b \le 500$ 범위의 데이터에서, 덮개 시스템이 존재하지 않는 경우 소수 개수가 예측치 ($G_2(a, b)$) 와 매우 잘 일치함을 확인했습니다.
• 예외 사례 확인: 소수가 매우 드물게 나오는 경우 (예: $\Pi_{a,b}(100) < 25$) 를 분석한 결과, 대부분 2 차원 덮개 시스템이 존재하여 소수 생성이 억제됨을 확인했습니다.
  • 예: $(13, 302), (122, 307), (13, 356)$ 등의 쌍은 특정 덮개 시스템에 의해 모든 $m, n$에 대해 소수 집합으로 나누어짐이 확인되었습니다.

5. 의의 및 결론 (Significance)

1. 새로운 연결 고리: 정수론의 고전적인 문제 ($a^m - b^n$의 소수 생성) 와 조합론적 구조 (2 차원 덮개 시스템) 를 깊이 있게 연결했습니다. 이는 소수 분포를 이해하는 데 새로운 기하학적/대수적 관점을 제공합니다.
2. 장애물의 체계적 분류: $a^m - b^n$이 소수가 되지 못하는 모든 경우를 2 차원 덮개 시스템의 존재로 설명할 수 있다는 강력한 주장을 제시했습니다. 이는 "소수 생성 실패"의 원인을 완전히 규명하려는 시도입니다.
3. 정량적 예측: 소수의 개수에 대한 구체적인 점근적 공식과 상수 $\kappa_{a,b}$를 제안하며, 이를 계산적 데이터를 통해 검증했습니다. 이는 랜덤 모델 (Cramér heuristic) 을 비선형적/구조적 문제에 적용할 때 필요한 보정 계수를 어떻게 구할지에 대한 실마리를 제공합니다.
4. 미래 연구 방향: 덮개 시스템이 존재하지 않는 모든 $(a, b)$ 쌍에 대해 실제로 무한히 많은 소수가 존재한다는 것을 증명하는 것은 여전히 열려 있는 문제이지만, 이 논문은 그 가능성을 강력하게 지지하는 이론적, 계산적 근거를 마련했습니다.

요약하자면, 이 논문은 2 차원 덮개 시스템을 통해 $a^m - b^n$ 형태의 수가 소수를 생성하지 못하는 조건을 완벽하게 규명하고, 그렇지 않은 경우의 소수 분포에 대한 정량적 예측을 제시함으로써 정수론의 중요한 난제에 대한 획기적인 진전을 이루었습니다.