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

ゼータ変換 $\zeta$ とメビウス変換 $\mu$ はどちらも関数 $f:\{0,1\}^n \to R$ に作用する高階関数である。$R$ は環とする。ゼータ変換は負元を要求しないが、メビウス変換は負元を要求する。なお、サイズ 2n の配列を map するものと考えても良い。

定義は次の通り。

$$ \zeta f(Y) = \sum_{X \subset Y} f(X) $$ $$ \mu f(Y) = \sum_{X \subset Y}(-1)^{|Y\setminus X|}f(X)$$

高速メビウス変換は高速ゼータ変換の逆変換になっている。つまり

$$ \mu \zeta f(Y) = f(Y) $$

が成り立つ。

この変換を高速に行うアルゴリズムを、高速ゼータ変換・高速メビウス変換と呼ぶ。C++ でのコードを以下に示す。

vector<int> fast_zeta_transform(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> fast_mobius_transform(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;
}

本質的には bitDP である。下位から上位に値を伝搬させているのだが、そのとき重複伝搬が起こらないように遷移が組まれている。証明する際には重ね合わせの原理を意識して、一点からの影響のみを調べると分かりやすいだろう。

ゼータ変換とメビウス変換は単体で用いることの方が多いが、組み合わせると畳み込みを高速化できるという性質がある。畳み込みは以下のように定義される。

$$ (f \ast g)(Y) = \sum_{S+T=Y} f(S)g(T) $$

ゼータ変換を適用すると単純になる。

$$ \zeta (f \ast g)(Y) = \zeta f (Y) \zeta g(Y) $$

証明は難しくない。

$$ \zeta (f \ast g)(Y) = \sum_{X \subset Y} \sum_{S+T=X} f(S)g(T) = \left( \sum_{X \subset Y} f(X) \right) \left( \sum_{X \subset Y} g(X) \right) $$

この記事では下位集合に対するゼータ変換およびメビウス変換を示したが、上位集合に対しても同様に議論することができる。