뫼비우스 반전 공식

수론에서의 뫼비우스 반전 공식(Möbius inversion formula)은 19세기 수학자 아우구스트 페르디난트 뫼비우스의 이름을 딴 공식이다.

공식

g(n) 과 f(n)이 수론적 함수(arithmetic function)이며 1보다 큰 모든 $n$에 대해 다음이 성립한다고 하자.

$g(n)=\sum _{d\mid n}f(d)$

이 때, 1보다 큰 모든 $n$에 대해 다음이 성립한다.

$f(n)=\sum _{d\mid n}g(d)\mu (n/d)$

여기서 $\mu$는 뫼비우스 함수(Möbius function)이고, 덧셈은 n의 양의 약수 d 전체에 대해 이루어진다.

수론적 함수 $g$는 $f$의 누적으로 이루어지는데, 역으로 $g$를 통해 $f$를 꺼내는 공식이므로 반전 공식이라 불린다.

f와 g가 자연수에서 어떤 아벨 군으로의 함수일 때에도 공식은 성립한다.

디리클레 합성곱과의 관계

디리클레 합성곱(Dirichlet convolution)을 사용하여 공식을 써 보면 다음과 같다.

$g=f*1$

여기서 * 는 디리클레 합성곱이고, 1은 모든 $n$에 대해 항상 1인 수론적 함수이다. 이 경우,

$f=\mu *g.$

가 성립한다. 즉, 뫼비우스 함수는 모든 함수값이 1인 수론적 함수의 역원이기 때문이다. 당연하게도

$\mu *1=\epsilon$

이 성립한다. 여기서 $\epsilon$은 $n=1$일 때만 1이고 나머지는 모두 0인 수론적 함수이다. 다양한 수론적 함수의 계산의 예는 Apostol의 책을 참조하면 좋다.

일반화

조합론(combinatorics)에서 자주 쓰이는 동치의 진술은 다음과 같다.

F(x)와 G(x)가 구간 [1,∞)에서 복소수로의 함수이고, 1보다 크거나 같은 모든 $x$에 대해

$G(x)=\sum _{1\leq n\leq x}F(x/n)$

을 만족하면, 1보다 크거나 같은 모든 $x$에 대해

$F(x)=\sum _{1\leq n\leq x}\mu (n)G(x/n)$

이 성립한다.

여기서 합은 x보다 작거나 같은 모든 양의 정수 n에 대해서 이루어진다.