解析數論入門:卷積(convolution)

沒錯，大家好，又是我，TMT，前幾天我們講完了關於積性函數的概念，今天我們來聊一聊數論裡面的卷積。

卷積，又稱Dirichlet卷積，英文名叫做convolution，卷積卷積，顧名思義，是通過「卷」的方法得到的積，那麼什麼叫做卷的方法呢？

我們先看看卷積在我們這篇文裡的定義。

如果有兩個算術函數f和g，定義*為卷積符號，則h=f*g滿足：

也就是說，把n通過很多方法分成因數的乘積，然後一個因數套到f，一個因數套到g，乘在一起，再求所有的和即可。很明顯，這個求和當中，和總共有d（n）項，也就是n的因數個數這麼多項。

很明顯，h也是一個算術函數，所以說，卷積表示兩個算術函數到一個新的算術函數的運算過程，既然如此，那麼可以類比和正常的整數間的乘法一樣（比如正整數相乘以後還是正整數）。

我們在這裡稍微講點基本抽象代數的內容，關於群（group）的知識：

我們會從最大的範圍出發，逐步深入。

假設有一個集合S。

首先我們定義二元運算。二元運算是什麼呢？我們假設從S中取任意元素a和b，對於運算法則*，如果a*b一直也是一個S中的元素，我們稱*為這個集合當中的二元運算（binary operation）。

譬如說，整數範圍內，加和乘就是典型的二元運算。

我們要講的第二個名詞叫做半群（semigroup），那麼什麼是半群呢？半群說的是，如果集合S內，對於二元運算*，滿足結合律：(a*b)*c=a*(b*c)，我們就稱（S，*）構成一個半群。

很明顯，（Z，+）就是一個半群，因為有加法結合律。

那麼我們再深入一點，講一講什麼是么半群(monoid group)，一個半群要得是么半群呢，要滿足以下條件：

存在單位元素(identity element)e，使得對於S中任意元素a滿足：a*e=e*a=a（這也間接證明了交換律）。

那麼我們稱這個半群（S，*）為么半群。

么半群再深一點，那就是群（group）本身了。那麼一個元素得是群，它首先得是一個么半群。其次，它若要是一個群的話，得滿足：

對於S中任意元素a，存在逆元（inverse element）b，使得a*b=e=b*a，那麼我們稱這個么半群（S，*）是一個群（group）。

那麼假設所有的算術函數構成的集合為A，那麼很明顯，（A，*（卷積符號））構成一個群，而其中的單位函數e（n）可以如此表示：

這樣任何算術函數卷積這個函數就是它們本身了。

這次先到這裡吧，困了，過兩天再更新。

大家再見。