相关系数$\widehat F(w) = C(f(a)，w^ta)$与$(-1)^{f(a)}$之间的关系

Question

在“相关矩阵”中，琼·戴门等人著。在第3页中，作者声明，如果布尔函数C(f(a),w^ta)的相关系数f由\widehat F(w)表示，则\widehat f(a) = \sum_w \widehat F(w) (-1)^{w^t a},与\widehat f(a) = (-1)^{f(a)}。

有人能解释一下为什么这个公式是正确的吗？

Answer 1

Kodlu已经给出了一个提示，但是这里有一些更多的细节(因为我不认为这是家庭作业)。根据定义(或参考文件中的等式3)，

\widehat F(w)= C(f(a), w^t a) = 2^{-n} \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x) + w^t x}.

因此

\sum_{w \in \mathbb{F}_2^n} \widehat F(w) (-1)^{w^t a} = 2^{-n} \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x)} \left(\sum_{w \in \mathbb{F}_2^n} (-1)^{w^t (x + a)}\right).

无论何时x \neq a，内和都是零，否则等于2^n。因此

\sum_{w \in \mathbb{F}_2^n} \widehat F(w) (-1)^{w^t a} = \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x)} \delta_{x, a} = (-1)^{f(a)} = \widehat f(a).

我在你的参考文献中使用了同样的符号。如果您想要对这个结果有一个更全面的理解，您应该阅读(局部紧致)群上的Fourier变换。

Answer 2

该和是由有限域傅里叶变换的定义得到的。在尝试证明之前，如果您写出了C(f(a),\omega^{<t,a>})的定义，就会更清楚。