# Relation between the correlation coefficients $\widehat F(w) = C(f(a), w^ta)$ and $(-1)^{f(a)}$

In the paper Correlation Matrices by Joan Daemen et. al., the authors state (on page 3) that if the correlation coefficients $$C(f(a),w^ta)$$ of a Boolean function $$f$$ are denoted by $$\widehat F(w)$$ then $$\widehat f(a) = \sum_w \widehat F(w) (-1)^{w^t a},$$ with $$\widehat f(a) = (-1)^{f(a)}$$.

Can someone explain why this formula is correct?

• Your notation is terrible and the equations make no sense. Please write them properly, use latex (MathJax) and define things. Dot products are written as ordinary products, which is plainly wrong. Nov 23 '18 at 5:06

Kodlu already gave a hint, but here are a bit more details (since I don't think this is homework). By definition (or equation 3 in your reference),

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

Hence

$$\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).$$

The inner sum is zero whenever $$x \neq a$$ and equal to $$2^n$$ otherwise. Hence

$$\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).$$

I've used the same notation as in your reference. If you want a more general understanding of this result, you should read about Fourier transformations on (locally compact) groups.

The sum follows from the definition of the finite field Fourier transform. It would be clearer if you wrote out the definition of $$C(f(a),\omega^{})$$ before attempting the proof.