Skip to content →

ゼータ・メビウス変換

各点積・各点和のゼータ・メビウス変換

\(k\) 変数多項式 \(P\) の写像を各点積・各点和で定義する。
\(x\) の down-set の各点積を逆元を掛けて戻すと、
\begin{align}(P(\zeta f_1, \ldots,\zeta f_k))(x)
&= \sum_{\bigvee x_i\leq x} P(f_1(x_1), \ldots,f_k(x_k)) \\
(\zeta^{-1}P(\zeta f_1, \ldots,\zeta f_k))(x)
&= \sum_{\bigvee x_i = x} P(f_1(x_1), \ldots,f_k(x_k)) \\
\end{align}となる。同様に \(x\) のup-set の各点積を逆元を掛けて戻すと
\begin{align}
(P(f_1\zeta , \ldots,f_k\zeta ))(x)
&= \sum_{\bigwedge x_i\geq x} P(f_1(x_1), \ldots,f_k(x_k)) \\
(P( f_1\zeta, \ldots,f_k\zeta)\zeta^{-1})(x)
&= \sum_{\bigwedge x_i = x} P(f_1(x_1), \ldots,f_k(x_k)) \\
\end{align}となる。

Twisted and/or convolution

\(f, g : P \to K\) に対して、各点積を \(f*g\)、内積を \(fg\) と書く。

  • \(f(g*h)=(g*f)h\)
  • \(\xi \in I(P, K)\) に対して \((f \xi) g = f (\xi g)\)

の二つが成り立つ。従って、\(f\zeta^{-1}(\zeta g * \zeta h) = (\zeta g * f\zeta^{-1})\zeta h\) となる。特に、\(h(x)=\delta_{k,x}\) とすると、\(\sum g(i) h(i \land k)\) が得られるので、\((\zeta g * f\zeta^{-1})\zeta\) は各 \(k\) に対するこのような変換を表している(yuki1503)。

各点積・各点和のメビウス変換前後の関係式

upset の各点和・各点積は変形すると\begin{align}
&\sum_{x \geq \bigvee x_i} P(f_1(x_1), \ldots,f_k(x_k))\\
=& P( f_1\zeta, \ldots,f_k\zeta)(x)\\
=& P( f_1\zeta, \ldots,f_k\zeta)\zeta^{-1}\zeta(x)\\
=& \sum_{y \in L} \#[y, x] \sum_{\bigvee x_i = y} P(f_1(x_1), \ldots,f_k(x_k))
\end{align}となる。

downset では $$\sum_{x \leq \bigwedge x_i} P(f_1(x_1),\ldots,f_k(x_k)) = \sum_{y \in L} \#[x, y] \sum_{\bigwedge x_i = y} P(f_1(x_1), \ldots,f_k(x_k))$$となる。例えば、整除束で \(P : t \mapsto t^m,f_i=\zeta\)とすると、\(\sum_{x=1}^M \sigma_0^m(x) = \sum_{a\in \mathbb{N}^m, x=\bigvee a_i} \lfloor M/x \rfloor\) となる(yuki1781)。

ランク付きゼータ・メビウス変換

モジュラー束では、$$ \sum \rho(x_i) = \rho\left(\bigvee x_i \right) \Leftrightarrow x_i \land x_j = \hat 0$$である。従って、不定元 \(t\) を用いて、$$\hat f(x)=f(x)t^{\rho(x)}$$ とすると、$$(\zeta^{-1}P(\zeta \hat f))(x)$$ の係数には、\(x_i \land x_j = \hat 0\) を満たす交わり \(\bigvee x_i= x\) が分離されている。例えば \(B_n\) では、\(x\) の分割に対応する。

特定のランク全体のゼータ・メビウス変換

あるランクの要素全体についてのゼータ・メビウス変換は次の様に変形すると、高速に計算できる場合がある。
\begin{align}
\sum_{\rho(x) = k} f(x)\zeta^{-1} &= \sum_{\rho(x) = k} \sum_{y \leq x} f(y)\mu(y, x) \\
&= \sum_{y} f(y) \sum_{y \leq x, \rho(x) = k} \mu(y, x)
\end{align}適切な前計算の下、\(B_n\) などでは \(\sum_{y \leq x, \rho(x) = k} \mu(y, x)\) が \(O(1)\) で求まる。

整除束のメビウス変換

\(\prod_{i=1}^M D_{N}\) 上のスパースな関数(非零が \(K\) 個)に対する downset の和を取りたいとする。\(i\) の約数が \(O(i^\epsilon)\) 個しかないので、約数を列挙しておくことで \(O(N^\varepsilon K)\) で計算できる。メビウス変換も同様(ABC230G)。

\(n=\prod p_i^{e_i}\) と因数分解できるとすると、整除関係の束は各素因数の冪の束の直積に分けられて

\begin{align}
&\mu_{D_n} \\
={}& \prod \mu_{D_{p_e^{e_i}}} \\
={}& \prod \mu_{\pmb{e_i+1}}
\end{align}

とできる。各素数のメビウス変換を独立にすることで、\(O(n \log n \log n)\) で \(f\mu\) が列挙できる。

各 \(x\) の downset \(I_x\) が事前に列挙でき、更に事前にトポロジカルソートができるような場合には、大きい元から計算することで、\(\sum |I_x|\) で \(f \mu \) が列挙できる。例えば、\(D_n\) では \(O(n \log n)\) になる。

