쌍둥이 소수(Twin prime)의 역수의 합의 수렴성 – Brun’s constant

이 증명은 Nathanson책[1]에 있는 내용을 나름 이해한 대로 재구성한 것이다. 이 책에서 쓰인 내용 중에서 낭비적인 계산을 고치고, 불필요한 notation을 줄였으며, 내용의 오류를 수정하여 올렸다. 그러나 책에 모두 있는 내용이니 본인의 설명이 충분치 못하다고 생각하는 분은 책을 참조하기 바란다.

 


유명한 harmonic series \sum 1/n 이 발산한다는 건 잘 알고 있을 것이다. 그 속도는 적분판정법으로 쉽게 \log n 이라는 것까지 알 수 있다.

좀 더 나아가자면 모든 소수의 역수의 합 \sum 1/p 도 생각해 볼 수 있는데, 이것 역시 엄청나게 느리지만 발산한다. 속도는 \log \log n 이다.

차가 2인 두 소수를 쌍둥이 소수(twin prime)이라고 부른다. 예를 들어 (3, 5), (5, 7), (11, 13) 이런 쌍들 말이다. 이러한 쌍둥이 소수가 무한히 많은지는 아직 증명되지 않았다. 물론 증명하면 대박이다. ㅋㅋ 그런데 이런 쌍둥이 소수의 역수의 합은 놀랍게도 수렴해서 소수와는 다르게 의외로 sparse하다는 것을 알 수 있다. 그 수렴값을 Brun’s constant라고 부른다. 근데 어떻게 증명하느냐? 그것을 한번 나름 이해한 형식으로 바꿔서 여기에 한 번 적어보겠다. 재미있게 보길 바란다. 틀린 점 지적은 환영이다.

여담이지만, 이 상수를 계산하여 펜티엄 프로세서의 버그를 찾은 적이 있다고 한다.[2] 이런 계산도 실질적인 쓸모가 있다는 거… -_-

 


0. Notation >
여기부터 별 설명이 없으면 x, y 는 양의 실수, n, m 은 자연수, p 는 소수이다. 실수에 꺾은 괄호 [x] 를 씌우면 x 를 넘지않는 최대 정수를 의미한다.

두 함수 fg 사이에 f = O(g) 라고 쓴다면 이것은 Big O notation이다. 즉 이것은 이러한 의미이다. domain안의 모든 x 에 대해 어떤 양의 상수 c 가 존재해서 다음 부등식이 성립한다.

|f(x)| \le c g(x)

먼저 Lemma 하나 증명하고 시작하겠다.

1. Lemma >
x는 1보다 큰 실수이고, p_{i_1}, \cdots p_{i_k} 는 모두 홀수 소수이다. N(i_1 , \cdots , i_k) 는 다음의 조건을 만족하는 x 이하의 자연수 n 의 개수이다.

n(n+2) \equiv 0 \pmod{p_{i_1} \cdots p_{i_k}}

그러면 N(i_1 , \cdots , i_k) 의 값은 이렇게 된다.

\displaystyle N(i_1 , \cdots , i_k) = \frac{2^k x}{p_{i_1} \cdots p_{i_k}} + 2^k \theta

여기서 \theta 는 절대값이 1이하인 어떤 적당한 상수이다.

1-1. proof of the lemma >
n(n + 2)p 의 배수이므로 n\mod p에서 0 아니면 -2이다. 게다가 둘 중 반드시 하나만 해당되어야 한다. u_1 , \cdots , u_k 가 각각 0 아니면 -2라고 하자. 어떤 자연수가 k 개의 다음 식

\begin{gathered}n \equiv u_1 \pmod{p_1} \\ \vdots \\n \equiv u_k \pmod{p_k}\end{gathered}

