뫼비우스 역공식(Möbius inversion formula)는 19세기의 수학자 오구스트 페르디난드 뫼비우스가 발견한 정수론과 관련된 공식이다. 자연수의 집합은 나누기 기호 "|"에 의해서 부분 순서 집합(Partially ordered set)이 되며, 좀 더 일반적인 부분 순서 집합 (P, ≤)에 대해서 확장적으로 정의될 수도 있다.
정수론에 관한 공식 : 우선 뫼비우스 역함수(Möbius Inversion function) μ(n)을 아래와 같이 정의한다.
[math]\displaystyle{ \mu(n) =\begin{cases} 1 & n=1 \\ 0 & { \exists p (p \in \mathbb{N} ~ \text{and} ~ p^2 | n) } \\ (-1)^r & n= p_1 p_2 \cdot \cdot \cdot p_r , p_i ~ \text{prime} \end{cases} }[/math]
그러면 산술함수(Arithmetic Function) f(n)과 F(n)에 대해서 아래 두 명제가 동치가 된다.
[math]\displaystyle{ F(n)= \sum_{d \vert n} f(d) \Leftrightarrow f(n) =\sum_{d \vert n} \mu(n/d) F(d) }[/math]
위의 공식은 디레클레 합성곱(Dirichlet Convolution) h(n)= (f*g)(n)=∑d|n f(d) g(n/d)을 이용하면 간단히 F=f*1 ↔ f=μ*F으로 표현할 수 있다.
이 뫼비우스의 반전공식은 국소적으로 유한한 부분순서집합에 대해서도 정의할 수 있다.
급수와 관련된 공식[편집 | 원본 편집]
두 수열 an, bn에 대해서 [math]\displaystyle{ a_n=\sum_{d\mid n} b_d }[/math]를 만족하면 뫼비우스의 반전공식에 의해서 [math]\displaystyle{ b_n=\sum_{d\mid n} \mu\left(\frac{n}{d}\right)a_d }[/math]도 성립한다.
이것은 [math]\displaystyle{ S(q)=\sum_{n=1}^\infty a_n \frac {q^n}{1-q^n} }[/math] 형태로 표현되는 람바르트 급수(영어 위키백과)의 아래의 공식과
- [math]\displaystyle{ \sum_{n=1}^\infty a_n x^n = \sum_{n=1}^\infty b_n \frac{x^n}{1-x^n} }[/math]
디레클레 급수의 아래의 공식과 관련이 있다. 여기서 ζ는 리만 제타 함수이다.
- [math]\displaystyle{ \sum_{n=1}^\infty \frac {a_n} {n^s} = \zeta(s)\sum_{n=1}^\infty \frac{b_n}{n^s} }[/math]
반복적으로 변환을 적용하기[편집 | 원본 편집]
정수함수에 대해서 약수의 합 함수 변환 f(n) → F(n)=∑d|nf(d)을 무한하게 적용하거나 반대로 역변환 F(n) → f(n)=∑d|nμ(n/d)F(d)을 무한하게 많이 적용할 수 있다.
- 일례로 φ를 오일러 피 함수라고 놓을 때
- φ ∗ 1 = I, 여기서 I(n) = n는 항등함수.
- I ∗ 1 = σ1 =σ, 약수의 합 함수가 된다.
한편으로는 뫼비우스 함수로부터 다음과 같이 반복적으로 변환을 적용할 수 있다.
- μ를 뫼비우스 함수로 놓는다.
- μ ∗ 1 = ε 여기서 ε는 아래와 같이 정의되는 함수이다.
- [math]\displaystyle{ \varepsilon(n) = \begin{cases} 1, & \mbox{if }n=1 \\ 0, & \mbox{if }n\gt 1 \end{cases} }[/math]
- ε ∗ 1 =}1, 즉 상수함수가 된다.
- 1 ∗ 1 = σ0 = d = τ 여기서τ는 n의 약수의 합을 반환하는 함수이다.
일례로 오일러 피 함수 φ로 시작해서 다음과 같이 무한히 많은 함수를 만들 수 있다.
- [math]\displaystyle{ f_n = \begin{cases} \underbrace{\mu * \ldots * \mu}_{-n \text{ factors}} * \varphi & \text{if } n \lt 0 \\[8px] \varphi & \text{if } n = 0 \\[8px] \varphi * \underbrace{\mathit{1}* \ldots * \mathit{1}}_{n \text{ factors}} & \text{if } n \gt 0 \end{cases} }[/math]
일반화[편집 | 원본 편집]
A related inversion formula more useful in combinatorics is as follows: suppose 틀:Math and 틀:Math are complex-valued functions defined on the interval 틀:Math such that
- [math]\displaystyle{ G(x) = \sum_{1 \le n \le x}F\left(\frac{x}{n}\right)\quad\mbox{ for all }x\ge 1 }[/math]
then
- [math]\displaystyle{ F(x) = \sum_{1 \le n \le x}\mu(n)G\left(\frac{x}{n}\right)\quad\mbox{ for all }x\ge 1. }[/math]
Here the sums extend over all positive integers 틀:Mvar which are less than or equal to 틀:Mvar.
This in turn is a special case of a more general form. If 틀:Math is an arithmetic function possessing a Dirichlet inverse 틀:Math, then if one defines
- [math]\displaystyle{ G(x) = \sum_{1 \le n \le x}\alpha (n) F\left(\frac{x}{n}\right)\quad\mbox{ for all }x\ge 1 }[/math]
then
- [math]\displaystyle{ F(x) = \sum_{1 \le n \le x}\alpha^{-1}(n)G\left(\frac{x}{n}\right)\quad\mbox{ for all }x\ge 1. }[/math]
The previous formula arises in the special case of the constant function 틀:Math, whose Dirichlet inverse is 틀:Math.
A particular application of the first of these extensions arises if we have (complex-valued) functions 틀:Math and 틀:Math defined on the positive integers, with
- [math]\displaystyle{ g(n) = \sum_{1 \le m \le n}f\left(\left\lfloor \frac{n}{m}\right\rfloor\right)\quad\mbox{ for all } n\ge 1. }[/math]
By defining 틀:Math and 틀:Math, we deduce that
- [math]\displaystyle{ f(n) = \sum_{1 \le m \le n}\mu(m)g\left(\left\lfloor \frac{n}{m}\right\rfloor\right)\quad\mbox{ for all } n\ge 1. }[/math]
A simple example of the use of this formula is counting the number of reduced fractions 틀:Math, where 틀:Mvar and 틀:Mvar are coprime and 틀:Math. If we let 틀:Math be this number, then 틀:Math is the total number of fractions 틀:Math with 틀:Math, where 틀:Mvar and 틀:Mvar are not necessarily coprime. (This is because every fraction 틀:Math with 틀:Math and 틀:Math can be reduced to the fraction 틀:Math with 틀:Math, and vice versa.) Here it is straightforward to determine 틀:Math, but 틀:Math is harder to compute.
Another inversion formula is (where we assume that the series involved are absolutely convergent):
- [math]\displaystyle{ g(x) = \sum_{m=1}^\infty \frac{f(mx)}{m^s}\quad\mbox{ for all } x\ge 1\quad\Longleftrightarrow\quad f(x) = \sum_{m=1}^\infty \mu(m)\frac{g(mx)}{m^s}\quad\mbox{ for all } x\ge 1. }[/math]
As above, this generalises to the case where 틀:Math is an arithmetic function possessing a Dirichlet inverse 틀:Math:
- [math]\displaystyle{ g(x) = \sum_{m=1}^\infty \alpha(m)\frac{f(mx)}{m^s}\quad\mbox{ for all } x\ge 1\quad\Longleftrightarrow\quad f(x) = \sum_{m=1}^\infty \alpha^{-1}(m)\frac{g(mx)}{m^s}\quad\mbox{ for all } x\ge 1. }[/math]
Multiplicative notation[편집 | 원본 편집]
As Möbius inversion applies to any abelian group, it makes no difference whether the group operation is written as addition or as multiplication. This gives rise to the following notational variant of the inversion formula:
- [math]\displaystyle{ \mbox{if } F(n) = \prod_{d|n} f(d),\mbox{ then } f(n) = \prod_{d|n} F\left(\frac{n}{d}\right)^{\mu(d)}. }[/math]
Proofs of generalizations[편집 | 원본 편집]
The first generalization can be proved as follows. We use Iverson's convention that [condition] is the indicator function of the condition, being 1 if the condition is true and 0 if false. We use the result that
- [math]\displaystyle{ \sum_{d|n}\mu(d)=i(n), }[/math]
that is, 틀:Math.
We have the following:
- [math]\displaystyle{ \begin{align} \sum_{1\le n\le x}\mu(n)g\left(\frac{x}{n}\right) &= \sum_{1\le n\le x} \mu(n) \sum_{1\le m\le \frac{x}{n}} f\left(\frac{x}{mn}\right)\\ &= \sum_{1\le n\le x} \mu(n) \sum_{1\le m\le \frac{x}{n}} \sum_{1\le r\le x} [r=mn] f\left(\frac{x}{r}\right)\\ &= \sum_{1\le r\le x} f\left(\frac{x}{r}\right) \sum_{1\le n\le x} \mu(n) \sum_{1\le m\le \frac{x}{n}} \left[m=\frac{r}{n}\right] \qquad\text{rearranging the summation order}\\ &= \sum_{1\le r\le x} f\left(\frac{x}{r}\right) \sum_{n|r} \mu(n) \\ &= \sum_{1\le r\le x} f\left(\frac{x}{r}\right) i(r) \\ &= f(x) \qquad\text{since }i(r)=0\text{ except when }r=1 \end{align} }[/math]
The proof in the more general case where 틀:Math replaces 1 is essentially identical, as is the second generalisation.
Contributions of Weisner, Hall, and Rota[편집 | 원본 편집]
See also[편집 | 원본 편집]
References[편집 | 원본 편집]
각주
External links[편집 | 원본 편집]
- 틀:MathWorld이 문서에는 영어판 위키백과의 Mobius Inversion formula 문서를 번역한 내용이 포함되어 있습니다.