1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – kodlu
    Nov 23 '18 at 5:06
2
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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^{<t,a>})$ before attempting the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.