Generalized Möbius inversion formula

이 정리는 상당히 유용하게 쓰이므로 별도의 포스트로 만들어 둔다.

 


1. theorem > Möbius inversion formula
두 수론적 함수(arithmetic function) f(n), g(n)가 다음과 같은 등식을 만족한다고 하자.

\displaystyle g(n) = \sum_{d \mid n}f(d)

이때, 다음 등식이 성립한다.

\displaystyle f(n) = \sum_{d \mid n}\mu(d)g\left(\frac{n}{d}\right)

물론 여기서 \mu(n)Möbius function이다.

2. direction >
위 정리는 Dirichlet convolution으로 표현하면, 주어진 등식은 모든 값이 1인 수론적 함수와 f(n)과의 convolution이 g(n)이라고 볼 수 있다. 즉,

g = f * 1

수론적 함수는 Dirichlet convolution을 연산으로 group을 이루며, 모든 값이 1인 수론적 함수의 역원은 Möbius function이다. 따라서 양변에 Möbius function을 취해주면 원하는 등식이 나온다. 즉,

f = g * \mu

보통 뫼비우스 반전공식(Möbius inversion formula)이라고 부를 때는 위 정리를 말하는데, 주어진 값의 약수에 대한 합이 아닌, 모든 자연수에 대한 합으로 하는 아래와 같은 버전이 있다.

3. theorem > generalized Möbius inversion formula
어떤 Completely multiplicative arithmetic function \alpha(n) 과 양의 실수에서 정의된 함수 F(x)가 주어져 있다고 하자. 이 주어진 함수를 이용하여 G(x)를 다음과 같이 정의한다.

\displaystyle G(x) = \sum_{n\le x}\alpha(n)F\left(\frac{x}{n}\right)

그러면 다음 등식이 성립하고, 그 역도 성립한다.

\displaystyle F(x) = \sum_{n\le x}\mu(n)\alpha(n)G\left(\frac{x}{n}\right)

3-1. proof of theorem 3 >
사실 이건 포함-배제의 원리(Inclusion–exclusion principle)를 이용하면 간단하게 보일 수 있다. 다음 등식을 보자.

\displaystyle \begin{aligned} G(x) &= \sum_{n\le x}\alpha(n)F\left(\frac{x}{n}\right) \\ &= \alpha(1)F(x) + \alpha(2)F\left(\frac{x}{2}\right) + \alpha(3)F\left(\frac{x}{3}\right) + \cdots + \alpha([x])F\left(\frac{x}{[x]}\right)\end{aligned}

정의에 의해 위와 같이 계산된다. 물론 여기서 [x]는 넘지 않는 최대 정수를 표시하는 floor function을 가리킨다. 또한 G(x/2)는 다음과 같이 계산된다.

\displaystyle G\left(\frac{x}{2}\right) = \alpha(1)F\left(\frac{x}{2}\right) + \alpha(2)F\left(\frac{x}{4}\right) + \alpha(3)F\left(\frac{x}{6}\right) + \cdots + \alpha([x])F\left(\frac{x}{2[x]}\right)

자, 그리하여 뫼비우스 함수(Möbius function)의 값대로 더하고 빼면서 아래와 같이 계산해보면 쉽게 정리가 성립함을 이해할 수 있다.

\begin{smallmatrix} \alpha(1)G(x)\hfill & = &\alpha(1)F(x) & + & \alpha(2)F\left(\frac{x}{2}\right) & + & \alpha(3)F\left(\frac{x}{3}\right) & + & \alpha(4)F\left(\frac{x}{4}\right) & + & \alpha(5)F\left(\frac{x}{5}\right) & + & \alpha(6)F\left(\frac{x}{6}\right) & + \cdots \\ \alpha(2)G\left(\frac{x}{2}\right) & = & & & \alpha(2)F\left(\frac{x}{2}\right) & & & + & \alpha(4)F\left(\frac{x}{4}\right) & & & + & \alpha(6)F\left(\frac{x}{6}\right) & + \cdots \\ \alpha(3)G\left(\frac{x}{3}\right) & = & & & & & \alpha(3)F\left(\frac{x}{3}\right) & & & & & + & \alpha(6)F\left(\frac{x}{6}\right) & + \cdots \\ \alpha(4) G\left(\frac{x}{4}\right) & = & & & & & & & \alpha(4)F\left(\frac{x}{4}\right) & & & & & + \cdots \\  \alpha(5)G\left(\frac{x}{5}\right) & = & & & & & & & & & \alpha(5)F\left(\frac{x}{5}\right) & & & + \cdots \\ \alpha(6)G\left(\frac{x}{6}\right) & = & & & & & & & & & & & \alpha(6)F\left(\frac{x}{6}\right) & + \cdots \end{smallmatrix}

즉, F(x)를 재구성하기 위해서는 다음과 같이 계산해야 한다.

\displaystyle F(x) = \alpha(1)G(x) - \alpha(2)G\left(\frac{x}{2}\right) - \alpha(3)G\left(\frac{x}{3}\right) - \alpha(5)G\left(\frac{x}{5}\right) + \alpha(6)G\left(\frac{x}{6}\right) \cdots

따라서 원하는 정리가 성립함을 알 수 있다. 참고로 이 증명은 [1]에 있는 내용을 본인이 약간 수정한 것이다.

 


[1] N. Levinson, “A motivated account of an elementary proof of the prime number theorem”, Amer. Math. Monthly 76 (1969), 225-245.

답글 남기기

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

WordPress.com 로고

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

Twitter 사진

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

Facebook 사진

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

Google+ photo

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

%s에 연결하는 중