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

This is a good question which is the subject of intensive research in mathematics and theoretical computer science. The blog (which is the serialization of a book in progress) "Analysis of Boolean Functions" by Ryan O'Donnell is a good source, and so is the Book: Lectures on noise sensitivity and percolation by Garban and Steif.

Here is some information

1) Of course, the Fourier coefficients of real functions over the discrete cube can be arbitrary. The question is therefore what restrictions apply for Boolean functions.

Boolean functions are characterized by $f^2(x)=1$ and since product translates to convolution for the Fourier transform, being Boolean is characterized by a property of the Fourier transform convolved with itself. However, this characterization by itself is not very useful.

Parseval formula asserts that for Boolean functions the sum of square of the Fourier
coefficients is 1. It also give the following formula for the variance of $f$,
$$operatorname{var}(f) = sum { hat f^2(S): S ne emptyset } $$

2) An important tool which gives much information is Bonami (or Bonami–Gross–Beckner) inequality. It asserts that for every function $f$, $$|T_epsilon (f) |_2 le |f| _{1+epsilon^2}.$$
This implies that if $f$ has values $0$, $1$, and $-1$ and the the support of $f$ has measure $t$ then most of the Fourier spectrum of $f$ is for $S$ with $|A|> log n/10$ (say).

3) A similar reasoning gives the so called KKL's theorem. It asserts that for a Boolean function $f$ there is an index $k$ so that $$sum { hat f^2(S): S subset [n], i in S } ge operatorname{var}(f) log n/n.$$

4) A theorem of Friedgut asserts that for a Boolean function $f$ if $sum hat f^2(S) |S|$ is bounded above by a constant $c$ then $f$ is "$epsilon$-close" to a "Junta. " A Junta is a Boolean function depending on a bounded number $C$ of variables. ($C$ is a function of $c$ and $epsilon$.)

5) A theorem by Green and Sanders from the paper Boolean functions with small spectral norm, asserts that a Boolean function all whose Fourier coefficients are bounded by $M$ is a linear combination of bounded number $(le 2^{2^{O(M^4)}}$) of characteristic functions of subspaces.

6) A result by Talagrand asserts that for a Boolean functions $f_n$ if $sum_i^nhat f_n^2({i})$ is o(1) then so is $sum_i^nhat f_n^2({i})$. An extension of this result to higher levels was given by Benjamini, Kalai and Schramm, and a sharp quantitative version by Keller and Kindler.

7) A theorem of Bourgain asserts that for a Boolean function if the decay of the Fourier coefficients squared is larger than quadratic in $|S|$, then again $f$ is approximately a Junta.

8) There is a conjecture called the Entropy influence conjecture that asserts that $sum hat f^2 (S)|S|$ is bounded from below by an absolute constant times $sum hat f^2(S) log (hat f^2(S))$.