소수 정리

(소수정리에서 넘어옴)

Prime Number Theorem


19세기 정수론의 최종보스

1 개요

어떤 양수 이하의 소수가 몇 개나 있는지 그 값을 어림해주는 정리. 어떤 양수 [math]x[/math]에 대해 [math]x[/math]보다 작은 소수의 개수는 대략 [math]\displaystyle \frac{x}{\log x}[/math]개가 있다고 주장하는 정리이다.[1] 정확히 말하면, [math]x[/math] 이하의 소수의 개수를 [math]\pi\left(x\right)[/math]라고 할 때,[2] [math]\displaystyle \lim_{x \to \infty}\frac{\pi\left(x\right)\log x}{x}=1[/math]이라는 것이다.

2 역사

흔히 천재 수학자 카를 프리드리히 가우스가 제시했다고 알려져 있는데, 가우스가 소수 정리를 먼저 생각하고 연구하긴 했지만, 실제로 소수 정리를 먼저 발표한 사람은 르장드르이다. 가우스는 1792년과 1793년 사이에 소수를 하루에 1000개씩, 그것도 15분만에 직접 손으로 찾아가면서, 소수의 빈도수가 평균적으로 로그함수에 반비례한다는 것을 알아냈다[3]. 하지만 발표는 하지 않았는데, 이는 가우스가 자신의 연구 성과를 잘 발표하지 않거나 느리게 발표하는 성향이 있어서이기도 했고, 그 당시 가우스가 겨우 15살이었던 것도 있다. 오오 가우스 오오.

그 후 1798년, 아드리앵마리 르장드르는 ‘정수론에 관한 소고’라는 제목으로 책을 한 권 출판했는데, 이 책에서 르장드르는 적당한 상수 [math]A[/math]에 대해 다음 식이 성립한다고 추측했다.
[math]\displaystyle \pi \left(x\right) \sim\frac{x}{\log x -A} [/math]
여기서 [math]\sim[/math]는 양변의 비가 [math]x[/math]가 무한대로 갈수록 1로 수렴한다는 뜻이다. 또한 그는 [math]A[/math]가 대략 1.08366일 것이라고 예상했는데, 이는 지금 쓰이고 있는 것과는 조금 다르다[4].

이후, 러시아 수학자 파프누티 체비쇼프는 소수 정리에 관해서 다음과 같은 사실을 증명하였다.

  • 어떤 상수 [math]B[/math]에 대해, [math]\displaystyle \lim_{x \to \infty}\frac{\pi\left(x\right)\log x}{x}=B[/math]라면 [math]B=1[/math]이 성립한다.[5]

체비쇼프는 이와 같은 사실을 증명하기 위해 다음과 같은 함수들을 정의했다.

  • [math]\displaystyle \theta\left(x\right)=\sum_{p \le x} \log p[/math]
  • [math]\displaystyle \psi\left(x\right)=\sum_{p^k \le x} \log p[/math]

여기서 [math]p[/math]는 소수들을 의미한다. 이 함수들은 각각 체비쇼프 세타 함수와 프사이 함수라고 불리는데, 체비쇼프는 다음이 모두 동치임을 증명하였다.

  • [math]\displaystyle \lim_{x \to \infty}\frac{\pi\left(x\right)\log x}{x}=1[/math]
  • [math]\displaystyle \lim_{x \to \infty}\frac{\theta\left(x\right)}{x}=1[/math]
  • [math]\displaystyle \lim_{x \to \infty}\frac{\psi\left(x\right)}{x}=1[/math]

즉, 소수 정리를 증명하려면 소수세기함수를 살펴보는 대신 세타 함수나 프사이 함수를 살펴봐도 충분하단 것이다! 언뜻 보면 소수세기함수가 훨씬 간단한데 왜 굳이 저런 이상한 함수를 만드나 싶을 수도 있는데, 사실 프사이 함수는 소수세기함수보다 계산이 훨씬 잘 된다. 실제도 소수세기함수에 대한 어림은 대부분 프사이 함수에 대한 어림을 이용해서 얻어진 것이다.

