3.1 소수의 분포 & 체비셰프 함수 실전 예제 10선
소수 계량 함수 $\pi(x)$의 점근적 거동과 리만 제타 함수로 이어지는 가중치 함수 $\psi(x), \theta(x)$의 관계를 증명과 예제를 통해 이해합니다.
Ex 1. 소수 정리 (PNT) 추정
문제: 소수 정리를 이용하여 $10^{10}$ 이하의 소수의 개수를 근사하고, 임의의 수 $n$이 소수일 확률을 구하시오.
$\pi(x) \sim \frac{x}{\ln x}$ 에 의해, $\pi(10^{10}) \approx \frac{10^{10}}{\ln 10^{10}} = \frac{10^{10}}{10 \ln 10} \approx \frac{10^9}{2.3025} \approx 434,294,481$ 개이다.
임의의 수 $n$ 근처에서 소수가 나타날 확률은 밀도 함수인 $1/\ln n$ 에 수렴한다.
Ex 2. n번째 소수 $p_n$의 점근식
문제: 소수 정리 $\pi(x) \sim x/\ln x$로부터 $p_n \sim n \ln n$임을 유도하시오.
$n = \pi(p_n) \sim \frac{p_n}{\ln p_n}$ 이다. 양변에 로그를 취하면 $\ln n \sim \ln p_n - \ln(\ln p_n) \sim \ln p_n$.
이를 원래 식의 분모에 대입하면 $n \sim \frac{p_n}{\ln n}$ 이 되므로, $p_n \sim n \ln n$ 이 유도된다.
Ex 3. Von Mangoldt 함수 $\Lambda(n)$
문제: $\sum_{d|n} \Lambda(d) = \ln n$ 임을 증명하시오.
$n = \prod p_i^{a_i}$ 라 하면 $\ln n = \sum a_i \ln p_i$ 이다.
$\sum_{d|n} \Lambda(d)$ 에서 $\Lambda(d)$가 0이 아닌 경우는 $d = p_i^k$ ($1 \le k \le a_i$) 일 때뿐이다.
따라서 $\sum_{d|n} \Lambda(d) = \sum_i \sum_{k=1}^{a_i} \Lambda(p_i^k) = \sum_i \sum_{k=1}^{a_i} \ln p_i = \sum_i a_i \ln p_i = \ln n$.
Ex 4. $\psi(x)$와 $\theta(x)$의 관계
문제: $\psi(x) = \sum_{k=1}^{\infty} \theta(x^{1/k})$ 임을 보이시오.
$\psi(x) = \sum_{p^k \le x} \ln p$ 이다. 지수 $k$를 고정하면 $p \le x^{1/k}$ 인 소수들에 대해 $\ln p$를 더하는 것이 된다.
이는 $\theta(x^{1/k})$의 정의와 같으므로, 모든 가능한 $k$에 대해 합산하면 $\psi(x) = \theta(x) + \theta(x^{1/2}) + \theta(x^{1/3}) + \dots$ 가 된다.
Ex 5. Bertrand's Postulate 확인
문제: $n < p \le 2n$ 사이에 소수가 항상 존재함을 이용하여, $n=100$일 때 이를 만족하는 소수를 3개 이상 찾으시오.
범위는 $100 < p \le 200$ 이다.
이 구간의 소수는 $101, 103, 107, 109, 113, \dots$ 등이 존재하며, 체비셰프는 이를 일반적인 $n$에 대해 증명하였다.
Ex 6. $\pi(x)$와 $\theta(x)$의 연결
문제: $\theta(x) = \pi(x) \ln x - \int_2^x \frac{\pi(t)}{t} dt$ 임을 보이시오.
$\theta(x) = \sum_{p \le x} \ln p$ 이다. $a_n$을 $n$이 소수면 1, 아니면 0이라 할 때 $\theta(x) = \sum_{n \le x} a_n \ln n$ 이다.
$\pi(x) = \sum_{n \le x} a_n$ 이므로 아벨 합 공식 $\sum a_n f(n) = A(x)f(x) - \int A(t)f'(t)dt$ 를 적용하면 위 식을 얻는다.
Ex 7. Mertens의 제2정리
문제: $\sum_{p \le x} \frac{1}{p}$ 의 점근적 크기가 $\ln(\ln x)$ 임을 설명하시오.
$\pi(x) \sim x/\ln x$ 이므로 $\sum_{p \le x} \frac{1}{p} \approx \int_2^x \frac{1}{t \ln t} dt$ 이다.
$u = \ln t$ 로 치환하면 $\int \frac{1}{u} du = \ln u = \ln(\ln t)$ 가 된다.
$\therefore \sum_{p \le x} \frac{1}{p} = \ln(\ln x) + M + O(1/\ln x)$ (여기서 $M$은 메르텐스 상수).
Ex 8. $\theta(x) < (2 \ln 2)x$ 증명 맛보기
문제: 이항계수 $\binom{2n}{n}$을 이용하여 $\theta(2n) - \theta(n)$의 상계를 구하시오.
$\prod_{n < p \le 2n} p$ 는 $\binom{2n}{n}$을 나눈다.
$\binom{2n}{n} < 2^{2n}$ 이므로, 로그를 취하면 $\sum_{n < p \le 2n} \ln p = \theta(2n) - \theta(n) < 2n \ln 2$ 가 성립한다.
이러한 상한과 하한의 결정은 소수 정리 증명의 기초가 된다.
Ex 9. 임의로 큰 소수 간격
문제: 소수가 존재하지 않는 연속된 정수 $k$개를 구성하시오.
$(k+1)! + 2, (k+1)! + 3, \dots, (k+1)! + (k+1)$ 의 연속된 $k$개 정수를 생각하자.
각 항은 $2, 3, \dots, k+1$ 로 나누어떨어지는 합성수이다.
따라서 소수 사이의 간격은 무한히 커질 수 있다.
Ex 10. $\psi(x)$의 명시적 공식 (Explicit Formula)
문제: 리만 가설이 참일 때 $|\psi(x) - x|$의 크기는 어떠한가?
리만의 명시적 공식에 따르면 $\psi(x) = x - \sum_{\rho} \frac{x^\rho}{\rho} - \ln(2\pi)$ 이다.
여기서 $\rho$는 제타 함수의 비자명 영점이다. 리만 가설이 참이면 모든 $\text{Re}(\rho) = 1/2$ 이므로,
오차항은 대략 $x^{1/2}$의 차수를 갖는다. 즉, $|\psi(x) - x| = O(\sqrt{x} \ln^2 x)$.