뫼비우스 반전 공식

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

정의

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

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

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

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

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

이를 뫼비우스 반전 공식이라고 한다. 두 등식의 우변의 합은 $n$ 의 양의 약수 $d$ 에 대한 합이다. 가환환 $R$ 의 대표적인 예는 복소수체 $\mathbb {C}$ 이다. 첫째 등식은 $g(n)$ 을 모든 $d\mid n$ 에 대한 $f(d)$ 들의 합으로 나타낸다. 둘째 등식은 $f(n)$ 을 $g(n/d)$ 들의 정수 계수 선형 결합으로 나타낸다. 여기에 붙는 계수는 뫼비우스 함수 $\mu \colon \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\colon \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{cases}1&n=1\\0&n\neq 1\end{cases}}

는 $(\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,\infty )$ 를 정의역으로 하고 아벨 군 $(A,+)$ 을 공역으로 하는 임의의 두 함수 $f,g\colon [1,\infty )\to A$ 에 대하여, 다음 두 조건이 서로 동치이다.

G(x)=\sum _{\scriptstyle 1\leq n\leq x \atop \scriptstyle n\in \mathbb {Z} ^{+}}F(x/n)\qquad \forall x\in [1,\infty )

F(x)=\sum _{\scriptstyle 1\leq n\leq x \atop \scriptstyle n\in \mathbb {Z} ^{+}}\mu (n)G(x/n)\qquad \forall x\in [1,\infty )

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

근접 대수

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

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

m\mid n\iff \exists d\in \mathbb {Z} ^{+}\colon n=md

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

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

([1,\infty ),\preceq )

x\preceq y\iff x\in \mathbb {Z} ^{+}\land x\leq y

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

예

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

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