色々な畳み込み
一般的な理解から始めるのではなく，まずは具体例をざっと確認します．
$A$ を数列とします．つまり，$A = [A_0,A_1,A_2,\ldots]$ のように数が非負整数で添字付けられていて並んでおり，その全体を $A$ と書きます．
※ 1-index な数列を扱ったり，無限数列ではなく有限数列を扱う必要があるときもあります．
2つの数列 $A,B$ から，第3の数列 $C$ を作る次のような計算は総じて「畳み込み」（convolution）と呼ばれ， $C = A*B$ のような記法をとることが多いです．
(1) $C_k = \sum_{i+j=k}A_iB_j$.
(2) $C_k = \sum_{ij=k}A_iB_j$.
(3) $C_k = \sum_{\max(i,j)=k}A_iB_j$.
(4) $C_k = \sum_{\min(i,j)=k}A_iB_j$.
(5) $C_k = \sum_{\gcd(i,j)=k}A_iB_j$.
(6) $C_k = \sum_{\mathrm{lcm}(i,j)=k}A_iB_j$.
(7) $C_k = \sum_{i \,\mathrm{xor}\, j=k}A_iB_j$.
(8) $C_k = \sum_{i \, \mathrm{and}\, j=k}A_iB_j$.
(9) $C_k = \sum_{i \,\mathrm{or}\, j=k}A_iB_j$.
※ xor, and, or はbit演算です（したがって集合に関する演算と見てもよいです）．
※ (2)(3)(4)は1-indexed。(3)(5)(6)(7)(8)は有限項を除き0であるような数列を考える必要があります．
※ 二項演算があると畳み込みが定義されると考えてよいでしょう。
慣れないうちは「$A_0,A_1,\ldots,B_0,B_1,\ldots,C_0,C_1,\ldots$ のたくさんの数の間の関係式」として目が行くと思いますが， 数列全体は 1 つのものと考えて，「$A$ と $B$ から $C$ を作る操作」というように、登場人物は3つであるかのように理解していくことが望ましいと思います．
記号としても、以後 $C_k,A_i,B_j$ を直接見ることはなるべく避けて、$C = A*B$という記法を積極利用します。もちろん「(1)～(9)のどれ？」などの情報は必要ですので、文脈で指定しているか、または全てに共通の性質を論じている場合ということになります。
半群代数
畳み込みは、なかなか「お気持ち」が掴みづらく、始めは人工的で不自然な概念に見えるかもしれません。しかし、実際には「半群の演算を線形に拡張したもの」として極めて自然な概念です。このことを確認してみます。
一般に、集合 $G$ に結合法則を満たす演算$\cdot\colon G\times G\longrightarrow G$が定義されているとき，$G$ は半群であるといいます． 数学語がしんどい方は，次のような具体例を念頭に置いてください．例えば、集合 $G = \mathbb{Z}_{\geqq 0}$ に次のような演算を定める（演算1つだけを考える）と，すべて半群が得られます。
(1)和 (2)積 (3)$\max$ (4)$\min$ (5)$\gcd$ (6)$\mathrm{lcm}$ (7)$\mathrm{xor}$ (8)$\mathrm{and}$ (9)$\mathrm{or}$
$R$を環とします（環が分からない人は $R=\mathbb{Z}$ と思っておきましょう）．このとき，「$G$ の元の形式的 $R$ 係数線型結合」全体を $G$ の $R$ 上の半群代数といい，$R[G]$ と書きます。
※しばしば「〇〇環」と「〇〇代数」は同じ意味で用いられ、$R[G]$ を半群環と呼ぶこともあります．
※ $G$ が群なら群環、モノイドならモノイド環などとも言います。
例えば、$R=\mathbb{Z}$, $G$ として(2)の半群をとってみます．$G$ は集合としては$\mathbb{N}$ ですので，$R[G]$ は次のような集合です：
\[ R[G] = \{a_1[1] + a_2[2] + a_3[3] + \cdots\mid a_i\in R \}.\]
$G$ の元 $g$ たちの $R$ 係数線型結合ですが、本記事では半群と係数環の区別を強調するため$G$の元を$[g]$のように書いています．当然，係数を取り出すことで数列 $[a_1,a_2,a_3,\ldots]$ と対応付けることもできますが，「数列」と思うよりも「$[1], [2], [3], \ldots$ を指定個数持っている状態」と思う方が理解が易しくなると思います。
半群 $G$ の演算はただの積でした．$[2][3]=[6]$ といった要領ですね．これを $R$ 双線形に拡張することで， $R[G]$ における積を自然に定めることができます．例えば次のように積が計算されます．
$\begin{align*}
(5[1]+4[2]+3[3])(3[1]+2[2]+[3]) &= 15[1][1]+10[1][2]+5[1][3]+12[2][1]+8[2][2]+4[2][3]+9[3][1]+6[3][2]+3[3][3]\\
&=15[1]+10[2]+5[3]+12[2]+8[4]+4[6]+9[3]+6[6]+3[9]\\
&=15[1]+22[2]+14[3]+8[4]+10[6]+3[9].
\end{align*}$
この計算は、冒頭に述べた (2) の畳み込みの意味で，「$A = [5,4,3]$, $B = [3,2,1]$ に対して $A*B = [15,22,14,8,0,10,0,0,3]$」という計算に対応します（ただし数列は 1-indexed）。
このように、半群の元の形式的線形結合に対して
・半群の演算
・和の結合法則，交換法則
・分配法則
等が成り立つように積を定めたものが、畳み込みと呼ばれる計算です。
この知識が直接的に畳み込みの計算に役立つことは少ないかもしれませんが、畳み込みが自然な数学概念と感じるための一助になるのではないかと思います。
【注】 $G$ が連続構造を持つ群である場合には、うまく積分を用いて群環，畳み込みを定義したりします。$G = \mathbb{Z}$ の場合でも無限個の元の線形結合を扱うと，半群代数が自然に定義できない場合があります。積分や和を収束させるために適切な条件を付与して扱う必要がありますが，基本的な考え方は同様といってよいでしょう。本記事ではこのような問題は見ないフリをしていきます。
畳み込みの性質
証明はしませんが、 半群 $G$ の演算の性質が半群代数 $R[G]$ の性質が遺伝して、次のことが言えます。
・ $G$ の演算が結合法則を満たすので，$R[G]$ の積も結合法則を満たす。
・ $G$ の演算が交換法則を満たすならば，$R[G]$ の積も交換法則を満たす。
・ $G$ が単位元を持つならば，$R[G]$ も積について単位元を持つ。
単位元については、$e$ が $G$ の単位元であるとき $1[e]$ が $R[G]$ の単位元を与えます。
※ 積分を用いて畳み込みを定義するような場合には、単位元にのみ値を持ち積分が $1$ であるような関数（Dirac の delta 関数）が登場します。
「畳み込みは〇〇法則を満たします！」ということが分かると、基本的な推論を、通常の積との類似を辿って行うことができます。
・同じ数列 $A$ を何度も畳み込む：$A*A*\cdots*A$ ($n$個)ときには、$O(\log n)$ の回数の畳み込みで済む。
・$A*X=Y$ という関係があるとき、$A$ に逆元 $A^{-1}$ があれば、$X$ を $Y$ から復元できる：$X = A^{-1}*Y$。
畳み込みを「謎の操作」と思うよりも，「一種の積」と思うようにしていくと，抽象代数に詳しくなくとも適切な推論に辿り着きやすくはなると思います。
形式的べき級数・Dirichlet級数
数列の代わりに半群代数の元を考えると、畳み込みがそのまんまの意味でいかにも「積」と思えます。
いくつかの畳み込みには、半群代数よりも馴染みやすそうな対応物もあるので紹介します（とはいえ同型なので一緒と言えば一緒なのですが）．
形式的べき級数
特に形式的べき級数でのキャラ付けを狙っているわけではないですが、最近の私の記事ではお馴染みですね。
$f_A(x) = A_0+A_1x+A_2x^2+\cdots$ と $f_B(x) = B_0+B_1x+B_2x^2+\cdots$ の積を $f_C = C_0+C_1x+C_2x^2+\cdots$ とすると，
和に関して畳み込みの等式 $C = A*B$が成り立ちます．
つまり，和に関する畳み込みを考えることは形式的べき級数の積を考えることと等価です．
特殊な数列による畳み込み操作，文字式や関数の視線から見通しの良い意味づけを与えられる場合がありますね．
Dirichlet 級数
\[D_A(s) = \frac{A_1}{1^s} + \frac{A_2}{2^s} + \frac{A_3}{3^s} + \cdots\] の形の式は Dirichlet級数 と呼ばれます．
$s$への複素数の代入を考えることもありますが，ここでは単に形式的な和だと思っておきましょう．
$\frac{1}{n^s}\cdot \frac{1}{m^s} = \frac{1}{(nm)^s}$ という計算規則に基づくと，2つのDirichlet級数の積を自然に定義することができます．
この意味でDirichlet級数の等式 $D_A(s) D_B(s) = D_C(s)$ が成り立つことと，積に関する畳み込みの意味で $C=A*B$ が成り立つことは同値です．自然数の積に関する畳み込みは Dirichlet積（Dirichlet convolution） と呼ばれ，解析数論などで頻出です．
Dirichlet 級数、ゼータ変換、メビウス変換
形式的べき級数については別記事である程度掘り下げているので、本記事の残りの部分では、Dirichlet積と親しみながら、Dirichlet積のゼータ変換・メビウス変換に入門したいと思います。以下、数列はすべて $1$-indexedです。
代表的なDirichlet級数
◆単位元
数列 $I$ を、$ I = [1,0,0,0,\ldots]$ により定めます。対応するDirichlet級数は
\[\frac{1}{1^s}+ \frac{0}{2^s}+\frac{0}{3^s}+\frac{0}{4^s}+\cdots = 1\] です。数列のDirichlet convolution はDirichlet級数の積と対応するので，任意の数列 $A$ に対して $A=A*I$ となります。
◆ ゼータ関数・メビウス関数
数列 $\zeta$ を、$ \zeta = [1,1,1,1,\ldots]$ により定めます 。 対応するDirichlet級数は
\[\zeta(s) = \frac{1}{1^s}+ \frac{1}{2^s}+\frac{1}{3^s}+\frac{1}{4^s}+\cdots\] で、Riemannのゼータ関数と呼ばれる数学（解析数論）ではとても有名な関数です。 Dirichlet級数として逆元がとれます：
\[\frac{1}{\zeta(s)} = \frac{\mu(1)}{1^s} +\frac{\mu(2)}{2^s} +\frac{\mu(3)}{3^s} +\frac{\mu(4)}{4^s} + \cdots.\] この係数 $\mu(n)$ はメビウス関数 と呼ばれます。畳み込みの式として書けば、$\zeta*\mu=I$ となります。$\mu(n)$ の値はここでは保留として、本記事の終盤に改めて計算します。
数列 $\zeta$ による畳み込み $A*\zeta=B$ が成り立つとき、$B(n) = \sum_{d\mid n} A(d)$ が成り立ちます。
◆ べき乗関数
実数 $k$ に対して、数列 $N^k$ を $N^k=[1^k,2^k,3^k,4^k,\cdots]$ により定めます。対応するDirichlet級数は、$\zeta(s-k)$ と表すことができます。
◆ 約数和関数
実数 $k$ に対して、数列 $\sigma_k$ を $\sigma_k(n) = \sum_{d\mid n}d^k$ （$n$ の約数の $k$ 乗和）により定めます。$\sigma_0$ が約数の個数、$\sigma_1$ が約数の和に対応します。定義により、$\sigma_k = N^k*\zeta$ なので、$\sigma_k$ に対応するDirichlet級数は$\zeta(s)\zeta(s-k)$ となります。
◆ Euler関数
$1$ 以上 $n$ 以下で、$n$ と互いに素な整数の個数を $\varphi(n)$ と書き、Euler関数と呼びます。
$1$ 以上 $n$ 以下の数のうち、$n$との最大公約数が$d$であるものの個数が $\varphi(n/d)$ になることから、$n = \sum_{d\mid n}\varphi(n/d)$ が成り立ちます。よって $N^1 = \varphi*\zeta$ なので、$\varphi$ のDirichlet級数は $\frac{\zeta(s-1)}{\zeta(s)}$ となることが分かります。
ゼータ関数を軸として、代表的な数論関数が Dirichlet積（畳み込み）により結びついていることが観察できますね。
ゼータ変換・メビウス変換
$\zeta$ との畳み込み $A*\zeta=B$ において、$A$ から $B$ を求めることをゼータ変換、$B$ から $A$ を求めることをメビウス変換（メビウス反転）といいます。数列の要素で書けば、$B_k = \sum_{ij=k}A_i = \sum_{d\mid k}A_d$ がゼータ変換です。$B$ から $A$ を求めるには、数列 $\zeta$ のDirichlet積に関する逆元 $\mu$ をとって、$A_k = \sum_{ij=k} B_i\mu(j)$ （メビウスの反転公式）とすればよいことが分かります。
安易な方法による、これらの計算量を見積もりましょう。（$\mu(n)$ の計算は保留したままですが、一旦既知として扱います）。無限数列を直接扱うのは難しいので、ここでは自然数 $N$ をとって、
・$A_1,\ldots,A_N$ を既知として、$B_1,\ldots,B_N$ を求める。
・$B_1,\ldots,B_N$ を既知として、$A_1,\ldots,A_N$ を求める。
という問題の計算量を考えます。$ij\leq N$ となる $(i,j)$ に対して定数の計算が行われるため、計算量は $O(N\log N)$ となります。
Euler積、ゼータ変換・メビウス変換の高速化
Euler積
Riemannのゼータ関数 $\zeta(s) = \sum_{n=1}^{\infty}\frac{1}{n^s}$ に関して、次の等式が有名です：
\[\zeta(s) = \prod_p\biggl(1+\frac{1}{p^s}+\frac{1}{p^{2s}}+\cdots\biggr) = \prod_p(1-p^{-s})^{-1}\] が有名です（Euler積）。 $\prod_p$ は全ての素数 $p$ にわたる積です。 無限積は雑に取り扱うことにして、 $\prod_p\bigl(1+\frac{1}{p^s}+\frac{1}{p^{2s}}+\cdots\bigr)$ を展開すると、素因数分解の一意性より、全ての $\frac{1}{n^s}$ が一度ずつ現れることが分かります。
無限積の $p$ 部分を、$\zeta_p(s)$ と書くことにして、対応する数列も $\zeta_p$ と書くことにしましょう。畳み込みの形で書けば、$\zeta = \prod_p\zeta_p = \zeta_2*\zeta_3*\zeta_5*\cdots$ ということになります。
※ 無限積や無限個の畳み込みが登場しますが、1つ1つの項には有限個の項しか影響しないことからすべて正当化できます。ここでは雑にいきます。
Euler積だけでもかなり色々な遊び方ができますが、例えばメビウス関数の素因数による表示を求めてみましょう。メビウス関数のDirichlet級数は $1/\zeta(s)$ で、これはEuler積 $\prod_p1/\zeta_p(s) = \prod_p\bigl(1-\frac{1}{p^s}\bigr)$ を持ちます。これを展開して $\frac{1}{n^s}$ の係数が $\mu(n)$ なので、$n$ の素因数分解 $n=\prod_p p^e$ に対して $\mu(n) = \prod_p\mu_p(p^e)$, ただし $\mu_p(p^e) = \begin{cases}1&(e=0)\\-1&(e=1)\\0&(e\geq2)\end{cases}$ となることが分かります。
同様にして、約数和関数やEuler関数についても素因数分解による表示を導出することもできます。
高速ゼータ変換・高速メビウス変換
Euler積を用いると、 $\zeta$ との畳み込み $A*\zeta=B$ がごく自然に高速化されます。ここからはDirichlet級数ではなく、数列の言葉で記述してみましょう。記号のおさらいです。素数 $p$ に対して
・$\zeta_p$：$e\geq 0$ に対して $p^e$ 番目が 1 で、それ以外の項が $0$ であるような無限数列
・$\mu_p$：1番目が $1$, $p$ 番目が $-1$, それ以外の項が $0$ であるような無限数列
とします。これらは、非常に疎 (sparse) つまり$0$でない項が非常に少ないことが高速化の根拠となります。
ゼータ変換 $A*\zeta$ は次のように計算できます。
・各素数 $p=2,3,5,\ldots$ に対して、$A$ を $A*\zeta_p$ に置き換える。
ここでは畳み込みの結合法則が利用されています。$A*\zeta = A*(\prod_p\zeta_p)$ ですが、計算の順序を入れ替えても計算結果は等しいです。同じように、メビウス変換 $B*\mu$（$B=A*\mu$となる$A$を求める）は次のように計算します。
・各素数 $p=2,3,5,\ldots$ に対して、$B$ を $B*\mu_p$ に置き換える。
これらの計算量を見積もりましょう（$N$番目までを求める場合）。ゼータ変換の $p$ 部分では、各 $p\nmid n$ に対して $A_n, A_{np}, A_{np^2}, \ldots$ をその累積和に置き換わります。数列に対して $p$ の倍数部分だけを in place に変更していくことで、$p$ 部分の計算が $O(N/p)$ で行えます。メビウス変換の $p$ 部分も、$B_n, B_{np}, B_{np^2}, \ldots$ をその差分に置き換えていくことで計算できて、やはり $O(N/p)$ です。
$\sum_{p\leq x}\frac{1}{p} = O(\log \log x)$ であることが知られているため、$p$に対する計算を全て足し合わせて、ゼータ変換・メビウス変換を $O(N\log \log N)$ で計算できることが分かりました。
※ $\sum_{p\leq x}\frac{1}{p}$ の評価は、Euler積の両辺の $\log$ を $s\to 1$ の発散の様子を計算すると手に入ります。
$\zeta$ という1つの数 の分解 （半群環の元 or Dirichlet級数の分解）に基づいて、$A*\zeta$ を計算するという「操作」の分解が得られているところが面白いところで、そこに本質的に結合法則が役立っているかと思います。
まとめ、今後の課題
今回のまとめ
◆ 畳み込みは半群代数の積と考えられる
・ 数列は、「それぞれの添字をいくつ持っている」という状態と思おう。
・ 畳み込みは半群の二項演算を線形に拡張したごく自然な概念である。
・ 適当な条件下で、単位元が存在したり、結合・交換法則などが成り立ったりする。
・演算によっては形式的べき級数、Dirichlet級数などとも思えて、見やすく扱える。
◆Dirichlet級数
・自然数の積の定める半群代数というのと同じ。
・ゼータ関数を中心に、代表的な数論関数の多くがDirichlet積を通して結びつく。
・ゼータ関数との積/商が、ゼータ変換、メビウス変換と呼ばれるものの原型。
・ゼータ関数の疎な元へ分解できる（Euler積） 。これと結合法則から、ゼータ変換・メビウス変換が高速に行えることが分かる。
今後の課題（自分用メモ）
畳み込みについては競プロの文脈に限定しても、深い性質がいろいろと知られており、一気に理解しきるのは大変です。引き続き整理して少しずつ取り上げていこうと思っています。どういうタスクがあるのかを列挙だけしておきます。
◆畳み込み定理
適切な $G$ に対して半群代数 $R[G]$ は $R$ の直積と $R$ 代数同型があり、畳み込みは各点積に変換される。
・順序構造に基づくもの：ゼータ変換・メビウス変換。
・群構造（群の表現論）に基づくもの：フーリエ変換・アダマール変換。
などがある。たぶん、分けて論ずる・理解するべき。
◆変換が高速で行えること
半群代数の直積分解と、変換が高速に行えることは別の事情で、区別して理解する。
・ ゼータ変換・メビウス変換：今回の記事の内容でかなり良い線まで行っている。ただ半群代数で論ずると少し不完全。
・フーリエ変換・アダマール変換：部分群の搭を作って疎な計算へ分解する。