1
$\begingroup$

I want to know what will change if we keep on using {0,1} for our Fourier analysis of boolean functions? What are the things, which can not be performed with {0,1} and can be done with {+1, -1}?

$\endgroup$

1 Answer 1

1
$\begingroup$

You can use $\{0,1\}$ if you want, and this point of view appears in many applications, for example in combinatorics and random graph theory. What is important is that you use the Fourier basis.

Sometimes other bases are used. For example, every function $f\colon \{0,1\}^n \to \mathbb{R}$ can be expressed in the form $$ \sum_{S \subseteq [n]} \tilde{f}(S) x_S, \text{ where } x_S = \prod_{i \in S} x_i. $$ This basis is sometimes useful, but its properties differ from the Fourier basis significantly. The main source of difference is the lack of orthogonality: whereas the Fourier basis is orthogonal (with respect to the inner product $\langle f,g \rangle = 2^{-n} \sum_{x \in \{0,1\}^n} f(x) g(x)$), the basis $(x_S)_{S \subseteq [n]}$ is not. Much of the usefulness of the Fourier basis stems from its orthogonality (together with its other defining property, that $\chi_S$ depends only on the coordinates in $S$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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