畳み込み積（convolution product）という概念があります。これは、意外に広い範囲で使えます。多項式の掛け算、正方行列の積は畳み込み積の事例です。特別な種類の正方行列、例えば上三角行列の積も畳み込み積で説明できます。形式言語理論における言語の連接も畳み込み積になります。この記事の最後のほうで、僕が出会った単純な、しかしちょっと変わった例も紹介します。
内容：
係数域（あるいは値域）となる半環
Hを半環（semiring）とします。つまり、Hは足し算と掛け算を備えた集合です。H = (H, +, 0, ・) とします。「+」は足し算で、「・」は掛け算です。0は足し算の単位元（零元）で、これは必要です。しかし、掛け算の単位元はなくてもかまいません（あっても害はありませんが）。分配法則は仮定しますが、引き算はできなくてもいいし（足し算が可換モノイド演算なら、それでよい）、掛け算が可換である必要もありません。
Hに関する仮定は、かなりゆるいですね。0以上の整数 {0. 1, 2, ...} に足し算／掛け算を考えたものはHの例です。3の倍数だけ {0, 3, 6, ...} でも足し算／掛け算がちゃんとできるのでOKです。真偽値 {true, false} に対して、ORを足し算、ANDを掛け算と考えたものもHの例です。適当な集合Uのベキ集合 H = Pow(U) において、合併を足し算、共通部分を掛け算としてもいいです。ここまでの例はすべて可換ですが、2×2行列に行列の足し算／掛け算を考えると非可換になります。これでもいいです。
半群と因数分解の有限性
Sは半群（semigroup）とします。つまり、結合的な二項演算を備えた集合です。S = (S, ・) とします。「・」はS上の二項演算です。Hの掛け算と同じ記号を使っていますが別物です。記号を乱用、あるいはオーバーロードしてるので注意してください。
a, b, c∈S に対して、(a・b)・c = a・(b・c) は要求しますが、単位元は要求しないので、半群はモノイドより弱い概念となります。可換性も仮定しません。
畳み込み積を定義するために、半群Sに条件を付けます。それは、Sの要素の「因数分解がたくさんはない」という条件です； a∈S に対して、a = x・y となる x, y をaの因数（factor、因子）と呼びます。与えられたSの元aに対して2つの因数を求めること、あるいはその結果をaの因数分解と呼びます。「因数分解がたくさんはない」とは：
- 任意の a∈ S に対して、a = x・y となる組み合わせ (x, y) は有限個しかない。
1以上の整数 {1, 2, 3, ...} に足し算を考えた半群、偶数の集合 {0, 2, 4, ...} に掛け算を考えた半群は上の条件を満たします。
畳み込み積の定義
Sは半群で「因数分解がたくさんはない」条件を満たしているとします。Hは最初に導入した係数（または値）の領域となる半環です。
S→H という関数を考えて、それらをα、βなどのギリシャ文字小文字で表します。S→H という関数の全体を Fun(S, H) と書けば、α, β∈Fun(S, H) となります。
αとβの畳み込み積 α*β は、次のように定義します。
- (α*β)(z) := Σ(z = x・y | α(x)・β(y))
定義の右辺の意味を説明します：
- Σは総和を表す記号です。
- Σ(条件 | 総和する項) という書き方をしてます。
- (z = x・y | α(x)・β(y)) は、任意の x, y に対する α(x)・α(y) ではなくて、z = x・y の条件を満たす x, y に対する α(x)・α(y) だけを足し合わせることを意味します。
- Sの二項演算と、Hの掛け算の両方に記号「・」を使っているので注意してください。
Sの要素zが与えられたとき、z = x・y となるペア (x, y) はSに関する仮定から有限個しかないので、Σ(z = x・y | α(x)・β(y)) という総和は有限和で、ｚごとに確定します。したがって、(α*β)(z) はS上でキチンと定義されます（well-defined）。
畳み込み積の性質
αとβの畳み込み積 α*β は、「積」と名付けられているので、積の法則を満たすことが期待されます。それは次のような法則です。
- (α*β)*γ = α*(β*γ)
- α*(β + γ) = α*β + α*γ
- (α + β)*γ = α*γ + β*γ
計算してみましょう。畳み込み積の定義をラムダ記法を使って、
- α*β := λz.Σ(z = x・y | α(x)・β(y))
のようにも書くことにします。角括弧（ブラケット）は丸括弧と同じですが、見やすくするために使っています。
[(α*β)*γ](w) = Σ(w = u・z | (α*β)(u)・γ(z)) = Σ(w = u・z | [λu.Σ(u = x・y | α(x)・β(y))]・γ(z)) = Σ(w = u・z, u = x・y | (α(x)・β(y))・γ(z))
最後に出てきた総和 Σ(w = u・z, u = x・y | ...) は、与えられたwをuとzに因数分解して、uのほうをさらにxとyに因数分解した組み合わせ (x, y, z) に渡る総和です。よって、次のように書き換えることができます。
- Σ(w = (x・y)・z | (α(x)・β(y))・γ(z))
同様に計算して、[α*(β*γ)](w) は、
- Σ(w = x・(y・z) | α(x)・(β(y)・γ(z)))
です。Sの二項演算もHの掛け算（どちらも記号「・」）も結合的だったの、2つの結果は一致します。
次は分配法則：
[α*(β + γ)](z) = Σ(z = x・y | α(x)・[(β + γ)(y)]) = Σ(z = x・y | α(x)・[β(y) + γ(y)]) = Σ(z = x・y | α(x)・β(y) + α(x)・γ(y)) = Σ(z = x・y | α(x)・β(y)) + Σ(z = x・y |α(x)・γ(y)) = (α*β)(z) + (α*γ)(z) = [α*β + α*γ](z)
もう一方の分配法則も同様です。
部分的な半群と圏の場合
S上の二項演算「・」が部分的にしか定義されてない状況を考えます。すべての a, b∈S に対して a・b が決まるとは限らず、a・b が未定義なことも許します。ただし、定義されている範囲内では結合法則が成り立っているとします。
このようなとき、未定義を意味する値⊥（ボトム）を導入して、S' = S + {⊥} の上で二項演算を定義します。次のように決めます。
- a・b がS上で定義されているとき、S'上でも同じ定義を採用する。
- a・b がS上では未定義のとき、S'上では、a・b = ⊥ とする。
- x∈S' がなんであっても（⊥でも）、x・⊥ = ⊥・x = ⊥ 。
S'上に定義した新しい二項演算は、S上のもとの二項演算の自然な拡張で、S'上では全域的で結合的な二項演算となります。S'に対して今までの議論を適用すれば、畳み込み積を定義できます。ただし、Fun(S', H) に属する関数 α:S'→H に次の制限を付けます。
- α(⊥) = 0
この制限のもとで、Hに値を取るS'上の関数に畳み込み積がうまく入ることの確認は練習問題ですね。
圏Cがあるとき、S = Mor(C) = (圏Cの射の全体) として、S上の二項演算として射の結合を考えます。射の結合は未定義なときもあるので、Sは部分的な半群とみなせます。S'を作れば、圏C上のH値関数の全体に畳み込み積を入れることができます。ただし、射の因数分解が有限個しかないという条件が付きます。
実例
以下、特に注意書きがなければ、半環Hは適当に選んで固定します。
非負整数 {0, 1, 2, ...} に足し算を考えた半群（この場合はモノイドになってますが）の上のH値関数に畳み込み積を入れると、H係数の形式的ベキ級数に対する掛け算になります。α(i) ≠ 0 であるiが有限個であるようなαだけを考えれば、H係数多項式の掛け算です。
{1, 2, ..., n} を頂点とする有向完全グラフをKとします。iとjを結ぶ辺を[i, j]と書いて、[i, j];[j, k] = [i, k] と定義すると、Kは圏となります。圏K上のH値関数の全体に先の方法で畳み込み積を入れると、n次の正方行列の積となります。
{1, 2, ..., n} に普通の大小順序を考えます。この順序集合を圏とみなして、同様な手順で畳み込み積を入れると、n次の三角行列の積となります
Aを記号の集合（アルファベット）として、Aから作られた自由モノイドをA*とします。A*はもちろん半群です。Hは、真偽値 {true, false} に半環構造を入れたものとします。この半群と半環を使って畳み込み積を定義すると、それはアルファベットA上の言語の連接演算になります。
最後にものすごく単純ですが、珍しい感じの例を紹介します。この例から、「畳み込み積って、一般性があるんだな」と思った次第です。Xを適当な（何でもいい）集合として、x, y∈X に対して部分的な二項演算 x・y を次のように定義します。
- x = y のとき、x・y = x
- x ≠ y のとき、x・y は未定義
これでも、部分的に定義された結合的二項演算と言えるので、適当な半環Hに対する畳み込み積が定義できます。
[追記]「圏とその他の代数構造」からリンクされているエントリー群にも似た話が。[/追記][さらに追記]因数分解が有限だという条件から、有限ベキ集合モナドのクライスリ圏において余モナドが作れることになるから、余モナド余積の双対となる積が畳み込み積なのかな。[/さらに追記]