체비쇼프가 소수 정리에 관해서 비약적인 발전을 이루었지만, 체비쇼프의 방법으로 증명하기에 소수 정리는 너무 막강한 적이었다. 이때, 수학자들에게 정수론에서 가장 중요한 무기 중 하나이며 150년이 지난 지금까지 최전방에서 무기로 사용되고 있는 것을 선사해 준 사람이 바로 베른하르트 리만이다.

리만은 1859년 베를린학술원에 가입하면서 관례에 따라 논문 한 편을 제출하였는데, 이 논문이 바로 이후 정수론의 역사에 지대한 영향을 미친 <주어진 수보다 작은 소수의 개수에 관하여>였다. 이 논문에서 리만은 그의 제타 함수를 소개하고, ‘실수부가 1 이상’이라는 제한 조건이 붙여 있었던 함수를 확장시켜[6] 1이 아닌 모든 복소수에 대해 정의하였다. 또한, 놀랍게도 리만은 이 함수의 해를 소수세기함수와 연관시켰다!

이에 대해 조금 살펴보면, 리만은 다음과 같은 함수를 정의하였다.

  • [math]\displaystyle f\left(x\right)=\sum_{i=1}^{\infty}\pi\left(x^{1/i}\right)[/math]

이 함수는 무한급수처럼 보이는데, 사실 [math]\displaystyle \pi\left(x^{1/i}\right)[/math][math]i[/math]가 충분히 크면 0이 되기 때문에 유한합만으로 끝난다. 리만은 이 함수와 제타 함수의 근들을 다음과 같이 연관지었다.

  • [math]\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}[/math]

여기서 [math]\displaystyle \text{li}\left(x\right)=\lim_{\epsilon \to 0+}\left(\int_{0}^{1-\epsilon}\frac{1}{\log t}dt+\int_{1+\epsilon}^{x}\frac{1}{\log t}dt\right)[/math]이고, [math]\rho[/math]는 리만 제타 함수의 비자명한, 즉, 음의 짝수가 아닌 근들이다.. 또한, 리만은 뫼비우스 반전을 이용하여 [math]f[/math]를 통해 소수세기함수를 구할 수 있는 공식을 만들었다.

  • [math]\displaystyle \pi_0\left(x\right)=\sum_{n=1}^{\infty}\frac{\mu\left(n\right)f\left(x^{1/n}\right)}{n}[/math]

[math]\displaystyle \pi_0\left(x\right)=\lim_{h \to 0}\frac{1}{2}\left(\pi\left(x+h\right)+\pi\left(x-h\right)\right)[/math]이다. 여기서 우리는 다음을 알 수 있다: 소수세기함수는 [math]f[/math]를 이용해서 나타낼 수 있다. [math]f[/math]는 리만 제타 함수의 근을 통해 계산된다. 그렇다면, 리만 제타 함수의 근에 대한 정보를 충분히 안다면, 소수세기함수를 근사할 수 있다!

실제로 리만은 리만 제타 함수의 비자명근의 실수부가 모두 [math]\frac{1}{2}[/math]이라면 소수 정리가 성립함을 보였는데, 이것이 그 유명한 리만 가설이다. 그 이후로 소수 정리를 연구하는 수학자들은 리만 가설을 공략하기 시작했고, 모두들 알듯 그 결과는....

그 이후, 1895년, 독일의 수학자 한스 폰 망골트는 리만의 방법론을 체비쇼프 프사이 함수에 적용해서, 망골트근사식(Mangoldt Explicit Formula)를 만들었는데, 망골트는 이 근사식을 이용해서 리만 제타 함수의 비자명근의 실수부가 1보다 작기만 하면 소수 정리가 성립함을 보였다! 그의 근사식은 다음과 같다.

  • [math]\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}[/math]

