뫼비우스 반전 공식

수론에서, 뫼비우스 반전 공식(Möbius反轉公式, 영어: Möbius inversion formula)은 수론적 함수의 약수에 대한 합으로부터 원래 함수를 되찾는 공식이다.

정의

양의 정수의 집합 ${\mathbb{Z}}^{+}$을 정의역으로 하고, 가환환 $R$를 공역으로 하는 임의의 두 함수

$f,g:{\mathbb{Z}}^{+}\to R$

에 대하여, 다음 두 조건이 서로 동치이다.^{:32, Theorem 2.9}

$g(n)=\sum _{d\mid n}f(d)\mathrm{\forall }n\in {\mathbb{Z}}^{+}$

$f(n)=\sum _{d\mid n}\mu (d)g(n/d)\mathrm{\forall }n\in {\mathbb{Z}}^{+}$

이를 뫼비우스 반전 공식이라고 한다. 두 등식의 우변의 합은 $n$의 양의 약수 $d$에 대한 합이다. 가환환 $R$의 대표적인 예는 복소수체 $ℂ$이다. 첫째 등식은 $g(n)$을 모든 $d\mid n$에 대한 $f(d)$들의 합으로 나타낸다. 둘째 등식은 $f(n)$을 $g(n/d)$들의 정수 계수 선형 결합으로 나타낸다. 여기에 붙는 계수는 뫼비우스 함수 $\mu :{\mathbb{Z}}^{+}\to \mathbb{Z}$이며, 이는 정수 $-1,0,1$을 값으로 한다. (0개 이상의 서로 다른 소수 $p_1,\dots ,p_k$에 대하여

$\mu (p_1\dots p_k)=(-1{)}^k$

이며, 소수 $p$ 및 양의 정수 $n$에 대하여

$\mu (p^{2}n)=0$

이다.)

두 공식에서 $n$에 대한 전칭은 필수적이다. 만약 임의의 $n$에서 첫째 등식이 성립한다면 임의의 $n$에서 둘째 등식이 성립하며, 그 역도 성립한다. 그러나 어떤 $n$에서 첫째 등식이 성립한다고 하여 그 $n$에서 둘째 등식이 성립하지는 않으며, 그 역도 마찬가지다.

두 함수가 곱셈적 함수인지 여부는 서로 동치이다. 즉, 만약 $f$가 곱셈적 함수라면, 그 상 $g$ 역시 곱셈적 함수이다. 반대로 만약 $g$가 곱셈적이라면, 그 원상 $f$ 역시 곱셈적이다.

디리클레 합성곱과의 관계

가환환 $R$가 주어졌을 때, 두 함수 $f,g:{\mathbb{Z}}^{+}\to R$의 디리클레 합성곱

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

을 정의할 수 있으며, 함수 ${\mathbb{Z}}^{+}\to R$의 집합 $R^{{\mathbb{Z}}^{+}}$은 점별 덧셈과 디리클레 합성곱에 대하여 가환환을 이룬다.

디리클레 합성곱을 사용하여, 뫼비우스 반전 공식의 첫째 등식을 다음과 같이 쓸 수 있다.

$g=1*f$

여기서 1은 모든 양의 정수를 가환환의 곱셈 항등원 $1\in A$로 보내는 상수 함수를 나타낸다. 마찬가지로, 둘째 등식은 다음과 같이 쓸 수 있다.

$f=\mu *g$

여기서 $\mu$는 뫼비우스 함수와 유일한 환 준동형 $\mathbb{Z}\to R$의 합성이며, 여기서는 뫼비우스 함수와 같은 기호로 나타낸다. 뫼비우스 반전 공식에 따르면, 두 등식이 서로 동치이다.

가환환 $(R^{{\mathbb{Z}}^{+}},+,*)$에서, 1과 $\mu$는 서로 곱셈 역원이다.

$\mu *1=\delta$

여기서

