뫼비우스 함수

수론과 조합론에서, 뫼비우스 함수(Möbius函數, 영어: Möbius function)는 정수가 제곱 인수가 없는 정수인지 여부에 따라 분류하는 곱셈적 함수이다. 뫼비우스 반전 공식에 사용되며, 리만 가설과도 깊은 관계를 가진다. 기호는 $\mu (n)$.

정의

뫼비우스 함수

$\mu :{\mathbb{Z}}^{+}\to \{-1,0,+1\}$

는 양의 정수 $n\in {\mathbb{Z}}^{+}$을 다음과 같이 $\{-1,0,1\}$ 가운데 하나에 대응시킨다.

• $n$이 $k$개의 소인수를 갖는 제곱 인수가 없는 정수라면 $\mu (n)=(-1{)}^k$이다. (특수한 경우로, $n=1$은 0개의 소인수를 가지므로 $\mu (1)=1$이다.)
• $n$이 제곱 인수가 없는 정수가 아니라면, $\mu (n)=0$이다.

즉, $n$의 소인수 분해가

$n=\prod _p{p}^{n_p}$

라면, 뫼비우스 함수는 다음과 같다.

$\mu (n)=(-1{)}^{\sum _p{n}_p}\prod _p[n_p\le 1]$

여기서 $[\cdots ]$는 아이버슨 괄호(조건이 참이면 1, 아니면 0)이다.

뫼비우스 함수 $\mu (n)$은 또한 1의 원시적 $n$제곱근의 합이다.

$\mu (n)=\sum _{\genfrac{}{}{0ex}{}{1\le k\le n}{\gcd \{k,n\}=1}}\exp (2\pi ik/n)$

증명 (포함배제의 원리을 통한 증명):

다음과 같은 항등식이 성립한다.