단, 이때 [math]x[/math]는 정수가 아니다. 위와 비슷하게, [math]\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)[/math]이다. 위의 근사식을 자세히 살펴보면, 맨 앞의 [math]x[/math]는 그냥 [math]x[/math]인데, 위에서 나온 체비쇼프의 결과에 따르면, 소수 정리는 [math]\psi\left(x\right)\sim x[/math]와 동치이다! 따라서 소수 정리를 증명하려면 뒤의 세 항이 [math]x[/math]에 대한 비가 0으로 감을 증명하면 된다. 그런데, 세 번째 항은 그냥 상수이고, 네 번째 항은 [math]x[/math]가 커질수록 0으로 간다. 즉 [math]x[/math]에 대한 비는 당연히 0이다. 그러므로 두 번째 항만 살펴보면 되는데, 망골트의 결과에 따르면 두 번째 항의 무한급수는 균등수렴한다. 즉, 리만 제타 함수의 비자명근의 실수부가 1보다 작으면 두 번째 항의 비도 0으로 간다. 즉, 리만 제타 함수의 근의 실수부가 1보다 작음을 증명하면 된다.

이것을 증명한 것이 바로 자크 아디마르와 발레 푸생이고, 이들은 1896년 각각 독립적으로 리만 제타 함수의 근의 실수부는 1보다 작음을 증명했다! 재밌는 것은, 이것을 증명하는 핵심 아이디어 중 하나는 [math]3+4\cos x+\cos 2x=2\left(1+\cos x\right)^2\ge 0[/math]라는, 고등학생도 증명할 수 있는 공식이라는 것이다.

3 증명

3.1 해석적 증명

망골트근사식의 증명부터 살펴보자. 다음 식에서 시작한다.

[math]\displaystyle \zeta\left(s\right)=\prod_{p}\left(1-\frac{1}{p^s}\right)^{-1}[/math]

양변을 로그미분하면 다음이 나온다.

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

여기서 [math]\Lambda\left(n\right)[/math][math]n[/math]이 소수 [math]p[/math]의 거듭제곱일 때만 [math]\log p[/math]의 값을 가지는 함수이다. 이제 다음과 같은 적분을 이용하자.

For [math]\sigma_0\gt0[/math], [math]\displaystyle \frac{1}{2\pi i}\int_{\sigma_0-i\infty}^{\sigma_0+i\infty}\frac{y^s}{s}ds=1[/math] if [math]y\gt1[/math], [math]\frac{1}{2}[/math] if [math]y=1[/math], [math]0[/math] if [math]0\lty\lt1[/math]

[math]\displaystyle \sum_{m \le x}\Lambda\left(m\right)=\psi\left(x\right)[/math]이므로, [math]\displaystyle -\frac{\zeta'\left(s\right)}{\zeta\left(s\right)}=\sum_{n=1}^{\infty}\Lambda\left(n\right)n^{-s}[/math]의 양변에 [math]\displaystyle \frac{x^s}{s}[/math]를 곱하고 적분하면

[math]\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}[/math]

가 나오며, 페론의 공식을 이용해 이상적분을 보통 적분으로 바꾸면,

[math]\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)[/math]

가 된다. [math]R[/math]은 제한된 크기를 가지고 있는 오차항이다. 이제 [math]\displaystyle \sigma_0=1+\frac{1}{\log x}[/math]라 놓고, 홀수 자연수 [math]K[/math]에 대해 적분구간을 다음과 같이 바꾼다.

[math]\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}[/math]

여기서 [math]C[/math][math]\sigma_0-iT,\sigma_0+iT,K-iT,K+iT[/math]를 꼭짓점으로 가지는 사각형이다. 이제 [math]C[/math]에 대한 적분을 제외한 나머지 적분과 오차항이 얼마나 큰지 분석하고, [math]K,T[/math]를 모두 무한대로 보내면 망골트근사식이 증명된다. 이제 제타 함수의 비자명근의 실수부가 1보다 작음을 증명하자. 0과 1 사이인 것부터 보이자. 제타 함수에 로그를 씌우면 다음과 같음을 보일 수 있다.

