소수정리의 증명 : part 1 물밑작업

정수론의 로망이라고 할 수 있는 소수 정리 (Prime number theorem)에 대해서 들어본 적이 있으신지? 주어진 값 이하의 소수 개수가 대충 x/\log x 와 비슷해진다는 정리이다. 좀 더 뽀대나게 써 보면 이렇다.

\displaystyle \lim_{x \to \infty} \frac{\pi(x)\log x}{x} = 1

여기서 \pi(x) 는 원주율의 의미가 아니고, 주어진 양의 실수 x 이하의 모든 소수의 개수로 정의되는 함수이다. 이것이 이번 증명의 목표가 되겠다.

이를테면 1억 이하의 소수의 개수는 5,761,455개인데, 100000000/log 100000000 의 값은 약 5,428,681.02 이므로 얼추 비슷해보인다.

이 소수 정리를 증명하려고 수학자들이 고생 좀 했는데, 결국 증명되긴 했지만, 이걸 증명하려다 리만 가설도 나오고 뭐 이런 저런 복잡한 스토리도 나오고 하니 정수론에 있어서 매우 중요하게 여기는 정리 중의 하나임에는 틀림없다. 그 긴 스토리는 이래저래 많이 있으니 읽어보시라.

수학자들이 처음에는 이걸 복소함수론을 써서 증명했다가 나중에는 복소함수를 쓰지 않고 증명하는데 성공하였다. 전자의 증명을 해석적 증명(analytic proof)이라 하고 후자의 증명을 초등적 증명(elementary proof)이라 하는데 ‘초등적(elementary)‘이라는 단어의 의미는 복소함수가 없다는 뜻이지, 절대 쉽다는 뜻이 아니다. 낚이지 마시길 ㅋㅋㅋ

일단 이 포스트에서는 그 두 증명을 하는데 있어 공통으로 필요한 정리를 먼저 증명하고, 두 증명을 따로 해보겠다. 여기서 소개한 정리의 내용은 해석적 증명의 경우 [1], [2], [3]을 주로 참조하였고, 초등적 증명의 경우는 [4], [5], [6]을 주로 참조하였다. 여기서의 설명이 불만족스러운 분들은 원본 책을 읽어보시길 바란다.

 


0. notation >
여기서부터 별 말이 없으면 소문자 p 는 소수, 대문자 P 는 소수 전체의 집합, n m 은 자연수, x y 는 양의 실수를 의미한다.

꺾은 괄호는 넘지 않는 최대의 정수를 의미한다. 예를 들어 [4.545] = 4 가 된다.

수론적 함수(arithmetic function)란 정의역이 자연수 집합이고 공역이 복소수 집합인 함수를 말한다. 다시 말해서 그냥 수열이다.

e_1 (n) 은 함수에 1을 대입할 때만 값이 1이 되고 나머지 값에 대해서는 0 이 되는 arithmetic function이다.

총합을 의미하는 대문자 시그마 기호(∑) 아래에 조건이 있으면 그 조건에 해당하는 모든 경우를 대입한 합을 의미한다. 이를테면

\displaystyle \sum_{n \le x}n = \frac{[x]([x]+1)}{2}

이 되는 것이다. 전통적인 방법인 아래에 k = 1 과 위쪽에 n 을 쓴 표현을 사용할 수도 있지만, 위와 같은 방법의 장점은 실수 변수에 대한 총합이 가능하다는 점이다.

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

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

1. definition > some basic functions
\pi(x)x 이하 소수의 개수를 의미한다. 예를 들어 \pi(5.34) = 3 이 된다. Prime-counting function이라고 부른다.

\Lambda(n)n 이 어떤 소수의 거듭제곱이 되는 경우, 즉 n = p^m 이면 \log p가 되고, 나머지 경우에는 0 이 되는 함수이다. Mangoldt function이라고 부른다.

\vartheta(x)x 이하의 모든 소수에 대해 그 로그값을 더한 것이다. 즉,

\displaystyle \vartheta(n) = \sum_{p \le x}\log p

x 가 2보다 작으면 값은 0 이 된다. 책에 따라서 그냥 \theta 로 표시하기도 한다. Chebyshev ϑ-function이라고 부른다.

\psi(x)x 이하의 \Lambda(n) 값을 모두 더한 것이다. 즉,

\displaystyle \psi(x) = \sum_{n \le x}\Lambda (x)

