소수 정리

소수 정리(Prime Number Theorem)은 정수론의 가장 유명한 정리 중 하나로, 소수의 개수에 관한 정리이다.

소수 정리란?

소수의 개별적인 분포는 상당히 불규칙하지만 소수의 전체적인 갯수는 특정한 패턴을 따른다. 소수 정리는 이러한 특정한 소수의 개수의 특별한 패턴을 보여주는 정리다. 소수 정리(Prime Number Theorem)은 특정한 자연수 이하의 소수의 개수 [math]\displaystyle{ \pi(x) }[/math]가 x값이 커짐에 따라 [math]\displaystyle{ x/\ln x }[/math]에 근사적으로 수렴한다는 것을 보인다. 또 다른 형태로는 [math]\displaystyle{ \pi(x) \sim \rm{Li} (x) = \int_2^x \frac{1}{\ln t} dt }[/math]로 로그적분함수(Logarithmic Integral Function)을 이용해서도 유도할 수 있다. 이것을 역으로 이용하면 n번째 소수 p_n에 대해서 n에 커짐에 따라 [math]\displaystyle{ p_n \sim n \ln n }[/math]에 근사적으로 다가간다는 것도 보일 수 있다.

역사

1797년에 프랑스의 수학자 아드리엔 마리 르장드르(Adrien Marie Legendre)가 소수의 개수에 관한 점근식을 [math]\displaystyle{ \pi(x) \sim x/(A \ln x+B) }[/math]로 추측했다고 전해진다. 르장드르는 1808년에 A=1, B=-1.08366으로 자신의 추측을 더 구체적으로 명시한다. 한편 카를 프리드리히 가우스(Carl Friedrich Gauss)에 따르면 자신이 15~16살 사이에 이 정리에 대한 추측을 발견했다고 서술하기도 했다.