을 만족한다면 Chinese Remainder Theorem에 의해 \mod p_{i_1} \cdots p_{i_k} 에서 유일한 congruence class a 가 생긴다. 그래서 x 이하 에서 class a 의 개수를 세면 a 랑 상관없이 xp 들의 곱으로 나눠준 값의 몫이 된다. 즉,

\displaystyle \left[\frac{x}{p_{i_1} \cdots p_{i_k}}\right] = \frac{x}{p_{i_1} \cdots p_{i_k}} + \theta(a)

이 되고 \theta 는 당연히 정수로 만들어주기 위한 보충값.
u_i 의 선택의 여지가 2^k 가지가 있으므로 위의 해의 개수에서 2^k 를 곱하면 증명 끝.

2. direction >
만약 pp + 2 가 모두 소수라고 하자. 그러면 p 이하의 모든 소수들은 p(p + 2) 를 나누지 못한다.

그렇다면 역으로, 어떤 n 이 있는데 n 이하의 특정소수들이 n(n + 2) 를 나누지 못하는 그러한 n 의 개수는 twin prime의 쌍의 개수보다 반드시 많게 된다. 그래서 이 n 의 개수의 upper bound가 twin prime 개수의 upper bound도 된다. 이 upper bound가 비록 무한히 증가할지라도 천천히 증가한다면 그 역수의 합이 수렴하게 될 것이다.

좀 더 정형화해서 다음과 같이 써 보자.

3. Brun’s Theorem >
\pi_2(x)x 이하 자연수중에 p 도 소수이고 p+2 도 소수인 것의 개수라고 정의하면, 다음이 성립한다.

\displaystyle \pi_2 (x) = O\left(\frac{x(\log\log x)^2}{(\log x)^2}\right)

Selberg의 체를 쓰면 이보다 더 좋은 bound가 나온다. 그러나 Selberg의 체를 증명하는데 별도의 논증이 필요하고, 수렴성을 증명하는데는 이정도의 bound로도 충분하므로 그 부분은 넘어간다.

3-1. the proof of Brun’s Theorem >
5 \le y \le x 라 하고, \pi_2 (y, x)y < p \le x 이고 p, p+2 모두 소수인 p 의 개수라 하자. 쉽게 말해서 \pi_2(y, x)yx 사이의 twin prime 쌍의 개수이다.
p_1, \cdots , p_ry 를 넘지 않는 모든 홀수 소수를 나열한 것이라고 하자. 물론 r 은 그 개수가 된다.

만약 y < n \le xn 이 twin prime쌍의 작은 쪽이면, n(n + 2)p_1, \cdots , p_r 에 의해 나누어 떨어지지 않는다.
N_0(y, x)n(n + 2) 가 모든 p_i 들로 나누어 떨어지지 않는 x 이하 n 의 개수라고 정의한다.

이제 N_0(y, x) 의 bound를 계산해서 소기의 목적을 달성한다. 즉, \pi_2(x) \le y + \pi_2(y, x) \le y + N_0(y, x)

\{1, \cdots , r\} 의 부분집합인 인덱스 집합 \{i_1, \cdots , i_k \} 에 대해, N(i_1, \cdots , i_k) 를 선택된 인덱스에 해당하는 소수들의 곱으로 n(n+2) 가 나누어 떨어지는 x 이하 n 의 개수라 하자. 정의에 의해 N(1, ... , r) = N_0(y,x) 이다. Lemma에 의해

\displaystyle N(i_1 , \cdots , i_k) = \frac{2^k x}{p_{i_1} \cdots p_{i_k}} + 2^k \theta

가 성립한다.

m1 \le m \le r 인 짝수라 하자 N_0(y, x) 를 계산하는데 Inclusion-exclusion principle을 이용한다. 즉, 전체에서 소수 한개에서 n(n + 2) 가 나누어 떨어지지 않는 것을 빼고, 소수 두 개에서 더하고, 세 개에서 빼고…. 이런 식이다. 짝수 번하면 마지막에 더하므로 부등식이 성립한다.