無平方数

任意の正整数は、正の無平方数と正の平方数の積に一意に書けるので、無平方数と平方数の指示関数を\(f, \zeta_2\)と置くと、$$\sum_{d \preceq n} \zeta_2(\hat 0, d)f(d, n) = 1$$が任意の正整数 \(n\) について成り立つ。\begin{align}
&\zeta_2f = \zeta \\
&f= \zeta_2^{-1}\zeta \\
&f = \sum_{d^2 \preceq n} \mu(d)
\end{align}求める値は \(\sum_{i=1}^n f(\hat 0, i) = \sum_{d=1}^N\mu(d)\lfloor N / d^2\rfloor\)
である。

Dirichlet積

整除束の upset の畳み込みは $$(\xi f)(\hat 0, n)=\sum_{d \preceq n} \xi(n/d) g(d)$$ だが、これはディリクレ積の畳み込み$$\sum_{i} \xi(i) i^{-s}\sum_{j} f(j) j^{-s} = \sum_{n}\sum_{d \preceq n} \xi(n/d)f(d) n^{-s}$$として書ける。

分割束のメビウス変換

\([n]\) を \(k\) 個に分割する方法の個数を \(s(n, k)\) とすると、$$x^n = \sum s(n, k)x(x-1)\cdots(x-k+1)$$
が成り立つ。なぜならLHS = x 色で n 人を塗る方法の数, RHS = n 人を k 個のグループに分けた後、各グループ毎に人を塗る方法の数だから。 \(x\) で割って \(0\) を代入すると、$$\mu(\hat 0, \Pi_n) = (n – 1)!(-1)^{n-1}$$ を得る。分割束の区間は分割束の直積に同型なので、これで全て計算できる。

\(f\) が分割の成分の直積で書けるとき(ABC236H)、\begin{align}
&\mu f(\hat 0, \Pi_n) \\
={}&\sum_{\pi=\{B_1,\ldots,B_k\}\in \Pi_n}\mu(\hat 0,\pi)f(\pi) \\
={}&\sum_{k}\frac{1}{k!}\prod_{B_i \neq \emptyset, \bigsqcup_{i=1}^k B_i=[n]}\mu(\hat 0,\{B_i\})f(\{B_i\})
\end{align}となる。これは、subset convolution で処理できる形である。

任意の分割 \(\pi = \{B_1, \ldots, B_k\}\) に対して $$f(\pi) = \prod f(\#B_i)$$
が成り立つとする。

\begin{align}
&\sum_{\hat 0 \leq \pi \leq \Pi_n} \mu(\hat 0, \pi) f(\pi) \\
=& \sum_{\{B_1,\ldots,B_k\}=\pi \leq \Pi_n} \prod \mu(\#B_i)f(\#B_i)\\
=& n!\sum_{\sum i a_i = n} \left(\frac{\mu(\hat 0, \Pi_i)f(i)}{i!}\right)^{a_i}\\
=& n!\sum_{\sum i a_i = n} \left((-1)^{i-1}\frac{f(i)}{i}\right)^{a_i}\\
\end{align}
畳み込みで \(O(n \log n)\) で計算できる。

$$f(\pi)=f(\{\!\!\{\#B_i : i \in \mathbb{N}\}\!\!\})$$のとき、
\begin{align}
&\sum_{\hat 0 \leq \pi} \mu(\hat 0, \pi)f(\pi) \\
=&\sum_{k=1}^N \sum_{\lambda \vdash k} {N \choose \lambda_1, \ldots, \lambda_l} f(\lambda) \prod \mu(\hat 0, \pi_{\lambda_i})\end{align}

となる。next-permutation と同様のアイディアにより \(\lambda \vdash n\) は \(O(np(n))\) で求まるので、上の計算は \(O(\sum i p(i)) = O(\sqrt N 14^{\sqrt{N}})\) でできる。

部分束のメビウス変換

\(M \subseteq L\) が \(L\) の部分束だとする。定義域を自然に拡張して\begin{eqnarray}
f_L(x)
=
\begin{cases}
f_M(x) & ( x \in M ) \\
0 & ( x \not \in M )
\end{cases}
\end{eqnarray}
とすると、\(\zeta_M f_M = \zeta {f|}_M\) だから \(\zeta_M^{-1}f_M = \zeta^{-1}{f|}_M\) となる。つまり、元の束でメビウス反転してから定義域を制限すればよい。

縮約束のメビウス変換

\(V(G)\) の分割 \(\pi\) のうち、任意の \(S \in \pi\) が誘導する部分グラフ \(G[S]\) が連結なものからなる集合は束をなす。この束は、分割束 \(\Pi_{|V(G)|}\) の部分束であるから、メビウス変換ができる。彩色多項式の計算などに用いる。

非空な downset/upset のゼータ変換

\(\hat 0\) を除いた downset の和は \(\zeta-1\) で取れる。直積の束 \(\prod L_i\) では \(\prod (\zeta_i-1)\) となる。\(g=\prod \zeta_i f \) が容易に求まるならば、\(g\) に \(\prod (1-\zeta_i^{-1})\) を掛けるだけでよい(ABC230G)。

参考文献

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA