뫼비우스 함수와 디리클레 합성곱

※ 앞으로 몇 개의 게시글에 걸쳐, 비슷한 주제로 글을 쓸 예정입니다.

 

▣ 정수론 시리즈 ─ 순서대로 읽으시는 걸 추천합니다.

1. 뫼비우스 함수와 디리클레 합성곱 (현재 글)

2. Double Counting과 Harmonic Lemma

3. 곱셈적 함수 테이블 만들기

4. Mertens Trick (xudyh's sieve)

 

Preliminaries and Notations

  정수론에서 다루는 대상 중 수론적 함수(산술적 함수, Arithmetic Function)라는 것이 있다. 모든 양의 정수에 대해 정의된 복소함수를 일컫는데, 쉽게 말해서 수열을 의미한다. 그리고 수론적 함수 중에서도 조금 더 특별한 아이들을 모아 따로 부르는 명칭이 있으니, 그것이 바로 곱셈적 함수(Multiplicative Function)이다. 곱셈적 함수의 정의는 다음과 같다.

Definition. 곱셈적 함수(곱산술 함수, Multiplicative Function)
함수 $f:\mathbb{Z}^+ \to \mathbb{C}$가 임의의 서로소인 두 수 $m,\, n \in \mathbb{Z}^+$에 대해 $f(mn) = f(m)f(n)$를 만족하면 곱셈적 함수라고 한다. 특히, 임의의 두 수 $m,\, n \in \mathbb{Z}^+$에 대해, $f(mn) = f(m)f(n)$를 만족하면 완전 곱셈적 함수(Completely Multiplicative Function)이라고 한다.

 

정의에 의해, 곱셈적 함수 $f$에 대해 $1$보다 큰 어떤 양의 정수 $n$이 $n = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$로 소인수분해된다고 할 때($p_i$는 서로 다른 소수, $e_i$는 $1$ 이상의 정수), $f(n) = f(p_1^{e_1}) f(p_2^{e_2}) \cdots f(p_t^{e_t})$가 된다. 또한 정의에서 $m = 1$을 대입하면 모든 $n \in \mathbb{Z}^+$에 대해 $f(n) = f(1)f(n)$이 되어야 하므로 $f(1)=1$이다(모든 함숫값이 $0$인 경우는 생각하지 않기로 하자). 즉 소수의 거듭제곱에 대한 함숫값들을 알고 있다면, 모든 양의 정수에 대한 함숫값을 구할 수 있다.

 

  유명한(그리고 정수론에서 자주 등장하는) 곱셈적 함수를 몇 개 나열하면 다음과 같다. (단, $n = \displaystyle \prod_{i=1}^t p_i^{e_i}$라고 하자.)

• $\tau(n):$ $n$의 양의 약수의 개수를 뜻하며, $\tau(p^e) = e + 1$이므로 $\tau(n) = \displaystyle \prod_{i=1}^t (e_i + 1)$이다. $d(n)$으로도 표기한다.
• $\sigma_k(n):$ $n$의 양의 약수의 $k$제곱의 합을 나타내고, 특히 $k = 1$일 때 $\sigma(n)$이라 표기한다. $\sigma_k(p^e) = \dfrac{p^{k(e+1)} - 1}{p^k -1}$이므로 $\sigma_k(n) = \displaystyle \prod_{i=1}^t \dfrac{p_i^{k(e_i +1)} - 1}{p_i ^k -1}$이다. 특히, $\sigma(n) = \displaystyle \prod_{i=1}^t \dfrac{p_i^{e_i +1} - 1}{p_i -1}$이다. 참고로 $\sigma_0(n) = \tau(n)$이다.
• $\phi(n):$ 오일러 파이(피) 함수, 혹은 토션트(totient) 함수라고 부르며, $n$과 서로소인 $n$ 이하의 양의 정수의 개수를 뜻한다. $\phi(p^e) = p^e - p^{e-1}$이므로($\because$ 소수 $p$에 대해 $p^e$와 서로소인 수는 $p$의 배수가 아닌 수들이므로, 전체 $p^e$에서 $p^e$ 이하의 $p$의 배수의 개수$(=p^{e-1})$를 뺀 값이 $\phi(p^e)$가 된다), $\phi(n) = \displaystyle \prod_{i=1}^t (p_i^{e_i} - p_i^{e_i -1})$이다.
• $1(n):$ 모든 $n \in \mathbb{Z}^+$에 대해 $1(n)=1$로 정의되는 함수.
• ${\rm Id}(n):$ 모든 $n \in \mathbb{Z}^+$에 대해 ${\rm Id}(n) = n$으로 정의되는 함수. 항등함수라고 한다.

그리고, 이제부터 소개할 뫼비우스 함수(Möbius Function)가 있다.

 

뫼비우스 함수(Möbius Function)

  뫼비우스 함수는 이름에서부터 느껴지다시피 '뫼비우스의 띠'로 유명한 수학자 뫼비우스가 고안한 함수로(다만 최초 고안자는 아니다. 기록상 오일러가 이 함수를 최초로 사용하였을 거라 추정된다), 정수론에서 심심찮게 등장하는 곱셈적 함수이며 정의는 다음과 같다.

Definition. 뫼비우스 함수(Möbius Function)
양의 정수 $n$에 대해 $n$의 서로 다른 소인수의 개수를 $\lambda(n)$이라고 할 때(단, $\lambda(1) = 0$이다), 뫼비우스 함수 $\mu(n)$을 다음과 같이 정의한다.
$$\mu(n) \equiv \begin{cases} (-1)^{\lambda(n)} & (n \text{ is a square-free integer}) \\ 0 & (\text{otherwise}) \end{cases}$$

 

여기서 square-free integer는 우리말로 제곱 인수가 없는 정수 혹은 무승수라 부르는 것으로, 말 그대로 $1$을 제외한 제곱수를 약수로 가지지 않는 정수를 의미한다. 달리 말하면 모든 소인수의 지수($e_i$)가 $1$ 이하다. 즉 $1$, $2$, $10$, $31$은 무승수이고 $16$, $45$, $196$ 등은 무승수가 아니다.

 

  뫼비우스 함수가 곱셈적 함수임을 밝히는 것은 그다지 어렵지 않다: 서로소인 두 수 $m$과 $n$은 소인수가 겹치지 않으므로, 두 수를 곱한다 해도 $m$과 $n$ 각각의 소인수의 지수는 변함이 없고 $\lambda(mn) = \lambda(m) + \lambda(n)$이 되어, 결국 $\gcd(m,\, n) = 1$일 때 $\mu(nm) = \mu(m)\mu(n)$가 된다.

 

  또한 뫼비우스 함수에는 다음과 같은 성질이 있다.

Theorem. 뫼비우스 함수의 성질
뫼비우스 함수 $\mu(n)$에 대해 다음이 성립한다.
$$\sum_{d|n}\mu(d) = \begin{cases} 1 & (n = 1) \\ 0 & (n > 1) \end{cases}$$

 

Proof.  우선 $n=1$인 경우는 자명하다. $n>1$인 경우, 좌변의 항들 중 값이 0인 항들은 계산에 영향을 주지 않으므로 제외해도 상관없다. 그러면 좌변의 항은 $d$가 무승수인 $\mu(d)$들만 남을 것이다. $n$의 가장 큰 소인수를 $P$라고 하자. $P$를 소인수로 가지지 않는 $d$들에 대해서, $\mu(d)$와 $\mu(Pd)$를 생각해 보자. $d$와 $Pd$는 무승수이므로 두 항은 $0$이 아니고, 소인수가 하나 추가되었으므로 $\lambda(Pd) = \lambda(d) + 1$이 될 것이다. 즉 두 항 중 하나는 $1$, 나머지 하나는 $-1$이 되고, 따라서 $\mu(d)+\mu(Pd) = 0$이다. 이때 남아 있는 항들 중 $P$를 소인수로 가지는 항과 그렇지 않은 항이 정확히 절반씩이고, $P$를 소인수로 가지지 않는 어떤 $d$를 골라도 $Pd$와 대응시킬 수 있으므로 결국 좌변의 합은 $0$이 된다.     $\square$

 

  사실 뫼비우스 함수를 처음 보면 굉장히 낯선 형태로 느껴진다. 정의도 복잡하고 저 성질을 알아서 어디다 쓸 텐가? 그런데 한번 이러한 문제를 생각해 보자: $1$부터 $n$까지의 양의 정수 중 $2$의 배수와 $3$의 배수가 아닌 수의 개수는? 이 문제는 포함-배제의 원리를 이용하는 전형적인 문제고, $n$까지의 수 중 $2$의 배수와 $3$의 배수를 빼면 $6$의 배수가 중복해서 빠지므로 $6$의 배수를 다시 더해 주는 식으로 풀 수 있다. 즉 답은 $n - \lfloor n/2 \rfloor - \lfloor n/3 \rfloor + \lfloor n/6 \rfloor$이 될 것인데… 여기서 각 항의 부호에 집중해 보자.

 

• $n$의 부호는 $+$인데, $\mu(1) = 1$이다.
• 또한 $\lfloor n/2 \rfloor$와 $\lfloor n/3 \rfloor$의 부호는 $-$인데, $\mu(2) = \mu(3) = -1$이다!
• 마지막으로 $\lfloor n/6 \rfloor$의 부호는 $+$이고, $\mu(6) = 1$이다.

어라? 가만 보니 $\lfloor n/k \rfloor$의 부호와 $\mu(k)$의 값이 같다! 이 사실은 뫼비우스 함수가 포함-배제의 원리와 관련이 있다는 걸 시사한다. 구체적으로 말해서, 뫼비우스 함수는 소인수에 대해 포함-배제 원리를 적용하는 틀을 제시하는 함수로 볼 수 있으며 이는 뫼비우스 함수와 포함-배제의 원리라는, 사뭇 달라 보이는 두 개념이 상호 호환될 수 있음을 의미한다. 이에 관해 수학적으로 조금 더 엄밀한 논의를 보고 싶다면 rkm0959 님의 블로그에 굉장히 좋은 글이 있으니 참고하는 것이 좋겠다.

 

디리클레 합성곱(Dirichlet Convolution)

  주제를 살짝 돌려서, 디리클레 합성곱이라는 새로운 연산을 하나 소개한다. 디리클레 합성곱은 수론적 함수 사이의 이항연산으로, 정수론에서 중요하게 다루어지는 연산이다. 디리클레 합성곱 정의는 다음과 같다.

Definition. 디리클레 합성곱(Dirichlet Convolution)
수론적 함수 $f(n)$와 $g(n)$에 대해, 디리클레 합성곱 $f \ast g$는 다음과 같이 정의한다.

$$(f \ast g)(n) = \sum_{d|n}f(d)g{\left(\frac{n}{d}\right)} = \sum_{ab=n}f(a)g(b)$$

 

이 뜬금없는 듯한 연산이 왜 등장한 것일까? 놀랍게도 디리클레 합성곱은 다음의 여러 유용한 성질들을 가진다.

 

• $f$와 $g$가 곱셈적이면 $f \ast g$도 곱셈적이다. 즉, 곱셈적 함수 집합에 대해 닫혀 있다. (단, 완전 곱셈적 함수 집합에 대해선 닫혀 있지 않다.)
• 교환법칙과 결합법칙, 덧셈에 대한 분배법칙이 성립한다.
• 항등원이 존재한다. 항등원은 존재하면 유일하므로 이 항등원을 $\varepsilon$으로 표기하고, 다음과 같이 정의된다. $$\varepsilon(n) \equiv \begin{cases} 1 & (n = 1) \\ 0 & (\text{otherwise}) \end{cases}$$ 눈치챘겠지만, $\varepsilon$ 또한 곱셈적 함수이다. 덧붙여, 위의 뫼비우스 함수의 성질에 따라 $\sum\limits _{d|n}\mu(d) = \varepsilon(n)$이 된다.
• $f(1) \ne 0$인 수론적 함수 $f$에 대해 역원이 존재한다. 역원이 존재하면 유일하므로 이를 $f_{\ast}^{-1}$이라고 표기한다. 즉 $f \ast f_{\ast}^{-1} = f_{\ast}^{-1} \ast f = \varepsilon$이 성립한다.

위 성질들을 만족한다는 것을 유식한(?) 말로, "수론적 함수 집합은 덧셈, 디리클레 합성곱에 대해 가환환(Commutative Ring)을 이룬다." 라고 하고, 이 환 구조를 특별히 디리클레 환(Dirichlet Ring)이라고 부른다. 게다가 곱셈적 함수 집합으로 한정하면 체(Field)가 된다! …라고 말하고 싶은데, 이상하게 아무리 찾아봐도 '곱셈적 함수 집합과 디리클레 합성곱은 아벨군을 이룬다'는 말밖에 없어서 조심스럽다. ㅎㅎ; 뭐 여하튼 어려운 단어가 여러 가지 나왔는데, 단순히 말하면 곱셈적 함수끼리의 디리클레 합성곱은 우리에게 친숙한 실수의 사칙연산과 다를 바 없다는 뜻이 된다.

 

  여기서 잠시 $\mu \ast 1$을 생각해 보면, $$(\mu \ast 1)(n) = \sum_{d|n}\mu(d) = \varepsilon(n)$$인데 이것은 역원의 정의와 같다! 따라서 $\mu(n) = 1_{\ast}^{-1}(n)$가 성립한다. 즉 뫼비우스 함수는 디리클레 합성곱에 대한 $1(n)$의 역원이다. 보다시피 디리클레 합성곱이 서로 관련 없는 것 같은 곱셈적 함수들을 연결해 주고 있다. 이 외에도 다음과 같은 관계들을 발견할 수 있다.

 

• $1 \ast 1$을 보면 이 식은 $\sum\limits_{d|n} 1$과 같은데, 이 식의 의미를 생각해 보면 $d$가 $n$을 나눌 때마다(즉 $d$가 $n$의 약수일 때마다) $1$을 더해 주므로 곧 양의 약수의 개수와 같다! 따라서 $\tau = 1 \ast 1$이 성립한다.
• ${\rm Id} \ast 1$은 $\sum\limits_{d|n}d$이고, 이는 양의 약수의 합과 같다. 따라서 $\sigma = {\rm Id} \ast 1$이 성립한다.
• $\mu \ast {\rm Id} = \displaystyle\sum_{d|n}\mu(d)\frac{n}{d}$인데, $n = \displaystyle \prod_{i=1}^t p_i^{e_i}$라 하면 우변은 $n - \displaystyle\sum_{i \le t}\frac{n}{p_i} + \displaystyle\sum_{i<j \le t}\frac{n}{p_i p_j} - \displaystyle\sum_{i<j<k \le t}\frac{n}{p_i p_j p_k} + \cdots$ 가 될 것이다. 헌데 이 식을 아까 살짝 언급했던 '포함-배제의 원리' 관점으로 보면, $1$부터 $n$까지 $n$개의 양의 정수 중 $p_i$의 배수들을 제외하고, $p_i p_j$의 배수들은 더하고, 다시 $p_i p_j p_k$의 배수들을 빼고, …로 이해할 수 있다. 이 과정은 "$1$부터 $n$까지의 양의 정수 중 $p_1$, $p_2$, $\cdots$, $p_t$의 배수가 아닌 수의 개수는?"에 대한 답을 찾는 것이 되고, 이것은 $n$ 이하의 $n$과 서로소인 양의 정수의 개수와 일치한다! 따라서 $\mu \ast {\rm Id} = \phi$가 성립한다.

이 외에도 많은 관계식이 성립하는데, 더 알고 싶다면 위키백과의 글을 참고하라.

 

뫼비우스 반전(Möbius Inversion)

  위에서 $\mu \ast 1 = \varepsilon$라는 걸 알았는데, 이 식의 양변에 어떤 수론적 함수 $f$를 합성곱해 보면 $\mu \ast 1 \ast f = \varepsilon \ast f = f$가 되고 $g = f \ast 1$이라 정의하면 결국 $f = g \ast \mu$가 된다. 즉 $g = f \ast 1$이면 $f = g \ast \mu$가 성립한다. 반대로, $f = g \ast \mu$라고 하면 $g = f \ast 1$가 된다. ("실수의 사칙연산과 똑같다"고 했던 걸 기억하는가?) 이 관계를 뫼비우스 반전 공식(Möbius Inversion Formula)이라 부르고, 수식으로 작성하면 다음과 같다.

Definition. 뫼비우스 반전 공식(Möbius Inversion Formula)
수론적 함수 $f(n)$와 $g(n)$가 있고 모든 양의 정수 $n$에 대해 $g(n) = \displaystyle\sum_{d|n}f(d)$를 만족하는 것은, $$f(n) = \sum_{d|n}g(d)\mu{\left(\frac{n}{d}\right)}$$이 모든 양의 정수 $n$에 대해 성립하는 것과 동치이다.

 

따라서 다음의 관계식들도 성립한다.

 

• $\tau = 1 \ast 1$이므로 $1 = \tau \ast \mu$이다. 즉 모든 양의 정수 $n$에 대해 $\displaystyle\sum_{d|n}\tau(d)\mu{\left(\frac{n}{d}\right)} = 1$이 성립한다.
• $\sigma = {\rm Id} \ast 1$이므로 ${\rm Id} = \sigma \ast \mu$이다. 즉 모든 양의 정수 $n$에 대해 $\displaystyle\sum_{d|n}\sigma(d)\mu{\left(\frac{n}{d}\right)} = n$이 성립한다.
• $\mu \ast {\rm Id} = \phi$ 이므로 ${\rm Id} = \phi \ast 1$이다. 즉 모든 양의 정수 $n$에 대해 $\displaystyle\sum_{d|n}\phi(d) = n$이 성립한다. (이 식은 사실 다른 방법으로도 증명할 수 있다.)
• 뫼비우스 반전과는 별개로, ${\rm Id} = \phi \ast 1$에서 양변에 $1$을 합성곱하면 ${\rm Id} \ast 1 = \phi \ast 1 \ast 1$ $\Rightarrow$ $\sigma = \phi \ast \tau$가 성립한다.

이렇듯 디리클레 합성곱과 뫼비우스 반전은 여러 곱셈적 함수들을 연결하는 징검다리 역할을 하는 것을 볼 수 있다.

 

 

---

 

 

  지금까지 수론적 함수의 정의와 종류에서 시작하여 디리클레 합성곱을 거쳐 뫼비우스 반전까지 알아 보았다. 그런데 슬슬 이런 의문이 들지 않는가? "그래서 이 일련의 개념들을 대체 왜 소개한 거지? 좋은 성질들도 많고 여러 관계식도 도출할 수 있다는 건 알겠는데, 그것들을 어디에 쓸 수 있는 거지?" 이 질문들에 대한 답은, 이 뒤로 이어질 게시글들을 읽다 보면 저절로 깨닫게 되니 한번 정독해 보도록 하자! :)

 

 

─ To Be Continued…