\displaystyle \begin{aligned}N_0(y,x) &\le \sum_{k=0}^{m} (-1)^k \sum_{\{i_1, \cdots ,i_k\} \subseteq \{1, \cdots , r\}} N(i_1, \cdots , i_k) \\ & \le \sum_{k=0}^{m} (-1)^k \sum_{\{i_1, \cdots ,i_k\} \subseteq \{1, \cdots , r\}} \left(\frac{2^k x}{p_{i_1} \cdots p_{i_k}} + O(2^k) \right) \\ & \le x\sum_{k=0}^{m} \sum_{\{i_1, \cdots ,i_k\} \subseteq \{1, \cdots , r\}} \frac{(-2)^k}{p_{i_1} \cdots p_{i_k}} + \sum_{k=0}^{m} (-1)^k \binom{r}{k} O(2^k) \\ & \le x\sum_{k=0}^{r} \sum_{\{i_1, \cdots ,i_k\} \subseteq \{1, \cdots , r\}} \frac{(-2)^k}{p_{i_1} \cdots p_{i_k}}\\ &\quad - x\sum_{k=m+1}^{r} \sum_{\{i_1, \cdots ,i_k\} \subseteq \{1, \cdots , r\}} \frac{(-2)^k}{p_{i_1} \cdots p_{i_k}} + O\left(\sum_{k=0}^{m} (-1)^k \binom{r}{k} 2^k\right) \end{aligned}

여기서 항이 세 개가 나왔는데 이 각각의 bound를 따로 계산할 것이다.

3-1-1. bound of the first term >
이 부분 근방에서 Nathanson책[1]에 자세히 보면 수식에 오타가 좀 있다.

\displaystyle \begin{gathered}x\sum_{k=0}^{r} \sum_{\{i_1, \cdots ,i_k\} \subseteq \{1, \cdots , r\}} \frac{(-2)^k}{p_{i_1} \cdots p_{i_k}} \\ \quad = x\prod_{2<p\le y}\left(1-\frac{2}{p}\right) \hfill \\ \quad < x\prod_{2<p\le y}\left(1-\frac{1}{p}\right)^2 \hfill \\ \quad = O\left(\frac{x}{(\log y)^2}\right) \hfill \end{gathered}

다른 건 다 잘 나가는데 맨 마지막 줄이 문제이다. Nathanson책[1]은 좀 더 복잡하고 강한 bound를 동원해서 마지막 줄을 증명하고 있는데, 본인이 보기에는 좀 더 간단하게 증명될 듯 하다. 원래 \prod_{2\le p \le y} (1 - 1/p)^{-1}y 가 커질 수록 harmonic series랑 비슷하게 될 것인데, harmonic series가 \log n 과 비슷하게 커진다. 따라서 마지막 줄은 간단하게 big O가 성립함을 알 수 있다.

3-1-2. bound of the second term >
여기서 잠깐 Elementary symmetric polynomial에서 성립하는 부등식에 대해 살펴보자.
s_k (x_1, \cdots , x_r)r 개의 변수를 갖는 k 차 Elementary symmetric polynomial이라고 하면 변수가 모두 양수일 때 다음 부등식이 성립한다.

\displaystyle \begin{aligned} s_k (x_1, \cdots , x_r) & =  \sum_{\{i_1, \cdots ,i_k\} \subseteq \{1, \cdots , r\}} x_{i_1} , \cdots , x_{i_k} \\ & \le \frac{(x_1 + \cdots + x_r)^k}{k!} \\ & < \left(\frac{e}{k}\right)^k (x_1 + \cdots + x_r)^k \end{aligned}

