Skip to main content
1 of 3

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

Consider functions on the discrete cube $\{-1,1\}^n$. 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)