$\sum _{k=1}^n\exp (2\pi ik/n)={\delta }_{n,1}=\{\begin{array}{cc}1& n=1\\ 0& n>1\end{array}$

포함배제의 원리에 따라, 다음이 성립한다.

$\begin{array}{cc}\mu (n)& =\sum _{d\mid n}\mu (d){\delta }_{n/d,1}\\ & =\sum _{d\mid n}\mu (d)\sum _{k=1}^{n/d}\exp (2\pi idk/n)\\ & =\sum _{k=1}^n\exp (2\pi ik/n)-\sum _{p\mid n}\sum _{k=1}^{n/p}\exp (2\pi ipk/n)+\sum _{\genfrac{}{}{0ex}{}{p,q\mid n}{p<q}}\sum _{k=1}^{n/pq}\exp (2\pi ipqk/n)-\cdots \\ & =\sum _{\genfrac{}{}{0ex}{}{1\le k\le n}{\gcd \{k,n\}=1}}\exp (2\pi ik/n)\end{array}$

증명 (중국인의 나머지 정리를 통한 증명):

우선, 우변 $f(n)$이 $n$에 대한 곱셈적 함수임을 보이자. $\exp (2\pi i)=1$이므로,

$k\equiv k^{\prime }(\mathrm{mod}n)$

라면

$\exp (2\pi ik/n)=\exp (2\pi i{k}^{\prime }/n)$

이다. 따라서, 우변의 합은 다음과 같이 다시 쓸 수 있다.

$f(n)=\sum _{k\in (\mathbb{Z}/(n){)}^{\times }}\exp (2\pi ik/n)$

이제, $n$의 소인수 분해가

$n=p_1^{a_1}\cdots p_r^{a_r}$

라고 하자. 중국인의 나머지 정리에 따라, 각 $i\in \{1,\dots ,r\}$에 대하여

$e_i\equiv 1(\mathrm{mod}{p}_i^{a^i})$

$e_i\equiv 0(\mathrm{mod}{p}_j^{a_j})(j\ne i)$

인 유일한 $e_i\in \mathbb{Z}/(n)$이 존재한다. 그렇다면,

$(k_1,\dots ,k_r)\mapsto k_1{e}_1+\cdots k_r{e}_r$

은 군 동형 사상

$(\mathbb{Z}/(p_1^{a_1}){)}^{\times }\times \cdots \times (\mathbb{Z}/(p_r^{a_r}){)}^{\times }\to (\mathbb{Z}/(n){)}^{\times }$

을 이루며, 특히 이는 전단사 함수이다. 마찬가지로,

$k_i\mapsto e_i{k}_i$

는 군의 자기 동형 사상

$(\mathbb{Z}/(p_i^{a_i}){)}^{\times }\to (\mathbb{Z}/(p_i^{a_i}){)}^{\times }$

을 이루며, 특히 이는 전단사 함수이다. 따라서,

$\begin{array}{cc}f(n)& =\sum _{k_1\in (\mathbb{Z}/(p_1^{a_1}){)}^{\times }}\cdots \sum _{k_1\in (\mathbb{Z}/(p_1^{a_1}){)}^{\times }}\exp (2\pi i(k_1{e}_1+\cdots +k_r{e}_r)/n)\\ & =(\sum _{k_1\in (\mathbb{Z}/(p_1^{a_1}){)}^{\times }}\exp (2\pi i{k}_1{e}_1/n))\cdots (\sum _{k_1\in (\mathbb{Z}/(p_1^{a_1}){)}^{\times }}\exp (2\pi i{k}_r{e}_r/n))\\ & =(\sum _{k_1\in (\mathbb{Z}/(p_1^{a_1}){)}^{\times }}\exp (2\pi i{k}_1/n))\cdots (\sum _{k_1\in (\mathbb{Z}/(p_1^{a_1}){)}^{\times }}\exp (2\pi i{k}_r/n))\\ & =f(p_1^{a_1})\cdots f(p_r^{a_4})\end{array}$

이다.

이제, 소수 $p$와 양의 정수 $a\in {\mathbb{Z}}^{+}$에 대하여, $f(p^a)=\mu (p^a)$임을 보이면 족하며, 이는 다음과 같이 쉽게 보일 수 있다.

$\begin{array}{cc}f(p^a)& =\sum _{\genfrac{}{}{0ex}{}{1\le k\le p^a}{\gcd \{k,p\}=1}}\exp (2\pi ik/p^a)\\ & =\sum _{k=1}^{p^a}\exp (2\pi ik/p^a)-\sum _{k=1}^{p^{a-1}}\exp (2\pi ik/p^{a-1})\\ & =\{\begin{array}{cc}-1& a=1\\ 0& a>1\end{array}\end{array}$

$\mu$는 양이 아닌 정수에 대하여 일반적으로 정의하지 않는다.

메르텐스 함수(Mertens函數, 영어: Mertens function)는 뫼비우스 함수의 부분합이다. 즉, 다음과 같은 함수이다.

$M:{\mathbb{Z}}^{+}\to \mathbb{Z}$

$M(n)=\sum _{k=1}^n\mu (k)$

뫼비우스 함수는 1의 원시적 $n$제곱근의 합이므로, 메르텐스 함수를 다음과 같이 정의할 수도 있다.

$M(n)=\sum _{a\in {ℱ}_n}\exp (2\pi ia)$

여기서 ${ℱ}_n$은 $n$차 페리 수열이다.

성질

뫼비우스 함수는 곱셈적 함수이다. 즉, 서로소 정수에 대하여 다음과 같다.

$\mu (ab)=\mu (a)\mu (b)(\gcd \{a,b\}=1)$

뫼비우스 함수는 디리클레 합성곱 아래 상수 함수 1의 역원이다.

$(\mu *1)(n)=\sum _{d\mid n}\mu (d)={\delta }_{n,1}=\{\begin{array}{cc}1& n=1\\ 0& n>1\end{array}$

이 성질 때문에 뫼비우스 함수는 뫼비우스 반전 공식에 등장한다.

생성 함수

뫼비우스 함수의 생성 함수는 다음과 같다.

$\sum _{n=1}^{\mathrm{\infty }}\mu (n)x^n=x-\sum _{a=2}^{\mathrm{\infty }}{x}^a+\sum _{a=2}^{\mathrm{\infty }}\sum _{b=2}^{\mathrm{\infty }}{x}^{ab}-\sum _{a=2}^{\mathrm{\infty }}\sum _{b=2}^{\mathrm{\infty }}\sum _{c=2}^{\mathrm{\infty }}{x}^{abc}+\sum _{a=2}^{\mathrm{\infty }}\sum _{b=2}^{\mathrm{\infty }}\sum _{c=2}^{\mathrm{\infty }}\sum _{d=2}^{\mathrm{\infty }}{x}^{abcd}-\cdots$

뫼비우스 함수의 람베르트 급수는 다음과 같다.

$\sum _{n=1}^{\mathrm{\infty }}\frac{\mu (n)q^n}{1-q^n}=q$

이는 $|q|<1$에 대하여 수렴한다.

뫼비우스 함수의 디리클레 급수는 리만 제타 함수의 역수이다.

$\sum _{n=1}^{\mathrm{\infty }}\frac{\mu (n)}{n^s}=\frac{1}{\zeta (s)}$

점근적 성질

파일:Congettura di Mertens.svg

메르텐스 추측은 메르텐스 함수의 그래프가 포물선 속에 머무른다는 추측이다. 이는 작은 수에 대해서 성립하지만, 매우 큰 수에 대하여 성립하지 않는다.

뫼비우스 함수의 값이 $\{\pm 1,0\}$뿐이므로, 메르텐스 함수는 매우 느리게 움직이며 또한 자명하게

$|M(n)|\le n\mathrm{\forall }n\in {\mathbb{Z}}^{+}$

이다.

소수 정리에 따라 다음이 성립한다.

$\underset{n\to \mathrm{\infty }}{\lim }\frac{1}{n}M(n)=0$

또한, 다음이 성립한다.

$\underset{n\to \mathrm{\infty }}{\lim }\frac{1}{n}\sum _{k=0}^n|\mu (n)|=\prod _p(1-\frac{1}{p^2})=\frac{1}{\zeta (2)}=\frac{6}{{\pi }^2}$

즉, 점근적으로 $3/{\pi }^2\approx 30.4\mathrm{\%}$의 수에 대하여 뫼비우스 함수가 +1이며, $3/{\pi }^2\approx 30.4\mathrm{\%}$의 수에 대하여 뫼비우스 함수가 −1이며, $1-6/{\pi }^2\approx 39.2\mathrm{\%}$의 수에 대하여 뫼비우스 함수가 0이다.

리만 가설은 메르텐스 함수에 대한 다음 조건과 동치이다.

$M(n)=O(x^{1/2+ϵ})\mathrm{\forall }ϵ\in {ℝ}^{+}$

메르텐스 추측(Mertens推測, 영어: Mertens conjecture)은 $\mathrm{\forall }n\in {\mathbb{Z}}^{+}:|M(n)|\le \sqrt{n}$라는 명제이다. 이는 오랫동안 난제로 있었으나, 1985년에 거짓으로 판명되었으며, 다음이 성립한다.^:188–189

$\mathrm{lim\; inf}\frac{M(n)}{\sqrt{n}}<-1.009$

$\mathrm{lim\; sup}\frac{M(n)}{\sqrt{n}}>1.06$

그러나 리만 가설은 현재 (2021년) 미해결 문제이다. 메르텐스 추측보다 더 약하지만 리만 가설보다 더 강한 명제

$M(x)=O(x^{1/2})$

역시 아직 반증되지 않았으나, 이는 아마 거짓일 것이라고 추측된다.

급수

뫼비우스 함수에 대하여 다음과 같은 급수가 존재한다.

$\sum _{n=1}^{\mathrm{\infty }}(\mu (n)/n{)}^2=15/{\pi }^2$

$\sum _{n=1}^{\mathrm{\infty }}\mu (n)\frac{\ln n}{n}=-1$

표

처음 몇 개의 양의 정수에 대해서 뫼비우스 함수와 메르텐스 함수의 값은 다음과 같다. (OEIS의 수열 A008683), (OEIS의 수열 A002321)

$n$	1	2	3	4	5	6	7	8	9	10	11	12
$\mu (n)$	1	−1	−1	0	−1	1	−1	0	0	1	−1	0
$M(n)$	1	0	−1	−1	−2	−1	−2	−2	−2	−1	−2	−2

뫼비우스 함수의 값의 그래프는 다음과 같다.

파일:Moebius mu.svg

메르텐스 함수의 10⁴까지의 값의 그래프는 다음과 같다.

파일:Mertens function.svg

$\mu (n)=0$인 정수 $n$ (즉, 제곱 인수가 없는 정수가 아닌 수)은 다음과 같다.

4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 60, 63, … (OEIS의 수열 A013929)

역사

레온하르트 오일러는 1748년 저서에 뫼비우스 함수를 정의하고 암묵적으로 사용하였지만, 자세하게 다루지 않았다.^{:99, Notes to §3.1} 1798년에 카를 프리드리히 가우스는 《산술 연구》(라틴어: Disquisitiones Arithmeticae)에서 1의 원시 $n$거듭제곱근의 합이 $\mu (n)$이라는 것을 보였으나, 역시 이 함수를 특별히 연구하지 않았다.

1831년에 아우구스트 페르디난트 뫼비우스는 뫼비우스 함수를 최초로 명시적으로 도입하였다.^{:99, Notes to §3.1} 1874년에 프란츠 메르텐스가 최초로 오늘날 사용되는 기호 μ를 사용하였다.^{:53:99, Notes to §3.1}

1885년 7월 11일에 토마스 요아너스 스틸티어스는 샤를 에르미트에게 보낸 편지에서 메르텐스 함수를 최초로 사용하였다. (이 편지는 1905년에 출판되었다.) 스틸티어스는 $M(n)=O(\sqrt{n})$임을 증명하였다고 주장하였고, 또 메르텐스 추측 ($|M(n)|\le \sqrt{n}$)을 추측하였다. 스틸티어스는 뫼비우스 함수를 $f(n)$으로, 메르텐스 함수를 $g(n)$으로 표기하였다. 이 편지에서 스틸티어스는 다음과 같이 적었다.

“	그러나 나는 이 합 $g(n)=f(1)+f(2)+\cdots +f(n)$ 에서 $\pm 1$ 항들이 서로 충분히 상쇄하여 $\frac{g(n)}{\sqrt{n}}$가 (임의로 큰 $n$에 대하여) 항상 상계와 하계를 갖는 것을 발견하였습니다. (아마 이 상계와 하계는 +1과 −1로 잡을 수 있을 것입니다.) […] 이와 같이 이 모든 산술 연구는 이 합 $f(1)+f(2)+\cdots +f(n)$에 의존합니다. 나의 증명은 매우 어렵습니다. 나는 연구를 계속하여 이 증명을 더 간략하게 하려고 시도할 것입니다. Or, je trouve que dans la somme $g(n)=f(1)+f(2)+\cdots +f(n),$ les termes $\pm 1$ se compensent assez bien pour que $\frac{g(n)}{\sqrt{n}}$ reste toujours comprise entre deux limites fixes, quelque grand que soit $n$ (probablement on peut prendre pour ces limites +1 et −1). […] Vous voyez que tout dépend d’une recherche arithmétique sur cette somme $f(1)+f(2)+\cdots +f(n)$. Ma démonstration est bien pénible; je tâcherai, lorsque je reprendrai ces recherches, de la simplifier encore.	”
	— :162–163

그러나 스틸티어스는 이 "증명"을 출판하지 않았다.

1897년에 프란츠 메르텐스는 메르텐스 함수를 독자적으로 재발견하였고, 메르텐스 추측을 스틸티어스와 독자적으로 추측하였다.

1985년에 앤드루 마이클 오들리스코(영어: Andrew Michael Odlyzko, 1949~)와 헤르마뉘스 요하너스 요서프 터 릴러(네덜란드어: Hermanus Johannes Joseph te Riele, 1947~)는 메르텐스 추측이 거짓임을 증명하였다.

같이 보기

• 뫼비우스 반전 공식
• 제곱 인수가 없는 정수
• 근접 대수
• 리만 제타 함수
• 프라임 제타 함수

외부 링크

• “Möbius function” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Möbius function” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Mertens function” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Mertens conjecture” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Lipton, R. J. (2011년 2월 23일). “The depth of the Möbius function” (영어). 《Gödel’s Lost Letter and P=NP》. 
• Tao, Terence (2015년 9월 6일). “Sign patterns of the Möbius and Liouville functions” (영어). 《What’s New》. 
• “Möbius function” (영어). 《OeisWiki》. 
• “뫼비우스 뮤 함수”. 《오메가》.