두 번째 줄의 부등식이 성립하는 이유를 처음에 이해 못해서 한참 생각했다-_- 그냥 전개하면 되는 것을… ㅋㅋ Multinomial theorem때문에 coefficient가 자연스럽게 k! 이 된다. 나머지 항들이 더 있으므로 자동적으로 부등식이 성립한다. 맨 마지막 부등식이 성립하는 이유는 (k/e)^k < k! 이기 때문인데 이 이유는 책에는 설명이 없지만 Stirling’s Approximation 때문이다. 뭐 어쨌든 따라서

\displaystyle \begin{gathered} \left|x\sum_{k=m+1}^{r} \sum_{\{i_1, \cdots ,i_k\} \subseteq \{1, \cdots , r\}} \frac{(-2)^k}{p_{i_1} \cdots p_{i_k}}\right| \hfill \\ \le x \sum_{k=m+1}^{r} \sum_{\{i_1, \cdots ,i_k\} \subseteq \{1, \cdots , r\}} \frac{2^k}{p_{i_1} \cdots p_{i_k}} \hfill \\ = x \sum_{k=m+1}^{r} \sum_{\{i_1, \cdots ,i_k\} \subseteq \{1, \cdots , r\}} \left(\frac{2}{p_{i_1}}\right) \cdots \left(\frac{2}{p_{i_k}}\right) \hfill \\ < \sum_{k=m+1}^r \left(\frac{e}{k}\right)^k \left(\frac{2}{p_1} + \cdots + \frac{2}{p_r}\right)^k \hfill \\ < x\sum_{k=m+1}^r \left(\frac{2e}{m}\right)^k \left(\sum_{p\le y}\frac{1}{p}\right)^k \hfill \\ < x \sum_{k=m+1}^r \left(\frac{c\log\log y}{m}\right)^k \hfill \end{gathered}

여기서 상수 c 는 부등식이 성립하게 하는 적절한 상수이다. 책에는 별 설명이 없지만 사실 \sum 1/p 의 속도가 \log \log n 이기 때문에 마지막 부등식은 적당한 상수를 쓰면 성립할 것이다.

여기에서 처음으로 돌아가 m2c \log \log y 보다 큰 값으로 선택했다면 (물론 y 가 충분히 큰 값이어야 할 것이다) 이 마지막 식은 다음 부등식을 만족시킨다.

\displaystyle x\sum_{k=m+1}^r \left(\frac{c\log\log y}{m}\right)^k \le x\sum_{k=m+1}^r \frac{1}{2^k} < \frac{x}{2^m}

그런데 가만히 생각해보면 첫 번째 항과 두 번째 항은 괜히 나눈게 아닌가 싶기도 하다. 왠지 좀 더 연구하면 한 방에 bound를 구할 수 있을 것 같기도 하다.

3-1-3. bound of the third term >
ry 보다 작은 홀수 소수의 개수이므로 y 가 적절히 크면 2r \le y 가 성립한다. (좀 더 구체적으로, Prime number theorem에 의해서 성립한다)

\displaystyle \sum_{k=0}^m \binom{r}{k}2^k < \sum_{k=0}^m (2r)^k = O((2r)^m) \le y^m

3-1-4. aggregation of three bounds >
위 세 항의 bound를 조합하면 다음과 같은 네 개의 항이 나온다.

\displaystyle \pi_2 (x) = O\left(y + \frac{x}{(\log y)^2} + \frac{x}{2^m} + y^m\right)

첫 번째 y 항은 y^m 의 영향에 비해 미미하다. 충분히 큰 y 가 되면 Big O이므로 사라진다.

맨 처음에 가정했듯이 이 식은 5 \le y \le x 를 만족하는 ym > 2c \log \log y 를 만족하는 짝수에 대해서 항상 만족한다는 사실에 주목하자. c' = \max\{2c, (\log 2)-1\}, m = 2[c' \log \log x] 이라 두고,

\displaystyle y = \exp\left(\frac{\log x}{3c' \log\log x}\right) = x^{\frac{1}{3c'\log \log x}}

