소수 정리

페르마의 소수 정리에 대한 내용은 페르마의 두 제곱수 정리 문서 참고하십시오.

1. 개요[편집]

---

素數定理 / prime number theorem

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

2. 역사[편집]

---

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

그 후 1798년, 아드리앵마리 르장드르는 ‘정수론에 관한 소고’라는 제목으로 책을 한 권 출판했는데, 이 책에서 르장드르는 적당한 상수 [math(A)]에 대해 다음 식이 성립한다고 추측했다.

여기서 [math(\sim)]는 [math(x)]가 무한대로 갈수록 양변의 비가 [math(1)]로 수렴한다는 뜻이다. 또한 그는 [math(A)]가 대략 [math(1.08366)]일 것이라고 예상했는데, 이는 지금 쓰이고 있는 것과는 표현이 조금 다르나 결국 동치이다.[4]

이후 러시아 수학자 파프누티 체비쇼프(Пафну́тий Чебышёв; 1821~1894)는 소수 정리에 관해서 다음과 같은 사실을 증명했다.

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

이 정리가 소수정리랑 뭐가 다르냐고 헷갈릴 수도 있는데, 이 정리는 [math(\displaystyle\lim_{x\to\infty}\frac{\pi\left(x\right)\log x}{x})]가 존재한다는 것을 가정했다. 따라서 저 극한값이 존재하지 않는다면 소수정리가 성립하지 않을 수도 있다는 말이다.

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

• [math(\displaystyle\vartheta\left(x\right)=\sum_{p\le x}\log p\quad (p\in\mathbb{P}))][6]
  [math(x)] 이하의 모든 소수에 대해 그 로그값을 더한 것이다.
  [7]
  표기가 같은 헤비사이드 계단 함수와 혼동에 주의.
• [math(\displaystyle\psi\left(x\right)=\sum_{p^k\le x}\log p\quad (p\in\mathbb{P}))][8]
  소수와 소수의 거듭제곱까지 로그를 더하는 것이다. [math(x)] 이하의 모든 자연수에 대한 최소공배수의 로그값과 같다.

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

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

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

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

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

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

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

여기서 [math(\displaystyle {\rm 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(\rho)]는 리만 제타 함수의 비자명한, 즉, 음의 짝수가 아닌 근들이다. 또한, 리만은 뫼비우스 반전을 이용하여 [math(f)]를 통해 소수세기함수를 구할 수 있는 공식을 만들었다.

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

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

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

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

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

3. 증명[편집]

---

3.1. 해석적 증명[편집]

---

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

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

여기서 [math(\Lambda\left(n\right))]은 [math(n)]이 소수 [math(p)]의 거듭제곱일 때만 [math(\log p)]의 값을 가지는 함수이다. 이제 다음과 같은 페론의 공식(perron's formula)을 이용하자.
여기서 [math(g(x))]는 수열 [math(a(n))]에 대해 [math(g(s)=\displaystyle\sum_{n=1}^{\infty}\frac{a(n)}{n^s})],[math( \ A(x))]는 [math(\displaystyle\sum_{1\le n\le x}^{}a(n))]이되, [math(x)]가 정수면 시그마의 마지막 항에 [math(\frac{1}{2})]을 곱해서 더하는 함수로 정의된다.

이제 [math(a(n)=\Lambda(n))]을 대입해보자. 그러면 [math(\displaystyle\sum_{m\le x}\Lambda\left(m\right)=\psi\left(x\right))]이고 [math(\displaystyle -\frac{\zeta'\left(s\right)}{\zeta\left(s\right)}=\sum_{n=1}^{\infty}\Lambda\left(n\right)n^{-s})]이므로 페론의 공식에 대입하면

가 나오며, 제한된 크기를 가지고 있는 오차항 [math(R)]에 대해

로 쓸 수 있다. 이제 [math(\displaystyle\sigma_0=1+\frac{1}{\log x})]라 놓고, 홀수 자연수 [math(K)]에 대해 적분구간을 다음과 같이 바꾼다.

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

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

이것을 [math(\sigma,\sigma+it,\sigma+2it)]에 대해 적용하면 다음 식을 얻는다.
따라서 [math(\sigma>1)]일 때는 해가 없다는 것을 알 수 있고, [math(\sigma=1)]일때 제타 함수는 simple pole을 가지므로 이때 또한 해가 없음을 알 수 있다. 즉, 리만 제타 함수의 비자명근들은 모두 소수부분이 [math(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\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. 오차[편집]

---

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

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

우선 [math(1)] 근방을 살펴보자. [math(\pi(1))]은 당연히 [math(0)]으로 맞아떨어진다. 그런데 [math(\mathrm{li}(1))]은...

음의 무한대로 곤두박질치는 것을 알 수 있다.

거기에 초기 정의인 [math(\dfrac{x}{\log x})]는 더한데 [math(\displaystyle \lim_{x\to 1^-}\dfrac{x}{\log x}=-\infty,\lim_{x \to 1^+}\dfrac{x}{\log x}=\infty)]로 극한값 부호가 반대이다. 더구나 그래프 개형을 보듯 [math(\dfrac{2}{\log 2} > \dfrac{3}{\log 3})]으로 소수 계량 함수의 함숫값과 괴리가 꽤 크다.

이렇듯, [math(1)] 근방의 상대적으로 작은 수에서는 소수 계량 함수와의 차이가 큼을 알 수 있다. 애시당초 점근급수의 특징상 작은 수의 오차는 당연하다. 스털링 근사와 마찬가지.

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

발레 푸생은 소수 정리를 증명하면서 적당한 상수 [math(a,C)]에 대해 [math(\displaystyle\left|\pi\left(x\right)-{\rm li}\left(x\right)\right|<C\frac{x}{\log x}e^{-a\sqrt{\log x}})]라는 것을 증명했으며, 현재 가장 좋은 오차항은 이 논문을 참고하자. 보면 알겠지만 리만 가설에서 요구하는 오차항까지는 아직 한참 멀었다.

5. 영향[편집]

---

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

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

초등적인 방법의 해석적 정수론만 쓴 체비쇼프가 1854년 논문집 Memoires de l’Academie des Sciences de Saint Pétersbourg에서 [math(\displaystyle\lim_{x\to\infty}\frac{\pi\left(x\right)\log x}{x})]의 하극한은 0.992 이상, 상극한은 1.105이하임을 증명했으나, 소수정리의 정밀함에 비할 바는 못 된다.

또한 소수 계량 함수와 로그 적분 함수를 다루는 과정에서 스큐스 수라는 것이 튀어나오기도 했다.

6. 확장[편집]

---

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

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

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

측지선[15] 버전의 Prime Geodesic Theorem도 있다. 소수정리의 초등적 증명을 한 아틀레 셀베르그가 필즈상을 받은 후에 연구한 셀베르그 트레이스 공식에 기반한다.[16]

처음 두 정리는 모두 증명 방법이 비슷한데,[17] 각각 적당한 제타 함수를 정의해준 다음 소수 정리에서 썼던 것과 비슷한 방법을 쓴다. 지겔-발피시에서는 디리클레 L함수를, Landau에서는 데데킨트 제타 함수를. 측지선의 경우도 비슷한 방법을 쓰는데, 문제는 다른 제타함수들처럼 '좋은 성질'을 가진 제타를 정의하는 것이다.[18]