디리클레 정리의 증명 part 1 : some asymptotic formulas

예고[1]한 대로, 디리클레 정리의 증명을 하기위해서는 물밑작업을 좀 할 필요가 있다. 먼저 핵심적인 기호의 의미와 사용법에 대해 설명하면 다음과 같다.

 


별 말이 없으면, p 는 소수, k, m, n 은 자연수, x 는 양의 실수 값만을 취하는 변수들이다. 그리하여 \sum_{n \le x} 1/n 라고 쓰면 주어진 양의 실수 x에 대해 x 이하의 모든 자연수의 역수의 합을 의미하게 된다. 또한 \sum_{p \le x} 1/p 라고 쓰면 x 이하의 모든 소수의 역수의 합을 의미하게 된다. 마찬가지로 \sum_{d | n} 의 의미는 주어진 자연수 n을 나누는 모든 약수에 대한 합을 구하라는 의미이다.

꺾은 괄호 [ ] 는 바닥함수(floor function)을 의미한다. 즉, 괄호안의 주어진 실수를 넘지 않는 최대의 정수값을 갖는다.

Big O notation에 대해서는 이미 들어본 일이 있을 것이다. 일전에 포스트[2]한 소수정리에 대한 내용에서도 소개한 적이 있다. 즉, 두 함수 fg 사이에 정의역안의 모든 값 x 에 대해 상수 C가 존재하여 f(x) \le C | g(x) |가 항상 성립하면 두 함수는 다음과 같이 쓴다.

f = O(g)

또한, f - g = O(h) 가 성립하면 f = g + O(h) 라고 흔히 쓴다. 엄밀히 말해서 모두 좀 모호하거나 말이 안 되는 표현들인데, 정수론에서 대단히 흔하게 쓰이는 표기이므로 넘어가자. ㅋ

\mu(n)Möbius function이다. 자연수 n에 대해, 제곱수로 나누어 떨어지면 값이 영이 되고, square-free일 경우 소인수의 개수가 홀수개이면 -1, 짝수개이면 1의 값을 가진다. 1일 때는 1이다.

\Lambda(n)Mangoldt function이다. 자연수 n이 어느 소수 p의 거듭제곱이면 \log p, 나머지 경우에는 영의 값을 가진다.

이해를 돕기위해 10 이하의 자연수에 대해 위 함수들의 값을 써 보면 다음과 같다.

n 1 2 3 4 5 6 7 8 9 10
\mu(n) 1 -1 -1 0 -1 1 -1 0 0 1
\Lambda(n) 0 log 2 log 3 log 2 log 5 0 log 7 log 2 log 3 0

다음 등식이 성립한다.

\displaystyle \Lambda(n) = \sum_{d | n} \mu(d)\log\frac{n}{d}

어렵지 않으므로 왜 그런지 각자 생각해보시라. ㅎㅎ

소수 p 에 대해 n을 나누는 p의 최고 지수를 v_p (n) 이라고 하자. 즉, p^kn을 나누지만, p^{k+1}n을 나누지 않으면 k= v_p (n) 이다.

 


이번 포스트의 목표는 다음 공식이다.

1 theorem > (Chebyshev)

\displaystyle \sum_{n \le x} \Lambda(n) = O(x)

사실 이보다 더 강력한 정리인 \lim_{x \to \infty}\sum_{n \le x} \Lambda(n) / x =1 를 이전의 소수정리를 증명할 때[3] 이미 하였는데, 그걸 그대로 가져다 쓰려니, 읽는 사람이 이전 포스트를 모두 읽어야 한다는 부담이 있을 듯 하여, 이 약한 형태를 간단하게 재증명해 보겠다.

보통 위 정리 1을 증명할 때, 많은 해석적 정수론이나 초등 정수론 책에서는 \sum_{n \le x} \Lambda(n)\sum_{p \le x} \log p 그리고 \pi(x)\log x의 asymptotic behavior가 일치하다는 내용으로 증명을 이끌어간다. 그래야 뒤의 소수 정리의 증명에서 써먹을 수 있기 때문이다. 그러나 본 포스트에서는 거기까지 필요하지 않으므로 책의 내용을 조금 수정하여 나름대로 정리해보았다. 본 포스트에서 쓰인 증명의 테크닉들은 모두 apostol 책[4], nathanson 책[5] 등의 책에서 찾아볼 수 있음을 알려둔다.

