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

note 2018-07-28: 参考図書としては Fedor V. Fomin, Dieter Kratsch. Exact Exponential Algorithms, Springer, 2010 がある。この本の中では、畳み込みは別の定義がされている。

ゼータ変換とメビウス変換は集合関数から集合関数への変換である。定義を以下に示す。 $$ \zeta f(Y) = \sum_{X \subseteq Y} f(X) $$ $$ \mu f(Y) = \sum_{X \subseteq Y}(-1)^{|Y\setminus X|}f(X)$$

高速メビウス変換は高速ゼータ変換の逆変換になっており $\mu \zeta f = f$ が成り立つ。ゼータ変換(メビウス変換)を高速に行うアルゴリズムを高速ゼータ変換(高速メビウス変換)と呼ぶ。処理は動的計画法に近い。

vector<int> zeta(vector<int> f) {
    for (int i = 0; (1 << i) < f.size(); i++) {
        for (int j = 0; j < f.size(); j++) {
            if (j & 1 << i) {
                f[j] += f[j ^ 1 << i];
            }
        }
    }
    return f;
}

vector<int> mu(vector<int> f) {
    for (int i = 0; (1 << i) < f.size(); i++) {
        for (int j = 0; j < f.size(); j++) {
            if (j & 1 << i) {
                f[j] -= f[j ^ 1 << i];
            }
        }
    }
    return f;
}

ゼータ変換は畳み込みに関して良い性質を持つ。畳み込みは以下で定義される。 $$ (f \ast g)(Y) = \sum_{S \cup T=Y} f(S)g(T) $$

このとき以下の性質が成り立つ。 $$ \zeta (f \ast g)(Y) = \zeta f (Y) \zeta g(Y) $$