[math]\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)[/math]

여기서 [math]\sigma[/math][math]s[/math]의 실수부분이며, [math]t[/math]는 허수부분이다. 이를 통해 다음을 보일 수 있다.

[math]\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)[/math]

이것을 [math]\sigma, \sigma+it, \sigma+2it[/math]에 대해 적용하면 다음 식을 얻는다.

[math]\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[/math]

따라서 [math]\sigma\gt1[/math]일 때는 해가 없다는 것을 알 수 있고, [math]\sigma=1[/math]일때 제타 함수는 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 초등적 증명

디리클레 대합 등 산술함수의 이론들을 총동원해(...) 다음 등식을 증명한다.

[math]\displaystyle \sum_{p \le x}\log^2 p+\sum_{pq \le x}\log p\log q=2x\log x+O\left(x\right)[/math]

이것을 이용해 [math]\displaystyle \lim_{x \to \infty}\frac{\theta\left(x\right)}{x}=1[/math]임을 증명하는데.. 해석적 증명처럼 몇개의 확실한 아이디어에서 나오는 것보단 정말 계산이라 교양 수준에서는 뭐라고 할 말이 별로 없다. 보고 싶은 사람은 네이선슨(Nathanson)의 Elementary Methods in Number Theory 9장을 참고하자. 첫 식의 증명 정도는 아포스톨의 Introduction to Analytic number Theory 4장에도 나온다.

4 Error Term

소수 정리로 인해 [math]\displaystyle \pi\left(x\right)\sim \frac{x}{\log x}[/math]인 것은 알았지만, 두 값은 얼마나 차이날까?

이 질문을 던지기 전에 하나 명시해야 할 것이 있다. 현대에는 [math]\pi\left(x\right)[/math]를 근사할 때 [math]\displaystyle \frac{x}{\log x}[/math]대신 [math]\displaystyle \text{li}\left(x\right)[/math]를 사용한다. 왜냐하면 후자가 더 정밀도가 높기 때문에... [math]\text{li}\left(x\right)[/math][math]\displaystyle \frac{x}{\log x}[/math]와도 값이 유사하기 때문에 [math]\displaystyle \pi\left(x\right)\sim \text{li}\left(x\right)[/math]라는 것은 쉽게 증명할 수 있다. 그렇다면, 얼마나 차이날까?

이 질문은 굉장히 중요한 질문이다. 아래 결과 부분에서 설명하겠지만, 소수의 개수를 정확히 근사하는 것은 현대 정수론에서 매우 중요한 문제이다. 특히, 적당한 상수 [math]C[/math]에 대해 [math]\displaystyle \left|\pi\left(x\right)-\text{li}\left(x\right)\right|\ltC\sqrt{x}\log x[/math]라는 것은 리만 가설과 동치이다!

발레 푸생은 소수 정리를 증명하면서 적당한 상수 [math]a,C[/math]에 대해 [math]\displaystyle \left|\pi\left(x\right)-\text{li}\left(x\right)\right|\ltC\frac{x}{\log x}e^{-a\sqrt{\log x}}[/math]라는 것을 증명했으며, 현재 가장 좋은 error term은 이 논문을 참고하자. 계산이 보기만해도 끔찍하다 보면 알겠지만 리만 가설에서 요구하는 error term까지는 아직 한참 멀었다. 이 문서를 보는 위키니트들도 도전해서 필즈상을 받아보자! 물론 그 전에 굶어죽을 확률이 더 높다. 아니면 존 내시처럼 미쳐서 정신병원에...

5 결과

엄청나게 많다

장난이 아니라, 현대 '해석적 정수론'[7]의 대부분은 소수 정리가 없으면 성립되지 않는다. 소수와 관련된 모든 정리들은 소수정리를 기반으로 두고 있다고 해도 과언이 아니다. 거의 모든 소수 관련 문제가 결국은 '그래서 소수가 얼마나 많이 있는데?'라는 질문으로 환원되니..

