디리클레 합성곱 (Dirichlet Convolution)

디리클레 합성곱 (Dirichlet Convolution) 은 수론적 함수 (Arithmetic Function) 를 다루는 데 매우 유용한 연산이다. 다양한 정수론 증명에서 매우 써먹을 데가 많을 것 같으므로 한번은 먼저 다루고 싶었다.

 

정의 / 기본적인 성질

함수 $f(n)$ 과 $g(n)$ 의 Dirichlet Convolution은 $(f * g) (n)$ 으로 쓰며, 다음과 같이 정의한다.
$$(f*g)(n) = \sum_{d | n}f(d)g(\frac{n}{d})$$
다르게 쓰면 이렇게도 쓸 수 있다. (이 notation은 조금 더 직관적인데, 의외로 이렇게 쓰여 있는 곳이 많지 않다.)
$$(f*g)(n) = \sum_{ab = n} f(a) g(b)$$
이런 이상한? 정의가 매우 도움이 되는 이유는 다음과 같은 좋은 성질들이 모두 성립하기 때문이다.

• $f$와 $g$ 가 모두 multiplicative라면 $f * g$ 도 multiplicative.
• 교환법칙과 결합법칙이 성립한다.
• 항등원과 역원이 존재한다. 즉, 어떤 함수 $\epsilon$ 이 있어서, $f * \epsilon = \epsilon * f = f$ 를 만족하는 $\epsilon(n)$ 이 존재하고, $f * f^{-1} = \epsilon$ 을 만족하는 $f^{-1}$ 이 거의 모든 $f$ 에 대해서 존재한다. (이 $f^{-1}$ 을 Dirichlet Inverse 라고 한다.) 물론 거의 모든 이라는 말은, 실수에서 0의 역수가 존재하지 않는 것과 마찬가지로, $f(1) \neq 0$ 인 모든 $f$ 에 대해서 inverse가 존재함을 의미한다.

 

특수한 함수들의 Dirichlet Convolution

Dirichlet Convolution의 정의를 이해하고 나면, 몇 가지 주요한 특수 함수들은 알아두면 유용하다. 대표적으로 다음과 같은 함수들은 이 합성곱의 의의와도 같은데, 정수론의 중요한 함수들을 서로 연결해주는 효과가 있다.
Dirichlet Convolution에서의 항등원 $\epsilon$
$$\epsilon(n) =\begin{cases}
1, & \text{for } n = 1\\  0, & \text{otherwise} \end{cases}$$
모든 항이 1인 함수는 $1$ 함수로 정의한다. $1(n)$ 이라고 쓰기로 하자. (상당수의 책이나 자료에서 $1$ 이라고 쓰고 맥락상 $1(n)$ 을 의미하기도 한다.)
$1(n)$ 의 Dirichlet Inverse 는 맥락상 매우 중요한 함수일 것 같은 느낌이 든다. 먼저, 이 $1^{-1}(n)$ 을 $f(n)$ 이라고 하자. $n = 1$ 일 때, $1(1)*f(1) = 1$ 이어야 하므로 $f(1) = 1$ 임은 자명. 그 외의 모든 $n$ 에 대하여,
$$\sum_{d|n}1(d)f(n/d) = 0$$ 이 식이 성립해야 한다. 따라서, 

$$\sum_{d|n}f(n/d) = \sum_{d|n}f(d)$$ 

가 모든 $n > 1$ 에 대해 0이어야 한다.
이 사실을 만족하는 함수는 뫼비우스 함수 $\mu(n)$ 인데, 다음과 같이 정의된다.
$$\mu(n) =\begin{cases}
0, &  \exists d \in \mathbb{N}, d > 1 \text{ such that } d^2 | n\\ (-1)^k, & n = p_1 p_2 p_3 \dots p_k \end{cases}$$

뫼비우스 함수가 이 성질을 만족하는 유일한 함수임을 증명하는 것은 쉽지 않은 일이지만, 반대로 뫼비우스 함수가 이 성질을 만족한다는 것은 어렵지 않게 보일 수 있다.