이후 러시아의 수학자 파브누티 체비쇼프(Pafnuty L'vovich Chebyshev)는 1848년과 1850년 사이에 이 정리에 대한 증명을 시도하였다. 체비쇼프는 리만 제타 함수 ζ(s)의 성질을 이용해서 이 정리보다 약한 정리인 [math]\displaystyle{ \pi(x) \ln x /x }[/math]가 x가 무한히 커짐에 따라 특정한 상수로 수렴함을 보였다.

1859년 베른하르트 리만(Bernhard Riemann)이 자신의 유일한 논문 On the Number of Primes Less Than a Given Magnitude(특정한 숫자보다 작은 소수들의 숫자에 관해서)에서 이 소수 정리의 완전한 형태를 처음으로 증명했다. 이 증명에서는 리만제타함수를 복소평면에 확장한 함수를 이용해서 증명하였다. 1896년에는 아다마드(Jacques Hadamard)와 발레푸신(Charles Jean de la Vallée-Poussin)이 제각기 리만의 방법을 개선한 증명을 보였다. 두 정리 모두 복소해석학(Complex Analysis)적 방법을 사용하며, 리만 제타 함수 ζ(s)가 Re(s)≥1인 모든 s에 대해 (특히 Re(s)=1인 모든 s에 대해) 0이 되지 않는다는 사실을 이용해서 유도하였다.

복소해석학을 이용한 증명이 나온 한참 후에 아들레 셀베르그(Atle Selberg)와 폴 에르되시(Paul Erdös)가 1949년에 순수하게 수론적인 증명(흔히 elementary proof라고 부르는 방법)을 찾아냈으며, 1980년에는 뉴먼(Donald J Newman)이 해석학적인 방법 중 좀 더 간단한 방법을 찾았다. 2016년 현재까지 소수 정리의 증명 중 가장 간단한 방법이다.

복소해석학을 사용한 정리 증명

소수 정리는 구체적으로 증명하다보면 복잡해진다. 여기서는 증명하는 전략에 대해서만 다룰 것이다. 여기서는 필즈상 수상자인 테렌스 타오(Terence Tao)의 강의 노트에 언급한 방법을 이용한다.

1단계

우선 [math]\displaystyle{ \pi(x) }[/math]의 점근식에 대해 증명하는 대신 [math]\displaystyle{ \psi(x) = \sum_{p^k \le x, \atop p \, \text{is prime}} \ln p. }[/math]로 정의되는 체비세브 함수(Chevychev Function)</math>가 y=x에 근사적으로 접근한다는 것을 보일 것이다. 즉, [math]\displaystyle{ \lim_{x \to \infty} {\frac{\psi (x)}{x}} = 1 }[/math]을 보이면 충분하다. 우선

[math]\displaystyle{ \psi(x) = \sum_{p\le x} \ln p \left\lfloor \frac{\ln x}{\ln p} \right\rfloor \le \sum_{p\le x} \log x = \pi(x)\ln x }[/math] 따라서 [math]\displaystyle{ 1 \le { \lim \inf}_{x \to \infty} \frac{\pi(x) \ln x}{\psi(x)} }[/math]

한편 big O notation을 이용해서 [math]\displaystyle{ \varepsilon \gt 0 }[/math]가 성립할 때

[math]\displaystyle{ \psi(x) \ge \sum_{x^{1-\varepsilon}\le p\le x} \ln p\ge\sum_{x^{1-\varepsilon}\le p\le x}(1-\varepsilon)\ln x=(1-\varepsilon)(\pi(x)+O(x^{1-\varepsilon}))\ln x. }[/math]. 따라서 임의의 작은 [math]\displaystyle{ \eta, \varepsilon \gt 0 }[/math]. [math]\displaystyle{ {\lim \sup}_{x \to \infty} \left| \frac{\psi(x) - (1-\varepsilon) \pi(x)}{x} \right| \lt \eta }[/math]가 성립한다. 즉 [math]\displaystyle{ \lim_{x \to \infty} \frac{ \pi(x) \ln x - \psi(x)}{x} =0 }[/math]이고, [math]\displaystyle{ \lim_{x \to \infty}\frac{\pi(x) \ln x}{x} =1 \Leftrightarrow \lim_{x \to \infty}\frac{\psi(x)}{x} =1 }[/math].

폰 망골트 함수(von Mangoldt Function)는 [math]\displaystyle{ \Lambda (n) = \begin{cases} \ln n & n~ \rm{prime} \\ 0 & n=1 ~ or ~ n ~\rm{composite} \end{cases} }[/math]로 정의되고, 한편 μ(n)이 뫼비우스 함수(Mōbius Function)일 때 [math]\displaystyle{ \Lambda(n)= \sum_{d|n} \mu(d) \ln (n/d) }[/math],

이 때 [math]\displaystyle{ \frac{\zeta'(s)}{\zeta(s)} = -\sum_{n=1}^{\infty} \Lambda(n) n^{-s} }[/math].

아래의 페론의 정리(Perron's Theorem)을 사용하면 정수가 아닌 [math]\displaystyle{ x }[/math], [math]\displaystyle{ c\gt 1 }[/math]에 대해 (x가 정수일 때까지 감안한다면 [math]\displaystyle{ \psi_0 = \lim_{h \to 0}{\psi(x+h)+\psi(x-h)}/2 }[/math]를 이용하면 된다. 오직 x가 소수의 k제곱수일 때에만 값이 달라진다.)

페론의 정리(Perron's Theorem) 정수 함수 [math]\displaystyle{ \{a(n)\} }[/math]와 그것으로 유도되는 디레클레 급수 [math]\displaystyle{ g(s){{=}}\sum_{n{{=}}1}^{\infty} \frac{a(n)}{n^s} }[/math]에 대해서 이 급수가 특정한 실수 s0에 대해 [math]\displaystyle{ \Re (s) \gt s_0 }[/math]가 성립하면 실수 x, c>s0에 대해서 [math]\displaystyle{ A(x){{=}}\sum_{n \le x} ' a(n) {{=}} \int_{c-i \cdot \infty}^{c+ i \cdot \infty} g(z) \frac{x^z}{z} dz }[/math] 여기서 시그마 기호의 프라임 표시는 x가 정수일 때는 마지막 항 a(n)의 1/2를 더하라는 의미이다.

[math]\displaystyle{ \psi(x) = \sum_{n \le x} \Lambda (n) = {\frac{1}{2 \pi i}} \int_{c-i \cdot \infty}^{c+ i \cdot \infty} \left( - \frac{\zeta ' (z) }{\zeta (z)} \right) \frac{x^z}{z} dz }[/math]

2단계

이제 [math]\displaystyle{ \psi(x)= x-\sum_{\rho}{\rm{Res}}_{s=\rho} \frac{\zeta'(s)}{\zeta(s)}{x^{\rho}} }[/math]임을 보인다.

우선 [math]\displaystyle{ \zeta(s) = \prod_{p~ \rm{prime}} \frac{1}{1-p^{-s}}, \Re(s)\gt 1, \xi(s)= \pi^{-s/2}\Gamma(s/2)\zeta(s) }[/math]에서 [math]\displaystyle{ \xi(s) }[/math]는 s=0, 1에서 극점을 갖는 유리형 함수(meromorphic)이면서 [math]\displaystyle{ \xi(s)=\xi(1-s) }[/math]를 만족한다. 구체적으로 세타함수를 [math]\displaystyle{ \vartheta(u)=\sum_{n=-\infty}^{\infty} e^{-\pi n^2 u} }[/math]와 같이 정의하면 [math]\displaystyle{ \xi(s) = \int_{1}^{\infty} \left( u^{-s/2-1/2}+u^{s/2-1} \right) \psi(u) du - \frac{1}{s}-\frac{1}{1-s} }[/math]

증명하기 추가 예정

■

따라서 [math]\displaystyle{ \zeta(s) }[/math]는 복소수 [math]\displaystyle{ \mathbb{C} }[/math]에 대해서 s=1에서만 극점을 가진 유리형 함수(meromorphic function)가 된다. 또한 제타함수의 [math]\displaystyle{ (s-1)\zeta(s) }[/math]가 복소수 전체에서 정칙함수(holomorphic)이고, 차수(growth order)가 1이므로 바이에스트라스의 곱정리(Weierstrass product theorem)을 이용하면 제타함수의 비자명근(nontrivial root) ρ에 대해서(참고로 제타함수는 자명근 n=-2, -4, -6, …을 가진다.)

바이에스테라스의 곱정리(Weierstrass product theorem) 

복소수 [math]\displaystyle{ \mathbb{C} }[/math] 전체에서 정칙인 함수(entire funciton) f(z)의 차수(growth order, 충분히 절대값이 큰 z에 대해서 [math]\displaystyle{ |f(z)| \le A {\rm{exp}}(B|z|^{\rho}) }[/math]를 만족하는 최소 ρ)를 [math]\displaystyle{ \rho_0 }[/math]라고 놓자. 이때 m을 z=0에서의 f의 영점의 차수(f(z)=0일 때만, f(z)≠0이면 m=0), [math]\displaystyle{ a_1 , a_2 , \cdot\cdot\cdot a_n, \cdot\cdot\cdot }[/math]를 f의 0 아닌 근(중근일 경우 차수만큼 a_i를 중복해서 쓴다.)이라고 가정하자. [math]\displaystyle{ k \le rho_0 \le k+1 }[/math]를 만족하는 k와 초등인수 [math]\displaystyle{ E_k (z)= (1-z) {\rm{exp}}(z+{z^2}/2+\cdot\cdot\cdot+{z^k}/k) }[/math], 차수가 k 이하인 P(z)에 대해서 [math]\displaystyle{ f(z)=e^{P(z)}z^m \prod_{n=1}^{\infty}E_k(z/a_n) }[/math]

■γ

[math]\displaystyle{ (s-1)\zeta(s)=e^{a+bs}\prod_{n=1}^{\infty}(1+s/2n)e^{-s/2n} \prod_{\rho} (1-z/\rho)e^{z/\rho} }[/math]

여기서 제타함수의 곱셈식 [math]\displaystyle{ \zeta(s)=\prod_{p} \frac{1}{1-p^{-s}} }[/math]를 이용해서 [math]\displaystyle{ \zeta'(s)/\zeta(s)=-\prod_{p} {-\ln p}p^{-ms}=b-\frac{1}{s-1}- \sum_{n=1}^{\infty}\frac{s}{2n(s+2n)} +\sum_{\rho} \frac{s}{\rho(s-\rho)} }[/math] 이 식에서 s=0을 대입하면 [math]\displaystyle{ b+1=\zeta'(0)/\zeta(0) }[/math]이므로, [math]\displaystyle{ \Re(s)\gt 0 }[/math]에 대해서
[math]\displaystyle{ - \frac{\zeta'(s)}{\zeta(s)}=\sum_{p} \ln p \cdot p^{-ms} = \frac{s}{s-1} - \frac{\zeta'(0)}{\zeta(0)}+\sum_{n=1}^{\infty}\frac{s}{2n(s+2n)} -\sum_{\rho} \frac{s}{\rho(s-\rho)} }[/math].

한편 [math]\displaystyle{ \psi(x) = {\frac{1}{2 \pi i}} \int_{c-i \cdot \infty}^{c+ i \cdot \infty} \left( - \frac{\zeta ' (z) }{\zeta (z)} \right) \frac{x^z}{z} dz }[/math]에서 이 식은

[math]\displaystyle{ \frac{1}{2 \pi i} \int_{c-i \cdot \infty}^{c+ i \cdot \infty} \left( \frac{s}{s-1} - \frac{\zeta'(0)}{\zeta(0)}+\sum_{n=1}^{\infty}\frac{s}{2n(s+2n)} -\sum_{\rho} \frac{s}{\rho(s-\rho)} \right) \frac{x^z}{z} dz }[/math]

여수 정리(Residue Theorem)를 활용하면 위의 식은 [math]\displaystyle{ s-\sum_{\rho} x^{\rho}/\rho - \zeta'(0)/\zeta(0) - 1/2 \sum_{n=1}^{\infty} s^{-2n}/n }[/math]으로 증명된다.

3단계

이제 제타함수 ζ(s)의 근 ρ에 대해 실수부 Re(ρ)<1인 것을 보여서 충분히 큰 s에 대해 ψ(s)~s임을 보인다. 참고로 리만 가설(Riemann Hypothesis)은 좀 더 강한 가설로 이 제타함수의 비자명근의 실수부가 1/2밖에 없다는 것에 대한 추측이다. 우선 실수 x에 대해서 [math]\displaystyle{ x^{a+bi} = x^a \cdot e^{\ln x \cdot bi} }[/math]이므로 허수 지수는 x^s의 절대값의 크기를 변화시키지 않는다. 따라서 충분히 큰 x에 대해서 x에 비해 작은 값으로 나타나게 된다.

우선 [math]\displaystyle{ \Re (s) \gt 1 }[/math]인 경우를 보면 [math]\displaystyle{ \zeta(s)= \prod_{p} \frac{1}{1-p^{-s}} }[/math]와 같이 수렴하는 곱셈식으로 표현할 수 있다. 각각의 곱셈을 이루는 식이 0이 되지 않으므로 따라서 자명하게 ζ(s)가 0이 되지 않는다.

이제 Re(s)=1, s≠1 에 대해서 ζ(s)가 0이 되지 않음을 보일 것이다. 우선 우리는 [math]\displaystyle{ 3+4 \cos \theta + cos 2\theta = 2(1+\cos \theta)^2 \ge 0 }[/math]임을 확인할 수 있다. 여기서 우리는 σ>1, 실수 t에서 [math]\displaystyle{ ln| \zeta^3 (\sigma) \zeta^4 (\sigma + it) \zeta (\sigma + 2 it)| \ge 0 }[/math]임을 확인할 수 있다.

우선 [math]\displaystyle{ \Re (n^{-\sigma - it}) = \Re (e^{-(\sigma+it) \ln n}) = n^{-\sigma} \cos (t \ln n) }[/math]이므로
[math]\displaystyle{ ln| \zeta^3 (\sigma) \zeta^4 (\sigma + it) \zeta (\sigma + 2 it)| = 3 \Re [\ln \zeta(\sigma)] + 4 \Re [\ln (\zeta(\sigma + it))]+ \Re [\ln (\zeta (\sigma + 2it))] }[/math] 여기서 [math]\displaystyle{ \ln [\zeta(s)]= \sum_n {c_n n^{-s}}, ~ c_n=\begin{cases} 1/m & n=p^r \\ 0 & n \neq p^r \end{cases} }[/math]를 이용하면

[math]\displaystyle{ =\sum_n c_n n^{-\sigma}[3+ 4 \cos (t \ln n) + \cos 2(t \ln n)] }[/math] 당연히 c_n와 대괄호 안의 부분은 0 이상이기에 전체 식도 0 이상이 된다. 따라서 위의 식이 성립한다.

이제 [math]\displaystyle{ \zeta(1+ it_0) = 0 }[/math]을 만족하는 t₀의 존재가 있다는 가정을 한 뒤에 모순을 이끌어내자. 우선 1+it₀에서 함수 ζ(s)가 정칙이므로 σ→1로 접근함에 따라 [math]\displaystyle{ {|\zeta (\sigma + it_0 )|}^4 \le C(\sigma -1)^4 }[/math]를 만족하게 하는 상수 C>0를 찾을 수 있다. 한편 σ=1에서는 ζ(s)가 1차원 극점이기에 상수 D>0에 대해서 [math]\displaystyle{ |\zeta(\sigma)|^3 \le D (\sigma -1)^{-3} }[/math]를 만족한다. 또한 ζ가 [math]\displaystyle{ \sigma + 2it_0 }[/math]에서도 정칙이기에 특정한 값이 존재한다. 따라서 σ→1로 감에 따라 [math]\displaystyle{ |\zeta^3 (\sigma) \zeta^4 (\sigma + it) \zeta (\sigma + 2it)| \le CD|\zeta(\sigma + 2it)|(\sigma-1) }[/math]가 성립하므로 0으로 간다. 결과적으로 위의 결과와 모순되므로 [math]\displaystyle{ \zeta(1+ it_0) = 0 }[/math]는 성립하지 않게 된다.

위의 1, 2, 3단계를 종합하면 x가 커짐에 따라 [math]\displaystyle{ \psi (x) \sim x }[/math]임이 증명되고, 따라서 [math]\displaystyle{ \pi (x) \sim \frac{x}{\ln x} }[/math]임이 증명된다.

여담

Tom Apostol의 Analytic Number Theorey에서는 직접 체비쇼브 함수 ψ(s)에 대해 구하는 대신 적분함수 [math]\displaystyle{ \psi_1 (s)=\int_{0}^{x} \psi(u) du \sim s^2 /2 }[/math]임을 보여서 증명하였다. 이 경우에는 위의 페론의 정리를 쓰지 않고 적분공식 [math]\displaystyle{ \int_{c-i \cdot \infty}^{c+i \cdot \infty} \frac{x^s}{s(s+1)}ds = \begin{cases} 0 & 0\lt a \le 1 \\ 1-1/a & 1 \le a \end{cases} }[/math]과 [math]\displaystyle{ \psi_1 (x) = \sum_{n\le x} \Lambda(n) (x-n) }[/math]를 이용해서 [math]\displaystyle{ \psi_1 (x) = \frac{1}{2\pi i} \int_{c-i \infty}^{c+ i \infty} \frac{x^{s+1}}{s(s+1)} \left( \frac{\zeta'(s)}{\zeta(s)}\right) ds }[/math]인 사실, 또한 이것을 이용해서 [math]\displaystyle{ \frac{\psi_1 (x)}{x^2}- 1/2{\left(1-1/x \right)}^2 =\frac{1}{2\pi i} \int_{c-i \infty}^{c+ i \infty} \frac{x^{s-1}}{s(s+1)} \left( - \frac{\zeta'(s)}{\zeta(s)}-\frac{1}{s-1} \right)ds }[/math](1)임을 증명한다. 그 다음에 σ≥1, 실수 t에 대해 [math]\displaystyle{ \zeta(\sigma+it) \neq 0 }[/math]임을 확인한 후에 충분히 큰 실수 t에 대해서 [math]\displaystyle{ \left| \frac{\zeta'(1+it)}{\zeta(1+it)}\right| \leq M {(\ln t)}^9 }[/math]임을 통해서 적분(1)이 x가 커짐에 따라 수렴함을 보이면서 [math]\displaystyle{ \psi_1 (x) \sim x^2 /2 }[/math]임을 보일 수 있다.

Li(x)와 관계

로그적분 함수 [math]\displaystyle{ {\rm{Li}}(x)= \int_{2}^{\infty} \{1}{￦ln u} du }[/math] 에 대해서 [math]\displaystyle{ \pi(x) \sim {\rm{Li}}(x) }[/math]가 성립한다.

두 함수간의 오차는 대략

[math]\displaystyle{ \pi(x)=\operatorname{Li} (x) + O \left(x \, \exp \left( -\frac{A(\log x)^{3/5}}{(\log \log x)^{1/5}} \right) \right). }[/math]

이 정도로 알려져 있으나 리만 가설(Riemann Hypothesis)이 참이라는 전제하에서는 x>2637에 대해

[math]\displaystyle{ |\pi(x)- \operatorname{li}(x)|\lt \frac{\sqrt x\,\log x}{8\pi} }[/math]인 것이 알려져 있다.

두 함수의 크기를 비교할 경우 Li(x)>π(x)로 알려져 있고 실제로도 "거의 모든 x에 대해" 성립한다. 그러나 100% 맞지는 아닌데 영국의 수학자 리틀우드가 Li(x)<π(x)인 x가 존재함을 증명했다.

초등적인 증명

노버트 위너 타베리안 정리(Wiener's Tauberian Theorem, wikipedia:Wiener's tauberian theorem 참조)가 증명되면서 초등적인 증명의 단서가 열렸다. 이후에 셀베르그와 에르되시가 1949년에 소수 정리의 초등적인 증명을 발견했다.

보통 "초등적 증명(elementary proof)"은 페아노 공리계(Peano Arithmetic)에서 1차 논리 사용할 수 있는 만을 이용해서 증명할 수 있는 것을 말한다. 쉽게 말하면 미적분적인 요소 등을 사용하지 않고 오로지 정수 함수와 사칙연산에 기초한 방법을 이용한 것이다.

자세한 증명은 이곳에 나와있다. 여기서는 이 증명법이 어떠한 아이디어를 이용하는지만 설명할 것이다.

간단한 증명 과정 요약

추가예정

참조

• wikipedia:Prime Number Theorem
• Elias M Stein, Rami Shakarchi, 《Complex Analysis》 2th editoin, Princeton University, 2002