メビウス関数

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

古典的メビウス関数

• $\mu (n)=\{\begin{array}{lc}(-1{)}^k& (nがk個の異なる素数の積)\\ 0& (otherwize)\end{array}$
• 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
  • ゼータ関数が累積和に相当し、メビウス関数はその逆に相当する。差分作用素

https://ja.wikipedia.org/wiki/隣接代数_(順序理論)

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