$n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$ 라고 하자. 이때, $n$의 약수를 고르는 것은 $p_1$이 $a_1$개, $p_2$가 $a_2$개 ... 있는 숫자 카드 더미에서 카드를 적당히 뽑는 것으로 생각할 수 있다. $a_1$ 부터 $a_k$ 까지가 몇이든, 2번 이상 같은 소수를 뽑으면 $\mu(d)$ 가 0으로 고정되어 버리므로 모두 버릴 수 있다. 즉 $k$개의 소수들 중 몇 개를 뽑는지가 중요하다는 뜻이다.

소수 0개를 뽑는 경우는 1가지이다. 0개를 뽑으면 $\mu(d)$의 값은 1이므로, $1 \times \binom{k}{0}$ 을 더한다. 

... 이와 같은 방법으로 생각하면,

소수 $r$개를 뽑는 경우는 $\binom{n}{r}$ 가지이며, 이때 $\mu(d)$의 값은 $(-1)^r$ 이므로, 

$$\sum_{d | n} \mu(d) = \sum_{r = 0}^{k} (-1)^r \binom{k}{r}$$ 이며 이 식의 값이 0임은 이미 고등학교 확률과 통계에서 배운 내용이다.

 

Mobius Inversion Formula

이것을 이용한 Mobius Inversion Formula, 곧 "뫼비우스 반전공식" 이라고 부르는 공식이 있다. 비교적 간단하게, 다음을 의미한다.
$$g(n) = \sum_{d | n} f(d)$$ 인 함수가 있다고 하자. 이때, 이 $f$ 와 $g$ 는 다음을 만족한다.
$$f(n) = \sum_{d | n} \mu(d) g(n/d)$$ 뭔가 그럴듯해 보이지만 단순하게 $g = f*1$ 일 때 (첫 번째 식), $f = g * \mu(n)$ 이라는 뜻이다. 이 성질을 이용한 Xudyh Sieve 라는 뭔가 굉장한 알고리즘이 있는데, 이해는 한참 동안 종이에 쓰면서 생각해 보면 뭐 그러려니 하겠는데 절대 코딩할 자신이 없으니까 패스. 
뫼비우스 함수는 이렇게 다른 포스팅 중에 끼워서 다루기에는 너무 많은 성질이 있고 중요하기 때문에 일단은 여기까지만 보고 넘기자. 아무튼 $\mu(n) * 1(n) = \epsilon(n)$ 이다.
약수의 개수를 나타내는 함수로 보통 $d(n)$ 이라는 Notation을 사용한다. 잘 생각해 보면 $d(n) = 1(n) * 1(n)$ 이라는 사실은 별로 어렵지 않게 알아낼 수 있다. 위 정의에 그냥 대입해 보면 된다. 이제 양변에 $1(n)$ 의 Dirichlet Inverse인 $\mu(n)$ 을 Convolution하면, $d(n) * \mu(n) = 1(n)$ 을 얻는다.

곱셈의 역원 $\epsilon$ 과 별개로 이름이 Identity 인 함수는 따로 있다. $Id(n)$ 이라고 쓰는데, 이름처럼 $Id(n) = n$ 을 만족하는 함수이다. 이 함수에 $1$ 을 Convolution하면, $\sigma(n)$ 을 얻는다. 생각해 보면, $d | n$ 에 대해서 $d$ 들을 더하는 함수니까 이 $\sigma(n)$ 은 당연히 "약수들의 합" 을 의미한다. 즉, $Id(n)* 1(n) = \sigma(n)$ 이며, 다시 앞에서 사용한 방법대로 $\mu(n)$ 을 양변에 합성하여 $Id(n) = \sigma(n) * \mu(n)$ 을 얻는다.
대략 이정도까지가 Dirichlet Convolution의 기본적인 성질들이고, 이걸 이용하는 알고리즘이나 여러 정리들을 다뤄보기 위해 간단한 내용들만 먼저 정리했다.