소수 정리
素數定理 / Prime Number Theorem
1. 개요
어떤 양수 이하의 소수가 몇 개나 있는지 그 값을 어림해주는 정리. 어떤 양수 $$x$$에 대해 $$x$$보다 작은 소수의 개수는 대략 $$\displaystyle \frac{x}{\log x}$$개가 있다고 주장하는 정리이다.[1] 정확히 말하면, $$x$$ 이하의 소수의 개수를 $$\pi\left(x\right)$$라고 할 때,[2] $$\displaystyle \lim_{x \to \infty}\frac{\pi\left(x\right)\log x}{x}=1$$이라는 것이다.
19세기 정수론의 최종보스라고 언급되어 있지만, 사실 20세기를 넘어 21세기에서도 별반 다르지 않다. 왜냐면, 이를 파고들면 결국에는 21세기의 최종보스로 연결되기 때문이다.
2. 역사
흔히 천재 수학자 카를 프리드리히 가우스가 제시했다고 알려져 있는데, 가우스가 소수 정리를 먼저 생각하고 연구하긴 했지만, 실제로 소수 정리를 먼저 발표한 사람은 르장드르이다. 가우스는 1792년과 1793년 사이에 소수를 하루에 '''1000개씩, 그것도 15분만에 직접 손으로''' 찾아가면서, 소수의 빈도수가 평균적으로 로그함수에 반비례한다는 것을 알아냈다[3]. 하지만 발표는 하지 않았는데, 이는 가우스가 자신의 연구 성과를 잘 발표하지 않거나 느리게 발표하는 성향이 있어서이기도 했고, 그 당시 가우스가 겨우 '''15살'''(...)이었던 것도 있다.
그 후 1798년, 아드리앵 마리 르장드르는 ‘정수론에 관한 소고’라는 제목으로 책을 한 권 출판했는데, 이 책에서 르장드르는 적당한 상수 $$A$$에 대해 다음 식이 성립한다고 추측했다.
$$\displaystyle \pi \left(x\right) \sim\frac{x}{\log x -A} $$
여기서 $$\sim$$는 양변의 비가 $$x$$가 무한대로 갈수록 1로 수렴한다는 뜻이다. 또한 그는 $$A$$가 대략 1.08366일 것이라고 예상했는데, 이는 지금 쓰이고 있는 것과는 표현이 조금 다르나 하지만 결국 동치이다.
이후, 러시아 수학자 파프누티 체비쇼프는 소수 정리에 관해서 다음과 같은 사실을 증명하였다.
- 어떤 상수 $$B$$에 대해, $$\displaystyle \lim_{x \to \infty}\frac{\pi\left(x\right)\log x}{x}=B$$라면 $$B=1$$이 성립한다.[4]
- $$\displaystyle \theta\left(x\right)=\sum_{p \le x} \log p \quad (p \in \mathbb{P})$$ [5][6]
- $$\displaystyle \psi\left(x\right)=\sum_{p^k \le x} \log p \quad (p \in \mathbb{P})$$ [7]
- $$\displaystyle \lim_{x \to \infty}\frac{\pi\left(x\right)\log x}{x}=1$$
- $$\displaystyle \lim_{x \to \infty}\frac{\theta\left(x\right)}{x}=1$$
- $$\displaystyle \lim_{x \to \infty}\frac{\psi\left(x\right)}{x}=1$$
체비쇼프가 소수 정리에 관해서 비약적인 발전을 이루었지만, 체비쇼프의 방법으로 증명하기에 소수 정리는 너무 막강한 적이었다. 이때, 정수론에서 가장 중요한 무기 중 하나이며 150년이 지난 지금까지 최전방에서 무기로 사용되고 있는 방법론을 제시한 사람이 바로 베른하르트 리만이다.
리만은 1859년 베를린학술원에 가입하면서 관례에 따라 논문 한 편을 제출하였는데, 이 논문이 바로 이후 정수론의 역사에 지대한 영향을 미친 <주어진 수보다 작은 소수의 개수에 관하여>였다. 이 논문에서 리만은 그의 제타 함수를 소개하고, ‘실수부가 1 이상’이라는 제한 조건이 붙여 있었던 함수를 확장시켜[8] 1이 아닌 모든 복소수에 대해 정의하였다. 또한, 놀랍게도 리만은 이 함수의 해를 소수세기함수와 연관시켰다!
이에 대해 조금 살펴보면, 리만은 다음과 같은 함수를 정의하였다.
- $$\displaystyle f\left(x\right)=\sum_{i=1}^{\infty}\frac{1}{i}\pi\left(x^{1/i}\right)$$
- $$\displaystyle f\left(x\right)=\text{li}\left(x\right)-\sum_{\rho}\text{li}\left(x^{\rho}\right)-\log 2+\int_{x}^{\infty}\frac{dt}{t\left(t^2-1\right)\log t}$$
- $$\displaystyle \pi_0\left(x\right)=\sum_{n=1}^{\infty}\frac{\mu\left(n\right)f\left(x^{1/n}\right)}{n}$$
실제로 리만은 리만 제타 함수의 비자명근의 실수부가 모두 $$\frac{1}{2}$$이라면 소수 정리가 성립함을 보였는데, 이것이 그 유명한 리만 가설이다. 그 이후로 소수 정리를 연구하는 수학자들은 리만 가설을 공략하기 시작했고, 모두들 알듯 그 결과는....
그 이후, 1895년, 독일의 수학자 한스 폰 망골트는 리만의 방법론을 체비쇼프 프사이 함수에 적용해서, 망골트근사식(Mangoldt Explicit Formula)를 만들었는데, 망골트는 이 근사식을 이용해서 리만 제타 함수의 비자명근의 실수부가 1보다 작기만 하면 소수 정리가 성립함을 보였다![9] 그의 근사식은 다음과 같다.
- $$\displaystyle \psi_0\left(x\right)=x-\sum_{\rho}\frac{x^{\rho}}{\rho}-\log\left(2\pi\right)-\frac{\log\left(1-x^{-2}\right)}{2}$$
위와 비슷하게, $$\displaystyle \psi_0\left(x\right)=\lim_{h \to 0}\frac{1}{2}\left(\psi\left(x+h\right)+\psi\left(x-h\right)\right)$$이다. 위의 근사식을 자세히 살펴보면, 맨 앞의 $$x$$는 그냥 $$x$$인데, 위에서 나온 체비쇼프의 결과에 따르면, 소수 정리는 $$\psi\left(x\right)\sim x$$와 동치이다! 따라서 소수 정리를 증명하려면 뒤의 세 항이 $$x$$에 대한 비가 0으로 감을 증명하면 된다. 그런데, 세 번째 항은 그냥 상수이고, 네 번째 항은 $$x$$가 커질수록 0으로 간다. 즉 $$x$$에 대한 비는 당연히 0이다. 그러므로 두 번째 항만 살펴보면 되는데, 망골트의 결과에 따르면 두 번째 항의 무한급수는 균등수렴한다. 즉, 리만 제타 함수의 비자명 근의 실수부가 1보다 작으면 두 번째 항의 비도 0으로 간다. 즉, 리만 제타 함수의 근의 실수부가 1보다 작음을 증명하면 된다.
이것을 증명한 것이 바로 자크 아디마르와 발레 푸생이고, 이들은 1896년 각각 독립적으로 리만 제타 함수의 근의 실수부는 1보다 작음을 증명했다![10] 재밌는 것은, 이것을 증명하는 핵심 아이디어 중 하나는 $$3+4\cos x+\cos 2x=2\left(1+\cos x\right)^2\ge 0$$라는, 고등학생도 증명할 수 있는 공식이라는 것이다.3. 증명
3.1. 해석적 증명
망골트근사식의 증명부터 살펴보자. 다음 식에서 시작한다.
$$\displaystyle \zeta\left(s\right)=\prod_{p}\left(1-\frac{1}{p^s}\right)^{-1}$$
양변을 로그를 취하고 미분하면 다음이 나온다.
$$\displaystyle -\frac{\zeta'\left(s\right)}{\zeta\left(s\right)}=\sum_{n=1}^{\infty}\Lambda\left(n\right)n^{-s}$$
여기서 $$\Lambda\left(n\right)$$은 $$n$$이 소수 $$p$$의 거듭제곱일 때만 $$\log p$$의 값을 가지는 함수이다. 이제 다음과 같은 적분을 이용하자.
For $$\sigma_0>0$$, $$\displaystyle \frac{1}{2\pi i}\int_{\sigma_0-i\infty}^{\sigma_0+i\infty}\frac{y^s}{s}ds=1$$ if $$y>1$$, $$\frac{1}{2}$$ if $$y=1$$, [math(0)] if $$0<y<1$$
$$\displaystyle \sum_{m \le x}\Lambda\left(m\right)=\psi\left(x\right)$$이므로, $$\displaystyle -\frac{\zeta'\left(s\right)}{\zeta\left(s\right)}=\sum_{n=1}^{\infty}\Lambda\left(n\right)n^{-s}$$의 양변에 $$\displaystyle \frac{x^s}{s}$$를 곱하고 적분하면
$$\displaystyle \psi_0\left(x\right)=-\frac{1}{2\pi i}\int_{\sigma_0-i\infty}^{\sigma_0+i\infty}\frac{\zeta'\left(s\right)}{\zeta\left(s\right)}\frac{x^s}{s}$$
가 나오며, 제한된 크기를 가지고 있는 오차항 $$R$$에 대해
$$\displaystyle \psi_0\left(x\right)=-\frac{1}{2\pi i}\int_{\sigma_0-iT}^{\sigma_0+iT}\frac{\zeta'\left(s\right)}{\zeta\left(s\right)}\frac{x^s}{s}+R\left(x,T,\sigma_0\right)$$
로 쓸 수 있다. 이제 $$\displaystyle \sigma_0=1+\frac{1}{\log x}$$라 놓고, 홀수 자연수 $$K$$에 대해 적분구간을 다음과 같이 바꾼다.
$$\displaystyle \int_{\sigma_0-iT}^{\sigma_0+iT}=\int_{C}-\int_{\sigma_0-iT}^{K-iT}-\int_{K-iT}^{K+iT}-\int_{K+iT}^{\sigma_0+iT}$$
여기서 $$C$$는 $$\sigma_0-iT,\sigma_0+iT,K-iT,K+iT$$를 꼭짓점으로 가지는 사각형이다. 이제 $$C$$에 대한 적분 유수정리를 이용하여 계산하고, 나머지 적분과 오차항이 얼마나 큰지 분석하고, $$K,T$$를 모두 무한대로 보내면 망골트근사식이 증명된다. 이제 제타 함수의 비자명근의 실수부가 1보다 작음을 증명하자. 0과 1 사이인 것부터 보이자. 제타 함수에 로그를 씌우면 다음과 같음을 보일 수 있다. $$\displaystyle \zeta\left(s\right)=\exp\left(\sum_{p}\sum_{m=1}^{\infty}\frac{1}{mp^{ms}}\right)=\exp\left(\sum_{p}\sum_{m=1}^{\infty}\frac{e^{-imt\log p}}{mp^{m\sigma}}\right)$$
여기서 $$\sigma$$는 $$s$$의 실수부분이며, $$t$$는 허수부분이다. 이를 통해 다음을 보일 수 있다.
$$\displaystyle \left|\zeta\left(s\right)\right|=\exp\left(\sum_{p}\sum_{m=1}^{\infty}\frac{\cos\left(mt\log p\right)}{mp^{m\sigma}}\right)$$
이것을 $$\sigma, \sigma+it, \sigma+2it$$에 대해 적용하면 다음 식을 얻는다.
$$\displaystyle \left|\zeta\left(\sigma\right)\right|^3\left|\zeta\left(\sigma+it\right)\right|^4\left|\zeta\left(\sigma+2it\right)\right|=\exp\left(\sum_{p}\sum_{m=1}^{\infty}\frac{3+4\cos\left(mt\log p\right)+\cos\left(2mt\log p\right)}{mp^{m\sigma}}\right) = \exp\left(\sum_{p}\sum_{m=1}^{\infty}\frac{\left(1+2\cos \left(mt\log p\right)\right)^2}{mp^{m\sigma}}\right) \ge 1$$
따라서 $$\sigma>1$$일 때는 해가 없다는 것을 알 수 있고, $$\sigma=1$$일때 제타 함수는 simple pole을 가지므로 이 때 또한 해가 없음을 알 수 있다. 즉, 리만 제타 함수의 비자명근들은 모두 소수부분이 1 미만이고, 따라서 소수 정리는 참이다!
증명의 세부 사항을 알고 싶으면 몽고메리와 본(Montgomery&Vaughan)의 Multiplicative Number Theory 5장과 12장을 보면 된다. 다만 이 책에서는 망골트근사식을 완전히 증명하지 않고 도중에 조금 다른 방법으로 6장에서 소수 정리를 증명한다. 또 다른 해석적 증명이 아포스톨(Apostol)의 Introduction to Analytic number Theory 13장에 나오는데, 이 증명은 길이가 더 길고 조금 복잡하지만 위의 증명보다 쉽다. 아포스톨이 계산을 재미있게(??) 쓰는 것을 한번 보는 것도 좋다. 좀 짧은 증명을 원하고 계산에 어느정도 자신이 있다면 뉴먼(Newman)의 Analytic Number Theory를 보면 된다. 무려 8페이지 만에 두 개의 증명을 소개한다!
3.2. 초등적 증명
디리클레 대합 등 산술함수의 이론들을 총동원해(...) 다음 등식을 증명한다.
$$\displaystyle \sum_{p \le x}\log^2 p+\sum_{pq \le x}\log p\log q=2x\log x+\mathcal{O}\left(x\right)$$
이것을 이용해 $$\displaystyle \lim_{x \to \infty}\frac{\theta\left(x\right)}{x}=1$$임을 증명하는데.. 해석적 증명처럼 몇개의 확실한 아이디어에서 나오는 것보단 정말 지루한 계산의 연속이라 교양 수준에서는 할 말이 별로 없다. 보고 싶은 사람은 네이선슨(Nathanson)의 Elementary Methods in Number Theory 9장을 참고하자. 첫 식의 증명 정도는 아포스톨의 Introduction to Analytic number Theory 4장에도 나온다.
4. Error Term
소수 정리로 인해 $$\displaystyle \pi\left(x\right)\sim \frac{x}{\log x}$$인 것은 알았지만, 두 값은 얼마나 차이날까?
이 질문을 던지기 전에 하나 명시해야 할 것이 있다. 현대에는 $$\pi\left(x\right)$$를 근사할 때 $$\displaystyle \frac{x}{\log x}$$대신 [math(\displaystyle \text{li}\left(x\right))][11]를 사용한다. 왜냐하면 후자가 더 정밀도가 높기 때문에...[12] $$\text{li}\left(x\right)$$는 $$\displaystyle \frac{x}{\log x}$$와도 값이 유사하기 때문에 $$\displaystyle \pi\left(x\right)\sim \text{li}\left(x\right)$$라는 것은 쉽게 증명할 수 있다. 그렇다면, 얼마나 차이날까?
우선 1 근방을 살펴보자. $$\pi(1)$$은 당연히 0으로 맞아떨어진다. 그런데 $$\mathrm{li}(1)$$은...
[image]
'''음의 무한대로 곤두박질치는 것을 알 수 있다.'''
거기에 초기 정의인 $$\dfrac{x}{\log x}$$는 더한데 [math(\displaystyle \lim_{x \to 1^-} \dfrac{x}{\log x} = -\infty, \lim_{x \to 1^+} \dfrac{x}{\log x} = \infty)]로 '''극한값 부호가 반대'''이다. 더구나 그래프 개형을 보듯 $$\dfrac{2}{\log 2} > \dfrac{3}{\log 3}$$으로 소수 계량 함수의 함숫값과 괴리가 꽤 크다.
이렇듯, 1 근방의 상대적으로 작은 수에서는 소수 계량 함수와의 차이가 큼을 알 수 있다. 애시당초 점근급수의 특징상 작은 수의 오차는 당연하다. 스털링 근사와 마찬가지.
사실 이 질문은 굉장히 중요한 질문이다. 아래 결과 부분에서 설명하겠지만, 소수의 개수를 정확히 근사하는 것은 현대 정수론에서 매우 중요한 문제이다. 특히, 적당한 상수 $$C$$에 대해 $$\displaystyle \left|\pi\left(x\right)-\text{li}\left(x\right)\right|<C\sqrt{x}\log x$$라는 것은 리만 가설과 동치이다!
발레 푸생은 소수 정리를 증명하면서 적당한 상수 $$a,C$$에 대해 $$\displaystyle \left|\pi\left(x\right)-\text{li}\left(x\right)\right|<C\frac{x}{\log x}e^{-a\sqrt{\log x}}$$라는 것을 증명했으며, 현재 가장 좋은 error term은 이 논문을 참고하자. 보면 알겠지만 리만 가설에서 요구하는 error term까지는 아직 한참 멀었다.
5. 결과
'''엄청나게 많다'''
장난이 아니라, 현대 '해석적 정수론'[13]의 대부분은 소수 정리가 없으면 성립되지 않는다. 소수와 관련된 모든 정리들은 소수정리를 기반으로 두고 있다고 해도 과언이 아니다. 거의 모든 소수 관련 문제가 결국은 '그래서 소수가 얼마나 많이 있는데?'라는 질문으로 환원되니..
소수 정리에서 직접적으로 나오는 결과들을 꼽자면, '$$x$$ 이하의 소수의 밀도는 대략 $$\displaystyle \frac{1}{\log x}$$이다'와 '$$n$$번째 소수는 대략 $$n\log n$$이다'가 있다. 이 두 사실 모두 초등정수론으로는 상상도 못할 결과라는 것을 생각해보면 소수정리가 얼마나 대단한지 할 수 있을 것이다.
초등적인 방법의 해석적 정수론만 쓴 체비쇼프가 1854년 논문집 Memoires de l’Academie des Sciences de Saint Pétersbourg에서 $$\displaystyle \lim_{x \to \infty}\frac{\pi\left(x\right)\log x}{x}$$의 하극한은 0.992 이상, 상극한은 1.105이하임을 증명하였으나,, 소수정리의 정밀함에 비할 바는 못 된다.
또한 소수 계량 함수와 로그 적분 함수를 다루는 과정에서 스큐스 수라는 것이 튀어나오기도 했다.
6. 확장
등차수열 버전으로 지겔-발피시 정리(Siegel-Walfisz Theorem)가 있다: 적당한 상수 $$B$$와 주어진 양수 $$A$$에 대해 $$q \le \left(\log x\right)^A$$이고 $$\left(a,q\right)=1$$이면 적당한 상수 $$C$$가 있어 $$\displaystyle \left|\psi\left(x;q,a\right)-\frac{x}{\varphi\left(q\right)}\right|<Cx \exp\left(-B\sqrt{\log x}\right)$$이다. 여기서 $$\psi\left(x;q,a\right)$$는 $$q$$로 나눈 나머지가 $$a$$인 소수에 대해서만 $$\psi$$를 세 준 것이다. 이 정리는 비노그라도프(Vinogradov)의 충분히 큰 수에 대한 홀수 골드바흐 추측 증명에도 쓰인 중요한 정리이다!
Prime ideal 버전으로는 Landau Prime Ideal Theorem이 있다: 대수적 수체에서 노름이 $$x$$ 이하인 Prime ideal의 개수는 대략 $$\frac{x}{\log x}$$개이다.
기약다항식 버전도 있다! 이것은 Prime Polynomial Theorem이라고 불린다: 원소가 $$q$$개인 유한체에서 차수가 $$n$$이하인 일계수 기약다항식의 개수를 $$\pi_q\left(n\right)$$이라고 했을 때 $$\displaystyle \left|\pi_q\left(n\right)-\frac{q^n}{n}\right|<C\frac{q^{n/2}}{n}$$이다.
측지선[14] 버전의 Prime Geodesic Theorem도 있다. 소수정리의 초등적 증명을 한 아틀레 셀베르그가 필즈상을 받은 후에 연구한 셀베르그 트레이스 공식에 기반한다. [15]
처음 두 정리는 모두 증명방법이 비슷한데,[16] 각각 적당한 제타 함수를 정의해준 다음 소수 정리에서 썼던 것과 비슷한 방법을 쓴다.. 지겔-발피시에서는 디리클레 L함수를, Landau에서는 데데킨트 제타 함수를. 측지선의 경우도 비슷한 방법을 쓰는데, 문제는 다른 제타함수들처럼 '좋은 성질'을 가진 제타를 정의하는 것이다. [17]
[1] 이 문서 전체에서 $$\log x$$는 자연로그를 가리킨다. 대부분의 순수수학 계열 전공서적은 상용로그를 쓸 일이 없기 때문에 log라고 하면 자연로그로 본다. 다만 전산분야에선 밑이 2인 경우를 그냥 log라고 쓸 때도 종종 있다.[2] 이 표기는 일반적으로 어떤 수 이하의 소수의 개수를 나타내는 함수, 즉 ‘소수세기함수’를 쓸 때 사용하는 표기이다.[3] 물론 이 때에 증명하진 못하였다.[4] 이 정리가 소수정리랑 뭐가 다르냐고 헷갈릴 수도 있는데, 이 정리는 $$\displaystyle \lim_{x \to \infty}\frac{\pi\left(x\right)\log x}{x}$$가 존재한다는 것을 가정했다. 따라서 저 극한값이 존재하지 않는다면 소수정리가 성립하지 않을 수도 있다는 말이다.[5] x 이하의 모든 소수에 대해 그 로그값을 더한 것이다.[6] 표기가 같은 헤비사이드 계단 함수와 혼동에 주의.[7] 소수와 소수의 거듭제곱까지 로그를 더하는 것이다.[8] 이 확장을 ‘해석적 접속’, 혹은 '해석적 확장'이라 부른다. 이게 가능한 이유는 복소함수의 성질중 하나로, 서로 다른 범위에서 정의된 두 복소함수가 극 외부에서 둘 다 전해석함수일 때, 두 범위의 교집합에서 두 함수가 완전히 일치할 경우에는 두 함수를 같다고 봐도 된다. 라는 특수한 성질이 존재하기 때문이다. 참고로 이 성질의 응용으로, 어떤 복소함수를 정의했는데 이게 실수축(혹은 반실수축)에서 이미 알려진 실함수와 동일하다면 이 복소함수를 해당 실함수의 복소평면상에서의 확장이라도 할 수 있다.[9] 여담이지만 리만 제타함수는 실수부 1/2인 복소수 축을 중심으로 좌우대칭이기 때문에, 리만 제타함수의 모든 비자명 근의 실수부가 0~1 사이의 복소수일때 성립한다는 것과 동치다. 자명근은 z가 음의 짝수라는 실수근이며, 이 근은 소수의 성질에 아무런 영향도 주지 못한다.[10] 이는 위의 각주에도 나와있지만, 제타함수의 특징에 의하여 리만 제타함수에서 모든 음의 짝수를 제외한 비자명근의 실수부는 0~1 사이에 존재한다는 것을 증명한 것도 된다.[11] $$\displaystyle \frac{1}{\log x}$$의 원시함수이다. $$\displaystyle \text{li}\left(x\right) = \int_0^{x} \frac{1}{\ln t} {\rm d}t$$로 정의된다.다만 적분구간에 $$1$$(피적분함수의 분모가 0이 된다)이 있으므로 아예 적분구간을 2부터 x까지 잡는 경우도 있다.[12] $$x \ge 599$$이면 $$\pi\left(x\right)-\dfrac{x}{\log x}>\dfrac{x}{(\log x)^2}$$임이 알려져있으므로 전자와의 차이는 무한대로 발산한다. 반면 후자와의 차이는 부호가 무한히 뒤바뀐다는 것이 증명되었고 그 첫번째 역전이 일어나는 수가 바로 스큐스 수다.[13] Modular Form등의 대수적인 테크닉이 적은 순수한 해석적 정수론을 말하는 것이다.[14] 어떤 공간에서, 두 점을 잇는 최단거리 경로를 측지선이라고 한다.[15] 이 공식은 랭글랜즈 프로그램에 영감을 준 중요한 주제 중의 하나이며 테렌스 타오는 이를 셀베르그의 가장 큰 업적이라고도 언급하였다.[16] 세 번째 정리는 훨씬 쉽게 증명할 수 있다. 몽고메리와 본(Montgomery&Vaughan)의 Multiplicative Number Theory 1장의 연습문제 혹은 Michael Rosen의 Number Theory in Function Fields의 2장 참고.[17] 제타 함수가 그렇게 많냐고 할 수도 있는데, 이만큼 있다...