記號

• \(\otimes\) 代表或/與/異或卷積；
• \(\oplus\) 代表“拼接”，例如 \(A\oplus B\) 即將 \(B\) 接在 \(A\) 的后面；
• \(+,-,\times\) 代表按位運算，例如 \(A+B=\{a_0+b_0,a_1+b_1,...,a_n + b_n\}\)；
• \(F(A)\) 代表 \(A\) 進行 fwt 后的序列；
• \(A_0\) 代表 \(A\) 的前半部分，\(A_1\) 代表 \(A\) 的后半部分，\(A_0\oplus A_1 = A\)

或卷積

直接給出或FWT的遞歸形式：

接下來是一些性質：

• \(F(A + B) = F(A) + F(B)\)，這一點比較明顯；
• \(F(A\otimes B)=F(A) \times F(B)\)，直接證明比較麻煩，我們考慮歸納證明。

易知在 \(|A| = |B| = 1\) 時，上述結論成立。

假設已經證明了對于 \(|A| = |B| = \frac n2\) 上述結論成立，下證對于 \(|A| = |B| = n\) 成立。

首先一個簡單的分析——考慮 \(A_0\) 和 \(A_1\)，其實下標上只有最高位上 \(A_0\) 是 \(0\)，\(A_1\) 是 \(1\) 的區別。然后我們再考慮 \((A \otimes B)_0\)，既然是或卷積，最高位是 \(0\)，那肯定參與的下標都是最高位為 \(0\)，也即

稍微復雜的是 \((A \otimes B)_1\)，要求最高位至少有一個 \(1\)，也就是說

有了以上的結論就可以完成或卷積性質的證明了：

與卷積與或卷積相同。

異或卷積

同樣的，我們可以得到

然后給出異或FWT的遞歸式：

接下來是類似的歸納推導：

小記

之前推導 FWT 是正向的構造，雖然構造非常巧妙，但是不太好理解。尤其是異或卷積利用到“異或后二進制位 1 的個數的奇偶性不變”這種雖然明顯，但并不好用的性質。

現在能找到一種用歸納法證明 FWT 的方式，感覺非常直接，所以記下來了。