바로 위의 \vartheta 함수랑 비슷한데, \vartheta 함수는 소수에 대해 로그를 더하는 것이고, 이건 소수와 소수의 거듭제곱까지 로그를 더하는 것이다. 마찬가지로 Chebyshev ψ-function이라고 부른다.

2. theorem > \vartheta(x)\psi(x) 의 관계 1
다음 등식이 성립한다.

\displaystyle \psi(x) = \sum_{m \le \log_2 x}\vartheta(x^{\frac{1}{m}})

2-1. proof of theorem 2>
이건 가만히 생각해보면 별로 어렵지 않게 증명이 가능한데, 비주얼하게 증명하자면 삼각형 모양으로 소수의 거듭제곱들을 늘어놓고 세로로 더하는 거랑 가로로 더하는 거랑 같다는 걸로 쉽게 증명이 된다.

좀더 자세히 설명하자면 \Lambda(n) 이 소수의 거듭제곱에서만 값을 가지는데, \vartheta(x) 함수로 n 이하의 소수에 대해 로그값을 더하고, x에 거듭제곱을 취해서, 또 소수에 대해 로그값을 더하고…. 이런 작업을 반복하는 것이다. 2 아래로는 소수가 더 이상 없으므로 x의 m제곱근이 2 아래로 줄어들 때 까지 계산이 반복된다. 즉 x^{1/m} \ge 2 인 동안 계산이 진행되므로 양변에 로그를 씌우면 m \le \log_2{x} 가 된다. 식을 안 쓰고 말로 때우니 포스팅이 쉽군-_-

3. theorem > \vartheta(x)\psi(x) 의 관계 2
다음 등식이 성립한다.

\displaystyle \psi(x) = \vartheta(x) + O(\sqrt{x}\log^2 x)

그러므로 다음과 같다.

\displaystyle \lim_{x \to \infty}\left(\frac{\psi(x)}{x} -\frac{\vartheta(x)}{x}\right) = 0

3-1. proof of theorem 3>
위의 정리에 의해 두 함수의 차이는 다음과 같게 된다.

\displaystyle 0 \le \psi(x)-\vartheta(x) = \sum_{2 \le m \le \log_2 x}\vartheta(x^{\frac{1}{m}})

근데 x 이하의 모든 소수를 곱한 것보다 x^x 이 당연히 더 크다. 따라서 \vartheta(x) \le x \log x 가 성립한다. 그러므로

\displaystyle \begin{gathered}0 \le \psi(x) - \vartheta(x)  = \sum_{2 \le m \le \log_2 x} \vartheta(x^{\frac{1}{m}})  \le \sum_{2 \le m \le \log_2 x} x^{\frac{1}{m}} \log(x^{\frac{1}{m}}) \hfill\\ \quad \le (\log_2 x) \sqrt{x} \log \sqrt{x} = \frac{\log x}{\log 2}\cdot \frac{\sqrt{x}}{2}\log x = \frac{\sqrt{x}(\log x)^2}{2\log 2}\hfill \end{gathered}

이 식은 x보다 커지는 속도가 느리다. 부등식의 양변을 x 로 나눈 식은 x 가 커지면 0 에 수렴한다.

4. theorem > summation by parts
f(x) 는 구간 [y, x] 에서 continuously differentiable(C^1)하다고 하자. 즉, 미분이 되고 그 미분한 게 연속이다. 어떤 수론적 함수 a(n)에 대하여 A(x)를 다음으로 정의하자.

\displaystyle A(x) = \sum_{n \le x}a(n)

단, x가 1보다 작으면 A(x) = 0 이 된다. 그러면 다음 등식이 성립한다.

\displaystyle \sum_{y < n \le x}a(n)f(n) = A(x)f(x) - A(y)f(y) - \int_y^x A(t)f'(t) dt

왜 이런 수론적 함수에 대한 일반론적인 정리를 꺼내냐 하면, 이 정리를 컴퓨터 프로그램의 서브루틴처럼 두 번 써먹기 때문이다. 원래는 구체적인 함수를 넣어서 증명 안으로 녹이려고 했는데, 이 편이 더 쉬운 것 같다. 증명은 별도의 포스트가 있으니 참조하기 바란다.

5. theorem >
\lim_{x \to \infty}\frac{\psi(x)}{x}=1 이면 \lim_{x \to \infty}\frac{\pi(x)\log x}{x}=1 이다.