이라고 두면 충분히 큰 x 에 대해서 위 쪽의 만족해야 하는 두 부등식을 만족한다. x 가 무진장 크면 3c' \log \log x 부분을 1보다 크게 해서 yx 보다 작게 만들 수 있는 것이다. m 도 마찬가지다. 그런데 (\log 2)-1 가 어디서 나왔는지 잘 모르겠는데, 이 값 대신에 1 같은 걸로 바꿔도 내용상 별 문제가 없어 보인다. (아닌가 ㅋ) 뭐 어쨌든 y 가 저러한 값이면 \log y 의 값은 다음과 같게 된다.

\displaystyle \log y = \frac{\log x}{3c' \log \log x}

그리하여 다음과 같은 Big O 관계식을 얻게 된다.

\displaystyle \frac{x}{(\log y)^2} = O\left(\frac{x(\log\log x)^2}{(\log x)^2}\right)

이로서 두 번째 항이 해결되었다.

c' 가 1보다 크므로 m = 2[c' \log \log x] > 2c' \log \log x - 2 가 성립한다. 따라서 다음 부등식을 얻는다.

\displaystyle \frac{x}{2^m} < \frac{4x}{2^{2c'\log\log x}} = \frac{4x}{(\log x)^{2c' \log 2}} \le \frac{4x}{(\log x)^2}

이건 두 번째 항의 bound보다 작아서 죽는다. 따라서 세 번째 항도 해결된다.

마지막으로 네 번째 항은 간단한 계산을 통해 다음을 얻을 수 있다.

