よく言及されるものに3通りある

n=1の時は「0個の異なる素数の積」なので1になる

n=4の時は「異なる素数の積」でないので0になる

aがbを割り切る「整除関係」(a \prec b, a | b)は半順序である。

ここに注目して抽象化したものが隣接代数。

隣接代数のゼータ関数は、すべての空でない区間 [a, b] に対し、ζ(a,b) = 1 となるような関数で、メビウス関数はゼータ関数の乗法逆元。

この隣接代数の具体例で、

1: 正整数全体に整除関係を入れたもの

→古典的メビウス関数に帰着

2: 有限集合の部分集合全体のなす集合(べき集合)に包含関係を入れたもの

→集合のサイズの差で定義されたメビウス関数

包除原理につながる

3: 自然数全体の集合に大小関係を入

→0,0,…,0,-1,1

ゼータ関数が累積和に相当し、メビウス関数はその逆に相当する。差分作用素

Sum over Subsetsでの高速ゼータ変換は2で、高速ゼータ変換の約数版 O(N log(log(N))) - noshi91のメモは1