Skip to main content
2 of 3
added details; Post Made Community Wiki

Characterization of Boolean-valued functions on the discrete cube based on its Fourier coefficients.

Consider functions on the discrete cube $\{-1,1\}^n$.

We consider the Discrete Fourier Transform of such functions. Suppose we denote the parity function on a subset $S \subseteq [n]$ of co-ordinates by $\Pi_S(x)=\pi_{i \in S}(x_i)$, then the Fourier coefficient $\hat{f}_S$ is simply the expectation: $\hat{f}_S=\mathbb{E}_x[f(x)\Pi_S(x)]$; and by orthonormality of the parity functions, any $f$ may be represented as $f(x)=\sum_{S \subseteq [n]}\hat{f}_S \Pi_S(x)$ (the summation being in $\mathbb{R}$.)

I am interested in knowing the difference between boolean-valued ($\{-1,1\}^n \rightarrow \{-1,1\}$) and real-valued functions ($\{-1,1\}^n \rightarrow \mathbb{R}$). More specifically, I would like to know the difference between the Fourier spectra of either class of functions.

What properties of the Fourier spectra hold for one class but not for the other?

(As an example: It can be proved that for Boolean valued functions, if all the weight is concentrated on Fourier coefficients of size at most 1 then the function is either a constant or a dictator. This is not true for real-valued functions.)