ゼータ変換とメビウス変換

高速ゼータ変換／高速メビウス変換 - naoya_t@hatenablogで誤りを指摘されたので、反省の意味を込めて自分でちゃんと考えた。
メビウスの反転公式 - Wikipediaを元にしているけど、よくわかってないので間違ってたら教えて

追記
全部隣接代数 (順序理論) - Wikipediaに書いてました。ちゃんちゃん
追記終わり

○ゼータ変換・メビウス変換とは
G$G$を可換順序群、R$R$を可換環とする。
このとき、{f:G+∪{0}→R}$\{f:G^{+}\cup \{0\}\to R\}$への作用素ζ$\zeta$を、(ζf)(x)=∑0≤y≤xf(y)${\displaystyle (\zeta f)(x)=\sum _{0\le y\le x}f(y)}$　により定める。
これをゼータ変換という。
もしζμ=ϵ$\zeta \mu =ϵ$となるμ$\mu$が存在すれば、ゼータ変換には逆変換が存在し
(ζ−1f)(x)=∑0≤y≤xμ(y)f(x−y)${\displaystyle ({\zeta }^{-1}f)(x)=\sum _{0\le y\le x}\mu (y)f(x-y)}$　となる。これをメビウス変換という。
ただし ϵ(x)={10(x=0)(otherwise)$ϵ(x)=\{\begin{array}{ll}1& (x=0)\\ 0& (\text{otherwise})\end{array}$である。

式の形を見れば分かる通り、これらは畳み込み積の計算であり、ζf=1∗f$\zeta f=1\ast f$である。
（G=R=R$G=R=\mathbb{R}$の場合などをイメージしてみよ）
ϵ$ϵ$は畳み込みにおける単位元であり、1∗μ=ϵ$1\ast \mu =ϵ$であるから、μ$\mu$は定数関数1の畳み込みにおける逆元である。
このことからμ∗(ζf)=μ∗(1∗f)=(μ∗1)∗f=f$\mu \ast (\zeta f)=\mu \ast (1\ast f)=(\mu \ast 1)\ast f=f$により、逆変換ができることが確かめられる。

は？

○競プロでよく見るやつ
・高速ゼータ変換
集合Xがあり、べき集合上の関数f:P(X)→Rがある。
g(S)=∑T⊂Sf(T)${\displaystyle g(S)=\sum _{T\subset S}f(T)}$を高速に求める
・高速メビウス変換
集合Xがあり、べき集合上の関数f:P(X)→Rがある。
g(S)=∑T⊂S(−1)|T|f(S∖T)${\displaystyle g(S)=\sum _{T\subset S}(-1{)}^{|T|}f(S\setminus T)}$を高速に求める

「普通にやるとO(3^N)だけどO(N*2^N)でできるよ～」というやつ。
これは、べき集合P(X)を自然にG=ZX$G={\mathbb{Z}}^X$へ持っていたと考えているようなもの（ほんとに？）
（もう少し仮定を弱めてGは群でなくてもよいのでは？？）
※この例でいうとS∖T$S\setminus T$のように、ある種の"差"が計算できる必要があると思っていたので、fの定義域を群にしたのだけど、wikipediaを見ると、区間を引数にとる関数だと思えばよかったらしい。なるほど

○メビウスの反転公式
正整数上の関数f,gが
g(n)=∑d|nf(d)${\displaystyle g(n)=\sum _{d|n}f(d)}$
を満たすとする。このとき
f(n)=∑d|nμ(d)g(n/d)${\displaystyle f(n)=\sum _{d|n}\mu (d)g(n/d)}$
が成り立つ。ただしμ$\mu$はメビウス関数

これはG=Q∗/{±1}⊂Zω$G={\mathbb{Q}}^{\ast }/\{\pm 1\}\subset {\mathbb{Z}}^{\omega }$に自然な順序x≤y⟺y/x∈Z$x\le y⟺y/x\in \mathbb{Z}$を定めたものと言える

〇メビウス変換と包除原理
Uを集合とし、N個の集合Ai⊂U$A_i\subset U$がある。
X={1,...,N}とし、f:P(X)→Z$f:P(X)\to \mathbb{Z}$を
f(S)=∣∣∣∣⋂i∈SAi∣∣∣∣${\displaystyle f(S)=\left|\bigcap _{i\in S}{A}_i\right|}$　により定める。
g(S)=∣∣∣∣⋃i∈SAi∣∣∣∣${\displaystyle g(S)=\left|\bigcup _{i\in S}{A}_i\right|}$　とおくと、包除原理から
∣∣∣∣⋃i∈SAi∣∣∣∣=∑∅≠T⊂S(−1)|T|+1∣∣∣⋂i∈TAi∣∣∣=∑∅≠T⊂S(−1)|T|+1f(T)=∑T⊂S(−1)|T|+1f(T)−f(∅)=(−1)|S|+1∑T⊂S(−1)|S∖T|f(T)−f(∅)=(−1)|S|+1∑T⊂S(−1)|T|f(S∖T)−f(∅)=(−1)|S|+1(ζ−1f)(S)−f(∅)$$\begin{gathered} {\displaystyle \left|\bigcup _{i\in S}{A}_i\right| \\ =\sum _{\mathrm{\varnothing }\ne T\subset S}(-1{)}^{|T|+1}\left|\bigcap _{i\in T}{A}_i\right| \\ =\sum _{\mathrm{\varnothing }\ne T\subset S}(-1{)}^{|T|+1}f(T) \\ =\sum _{T\subset S}(-1{)}^{|T|+1}f(T)-f(\mathrm{\varnothing }) \\ =(-1{)}^{|S|+1}\sum _{T\subset S}(-1{)}^{|S\setminus T|}f(T)-f(\mathrm{\varnothing }) \\ =(-1{)}^{|S|+1}\sum _{T\subset S}(-1{)}^{|T|}f(S\setminus T)-f(\mathrm{\varnothing }) \\ =(-1{)}^{|S|+1}({\zeta }^{-1}f)(S)-f(\mathrm{\varnothing }) \\ } \end{gathered}$$
となる。
よってあらかじめf(∅)$f(\mathrm{\varnothing })$を|U|ではなく|∅|$|\mathrm{\varnothing }|$=0と定めておけば、g(S)=(−1)|S|+1(ζ−1f)(S)$g(S)=(-1{)}^{|S|+1}({\zeta }^{-1}f)(S)$となることが確かめられる。