$\delta (n)=\{\begin{array}{cc}1& n=1\\ 0& n\ne 1\end{array}$

는 $({\mathbb{Z}}^{{\mathbb{Z}}^{+}},+,*)$의 곱셈 항등원이다. 이는 뫼비우스 반전 공식을 자명하게 함의한다. (즉, 만약 $g=1*f$라면

$\mu *g=\mu *(1*f)=(\mu *1)*f=\delta *f=f$

이며, 만약 $f=\mu *g$라면

$1*f=1*(\mu *g)=(1*\mu )*g=\delta *g=g$

이다.)

두 곱셈적 함수의 디리클레 합성곱은 곱셈적 함수이다. 또한, 1과 $\mu$ 모두 곱셈적 함수이다. 뫼비우스 반전 공식에 등장하는 두 함수의 곱셈적 함수 여부가 동치임은 이로부터 자명하다.

연속 정의역

조합론에서 자주 쓰이는 뫼비우스 반전 공식은 다음과 같다. 폐구간 $[1,\mathrm{\infty })$를 정의역으로 하고 아벨 군 $(A,+)$을 공역으로 하는 임의의 두 함수 $f,g:[1,\mathrm{\infty })\to A$에 대하여, 다음 두 조건이 서로 동치이다.

$G(x)=\sum _{\genfrac{}{}{0ex}{}{1\le n\le x}{n\in {\mathbb{Z}}^{+}}}F(x/n)\mathrm{\forall }x\in [1,\mathrm{\infty })$

$F(x)=\sum _{\genfrac{}{}{0ex}{}{1\le n\le x}{n\in {\mathbb{Z}}^{+}}}\mu (n)G(x/n)\mathrm{\forall }x\in [1,\mathrm{\infty })$

여기서 우변의 합은 $x$보다 작거나 같은 모든 양의 정수 $n$에 대한 합이다.

근접 대수

섬네일을 만드는 중 오류 발생:  이 부분의 본문은 근접 대수입니다.

수론의 뫼비우스 반전 공식은 근접 대수에 대한 뫼비우스 반전 공식의 특수한 경우이다. 구체적으로, 양의 정수의 집합은 약수 관계에 따라 국소 유한 부분 순서 집합

$({\mathbb{Z}}^{+},\mid )$

$m\mid n⟺\mathrm{\exists }d\in {\mathbb{Z}}^{+}:n=md$

을 이룬다. $({\mathbb{Z}}^{+},\mid )$의 근접 대수에 대한 뫼비우스 반전 공식은 수론의 뫼비우스 반전 공식이다.

함수 $[1,\mathrm{\infty })\to R$에 대한 뫼비우스 반전 공식 역시 근접 대수에 대한 뫼비우스 반전 공식의 특수한 경우이다. 구체적으로, 국소 유한 부분 순서 집합

$([1,\mathrm{\infty }),⪯)$

$x⪯y⟺x\in {\mathbb{Z}}^{+}\wedge x\le y$

의 근접 대수에 대한 뫼비우스 반전 공식과 같다.

예

대표적인 예는 다음과 같다. (모두 복소수체 $ℂ$를 공역으로 한다.)

$f(n)$	$g(n)$
1	약수 함수 ${\sigma }_0(n)$
$n$	약수 함수 ${\sigma }_1(n)$
오일러 피 함수 $\varphi (n)$	$n$
뫼비우스 함수 $\mu (n)$	델타 함수 $\delta (n)$
$\mu (n)/n$	$\varphi (n)/n$
폰 망골트 함수 $\Lambda (n)$	자연로그 $\ln n$
$\cos (n\pi /2)$	방정식 $x^2+y^2=n$의 정수해의 개수의 1/4

역사

19세기 수학자 아우구스트 페르디난트 뫼비우스의 이름을 딴 공식이다.

같이 보기

• 페리 수열
• 포함배제의 원리

외부 링크

• 이철희. “뫼비우스 반전공식”. 《수학노트》. 
• “Möbius inversion” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Möbius inversion formula” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• “Möbius inversion” (영어). 《nLab》. 
• “Möbius inversion” (영어). 《PlanetMath》. 
• “Alternate proof of Möbius inversion formula” (영어). 《PlanetMath》.