소수 정리에서 직접적으로 나오는 결과들을 꼽자면, '[math]x[/math] 이하의 소수의 밀도는 대략 [math]\displaystyle \frac{1}{\log x}[/math]이다'와 '[math]n[/math]번째 소수는 대략 [math]n\log n[/math]이다'가 있다. 이 두 사실 모두 초등정수론으로는 상상도 못할 결과라는 것을 생각해보면 소수정리가 얼마나 대단한지 할 수 있을 것이다.

초등적인 방법의 해석적 정수론만 쓴 체비쇼프가 저 비슷한 결과를 증명하긴 했지만, 소수정리의 정밀함에 비할 바는 못 된다.

6 확장

등차수열 버전으로 지겔-발피시 정리(Siegel-Walfisz Theorem)가 있다: 적당한 상수 [math]B[/math]와 주어진 양수 [math]A[/math]에 대해 [math]q \le \left(\log x\right)^A[/math]이고 [math]\left(a,q\right)=1[/math]이면 적당한 상수 [math]C[/math]가 있어 [math]\displaystyle \left|\psi\left(x;q,a\right)-\frac{x}{\varphi\left(q\right)}\right|\ltCx \exp\left(-B\sqrt{\log x}\right)[/math]이다. 여기서 [math]\psi\left(x;q,a\right)[/math][math]q[/math]로 나눈 나머지가 [math]a[/math]인 소수에 대해서만 [math]\psi[/math]를 세 준 것이다. 이 정리는 비노그라도프(Vinogradov)의 충분히 큰 수에 대한 홀수 골드바흐 추측 증명에도 쓰인 중요한 정리이다!

Prime ideal 버전으로는 Landau Prime Ideal Theorem이 있다: 대수적 수체에서 노름이 [math]x[/math] 이하인 Prime ideal의 개수는 대략 [math]\frac{x}{\log x}[/math]개이다.

기약다항식 버전도 있다! 이것은 Prime Polynomial Theorem이라고 불린다: 원소가 [math]q[/math]개인 유한체에서 차수가 [math]n[/math]이하인 일계수 기약다항식의 개수를 [math]\pi_q\left(n\right)[/math]이라고 했을 때 [math]\displaystyle \left|\pi_q\left(n\right)-\frac{q^n}{n}\right|\ltC\frac{q^{n/2}}{n}[/math]이다.

위의 세 정리는 모두 증명방법이 비슷한데, 각각 적당한 제타 함수를 정의해준 다음 소수 정리에서 했던 짓을 반복해 준다. 지겔-발피시에서는 디리클레 L함수를, Landau에서는 데데킨트 제타 함수를, 기약다항식에서는 또 적당한 제타 함수를... [8]
  1. 이 문서 전체에서 [math]\log x[/math]는 자연로그를 가리키는 것이다. 사실 고등학생이나 학부 초에야 자연로그를 ln으로 쓰지 대부분의 순수수학 계열 전공서적은 상용로그를 쓸 일이 없기 때문에 log라고 하면 무조건 자연로그이다.
  2. 이 표기는 일반적으로 어떤 수 이하의 소수의 개수를 나타내는 함수, 즉 ‘소수세기함수’를 쓸 때 사용하는 표기이다.
  3. 물론 이 때에 증명하진 못하였다.
  4. 하지만 결국 동치이다.
  5. 이 정리가 소수정리랑 뭐가 다르냐고 헷갈릴 수도 있는데, 이 정리는 [math]\displaystyle \lim_{x \to \infty}\frac{\pi\left(x\right)\log x}{x}[/math]가 존재한다는 것을 가정했다. 따라서 저 극한값이 존재하지 않는다면 소수정리가 성립하지 않을 수도 있다는 말이다.
  6. 이 확장을 ‘해석적 접속’이라 부른다.
  7. Modular Form등의 대수적인 테크닉이 적은 순수한 해석적 정수론을 말하는 것이다.
  8. 제타 함수가 그렇게 많냐고 할 수도 있는데, 이만큼 있다...