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}となる。

基底

束 \(L\) の交わりによって \(K\)上の双線形形式 \(A\) を定める。
\(\delta_{i}’\stackrel{\text{def}}{=}\zeta^{-1} \delta_{x, i}\) とする。 \(\zeta\delta_{i}’ = \delta_{x, i}\) より \(\delta_{i}’\) は \(A\) を張る。積は

\begin{align}
\delta_{i}’ \cdot \delta_{j}’
&= \zeta^{-1}(\zeta \delta_{i}’ * \zeta \delta_{j}’) \\
&= \zeta^{-1}(\delta_{x, i} * \delta_{x, j}) \\
&= \zeta^{-1} \delta_{x, i}\delta_{x, j} \\
&= \begin{cases}
\delta_i’ & ( i = j ) \\
0 & ( i \neq j )
\end{cases}
\end{align}
となる。従って、\(A\) は \(\delta_i’\) を基底として、\(\bigoplus_{t \in L} K_t\) 同型
(\(K_t \cong K\)) である。

Weisnerの定理

\(a \neq \hat 1\) とする。
\begin{align}
&\sum_{i, i \land a = x} \mu(i, \hat 1) \\
=&\delta_a \cdot \zeta^{-1} \delta_{\hat 1} \\
=&\zeta^{-1} (\zeta \delta_a \cdot \zeta \zeta^{-1} \delta_{\hat 1}) \\
=&\zeta^{-1} (\zeta \delta_a \cdot \delta_{\hat 1}) \\
=&\hat 0
\end{align}

cross-cut定理

束\(L\)の元の集合\(X\)が

  • \(\hat 1 \not \in X\)
  • \(\forall s \in L, s \neq \hat 1 \Rightarrow \exists t, s \leq t \in X
    \)

を満たすとする。\(N_k\) を \(X\) の \(k\) 元集合のうち結びが \(\hat 0\) となるようなものの個数とする。\(\mu(\hat 0, \hat 1) = \sum_k N_k (-1)^k\) が成り立つ。

\begin{align}
&\sum_k N_k (-1)^k \\
= & \left(\prod_t (\delta_{\hat 1} – \delta_t) \right)(\hat 0) \\
= & \left(\zeta^{-1} \prod_t'(\zeta\delta_{\hat 1} – \zeta\delta_t) \right)(\hat 0) \\
= & \mu(\hat 0, \hat 1)
\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))$$となる。

\(\sum_{a=1}^M \sum_{x\in \mathbb{N}^m} \lfloor M/\mathrm{lcm}(x) \rfloor = \sum_{d=1}^M \sigma_0^m(d)\) を示せ。(yukicoder1781)

\begin{align}
&\sum_{a=1}^M \sum_{x\in \mathbb{N}^m,\\ a=\bigvee x_i} \lfloor M/a \rfloor \\
=&\sum_{d=1}^M \sum_{x\in \mathbb{N}^m ,\\ a=\bigvee x_i} \zeta(a, d) \\
=&\sum_{d=1}^M \sum_{x\in \mathbb{N}^m ,\\ a=\bigvee x_i} \left(\prod_i \zeta(\hat 0, x_i)\right)\zeta(a, d) \\
=&\sum_{d=1}^M \left( (\zeta^2*\zeta^2*\cdots*\zeta^2)\zeta^{-1}\zeta\right)(\hat 0, d) \\
=&\sum_{d=1}^M (\zeta^2*\zeta^2*\cdots*\zeta^2)(\hat 0, d) \\
=&\sum_{d=1}^M \sigma_0^m(d) \\
\end{align}

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

モジュラー束では、$$ \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)\) で求まる。

Boolean束

\(s_i := \{i, i + 1, \ldots, i+k-1\}\) \((1 \leq i \leq n – k + 1)\) を原子とする \(B_n\) の部分束を \(L\) とする。\(L\) のメビウス関数を求めたい。\([n] \setminus \{i\}\) \((2 \leq i \leq k \ \lor \ n-k+2 \leq i \leq n – 1)\) を \(L\) に加えてもそれらは既約なので、\(\mu(\hat 0, \hat 1)\) は不変である。従って、任意の補原子はある \(i\) \((2 \leq i \leq n – 1)\) を用いて \([n] \setminus \{i\}\) と書けるとしてもよい。補原子全体を \(X\) と置く。cross-cut 定理より、 \(N_m\) を \(X\) の \(m\) 元集合であって交わりが \(\hat 0\) であるものの個数とすると \(\mu(\hat 0, \hat 1) = \sum_m N_m(-1)^m\) である。交わりが \(\hat 0\) となるための必要十分条件は、\(m\) 元集合として選ばれなかった補原子の添え字を昇順に並べたときに、連続する整数の長さが \(k\) 未満であることである。このような選び方は \([x^{n-m}]\left(1+x+\cdots+x^{k-1}\right)^{m+1}\) 通りある。以下、機械的に計算すると、
\begin{align}
\mu(\hat 0, \hat 1)=&\sum_m N_m (-1)^m \\
={}& \sum_m \sum_m [x^{n-m}]\left(1+x+\cdots+x^{k-1}\right)^{m+1}(-1)^m \\
={}& [x^{n}]\frac{1+x+\cdots+x^{k-1}}{1+x(1+x+\cdots+x^{k-1})} \\
={}& [x^{n}]\frac{1 – x^{k}}{1 – x^{k+1}} \\
={}& [x^{n}](1 – x^{k})\sum_{i \geq 0} x^{i(k+1)} \\
={}& \begin{cases}
1 & ( n = 0 \pmod {(k + 1)}) \\
-1 & (n = k \pmod {(k + 1)} ) \\
0 & (\text{otherwise})
\end{cases}
\end{align}
を得る。

長さ \(k\) \((\geq 2)\) 以上の任意の連続部分列が条件 \(P\) を満たさない場合を数えたい。条件 \(P\) を無視したときの長さ \(n\) の列の個数が \(a_1^n\)、\(P\) を満たす長さ \(i\) の列の個数が \(b_i\) だとする。メビウス変換により、求める場合の数のOGFは $$\frac{1}{1-\left(a_1x-\sum_{i \geq 1} b_{ki}x^{ki}+\sum_{i \geq 1} b_{ki+1}x^{ki+1}\right)}$$ となる。AGC058Dは \(k=3\) で3変数の場合。yuki1962は \(a_1 = \sum_j c_j, b_{i}=\sum_j c_j^i\) で $$\frac{1}{1-\sum_i \frac{\sum_{j = 1}^{k – 1} (c_ix)^j}{1+\sum_{j = 1}^{k – 1} (c_ix)^j}}$$とした場合。\(f_i = \frac{\sum_{j = 1}^{k – 1} (c_ix)^j}{1+\sum_{j = 1}^{k – 1} (c_ix)^j}\) と置くと $$\sum_{j=1}^{k-1} (c_ix)^j = \frac{f_i}{1-f_i}$$
となり、1個以上並べることで長さ \(k-1\) 以下の列を生成する形式的なオブジェクトのOGFが \(f_i\) になっている(かならいさんの解説)。

整除束のメビウス変換

\(\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