Möbius関数

$m=1$ または $n=1$ なら明らかである。$m,n\ge2$ とすると、$m$ と $n$ は互いに素なので共通の素因数をもたず、$mn$ の素因数分解は $m$ の分解と $n$ の分解を並べたものである。$m$ か $n$ のどちらかがある素数を 2 回以上含めば $mn$ も含むので、両辺とも $0$ である。どちらも平方因数をもたず、それぞれ $k$ 個、$l$ 個の相異なる素数の積なら、$mn$ は $k+l$ 個の相異なる素数の積であり、$\mu(mn)=(-1)^{k+l}=\mu(m)\mu(n)$ である。$\square$

$n=1$ では和は $\mu(1)=1$ である。$n\ge2$ とし、$n$ の素因数 $p$ を 1 つ固定する。平方因数をもつ約数 $d$ は $\mu(d)=0$ なので、平方因数をもたない約数だけを考えればよい。そのような約数のうち $p$ で割り切れないもの全体を $S$、$p$ で割り切れるもの全体を $T$ とする。
$d\in S$ に $dp$ を対応させる。$d\mid n$、$p\mid n$ で $d$ と $p$ は互いに素なので $dp\mid n$ であり、$d$ は平方因数をもたず $p\nmid d$ なので $dp$ も平方因数をもたない。よって $dp\in T$ である。逆に $e\in T$ なら $e/p$ は $n$ の約数で平方因数をもたず、$p$ を 2 回は含まないので $p\nmid e/p$、すなわち $e/p\in S$ である。したがって $d\mapsto dp$ は $S$ から $T$ への全単射であり、$dp$ の素因数は $d$ の素因数より 1 個多いので $\mu(dp)=-\mu(d)$ である。よって
$$ \sum_{d\mid n}\mu(d)=\sum_{d\in S}\mu(d)+\sum_{d\in S}\mu(dp)=\sum_{d\in S}\bigl(\mu(d)-\mu(d)\bigr)=0 $$
である。$\square$

thm-mobius-divisor-sum を $n=1,2,\dots,\lfloor x\rfloor$ について足すと、右辺は $n=1$ の項だけが残って $1$ である。左辺は
$$ \sum_{n\le x}\sum_{d\mid n}\mu(d)=\sum_{d\le x}\mu(d)\cdot\#\{n\le x\mid d\mid n\}=\sum_{d\le x}\mu(d)\left\lfloor\frac xd\right\rfloor $$
である。$x$ 以下の $d$ の正の倍数は $d,2d,\dots,\lfloor x/d\rfloor d$ の $\lfloor x/d\rfloor$ 個だからである。$\square$

1. 可換性は、組 $(a,b)$ と $(b,a)$ の入れ替えによる。結合法則は、両辺の $n$ での値がともに
   $$ \sum_{abc=n}f(a)g(b)h(c) $$
   （$abc=n$ を満たす正の整数の 3 つ組全体にわたる和）に等しいことによる。実際 $((f*g)*h)(n)=\sum_{ec=n}\sum_{ab=e}f(a)g(b)h(c)$ であり、3 つ組 $(a,b,c)$ は $e=ab$ によって 1 回ずつ現れる。$(f*(g*h))(n)$ も同様である。
2. $(f*\varepsilon)(n)=\sum_{ab=n}f(a)\varepsilon(b)$ で $\varepsilon(b)\neq0$ となるのは $b=1$ だけなので、値は $f(n)$ である。
3. $g(1):=1/f(1)$ とし、$n\ge2$ について $n$ より小さい値が定まったとして
   $$ g(n):=-\frac1{f(1)}\sum_{\substack{d\mid n\\ d< n}}g(d)\,f\!\left(\frac nd\right) $$
   と帰納的に定める。これは $(f*g)(n)=f(1)g(n)+\sum_{d\mid n,\,d< n}g(d)f(n/d)$ が $n=1$ で $1$、$n\ge2$ で $0$ になるという条件をちょうど $g(n)$ について解いたものなので、$f*g=\varepsilon$ である。逆に $f*g=\varepsilon$ を満たす $g$ は、この等式から $g(1),g(2),\dots$ が順に一意に決まるので一意である。$\mathbf{1}(1)=1\neq0$ で、thm-mobius-divisor-sum により $\mathbf{1}*\mu=\varepsilon$ なので、$\mathbf{1}^{-1}=\mu$ である。
4. $f,g$ が乗法的なら $(f*g)(1)=f(1)g(1)=1$ で、$f*g$ は恒等的に $0$ ではない。$m,n$ を互いに素とする。$mn$ の約数 $d$ は、$d_1:=\gcd(d,m)$、$d_2:=\gcd(d,n)$ によって $d=d_1d_2$ とただ 1 通りに書け、$d_1\mid m$、$d_2\mid n$ である（素因数分解で $mn$ の各素数が $m$ か $n$ の一方だけに現れることによる）。逆に $d_1\mid m$、$d_2\mid n$ なら $d_1d_2\mid mn$ である。この対応で $mn/d=(m/d_1)(n/d_2)$ であり、$d_1$ と $d_2$、$m/d_1$ と $n/d_2$ はそれぞれ互いに素なので
   $$ (f*g)(mn)=\sum_{d_1\mid m}\sum_{d_2\mid n}f(d_1)f(d_2)\,g\!\left(\frac m{d_1}\right)g\!\left(\frac n{d_2}\right)=(f*g)(m)\,(f*g)(n) $$
   である。$\square$

1 は $F=f*\mathbf{1}$、2 は $f=\mu*F$ と書ける。1 が成り立てば、prop-mobius-dirichlet-basic の 1–3 により
$$ \mu*F=\mu*(f*\mathbf{1})=f*(\mu*\mathbf{1})=f*\varepsilon=f $$
である。2 が成り立てば同様に $f*\mathbf{1}=(\mu*F)*\mathbf{1}=F*(\mu*\mathbf{1})=F$ である。$\square$

Eulerのφ関数 の記事の定理「Gaussの約数和公式」により、すべての $n$ について $\sum_{d\mid n}\varphi(d)=n$、すなわち $\varphi*\mathbf{1}=\mathrm{id}$ である。thm-mobius-inversion により $\varphi=\mu*\mathrm{id}$ であり、これが 1 つ目の等式である。$\mu$ と $\mathrm{id}$ は乗法的なので、prop-mobius-dirichlet-basic の 4 により $\varphi$ も乗法的である。素数冪 $p^e$（$e\ge1$）では、$\mu(p^j)=0$（$j\ge2$）なので
$$ \varphi(p^e)=\mu(1)p^e+\mu(p)p^{e-1}=p^e-p^{e-1}=p^e\Bigl(1-\frac1p\Bigr) $$
であり、$n=\prod p^{e}$ について掛け合わせて 2 つ目の等式を得る。$\square$

thm-mobius-divisor-sum により、$\sum_{d\mid\gcd(k,n)}\mu(d)$ は $\gcd(k,n)=1$ なら $1$、そうでなければ $0$ である。$d\mid\gcd(k,n)$ は「$d\mid k$ かつ $d\mid n$」と同値なので（最大公約数 の記事の定理「公約数と最大公約数の約数」）、求める個数は
$$ \sum_{k=1}^N\ \sum_{\substack{d\mid n\\ d\mid k}}\mu(d)=\sum_{d\mid n}\mu(d)\cdot\#\{1\le k\le N\mid d\mid k\}=\sum_{d\mid n}\mu(d)\left\lfloor\frac Nd\right\rfloor $$
である。$\square$

長さ $n$ の文字列 $w$ と整数 $s$ について、すべての $i$ で $w_i=w_{i+s}$（添字は $n$ を法として $1,\dots,n$ に読む）が成り立つとき、$w$ は $s$ だけ巡回的にずらしても不変であるという。そのような $s$ の全体 $H(w)$ は和と差で閉じ、$n$ を含む。$d\mid n$ について、$w=u^{n/d}$（$|u|=d$）と書けることは $d\in H(w)$ と同値である。
$H(w)$ の正の元のうち最小のものを $d_0$ とする。$s\in H(w)$ を $s=td_0+r$（$0\le r< d_0$）と割ると $r=s-td_0\in H(w)$ なので、最小性から $r=0$ であり、$H(w)=d_0\mathbb{Z}$ である。特に $n\in H(w)$ から $d_0\mid n$ である。よって $w=u_0^{n/d_0}$（$u_0$ は $w$ の最初の $d_0$ 文字）と書ける。$u_0$ は原始的である。実際 $u_0=v^{d_0/e}$（$e\mid d_0$、$e< d_0$）なら、$w=v^{n/e}$ となって $e\in H(w)$ となり、$d_0$ の最小性に反する。
逆に $w=u^{n/d}$（$d\mid n$、$u$ は長さ $d$ の原始的な文字列）とすると $d\in H(w)=d_0\mathbb{Z}$ なので $d_0\mid d$ であり、$u$ は $w$ の最初の $d$ 文字なので $u=u_0^{d/d_0}$ である。$u$ が原始的なので $d=d_0$、$u=u_0$ である。
以上から、長さ $n$ の文字列はそれぞれ、$n$ の約数 $d$ と長さ $d$ の原始的な文字列 $u$ の組にただ 1 通りに対応する（$w=u^{n/d}$）。文字列は全部で $q^n$ 個あるので、すべての $n$ について
$$ q^n=\sum_{d\mid n}P_q(d) $$
である。thm-mobius-inversion を $F(n)=q^n$、$f=P_q$ に適用して主張を得る。$\square$