\displaystyle y^m \le y^{2c' \log \log x} = \exp\left(\frac{2c' \log\log x \log x}{3c' \log\log x}\right) = x^{\frac{2}{3}}

근데 이것도 두 번째 항의 bound에 못 미친다. 따라서 죽는다.

이 모든 것을 종합하면 소기의 목적을 달성한다.

\displaystyle \pi_2 (x) = O\left(\frac{x(\log\log x)^2}{(\log x)^2}\right)

사실, Selberg의 체를 쓰면 다음과 같이 더 좋은 bound를 얻을 수 있다. 본인이 알기로는 아마 twin prime의 알려진 가장 좋은 bound이다.

\displaystyle \pi_2 (x) = O\left(\frac{x}{(\log x)^2}\right)

4. Brun’s Constant >
p_1, p_2 .... 가 쌍둥이 소수의 쌍 중 작은 쪽인 수열이라 하자. 즉 p_ip_i + 2 가 모두 소수인 수열이다. (무한한지는 아무도 모르지만…)
그러면 다음 수열은 수렴한다.

\displaystyle \begin{gathered} \sum_{n=1}^{\infty}\left(\frac{1}{p_n} + \frac{1}{p_n + 2}\right) \hfill \\ = \left(\frac{1}{3} + \frac{1}{5}\right) + \left(\frac{1}{5} + \frac{1}{7}\right) + \left(\frac{1}{11} + \frac{1}{13}\right) + \left(\frac{1}{17} + \frac{1}{19}\right) \cdots\end{gathered}

4-1. proof of Brun’s theorem >
앞의 증명에 의해 2보다 큰 모든 실수 x 에 대해 다음이 성립한다.

\displaystyle \pi_2 (x) = O\left(\frac{x}{(\log x)^{3/2}}\right)

이 다음부터는 일사천리다. 2보다 큰 n 에 대해 다음이 성립하고,

\displaystyle n = \pi_2 (p_n) = O\left(\frac{p_n}{(\log p_n)^{3/2}}\right) \le O\left(\frac{p_n}{(\log n)^{3/2}}\right)

따라서 다음이 성립한다.

\displaystyle \frac{1}{p_n} = O\left(\frac{1}{n(\log n)^{3/2}}\right)

따라서 주어진 무한급수는 twin의 작은 쪽 역수를 합한 것의 2배 보다 작으므로 다음과 같이 bound를 가진다.

\displaystyle \sum_{n=1}^{\infty}\frac{1}{p_n} = \frac{1}{3} + \sum_{n=2}^{\infty}\frac{1}{p_n} = O\left(\frac{1}{3} + \sum_{n=2}^{\infty}\frac{1}{n(\log n)^{3/2}}\right)

 


[1] Melvyn B. Nathanson (1996). Additive Number Theory: the Classical Bases. Graduate Texts in Mathematics. 164. Springer-Verlag. ISBN 0-387-94656-X. p169-173
[2] Cipra, B. “How Number Theory Got the Best of the Pentium Chip”. Science 267, 175, 1995.

11 thoughts on “쌍둥이 소수(Twin prime)의 역수의 합의 수렴성 – Brun’s constant

  1. 쌍둥이 소수 역수 무한급수 수렴 증명
    너무나 궁금했는데
    어떤 책에도 없고
    어떤 사이트에도 없고
    기적적으로 여기서 발견했는데
    수학을 초전문적으로 하는 사람이 아니면
    도저히 이해할 수 없는
    난해한 수학이 사용되니까
    보는 사람으로서는 이해를 못해 답답합니다 …

    • 이 내용은 다른 수학에 비해 그나마 배경지식을 적게 요구하는 편에 속합니다. 정말 진정으로 이해하고 싶다면 수학 공부하셔야지요. 다른 방법이 없죠.

      • 저의 실력으로
        위에 있는 글을 이해한다는 것은
        도저히 무리이고
        무슨 말인지도 모르겠고
        저의 실력에 맞추어서
        묻고 싶습니다
        위의 글을 보니
        빅오 함수 이런 게 나오는 것 보니까
        쌍둥이 소수의 역수의 합을
        나타내는 함수를 만들기는 어렵고
        하니까
        쌍둥이 소수 역수의 합보다
        항상 크기가 약간 크게 나오는 함수를
        만들어서
        그 함수가 발산하지 않고 수렴하니까
        쌍둥이 소수의 역수의 합은 수렴한다 !
        아마
        이렇게 증명한 것이 아닌가 …
        제 나름대로 대략 추측을 하고 있는데
        제가
        이런 대략적인 추측은 맞게 한 건가요 ?
        좀 가르쳐 주세요
        그리고
        이 문제는
        서점이나 도서관에 있는 책들에서
        왜 안 다루나요 ?
        건강하시기 바랍니다 !

        • 1. 추측이 맞습니다.
          2. 서점이나 도서관에 있는 책들은 독자가 수학적 훈련을 받지 않았다는 가정하에서 썼기 때문이고, 제가 쓴 글은 읽는 사람이 수학적 훈련을 어느 정도 받았다는 가정하에서 쓴 글이기 떼문입니다.

          • 고맙습니다
            그 정도라도
            감을 잡으니 답답한 마음이 상당해 해소됩니다
            이런 글을 써 주셔서
            어느 정도 윤곽이라도 잡을 수 있었습니다
            님의 블로그에
            소수정리 증명한 글 두 개를 보고
            저로서는 도저히 무리인 수학영역임을 알았습니다
            앞으로
            수학에 관해 모르는 것 있으면 물어보고 싶습니다
            고맙습니다 ^_^

          • 너무 궁금해서
            서점과
            도서관의 수학책
            100 권 이상 뒤적거려도
            쌍둥이 소수 역수 수렴
            브룬상수 증명
            글 자체가 없어서 답답해서 미치겠던데
            아마
            님의 이 글이 웹사이트와 책을 통틀어
            우리나라에 유일하게
            그 문제 증명을 설명한 글이 아닐까 싶습니다
            너무 귀한 글 같습니다
            저도
            이 글 보고
            빅오함수나 뫼비우스 함수를
            약간 공부했습니다
            (님의 글을 약간이라도 이해하기 위해서 ! )
            고맙습니다 ^_^ ^-^ ^-^ ^-^

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중