| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
prime number theorem / 素數 定理소수 계량 함수 [math(pi(x))], 즉 주어진 양수 [math(x)] 이하의 소수(수론)의 개수를 근사적으로 표현하는 정리. 수식으로는
[math(
\pi(x) \sim \dfrac x{\log x}
)]
[1]와 같이 쓰며, 정확한 뜻은
[math(
\lim\limits_{x\to\infty} \dfrac{\pi(x)}{x/\log x} = 1
)]
이라는 것이다.[2] 1896년 자크 아다마르와 드 라 발레 푸생이라는 수학자들에 의해 증명되었다.
2. 역사
2.1. 초기
소수는 모든 자연수를 곱셈으로 유일하게 표현할 수 있는 기본적인 수이기 때문에, 아주 중요한 수들이다. 실제로 매우 오래 전부터 소수에 대한 연구가 시작되었으며, 기원전 유클리드는 간단한 논증으로 소수의 개수가 무한히 많음을 밝혔다. 그런데 이런 소수는 앞의 몇가지만 살펴봐도 알겠지만, 매우 불규칙하다는 것을 알 수 있다. 자연스레 소수의 일관적인 규칙을 찾는 문제가 시대를 넘어 여러 뛰어난 수학자들을 매료했지만, 몇천년 동안 대부분의 시도는 성공하지 못했다. 일례로 레온하르트 오일러는 소수를 만들어내는 다항함수 [math(P(n) = n^2+n+41)]을 제시했는데, 이는 [math(0 \le n \le 39)]인 정수 [math(n)]에 대해서는 전부 소수를 내놓지만 [math(n = 40)]일 때는 [math(41)]의 배수가 된다.이러한 배경 속에서 천재 수학자 카를 프리드리히 가우스가 소수 정리를 제시했다. 가우스는 15세이던 1792년과 1793년 사이에 소수 세기 함수의 값을 관찰하고, [math(x)] 근처의 소수의 밀도가 대략 [math(1/\log x)]와 비슷함을 발견했다. 매우 불규칙해 보이는 소수들이지만, 각각의 소수가 아니라 소수들의 대략적인 분포를 살피니, 희미하지만 어떤 규칙성이 보인다는 것이다. 이를 통해 가우스는 소수 정리를 추측했지만, 증명할 수는 없었다. 또 이와 관련해 가우스가 매일 15분마다 연속한 1000개의 자연수 중 소수를 전부 골라내며 이를 발견했다는 일화가 있는데, 이는 확인되지 않은 사실이며, 이때 가우스는 이미 상당한 길이의 소수표를 가지고 있었다고 한다.
그 후 1798년, 아드리앵마리 르장드르는 '정수론에 관한 소고'라는 제목의 책을 한 권 출판하며, 적당한 상수 [math(A)]에 대해 다음 식이 성립한다고 추측했다.
[math(\displaystyle \begin{aligned}
\pi(x) \sim \dfrac x{\log x-A}
\end{aligned} )]
또한 그는 [math(A)]가 대략 [math(1.08366)]일 것이라고 예상했는데, 이는 지금 쓰이고 있는 로그 적분 함수와는 표현이 조금 다르나 결국 동치이다.[3] 이것이 처음으로 공식적으로 제시된 소수 정리의 버전이며, 이 추측은 거의 100년의 시간 동안 증명되지 못한 채 소수 추측으로 남았다.
2.2. 체비쇼프
대략 50년 후, 러시아 수학자인 파프누티 체비쇼프(Пафну́тий Чебышёв; 1821~1894)는 1848년과 1850년에 걸쳐 소수 정리보다는 약한 정리이지만 다음을 증명하였다.| 극한 [math(\lim\limits_{x\to\infty} \dfrac{\pi(x)}{x/\log x})]가 존재한다면, 그 값은 [math(1)]이다. |
그는 소수 계량 함수를 변형한, 체비쇼프 함수라고 부르는 다음 함수들을 정의했다.
- [math(\displaystyle \vartheta(x) = \sum_{p\le x} \log p)], 즉 [math(x)] 이하의 모든 소수 [math(p)]에 대해 [math(\log p)]를 더한 것이다.
- [math(\displaystyle \psi(x) = \sum_{p^k\le x} \log p)], 즉 [math(x)] 이하의 모든 소수의 거듭제곱에 대해 [math(\log p)]를 더한 것이다.
- [math(\vartheta(x) = \psi(x) + O(x^{1/2}))]
- [math(\pi(x) = \dfrac{\psi(x)}{\log x} + O\biggl( \dfrac x{\log^2 x} \biggr))]
이 정리와 소수 정리의 차이점은 '존재성'을 가정했다는 것이다. 즉, '해당 극한이 존재한다'를 추가로 증명해야 소수 정리가 완성되는 것이다.
2.3. 리만
체비쇼프가 소수 정리에 관해서 비약적인 발전을 이루었지만, 체비쇼프의 방법으로 증명하기에 소수 정리는 너무 막강한 적이었다. 이때, 정수론에서 가장 중요한 무기 중 하나이며 150년이 지난 지금까지 최전방에서 무기로 사용되고 있는 방법론을 제시한 사람이 바로 베른하르트 리만이다.리만은 1859년에 베를린학술원에 가입하면서 관례에 따라 논문 한 편을 제출했는데, 이 논문이 바로 이후 정수론의 역사에 지대한 영향을 미친 <주어진 수보다 작은 소수의 개수에 관하여>이다. 이 논문에서 리만은 그의 제타 함수를 소개하고, '실수부가 1 초과'라는 제한 조건이 붙어 있었던 함수를 확장시켜[5] 1이 아닌 모든 복소수에 대해 정의하였다. 또한 놀랍게도 리만은 이 함수의 영점을 소수세기함수와 연관시켰다.
이에 대해 조금 살펴보면, 리만은 다음과 같은 함수를 정의하였다.
[math(\displaystyle \begin{aligned}
f(x) = \sum_{i=1}^\infty \frac1i \pi(x^{1/i})
\end{aligned} )]
이 함수는 무한급수처럼 보이는데, 사실 [math(i)]가 [math(\log_2 x)]보다 크면 [math(\pi(x^{1/i}))]가 0이 되기 때문에 유한합만으로 끝난다. 리만은 이 함수와 제타 함수의 근들을 다음과 같이 연관지었다.
[math(\displaystyle \begin{aligned} f(x) = \operatorname{li}(x) -\sum_p \operatorname{li}(x^p) -\log2 +\int_x^\infty \frac{{\rm d}t}{t(t^2-1) \log t} \end{aligned} )] |
[math(\displaystyle \begin{aligned}
\pi_0(x) = \sum_{n=1}^\infty \frac{\mu(n)f(x^{1/n})}n
\end{aligned} )]
[math(\pi_0(x) = \lim\limits_{h\to0} \dfrac{\pi(x+h)+\pi(x-h)}2)]이다. 여기서 우리는 다음을 알 수 있다: 소수세기함수는 [math(f)]를 이용해서 나타낼 수 있고, [math(f)]는 리만 제타 함수의 근을 통해 계산된다. 그렇다면, 리만 제타 함수의 근에 대한 정보를 충분히 안다면, 소수세기함수를 근사할 수 있다!
실제로 리만은 리만 제타 함수의 비자명근의 실수부가 모두 [math(\dfrac12)]이라면 소수 정리가 성립함을 보였는데, 이것이 그 유명한 리만 가설이다. 그 이후로 소수 정리를 연구하는 수학자들은 리만 가설을 공략하기 시작했고, 모두들 알듯 아직 풀리지 않고 있다.
그 이후, 1895년, 독일의 수학자 한스 폰 망골트는 리만의 방법론을 체비쇼프 프사이([math(\psi)]) 함수에 적용해서 망골트 명시식(Mangoldt explicit formula)을 만들었다.
[math(\displaystyle \begin{aligned} \psi_0(x) = x -\sum_\rho \frac{x^\rho}\rho -\log(2\pi) -\frac{\log(1-x^{-2})}2 \end{aligned} )] |
이것을 증명한 것이 바로 자크 아디마르와 발레 푸생이고, 이들은 1896년 각각 독립적으로 리만 제타 함수의 근의 실수부는 [math(1)]보다 작음을 증명했고,[6] 해석학적 디테일을 추가해 증명을 완료하였다. 재밌는 것은, 이것을 증명하는 핵심 아이디어 중 하나는 [math(3+4\cos x+\cos2x = 2(1+\cos x)^2 \ge 0)]이라는, 고등학생도 증명할 수 있는 공식이라는 것이다.
3. 증명
3.1. 해석적 증명
망골트 근사식의 증명부터 살펴보자. 다음 식에서 시작한다.[math(\displaystyle
\zeta(s) = \prod_p \!\left( 1-\frac1{p^s} \right)^{\!-1}
)]
양변에 로그를 취하고 미분하면 다음이 나온다.
[math(\displaystyle
-\frac{\zeta'(s)}{\zeta(s)} = \sum_{n=1}^\infty \Lambda(n) \,n^{-s}
)]
여기서 [math(\Lambda(n))]은 [math(n)]이 소수 [math(p)]의 거듭제곱일 때만 [math(log p)]의 값을 가지는 함수이다. 이제 다음과 같은 페론의 공식(Perron's formula)을 이용하자.
[math(\displaystyle \begin{aligned} \frac1{2\pi i} \int_{\sigma_0-i\infty}^{\sigma_0+i\infty} \frac{x^s}s g(s) \,{\rm d}s = A(x), \quad \sigma_0>0 \end{aligned} )] |
이제 [math(a(n)=\Lambda(n))]을 대입해보자. 그러면 [math(\displaystyle \sum_{m\le x} \Lambda(m) = \psi(x))]이고 [math(\displaystyle -\frac{\zeta'(s)}{\zeta(s)} = \sum_{n=1}^\infty \Lambda(n)n^{-s})]이므로 페론의 공식에 대입하면
[math(\displaystyle
\psi_0(x) = -\frac1{2\pi i} \int_{\sigma_0-i\infty}^{\sigma_0+i\infty} \frac{\zeta'(s)}{\zeta(s)} \frac{x^s}s \,{\rm d}s
)]
가 나오며, 제한된 크기를 가지고 있는 오차항 [math(R)]에 대해
[math(\displaystyle \begin{aligned} \psi_0(x) = -\frac1{2\pi i} \int_{\sigma_0-iT}^{\sigma_0+iT} \frac{\zeta'(s)}{\zeta(s)} \frac{x^s}s \,{\rm d}s +R(x, T, \sigma_0) \end{aligned} )] |
[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(C)]는 [math(\sigma_0-iT)], [math(\sigma_0+iT)], [math(K-iT)], [math(K+iT)]를 꼭짓점으로 가지는 사각형이다. 이제 [math(C)]에 대한 적분 유수정리를 이용하여 계산하고, 나머지 적분과 오차항이 얼마나 큰지 분석하고, [math(K)], [math(T)]를 모두 무한대로 보내면 망골트 근사식이 증명된다. 이제 제타 함수의 비자명근의 실수부가 [math(1)]보다 작음을 증명하자. [math(0)]과 [math(1)] 사이인 것부터 보이자. 제타 함수에 로그를 씌우면 다음과 같음을 보일 수 있다.
[math(\displaystyle \begin{aligned}
\zeta(s) &= \exp \!\left( \sum_p \sum_{m=1}^\infty \frac1{mp^{ms}} \right) \\
&= \exp \!\left( \sum_p \sum_{m=1}^\infty \frac{e^{-imt\log p}}{mp^{m\sigma}} \right)
\end{aligned} )]
여기서 [math(\sigma)]는 [math(s)]의 실수부분이며, [math(t)]는 허수부분이다. 이를 통해 다음을 보일 수 있다.
[math(\displaystyle \begin{aligned}
이것을 [math(\sigma)], [math(\sigma+it)], [math(\sigma+2it)]에 대해 적용하면 다음 식을 얻는다.
[math(\displaystyle \begin{aligned} &|\zeta(\sigma)|^3 \,|\zeta(\sigma+it)|^4 \,|\zeta(\sigma+2it)| \\ = &\exp \!\left( \sum_p \sum_{m=1}^\infty \frac{3 +4\cos(mt\log p) +\cos(2mt\log p)}{mp^{m\sigma}} \right) \\ = &\exp \!\left( \sum_p \sum_{m=1}^\infty \frac{(1+2\cos(mt\log p))^2}{mp^{m\sigma}} \right) \\ \ge &1 \end{aligned} )] |
따라서 [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 \begin{aligned} \sum_{p\le x} \log^2p +\sum_{pq\le x} \log p\log q = 2x\log x +O(x) \end{aligned} )] |
4. 오차
소수 정리로 인해 [math(\pi(x) \sim \dfrac x{\log x})]인 것은 알았지만, 두 값은 얼마나 차이날까?이 질문을 던지기 전에 하나 명시해야 할 것이 있다. 현대에는 [math(\pi(x))]를 근사할 때 [math(\dfrac x{\log x})]대신 [math(operatorname{li}(x))]를 사용한다. 왜냐하면 후자가 더 정밀도가 높기 때문이다.[7] [math(\operatorname{li}(x))]는 [math(\dfrac x{\log x})]와도 값이 유사하기 때문에 [math(\pi(x) \sim \operatorname{li}(x))]라는 것은 쉽게 증명할 수 있다. 그렇다면, 얼마나 차이날까?
우선 [math(1)] 근방을 살펴보자. [math(\pi(1))]은 당연히 [math(0)]으로 맞아 떨어진다. 그런데 [math(\operatorname{li}(1))]은...
게다가 초기 정의인 [math(\dfrac x{\log x})]는 더한데, [math(displaystyle lim_{xto1^-} dfrac x{log x} = -infty, lim_{xto1^+} dfrac x{log x} = infty)]로 극한값 부호가 반대이다. 더구나 그래프 개형을 보듯 [math(\dfrac2{\log 2} > \dfrac3{\log 3})]으로 소수 계량 함수의 함숫값과 괴리가 꽤 크다.
이렇듯, [math(1)] 근방의 상대적으로 작은 수에서는 소수 계량 함수와의 차이가 큼을 알 수 있다. 애시당초 점근급수의 특징상 작은 수에서의 오차는 당연하다. 스털링 근사와 마찬가지.
사실 이 질문은 굉장히 중요한 질문이다. 아래의 영향 문단에서 설명하겠지만, 소수의 개수를 정확히 근사하는 것은 현대 정수론에서 매우 중요한 문제이다. 특히, 적당한 상수 [math(C)]에 대해 [math(|\pi(x)-\operatorname{li}(x)| < C\sqrt x\log x)]라는 것은 리만 가설과 동치이다!
발레 푸생은 소수 정리를 증명하면서 적당한 상수 [math(a)], [math(C)]에 대해 [math(|\pi(x)-\operatorname{li}(x)| < C \dfrac x{\log x} e^{-a\sqrt{\log x}})]라는 것을 증명했으며, 현재 가장 좋은 오차항은 이 논문을 참고하자. 보면 알겠지만 리만 가설에서 요구하는 오차항까지는 아직 한참 멀었다.
5. 영향
현대 '해석적 정수론'[8]의 대부분은 소수 정리가 없으면 성립되지 않는다. 소수와 관련된 모든 정리들은 소수 정리를 기반으로 두고 있다고 해도 과언이 아니다. 거의 모든 소수 관련 문제가 결국은 '그래서 소수가 얼마나 많이 있는데?'라는 질문으로 연결되니...소수 정리에서 직접적으로 나오는 결과들을 꼽자면, '[math(x)] 이하의 소수의 밀도는 대략 [math(\dfrac1{\log x})]이다.'와 '[math(n)]번째 소수는 대략 [math(n\log n)]이다.'가 있다. 이 두 사실 모두 초등 정수론으로는 상상도 못할 결과라는 것을 생각해보면, 소수정리가 얼마나 대단한지 할 수 있을 것이다.
초등적인 방법의 해석적 정수론만 쓴 체비쇼프가 1854년 논문집 "Memoires de l'Academie des Sciences de Saint Pétersbourg"에서 [math(\lim\limits_{x\to\infty} \dfrac{\pi(x)\log x}x)]의 하극한은 0.992 이상, 상극한은 1.105이하임을 증명했으나, 소수정리의 정밀함에 비할 바는 못 된다.
또한 소수 계량 함수와 로그 적분 함수를 다루는 과정에서 스큐스 수라는 것이 튀어나오기도 했다.
6. 확장
등차수열 버전으로 지겔-발피시 정리(Siegel-Walfisz theorem)가 있다.| 적당한 상수 [math(B)]와 주어진 양수 [math(A)]에 대해 [math(q \le (\log x)^A)]이고 [math((a,q)=1)]이면, 적당한 상수 [math(C)]가 있어 [math(\left| \psi(x;q,a) -\dfrac x{\varphi(q)} \right| < C x \exp \!\left( -B\sqrt{\log x} \right))]이다. |
여기서 [math(\psi(x;q,a))]는 [math(q)]로 나눈 나머지가 [math(a)]인 소수에 대해서만 [math(\psi)]를 세 준 것이다. 이 정리는 비노그라도프(Vinogradov)의 "충분히 큰 수에 대한 홀수 골드바흐 추측 증명"에도 쓰인 중요한 정리이다!
Prime ideal 버전으로는 Landau prime ideal theorem이 있다.
| 대수적 수체에서 노름이 [math(x)] 이하인 prime ideal의 개수는 대략 [math(\dfrac x{\log x})]개이다. |
기약다항식 버전도 있다! 이것은 prime polynomial theorem이라고 불린다.
| 원소가 [math(q)]개인 유한체에서 차수가 [math(n)] 이하인 일계수 기약다항식의 개수를 [math(\pi_q(n))]이라고 했을 때 [math(\left| \pi_q(n)-\dfrac{q^n}n \right| < C \dfrac{q^{n/2}}n)]이다. |
측지선[9] 버전의 prime geodesic theorem도 있다. 소수 정리의 초등적 증명을 한 아틀레 셀베르그가 필즈상을 받은 후에 연구한 '셀베르그 트레이스 공식'에 기반한다.[10]
처음 두 정리는 모두 증명 방법이 비슷한데,[11] 각각 적당한 제타 함수를 정의해준 다음 소수 정리에서 썼던 것과 비슷한 방법을 쓴다. 지겔-발피시에서는 디리클레 L함수를, Landau에서는 데데킨트 제타 함수를. 측지선의 경우도 비슷한 방법을 쓰는데, 문제는 다른 제타함수들처럼 '좋은 성질'을 가진 제타를 정의하는 것이다.[12]
[1] 이 문서 전체에서 [math(\log x)]는 자연로그를 의미한다. 고등학교 수학과 달리, 대부분의 순수수학에서는 상용로그를 전혀 쓰지 않고, [math(\log x)]는 자연로그를 의미한다.[2] [math(\sim)]은 점근 표기법의 일종으로, 일반적으로 [math(f\sim g)]는 두 함수의 비가 [math(1)]로 수렴함을 의미한다.[3] 오차항 관련 문단 참고. [math(1.08366)]이라는 예측치가 나온 이유는, 비교적 작은 [math(x)]([math(x<100000)])에 대해서는 그럴듯하게 보이기 때문.[4] 아래의 식에서 [math(O)]는 점근 표기법이다.[5] 이 확장을 해석적 연속이라고 부른다. 이게 가능한 이유는 복소함수의 성질 중 "어떤 영역에서 정의된 정칙함수를 더 큰 영역으로 확장하는 정칙함수가 존재한다면, 이는 유일하다."는 특수한 성질이 존재하기 때문이다.[6] 제타함수의 비자명근의 실수부는 항상 [math(0)] 초과 [math(1)] 미만이므로, 제타함수의 특징에 의해 리만 제타함수에서 모든 비자명근의 실수부는 [math(0)]과 [math(1)] 사이에 존재한다는 것을 증명한 것도 된다.[7] [math(x \ge 599)]이면 [math(\pi(x)-\dfrac x{\log x} > \dfrac x{\log^2x})]임이 알려져 있으므로, 전자와의 차이는 무한대로 발산한다. 반면 후자와의 차이는 부호가 무한히 뒤바뀐다는 것이 증명되었고, 그 첫 번째 역전이 일어나는 수가 바로 스큐스 수다.[8] Modular form 등의 대수적인 테크닉이 적은 순수한 해석적 정수론을 말하는 것이다.[9] 어떤 공간에서, 두 점을 잇는 최단거리 경로를 측지선이라고 한다.[10] 이 공식은 랭글랜즈 프로그램에 영감을 준 중요한 주제 중의 하나이며, 테렌스 타오는 이를 셀베르그의 가장 큰 업적이라고도 언급하였다.[11] 세 번째 정리는 훨씬 쉽게 증명할 수 있다. 몽고메리와 본(Montgomery & Vaughan)의 "Multiplicative Number Theory" 1장의 연습문제 혹은 마이클 로젠(Michael Rosen)의 "Number Theory in Function Fields"의 2장 참고.[12] 제타 함수가 그렇게 많냐고 할 수도 있는데, 이만큼 있다...