2 theorem >

\displaystyle v_p (n!) = \sum_{m=1}^{\infty} \left[ \frac{n}{p^m} \right]

이건 뭐 사실 중고교 시험문제에서도 흔히 쓰이는 정리이다. 100!을 십진법으로 나타냈을 때, 마지막에 연속되는 영이 몇 개 나오는가? 하는 형태로 종종 출제되기도 한다. ㅎㅎ 팩토리얼의 지수를 알고 싶을 때, 원하는 소수의 거듭제곱으로 계속 나누어준 후, 그 합을 구하면 되는 것이다. 간단하니 굳이 증명이 필요없을 듯 하다.

소수와 관련된 정리들 중 많은 중요한 출발은 Central binomial coefficient에서 시작한다.

3 theorem >

\displaystyle {{2n}\choose{n}} < 4^n

3-1 proof of theorem 3 >
용어의 정의 그대로 (1+1)^{2n} 를 이항전개하면 가운데 항이 바로 Central binomial coefficient가 된다. 그러므로 부등식이 성립한다.

4 theorem >

\displaystyle \prod_{n < p^m \le 2n} p < {{2n}\choose{n}}

4-1 proof of theorem 4 >
위 부등식에서 좌변의 의미는 소수 p 를 거듭제곱하여 n < p^m \le 2n 을 만족하는 m이 존재하는 소수들을 모두 곱한다는 의미이다. 물론 이 곱셈 안에는 n2n 사이의 모든 소수도 포함된다.

정리 2에 의해 다음이 성립함에 주목해보자.

\displaystyle v_p \left({{2n}\choose{n}}\right) = v_p \left(\frac{(2n)!}{(n!)^2}\right) = v_p ((2n)!) - 2v_p (n!) = \sum_{m=1}^{\infty}\left(\left[\frac{2n}{p^m}\right] - 2\left[\frac{n}{p^m}\right]\right)

모든 실수 x 에 대해 [2x] - 2[x] 의 값은 0 또는 1이 된다. 그리고 n < p^m \le 2n 를 만족하는 모든 소수에 대해 \left[\frac{2n}{p^m}\right] =1 이지만 \left[\frac{n}{p^m}\right] =0 이므로 v_p \left({{2n}\choose{n}}\right) \ge 1 이라는 것을 알 수 있다. 즉, 증명하고자 하는 부등식의 좌변에 있는 모든 소수를 우변이 가지고 있음을 알 수 있다.

5 proof of theorem 1 >
자, 이제 이번 포스트의 목표를 증명해 보겠다.
정리 3과 4에 의해 다음이 성립한다.

\displaystyle \prod_{n < p^m \le 2n} p < 4^n

k \ge 1 일 때, n = 2^{k-1} 이라고 두면,

\displaystyle \prod_{2^{k-1} < p^m \le 2^k} p < 2^{2^k}

그러므로 모든 자연수 r 에 대해,

\displaystyle \prod_{p^m \le 2^r} p = \prod_{k=1}^{r}\;\prod_{2^{k-1} < p^m \le 2^k} p < \prod_{k=1}^{r} 2^{2^k} < 2^{2^{r+1}}

2보다 큰 임의의 실수 x는 어느 두 2의 거듭제곱에 끼인다. 즉, 자연수 r이 존재하여 다음이 성립한다.

\displaystyle 2^{r-1} < x \le 2^r

그러므로 다음 부등식이 성립한다.

\displaystyle \prod_{p^m \le x} p \le \prod_{p^m \le 2^r} p < 2^{2^{r+1}} < 2^{4x}

따라서 양변에 로그를 씌우면

\displaystyle \sum_{n \le x} \Lambda(n) < (4 \log 2)x

가 성립한다. 그러므로 원하는 asymptotic relation을 얻을 수 있다.

 


[1] 내 백과사전 디리클레 정리의 증명 : 서론 2010년 9월 2일
[2] 내 백과사전 소수정리의 증명 : part 1 물밑작업 2010년 3월 2일
[3] 내 백과사전 소수정리의 증명 : part 2-2 해석적 증명 2010년 3월 6일
[4] Tom M. Apostol, Introduction to analytic number theory 1권, Springer, 1998
[5] Melvyn B. Nathanson, Additive Number Theory: the Classical Bases. Graduate Texts in Mathematics. 164. Springer-Verlag. ISBN 0-387-94656-X, 1996

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중