5-1. proof of theorem 5>
위의 summation by parts에 n 에 소수 p 를 대입할 때만 함수값이 \log p 가 되는 함수를 a(n) , f(x) = 1/\log x , 구간 [3/2, x] 을 대입한다.
그러므로 x 이하의 자연수에 대해 a(n) 을 모두 더하면 \vartheta(x) 가 된다. 따라서 \vartheta(x) = A(x) 가 된다. 그러면 위 summation by parts는 다음과 같이 변한다.

\displaystyle \pi(x) = \sum_{3/2 < n \le x}a(n)\frac{1}{\log n} = \frac{\vartheta(x)}{\log x}-\frac{\vartheta(3/2)}{\log 3/2}+\int_{3/2}^x \frac{\vartheta(t)}{t \log^2 t}dt

근데 \vartheta(x) 는 2보다 작을 때는 죽는다. 따라서 가운데 항이 사라진다. 양변에 \log x/x 를 곱하면

\displaystyle \frac{\pi(x)\log x}{x}=\frac{\vartheta(x)}{x}+\frac{\log x}{x}\int_2^x \frac{\vartheta(t)}{t \log^2 t}dt

3번 정리에 의해 \lim \psi(x)/x = 1 이면 \lim \vartheta(x)/x = 1 이 된다. 따라서 이제 x가 커지면 뒤쪽 적분항이 죽는다는 걸 보이면 증명이 된다.

\lim \vartheta(x)/x = 1 이면 \vartheta(t) = O(t) 이다. 따라서

\displaystyle \frac{\log x}{x}\int_2^x \frac{\vartheta(t)dt}{t \log^2 t} = O\left(\frac{\log x}{x}\int_2^x \frac{dt}{\log^2 t}\right)

이다. 1/\log^2 t 가 문제인데 책에서는 구간을 두 개로 쪼개서 0 으로 사라짐을 증명했다. 계산이 번거로와서 적분을 통째로 없애보려 했는데, 함수의 속도가 미묘해서 통째로는 0으로 죽는다는게 잘 증명이 안 되었다-_- 뭐 어쨌든 책의 방법을 따라가자.

주어진 구간에서 1/\log^2 t 는 감소함수이므로

\displaystyle \int_2^x \frac{dt}{\log^2 t}=\int_2^{\sqrt{x}}\frac{dt}{\log^2 t}+\int_{\sqrt{x}}^x \frac{dt}{\log^2 t} \le \frac{\sqrt{x}}{\log^2 2}+\frac{x-\sqrt{x}}{\log^2 \sqrt{x}}

이다. 그래서 결국 x 를 극한으로 보내면 마지막 텀이 사라지므로 위의 정리가 성립함을 알 수 있다.

6. direction >
결국 소수정리를 증명하기 위해서는

\displaystyle \lim_{x \to \infty}\frac{\psi(x)}{x} =1

위 극한을 증명해야 하는 것임을 알 수 있다. 초등적 증명이든 해석적 증명이든 위 극한을 증명하여서 결국 문제를 해결하게 된다.

 


[1] Tom M. Apostol, Introduction to analytic number theory 1권, Springer, 1998
[2] G. J. O. Jameson, The Prime Number Theorem, Cambridge University Press (2003)
[3] Maruti Ram Murty, Problems in analytic number theory, Springer (2000)
[4] Harold G. Diamond, “Elementary Methods in the Study of the Distribution of Prime Numbers”, Bull. Amer. Math. Soc. (N.S.) Volume 7, Number 3 (1982), 553-589.
[5] N Levinson, “A Motivated Account of an Elementary Proof of the Prime Number Theorem”, American Math. Monthly 76 (1969), 225-245.
[6] M. B. Nathanson, Elementary Methods in Number Theory, Springer (2000)

2 thoughts on “소수정리의 증명 : part 1 물밑작업

  1. \vartheta 함수는 소수에 대해 로그를 더하는 것이고, 이건 소수의 거듭제곱만 로그를 더하는 것이다.”

    이 문장때문에 좀 헷갈렸네요….. “이건 소수와 소수의 거듭제곱까지 로그를 더하는 것이다” 가 명확한 표현이 아닐까요?

답글 남기기

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

WordPress.com 로고

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

Twitter 사진

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

Facebook 사진

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

Google+ photo

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

%s에 연결하는 중